super indexes to span multiple packfiles

Dana talking about some sort of global index that spans all packfiles got me thinking. Could we build a "super index" that covered all known packfiles at the time it was created, but that doesn't really hurt us when the packfiles are repacked? Or that doesn't have to be repacked every single time a packfile is added to the repository.

This patch introduces a new command git super-index which reads all known pack-*.idx files and merges them together into a single super-index.sdx file, located in $GIT_OBJECT_DIRECTORY/pack. At runtime we load the first super-index.sdx file we come across during our packfile scanning. Using a single super-index works because the super-index.sdx should contain data for this repository's packs, and for all of its alternate's packs.

A super-index holds a list of packfile names that it will match at the start of its data file. A super-index can only be used for the pack(s) mentioned there. At runtime we try to lazily match these pack SHA-1 names up to the struct packed_git.sha1 field, giving us the struct packed_git* for direct index access.

The super-index does not hold the object offsets; instead it holds an array of percentage shifts within the index fan-out ranges. The shifts are normalized into the range 1-65535.

The basic idea is:

1) Use the first byte of the input SHA-1 to index into the fan-out table of the super-index.sdx.

2) Use the next sdx_prefix bytes of the SHA-1 to binary search through that region of the sdx file. Since we are working only with the abbreviated prefix the memcmp() has less data to wade through. We've also eliminated the common first byte, thanks to the fan-out table.

3) The matching record in the sdx table holds sdx_packs uint16_t values. The indexes in that list corresponding to the index of the pack SHA-1 names in the header of the sdx file; hence the first uint16_t goes to the first packfile, the second to the second, etc. I call these "shifts". I don't know why.

4) If the shift value for a pack is 0 then that pack does not contain any objects that start with that prefix. So a 0 shift means we do not need to scan the corresponding pack's .idx file for an object.

5) If the shift is non-zero then there is at least one object in the corresponding packfile starting with the prefix and further searching in the specific packfile is required. The shift is actually the percentage within the range of [lo, hi) in the pack's .idx of where the middle of that prefix's block appears. We use this as a seed value for mi, rather than (lo+hi)/2, as it gets us much much closer to the interesting SHA-1s in the .idx.

6) We binary search the .idx in a traditional way, once we have selected a reasonable guess for the starting position.

7) If a packfile cannot be found at runtime (e.g. it has been repacked away) we treat it's shift as though it were 0; the object is not in that packfile (since the packfile does not exist).

8) If the sdx cannot give us the object, we fallback to standard packfile scanning.

In the single packfile case (everything repacked into one) this is not faster; its actually slightly slower. With a handful of smaller recent packfiles (such as immediately after a git-fetch) it breaks even with the stock code. I haven't tested it yet with a high number of packfiles (e.g. 20). I suspect it won't gain us a lot up there either...

So in short this shouldn't be applied, because its not any faster, and is sometimes slower. But I'm tossing it out here for discussion. I'm also not documenting the new super-index command line program, because I don't think this should be applied. ;-)

----

 .gitignore             |    1 +
 Makefile               |    1 +
 builtin-pack-objects.c |    2 +-
 builtin-super-index.c  |  226 ++++++++++++++++++++++++++++++++++++++++++++++++
 builtin.h              |    1 +
 cache.h                |    2 +-
 git.c                  |    1 +
 pack-check.c           |    4 +-
 pack.h                 |   17 ++++
 sha1_file.c            |  208 ++++++++++++++++++++++++++++++++++++--------
 10 files changed, 423 insertions(+), 40 deletions(-)
 create mode 100644 builtin-super-index.c

index 4dc0c39..3cd1b2c 100644
@@ -126,6 +126,7 @@ git-ssh-push
 git-ssh-upload
 git-status
 git-stripspace
+git-super-index
 git-svn
 git-svnimport
 git-symbolic-ref

index 29243c6..26ac766 100644
@@ -371,6 +371,7 @@ BUILTIN_OBJS = \
 	builtin-shortlog.o \
 	builtin-show-branch.o \
 	builtin-stripspace.o \
+	builtin-super-index.o \
 	builtin-symbolic-ref.o \
 	builtin-tar-tree.o \
 	builtin-unpack-objects.o \

index d165f10..3b49336 100644
@@ -756,7 +756,7 @@ static int add_object_entry(const unsigned char *sha1, enum object_type type,
 	}
 
 	for (p = packed_git; p; p = p->next) {
-		off_t offset = find_pack_entry_one(sha1, p);
+		off_t offset = find_pack_entry_one(sha1, p, 0);
 		if (offset) {
 			if (!found_pack) {
 				found_offset = offset;

index d3f3a74..2a11187 100644
@@ -71,6 +71,7 @@ extern int cmd_shortlog(int argc, const char **argv, const char *prefix);
 extern int cmd_show(int argc, const char **argv, const char *prefix);
 extern int cmd_show_branch(int argc, const char **argv, const char *prefix);
 extern int cmd_stripspace(int argc, const char **argv, const char *prefix);
+extern int cmd_super_index(int argc, const char **argv, const char *prefix);
 extern int cmd_symbolic_ref(int argc, const char **argv, const char *prefix);
 extern int cmd_tar_tree(int argc, const char **argv, const char *prefix);
 extern int cmd_unpack_objects(int argc, const char **argv, const char *prefix);

index 0f4a05b..3c8a41d 100644
@@ -490,7 +490,7 @@ extern unsigned char* use_pack(struct packed_git *, struct pack_window **, off_t
 extern void unuse_pack(struct pack_window **);
 extern struct packed_git *add_packed_git(const char *, int, int);
 extern const unsigned char *nth_packed_object_sha1(struct packed_git *, uint32_t);
-extern off_t find_pack_entry_one(const unsigned char *, struct packed_git *);
+extern off_t find_pack_entry_one(const unsigned char *, struct packed_git *, unsigned);
 extern void *unpack_entry(struct packed_git *, off_t, enum object_type *, unsigned long *);
 extern unsigned long unpack_object_header_gently(const unsigned char *buf, unsigned long len, enum object_type *type, unsigned long *sizep);
 extern unsigned long get_size_from_delta(struct packed_git *, struct pack_window **, off_t);

index 29b55a1..c323479 100644
@@ -284,6 +284,7 @@ static void handle_internal_command(int argc, const char **argv, char **envp)
 		{ "show-branch", cmd_show_branch, RUN_SETUP },
 		{ "show", cmd_show, RUN_SETUP | USE_PAGER },
 		{ "stripspace", cmd_stripspace },
+		{ "super-index", cmd_super_index, RUN_SETUP },
 		{ "symbolic-ref", cmd_symbolic_ref, RUN_SETUP },
 		{ "tar-tree", cmd_tar_tree },
 		{ "unpack-objects", cmd_unpack_objects, RUN_SETUP },

index 7475348..ec61592 100644
@@ -51,7 +51,7 @@ static int verify_packfile(struct packed_git *p,
 		sha1 = nth_packed_object_sha1(p, i);
 		if (!sha1)
 			die("internal error pack-check nth-packed-object");
-		offset = find_pack_entry_one(sha1, p);
+		offset = find_pack_entry_one(sha1, p, 0);
 		if (!offset)
 			die("internal error pack-check find-pack-entry-one");
 		data = unpack_entry(p, offset, &type, &size);

@@ -94,7 +94,7 @@ static void show_pack_info(struct packed_git *p)
 		sha1 = nth_packed_object_sha1(p, i);
 		if (!sha1)
 			die("internal error pack-check nth-packed-object");
-		offset = find_pack_entry_one(sha1, p);
+		offset = find_pack_entry_one(sha1, p, 0);
 		if (!offset)
 			die("internal error pack-check find-pack-entry-one");
 

index d667fb8..b660833 100644
@@ -43,6 +43,23 @@ struct pack_idx_header {
 };
 
 
+/*
+ * Super-pack index header
+ *
+ * This file points to multiple packfiles by name and provides a
+ * hint to tell us if it is likely that a given packfile contains
+ * a particular object.  This file is not an index file replacement,
+ * it is only a performance optimization hint.
+ */
+#define PACK_SDX_SIGNATURE 0x50534458	/* "PSDX" */
+struct pack_sdx_header {
+	uint32_t sdx_signature;
+	uint32_t sdx_version;
+	uint16_t sdx_packs;
+	uint8_t  sdx_prefix;
+	uint8_t  _unused_padding;
+};
+
 extern int verify_pack(struct packed_git *, int);
 extern void fixup_pack_header_footer(int, unsigned char *, const char *, uint32_t);
 

1.5.2.838.g8a923

Object's are not accessed in random order with git. Once an object reference hits a pack file it is very likely that following references will hit the same pack file. That's because you always find object SHA's by following the chains.

So first place to look for an object is the same place the previous object was found. If it isn't there order the search of the pack files by creation data (just a heuristic). Make this list a circle and start the search in the pack where the previous object was found. This can all be done with the existing indexes.

I haven't been reading all of the messages on this subject, but is this strategy enough to eliminate the need for a super index?

If you still need a super index, note that it may be good enough for it to only contain the SHA's for objects that are externally referenced. This index would be small and simply point to the correct pack file index to find the object in. You could add a list of dangling links to each packfile index to assist with building this super index.

My work with databases leads me to believe that figuring out how to pack everything into a smaller space always beats efforts put into incrementally improving the indexing scheme. Packing into a smaller space reduces the total IO needs and that's always a winner.

Jon Smirl
[email protected]

Another way to achieve that is to place objects that are accessed together nearby, and issue a larger read so as to bring them into cache. I imagine that placing commit objects and associated tree and blobs in history order should help here (but maybe git already does that, I'm not familiar with the internals).

error compiling committee.c: too many arguments to function

GIT already does that indeed, except for commit objects which are all together for better performances on history traversal operations.

After a fresh repack, the checkout of the latest revision should produce a nearly perfect linear and contigous access into the early portion of the same pack. Things will get more random with access to objects further back in history of course, but those objects are less likely to be accessed as often.

Nicolas

Thanks. Actually I should have deduced this from the speed of 'git log' ;-)

error compiling committee.c: too many arguments to function

I think it could.

Personally I'm not a big fan of the super index notion. It needs extra maintenance to keep in synch, and when it is not in synch it requires extra work at run time to fall back to traditional lookup. And Shawn's testing didn't provide significant performance gains either.

But a simple heuristic like the presumption that the next object is likely to be in the same pack as the previous is the kind of thing that could provide significant improvements with really little effort.

Nicolas

[resent, my email client doesn't like Shawn's name :( ]

A super-index should have a fan-out factor dependent on the number of entries in the index. So an index with 2^20 entries would have 2^16 fan-outs. So there will be about 2^4 entries per fanout slot. Each slot only contains the next byte of the key, so in this case bit 16 through 23 (numbering bits starting at zero).

The format would look like:
* Header
* Fan-out table (approx 2 bits/object)
* Next key-byte table (1 byte/object)
* Object info (offset into packfile(s) and/or rest of object name)

So, after a single lookup to get to about the right entry, only an expected 16 single-byte comparisons are necessary to find the entry that is needed or return a "entry doesn't exist".

Below I repeat a previous suggestion for a new pack file index. I'm happy to implement this, although it seems that there are so many pending index/pack file format changes that this may be premature. If the pack file itself will have the full SHA-1, the

(snipped from <http://article.gmane.org/gmane.comp.version-control.git/43545>)

Multiple Pack Index

The linear search through packs is very inefficient with large numbers of packs. Having packs much larger than a GB is also problematic, due to this as repacking and otherwise modifying packs gets very expensive.

Another issue is that binary search requires many semi-random accesses spread over the index. Finally, most of the information actually read consists of SHA1's that are never needed.

This proposed pack index format does not focus on reducing used disk space, but instead aims to reduce the number of blocks that needs to be read to perform lookups. This is done using three techniques:
1) scale the number of fan-out bins with the number of objects in the index, keeping the expected number of objects in each bin constant
2) take advantage of 1) by only storing a few bits following the common prefix in the main lookup table as a discriminant. Store the rest of the SHA1 and the pack offest in a separate, parallel, object table.
3) Instead of repeating the variable-length common prefix and the discriminant, use the space for the prefix for a pack identifier and omit the discriminant altogether.

For a repository with N objects and highest PACK_NR P, the total space used for the index is bounded by 24 * (N + P) bytes, if N is at least 512 and N >= 512 * P.

Limits:
- Maximum number of packs: 2^27
- Maximum number of objects: 2^40
- Maximum repository size: 2^48 bytes

<PACK_INDEX>
: <IDX_PACK_LIST>
<IDX_FANOUT_BITS>
<IDX_FANOUT_TABLE>
<IDX_LOOKUP_TABLE>
<IDX_OBJECT_TABLE>
<IDX_CHECKSUM>
;

<IDX_PACK_LIST>
: <IDX_PACK_LIST_ENTRIES>

       <ZERO_32> <IDX_PACK_LIST_CHECKSUM>

;
<IDX_PACK_LIST_ENTRIES>
# List of packs sorted by ascending PACK_ID
: ( <IDX_PACK_NR> <PACK_ID> ) *
;

<PACK_ID>
# 20-byte binary representation of the 40 hex-digit

   # value PACK_ID_HEX, such that pack-${PACK_ID_HEX}.pack
   # is the name of the pack file
   ;

<IDX_PACK_NR>
# 32-bit unsigned integer in network order, with the same

   # value as the preceding <IDX_PACK_NR> (or zero for the
   # first entry), increased by the size of the pack file in
   # bytes, divided by 2^32 and rounded up.
   ;

<ZERO_32>
# 32-bit zero
;

<IDX_PACK_LIST_CHECKSUM>
# 20-byte SHA1 of <IDX_PACK_LIST_ENTRIES>
;

<IDX_FANOUT_BITS>
# 1 byte with the smallest value N between 8 and 35,

   # such that 2^(N - 8) greater than or equal to the
   # largest IDX_PACK_NR in the IDX_PACK_LIST, and such that
   # 2^(N+5) is greater than or equal to the total number
   # of objects in all packs.
   ;

<IDX_FANOUT_TABLE>
# Table of 2^${IDX_FANOUT_BITS} entries
: ( <IDX_PARTIAL_COUNT> ) *
;

<IDX_PARTIAL_COUNT>
# 40 bit, network byte order, binary integer of the count of

   # objects in the pack file with the high IDX_FANOUT_BITS bits of
   # the object ID less than or equal to the index of the count,
   # starting from zero.
   ;

<IDX_LOOKUP_TABLE>
# One 8-bit key per object indexed by the pack
: ( <IDX_LOOKUP_KEY> ) *
;

<IDX_LOOKUP_KEY>
# Bits IDX_FANOUT_BITS through IDX_FANOUT_BITS + 7 of the

   # object ID.
   ;

<IDX_OBJECT_ENTRY>
# The total width of each entry is 22 bytes
: ( <IDX_PACK_REF> <IDX_OBJECT_ID> <IDX_OFFSET> ) *
;

<IDX_PACK_REF>
# A IDX_FANOUT_BITS - 8 bit wide integer value, equal to # PACK_NR of pack preceding the one containing the object # (or zero, if object is in first pack) increased with the

   # pack offset divided by 2^32.
   ;

<IDX_OBJECT_ID>
# Bits IDX_FANOUT_BITS + 8 .. 159 of the object ID ;

<IDX_OFFSET>
# 32-bits offset in network byte order
;