Re: GSoC - Designing a faster index format

On Mon, Apr 02, 2012 at 09:50:53PM +1000, elton sky wrote:

In current index, tree is implied in path names. We only store blob sha-1.

We don't store blobs in index. We only need their sha-1, which is computed and content stored in object database at "git add".

By the way, I revised my new index format a little bit, see the end of this email. It may work, or may not. Food for thoughts.

I think so. But until we can read just parts of index, we still have to verify integrity for the whole index, which takes more or less the same amount of time you see and should be proportional to index size (or the number of entries in index). Either we shrink the index, or go with cheaper checksum, or both.

{read,fill}_directory is not always used (for example, "git diff" does not need it). Meanwhile, as working directory grows, index size grows, verify_hdr() will take longer.

I think fill_directory is dominated by kernel time (read_dir, stat...), there's little thing we can do there. Anyway I'm pretty sure fill_directory is out of scope. It's just one of the code that uses index.

-- 8< -- GIT index format ================

This format replaces the old "DIRC" format. Compared to the old format, which is essentially a sorted list of pathnames, this one:

 - is tree-based
 - use crc32 as checksum
 - only verify integrity on parts that git accesses, instead of whole
   file
 - append changes to the end
 - allow index versioning

Updates can be made directly to the index by appending to the end. The index traversed by locating the root tree block from the trailer. When a path is updated, all related tree blocks are updated and appended to the end, then a new trailer (with generation increased by one) is written to conclude the index.

The index size will increase continuously. At some point, we will need to repack it. Let assume a tree block is 64k on average and a path generally consists of 3 path components. That means an entry update adds 192k and we can do about 80 updates before index reaches 16M (in addition to initial index size).

At 16M or when trailer generation hits a limit (the limit can be configurable), we rewrite the index to reduce its size. Some heavy operations can also be used to rewrite index, such as checkout or reset.

The index integrity is verified by crc32. One crc32 covers header and trailer. Each block has its own crc32. When the index is found corrupt, we could try to roll back to latest good version by looking for trailers from bottom up. Even when the index is not corrupt, users can still look back this way for older index versions.

= The git index file has the following format

   - A 8-byte header consisting of

     4-byte signature:
       The signature is { 'T', 'R', 'E', 'E' }

     4-byte version number:
       The current supported versions are 1.

   - A number of blocks of variable size

      1-byte block type

      3-byte content size in byte

      block content

      4-byte crc32 of all above

   - A 18-byte trailer consisting of

      4-byte trailer signature:
        The signature is { 'R', 'O', 'O', 'T' }

      2-byte generation:
         The first trailer is 0, the second 1 and so on.

      4-byte root block offset

      4-byte extension table offset:
        Zero means no extension

      4-byte checksum:
        CRC32 of the header and the trailer (excluding this field)

== Tree block

  A tree block contains a (maybe invalid) tree object and extra
  information of its companion in working directory. Tree block has
  block type 'T'.

  Tree block content is basically the list of non-recursive entries in
  specified path, with all attributes we store in the index now. There
  are a few changes though to intergrate cache-tree and allow
  bsearch() on mmap'd block.

  A tree block content consists of

  - 4-byte tree object size

  - 20-byte SHA-1 of the cached tree object

  - a list attributes corresponding to tree object's item, in the same
    order.  These attributes are the same as in DIRC entry format
    except that entry name is removed, and a tree block offset is
    added in case the item is a directory.

    32-bit ctime seconds, the last time a file's metadata changed
      this is stat(2) data
  
    32-bit ctime nanosecond fractions
      this is stat(2) data
  
    32-bit mtime seconds, the last time a file's data changed
      this is stat(2) data
  
    32-bit mtime nanosecond fractions
      this is stat(2) data
  
    32-bit dev
      this is stat(2) data
  
    32-bit ino
      this is stat(2) data
  
    32-bit mode, split into (high to low bits)
  
      4-bit object type
        valid values in binary are 1000 (regular file), 1010 (symbolic link)
        and 1110 (gitlink)
  
      3-bit unused
  
      9-bit unix permission. Only 0755 and 0644 are valid for regular files.
      Symbolic links and gitlinks have value 0 in this field.
  
    32-bit uid
      this is stat(2) data
  
    32-bit gid
      this is stat(2) data
  
    32-bit file size
      This is the on-disk size from stat(2), truncated to 32-bit.
  
    160-bit SHA-1 for the represented object if blobs or the offset
      to another tree block if trees

    A 32-bit 'flags' field split into (high to low bits)
  
      1-bit assume-valid flag
  
      1-bit extended flag (must be zero in version 2)
  
      2-bit stage (during merge)
  
      12-bit name length if the length is less than 0xFFF; otherwise 0xFFF
      is stored in this field.
  
      1-bit skip-worktree flag (used by sparse checkout)
  
      1-bit intent-to-add flag (used by "git add -N")

      14-bit unused, must be zero

    A 16-bit offset, relative to the beginning of this block, to the
      pathname of this entry. FIXME: make it 32-bit, relative to the
      beginning of the file, so that we can reuse pathnames from other
      (old) blocks?

  - a list of NUL-terminated pathnames, pointed to from the 16-bit offset
    above. This list does not have to be of the same order as the attribute
    list. The reason this is separated from the attribute list is to make
    attribute list fixed size, searchable using bsearch().

== Extension table block

 Extension table has block type 'X'. It consists of a series of 4-byte
 extension block offset.

== Extension block

 Extension block has block type 'E'. Extension content is the same as
 in the old format.
-- 8< --
--
Duy