Re: reftable [v4]: new ref storage format

From: Shawn Pearce <spearce@spearce.org>
Date: Aug 5, 2017, 21:00 UTC
Message-ID: <CAJo=hJszDQ2N8cAjSqbJTTja03ke=i5H323U2Af+sZhviG9m-A@mail.gmail.com>
In-Reply-To: <CAMy9T_HUoD4--s1gNTUjnCgdiAqfYbX-GSqygDwNO-JRwdh4NQ@mail.gmail.com>

On Tue, Aug 1, 2017 at 6:51 PM, Michael Haggerty <mhagger@alum.mit.edu> wrote:

Show 17 quoted lines

> On Tue, Aug 1, 2017 at 4:27 PM, Shawn Pearce <spearce@spearce.org> wrote:
>> On Mon, Jul 31, 2017 at 11:41 PM, Michael Haggerty <mhagger@alum.mit.edu> wrote:
>>> On Sun, Jul 30, 2017 at 8:51 PM, Shawn Pearce <spearce@spearce.org> wrote:
>>>> 4th iteration of the reftable storage format.
>>>> [...]
>>>
>>> Before we commit to Shawn's reftable proposal, I wanted to explore
>>> what a contrasting design that is not block based would look like.
>>
>> I forgot to look at a 1k chunk size, as you suggested that might also
>> be suitable. Here is the more complete experiment table:
>>
>>        | size   | seek_cold | seek_hot  |
>> mh  1k | 29.4 M | 20.6 usec | 10.7 usec |   <== Row fixed
>> mh  4k | 28.3 M | 24.5 usec | 14.5 usec |
>> sp  4k | 29.2 M | 63.0 usec |  5.8 usec |
>> sp 64k | 27.7 M | 35.6 usec | 23.3 usec |

I modified reftable to use a mutli-level index as recommended by Michael Haggerty, and re-ran the above table:

fmt |  bs | idx  |  size  | seek_cold | seek_hot  |
----|-----|------|--------|-----------|-----------|
 mh |  1k | 4 lv | 29.4 M | 20.1 usec |  7.1 usec |
 sp |  1k | 4 lv | 30.7 M | 21.0 usec |  5.5 usec |

 mh |  4k | 2 lv | 28.3 M | 23.4 usec | 11.2 usec |
 sp |  4k | 2 lv | 29.2 M | 19.9 usec |  5.4 usec |

 sp |  4k | 1 lv | 29.2 M | 62.9 usec |  5.6 usec |
 sp | 64k | 1 lv | 27.7 M | 35.6 usec | 21.6 usec |

fmt: mh = Michael's proposal, sp = Shawn's reftable bs: chunk size or block size in bytes idx: how many levels of index size: total file size in bytes

I can't explain the slightly slower sp-1k-4lv vs. mh-1k-4lv cold_seek in the first two rows. It might simply be the larger footer read slowing down JGit. Its reliably flipped in the next two (at 4k).

reftable is more efficient in seek_hot at finding and parsing a reference. For multi-level indexes both sp and mh implementations used a lazy caching strategy that caches index blocks along the path to the ref, but doesn't cache the final ref block. The tests amortized this by performing 60,000 lookups on the same ref.

>> At least in this case, the 1k block size seems like a good tradeoff.

With the multi-level index now in reftable, it seems like reftable at 4k, 2 level index is a better tradeoff. It aligns with the most common filesystem block size, and has lower seek times, both cold and hot. Its slightly larger than Michael's alternative proposal (+921 K), but compresses better than reftable at 1k (-1.5 M).