Re: GSoC - Designing a faster index format

[elton sky <eltonsky9404@gmail.com>]

Hi Nguyen,

On Mon, Mar 26, 2012 at 12:06 PM, Nguyen Thai Ngoc Duy
<pclouds@gmail.com> wrote:
> (I think this should be on git@vger as there are many experienced devs there)
>
> On Sun, Mar 25, 2012 at 11:13 AM, elton sky <eltonsky9404@gmail.com> wrote:
>> About the new format:
>>
>> The index is a single file. Entries in the index still stored
>> sequentially as old format. The difference is they are grouped into
>> blocks. A block contains many entries and they are ordered by names.
>> Blocks are also ordered by the name of the first entry. Each block
>> contains a sha1 for entries in it.
>
> If I remove an entry in the first block, because blocks are of fixed
> size, you would need to shift all entries up by one, thus update all
> blocks?
>

We need some GC here. I am not moving all blocks. Rather I would
consider merge or recycle the block. In a simple case if a block
becomes empty, I ll change the offset of new block in the header point
to this block, and make this block points to the original offset of
new block. In this way, I keep the list of empty blocks I can reuse.
If a block is not empty but not full, we better merge it with adjacent
block for efficiency. But I don't know an light way to handle that
when refreshing index. But we can always run a background thread to
rebuild the index, at some stage, while system is quiet.

> Also note the sequence format means duplication because we always
> store full path.

You are right, this keeps the size of the index as current system. Use
a tree will save disk space for sure. Need think more about this.

> --
> Duy

Attach my previous email here:

The goal of this project is :
1. verify checksum for only necessary part of index
2. keep the time complexity of most git-app below logn

About the new format:

The index is a single file. Entries in the index still stored
sequentially as old format. The difference is they are grouped into
blocks. A block contains many entries and they are ordered by names.
Blocks are also ordered by the name of the first entry. Each block
contains a sha1 for entries in it.
For using a binary search to locate the block for an entry, the
offsets of blocks are stored in the header of the index. We reserve
100 spaces for block offsets in the header. More offsets are stored in
a meta block (see below) afterwards. An offset of the first meta block
is stored.
The checksum is computed on block. After we locate the block, the
checksum is recomputed for the block. And only the this block will be
read and write back later. As the block is read into ram, it is easy
to do a binary search for entries in a block when they are in ram.
When the index doesn't have many entries, it works very similar with
current format. When more entries git-added, blocks will come into
play.

Format:

Head:
* 4-byte signature
* 4-byte version num
* 4-byte num of entries blocks
* 4-byte offset for new block
* list of offsets for blocks (e.g. 96, 14096, 8192, ..) : For binary
search. Each offset is 8 bytes, we reserve 100 x 4 = 400 bytes for
first 100 blocks. More offsets (if applicable) will be stored in a
meta blocks.
* 4-byte offset to the first meta block
* 20-byte sha1 for above and meta blocks

List of Blocks:
* sha1 for all entries
* list of entries

Meta block:
* offset to next meta block
* list of offsets

Extensions:
      TBD. Have not hacked cache tree yet. Need more knowledge of cache tree...


Block Split & Delete:
      TBD.


-Elton