reftable: file format documentation
Some repositories contain a lot of references (e.g. android at 866k,
rails at 31k). The reftable format provides:
- Near constant time lookup for any single reference, even when the
repository is cold and not in process or kernel cache.
- Near constant time verification a SHA-1 is referred to by at least
one reference (for allow-tip-sha1-in-want).
- Efficient lookup of an entire namespace, such as `refs/tags/`.
- Support atomic push `O(size_of_update)` operations.
- Combine reflog storage with ref storage.
Change-Id: I29d0ff1eee475845660ac9173413e1407adcfbf2
diff --git a/Documentation/technical/reftable.md b/Documentation/technical/reftable.md
new file mode 100644
index 0000000..34f7529
--- /dev/null
+++ b/Documentation/technical/reftable.md
@@ -0,0 +1,950 @@
+# reftable
+
+[TOC]
+
+## Overview
+
+### Problem statement
+
+Some repositories contain a lot of references (e.g. android at 866k,
+rails at 31k). The existing packed-refs format takes up a lot of
+space (e.g. 62M), and does not scale with additional references.
+Lookup of a single reference requires linearly scanning the file.
+
+Atomic pushes modifying multiple references require copying the
+entire packed-refs file, which can be a considerable amount of data
+moved (e.g. 62M in, 62M out) for even small transactions (2 refs
+modified).
+
+Repositories with many loose references occupy a large number of disk
+blocks from the local file system, as each reference is its own file
+storing 41 bytes (and another file for the corresponding reflog).
+This negatively affects the number of inodes available when a large
+number of repositories are stored on the same filesystem. Readers can
+be penalized due to the larger number of syscalls required to traverse
+and read the `$GIT_DIR/refs` directory.
+
+### Objectives
+
+- Near constant time lookup for any single reference, even when the
+ repository is cold and not in process or kernel cache.
+- Near constant time verification if a SHA-1 is referred to by at
+ least one reference (for allow-tip-sha1-in-want).
+- Efficient lookup of an entire namespace, such as `refs/tags/`.
+- Support atomic push with `O(size_of_update)` operations.
+- Combine reflog storage with ref storage for small transactions.
+- Separate reflog storage for base refs and historical logs.
+
+### Description
+
+A reftable file is a portable binary file format customized for
+reference storage. References are sorted, enabling linear scans,
+binary search lookup, and range scans.
+
+Storage in the file is organized into variable sized blocks. Prefix
+compression is used within a single block to reduce disk space. Block
+size and alignment is tunable by the writer.
+
+### Performance
+
+Space used, packed-refs vs. reftable:
+
+repository | packed-refs | reftable | % original | avg ref | avg obj
+-----------|------------:|---------:|-----------:|---------:|--------:
+android | 62.2 M | 36.1 M | 58.0% | 33 bytes | 5 bytes
+rails | 1.8 M | 1.1 M | 57.7% | 29 bytes | 4 bytes
+git | 78.7 K | 48.1 K | 61.0% | 50 bytes | 4 bytes
+git (heads)| 332 b | 269 b | 81.0% | 33 bytes | 0 bytes
+
+Scan (read 866k refs), by reference name lookup (single ref from 866k
+refs), and by SHA-1 lookup (refs with that SHA-1, from 866k refs):
+
+format | cache | scan | by name | by SHA-1
+------------|------:|--------:|---------------:|---------------:
+packed-refs | cold | 402 ms | 409,660.1 usec | 412,535.8 usec
+packed-refs | hot | | 6,844.6 usec | 20,110.1 usec
+reftable | cold | 112 ms | 33.9 usec | 323.2 usec
+reftable | hot | | 20.2 usec | 320.8 usec
+
+Space used for 149,932 log entries for 43,061 refs,
+reflog vs. reftable:
+
+format | size | avg entry
+--------------|------:|-----------:
+$GIT_DIR/logs | 173 M | 1209 bytes
+reftable | 5 M | 37 bytes
+
+## Details
+
+### Peeling
+
+References stored in a reftable are peeled, a record for an annotated
+(or signed) tag records both the tag object, and the object it refers
+to.
+
+### Reference name encoding
+
+Reference names are an uninterpreted sequence of bytes that must pass
+[git-check-ref-format][ref-fmt] as a valid reference name.
+
+[ref-fmt]: https://git-scm.com/docs/git-check-ref-format
+
+### Network byte order
+
+All multi-byte, fixed width fields are in network byte order.
+
+### Ordering
+
+Blocks are lexicographically ordered by their first reference.
+
+### Directory/file conflicts
+
+The reftable format accepts both `refs/heads/foo` and
+`refs/heads/foo/bar` as distinct references.
+
+This property is useful for retaining log records in reftable, but may
+confuse versions of Git using `$GIT_DIR/refs` directory tree to
+maintain references. Users of reftable may choose to continue to
+reject `foo` and `foo/bar` type conflicts to prevent problems for
+peers.
+
+## File format
+
+### Structure
+
+A reftable file has the following high-level structure:
+
+ first_block {
+ header
+ first_ref_block
+ }
+ ref_block*
+ ref_index*
+ obj_block*
+ obj_index*
+ log_block*
+ log_index*
+ footer
+
+A log-only file omits the `ref_block`, `ref_index`, `obj_block` and
+`obj_index` sections, containing only the file header and log block:
+
+ first_block {
+ header
+ }
+ log_block*
+ log_index*
+ footer
+
+in a log-only file the first log block immediately follows the file
+header, without padding to block alignment.
+
+### Block size
+
+The file's block size is arbitrarily determined by the writer, and
+does not have to be a power of 2. The block size must be larger than
+the longest reference name or log entry used in the repository, as
+references cannot span blocks.
+
+Powers of two that are friendly to the virtual memory system or
+filesystem (such as 4k or 8k) are recommended. Larger sizes (64k) can
+yield better compression, with a possible increased cost incurred by
+readers during access.
+
+The largest block size is `16777215` bytes (15.99 MiB).
+
+### Block alignment
+
+Writers may choose to align blocks at multiples of the block size by
+including `padding` filled with NUL bytes at the end of a block to
+round out to the chosen alignment. When alignment is used, writers
+must specify the alignment with the file header's `block_size` field.
+
+Block alignment is not required by the file format. Unaligned files
+must set `block_size = 0` in the file header, and omit `padding`.
+Unaligned files with more than one ref block must include the
+[ref index](#Ref-index) to support fast lookup. Readers must be
+able to read both aligned and non-aligned files.
+
+Very small files (e.g. 1 only ref block) may omit `padding` and the
+ref index to reduce total file size.
+
+### Header
+
+A 24-byte header appears at the beginning of the file:
+
+ 'REFT'
+ uint8( version_number = 1 )
+ uint24( block_size )
+ uint64( min_update_index )
+ uint64( max_update_index )
+
+Aligned files must specify `block_size` to configure readers with the
+expected block alignment. Unaligned files must set `block_size = 0`.
+
+The `min_update_index` and `max_update_index` describe bounds for the
+`update_index` field of all log records in this file. When reftables
+are used in a stack for [transactions](#Update-transactions), these
+fields can order the files such that the prior file's
+`max_update_index + 1` is the next file's `min_update_index`.
+
+### First ref block
+
+The first ref block shares the same block as the file header, and is
+24 bytes smaller than all other blocks in the file. The first block
+immediately begins after the file header, at position 24.
+
+If the first block is a log block (a log-only file), its block header
+begins immediately at position 24.
+
+### Ref block format
+
+A ref block is written as:
+
+ 'r'
+ uint24( block_len )
+ ref_record+
+ uint24( restart_offset )+
+ uint16( restart_count )
+
+ padding?
+
+Blocks begin with `block_type = 'r'` and a 3-byte `block_len` which
+encodes the number of bytes in the block up to, but not including the
+optional `padding`. This is always less than or equal to the file's
+block size. In the first ref block, `block_len` includes 24 bytes
+for the file header.
+
+The 2-byte `restart_count` stores the number of entries in the
+`restart_offset` list, which must not be empty. Readers can use
+`restart_count` to binary search between restarts before starting a
+linear scan.
+
+Exactly `restart_count` 3-byte `restart_offset` values precedes the
+`restart_count`. Offsets are relative to the start of the block and
+refer to the first byte of any `ref_record` whose name has not been
+prefix compressed. Entries in the `restart_offset` list must be
+sorted, ascending. Readers can start linear scans from any of these
+records.
+
+A variable number of `ref_record` fill the middle of the block,
+describing reference names and values. The format is described below.
+
+As the first ref block shares the first file block with the file
+header, all `restart_offset` in the first block are relative to the
+start of the file (position 0), and include the file header. This
+forces the first `restart_offset` to be `28`.
+
+#### ref record
+
+A `ref_record` describes a single reference, storing both the name and
+its value(s). Records are formatted as:
+
+ varint( prefix_length )
+ varint( (suffix_length << 3) | value_type )
+ suffix
+ value?
+
+The `prefix_length` field specifies how many leading bytes of the
+prior reference record's name should be copied to obtain this
+reference's name. This must be 0 for the first reference in any
+block, and also must be 0 for any `ref_record` whose offset is listed
+in the `restart_offset` table at the end of the block.
+
+Recovering a reference name from any `ref_record` is a simple concat:
+
+ this_name = prior_name[0..prefix_length] + suffix
+
+The `suffix_length` value provides the number of bytes available in
+`suffix` to copy from `suffix` to complete the reference name.
+
+The `value` follows. Its format is determined by `value_type`, one of
+the following:
+
+- `0x0`: deletion; no value data (see transactions, below)
+- `0x1`: one 20-byte object id; value of the ref
+- `0x2`: two 20-byte object ids; value of the ref, peeled target
+- `0x3`: symbolic reference: `varint( target_len ) target`
+
+Symbolic references use `0x3`, followed by the complete name of the
+reference target. No compression is applied to the target name.
+
+Types `0x4..0x7` are reserved for future use.
+
+### Ref index
+
+The ref index stores the name of the last reference from every ref
+block in the file, enabling reduced disk seeks for lookups. Any
+reference can be found by searching the index, identifying the
+containing block, and searching within that block.
+
+The index may be organized into a multi-level index, where the 1st
+level index block points to additional ref index blocks (2nd level),
+which may in turn point to either additional index blocks (e.g. 3rd
+level) or ref blocks (leaf level). Disk reads required to access a
+ref go up with higher index levels. Multi-level indexes may be
+required to ensure no single index block exceeds the file format's max
+block size of `16777215` bytes (15.99 MiB). To acheive constant O(1)
+disk seeks for lookups the index must be a single level, which is
+permitted to exceed the file's configured block size, but not the
+format's max block size of 15.99 MiB.
+
+If present, the ref index block(s) appears after the last ref block.
+
+If there are at least 4 ref blocks, a ref index block should be
+written to improve lookup times. Cold reads using the index require
+2 disk reads (read index, read block), and binary searching < 4 blocks
+also requires <= 2 reads. Omitting the index block from smaller files
+saves space.
+
+If the file is unaligned and contains more than one ref block, the ref
+index must be written.
+
+Index block format:
+
+ 'i'
+ uint24( block_len )
+ index_record+
+ uint24( restart_offset )+
+ uint16( restart_count )
+
+ padding?
+
+The index blocks begin with `block_type = 'i'` and a 3-byte
+`block_len` which encodes the number of bytes in the block,
+up to but not including the optional `padding`.
+
+The `restart_offset` and `restart_count` fields are identical in
+format, meaning and usage as in ref blocks.
+
+To reduce the number of reads required for random access in very large
+files the index block may be larger than other blocks. However,
+readers must hold the entire index in memory to benefit from this, so
+it's a time-space tradeoff in both file size and reader memory.
+
+Increasing the file's block size decreases the index size.
+Alternatively a multi-level index may be used, keeping index blocks
+within the file's block size, but increasing the number of blocks
+that need to be accessed.
+
+#### 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. Readers can seek to `block_position` to
+begin reading the block header.
+
+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.
+
+#### Reading the index
+
+Readers loading the ref index must first read the footer (below) to
+obtain `ref_index_position`. If not present, the position will be 0.
+The `ref_index_position` is for the 1st level root of the ref index.
+
+### Obj block format
+
+Object blocks are optional. Writers may choose to omit object blocks,
+especially if readers will not use the SHA-1 to ref mapping.
+
+Object blocks use unique, abbreviated 2-20 byte SHA-1 keys, mapping
+to ref blocks containing references pointing to that object directly,
+or as the peeled value of an annotated tag. Like ref blocks, object
+blocks use the file's standard block size. The abbrevation length is
+available in the footer as `obj_id_len`.
+
+To save space in small files, object blocks may be omitted if the ref
+index is not present, as brute force search will only need to read a
+few ref blocks. When missing, readers should brute force a linear
+search of all references to lookup by SHA-1.
+
+An object block is written as:
+
+ 'o'
+ uint24( block_len )
+ obj_record+
+ uint24( restart_offset )+
+ uint16( restart_count )
+
+ padding?
+
+Fields are identical to ref block. Binary search using the restart
+table works the same as in reference blocks.
+
+Because object identifiers are abbreviated by writers to the shortest
+unique abbreviation within the reftable, obj key lengths are variable
+between 2 and 20 bytes. Readers must compare only for common prefix
+match within an obj block or obj index.
+
+#### obj record
+
+An `obj_record` describes a single object abbreviation, and the blocks
+containing references using that unique abbreviation:
+
+ varint( prefix_length )
+ varint( (suffix_length << 3) | cnt_3 )
+ suffix
+ varint( cnt_large )?
+ varint( position_delta )*
+
+Like in reference blocks, abbreviations are prefix compressed within
+an obj block. On large reftables with many unique objects, higher
+block sizes (64k), and higher restart interval (128), a
+`prefix_length` of 2 or 3 and `suffix_length` of 3 may be common in
+obj records (unique abbreviation of 5-6 raw bytes, 10-12 hex digits).
+
+Each record contains `position_count` number of positions for matching
+ref blocks. For 1-7 positions the count is stored in `cnt_3`. When
+`cnt_3 = 0` the actual count follows in a varint, `cnt_large`.
+
+The use of `cnt_3` bets most objects are pointed to by only a single
+reference, some may be pointed to by a couple of references, and very
+few (if any) are pointed to by more than 7 references.
+
+A special case exists when `cnt_3 = 0` and `cnt_large = 0`: there
+are no `position_delta`, but at least one reference starts with this
+abbreviation. A reader that needs exact reference names must scan all
+references to find which specific references have the desired object.
+Writers should use this format when the `position_delta` list would have
+overflowed the file's block size due to a high number of references
+pointing to the same object.
+
+The first `position_delta` is the position from the start of the file.
+Additional `position_delta` entries are sorted ascending and relative
+to the prior entry, e.g. a reader would perform:
+
+ pos = position_delta[0]
+ prior = pos
+ for (j = 1; j < position_count; j++) {
+ pos = prior + position_delta[j]
+ prior = pos
+ }
+
+With a position in hand, a reader must linearly scan the ref block,
+starting from the first `ref_record`, testing each reference's SHA-1s
+(for `value_type = 0x1` or `0x2`) for full equality. Faster searching
+by SHA-1 within a single ref block is not supported by the reftable
+format. Smaller block sizes reduce the number of candidates this step
+must consider.
+
+### Obj index
+
+The obj index stores the abbreviation from the last entry for every
+obj block in the file, enabling reduced disk seeks for all lookups.
+It is formatted exactly the same as the ref index, but refers to obj
+blocks.
+
+The obj index should be present if obj blocks are present, as
+obj blocks should only be written in larger files.
+
+Readers loading the obj index must first read the footer (below) to
+obtain `obj_index_position`. If not present, the position will be 0.
+
+### Log block format
+
+Unlike ref and obj blocks, log blocks are always unaligned.
+
+Log blocks are variable in size, and do not match the `block_size`
+specified in the file header or footer. Writers should choose an
+appropriate buffer size to prepare a log block for deflation, such as
+`2 * block_size`.
+
+A log block is written as:
+
+ 'g'
+ uint24( block_len )
+ zlib_deflate {
+ log_record+
+ uint24( restart_offset )+
+ uint16( restart_count )
+ }
+
+Log blocks look similar to ref blocks, except `block_type = 'g'`.
+
+The 4-byte block header is followed by the deflated block contents
+using zlib deflate. The `block_len` in the header is the inflated
+size (including 4-byte block header), and should be used by readers to
+preallocate the inflation output buffer. A log block's `block_len`
+may exceed the file's block size.
+
+Offsets within the log block (e.g. `restart_offset`) still include
+the 4-byte header. Readers may prefer prefixing the inflation output
+buffer with the 4-byte header.
+
+Within the deflate container, a variable number of `log_record`
+describe reference changes. The log record format is described
+below. See ref block format (above) for a description of
+`restart_offset` and `restart_count`.
+
+Because log blocks have no alignment or padding between blocks,
+readers must keep track of the bytes consumed by the inflater to
+know where the next log block begins.
+
+#### log record
+
+Log record keys are structured as:
+
+ ref_name '\0' reverse_int64( update_index )
+
+where `update_index` is the unique transaction identifier. The
+`update_index` field must be unique within the scope of a `ref_name`.
+See the update transactions section below for further details.
+
+The `reverse_int64` function inverses the value so lexographical
+ordering the network byte order encoding sorts the more recent records
+with higher `update_index` values first:
+
+ reverse_int64(int64 t) {
+ return 0xffffffffffffffff - t;
+ }
+
+Log records have a similar starting structure to ref and index
+records, utilizing the same prefix compression scheme applied to the
+log record key described above.
+
+```
+ varint( prefix_length )
+ varint( (suffix_length << 3) | log_type )
+ suffix
+ log_data {
+ old_id
+ new_id
+ varint( name_length ) name
+ varint( email_length ) email
+ varint( time_seconds )
+ sint16( tz_offset )
+ varint( message_length ) message
+ }?
+```
+
+Log record entries use `log_type` to indicate what follows:
+
+- `0x0`: deletion; no log data.
+- `0x1`: standard git reflog data using `log_data` above.
+
+The `log_type = 0x0` is mostly useful for `git stash drop`, removing
+an entry from the reflog of `refs/stash` in a transaction file
+(below), without needing to rewrite larger files. Readers reading a
+stack of reflogs must treat this as a deletion.
+
+For `log_type = 0x1`, the `log_data` section follows
+[git update-ref][update-ref] logging, and includes:
+
+- two 20-byte SHA-1s (old id, new id)
+- varint string of committer's name
+- varint string of committer's email
+- varint time in seconds since epoch (Jan 1, 1970)
+- 2-byte timezone offset in minutes (signed)
+- varint string of message
+
+`tz_offset` is the absolute number of minutes from GMT the committer
+was at the time of the update. For example `GMT-0800` is encoded in
+reftable as `sint16(-480)` and `GMT+0230` is `sint16(150)`.
+
+The committer email does not contain `<` or `>`, it's the value
+normally found between the `<>` in a git commit object header.
+
+The `message_length` may be 0, in which case there was no message
+supplied for the update.
+
+[update-ref]: https://git-scm.com/docs/git-update-ref#_logging_updates
+
+#### Reading the log
+
+Readers accessing the log must first read the footer (below) to
+determine the `log_position`. The first block of the log begins at
+`log_position` bytes since the start of the file. The `log_position`
+is not block aligned.
+
+#### 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.
+
+### Log index
+
+The log index stores the log key (`refname \0 reverse_int64(update_index)`)
+for the last log record of every log block in the file, supporting
+bounded-time lookup.
+
+A log index block must be written if 2 or more log blocks are written
+to the file. If present, the log index appears after the last log
+block. There is no padding used to align the log index to block
+alignment.
+
+Log index format is identical to ref index, except the keys are 9
+bytes longer to include `'\0'` and the 8-byte
+`reverse_int64(update_index)`. Records use `block_position` to
+refer to the start of a log block.
+
+#### Reading the index
+
+Readers loading the log index must first read the footer (below) to
+obtain `log_index_position`. If not present, the position will be 0.
+
+### Footer
+
+After the last block of the file, a file footer is written. It begins
+like the file header, but is extended with additional data.
+
+A 68-byte footer appears at the end:
+
+```
+ 'REFT'
+ uint8( version_number = 1 )
+ uint24( block_size )
+ uint64( min_update_index )
+ uint64( max_update_index )
+
+ uint64( ref_index_position )
+ uint64( (obj_position << 5) | obj_id_len )
+ uint64( obj_index_position )
+
+ uint64( log_position )
+ uint64( log_index_position )
+
+ uint32( CRC-32 of above )
+```
+
+If a section is missing (e.g. ref index) the corresponding position
+field (e.g. `ref_index_position`) will be 0.
+
+- `obj_position`: byte position for the first obj block.
+- `obj_id_len`: number of bytes used to abbreviate object identifiers
+ in obj blocks.
+- `log_position`: byte position for the first log block.
+- `ref_index_position`: byte position for the start of the ref index.
+- `obj_index_position`: byte position for the start of the obj index.
+- `log_index_position`: byte position for the start of the log index.
+
+#### Reading the footer
+
+Readers must seek to `file_length - 68` to access the footer. A
+trusted external source (such as `stat(2)`) is necessary to obtain
+`file_length`. When reading the footer, readers must verify:
+
+- 4-byte magic is correct
+- 1-byte version number is recognized
+- 4-byte CRC-32 matches the other 64 bytes (including magic, and version)
+
+Once verified, the other fields of the footer can be accessed.
+
+### Varint encoding
+
+Varint encoding is identical to the ofs-delta encoding method used
+within pack files.
+
+Decoder works such as:
+
+ val = buf[ptr] & 0x7f
+ while (buf[ptr] & 0x80) {
+ ptr++
+ val = ((val + 1) << 7) | (buf[ptr] & 0x7f)
+ }
+
+### Binary search
+
+Binary search within a block is supported by the `restart_offset`
+fields at the end of the block. Readers can binary search through the
+restart table to locate between which two restart points the sought
+reference or key should appear.
+
+Each record identified by a `restart_offset` stores the complete key
+in the `suffix` field of the record, making the compare operation
+during binary search straightforward.
+
+Once a restart point lexicographically before the sought reference has
+been identified, readers can linearly scan through the following
+record entries to locate the sought record, terminating if the current
+record sorts after (and therefore the sought key is not present).
+
+#### Restart point selection
+
+Writers determine the restart points at file creation. The process is
+arbitrary, but every 16 or 64 records is recommended. Every 16 may
+be more suitable for smaller block sizes (4k or 8k), every 64 for
+larger block sizes (64k).
+
+More frequent restart points reduces prefix compression and increases
+space consumed by the restart table, both of which increase file size.
+
+Less frequent restart points makes prefix compression more effective,
+decreasing overall file size, with increased penalities for readers
+walking through more records after the binary search step.
+
+A maximum of `65535` restart points per block is supported.
+
+## Considerations
+
+### Lightweight refs dominate
+
+The reftable format assumes the vast majority of references are single
+SHA-1 valued with common prefixes, such as Gerrit Code Review's
+`refs/changes/` namespace, GitHub's `refs/pulls/` namespace, or many
+lightweight tags in the `refs/tags/` namespace.
+
+Annotated tags storing the peeled object cost an additional 20 bytes
+per reference.
+
+### Low overhead
+
+A reftable with very few references (e.g. git.git with 5 heads)
+is 269 bytes for reftable, vs. 332 bytes for packed-refs. This
+supports reftable scaling down for transaction logs (below).
+
+### Block size
+
+For a Gerrit Code Review type repository with many change refs, larger
+block sizes (64 KiB) and less frequent restart points (every 64) yield
+better compression due to more references within the block compressing
+against the prior reference.
+
+Larger block sizes reduce the index size, as the reftable will
+require fewer blocks to store the same number of references.
+
+### Minimal disk seeks
+
+Assuming the index block has been loaded into memory, binary searching
+for any single reference requires exactly 1 disk seek to load the
+containing block.
+
+### Scans and lookups dominate
+
+Scanning all references and lookup by name (or namespace such as
+`refs/heads/`) are the most common activities performed on repositories.
+SHA-1s are stored directly with references to optimize this use case.
+
+### Logs are infrequently read
+
+Logs are infrequently accessed, but can be large. Deflating log
+blocks saves disk space, with some increased penalty at read time.
+
+Logs are stored in an isolated section from refs, reducing the burden
+on reference readers that want to ignore logs. Further, historical
+logs can be isolated into log-only files.
+
+### Logs are read backwards
+
+Logs are frequently accessed backwards (most recent N records for
+master to answer `master@{4}`), so log records are grouped by
+reference, and sorted descending by update index.
+
+## Repository format
+
+### Version 1
+
+A repository must set its `$GIT_DIR/config` to configure reftable:
+
+ [core]
+ repositoryformatversion = 1
+ [extensions]
+ refStorage = reftable
+
+### Layout
+
+The `$GIT_DIR/refs` path is a file when reftable is configured, not a
+directory. This prevents loose references from being stored.
+
+A collection of reftable files are stored in the `$GIT_DIR/reftable/`
+directory:
+
+ 00000001.log
+ 00000001.ref
+ 00000002.ref
+
+where reftable files are named by a unique name such as produced by
+the function `${update_index}.ref`.
+
+Log-only files use the `.log` extension, while ref-only and mixed ref
+and log files use `.ref`. extension.
+
+The stack ordering file is `$GIT_DIR/refs` and lists the current
+files, one per line, in order, from oldest (base) to newest (most
+recent):
+
+ $ cat .git/refs
+ 00000001.log
+ 00000001.ref
+ 00000002.ref
+
+Readers must read `$GIT_DIR/refs` to determine which files are
+relevant right now, and search through the stack in reverse order
+(last reftable is examined first).
+
+Reftable files not listed in `refs` may be new (and about to be added
+to the stack by the active writer), or ancient and ready to be pruned.
+
+### Readers
+
+Readers can obtain a consistent snapshot of the reference space by
+following:
+
+1. Open and read the `refs` file.
+2. Open each of the reftable files that it mentions.
+3. If any of the files is missing, goto 1.
+4. Read from the now-open files as long as necessary.
+
+### Update transactions
+
+Although reftables are immutable, mutations are supported by writing a
+new reftable and atomically appending it to the stack:
+
+1. Acquire `refs.lock`.
+2. Read `refs` to determine current reftables.
+3. Select `update_index` to be most recent file's `max_update_index + 1`.
+4. Prepare temp reftable `${update_index}_XXXXXX`, including log entries.
+5. Rename `${update_index}_XXXXXX` to `${update_index}.ref`.
+6. Copy `refs` to `refs.lock`, appending file from (5).
+7. Rename `refs.lock` to `refs`.
+
+During step 4 the new file's `min_update_index` and `max_update_index`
+are both set to the `update_index` selected by step 3. All log
+records for the transaction use the same `update_index` in their keys.
+This enables later correlation of which references were updated by the
+same transaction.
+
+Because a single `refs.lock` file is used to manage locking, the
+repository is single-threaded for writers. Writers may have to
+busy-spin (with backoff) around creating `refs.lock`, for up to an
+acceptable wait period, aborting if the repository is too busy to
+mutate. Application servers wrapped around repositories (e.g. Gerrit
+Code Review) can layer their own lock/wait queue to improve fairness
+to writers.
+
+### Reference deletions
+
+Deletion of any reference can be explicitly stored by setting the
+`type` to `0x0` and omitting the `value` field of the `ref_record`.
+This serves as a tombstone, overriding any assertions about the
+existence of the reference from earlier files in the stack.
+
+### Compaction
+
+A partial stack of reftables can be compacted by merging references
+using a straightforward merge join across reftables, selecting the
+most recent value for output, and omitting deleted references that do
+not appear in remaining, lower reftables.
+
+A compacted reftable should set its `min_update_index` to the smallest of
+the input files' `min_update_index`, and its `max_update_index`
+likewise to the largest input `max_update_index`.
+
+For sake of illustration, assume the stack currently consists of
+reftable files (from oldest to newest): A, B, C, and D. The compactor
+is going to compact B and C, leaving A and D alone.
+
+1. Obtain lock `refs.lock` and read the `refs` file.
+2. Obtain locks `B.lock` and `C.lock`.
+ Ownership of these locks prevents other processes from trying
+ to compact these files.
+3. Release `refs.lock`.
+4. Compact `B` and `C` into a temp file `${min_update_index}_XXXXXX`.
+5. Reacquire lock `refs.lock`.
+6. Verify that `B` and `C` are still in the stack, in that order. This
+ should always be the case, assuming that other processes are adhering
+ to the locking protocol.
+7. Rename `${min_update_index}_XXXXXX` to `${min_update_index}_2.ref`.
+8. Write the new stack to `refs.lock`, replacing `B` and `C` with the
+ file from (4).
+9. Rename `refs.lock` to `refs`.
+10. Delete `B` and `C`, perhaps after a short sleep to avoid forcing
+ readers to backtrack.
+
+This strategy permits compactions to proceed independently of updates.
+
+## Alternatives considered
+
+### bzip packed-refs
+
+`bzip2` can significantly shrink a large packed-refs file (e.g. 62
+MiB compresses to 23 MiB, 37%). However the bzip format does not support
+random access to a single reference. Readers must inflate and discard
+while performing a linear scan.
+
+Breaking packed-refs into chunks (individually compressing each chunk)
+would reduce the amount of data a reader must inflate, but still
+leaves the problem of indexing chunks to support readers efficiently
+locating the correct chunk.
+
+Given the compression achieved by reftable's encoding, it does not
+seem necessary to add the complexity of bzip/gzip/zlib.
+
+### Michael Haggerty's alternate format
+
+Michael Haggerty proposed [an alternate][mh-alt] format to reftable on
+the Git mailing list. This format uses smaller chunks, without the
+restart table, and avoids block alignment with padding. Reflog entries
+immediately follow each ref, and are thus interleaved between refs.
+
+Performance testing indicates reftable is faster for lookups (51%
+faster, 11.2 usec vs. 5.4 usec), although reftable produces a
+slightly larger file (+ ~3.2%, 28.3M vs 29.2M):
+
+format | size | seek cold | seek hot |
+---------:|-------:|----------:|----------:|
+mh-alt | 28.3 M | 23.4 usec | 11.2 usec |
+reftable | 29.2 M | 19.9 usec | 5.4 usec |
+
+[mh-alt]: https://public-inbox.org/git/CAMy9T_HCnyc1g8XWOOWhe7nN0aEFyyBskV2aOMb_fe+wGvEJ7A@mail.gmail.com/
+
+### JGit Ketch RefTree
+
+[JGit Ketch][ketch] proposed [RefTree][reftree], an encoding of
+references inside Git tree objects stored as part of the repository's
+object database.
+
+The RefTree format adds additional load on the object database storage
+layer (more loose objects, more objects in packs), and relies heavily
+on the packer's delta compression to save space. Namespaces which are
+flat (e.g. thousands of tags in refs/tags) initially create very
+large loose objects, and so RefTree does not address the problem of
+copying many references to modify a handful.
+
+Flat namespaces are not efficiently searchable in RefTree, as tree
+objects in canonical formatting cannot be binary searched. This fails
+the need to handle a large number of references in a single namespace,
+such as GitHub's `refs/pulls`, or a project with many tags.
+
+[ketch]: https://dev.eclipse.org/mhonarc/lists/jgit-dev/msg03073.html
+[reftree]: https://public-inbox.org/git/CAJo=hJvnAPNAdDcAAwAvU9C4RVeQdoS3Ev9WTguHx4fD0V_nOg@mail.gmail.com/
+
+### LMDB
+
+David Turner proposed [using LMDB][dt-lmdb], as LMDB is lightweight
+(64k of runtime code) and GPL-compatible license.
+
+A downside of LMDB is its reliance on a single C implementation. This
+makes embedding inside JGit (a popular reimplemenation of Git)
+difficult, and hoisting onto virtual storage (for JGit DFS) virtually
+impossible.
+
+A common format that can be supported by all major Git implementations
+(git-core, JGit, libgit2) is strongly preferred.
+
+[dt-lmdb]: https://public-inbox.org/git/1455772670-21142-26-git-send-email-dturner@twopensource.com/
+
+## Future
+
+### Longer hashes
+
+Version will bump (e.g. 2) to indicate `value` uses a different
+object id length other than 20. The length could be stored in an
+expanded file header, or hardcoded as part of the version.
