Re: reftable [v6]: new ref storage format

On Mon, Aug 14, 2017 at 5:13 AM, Michael Haggerty [off-list ref] wrote:

On 08/07/2017 03:47 AM, Shawn Pearce wrote:

quoted

6th iteration of the reftable storage format.

Thanks!

quoted

Changes from v5:
- extensions.refStorage = reftable is used to select this format.

- Log records can be explicitly deleted (for refs/stash).
- Log records may use Michael Haggerty's chained idea to compress before zlib.
  This saved ~5.8% on one of my example repositories.

Meh. Do you think that's worth the complexity? The percentage savings
will presumably be even lower for repositories that store significant
information in their reflog messages.

No, I don't. I'm quite happy to remove the chained compression. I'll
keep the explicit deletion support for refs/stash.

quoted

[...]
#### ref record
- `0x3`: symref and text: `varint( text_len ) text`

[...]

I'm still relatively negative on storing "other" references (except
`HEAD`) in reftable. Here are my thoughts:

* "Other" references are not considered for reachability, so there
  is no need for their modification to be done atomically.

* "Other" references don't have or need reflogs.

* The refs API would have to provide a way for other Git code to
  read and write "other" references including their extra
  information, and the users of that information would have to
  be rewritten to use the new API.

* Presumably there are other programs in the wild (e.g., scripts)
  that want to read that information. They wouldn't be able to
  extract it from reftable files themselves, so we would also have
  to provide a command-line tool to read (and write?) such files.

Regardless, I suggest allocating separate `value_type`s for generic
symrefs (which then wouldn't need a `ref: ` prefix) vs. for "other"
references.

Ack, I agree with you. Lets only store symrefs as 0x3, without the
"ref: " prefix nonsense, and don't support the "other" ref types. You
make good arguments above about why those would not be stored in a
reftable.

quoted

[...]
### Ref index

It wasn't clear to me whether (in the case of a multi-level index) ref
index blocks have to be aligned in `block_size` blocks (both their
maximum size and their alignment). I don't see a reason for that to be
required, though of course a compactor implementation might choose to
block-align these blocks based on the filesystem that is in use.

For that matter, I don't see an intrinsic reason that object blocks or
object index blocks need to be block aligned.

Yea, you are correct. There isn't an actual need for alignment.

In fact, the only way I can see that the current reftable proposal makes
use of `block_size` is so that `obj_record`s can record `block_delta` in
units of `block_size` rather than in units of bytes. (And given that I'm
skeptical about the value of the object index, that justification seems
thin.)

This use of block_size in the obj_record also has been bothering me.
I'm changing it to use position, which removes any requirement on
alignment. It does cost a bit more space, but I'm willing to trade
that for simplification in the format definition.

I totally accept that *you* want to align your blocks, and I'm totally
supportive of a format that permits a reftable compactor to write
reftables that are block-aligned. It just still seems to me that it
imposes more complexity than necessary on *other* reftable compactor
implementations that don't care about block alignment.

Aside from the object index, I think it would be straightforward to
write a reftable reader that is totally ignorant of `block_size`.

Yup, I think you are right. So I'll try to rework the document to make
it so alignment and padding are writer-local decisions. A writer can
choose to align, or choose to skip alignment. Readers should be
prepared for either.

quoted

[...]
#### index record

An index record describes the last entry in another block.
Index records are written as:

    varint( prefix_length )
    varint( (suffix_length << 3) | 0 )
    suffix
    varint( block_position )

Index records use prefix compression exactly like `ref_record`.

Index records store `block_position` after the suffix, specifying the
absolute position in bytes (from the start of the file) of the block
that ends with this reference.

Is there a reason that the index lists the *last* refname that is
contained in a block rather than the *first* refname? I can't think of a
reason to choose one vs. the other, but your choice was initially
surprising. I don't think it matters either way; I was just curious.

Yes, there is a reason. When a reader is searching the index block and
discovers a key that is greater than their search needle, they are now
sitting on a record with the block_position for that greater key. By
using the *last* refname the current block_position is the one to seek
to.

If instead we used *first* refname, the reader would now have to
backtrack to the prior index record to get the block_position out of
that record. Or it has to keep a running "prior_position" local
variable.

Using last simplifies the reader's code.

Do I understand correctly that all `block_position`s are *byte*
addresses, even in the `ref_index` where they should all be multiples of
the block size (except the zeroth one)? I think that's OK, but note that
it will waste more than a byte per `ref_index` and `obj_index` record,
on average.

Yes, because it simplifies a lot of code, especially if we do away
with any sort of requirement for alignment.

quoted

Readers must examine the block header at `block_position` to determine
if the next block is another level index block, or the leaf-level ref
block.

For scanning through a whole namespace, like `refs/tags/`, I guess you
only need to use a binary search to find the beginning of the range.
Then you would read serially forwards from there, continuing from one
`ref_block` to the next, until you find a refname that doesn't start
with `refs/tags/`. In other words, there is no reason to binary search
to find the end of the namespace, correct?

Correct.

quoted

[...]
#### Importing logs

When importing from `$GIT_DIR/logs` writers should globally order all
log records roughly by timestamp while preserving file order, and
assign unique, increasing `update_index` values for each log line.
Newer log records get higher `update_index` values.

Although an import may write only a single reftable file, the reftable
file must span many unique `update_index`, as each log line requires
its own `update_index` to preserve semantics.

Thinking out loud here: A really high-quality importer might want to
group together, under the same `update_index`, ref updates that are
thought originally to have been done in the same transaction.

[...]

But I doubt that it is worth the effort. (The whole idea gives me nasty
flashbacks from working on cvs2svn/cvs2git.)

Yup, that is why I didn't go down writing a description like that here. :)

On Wed, Aug 16, 2017 at 12:47 AM, Shawn Pearce [off-list ref] wrote:

On Mon, Aug 14, 2017 at 5:13 AM, Michael Haggerty [off-list ref] wrote:

quoted

On 08/07/2017 03:47 AM, Shawn Pearce wrote:

quoted

6th iteration of the reftable storage format.

[...]

quoted

quoted

#### index record

An index record describes the last entry in another block.
Index records are written as:

    varint( prefix_length )
    varint( (suffix_length << 3) | 0 )
    suffix
    varint( block_position )

Index records use prefix compression exactly like `ref_record`.

Index records store `block_position` after the suffix, specifying the
absolute position in bytes (from the start of the file) of the block
that ends with this reference.

Is there a reason that the index lists the *last* refname that is
contained in a block rather than the *first* refname? I can't think of a
reason to choose one vs. the other, but your choice was initially
surprising. I don't think it matters either way; I was just curious.

Yes, there is a reason. When a reader is searching the index block and
discovers a key that is greater than their search needle, they are now
sitting on a record with the block_position for that greater key. By
using the *last* refname the current block_position is the one to seek
to.

If instead we used *first* refname, the reader would now have to
backtrack to the prior index record to get the block_position out of
that record. Or it has to keep a running "prior_position" local
variable.

Using last simplifies the reader's code.

Ah, OK. I was thinking of this as being a binary search, in which case
you *must* see both bracketing records before you are done, and the
chances are 50-50 which one you see first. But this search is a little
bit different, because the index records within a restart block have
to be scanned linearly. So it is much more likely that you see the
"before" record followed by the "after" record.

Thanks for the explanation.

Michael