Re: reftable [v4]: new ref storage format

On Mon, Jul 31, 2017 at 11:41 PM, Michael Haggerty <mhagger@alum.mit.edu> wrote:

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 | 36.6 M | 20.6 usec | 10.7 usec |
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 |

A couple of other notes about your contrasting design:

Using a varint for the chunk length made for a complicated reader. JGit doesn't have the luxury of mmap to access the file, so we have to allocate a byte[] and read data from a file descriptor to do anything fancy like decoding a varint. For my experiment I wound up just hardcoding the IO to read 1k or 4k from whatever address.

A "real" implementation would likely prefer to read a fixed width field here such that chunks have a 3 byte header (1 byte chunk_type, 2 byte chunk_length), and then issue a second read to acquire the rest of the chunk. Given that encoding a chunk length of 1024 or 4096 both requires 2 bytes of varint, its always going to be 2 bytes in your design anyway. With the way chunks are scanned, I don't think you want chunks as large as 16k, which would have caused the varint to go to 3 bytes (but still fits in a fixed 2-byte chunk_length).

My reftable proposal should still do well in a mmap region. Most of the cold start penalty for reftable is JGit copying the ref index from the file descriptor to the memory block where we can parse the format. That is why the cold_seek time declines for a larger block size, the index is smaller.

Having no prefix_len on first_child made for a slightly funkier parser. It does save you a byte, but the parser has to know if its looking at the first child, or an other_children to know if it should expect the prefix_len. Its a simple condition, but it kind of grated on me when I wrote that particular section of the experiment. For the majority of records the parser considers, the prefix_len is always present.

That is why I proposed the restart_offsets point to the prefix_len, and prefix_len = 0 at restart points. It slightly simplified the parser.

This is space saving and cute, but kind of annoying. If it was fixed width 32 bit you can address up to 4G away from this chunk's address, and you can directly jump to the byte of interest. By being varints you do save a little space, as most files will probably only need 3 byte varints, and the 0s do collapse down to 1 byte, but you have to linearly walk the list to find any specific byte.

FWIW I didn't implement log_type or symref_target in my experiment, so the size per ref was maybe a few bytes smaller than what you outlined here.

I wonder how desirable this feature is. Most updates are done through HEAD, which is a symref and can therefore update both HEAD and the target's reflogs in the same operation. It seems to me its rare to issue an update directly on the ref that HEAD points at. Its even rarer to have a non-HEAD symbolic reference whose reflog you expect to track something else.

Is this for refs/remotes/origin/HEAD to be a symref and have its reflog mirror the fetch operations that touched the underlying ref?