10 Some repositories contain a lot of references (e.g. android at 866k,
11 rails at 31k). The existing packed-refs format takes up a lot of space
12 (e.g. 62M), and does not scale with additional references. Lookup of a
13 single reference requires linearly scanning the file.
15 Atomic pushes modifying multiple references require copying the entire
16 packed-refs file, which can be a considerable amount of data moved
17 (e.g. 62M in, 62M out) for even small transactions (2 refs modified).
19 Repositories with many loose references occupy a large number of disk
20 blocks from the local file system, as each reference is its own file
21 storing 41 bytes (and another file for the corresponding reflog). This
22 negatively affects the number of inodes available when a large number of
23 repositories are stored on the same filesystem. Readers can be penalized
24 due to the larger number of syscalls required to traverse and read the
25 `$GIT_DIR/refs` directory.
31 * Near constant time lookup for any single reference, even when the
32 repository is cold and not in process or kernel cache.
33 * Near constant time verification if an object name is referred to by at least
34 one reference (for allow-tip-sha1-in-want).
35 * Efficient enumeration of an entire namespace, such as `refs/tags/`.
36 * Support atomic push with `O(size_of_update)` operations.
37 * Combine reflog storage with ref storage for small transactions.
38 * Separate reflog storage for base refs and historical logs.
43 A reftable file is a portable binary file format customized for
44 reference storage. References are sorted, enabling linear scans, binary
45 search lookup, and range scans.
47 Storage in the file is organized into variable sized blocks. Prefix
48 compression is used within a single block to reduce disk space. Block
49 size and alignment is tunable by the writer.
54 Space used, packed-refs vs. reftable:
56 [cols=",>,>,>,>,>",options="header",]
57 |===============================================================
58 |repository |packed-refs |reftable |% original |avg ref |avg obj
59 |android |62.2 M |36.1 M |58.0% |33 bytes |5 bytes
60 |rails |1.8 M |1.1 M |57.7% |29 bytes |4 bytes
61 |git |78.7 K |48.1 K |61.0% |50 bytes |4 bytes
62 |git (heads) |332 b |269 b |81.0% |33 bytes |0 bytes
63 |===============================================================
65 Scan (read 866k refs), by reference name lookup (single ref from 866k
66 refs), and by SHA-1 lookup (refs with that SHA-1, from 866k refs):
68 [cols=",>,>,>,>",options="header",]
69 |=========================================================
70 |format |cache |scan |by name |by SHA-1
71 |packed-refs |cold |402 ms |409,660.1 usec |412,535.8 usec
72 |packed-refs |hot | |6,844.6 usec |20,110.1 usec
73 |reftable |cold |112 ms |33.9 usec |323.2 usec
74 |reftable |hot | |20.2 usec |320.8 usec
75 |=========================================================
77 Space used for 149,932 log entries for 43,061 refs, reflog vs. reftable:
79 [cols=",>,>",options="header",]
80 |================================
81 |format |size |avg entry
82 |$GIT_DIR/logs |173 M |1209 bytes
83 |reftable |5 M |37 bytes
84 |================================
92 References stored in a reftable are peeled, a record for an annotated
93 (or signed) tag records both the tag object, and the object it refers
94 to. This is analogous to storage in the packed-refs format.
96 Reference name encoding
97 ^^^^^^^^^^^^^^^^^^^^^^^
99 Reference names are an uninterpreted sequence of bytes that must pass
100 linkgit:git-check-ref-format[1] as a valid reference name.
105 Each entry must have a unique key; repeated keys are disallowed.
110 All multi-byte, fixed width fields are in network byte order.
115 Varint encoding is identical to the ofs-delta encoding method used
118 Decoder works such as:
121 val = buf[ptr] & 0x7f
122 while (buf[ptr] & 0x80) {
124 val = ((val + 1) << 7) | (buf[ptr] & 0x7f)
131 Blocks are lexicographically ordered by their first reference.
133 Directory/file conflicts
134 ^^^^^^^^^^^^^^^^^^^^^^^^
136 The reftable format accepts both `refs/heads/foo` and
137 `refs/heads/foo/bar` as distinct references.
139 This property is useful for retaining log records in reftable, but may
140 confuse versions of Git using `$GIT_DIR/refs` directory tree to maintain
141 references. Users of reftable may choose to continue to reject `foo` and
142 `foo/bar` type conflicts to prevent problems for peers.
150 A reftable file has the following high-level structure:
166 A log-only file omits the `ref_block`, `ref_index`, `obj_block` and
167 `obj_index` sections, containing only the file header and log block:
178 in a log-only file the first log block immediately follows the file
179 header, without padding to block alignment.
184 The file's block size is arbitrarily determined by the writer, and does
185 not have to be a power of 2. The block size must be larger than the
186 longest reference name or log entry used in the repository, as
187 references cannot span blocks.
189 Powers of two that are friendly to the virtual memory system or
190 filesystem (such as 4k or 8k) are recommended. Larger sizes (64k) can
191 yield better compression, with a possible increased cost incurred by
192 readers during access.
194 The largest block size is `16777215` bytes (15.99 MiB).
199 Writers may choose to align blocks at multiples of the block size by
200 including `padding` filled with NUL bytes at the end of a block to round
201 out to the chosen alignment. When alignment is used, writers must
202 specify the alignment with the file header's `block_size` field.
204 Block alignment is not required by the file format. Unaligned files must
205 set `block_size = 0` in the file header, and omit `padding`. Unaligned
206 files with more than one ref block must include the link:#Ref-index[ref
207 index] to support fast lookup. Readers must be able to read both aligned
208 and non-aligned files.
210 Very small files (e.g. a single ref block) may omit `padding` and the ref
211 index to reduce total file size.
216 A 24-byte header appears at the beginning of the file:
220 uint8( version_number = 1 )
222 uint64( min_update_index )
223 uint64( max_update_index )
226 Aligned files must specify `block_size` to configure readers with the
227 expected block alignment. Unaligned files must set `block_size = 0`.
229 The `min_update_index` and `max_update_index` describe bounds for the
230 `update_index` field of all log records in this file. When reftables are
231 used in a stack for link:#Update-transactions[transactions], these
232 fields can order the files such that the prior file's
233 `max_update_index + 1` is the next file's `min_update_index`.
238 A 28-byte header appears at the beginning of the file:
242 uint8( version_number = 2 )
244 uint64( min_update_index )
245 uint64( max_update_index )
249 The header is identical to `version_number=1`, with the 4-byte hash ID
250 ("sha1" for SHA1 and "s256" for SHA-256) append to the header.
252 For maximum backward compatibility, it is recommended to use version 1 when
253 writing SHA1 reftables.
258 The first ref block shares the same block as the file header, and is 24
259 bytes smaller than all other blocks in the file. The first block
260 immediately begins after the file header, at position 24.
262 If the first block is a log block (a log-only file), its block header
263 begins immediately at position 24.
268 A ref block is written as:
274 uint24( restart_offset )+
275 uint16( restart_count )
280 Blocks begin with `block_type = 'r'` and a 3-byte `block_len` which
281 encodes the number of bytes in the block up to, but not including the
282 optional `padding`. This is always less than or equal to the file's
283 block size. In the first ref block, `block_len` includes 24 bytes for
286 The 2-byte `restart_count` stores the number of entries in the
287 `restart_offset` list, which must not be empty. Readers can use
288 `restart_count` to binary search between restarts before starting a
291 Exactly `restart_count` 3-byte `restart_offset` values precedes the
292 `restart_count`. Offsets are relative to the start of the block and
293 refer to the first byte of any `ref_record` whose name has not been
294 prefix compressed. Entries in the `restart_offset` list must be sorted,
295 ascending. Readers can start linear scans from any of these records.
297 A variable number of `ref_record` fill the middle of the block,
298 describing reference names and values. The format is described below.
300 As the first ref block shares the first file block with the file header,
301 all `restart_offset` in the first block are relative to the start of the
302 file (position 0), and include the file header. This forces the first
303 `restart_offset` to be `28`.
308 A `ref_record` describes a single reference, storing both the name and
309 its value(s). Records are formatted as:
312 varint( prefix_length )
313 varint( (suffix_length << 3) | value_type )
315 varint( update_index_delta )
319 The `prefix_length` field specifies how many leading bytes of the prior
320 reference record's name should be copied to obtain this reference's
321 name. This must be 0 for the first reference in any block, and also must
322 be 0 for any `ref_record` whose offset is listed in the `restart_offset`
323 table at the end of the block.
325 Recovering a reference name from any `ref_record` is a simple concat:
328 this_name = prior_name[0..prefix_length] + suffix
331 The `suffix_length` value provides the number of bytes available in
332 `suffix` to copy from `suffix` to complete the reference name.
334 The `update_index` that last modified the reference can be obtained by
335 adding `update_index_delta` to the `min_update_index` from the file
336 header: `min_update_index + update_index_delta`.
338 The `value` follows. Its format is determined by `value_type`, one of
341 * `0x0`: deletion; no value data (see transactions, below)
342 * `0x1`: one object name; value of the ref
343 * `0x2`: two object names; value of the ref, peeled target
344 * `0x3`: symbolic reference: `varint( target_len ) target`
346 Symbolic references use `0x3`, followed by the complete name of the
347 reference target. No compression is applied to the target name.
349 Types `0x4..0x7` are reserved for future use.
354 The ref index stores the name of the last reference from every ref block
355 in the file, enabling reduced disk seeks for lookups. Any reference can
356 be found by searching the index, identifying the containing block, and
357 searching within that block.
359 The index may be organized into a multi-level index, where the 1st level
360 index block points to additional ref index blocks (2nd level), which may
361 in turn point to either additional index blocks (e.g. 3rd level) or ref
362 blocks (leaf level). Disk reads required to access a ref go up with
363 higher index levels. Multi-level indexes may be required to ensure no
364 single index block exceeds the file format's max block size of
365 `16777215` bytes (15.99 MiB). To achieve constant O(1) disk seeks for
366 lookups the index must be a single level, which is permitted to exceed
367 the file's configured block size, but not the format's max block size of
370 If present, the ref index block(s) appears after the last ref block.
372 If there are at least 4 ref blocks, a ref index block should be written
373 to improve lookup times. Cold reads using the index require 2 disk reads
374 (read index, read block), and binary searching < 4 blocks also requires
375 <= 2 reads. Omitting the index block from smaller files saves space.
377 If the file is unaligned and contains more than one ref block, the ref
378 index must be written.
386 uint24( restart_offset )+
387 uint16( restart_count )
392 The index blocks begin with `block_type = 'i'` and a 3-byte `block_len`
393 which encodes the number of bytes in the block, up to but not including
394 the optional `padding`.
396 The `restart_offset` and `restart_count` fields are identical in format,
397 meaning and usage as in ref blocks.
399 To reduce the number of reads required for random access in very large
400 files the index block may be larger than other blocks. However, readers
401 must hold the entire index in memory to benefit from this, so it's a
402 time-space tradeoff in both file size and reader memory.
404 Increasing the file's block size decreases the index size. Alternatively
405 a multi-level index may be used, keeping index blocks within the file's
406 block size, but increasing the number of blocks that need to be
412 An index record describes the last entry in another block. Index records
416 varint( prefix_length )
417 varint( (suffix_length << 3) | 0 )
419 varint( block_position )
422 Index records use prefix compression exactly like `ref_record`.
424 Index records store `block_position` after the suffix, specifying the
425 absolute position in bytes (from the start of the file) of the block
426 that ends with this reference. Readers can seek to `block_position` to
427 begin reading the block header.
429 Readers must examine the block header at `block_position` to determine
430 if the next block is another level index block, or the leaf-level ref
436 Readers loading the ref index must first read the footer (below) to
437 obtain `ref_index_position`. If not present, the position will be 0. The
438 `ref_index_position` is for the 1st level root of the ref index.
443 Object blocks are optional. Writers may choose to omit object blocks,
444 especially if readers will not use the object name to ref mapping.
446 Object blocks use unique, abbreviated 2-32 object name keys, mapping to
447 ref blocks containing references pointing to that object directly, or as
448 the peeled value of an annotated tag. Like ref blocks, object blocks use
449 the file's standard block size. The abbreviation length is available in
450 the footer as `obj_id_len`.
452 To save space in small files, object blocks may be omitted if the ref
453 index is not present, as brute force search will only need to read a few
454 ref blocks. When missing, readers should brute force a linear search of
455 all references to lookup by object name.
457 An object block is written as:
463 uint24( restart_offset )+
464 uint16( restart_count )
469 Fields are identical to ref block. Binary search using the restart table
470 works the same as in reference blocks.
472 Because object names are abbreviated by writers to the shortest unique
473 abbreviation within the reftable, obj key lengths have a variable length. Their
474 length must be at least 2 bytes. Readers must compare only for common prefix
475 match within an obj block or obj index.
480 An `obj_record` describes a single object abbreviation, and the blocks
481 containing references using that unique abbreviation:
484 varint( prefix_length )
485 varint( (suffix_length << 3) | cnt_3 )
488 varint( position_delta )*
491 Like in reference blocks, abbreviations are prefix compressed within an
492 obj block. On large reftables with many unique objects, higher block
493 sizes (64k), and higher restart interval (128), a `prefix_length` of 2
494 or 3 and `suffix_length` of 3 may be common in obj records (unique
495 abbreviation of 5-6 raw bytes, 10-12 hex digits).
497 Each record contains `position_count` number of positions for matching
498 ref blocks. For 1-7 positions the count is stored in `cnt_3`. When
499 `cnt_3 = 0` the actual count follows in a varint, `cnt_large`.
501 The use of `cnt_3` bets most objects are pointed to by only a single
502 reference, some may be pointed to by a couple of references, and very
503 few (if any) are pointed to by more than 7 references.
505 A special case exists when `cnt_3 = 0` and `cnt_large = 0`: there are no
506 `position_delta`, but at least one reference starts with this
507 abbreviation. A reader that needs exact reference names must scan all
508 references to find which specific references have the desired object.
509 Writers should use this format when the `position_delta` list would have
510 overflowed the file's block size due to a high number of references
511 pointing to the same object.
513 The first `position_delta` is the position from the start of the file.
514 Additional `position_delta` entries are sorted ascending and relative to
515 the prior entry, e.g. a reader would perform:
518 pos = position_delta[0]
520 for (j = 1; j < position_count; j++) {
521 pos = prior + position_delta[j]
526 With a position in hand, a reader must linearly scan the ref block,
527 starting from the first `ref_record`, testing each reference's object names
528 (for `value_type = 0x1` or `0x2`) for full equality. Faster searching by
529 object name within a single ref block is not supported by the reftable format.
530 Smaller block sizes reduce the number of candidates this step must
536 The obj index stores the abbreviation from the last entry for every obj
537 block in the file, enabling reduced disk seeks for all lookups. It is
538 formatted exactly the same as the ref index, but refers to obj blocks.
540 The obj index should be present if obj blocks are present, as obj blocks
541 should only be written in larger files.
543 Readers loading the obj index must first read the footer (below) to
544 obtain `obj_index_position`. If not present, the position will be 0.
549 Unlike ref and obj blocks, log blocks are always unaligned.
551 Log blocks are variable in size, and do not match the `block_size`
552 specified in the file header or footer. Writers should choose an
553 appropriate buffer size to prepare a log block for deflation, such as
556 A log block is written as:
563 uint24( restart_offset )+
564 uint16( restart_count )
568 Log blocks look similar to ref blocks, except `block_type = 'g'`.
570 The 4-byte block header is followed by the deflated block contents using
571 zlib deflate. The `block_len` in the header is the inflated size
572 (including 4-byte block header), and should be used by readers to
573 preallocate the inflation output buffer. A log block's `block_len` may
574 exceed the file's block size.
576 Offsets within the log block (e.g. `restart_offset`) still include the
577 4-byte header. Readers may prefer prefixing the inflation output buffer
578 with the 4-byte header.
580 Within the deflate container, a variable number of `log_record` describe
581 reference changes. The log record format is described below. See ref
582 block format (above) for a description of `restart_offset` and
585 Because log blocks have no alignment or padding between blocks, readers
586 must keep track of the bytes consumed by the inflater to know where the
587 next log block begins.
592 Log record keys are structured as:
595 ref_name '\0' reverse_int64( update_index )
598 where `update_index` is the unique transaction identifier. The
599 `update_index` field must be unique within the scope of a `ref_name`.
600 See the update transactions section below for further details.
602 The `reverse_int64` function inverses the value so lexicographical
603 ordering the network byte order encoding sorts the more recent records
604 with higher `update_index` values first:
607 reverse_int64(int64 t) {
608 return 0xffffffffffffffff - t;
612 Log records have a similar starting structure to ref and index records,
613 utilizing the same prefix compression scheme applied to the log record
617 varint( prefix_length )
618 varint( (suffix_length << 3) | log_type )
623 varint( name_length ) name
624 varint( email_length ) email
625 varint( time_seconds )
627 varint( message_length ) message
631 Log record entries use `log_type` to indicate what follows:
633 * `0x0`: deletion; no log data.
634 * `0x1`: standard git reflog data using `log_data` above.
636 The `log_type = 0x0` is mostly useful for `git stash drop`, removing an
637 entry from the reflog of `refs/stash` in a transaction file (below),
638 without needing to rewrite larger files. Readers reading a stack of
639 reflogs must treat this as a deletion.
641 For `log_type = 0x1`, the `log_data` section follows
642 linkgit:git-update-ref[1] logging and includes:
644 * two object names (old id, new id)
645 * varint string of committer's name
646 * varint string of committer's email
647 * varint time in seconds since epoch (Jan 1, 1970)
648 * 2-byte timezone offset in minutes (signed)
649 * varint string of message
651 `tz_offset` is the absolute number of minutes from GMT the committer was
652 at the time of the update. For example `GMT-0800` is encoded in reftable
653 as `sint16(-480)` and `GMT+0230` is `sint16(150)`.
655 The committer email does not contain `<` or `>`, it's the value normally
656 found between the `<>` in a git commit object header.
658 The `message_length` may be 0, in which case there was no message
659 supplied for the update.
661 Contrary to traditional reflog (which is a file), renames are encoded as
662 a combination of ref deletion and ref creation. A deletion is a log
663 record with a zero new_id, and a creation is a log record with a zero old_id.
668 Readers accessing the log must first read the footer (below) to
669 determine the `log_position`. The first block of the log begins at
670 `log_position` bytes since the start of the file. The `log_position` is
676 When importing from `$GIT_DIR/logs` writers should globally order all
677 log records roughly by timestamp while preserving file order, and assign
678 unique, increasing `update_index` values for each log line. Newer log
679 records get higher `update_index` values.
681 Although an import may write only a single reftable file, the reftable
682 file must span many unique `update_index`, as each log line requires its
683 own `update_index` to preserve semantics.
688 The log index stores the log key
689 (`refname \0 reverse_int64(update_index)`) for the last log record of
690 every log block in the file, supporting bounded-time lookup.
692 A log index block must be written if 2 or more log blocks are written to
693 the file. If present, the log index appears after the last log block.
694 There is no padding used to align the log index to block alignment.
696 Log index format is identical to ref index, except the keys are 9 bytes
697 longer to include `'\0'` and the 8-byte `reverse_int64(update_index)`.
698 Records use `block_position` to refer to the start of a log block.
703 Readers loading the log index must first read the footer (below) to
704 obtain `log_index_position`. If not present, the position will be 0.
709 After the last block of the file, a file footer is written. It begins
710 like the file header, but is extended with additional data.
715 uint64( ref_index_position )
716 uint64( (obj_position << 5) | obj_id_len )
717 uint64( obj_index_position )
719 uint64( log_position )
720 uint64( log_index_position )
722 uint32( CRC-32 of above )
725 If a section is missing (e.g. ref index) the corresponding position
726 field (e.g. `ref_index_position`) will be 0.
728 * `obj_position`: byte position for the first obj block.
729 * `obj_id_len`: number of bytes used to abbreviate object names in
731 * `log_position`: byte position for the first log block.
732 * `ref_index_position`: byte position for the start of the ref index.
733 * `obj_index_position`: byte position for the start of the obj index.
734 * `log_index_position`: byte position for the start of the log index.
736 The size of the footer is 68 bytes for version 1, and 72 bytes for
742 Readers must first read the file start to determine the version
743 number. Then they seek to `file_length - FOOTER_LENGTH` to access the
744 footer. A trusted external source (such as `stat(2)`) is necessary to
745 obtain `file_length`. When reading the footer, readers must verify:
747 * 4-byte magic is correct
748 * 1-byte version number is recognized
749 * 4-byte CRC-32 matches the other 64 bytes (including magic, and
752 Once verified, the other fields of the footer can be accessed.
757 A reftable may be empty. In this case, the file starts with a header
758 and is immediately followed by a footer.
763 Binary search within a block is supported by the `restart_offset` fields
764 at the end of the block. Readers can binary search through the restart
765 table to locate between which two restart points the sought reference or
768 Each record identified by a `restart_offset` stores the complete key in
769 the `suffix` field of the record, making the compare operation during
770 binary search straightforward.
772 Once a restart point lexicographically before the sought reference has
773 been identified, readers can linearly scan through the following record
774 entries to locate the sought record, terminating if the current record
775 sorts after (and therefore the sought key is not present).
777 Restart point selection
778 +++++++++++++++++++++++
780 Writers determine the restart points at file creation. The process is
781 arbitrary, but every 16 or 64 records is recommended. Every 16 may be
782 more suitable for smaller block sizes (4k or 8k), every 64 for larger
785 More frequent restart points reduces prefix compression and increases
786 space consumed by the restart table, both of which increase file size.
788 Less frequent restart points makes prefix compression more effective,
789 decreasing overall file size, with increased penalties for readers
790 walking through more records after the binary search step.
792 A maximum of `65535` restart points per block is supported.
797 Lightweight refs dominate
798 ^^^^^^^^^^^^^^^^^^^^^^^^^
800 The reftable format assumes the vast majority of references are single
801 object names valued with common prefixes, such as Gerrit Code Review's
802 `refs/changes/` namespace, GitHub's `refs/pulls/` namespace, or many
803 lightweight tags in the `refs/tags/` namespace.
805 Annotated tags storing the peeled object cost an additional object name per
811 A reftable with very few references (e.g. git.git with 5 heads) is 269
812 bytes for reftable, vs. 332 bytes for packed-refs. This supports
813 reftable scaling down for transaction logs (below).
818 For a Gerrit Code Review type repository with many change refs, larger
819 block sizes (64 KiB) and less frequent restart points (every 64) yield
820 better compression due to more references within the block compressing
821 against the prior reference.
823 Larger block sizes reduce the index size, as the reftable will require
824 fewer blocks to store the same number of references.
829 Assuming the index block has been loaded into memory, binary searching
830 for any single reference requires exactly 1 disk seek to load the
833 Scans and lookups dominate
834 ^^^^^^^^^^^^^^^^^^^^^^^^^^
836 Scanning all references and lookup by name (or namespace such as
837 `refs/heads/`) are the most common activities performed on repositories.
838 Object names are stored directly with references to optimize this use case.
840 Logs are infrequently read
841 ^^^^^^^^^^^^^^^^^^^^^^^^^^
843 Logs are infrequently accessed, but can be large. Deflating log blocks
844 saves disk space, with some increased penalty at read time.
846 Logs are stored in an isolated section from refs, reducing the burden on
847 reference readers that want to ignore logs. Further, historical logs can
848 be isolated into log-only files.
850 Logs are read backwards
851 ^^^^^^^^^^^^^^^^^^^^^^^
853 Logs are frequently accessed backwards (most recent N records for master
854 to answer `master@{4}`), so log records are grouped by reference, and
855 sorted descending by update index.
863 A repository must set its `$GIT_DIR/config` to configure reftable:
867 repositoryformatversion = 1
869 refStorage = reftable
875 A collection of reftable files are stored in the `$GIT_DIR/reftable/` directory.
876 Their names should have a random element, such that each filename is globally
877 unique; this helps avoid spurious failures on Windows, where open files cannot
878 be removed or overwritten. It suggested to use
879 `${min_update_index}-${max_update_index}-${random}.ref` as a naming convention.
881 Log-only files use the `.log` extension, while ref-only and mixed ref
882 and log files use `.ref`. extension.
884 The stack ordering file is `$GIT_DIR/reftable/tables.list` and lists the
885 current files, one per line, in order, from oldest (base) to newest
889 $ cat .git/reftable/tables.list
890 00000001-00000001-RANDOM1.log
891 00000002-00000002-RANDOM2.ref
892 00000003-00000003-RANDOM3.ref
895 Readers must read `$GIT_DIR/reftable/tables.list` to determine which
896 files are relevant right now, and search through the stack in reverse
897 order (last reftable is examined first).
899 Reftable files not listed in `tables.list` may be new (and about to be
900 added to the stack by the active writer), or ancient and ready to be
903 Backward compatibility
904 ^^^^^^^^^^^^^^^^^^^^^^
906 Older clients should continue to recognize the directory as a git
907 repository so they don't look for an enclosing repository in parent
908 directories. To this end, a reftable-enabled repository must contain the
909 following dummy files
911 * `.git/HEAD`, a regular file containing `ref: refs/heads/.invalid`.
912 * `.git/refs/`, a directory
913 * `.git/refs/heads`, a regular file
918 Readers can obtain a consistent snapshot of the reference space by
921 1. Open and read the `tables.list` file.
922 2. Open each of the reftable files that it mentions.
923 3. If any of the files is missing, goto 1.
924 4. Read from the now-open files as long as necessary.
929 Although reftables are immutable, mutations are supported by writing a
930 new reftable and atomically appending it to the stack:
932 1. Acquire `tables.list.lock`.
933 2. Read `tables.list` to determine current reftables.
934 3. Select `update_index` to be most recent file's
935 `max_update_index + 1`.
936 4. Prepare temp reftable `tmp_XXXXXX`, including log entries.
937 5. Rename `tmp_XXXXXX` to `${update_index}-${update_index}-${random}.ref`.
938 6. Copy `tables.list` to `tables.list.lock`, appending file from (5).
939 7. Rename `tables.list.lock` to `tables.list`.
941 During step 4 the new file's `min_update_index` and `max_update_index`
942 are both set to the `update_index` selected by step 3. All log records
943 for the transaction use the same `update_index` in their keys. This
944 enables later correlation of which references were updated by the same
947 Because a single `tables.list.lock` file is used to manage locking, the
948 repository is single-threaded for writers. Writers may have to busy-spin
949 (with backoff) around creating `tables.list.lock`, for up to an
950 acceptable wait period, aborting if the repository is too busy to
951 mutate. Application servers wrapped around repositories (e.g. Gerrit
952 Code Review) can layer their own lock/wait queue to improve fairness to
958 Deletion of any reference can be explicitly stored by setting the `type`
959 to `0x0` and omitting the `value` field of the `ref_record`. This serves
960 as a tombstone, overriding any assertions about the existence of the
961 reference from earlier files in the stack.
966 A partial stack of reftables can be compacted by merging references
967 using a straightforward merge join across reftables, selecting the most
968 recent value for output, and omitting deleted references that do not
969 appear in remaining, lower reftables.
971 A compacted reftable should set its `min_update_index` to the smallest
972 of the input files' `min_update_index`, and its `max_update_index`
973 likewise to the largest input `max_update_index`.
975 For sake of illustration, assume the stack currently consists of
976 reftable files (from oldest to newest): A, B, C, and D. The compactor is
977 going to compact B and C, leaving A and D alone.
979 1. Obtain lock `tables.list.lock` and read the `tables.list` file.
980 2. Obtain locks `B.lock` and `C.lock`. Ownership of these locks
981 prevents other processes from trying to compact these files.
982 3. Release `tables.list.lock`.
983 4. Compact `B` and `C` into a temp file
984 `${min_update_index}-${max_update_index}_XXXXXX`.
985 5. Reacquire lock `tables.list.lock`.
986 6. Verify that `B` and `C` are still in the stack, in that order. This
987 should always be the case, assuming that other processes are adhering to
988 the locking protocol.
989 7. Rename `${min_update_index}-${max_update_index}_XXXXXX` to
990 `${min_update_index}-${max_update_index}-${random}.ref`.
991 8. Write the new stack to `tables.list.lock`, replacing `B` and `C`
992 with the file from (4).
993 9. Rename `tables.list.lock` to `tables.list`.
994 10. Delete `B` and `C`, perhaps after a short sleep to avoid forcing
995 readers to backtrack.
997 This strategy permits compactions to proceed independently of updates.
999 Each reftable (compacted or not) is uniquely identified by its name, so
1000 open reftables can be cached by their name.
1005 On windows, and other systems that do not allow deleting or renaming to open
1006 files, compaction may succeed, but other readers may prevent obsolete tables
1009 On these platforms, the following strategy can be followed: on closing a
1010 reftable stack, reload `tables.list`, and delete any tables no longer mentioned
1013 Irregular program exit may still leave about unused files. In this case, a
1014 cleanup operation can read `tables.list`, note its modification timestamp, and
1015 delete any unreferenced `*.ref` files that are older.
1018 Alternatives considered
1019 ~~~~~~~~~~~~~~~~~~~~~~~
1024 `bzip2` can significantly shrink a large packed-refs file (e.g. 62 MiB
1025 compresses to 23 MiB, 37%). However the bzip format does not support
1026 random access to a single reference. Readers must inflate and discard
1027 while performing a linear scan.
1029 Breaking packed-refs into chunks (individually compressing each chunk)
1030 would reduce the amount of data a reader must inflate, but still leaves
1031 the problem of indexing chunks to support readers efficiently locating
1034 Given the compression achieved by reftable's encoding, it does not seem
1035 necessary to add the complexity of bzip/gzip/zlib.
1037 Michael Haggerty's alternate format
1038 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
1040 Michael Haggerty proposed
1041 link:https://lore.kernel.org/git/CAMy9T_HCnyc1g8XWOOWhe7nN0aEFyyBskV2aOMb_fe%2BwGvEJ7A%40mail.gmail.com/[an
1042 alternate] format to reftable on the Git mailing list. This format uses
1043 smaller chunks, without the restart table, and avoids block alignment
1044 with padding. Reflog entries immediately follow each ref, and are thus
1045 interleaved between refs.
1047 Performance testing indicates reftable is faster for lookups (51%
1048 faster, 11.2 usec vs. 5.4 usec), although reftable produces a slightly
1049 larger file (+ ~3.2%, 28.3M vs 29.2M):
1051 [cols=">,>,>,>",options="header",]
1052 |=====================================
1053 |format |size |seek cold |seek hot
1054 |mh-alt |28.3 M |23.4 usec |11.2 usec
1055 |reftable |29.2 M |19.9 usec |5.4 usec
1056 |=====================================
1061 https://dev.eclipse.org/mhonarc/lists/jgit-dev/msg03073.html[JGit Ketch]
1063 link:https://lore.kernel.org/git/CAJo%3DhJvnAPNAdDcAAwAvU9C4RVeQdoS3Ev9WTguHx4fD0V_nOg%40mail.gmail.com/[RefTree],
1064 an encoding of references inside Git tree objects stored as part of the
1065 repository's object database.
1067 The RefTree format adds additional load on the object database storage
1068 layer (more loose objects, more objects in packs), and relies heavily on
1069 the packer's delta compression to save space. Namespaces which are flat
1070 (e.g. thousands of tags in refs/tags) initially create very large loose
1071 objects, and so RefTree does not address the problem of copying many
1072 references to modify a handful.
1074 Flat namespaces are not efficiently searchable in RefTree, as tree
1075 objects in canonical formatting cannot be binary searched. This fails
1076 the need to handle a large number of references in a single namespace,
1077 such as GitHub's `refs/pulls`, or a project with many tags.
1082 David Turner proposed
1083 https://lore.kernel.org/git/1455772670-21142-26-git-send-email-dturner@twopensource.com/[using
1084 LMDB], as LMDB is lightweight (64k of runtime code) and GPL-compatible
1087 A downside of LMDB is its reliance on a single C implementation. This
1088 makes embedding inside JGit (a popular reimplementation of Git)
1089 difficult, and hoisting onto virtual storage (for JGit DFS) virtually
1092 A common format that can be supported by all major Git implementations
1093 (git-core, JGit, libgit2) is strongly preferred.
projects / git / blob