This is the technical documentation and design rationale for the new
Bitmap v2 on-disk format.
 Documentation/technical/bitmap-format.txt |  235 +++++++++++++++++++++++++++++
 1 file changed, 235 insertions(+)
 create mode 100644 Documentation/technical/bitmap-format.txt

diff --git a/Documentation/technical/bitmap-format.txt 
new file mode 100644
index 0000000..5400082
--- /dev/null
+++ b/Documentation/technical/bitmap-format.txt
@@ -0,0 +1,235 @@
+GIT bitmap v2 format & rationale
+       - A header appears at the beginning, using the same format
+       as JGit's original bitmap indexes.
+               4-byte signature: {'B', 'I', 'T', 'M'}
+               2-byte version number (network byte order)
+                       The current implementation only supports version 2
+                       of the bitmap index. The rationale for this is explained
+                       in this document.
+               2-byte flags (network byte order)
+                       The folowing flags are supported:
+                       - BITMAP_OPT_FULL_DAG (0x1) REQUIRED
+                       This flag must always be present. It implies that the 
+                       index has been generated for a packfile with full 
+                       (i.e. where every single object in the packfile can find
+                        its parent links inside the same packfile). This is a
+                       requirement for the bitmap index format, also present 
in JGit,
+                       that greatly reduces the complexity of the 
+                       - BITMAP_OPT_LE_BITMAPS (0x2)
+                       If present, this implies that that the EWAH bitmaps in 
+                       index has been serialized to disk in little-endian byte 
+                       Note that this only applies to the actual bitmaps, not 
to the
+                       Git data structures in the index, which are always in 
+                       Byte order as it's costumary.
+                       - BITMAP_OPT_BE_BITMAPS (0x4)
+                       If present, this implies that the EWAH bitmaps have 
been serialized
+                       using big-endian byte order (NWO). If the flag is 
missing, **the
+                       default is to assume that the bitmaps are in 
+                       - BITMAP_OPT_HASH_CACHE (0x8)
+                       If present, a hash cache for finding delta bases will 
be available
+                       right after the header block in this index. See the 
+                       section for details.
+               4-byte entry count (network byte order)
+                       The total count of entries (bitmapped commits) in this 
bitmap index.
+               20-byte checksum
+                       The SHA1 checksum of the pack this bitmap index belongs 
+       - An OPTIONAL delta cache follows the header.
+               The cache is formed by `n` 4-byte hashes in a row, where `n` is
+               the amount of objects in the indexed packfile. Note that this 
+               is the **total number of objects** and is not related to the
+               number of commits that have been selected and indexed in the
+               bitmap index.
+               The hashes are stored in Network Byte Order and they are the 
+               values generated by a normal revision walk during the 
+               phase.
+               The `n`nth hash in the cache is the name hash for the `n`th 
+               in the index for the indexed packfile.
+               [RATIONALE]:
+               The bitmap index allows us to skip the Counting Objects phase
+               during `pack-objects` and yield all the OIDs that would be 
+               ("WANTS") when generating the pack.
+               This optimization, however, means that we're adding objects to 
+               packfile straight from the packfile index, and hence we are 
+               path information for the objects that would normally be 
+               during the "Counting Objects" phase.
+               This path information for each object is hashed and used as a 
+               effective way to find good delta bases when compressing the 
+               without these hashes, the resulting packfiles are much less 
+               By storing all the hashes in a cache together with the bitmapsin
+               the bitmap index, we can yield not only the SHA1 of all the 
+               objects, but also their hashes, and allow Git to be much 
smarter when
+               finding delta bases for packing.
+               If the delta cache is not available, the bitmap index will 
+               be smaller in disk, but the packfiles generated using this 
index will
+               be between 20% and 30% bigger, because of the lack of name/path
+               information when finding delta bases.
+       - 4 EWAH bitmaps that act as type indexes
+               Type indexes are serialized after the hash cache in the shape
+               of four EWAH bitmaps stored consecutively (see Appendix A for
+               the serialization format of an EWAH bitmap).
+               There is a bitmap for each Git object type, stored in the 
+               order:
+                       - Commits
+                       - Trees
+                       - Blobs
+                       - Tags
+               In each bitmap, the `n`th bit is set to true if the `n`th object
+               in the packfile index is of that type.
+               The obvious consequence is that the XOR of all 4 bitmaps will 
+               in a full set (all bits sets), and the AND of all 4 bitmaps will
+               result in an empty bitmap (no bits set).
+       - N EWAH bitmaps, one for each indexed commit
+               Where `N` is the total amount of entries in this bitmap index.
+               See Appendix A for the serialization format of an EWAH bitmap.
+       - An entry index with `N` entries for the indexed commits
+               Index entries are stored consecutively, and each entry has the
+               following format:
+               - 20-byte SHA1
+                       The SHA1 of the commit that this bitmap indexes
+               - 4-byte offset (Network Byte Order)
+                       The offset **from the beginning of the file** where the
+                       bitmap for this commit is stored.
+               - 1-byte XOR-offset
+                       The xor offset used to compress this bitmap. For an 
+                       in position `x`, a XOR offset of `y` means that the 
+                       bitmap representing for this commit is composed by 
XORing the
+                       bitmap for this entry with the bitmap in entry `x-y` 
+                       the bitmap `y` entries before this one).
+                       Note that this compression can be recursive. In order to
+                       XOR this entry with a previous one, the previous entry 
+                       to be decompressed first, and so on.
+                       The hard-limit for this offset is 160 (an entry can 
only be
+                       xor'ed against one of the 160 entries preceding it). 
+                       number is always positivea, and hence entries are 
always xor'ed
+                       with **previous** bitmaps, not bitmaps that will come 
+                       in the index.
+               - 1-byte flags for this bitmap
+                       At the moment the only available flag is `0x1`, which 
+                       that this bitmap can be re-used when rebuilding bitmap 
+                       for the repository.
+               - 2 bytes of RESERVED data (used right now for better packing).
+== Rationale for changes from the Bitmap Format v1
+- Serialized EWAH bitmaps can be stored in Little-Endian byte order,
+  if defined by the BITMAP_OPT_LE_BITMAPS flag in the header.
+  The original JGit implementation stored bitmaps in Big-Endian byte
+  order (NWO) because it was unable to `mmap` the serialized format,
+  and hence always required a full parse of the bitmap index to memory,
+  where the BE->LE conversion could be performed.
+  This full parse, however, requires prohibitive loading times in LE
+  machines (i.e. all modern server hardware): a repository like
+  `torvalds/linux` can have about 8mb of bitmap indexes, resulting
+  in roughly 400ms of parse time.
+  This is not an issue in JGit, which is capable of serving repositories
+  from a single-process daemon running on the JVM, but `git-daemon` in
+  git has been implemented with a process-based design (a new
+  `pack-objects` is spawned for each request), and the boot times
+  of parsing the bitmap index every time `pack-objects` is spawned can
+  seriously slow down requests (particularly for small fetches, where we'd
+  spend about 1.5s booting up and 300ms performing the Counting Objects
+  phase).
+  By storing the bitmaps in Little-Endian, we're able to `mmap` their
+  compressed data straight in memory without parsing it beforehand, and
+  since most queries don't require accessing all the serialized bitmaps,
+  we'll only page in the minimal amount of bitmaps necessary to perform
+  the reachability analysis as they are accessed.
+- An index of all the bitmapped commits is written at the end of the packfile,
+  instead of interpersed with the serialized bitmaps in the middle of the
+  file.
+  Again, the old design implied a full parse of the whole bitmap index
+  (which JGit can afford because its daemon is single-process), but it made
+  impossible `mmaping` the bitmap index file and accessing only the parts
+  required to actually solve the query.
+  With an index at the end of the file, we can load only this index in memory,
+  allowing for very efficient access to all the available bitmaps lazily (we
+  have their offsets in the mmaped file).
+- The ordering of the objects in each bitmap has changed from
+  packfile-order (the nth bit in the bitmap is the nth object in the
+  packfile) to index-order (the nth bit in the bitmap is the nth object
+  in the INDEX of the packfile).
+  There is not a noticeable performance difference when actually converting
+  from bitmap position to SHA1 and from SHA1 to bitmap position, but when
+  using packfile ordering like JGit does, queries need to go through the
+  reverse index (pack-revindex.c).
+  Generating this reverse index at runtime is **not** free (around 900ms
+  generation time for a repository like `torvalds/linux`), and once again,
+  this generation time needs to happen every time `pack-objects` is
+  spawned.
+  With index-ordering, the only requirement for SHA1 -> Bitmap conversions
+  is the packfile index, which we essentially load for free.
+== Appendix A: Serialization format for an EWAH bitmap
+Ewah bitmaps are serialized in the protocol as the JAVAEWAH
+library, making them backwards compatible with the JGit
+       - 4-byte number of bits of the resulting UNCOMPRESSED bitmap
+       - 4-byte number of words of the COMPRESSED bitmap, when stored
+       - N x 8-byte words, as specified by the previous field
+               This is the actual content of the compressed bitmap.
+       - 4-byte position of the current RLW for the compressed
+               bitmap
+Note that the byte order for this serialization is not defined by
+default. The byte order for all the content in a serialized EWAH
+bitmap can be known by the byte order flags in the header of the
+bitmap index file.

To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to
More majordomo info at

Reply via email to