Required information

For a given groupcompress record, we need to know the offset and length of the compressed group in the .pack file, and the start and end of the content inside the uncompressed group. The absolute minimum is slightly less, but this is a good starting point. The other thing to consider, is that for 1M revisions and 1M files, we’ll probably have 10-20M CHK pages, so we want to make sure we have an index that can scale up efficiently.

1. A compressed sha hash is 20-bytes
2. Pack files can be > 4GB, we could use an 8-byte (64-bit) pointer, or we could store a 5-byte pointer for a cap at 1TB. 8-bytes still seems like overkill, even if it is the natural next size up.
3. An individual group would never be longer than 2^32, but they will often be bigger than 2^16. 3 bytes for length (16MB) would be the minimum safe length, and may not be safe if we expand groups for large content (like ISOs). So probably 4-bytes for group length is necessary.
4. A given start offset has to fit in the group, so another 4-bytes.
5. Uncompressed length of record is based on original size, so 4-bytes is expected as well.
6. That leaves us with 20+8+4+4+4 = 40 bytes per record. At the moment, btree compression gives us closer to 38.5 bytes per record. We don’t have perfect compression, but we also don’t have >4GB pack files (and if we did, the first 4GB are all under then 2^32 barrier :).

If we wanted to go back to the ‘’minimal’’ amount of data that we would need to store.

1. 8 bytes of a sha hash are generally going to be more than enough to fully determine the entry (see Partial hash). We could support some amount of collision in an index record, in exchange for resolving it inside the content. At least in theory, we don’t have to record the whole 20-bytes for the sha1 hash. (8-bytes gives us less than 1 in 1000 chance of a single collision for 10M nodes in an index)

2. We could record the start and length of each group in a separate location, and then have each record reference the group by an ‘offset’. This is because we expect to have many records in the same group (something like 10k or so, though we’ve fit >64k under some circumstances). At a minimum, we have one record per group so we have to store at least one reference anyway. So the maximum overhead is just the size and cost of the dereference (and normally will be much much better than that.)

3. If a group reference is an 8-byte start, and a 4-byte length, and we have 10M keys, but get at least 1k records per group, then we would have 10k groups. So we would need 120kB to record all the group offsets, and then each individual record would only need a 2-byte group number, rather than a 12-byte reference. We could be safe with a 4-byte group number, but if each group is ~1MB, 64k groups is 64GB. We can start with 2-byte, but leave room in the header info to indicate if we have more than 64k group entries. Also, current grouping creates groups of 4MB each, which would make it 256GB, to create 64k groups. And our current chk pages compress down to less than 100 bytes each (average is closer to 40 bytes), which for 256GB of raw data, would amount to 2.7 billion CHK records. (This will change if we start to use CHK for text records, as they do not compress down as small.) Using 100 bytes per 10M chk records, we have 1GB of compressed chk data, split into 4MB groups or 250 total groups. Still << 64k groups. Conversions could create 1 chk record at a time, creating a group for each, but they would be foolish to not commit a write group after 10k revisions (assuming 6 CHK pages each).

4. We want to know the start-and-length of a record in the decompressed stream. This could actually be moved into a mini-index inside the group itself. Initial testing showed that storing an expanded “key => start,offset” consumed a considerable amount of compressed space. (about 30% of final size was just these internal indices.) However, we could move to a pure “record 1 is at location 10-20”, and then our external index would just have a single ‘group entry number’.

   There are other internal forces that would give a natural cap of 64k entries per group. So without much loss of generality, we could probably get away with a 2-byte ‘group entry’ number. (which then generates an 8-byte offset + endpoint as a header in the group itself.)

5. So for 1M keys, an ideal chk+group index would be:

   1. 6-byte hash prefix
   2. 2-byte group number
   3. 2-byte entry in group number
   4. a separate lookup of 12-byte group number to offset + length
   5. a variable width mini-index that splits X bits of the key. (to maintain small keys, low chance of collision, this is not redundant with the value stored in (a)) This should then dereference into a location in the index. This should probably be a 4-byte reference. It is unlikely, but possible, to have an index >16MB. With an 10-byte entry, it only takes 1.6M chk nodes to do so. At the smallest end, this will probably be a 256-way (8-bits) fan out, at the high end it could go up to 64k-way (16-bits) or maybe even 1M-way (20-bits). (64k-way should handle up to 5-16M nodes and still allow a cheap <4k read to find the final entry.)

So the max size for the optimal groupcompress+chk index with 10M entries would be:

10 * 10M (entries) + 64k * 12 (group) + 64k * 4 (mini index) = 101 MiB

So 101MiB which breaks down as 100MiB for the actual entries, 0.75MiB for the group records, and 0.25MiB for the mini index.

1. Looking up a key would involve:

   1. Read XX bytes to get the header, and various config for the index. Such as length of the group records, length of mini index, etc.

   2. Find the offset in the mini index for the first YY bits of the key. Read the 4 byte pointer stored at that location (which may already be in the first content if we pre-read a minimum size.)

   3. Jump to the location indicated, and read enough bytes to find the correct 12-byte record. The mini-index only indicates the start of records that start with the given prefix. A 64k-way index resolves 10MB records down to 160 possibilities. So at 12 bytes each, to read all would cost 1920 bytes to be read.

   4. Determine the offset for the group entry, which is the known start of groups location + 12B*offset number. Read its 12-byte record.

   5. Switch to the .pack file, and read the group header to determine where in the stream the given record exists. At this point, you have enough information to read the entire group block. For local ops, you could only read enough to get the header, and then only read enough to decompress just the content you want to get at.

      Using an offset, you also don’t need to decode the entire group header. If we assume that things are stored in fixed-size records, you can jump to exactly the entry that you care about, and read its 8-byte (start,length in uncompressed) info. If we wanted more redundancy we could store the 20-byte hash, but the content can verify itself.

   6. If the size of these mini headers becomes critical (8 bytes per record is 8% overhead for 100 byte records), we could also compress this mini header. Changing the number of bytes per entry is unlikely to be efficient, because groups standardize on 4MiB wide, which is >>64KiB for a 2-byte offset, 3-bytes would be enough as long as we never store an ISO as a single entry in the content. Variable width also isn’t a big win, since base-128 hits 4-bytes at just 2MiB.

      For minimum size without compression, we could only store the 4-byte length of each node. Then to compute the offset, you have to sum all previous nodes. We require <64k nodes in a group, so it is up to 256KiB for this header, but we would lose partial reads. This should still be cheap in compiled code (needs tests, as you can’t do partial info), and would also have the advantage that fixed width would be highly compressible itself. (Most nodes are going to have a length that fits 1-2 bytes.)

      An alternative form would be to use the base-128 encoding. (If the MSB is set, then the next byte needs to be added to the current value shifted by 7*n bits.) This encodes 4GiB in 5 bytes, but stores 127B in 1 byte, and 2MiB in 3 bytes. If we only stored 64k entries in a 4 MiB group, the average size can only be 64B, which fits in a single byte length, so 64KiB for this header, or only 1.5% overhead. We also don’t have to compute the offset of all nodes, just the ones before the one we want, which is the similar to what we have to do to get the actual content out.

Partial Hash

The size of the index is dominated by the individual entries (the 1M records). Saving 1 byte there saves 1MB overall, which is the same as the group entries and mini index combined. If we can change the index so that it can handle collisions gracefully (have multiple records for a given collision), then we can shrink the number of bytes we need overall. Also, if we aren’t going to put the full 20-bytes into the index, then some form of graceful handling of collisions is recommended anyway.

The current structure does this just fine, in that the mini-index dereferences you to a “list” of records that start with that prefix. It is assumed that those would be sorted, but we could easily have multiple records. To resolve the exact record, you can read both records, and compute the sha1 to decide between them. This has performance implications, as you are now decoding 2x the records to get at one.

The chance of n texts colliding with a hash space of H is generally given as:

1 - e ^(-n^2 / 2 H)

Or if you use H = 2^h, where h is the number of bits:

1 - e ^(-n^2 / 2^(h+1))

For 1M keys and 4-bytes (32-bit), the chance of collision is for all intents and purposes 100%. Rewriting the equation to give the number of bits (h) needed versus the number of entries (n) and the desired collision rate (epsilon):

h = log_2(-n^2 / ln(1-epsilon)) - 1

The denominator ln(1-epsilon) == -epsilon` for small values (even @0.1 == -0.105, and we are assuming we want a much lower chance of collision than 10%). So we have:

h = log_2(n^2/epsilon) - 1 = 2 log_2(n) - log_2(epsilon) - 1

Given that epsilon will often be very small and n very large, it can be more convenient to transform it into epsilon = 10^-E and n = 10^N, which gives us:

h = 2 * log_2(10^N) - 2 log_2(10^-E) - 1
h = log_2(10) (2N + E) - 1
h ~ 3.3 (2N + E) - 1

Or if we use number of bytes h = 8H:

H ~ 0.4 (2N + E)

This actually has some nice understanding to be had. For every order of magnitude we want to increase the number of keys (at the same chance of collision), we need ~1 byte (0.8), for every two orders of magnitude we want to reduce the chance of collision we need the same extra bytes. So with 8 bytes, you can have 20 orders of magnitude to work with, 10^10 keys, with guaranteed collision, or 10 keys with 10^-20 chance of collision.

Putting this in a different form, we could make epsilon == 1/n. This gives us an interesting simplified form:

h = log_2(n^3) - 1 = 3 log_2(n) - 1

writing n as 10^N, and H=8h:

h = 3 N log_2(10) - 1 =~ 10 N - 1
H ~ 1.25 N

So to have a one in a million chance of collision using 1 million keys, you need ~59 bits, or slightly more than 7 bytes. For 10 million keys and a one in 10 million chance of any of them colliding, you can use 9 (8.6) bytes. With 10 bytes, we have a one in a 100M chance of getting a collision in 100M keys (substituting back, the original equation says the chance of collision is 4e-9 for 100M keys when using 10 bytes.)

Given that the only cost for a collision is reading a second page and ensuring the sha hash actually matches we could actually use a fairly “high” collision rate. A chance of 1 in 1000 that you will collide in an index with 1M keys is certainly acceptible. (note that isn’t 1 in 1000 of those keys will be a collision, but 1 in 1000 that you will have a single collision). Using a collision chance of 10^-3, and number of keys 10^6, means we need (12+3)*0.4 = 6 bytes. For 10M keys, you need (14+3)*0.4 = 6.8 aka 7. We get that extra byte from the mini-index. In an index with a lot of keys, you want a bigger fan-out up front anyway, which gives you more bytes consumed and extends your effective key width.

Also taking one more look at H ~ 0.4 (2N + E), you can rearrange and consider that for every order of magnitude more keys you insert, your chance for collision goes up by 2 orders of magnitude. But for 100M keys, 8 bytes gives you a 1 in 10,000 chance of collision, and that is gotten at a 16-bit fan-out (64k-way), but for 100M keys, we would likely want at least 20-bit fan out.

You can also see this from the original equation with a bit of rearranging:

epsilon = 1 - e^(-n^2 / 2^(h+1))
epsilon = 1 - e^(-(2^N)^2 / (2^(h+1))) = 1 - e^(-(2^(2N))(2^-(h+1)))
        = 1 - e^(-(2^(2N - h - 1)))

Such that you want 2N - h to be a very negative integer, such that 2^-X is thus very close to zero, and 1-e^0 = 0. But you can see that if you want to double the number of source texts, you need to quadruple the number of bits.

Scaling Sizes

Other discussion