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 a SHA-1 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 The first ref block shares the same block as the file header, and is 24
239 bytes smaller than all other blocks in the file. The first block
240 immediately begins after the file header, at position 24.
242 If the first block is a log block (a log-only file), its block header
243 begins immediately at position 24.
248 A ref block is written as:
254 uint24( restart_offset )+
255 uint16( restart_count )
260 Blocks begin with `block_type = 'r'` and a 3-byte `block_len` which
261 encodes the number of bytes in the block up to, but not including the
262 optional `padding`. This is always less than or equal to the file's
263 block size. In the first ref block, `block_len` includes 24 bytes for
266 The 2-byte `restart_count` stores the number of entries in the
267 `restart_offset` list, which must not be empty. Readers can use
268 `restart_count` to binary search between restarts before starting a
271 Exactly `restart_count` 3-byte `restart_offset` values precedes the
272 `restart_count`. Offsets are relative to the start of the block and
273 refer to the first byte of any `ref_record` whose name has not been
274 prefix compressed. Entries in the `restart_offset` list must be sorted,
275 ascending. Readers can start linear scans from any of these records.
277 A variable number of `ref_record` fill the middle of the block,
278 describing reference names and values. The format is described below.
280 As the first ref block shares the first file block with the file header,
281 all `restart_offset` in the first block are relative to the start of the
282 file (position 0), and include the file header. This forces the first
283 `restart_offset` to be `28`.
288 A `ref_record` describes a single reference, storing both the name and
289 its value(s). Records are formatted as:
292 varint( prefix_length )
293 varint( (suffix_length << 3) | value_type )
295 varint( update_index_delta )
299 The `prefix_length` field specifies how many leading bytes of the prior
300 reference record's name should be copied to obtain this reference's
301 name. This must be 0 for the first reference in any block, and also must
302 be 0 for any `ref_record` whose offset is listed in the `restart_offset`
303 table at the end of the block.
305 Recovering a reference name from any `ref_record` is a simple concat:
308 this_name = prior_name[0..prefix_length] + suffix
311 The `suffix_length` value provides the number of bytes available in
312 `suffix` to copy from `suffix` to complete the reference name.
314 The `update_index` that last modified the reference can be obtained by
315 adding `update_index_delta` to the `min_update_index` from the file
316 header: `min_update_index + update_index_delta`.
318 The `value` follows. Its format is determined by `value_type`, one of
321 * `0x0`: deletion; no value data (see transactions, below)
322 * `0x1`: one 20-byte object name; value of the ref
323 * `0x2`: two 20-byte object names; value of the ref, peeled target
324 * `0x3`: symbolic reference: `varint( target_len ) target`
326 Symbolic references use `0x3`, followed by the complete name of the
327 reference target. No compression is applied to the target name.
329 Types `0x4..0x7` are reserved for future use.
334 The ref index stores the name of the last reference from every ref block
335 in the file, enabling reduced disk seeks for lookups. Any reference can
336 be found by searching the index, identifying the containing block, and
337 searching within that block.
339 The index may be organized into a multi-level index, where the 1st level
340 index block points to additional ref index blocks (2nd level), which may
341 in turn point to either additional index blocks (e.g. 3rd level) or ref
342 blocks (leaf level). Disk reads required to access a ref go up with
343 higher index levels. Multi-level indexes may be required to ensure no
344 single index block exceeds the file format's max block size of
345 `16777215` bytes (15.99 MiB). To achieve constant O(1) disk seeks for
346 lookups the index must be a single level, which is permitted to exceed
347 the file's configured block size, but not the format's max block size of
350 If present, the ref index block(s) appears after the last ref block.
352 If there are at least 4 ref blocks, a ref index block should be written
353 to improve lookup times. Cold reads using the index require 2 disk reads
354 (read index, read block), and binary searching < 4 blocks also requires
355 <= 2 reads. Omitting the index block from smaller files saves space.
357 If the file is unaligned and contains more than one ref block, the ref
358 index must be written.
366 uint24( restart_offset )+
367 uint16( restart_count )
372 The index blocks begin with `block_type = 'i'` and a 3-byte `block_len`
373 which encodes the number of bytes in the block, up to but not including
374 the optional `padding`.
376 The `restart_offset` and `restart_count` fields are identical in format,
377 meaning and usage as in ref blocks.
379 To reduce the number of reads required for random access in very large
380 files the index block may be larger than other blocks. However, readers
381 must hold the entire index in memory to benefit from this, so it's a
382 time-space tradeoff in both file size and reader memory.
384 Increasing the file's block size decreases the index size. Alternatively
385 a multi-level index may be used, keeping index blocks within the file's
386 block size, but increasing the number of blocks that need to be
392 An index record describes the last entry in another block. Index records
396 varint( prefix_length )
397 varint( (suffix_length << 3) | 0 )
399 varint( block_position )
402 Index records use prefix compression exactly like `ref_record`.
404 Index records store `block_position` after the suffix, specifying the
405 absolute position in bytes (from the start of the file) of the block
406 that ends with this reference. Readers can seek to `block_position` to
407 begin reading the block header.
409 Readers must examine the block header at `block_position` to determine
410 if the next block is another level index block, or the leaf-level ref
416 Readers loading the ref index must first read the footer (below) to
417 obtain `ref_index_position`. If not present, the position will be 0. The
418 `ref_index_position` is for the 1st level root of the ref index.
423 Object blocks are optional. Writers may choose to omit object blocks,
424 especially if readers will not use the SHA-1 to ref mapping.
426 Object blocks use unique, abbreviated 2-20 byte SHA-1 keys, mapping to
427 ref blocks containing references pointing to that object directly, or as
428 the peeled value of an annotated tag. Like ref blocks, object blocks use
429 the file's standard block size. The abbrevation length is available in
430 the footer as `obj_id_len`.
432 To save space in small files, object blocks may be omitted if the ref
433 index is not present, as brute force search will only need to read a few
434 ref blocks. When missing, readers should brute force a linear search of
435 all references to lookup by SHA-1.
437 An object block is written as:
443 uint24( restart_offset )+
444 uint16( restart_count )
449 Fields are identical to ref block. Binary search using the restart table
450 works the same as in reference blocks.
452 Because object names are abbreviated by writers to the shortest
453 unique abbreviation within the reftable, obj key lengths are variable
454 between 2 and 20 bytes. Readers must compare only for common prefix
455 match within an obj block or obj index.
460 An `obj_record` describes a single object abbreviation, and the blocks
461 containing references using that unique abbreviation:
464 varint( prefix_length )
465 varint( (suffix_length << 3) | cnt_3 )
468 varint( position_delta )*
471 Like in reference blocks, abbreviations are prefix compressed within an
472 obj block. On large reftables with many unique objects, higher block
473 sizes (64k), and higher restart interval (128), a `prefix_length` of 2
474 or 3 and `suffix_length` of 3 may be common in obj records (unique
475 abbreviation of 5-6 raw bytes, 10-12 hex digits).
477 Each record contains `position_count` number of positions for matching
478 ref blocks. For 1-7 positions the count is stored in `cnt_3`. When
479 `cnt_3 = 0` the actual count follows in a varint, `cnt_large`.
481 The use of `cnt_3` bets most objects are pointed to by only a single
482 reference, some may be pointed to by a couple of references, and very
483 few (if any) are pointed to by more than 7 references.
485 A special case exists when `cnt_3 = 0` and `cnt_large = 0`: there are no
486 `position_delta`, but at least one reference starts with this
487 abbreviation. A reader that needs exact reference names must scan all
488 references to find which specific references have the desired object.
489 Writers should use this format when the `position_delta` list would have
490 overflowed the file's block size due to a high number of references
491 pointing to the same object.
493 The first `position_delta` is the position from the start of the file.
494 Additional `position_delta` entries are sorted ascending and relative to
495 the prior entry, e.g. a reader would perform:
498 pos = position_delta[0]
500 for (j = 1; j < position_count; j++) {
501 pos = prior + position_delta[j]
506 With a position in hand, a reader must linearly scan the ref block,
507 starting from the first `ref_record`, testing each reference's SHA-1s
508 (for `value_type = 0x1` or `0x2`) for full equality. Faster searching by
509 SHA-1 within a single ref block is not supported by the reftable format.
510 Smaller block sizes reduce the number of candidates this step must
516 The obj index stores the abbreviation from the last entry for every obj
517 block in the file, enabling reduced disk seeks for all lookups. It is
518 formatted exactly the same as the ref index, but refers to obj blocks.
520 The obj index should be present if obj blocks are present, as obj blocks
521 should only be written in larger files.
523 Readers loading the obj index must first read the footer (below) to
524 obtain `obj_index_position`. If not present, the position will be 0.
529 Unlike ref and obj blocks, log blocks are always unaligned.
531 Log blocks are variable in size, and do not match the `block_size`
532 specified in the file header or footer. Writers should choose an
533 appropriate buffer size to prepare a log block for deflation, such as
536 A log block is written as:
543 uint24( restart_offset )+
544 uint16( restart_count )
548 Log blocks look similar to ref blocks, except `block_type = 'g'`.
550 The 4-byte block header is followed by the deflated block contents using
551 zlib deflate. The `block_len` in the header is the inflated size
552 (including 4-byte block header), and should be used by readers to
553 preallocate the inflation output buffer. A log block's `block_len` may
554 exceed the file's block size.
556 Offsets within the log block (e.g. `restart_offset`) still include the
557 4-byte header. Readers may prefer prefixing the inflation output buffer
558 with the 4-byte header.
560 Within the deflate container, a variable number of `log_record` describe
561 reference changes. The log record format is described below. See ref
562 block format (above) for a description of `restart_offset` and
565 Because log blocks have no alignment or padding between blocks, readers
566 must keep track of the bytes consumed by the inflater to know where the
567 next log block begins.
572 Log record keys are structured as:
575 ref_name '\0' reverse_int64( update_index )
578 where `update_index` is the unique transaction identifier. The
579 `update_index` field must be unique within the scope of a `ref_name`.
580 See the update transactions section below for further details.
582 The `reverse_int64` function inverses the value so lexicographical
583 ordering the network byte order encoding sorts the more recent records
584 with higher `update_index` values first:
587 reverse_int64(int64 t) {
588 return 0xffffffffffffffff - t;
592 Log records have a similar starting structure to ref and index records,
593 utilizing the same prefix compression scheme applied to the log record
597 varint( prefix_length )
598 varint( (suffix_length << 3) | log_type )
603 varint( name_length ) name
604 varint( email_length ) email
605 varint( time_seconds )
607 varint( message_length ) message
611 Log record entries use `log_type` to indicate what follows:
613 * `0x0`: deletion; no log data.
614 * `0x1`: standard git reflog data using `log_data` above.
616 The `log_type = 0x0` is mostly useful for `git stash drop`, removing an
617 entry from the reflog of `refs/stash` in a transaction file (below),
618 without needing to rewrite larger files. Readers reading a stack of
619 reflogs must treat this as a deletion.
621 For `log_type = 0x1`, the `log_data` section follows
622 linkgit:git-update-ref[1] logging and includes:
624 * two 20-byte SHA-1s (old id, new id)
625 * varint string of committer's name
626 * varint string of committer's email
627 * varint time in seconds since epoch (Jan 1, 1970)
628 * 2-byte timezone offset in minutes (signed)
629 * varint string of message
631 `tz_offset` is the absolute number of minutes from GMT the committer was
632 at the time of the update. For example `GMT-0800` is encoded in reftable
633 as `sint16(-480)` and `GMT+0230` is `sint16(150)`.
635 The committer email does not contain `<` or `>`, it's the value normally
636 found between the `<>` in a git commit object header.
638 The `message_length` may be 0, in which case there was no message
639 supplied for the update.
641 Contrary to traditional reflog (which is a file), renames are encoded as
642 a combination of ref deletion and ref creation. A deletion is a log
643 record with a zero new_id, and a creation is a log record with a zero old_id.
648 Readers accessing the log must first read the footer (below) to
649 determine the `log_position`. The first block of the log begins at
650 `log_position` bytes since the start of the file. The `log_position` is
656 When importing from `$GIT_DIR/logs` writers should globally order all
657 log records roughly by timestamp while preserving file order, and assign
658 unique, increasing `update_index` values for each log line. Newer log
659 records get higher `update_index` values.
661 Although an import may write only a single reftable file, the reftable
662 file must span many unique `update_index`, as each log line requires its
663 own `update_index` to preserve semantics.
668 The log index stores the log key
669 (`refname \0 reverse_int64(update_index)`) for the last log record of
670 every log block in the file, supporting bounded-time lookup.
672 A log index block must be written if 2 or more log blocks are written to
673 the file. If present, the log index appears after the last log block.
674 There is no padding used to align the log index to block alignment.
676 Log index format is identical to ref index, except the keys are 9 bytes
677 longer to include `'\0'` and the 8-byte `reverse_int64(update_index)`.
678 Records use `block_position` to refer to the start of a log block.
683 Readers loading the log index must first read the footer (below) to
684 obtain `log_index_position`. If not present, the position will be 0.
689 After the last block of the file, a file footer is written. It begins
690 like the file header, but is extended with additional data.
692 A 68-byte footer appears at the end:
696 uint8( version_number = 1 )
698 uint64( min_update_index )
699 uint64( max_update_index )
701 uint64( ref_index_position )
702 uint64( (obj_position << 5) | obj_id_len )
703 uint64( obj_index_position )
705 uint64( log_position )
706 uint64( log_index_position )
708 uint32( CRC-32 of above )
711 If a section is missing (e.g. ref index) the corresponding position
712 field (e.g. `ref_index_position`) will be 0.
714 * `obj_position`: byte position for the first obj block.
715 * `obj_id_len`: number of bytes used to abbreviate object names in
717 * `log_position`: byte position for the first log block.
718 * `ref_index_position`: byte position for the start of the ref index.
719 * `obj_index_position`: byte position for the start of the obj index.
720 * `log_index_position`: byte position for the start of the log index.
725 Readers must seek to `file_length - 68` to access the footer. A trusted
726 external source (such as `stat(2)`) is necessary to obtain
727 `file_length`. When reading the footer, readers must verify:
729 * 4-byte magic is correct
730 * 1-byte version number is recognized
731 * 4-byte CRC-32 matches the other 64 bytes (including magic, and
734 Once verified, the other fields of the footer can be accessed.
739 Binary search within a block is supported by the `restart_offset` fields
740 at the end of the block. Readers can binary search through the restart
741 table to locate between which two restart points the sought reference or
744 Each record identified by a `restart_offset` stores the complete key in
745 the `suffix` field of the record, making the compare operation during
746 binary search straightforward.
748 Once a restart point lexicographically before the sought reference has
749 been identified, readers can linearly scan through the following record
750 entries to locate the sought record, terminating if the current record
751 sorts after (and therefore the sought key is not present).
753 Restart point selection
754 +++++++++++++++++++++++
756 Writers determine the restart points at file creation. The process is
757 arbitrary, but every 16 or 64 records is recommended. Every 16 may be
758 more suitable for smaller block sizes (4k or 8k), every 64 for larger
761 More frequent restart points reduces prefix compression and increases
762 space consumed by the restart table, both of which increase file size.
764 Less frequent restart points makes prefix compression more effective,
765 decreasing overall file size, with increased penalties for readers
766 walking through more records after the binary search step.
768 A maximum of `65535` restart points per block is supported.
773 Lightweight refs dominate
774 ^^^^^^^^^^^^^^^^^^^^^^^^^
776 The reftable format assumes the vast majority of references are single
777 SHA-1 valued with common prefixes, such as Gerrit Code Review's
778 `refs/changes/` namespace, GitHub's `refs/pulls/` namespace, or many
779 lightweight tags in the `refs/tags/` namespace.
781 Annotated tags storing the peeled object cost an additional 20 bytes per
787 A reftable with very few references (e.g. git.git with 5 heads) is 269
788 bytes for reftable, vs. 332 bytes for packed-refs. This supports
789 reftable scaling down for transaction logs (below).
794 For a Gerrit Code Review type repository with many change refs, larger
795 block sizes (64 KiB) and less frequent restart points (every 64) yield
796 better compression due to more references within the block compressing
797 against the prior reference.
799 Larger block sizes reduce the index size, as the reftable will require
800 fewer blocks to store the same number of references.
805 Assuming the index block has been loaded into memory, binary searching
806 for any single reference requires exactly 1 disk seek to load the
809 Scans and lookups dominate
810 ^^^^^^^^^^^^^^^^^^^^^^^^^^
812 Scanning all references and lookup by name (or namespace such as
813 `refs/heads/`) are the most common activities performed on repositories.
814 SHA-1s are stored directly with references to optimize this use case.
816 Logs are infrequently read
817 ^^^^^^^^^^^^^^^^^^^^^^^^^^
819 Logs are infrequently accessed, but can be large. Deflating log blocks
820 saves disk space, with some increased penalty at read time.
822 Logs are stored in an isolated section from refs, reducing the burden on
823 reference readers that want to ignore logs. Further, historical logs can
824 be isolated into log-only files.
826 Logs are read backwards
827 ^^^^^^^^^^^^^^^^^^^^^^^
829 Logs are frequently accessed backwards (most recent N records for master
830 to answer `master@{4}`), so log records are grouped by reference, and
831 sorted descending by update index.
839 A repository must set its `$GIT_DIR/config` to configure reftable:
843 repositoryformatversion = 1
845 refStorage = reftable
851 A collection of reftable files are stored in the `$GIT_DIR/reftable/`
855 00000001-00000001.log
856 00000002-00000002.ref
857 00000003-00000003.ref
860 where reftable files are named by a unique name such as produced by the
861 function `${min_update_index}-${max_update_index}.ref`.
863 Log-only files use the `.log` extension, while ref-only and mixed ref
864 and log files use `.ref`. extension.
866 The stack ordering file is `$GIT_DIR/reftable/tables.list` and lists the
867 current files, one per line, in order, from oldest (base) to newest
871 $ cat .git/reftable/tables.list
872 00000001-00000001.log
873 00000002-00000002.ref
874 00000003-00000003.ref
877 Readers must read `$GIT_DIR/reftable/tables.list` to determine which
878 files are relevant right now, and search through the stack in reverse
879 order (last reftable is examined first).
881 Reftable files not listed in `tables.list` may be new (and about to be
882 added to the stack by the active writer), or ancient and ready to be
885 Backward compatibility
886 ^^^^^^^^^^^^^^^^^^^^^^
888 Older clients should continue to recognize the directory as a git
889 repository so they don't look for an enclosing repository in parent
890 directories. To this end, a reftable-enabled repository must contain the
891 following dummy files
893 * `.git/HEAD`, a regular file containing `ref: refs/heads/.invalid`.
894 * `.git/refs/`, a directory
895 * `.git/refs/heads`, a regular file
900 Readers can obtain a consistent snapshot of the reference space by
903 1. Open and read the `tables.list` file.
904 2. Open each of the reftable files that it mentions.
905 3. If any of the files is missing, goto 1.
906 4. Read from the now-open files as long as necessary.
911 Although reftables are immutable, mutations are supported by writing a
912 new reftable and atomically appending it to the stack:
914 1. Acquire `tables.list.lock`.
915 2. Read `tables.list` to determine current reftables.
916 3. Select `update_index` to be most recent file's
917 `max_update_index + 1`.
918 4. Prepare temp reftable `tmp_XXXXXX`, including log entries.
919 5. Rename `tmp_XXXXXX` to `${update_index}-${update_index}.ref`.
920 6. Copy `tables.list` to `tables.list.lock`, appending file from (5).
921 7. Rename `tables.list.lock` to `tables.list`.
923 During step 4 the new file's `min_update_index` and `max_update_index`
924 are both set to the `update_index` selected by step 3. All log records
925 for the transaction use the same `update_index` in their keys. This
926 enables later correlation of which references were updated by the same
929 Because a single `tables.list.lock` file is used to manage locking, the
930 repository is single-threaded for writers. Writers may have to busy-spin
931 (with backoff) around creating `tables.list.lock`, for up to an
932 acceptable wait period, aborting if the repository is too busy to
933 mutate. Application servers wrapped around repositories (e.g. Gerrit
934 Code Review) can layer their own lock/wait queue to improve fairness to
940 Deletion of any reference can be explicitly stored by setting the `type`
941 to `0x0` and omitting the `value` field of the `ref_record`. This serves
942 as a tombstone, overriding any assertions about the existence of the
943 reference from earlier files in the stack.
948 A partial stack of reftables can be compacted by merging references
949 using a straightforward merge join across reftables, selecting the most
950 recent value for output, and omitting deleted references that do not
951 appear in remaining, lower reftables.
953 A compacted reftable should set its `min_update_index` to the smallest
954 of the input files' `min_update_index`, and its `max_update_index`
955 likewise to the largest input `max_update_index`.
957 For sake of illustration, assume the stack currently consists of
958 reftable files (from oldest to newest): A, B, C, and D. The compactor is
959 going to compact B and C, leaving A and D alone.
961 1. Obtain lock `tables.list.lock` and read the `tables.list` file.
962 2. Obtain locks `B.lock` and `C.lock`. Ownership of these locks
963 prevents other processes from trying to compact these files.
964 3. Release `tables.list.lock`.
965 4. Compact `B` and `C` into a temp file
966 `${min_update_index}-${max_update_index}_XXXXXX`.
967 5. Reacquire lock `tables.list.lock`.
968 6. Verify that `B` and `C` are still in the stack, in that order. This
969 should always be the case, assuming that other processes are adhering to
970 the locking protocol.
971 7. Rename `${min_update_index}-${max_update_index}_XXXXXX` to
972 `${min_update_index}-${max_update_index}.ref`.
973 8. Write the new stack to `tables.list.lock`, replacing `B` and `C`
974 with the file from (4).
975 9. Rename `tables.list.lock` to `tables.list`.
976 10. Delete `B` and `C`, perhaps after a short sleep to avoid forcing
977 readers to backtrack.
979 This strategy permits compactions to proceed independently of updates.
981 Each reftable (compacted or not) is uniquely identified by its name, so
982 open reftables can be cached by their name.
984 Alternatives considered
985 ~~~~~~~~~~~~~~~~~~~~~~~
990 `bzip2` can significantly shrink a large packed-refs file (e.g. 62 MiB
991 compresses to 23 MiB, 37%). However the bzip format does not support
992 random access to a single reference. Readers must inflate and discard
993 while performing a linear scan.
995 Breaking packed-refs into chunks (individually compressing each chunk)
996 would reduce the amount of data a reader must inflate, but still leaves
997 the problem of indexing chunks to support readers efficiently locating
1000 Given the compression achieved by reftable's encoding, it does not seem
1001 necessary to add the complexity of bzip/gzip/zlib.
1003 Michael Haggerty's alternate format
1004 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
1006 Michael Haggerty proposed
1007 link:https://lore.kernel.org/git/CAMy9T_HCnyc1g8XWOOWhe7nN0aEFyyBskV2aOMb_fe%2BwGvEJ7A%40mail.gmail.com/[an
1008 alternate] format to reftable on the Git mailing list. This format uses
1009 smaller chunks, without the restart table, and avoids block alignment
1010 with padding. Reflog entries immediately follow each ref, and are thus
1011 interleaved between refs.
1013 Performance testing indicates reftable is faster for lookups (51%
1014 faster, 11.2 usec vs. 5.4 usec), although reftable produces a slightly
1015 larger file (+ ~3.2%, 28.3M vs 29.2M):
1017 [cols=">,>,>,>",options="header",]
1018 |=====================================
1019 |format |size |seek cold |seek hot
1020 |mh-alt |28.3 M |23.4 usec |11.2 usec
1021 |reftable |29.2 M |19.9 usec |5.4 usec
1022 |=====================================
1027 https://dev.eclipse.org/mhonarc/lists/jgit-dev/msg03073.html[JGit Ketch]
1029 link:https://lore.kernel.org/git/CAJo%3DhJvnAPNAdDcAAwAvU9C4RVeQdoS3Ev9WTguHx4fD0V_nOg%40mail.gmail.com/[RefTree],
1030 an encoding of references inside Git tree objects stored as part of the
1031 repository's object database.
1033 The RefTree format adds additional load on the object database storage
1034 layer (more loose objects, more objects in packs), and relies heavily on
1035 the packer's delta compression to save space. Namespaces which are flat
1036 (e.g. thousands of tags in refs/tags) initially create very large loose
1037 objects, and so RefTree does not address the problem of copying many
1038 references to modify a handful.
1040 Flat namespaces are not efficiently searchable in RefTree, as tree
1041 objects in canonical formatting cannot be binary searched. This fails
1042 the need to handle a large number of references in a single namespace,
1043 such as GitHub's `refs/pulls`, or a project with many tags.
1048 David Turner proposed
1049 https://lore.kernel.org/git/1455772670-21142-26-git-send-email-dturner@twopensource.com/[using
1050 LMDB], as LMDB is lightweight (64k of runtime code) and GPL-compatible
1053 A downside of LMDB is its reliance on a single C implementation. This
1054 makes embedding inside JGit (a popular reimplementation of Git)
1055 difficult, and hoisting onto virtual storage (for JGit DFS) virtually
1058 A common format that can be supported by all major Git implementations
1059 (git-core, JGit, libgit2) is strongly preferred.
1067 Version will bump (e.g. 2) to indicate `value` uses a different object
1068 name length other than 20. The length could be stored in an expanded file
1069 heaer, or hardcoded as part of the version.
projects / thirdparty / git.git / blob