Re: reftable [v2]: new ref storage format

[Stefan Beller <sbeller@google.com>]

On Mon, Jul 17, 2017 at 12:04 PM, Shawn Pearce <spearce@spearce.org> wrote:

> A block must have at least one restart in it, the first ref_record
> must be a restart. So number_of_restarts in the tail of the block can
> be 0, which implies 1 restart (number_of_restarts + 1), and the first
> restart is required at the first ref_record. :)

Hah! I assumed the first entry to not be recorded because it is always
a restart by definition of the file format, so it could be omitted in the
restart_offset list, but that would complicate the implementation, such
that including it makes sense.

>
>> When starting to write a block, we need to know exactly how large
>> the ref_records* and restart offsets need to be to put the
>> number_of_restarts at the position as promised via block_len.
>> This sounds complicated unless I missed the obvious.
>
> Correct. The writer needs to compute the block size before it writes
> the block. It does so by buffering the block contents until its
> approximately full, then fixes block_len, and flushes the block.

So that is another trade off for determining the block size. "How much
can I buffer?"

>> Going by this, would it rather make sense to omit the block_len
>> and then scan backwards from *block_size-1 to find the first non-NUL
>> and that will be the number_of_restarts?
>
> Not quite. On small reftable files the "physical" block may be shared
> with a log block ('g'). We need to be able to reliably find the of the
> ref block ('r'), without padding between the two blocks.

I'd need to reread the proposal to understand this bit as I assumed that
each block starts at a multiple of block_size. However we could choose
block_size such that there is no padding between 'r' and 'g'. Ok,
makes sense.

> The time field is also prefix compressed as part of the ref name's
> prefix compression. So there is no need to move to the complexity of a
> varint or anything else.

I agree, that is why you explicitly said that the key is
    ref_name '\0' reverse_int32( time_sec )

Note (as found out in discussion with jrnieder@): The size of the integer
is determined by the suffix length encoding and the preceding '\0',
such that the file format allows arbitrary integer size. So instead of
pretending we can only do 32 bit here, just say 'uint' ?