{"thread":{"id":"46487","subject":"Re: reftable [v4]: new ref storage format","startedAt":"2017-07-31T03:51:53Z","lastAt":"2017-08-05T21:01:08Z","messageCount":34,"participants":["Shawn Pearce","Dave Borowitz","Stefan Beller","Junio C Hamano","Michael Haggerty","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"325294","messageId":"CAJo=hJv7scc1L0_MdRkFeLAJGjYm2UkTFNOgj2e4+9Zj7KSiiQ@mail.gmail.com","threadId":"46487","inReplyTo":null,"subject":"Re: reftable [v4]: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-07-31T03:51:24Z","receivedAt":"2017-07-31T03:51:53Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"4th iteration of the reftable storage format.\n\nYou can read a rendered version of this here:\nhttps://googlers.googlesource.com/sop/jgit/+/reftable/Documentation/technical/reftable.md\n\nSignificant changes from v3:\n- Incorporated Michael Haggerty's update_index concept for reflog.\n- Explicitly documented log-only tables.\n\n- Magic changed to 'REFT'\n- Symlinks now use type 0x3 with \"ref: \" prefix.\n- Ref-like files (FETCH_HEAD, MERGE_HEAD) also use type 0x3.\n- restart_count simplified, obj block_count simplified\n\n\n# reftable\n\n[TOC]\n\n## Overview\n\n### Problem statement\n\nSome repositories contain a lot of references (e.g. android at 866k,\nrails at 31k). The existing packed-refs format takes up a lot of\nspace (e.g. 62M), and does not scale with additional references.\nLookup of a single reference requires linearly scanning the file.\n\nAtomic pushes modifying multiple references require copying the\nentire packed-refs file, which can be a considerable amount of data\nmoved (e.g. 62M in, 62M out) for even small transactions (2 refs\nmodified).\n\nRepositories with many loose references occupy a large number of disk\nblocks from the local file system, as each reference is its own file\nstoring 41 bytes (and another file for the corresponding reflog).\nThis negatively affects the number of inodes available when a large\nnumber of repositories are stored on the same filesystem. Readers can\nbe penalized due to the larger number of syscalls required to traverse\nand read the `$GIT_DIR/refs` directory.\n\n### Objectives\n\n- Near constant time lookup for any single reference, even when the\n repository is cold and not in process or kernel cache.\n- Near constant time verification a SHA-1 is referred to by at least\n one reference (for allow-tip-sha1-in-want).\n- Efficient lookup of an entire namespace, such as `refs/tags/`.\n- Support atomic push with `O(size_of_update)` operations.\n- Combine reflog storage with ref storage for small transactions.\n- Separate reflog storage for base refs and historical logs.\n\n### Description\n\nA reftable file is a portable binary file format customized for\nreference storage. References are sorted, enabling linear scans,\nbinary search lookup, and range scans.\n\nStorage in the file is organized into blocks. Prefix compression\nis used within a single block to reduce disk space. Block size is\ntunable by the writer.\n\n### Performance\n\nSpace used, packed-refs vs. reftable:\n\nrepository | packed-refs | reftable | % original | avg ref | avg obj\n-----------|------------:|---------:|-----------:|---------:|--------:\nandroid | 62.2 M | 34.4 M | 55.2% | 33 bytes | 8 bytes\nrails | 1.8 M | 1.1 M | 57.7% | 29 bytes | 6 bytes\ngit | 78.7 K | 44.0 K | 60.0% | 50 bytes | 6 bytes\ngit (heads)| 332 b | 276 b | 83.1% | 34 bytes | 0 bytes\n\nScan (read 866k refs), by reference name lookup (single ref from 866k\nrefs), and by SHA-1 lookup (refs with that SHA-1, from 866k refs):\n\nformat | cache | scan | by name | by SHA-1\n------------|------:|--------:|---------------:|---------------:\npacked-refs | cold | 402 ms | 409,660.1 usec | 412,535.8 usec\npacked-refs | hot | | 6,844.6 usec | 20,110.1 usec\nreftable | cold | 112 ms | 33.9 usec | 323.2 usec\nreftable | hot | | 20.2 usec | 320.8 usec\n\nSpace used for 149,932 log entries for 43,061 refs,\nreflog vs. reftable:\n\nformat | size | avg entry\n--------------|------:|-----------:\n$GIT_DIR/logs | 173 M | 1209 bytes\nreftable | 5 M | 37 bytes\n\n## Details\n\n### Peeling\n\nReferences in a reftable are always peeled.\n\n### Reference name encoding\n\nReference names should be encoded with UTF-8.\n\n### Network byte order\n\nAll multi-byte, fixed width fields are in network byte order.\n\n### Ordering\n\nBlocks are lexicographically ordered by their first reference.\n\n### Directory/file conflicts\n\nThe reftable format accepts both `refs/heads/foo` and\n`refs/heads/foo/bar` as distinct references.\n\nThis property is useful for retaining log records in reftable, but may\nconfuse versions of Git using `$GIT_DIR/refs` directory tree to\nmaintain references. Users of reftable may choose to continue to\nreject `foo` and `foo/bar` type conflicts to prevent problems for\npeers.\n\n## File format\n\n### Structure\n\nA reftable file has the following high-level structure:\n\n first_block {\n header\n first_ref_block\n }\n ref_blocks*\n ref_index?\n obj_blocks*\n obj_index?\n log_blocks*\n log_index?\n footer\n\nA log-only file omits the `ref_blocks`, `ref_index`, `obj_blocks` and\n`obj_index` sections, containing only the file header and log blocks:\n\n first_block {\n header\n }\n log_blocks*\n log_index?\n footer\n\nin a log-only file the first log block immediately follows the file\nheader, without padding to block alignment.\n\n### Block size\n\nThe `block_size` is arbitrarily determined by the writer, and does not\nhave to be a power of 2. The block size must be larger than the\nlongest reference name or log entry used in the repository, as\nreferences cannot span blocks.\n\nPowers of two that are friendly to the virtual memory system or\nfilesystem (such as 4k or 8k) are recommended. Larger sizes (64k) can\nyield better compression, with a possible increased cost incurred by\nreaders during access.\n\nThe largest block size is `16777215` bytes (15.99 MiB).\n\n### Header\n\nA 24-byte header appears at the beginning of the file:\n\n 'REFT'\n uint8( version_number = 1 )\n uint24( block_size )\n uint64( min_update_index )\n uint64( max_update_index )\n\nThe `min_update_index` and `max_update_index` describe bounds for the\n`update_index` field of all log records in this file. When reftables\nare used in a stack for transactions (see below), these fields can\norder the files such that the prior file's `max_update_index + 1` is\nthe next file's `min_update_index`.\n\n### First ref block\n\nThe first ref block shares the same block as the file header, and is\n24 bytes smaller than all other blocks in the file. The first block\nimmediately begins after the file header, at offset 24.\n\nIf the first block is a log block (a log only table), its block header\nbegins immediately at offset 24.\n\n### Ref block format\n\nA ref block is written as:\n\n 'r'\n uint24( block_len )\n ref_record+\n uint32( restart_offset )+\n uint16( restart_count )\n padding?\n\nBlocks begin with `block_type = 'r'` and a 3-byte `block_len` which\nencodes the number of bytes in the block up to, but not including the\noptional `padding`. This is almost always shorter than the file's\n`block_size`. In the first ref block, `block_len` includes 24 bytes\nfor the file header.\n\nThe 4-byte block header is followed by a variable number of\n`ref_record`, describing reference names and values. The format\nis described below.\n\nA variable number of 4-byte `restart_offset` values follow the\nrecords. Offsets are relative to the start of the block and refer to\nthe first byte of any `ref_record` whose name has not been prefix\ncompressed. Entries in the `restart_offset` list must be sorted,\nascending. Readers can start linear scans from any of these records.\n\nAs the first ref block shares the first file block with the file\nheader, offsets in the first block are relative to the start of the\nfile (position 0), and include the file header. This requires the\nfirst restart in the first block to be at offset 24. Restarts in\nsubsequent ref blocks are relative to the start of the ref block.\n\nThe 2-byte `restart_count` stores the number of entries in the\n`restart_offset` list, which must not be empty.\n\nReaders can use the restart count to binary search between restarts\nbefore starting a linear scan. The `restart_count` field must be\nthe last 2 bytes of the block as specified by `block_len` from the\nblock header.\n\nThe end of the block may be filled with `padding` NUL bytes to fill\nout the block to the common `block_size` as specified in the file\nheader. Padding may be necessary to ensure the following block starts\nat a block alignment, and does not spill into the tail of this block.\nPadding may be omitted if the block is the last block of the file, and\nthere is no index block. This allows reftable to efficiently scale\ndown to a small number of refs.\n\n#### ref record\n\nA `ref_record` describes a single reference, storing both the name and\nits value(s). Records are formatted as:\n\n varint( prefix_length )\n varint( (suffix_length << 3) | value_type )\n suffix\n value?\n\nThe `prefix_length` field specifies how many leading bytes of the\nprior reference record's name should be copied to obtain this\nreference's name. This must be 0 for the first reference in any\nblock, and also must be 0 for any `ref_record` whose offset is listed\nin the `restart_offset` table at the end of the block.\n\nRecovering a reference name from any `ref_record` is a simple concat:\n\n this_name = prior_name[0..prefix_length] + suffix\n\nThe `suffix_length` value provides the number of bytes to copy from\n`suffix` to complete the reference name.\n\nThe `value` follows. Its format is determined by `value_type`, one of\nthe following:\n\n- `0x0`: deletion; no value data (see transactions, below)\n- `0x1`: one 20-byte object id; value of the ref\n- `0x2`: two 20-byte object ids; value of the ref, peeled target\n- `0x3`: symref and text: `varint( text_len ) text`\n- `0x4`: index record (see below)\n- `0x5`: log record (see below)\n\nSymbolic references use `0x3` with a `text` string starting with `\"ref: \"`,\nfollowed by the complete name of the reference target. No\ncompression is applied to the target name. Other types of contents\nthat are also reference like, such as `FETCH_HEAD` and `MERGE_HEAD`,\nmay also be stored using type `0x3`.\n\nTypes `0x6..0x7` are reserved for future use.\n\n### Ref index\n\nThe ref index stores the name of the last reference from every ref\nblock in the file, enabling constant O(1) disk seeks for all lookups.\nAny reference can be found by searching the index, identifying the\ncontaining block, and searching within that block.\n\nIf present the ref index block appears after the last ref block. The\nprior ref block should be padded to ensure the ref index starts on a\nblock alignment.\n\nAn index block should only be written if there are at least 4 blocks\nin the file, as cold reads using the index requires 2 disk reads (read\nindex, read block), and binary searching <= 4 blocks also requires <=\n2 reads. Omitting the index block from smaller files saves space.\n\nIndex block format:\n\n uint32( (0x80 << 24) | block_len )\n index_record+\n uint32( restart_offset )+\n uint16( restart_count )\n padding?\n\nThe index block header starts with the high bit set. This identifies\nthe block as an index block, and not as a ref block, log block or file\nfooter. The `block_len` field in an index block is 30-bits network\nbyte order, and allowed to occupy space normally used by the block\ntype in other blocks. This supports indexes significantly larger than\nthe file's `block_size`.\n\nThe `restart_offset` and `restart_count` fields are identical in\nformat, meaning and usage as in ref blocks.\n\nTo reduce the number of reads required for random access in very large\nfiles, the index block may be larger than the other blocks. However,\nreaders must hold the entire index in memory to benefit from this, so\nit's a time-space tradeoff in both file size and reader memory.\nIncreasing the block size decreases the index size.\n\nWhen object blocks are present the ref index block is padded with\n`padding` to maintain alignment for the next block. No padding is\nnecessary if log blocks or the file trailer follows the ref index.\n\n#### index record\n\nAn index record describes the last entry in another block.\nIndex records are written as:\n\n varint( prefix_length )\n varint( (suffix_length << 3) | 0x4 )\n suffix\n varint( block_position )\n\nIndex records use prefix compression exactly like `ref_record`.\n\nIndex records store `block_position` after the suffix, specifying the\nabsolute position in bytes (from the start of the file) of the block\nthat ends with this reference. Readers can seek to `block_position` to\nbegin reading the block header.\n\n#### Reading the index\n\nReaders loading the ref index must first read the footer (below) to\nobtain `ref_index_offset`. If not present, the offset will be 0.\n\n### Obj block format\n\nObject blocks use unique, abbreviated 2-20 byte SHA-1 keys, mapping\nto ref blocks containing references pointing to that object directly,\nor as the peeled value of an annotated tag. Like ref blocks, object\nblocks use the file's standard `block_size`.\n\nTo save space in small files, object blocks may be omitted if the ref\nindex is not present. When missing readers should brute force a\nlinear search of all references to lookup by SHA-1.\n\nAn object block is written as:\n\n 'o'\n uint24( block_len )\n obj_record+\n uint32( restart_offset )+\n uint16( restart_count )\n padding?\n\nFields are identical to ref block. Binary search using the restart\ntable works the same as in reference blocks.\n\nBecause object identifiers are abbreviated by writers to the shortest\nunique abbreviation within the reftable, obj key lengths are variable\nbetween 2 and 20 bytes. Readers must compare only for common prefix\nmatch within an obj block or obj index.\n\nObject blocks should be block aligned, according to `block_size` from\nthe file header. The `padding` field is filled with NULs to maintain\nalignment for the next block.\n\n#### obj record\n\nAn `obj_record` describes a single object abbreviation, and the blocks\ncontaining references using that unique abbreviation:\n\n varint( prefix_length )\n varint( (suffix_length << 3) | cnt_3 )\n suffix\n varint( cnt_large )?\n varint( block_delta )+\n\nLike in reference blocks, abbreviations are prefix compressed within\nan obj block. On large reftables with many unique objects, higher\nblock sizes (64k), and higher restart interval (128), a\n`prefix_length` of 2 or 3 and `suffix_length` of 3 may be common in\nobj records (unique abbreviation of 5-6 raw bytes, 10-12 hex digits).\n\nEach record contains `block_count` number of block identifiers for ref\nblocks. For 1-7 blocks the block count is stored in `cnt_3`. When\n`cnt_3 = 0` the actual block count follows in a varint, `cnt_large`.\n\nThe first `block_delta` is the absolute block identifier counting from\nthe start of the file. The offset of that block can be obtained by\n`block_delta[0] * block_size`. Additional `block_delta` entries are\nrelative to the prior entry, e.g. a reader would perform:\n\n block_id = block_delta[0]\n prior = block_id\n for (j = 1; j < block_count; j++) {\n block_id = prior + block_delta[j]\n prior = block_id\n }\n\nWith a `block_id` in hand, a reader must linearly scan the ref block\nat `block_id * block_size` offset in the file, starting from the first\n`ref_record`, testing each reference's SHA-1s (for `value_type = 0x1`\nor `0x2`) for full equality. Faster searching by SHA-1 within a\nsingle ref block is not supported by the reftable format. Smaller\nblock sizes reduces the number of candidates this step must consider.\n\n### Obj index\n\nThe obj index stores the abbreviation from the last entry for every\nobj block in the file, enabling constant O(1) disk seeks for all\nlookups. It is formatted exactly the same as the ref index, but\nrefers to obj blocks.\n\nThe obj index should be present if obj blocks are present, as\nobj blocks should only be written in larger files.\n\nThe obj index should be block aligned, according to `block_size` from\nthe file header. This requires padding the last obj block to maintain\nalignment.\n\nReaders loading the obj index must first read the footer (below) to\nobtain `obj_index_offset`. If not present, the offset will be 0.\n\n### Log block format\n\nUnlike ref and obj blocks, log block sizes are variable in size, and\ndo not match the `block_size` specified in the file header or footer.\nWriters should choose an appropriate buffer size to prepare a log block\nfor deflation, such as `2 * block_size`.\n\nA log block is written as:\n\n 'g'\n uint24( block_len )\n zlib_deflate {\n log_record+\n int32( restart_offset )+\n int16( restart_count )\n }\n\nLog blocks look similar to ref blocks, except `block_type = 'g'`.\n\nThe 4-byte block header is followed by the deflated block contents\nusing zlib deflate. The `block_len` in the header is the inflated\nsize (including 4-byte block header), and should be used by readers to\npreallocate the inflation output buffer. Offsets within the block\n(e.g. `restart_offset`) still include the 4-byte header. Readers may\nprefer prefixing the inflation output buffer with the 4-byte header.\n\nWithin the deflate container, a variable number of `log_record`\ndescribe reference changes. The log record format is described\nbelow. See ref block format (above) for a description of\n`restart_offset` and `restart_count`.\n\nUnlike ref blocks, log blocks are written at any alignment, without\npadding. The first log block immediately follows the end of the prior\nblock, which omits its trailing padding. In very small files the log\nblock may appear in the first block.\n\nBecause log blocks have no alignment or padding between blocks,\nreaders must keep track of the bytes consumed by the inflater to\nknow where the next log block begins.\n\n#### log record\n\nLog record keys are structured as:\n\n ref_name '\\0' reverse_int64( update_index )\n\nwhere `update_index` is the unique transaction identifier. The\n`update_index` field must be unique within the scope of a `ref_name`.\nSee the update index section below for further details.\n\nThe `reverse_int64` function inverses the value so lexographical\nordering the network byte order encoding sorts the more recent records\nwith higher `update_index` values first:\n\n reverse_int64(int64 t) {\n return 0xffffffffffffffff - t;\n }\n\nLog records have a similar starting structure to ref and index\nrecords, utilizing the same prefix compression scheme applied to the\nlog record key described above.\n\n```\n varint( prefix_length )\n varint( (suffix_length << 3) | 0x5 )\n suffix\n\n old_id\n new_id\n varint( time_seconds )\n sint16( tz_offset )\n varint( name_length ) name\n varint( email_length ) email\n varint( message_length ) message\n```\n\nThe value data following the key suffix is complex:\n\n- two 20-byte SHA-1s (old id, new id)\n- varint time in seconds since epoch (Jan 1, 1970)\n- 2-byte timezone offset (signed)\n- varint string of committer's name\n- varint string of committer's email\n- varint string of message\n\n`tz_offset` is the absolute number of minutes from GMT the committer\nwas at the time of the update. For example `GMT-0800` is encoded in\nreftable as `sint16(-480)` and `GMT+0230` is `sint16(150)`.\n\nThe `message_length` may be 0, in which case there was no message\nsupplied for the update.\n\n#### Reading the log\n\nReaders accessing the log must first read the footer (below) to\ndetermine the `log_offset`. The first block of the log begins at\n`log_offset` bytes since the start of the file. The `log_offset` is\nnot block aligned.\n\n#### Importing logs\n\nWhen importing from `$GIT_DIR/logs` writers should globally order all\nlog records roughly by timestamp while preserving file order, and\nassign unique, increasing `update_index` values for each log line.\n\n### Log index\n\nThe log index stores the log key (`refname \\0 reverse_int64(update_index)`)\nfor the last log record of every log block in the file, supporting\nbounded-time lookup.\n\nA log index block must be written if 2 or more log blocks are written\nto the file. If present, the log index appears after the last log\nblock. There is no padding used to align the log index to block\nalignment.\n\nLog index format is identical to ref index, except the keys are 9\nbytes longer to include `'\\0'` and the 8-byte\n`reverse_int64(update_index)`. Records use `block_position` to\nrefer to the start of a log block.\n\n#### Reading the index\n\nReaders loading the log index must first read the footer (below) to\nobtain `log_index_offset`. If not present, the offset will be 0.\n\n### Footer\n\nAfter the last block of the file, a file footer is written. It begins\nlike the file header, but is extended with additional data.\n\nA 68-byte footer appears at the end:\n\n```\n 'REFT'\n uint8( version_number = 1 )\n uint24( block_size )\n uint64( min_update_index )\n uint64( max_update_index )\n\n uint64( ref_index_offset )\n uint64( obj_offset )\n uint64( obj_index_offset )\n\n uint64( log_offset )\n uint64( log_index_offset )\n\n uint32( CRC-32 of above )\n```\n\nIf a section is missing (e.g. ref index) the corresponding offset\nfield (e.g. `ref_index_offset`) will be 0.\n\n- `obj_offset`: byte offset for the first obj block.\n- `log_offset`: byte offset for the first log block.\n- `ref_index_offset`: byte offset for the start of the ref index.\n- `obj_index_offset`: byte offset for the start of the obj index.\n- `log_index_offset`: byte offset for the start of the log index.\n\n#### Reading the footer\n\nReaders must seek to `file_length - 68` to access the footer. A\ntrusted external source (such as `stat(2)`) is necessary to obtain\n`file_length`. When reading the footer, readers must verify:\n\n- 4-byte magic is correct\n- 1-byte version number is recognized\n- 4-byte CRC-32 matches the other 64 bytes (including magic, and version)\n\nOnce verified, the other fields of the footer can be accessed.\n\n### Varint encoding\n\nVarint encoding is identical to the ofs-delta encoding method used\nwithin pack files.\n\nDecoder works such as:\n\n val = buf[ptr] & 0x7f\n while (buf[ptr] & 0x80) {\n ptr++\n val = ((val + 1) << 7) | (buf[ptr] & 0x7f)\n }\n\n### Binary search\n\nBinary search within a block is supported by the `restart_offset`\nfields at the end of the block. Readers can binary search through the\nrestart table to locate between which two restart points the sought\nreference or key should appear.\n\nEach record identified by a `restart_offset` stores the complete key\nin the `suffix` field of the record, making the compare operation\nduring binary search straightforward.\n\nOnce a restart point lexicographically before the sought reference has\nbeen identified, readers can linearly scan through the following\nrecord entries to locate the sought record, terminating if the current\nrecord sorts after (and therefore the sought key is not present).\n\n#### Restart point selection\n\nWriters determine the restart points at file creation. The process is\narbitrary, but every 16 or 64 records is recommended. Every 16 may\nbe more suitable for smaller block sizes (4k or 8k), every 64 for\nlarger block sizes (64k).\n\nMore frequent restart points reduces prefix compression and increases\nspace consumed by the restart table, both of which increase file size.\n\nLess frequent restart points makes prefix compression more effective,\ndecreasing overall file size, with increased penalities for readers\nwalking through more records after the binary search step.\n\nA maximum of `65535` restart points per block is supported.\n\n## Considerations\n\n### Lightweight refs dominate\n\nThe reftable format assumes the vast majority of references are single\nSHA-1 valued with common prefixes, such as Gerrit Code Review's\n`refs/changes/` namespace, GitHub's `refs/pulls/` namespace, or many\nlightweight tags in the `refs/tags/` namespace.\n\nAnnotated tags storing the peeled object cost only an additional 20\nbytes per reference.\n\n### Low overhead\n\nA reftable with very few references (e.g. git.git with 5 heads)\nis 276 bytes for reftable, vs. 332 bytes for packed-refs. This\nsupports reftable scaling down for transaction logs (below).\n\n### Block size\n\nFor a Gerrit Code Review type repository with many change refs, larger\nblock sizes (64 KiB) and less frequent restart points (every 64) yield\nbetter compression due to more references within the block compressing\nagainst the prior reference.\n\nLarger block sizes reduces the index size, as the reftable will\nrequire fewer blocks to store the same number of references.\n\n### Minimal disk seeks\n\nAssuming the index block has been loaded into memory, binary searching\nfor any single reference requires exactly 1 disk seek to load the\ncontaining block.\n\n### Scans and lookups dominate\n\nScanning all references and lookup by name (or namespace such as\n`refs/heads/`) are the most common activities performed by repositories.\nSHA-1s are stored twice when obj blocks are present, avoiding disk\nseeks for the common cases of scan and lookup by name.\n\n### Logs are infrequently read\n\nLogs are infrequently accessed, but can be large. Deflating log\nblocks saves disk space, with some increased penalty at read time.\n\nLogs are stored in an isolated section from refs, reducing the burden\non reference readers that want to ignore logs. Further, historical\nlogs can be isolated into log-only reftables.\n\n### Logs are read backwards\n\nLogs are frequently accessed backwards (most recent N records for\nmaster to answer `master@{4}`), so log records are grouped by\nreference, and sorted descending by update index.\n\n## Repository format\n\n### Version 1\n\nA repository must set its `$GIT_DIR/config` to configure reftable:\n\n [core]\n repositoryformatversion = 1\n [extensions]\n reftable = 1\n\n### Layout\n\nThe `$GIT_DIR/refs` path is a file when reftable is configured, not a\ndirectory. This prevents loose references from being stored.\n\nA collection of reftable files are stored in the `$GIT_DIR/reftable/`\ndirectory:\n\n 00000001_UF4paF\n 00000002_bUVgy4\n\nwhere reftable files are named by a unique name such as produced by\nthe function:\n\n mktemp \"${update_index}_XXXXXX\"\n\nThe stack ordering file is `$GIT_DIR/refs` and lists the current\nfiles, one per line, in order, from oldest (base) to newest (most\nrecent):\n\n $ cat .git/refs\n 00000001_UF4paF\n 00000002_bUVgy4\n\nReaders must read `$GIT_DIR/refs` to determine which files are\nrelevant right now, and search through the stack in reverse order\n(last reftable is examined first).\n\nReftable files not listed in `refs` may be new (and about to be added\nto the stack by the active writer), or ancient and ready to be pruned.\n\n### Update transactions\n\nAlthough reftables are immutable, mutations are supported by writing a\nnew reftable and atomically appending it to the stack:\n\n1. Acquire `refs.lock`.\n2. Read `refs` to determine current reftables.\n3. Select `update_index` to be most recent file's `max_update_index + 1`.\n4. Prepare new reftable `${update_index}_XXXXXX`, including log entries.\n5. Copy `refs` to `refs.lock`, appending file from (4).\n6. Rename `refs.lock` to `refs`.\n\nDuring step 4 the new file's `min_update_index` and `max_update_index`\nare both set to the `update_index` selected by step 3. All log\nrecords for the transaction use the same `update_index` in their keys.\nThis enables later correlation of which references were updated by the\nsame transaction.\n\nBecause a single `refs.lock` file is used to manage locking, the\nrepository is single-threaded for writers. Writers may have to\nbusy-spin (with backoff) around creating `refs.lock`, for up to an\nacceptable wait period, aborting if the repository is too busy to\nmutate. Application servers wrapped around repositories (e.g. Gerrit\nCode Review) can layer their own lock/wait queue to improve fairness\nto writers.\n\n### Reference deletions\n\nDeletion of any reference can be explicitly stored by setting the\n`type` to `0x0` and omitting the `value` field of the `ref_record`.\nThis entry shadows the reference in earlier files in the stack.\n\n### Compaction\n\nA partial stack of reftables can be compacted by merging references\nusing a straightforward merge join across reftables, selecting the\nmost recent value for output, and omitting deleted references that do\nnot appear in remaining, lower reftables.\n\nA compacted reftable should set its `min_update_index` to the smallest of\nthe input files' `min_update_index`, and its `max_update_index`\nlikewise to the largest input `max_update_index`.\n\nFor sake of illustration, assume the stack currently consists of\nreftable files (from oldest to newest): A, B, C, and D. The compactor\nis going to compact B and C, leaving A and D alone.\n\n1. Obtain lock `refs.lock` and read the `refs` file.\n2. Obtain locks `B.lock` and `C.lock`.\n Ownership of these locks prevents other processes from trying\n to compact these files.\n3. Release `refs.lock`.\n4. Compact `B` and `C` into a new file `${min_update_index}_XXXXXX`.\n5. Reacquire lock `refs.lock`.\n6. Verify that `B` and `C` are still in the stack, in that order. This\n should always be the case, assuming that other processes are adhering\n to the locking protocol.\n7. Write the new stack to `refs.lock`, replacing `B` and `C` with the\n file from (4).\n8. Rename `refs.lock` to `refs`.\n9. Delete `B` and `C`, perhaps after a short sleep to avoid forcing\n readers to backtrack.\n\nThis strategy permits compactions to proceed independently of updates.\n\n## Alternatives considered\n\n### bzip packed-refs\n\n`bzip2` can significantly shrink a large packed-refs file (e.g. 62\nMiB compresses to 23 MiB, 37%). However the bzip format does not support\nrandom access to a single reference. Readers must inflate and discard\nwhile performing a linear scan.\n\nBreaking packed-refs into chunks (individually compressing each chunk)\nwould reduce the amount of data a reader must inflate, but still\nleaves the problem of indexing chunks to support readers efficiently\nlocating the correct chunk.\n\nGiven the compression achieved by reftable's encoding, it does not\nseem necessary to add the complexity of bzip/gzip/zlib.\n\n### JGit Ketch RefTree\n\n[JGit Ketch][ketch] proposed [RefTree][reftree], an encoding of\nreferences inside Git tree objects stored as part of the repository's\nobject database.\n\nThe RefTree format adds additional load on the object database storage\nlayer (more loose objects, more objects in packs), and relies heavily\non the packer's delta compression to save space. Namespaces which are\nflat (e.g. thousands of tags in refs/tags) initially create very\nlarge loose objects, and so RefTree does not address the problem of\ncopying many references to modify a handful.\n\nFlat namespaces are not efficiently searchable in RefTree, as tree\nobjects in canonical formatting cannot be binary searched. This fails\nthe need to handle a large number of references in a single namespace,\nsuch as GitHub's `refs/pulls`, or a project with many tags.\n\n[ketch]: https://dev.eclipse.org/mhonarc/lists/jgit-dev/msg03073.html\n[reftree]: https://public-inbox.org/git/CAJo=hJvnAPNAdDcAAwAvU9C4RVeQdoS3Ev9WTguHx4fD0V_nOg@mail.gmail.com/\n\n### LMDB\n\nDavid Turner proposed [using LMDB][dt-lmdb], as LMDB is lightweight\n(64k of runtime code) and GPL-compatible license.\n\nA downside of LMDB is its reliance on a single C implementation. This\nmakes embedding inside JGit (a popular reimplemenation of Git)\ndifficult, and hoisting onto virtual storage (for JGit DFS) virtually\nimpossible.\n\nA common format that can be supported by all major Git implementations\n(git-core, JGit, libgit2) is strongly preferred.\n\n[dt-lmdb]: https://public-inbox.org/git/1455772670-21142-26-git-send-email-dturner@twopensource.com/\n\n## Future\n\n### Longer hashes\n\nVersion will bump (e.g. 2) to indicate `value` uses a different\nobject id length other than 20. The length could be stored in an\nexpanded file header, or hardcoded as part of the version.\n"},{"id":"325304","messageId":"CAD0k6qTLSghs2Z6iv+kVQe091b+6=zqcR1k7_2eGks01rWUAsQ@mail.gmail.com","threadId":"46487","inReplyTo":"CAJo=hJv7scc1L0_MdRkFeLAJGjYm2UkTFNOgj2e4+9Zj7KSiiQ@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Dave Borowitz","fromEmail":"dborowitz@google.com","sentAt":"2017-07-31T17:41:42Z","receivedAt":"2017-07-31T17:45:04Z","isPatch":false,"sender":{"key":"dborowitz@google.com","avatar":"https://avatars.githubusercontent.com/u/194927?v=4"},"body":"On Sun, Jul 30, 2017 at 11:51 PM, Shawn Pearce wrote:\n> - Near constant time verification a SHA-1 is referred to by at least\n> one reference (for allow-tip-sha1-in-want).\n\nI think I understated the importance of this when I originally brought\nup allow-tip-sha1-in-want. This is an important optimization for *any*\nHTTP server, even without allow-tip-sha1-in-want, in order to validate\nthe SHA-1s sent in the upload-pack request, which doesn't share memory\nstate with the /info/refs request processing.\n"},{"id":"325309","messageId":"CAGZ79kZ3vbpzSEMHVHMtF0drY1P1rgz1eB7OB-J31-y6K+x5sw@mail.gmail.com","threadId":"46487","inReplyTo":"CAJo=hJv7scc1L0_MdRkFeLAJGjYm2UkTFNOgj2e4+9Zj7KSiiQ@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-07-31T19:01:13Z","receivedAt":"2017-07-31T19:01:20Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Sun, Jul 30, 2017 at 8:51 PM, Shawn Pearce wrote:\n> 4th iteration of the reftable storage format.\n>\n> You can read a rendered version of this here:\n> https://googlers.googlesource.com/sop/jgit/+/reftable/Documentation/technical/reftable.md\n>\n> Significant changes from v3:\n> - Incorporated Michael Haggerty's update_index concept for reflog.\n> - Explicitly documented log-only tables.\n\nI have read through v4 and I was missing the rationale\nto why this is a good idea, digging up the discussion for\nv3 seems to indicate that reflogs and refs themselves have\ndifferent usage patterns such that different compaction patterns\nare desired, hence we need to have different files for them.\n\n> ### Ref block format\n>\n> A ref block is written as:\n>\n> 'r'\n> uint24( block_len )\n> ref_record+\n> uint32( restart_offset )+\n\nAs the block_size is encoded in uint24, (and so is block_len),\nthe restart offsets could be made uint24 as well, though that may\nhave alignment issues, such that reading may be slower.\nBut as the ref_records may produce unaligned 32 bit ints\nalready, I am not worried about that.\n\n> uint16( restart_count )\n\nWhen looking for 16/32/64 bit hard coded ints I came across\nthis one once again. How much more expensive is reading\na varint? As the block_len points at the restart_count, we cannot\nreplace it with a varint easily, but we could use a byte-reversed\nvarint instead. If we do this step, all restart offsets could also be\n(reverse) varints?\n"},{"id":"325310","messageId":"xmqqlgn4ieaw.fsf@gitster.mtv.corp.google.com","threadId":"46487","inReplyTo":"CAJo=hJv7scc1L0_MdRkFeLAJGjYm2UkTFNOgj2e4+9Zj7KSiiQ@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-07-31T19:42:15Z","receivedAt":"2017-07-31T19:42:31Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> ### Peeling\n>\n> References in a reftable are always peeled.\n\nThis hopefully means \"a record for an annotated (or signed) tag\nrecords both the tag object and the object it refers to\", and does\nnot include peeling a commit down to its tree.\n\n> ### Reference name encoding\n>\n> Reference names should be encoded with UTF-8.\n\nIf we limited ourselves to say that a refname is an uninterpreted\nsequence of bytes that must pass check_refname_format() test, then\nwe won't open us to confusion such as \"are two refs with the same\nUnicode name encoded with different normalization form considered\nthe same?\"\n\nIn what way does this \"should be in UTF-8\" help describing the file\nformat, I wonder.\n\n> ### Directory/file conflicts\n>\n> The reftable format accepts both `refs/heads/foo` and\n> `refs/heads/foo/bar` as distinct references.\n>\n> This property is useful for retaining log records in reftable, but may\n> confuse versions of Git using `$GIT_DIR/refs` directory tree to\n> maintain references. Users of reftable may choose to continue to\n> reject `foo` and `foo/bar` type conflicts to prevent problems for\n> peers.\n\nThis is an interesting one. I do agree that preserving reflog for\nremoved refs is a nice propertly to have.\n\n> ### First ref block\n>\n> The first ref block shares the same block as the file header, and is\n> 24 bytes smaller than all other blocks in the file. The first block\n> immediately begins after the file header, at offset 24.\n>\n> If the first block is a log block (a log only table), its block header\n> begins immediately at offset 24.\n\nA minor nit: You called such a file \"a log-only file\"; let's be consistent.\n\n>\n> ### Ref block format\n>\n> A ref block is written as:\n>\n> 'r'\n> uint24( block_len )\n> ref_record+\n> uint32( restart_offset )+\n> uint16( restart_count )\n> padding?\n>\n> Blocks begin with `block_type = 'r'` and a 3-byte `block_len` which\n> encodes the number of bytes in the block up to, but not including the\n> optional `padding`. This is almost always shorter than the file's\n> `block_size`. In the first ref block, `block_len` includes 24 bytes\n> for the file header.\n\nAs a block cannot be longer than 16MB, allocating uint32 to a\nrestart offset may be a bit overkill. I do not know if it is worth\nattempting to pack 1/3 more restart entries in a block by using\nuint24, though.\n\n> The end of the block may be filled with `padding` NUL bytes to fill\n> out the block to the common `block_size` as specified in the file\n> header. Padding may be necessary to ensure the following block starts\n> at a block alignment, and does not spill into the tail of this block.\n> Padding may be omitted if the block is the last block of the file, and\n> there is no index block. This allows reftable to efficiently scale\n> down to a small number of refs.\n\nWe may want to phrase it in a way that it is more clear that\npadding, if exists, must be filled with NUL bytes, not arbitrary\ngarbage. Your version may be clear enough already. I dunno.\n\n> #### ref record\n>\n> A `ref_record` describes a single reference, storing both the name and\n> its value(s). Records are formatted as:\n>\n> varint( prefix_length )\n\nJust like we saw that \"uintX are network byte order\" upfront, it may\nbe easier to give the definition, or at least an outline, of varint()\nnear there.\n\n> varint( (suffix_length << 3) | value_type )\n> suffix\n> value?\n>\n> The `prefix_length` field specifies how many leading bytes of the\n> prior reference record's name should be copied to obtain this\n> reference's name. This must be 0 for the first reference in any\n> block, and also must be 0 for any `ref_record` whose offset is listed\n> in the `restart_offset` table at the end of the block.\n>\n> Recovering a reference name from any `ref_record` is a simple concat:\n>\n> this_name = prior_name[0..prefix_length] + suffix\n>\n> The `suffix_length` value provides the number of bytes to copy from\n> `suffix` to complete the reference name.\n>\n> The `value` follows. Its format is determined by `value_type`, one of\n> the following:\n>\n> - `0x0`: deletion; no value data (see transactions, below)\n> - `0x1`: one 20-byte object id; value of the ref\n> - `0x2`: two 20-byte object ids; value of the ref, peeled target\n> - `0x3`: symref and text: `varint( text_len ) text`\n> - `0x4`: index record (see below)\n> - `0x5`: log record (see below)\n>\n> Symbolic references use `0x3` with a `text` string starting with `\"ref: \"`,\n> followed by the complete name of the reference target. No\n> compression is applied to the target name. Other types of contents\n> that are also reference like, such as `FETCH_HEAD` and `MERGE_HEAD`,\n> may also be stored using type `0x3`.\n>\n> Types `0x6..0x7` are reserved for future use.\n\nI wondered if we regret the apparent limited extensibility later,\nbut giving 4 bits to value-type would limit suffix length that can\nbe represented by a single varint() only to 7, while the format\ndescribed would give us up to 15 bytes. We can say type 0x7 would\nbe followed by another varint() to record the extended type, or\nsomething, to extend it, so probably what you did here strikes a\ngood balance.\n\n> ### Ref index\n> ...\n> An index block should only be written if there are at least 4 blocks\n> in the file, as cold reads using the index requires 2 disk reads (read\n> index, read block), and binary searching <= 4 blocks also requires <=\n> 2 reads. Omitting the index block from smaller files saves space.\n\nI think the last \"<= 4\" should be \"< 4\" here. That is consistent\nwith an earlier part of the paragraph that requires at least 4\nref-blocks in the file, because a reftable with only 3 ref-blocks\nstill can be accessed with 2 reads (a reftable with 4 ref-blocks\nwithout index may need 3 reads as there is no \"middle\" for binary\nsearch).\n\nThe first sentence should be \"if there are at least 4 ref-blocks\", I\nguess.\n\n> ### Obj block format\n>\n> Object blocks use unique, abbreviated 2-20 byte SHA-1 keys, mapping\n> to ref blocks containing references pointing to that object directly,\n> or as the peeled value of an annotated tag. Like ref blocks, object\n> blocks use the file's standard `block_size`.\n>\n> To save space in small files, object blocks may be omitted if the ref\n> index is not present. When missing readers should brute force a\n> linear search of all references to lookup by SHA-1.\n\nI want a comma after \"When missing\".\n\nIt is a bit unclear why the presense of ref-index is linked to the\npresense and/or need of this block. I first thought that the reason\nis because the data in this table is to index into ref-index table,\nin which case of course it would not make sense to have this table\nif ref-index table is not present, but that is not the case. Am I\ncorrect to read the above advice/suggestion to mean \"if the reftable\nhas so few blocks not to require ref-index blocks, we hypothesize\nthat it is not worth having obj-block table either\"?\n\n> #### obj record\n>\n> An `obj_record` describes a single object abbreviation, and the blocks\n> containing references using that unique abbreviation:\n>\n> varint( prefix_length )\n> varint( (suffix_length << 3) | cnt_3 )\n> suffix\n> varint( cnt_large )?\n> varint( block_delta )+\n>\n> Like in reference blocks, abbreviations are prefix compressed within\n> an obj block. On large reftables with many unique objects, higher\n> block sizes (64k), and higher restart interval (128), a\n> `prefix_length` of 2 or 3 and `suffix_length` of 3 may be common in\n> obj records (unique abbreviation of 5-6 raw bytes, 10-12 hex digits).\n\nOK.\n\n> Each record contains `block_count` number of block identifiers for ref\n> blocks. For 1-7 blocks the block count is stored in `cnt_3`. When\n> `cnt_3 = 0` the actual block count follows in a varint, `cnt_large`.\n\nI feel a bit lost here. Is this about a single object pointed by\nmultiple refs, and that we expect to have not too many refs pointing\nat a single object?\n\n> The first `block_delta` is the absolute block identifier counting from\n> the start of the file. The offset of that block can be obtained by\n> `block_delta[0] * block_size`. Additional `block_delta` entries are\n> relative to the prior entry, e.g. a reader would perform:\n>\n> block_id = block_delta[0]\n> prior = block_id\n> for (j = 1; j < block_count; j++) {\n> block_id = prior + block_delta[j]\n> prior = block_id\n> }\n>\n> With a `block_id` in hand, a reader must linearly scan the ref block\n> at `block_id * block_size` offset in the file, starting from the first\n> `ref_record`, testing each reference's SHA-1s (for `value_type = 0x1`\n> or `0x2`) for full equality. Faster searching by SHA-1 within a\n> single ref block is not supported by the reftable format. Smaller\n> block sizes reduces the number of candidates this step must consider.\n\nAssuming varint() yields an unsigned quantity, the writer needs to\nsort the refs that point at the same object by their block numbers\nfirst and record from the smallest one to the larger ones? Not a\ncomplaint, but just seeking help to make sure I understood it.\n\n> ### Log block format\n>\n> Unlike ref and obj blocks, log block sizes are variable in size, and\n> do not match the `block_size` specified in the file header or footer.\n> Writers should choose an appropriate buffer size to prepare a log block\n> for deflation, such as `2 * block_size`.\n>\n> A log block is written as:\n>\n> 'g'\n> uint24( block_len )\n> zlib_deflate {\n> log_record+\n> int32( restart_offset )+\n> int16( restart_count )\n> }\n>\n> Log blocks look similar to ref blocks, except `block_type = 'g'`.\n>\n> The 4-byte block header is followed by the deflated block contents\n> using zlib deflate. The `block_len` in the header is the inflated\n> size (including 4-byte block header), and should be used by readers to\n> preallocate the inflation output buffer. Offsets within the block\n> (e.g. `restart_offset`) still include the 4-byte header. Readers may\n> prefer prefixing the inflation output buffer with the 4-byte header.\n\nIs block_len allowed to exceed the file-global block_size?\n\n> #### log record\n>\n> Log record keys are structured as:\n>\n> ref_name '\\0' reverse_int64( update_index )\n>\n> where `update_index` is the unique transaction identifier. The\n> `update_index` field must be unique within the scope of a `ref_name`.\n> See the update index section below for further details.\n>\n> The `reverse_int64` function inverses the value so lexographical\n> ordering the network byte order encoding sorts the more recent records\n> with higher `update_index` values first:\n>\n> reverse_int64(int64 t) {\n> return 0xffffffffffffffff - t;\n> }\n\nOK, so this no longer is linked to timestamp, which makes things\nsimpler.\n\nAll log records in a single reftable is sorted with the log record\nkey, so the reflog entries for a specific ref are adjacent to each\nother and are ordered in reverse \"chronological\" order, assuming\nthat the update_index transaction numbers monotonically increase?\n\n> The value data following the key suffix is complex:\n>\n> - two 20-byte SHA-1s (old id, new id)\n> - varint time in seconds since epoch (Jan 1, 1970)\n> - 2-byte timezone offset (signed)\n\n\"offset in minutes\"\n\n> - varint string of committer's name\n> - varint string of committer's email\n\nWe might want to clarify that this is without surrounding <>.\n\n> #### Reading the log\n>\n> Readers accessing the log must first read the footer (below) to\n> determine the `log_offset`. The first block of the log begins at\n> `log_offset` bytes since the start of the file. The `log_offset` is\n> not block aligned.\n>\n> #### Importing logs\n>\n> When importing from `$GIT_DIR/logs` writers should globally order all\n> log records roughly by timestamp while preserving file order, and\n> assign unique, increasing `update_index` values for each log line.\n\nI am not quite sure why you need global order (I am assuming that\nyou mean \"consistency across multiple logs, e.g. $GIT_DIR/logs/HEAD\nand $GIT_DIR/logs/refs/heads/master\"), as the resulting log table\nsorts the entries essentially with refname as the first key and then\nrecentness of the entry as the second key. Wouldn't the resulting\nlog table in a reftable be sorted in the same way as\n\n cd $GIT_DIR/logs &&\n find -type f -print |\n sort |\n xargs -n 1 tac\n\nanyway?\n\n... Ah, you want to give the same (or at least close-enough)\ntransaction ID to two reflog entries that result from a commit while\n'master' branch is checked out, one for 'refs/heads/master' and the\nother for HEAD. Then the suggestion makes sense. I wonder if the\nexisting log records that are migrated are known to have timestamps\nthat fit in int64_t, using the timestamp from the original is\nsufficient?\n\n... The answer is no; if the original records clock rewind, you'd\nstill want to assign the update_index number that is in line with\nthe order of the entries, not with the skewed clock value.\n\nOK.\n\n> ## Repository format\n>\n> ### Version 1\n>\n> A repository must set its `$GIT_DIR/config` to configure reftable:\n>\n> [core]\n> repositoryformatversion = 1\n> [extensions]\n> reftable = 1\n\nThe expectation is that this number matches the version number\nrecorded in the reftable itself?\n\nThat's it for now. I'll comment on the part after Update\ntransactions in a separate message.\n\nThanks.\n"},{"id":"325353","messageId":"CAJo=hJu-j+7CfKy8vCS9t+6=-PVGNC5D6HuYgqpO7GrNi=MDig@mail.gmail.com","threadId":"46487","inReplyTo":"CAGZ79kZ3vbpzSEMHVHMtF0drY1P1rgz1eB7OB-J31-y6K+x5sw@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-07-31T23:05:09Z","receivedAt":"2017-07-31T23:05:36Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Mon, Jul 31, 2017 at 12:01 PM, Stefan Beller wrote:\n> On Sun, Jul 30, 2017 at 8:51 PM, Shawn Pearce wrote:\n>> 4th iteration of the reftable storage format.\n>>\n>> You can read a rendered version of this here:\n>> https://googlers.googlesource.com/sop/jgit/+/reftable/Documentation/technical/reftable.md\n>>\n>\n>> uint16( restart_count )\n>\n> When looking for 16/32/64 bit hard coded ints I came across\n> this one once again. How much more expensive is reading\n> a varint? As the block_len points at the restart_count, we cannot\n> replace it with a varint easily, but we could use a byte-reversed\n> varint instead. If we do this step, all restart offsets could also be\n> (reverse) varints?\n\nIts not the expense of decoding a varint, its making the file\nstructure predictable so its simple to binary search within restart\npoints. If these were varints, it becomes much more difficult to\ndivide the remaining range in half and update the boundary conditions\nto locate the next mid-point.\n"},{"id":"325359","messageId":"CAJo=hJurMO=eQP3xctwTX9cO3yTZogJsw5HMztWjB8JHHtJ=fQ@mail.gmail.com","threadId":"46487","inReplyTo":"xmqqlgn4ieaw.fsf@gitster.mtv.corp.google.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-07-31T23:43:07Z","receivedAt":"2017-07-31T23:43:33Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Mon, Jul 31, 2017 at 12:42 PM, Junio C Hamano wrote:\n> Shawn Pearce writes:\n>\n>> ### Peeling\n>>\n>> References in a reftable are always peeled.\n>\n> This hopefully means \"a record for an annotated (or signed) tag\n> records both the tag object and the object it refers to\", and does\n> not include peeling a commit down to its tree.\n\nYes, thanks for the clarification. I've added that to this section.\n\n\n>> ### Reference name encoding\n>>\n>> Reference names should be encoded with UTF-8.\n>\n> If we limited ourselves to say that a refname is an uninterpreted\n> sequence of bytes that must pass check_refname_format() test, mthen\n> we won't open us to confusion such as \"are two refs with the same\n> Unicode name encoded with different normalization form considered\n> the same?\"\n\nAck. I'll reword this as bytes, and point to git-check-ref-format.\n\n> In what way does this \"should be in UTF-8\" help describing the file\n> format, I wonder.\n\nIn JGit we have a String object for a reference name. Dropping that\ndown to a sequence of bytes requires converting it with a character\nencoding, such as US-ASCII or UTF-8.\n\n\n>> ### First ref block\n>>\n>> The first ref block shares the same block as the file header, and is\n>> 24 bytes smaller than all other blocks in the file. The first block\n>> immediately begins after the file header, at offset 24.\n>>\n>> If the first block is a log block (a log only table), its block header\n>> begins immediately at offset 24.\n>\n> A minor nit: You called such a file \"a log-only file\"; let's be consistent.\n\nFixed. I found another that also was inconsistent. Thanks for the\nattention to detail.\n\n\n>> ### Ref block format\n>>\n>> A ref block is written as:\n>>\n>> 'r'\n>> uint24( block_len )\n>> ref_record+\n>> uint32( restart_offset )+\n>> uint16( restart_count )\n>> padding?\n>>\n>> Blocks begin with `block_type = 'r'` and a 3-byte `block_len` which\n>> encodes the number of bytes in the block up to, but not including the\n>> optional `padding`. This is almost always shorter than the file's\n>> `block_size`. In the first ref block, `block_len` includes 24 bytes\n>> for the file header.\n>\n> As a block cannot be longer than 16MB, allocating uint32 to a\n> restart offset may be a bit overkill. I do not know if it is worth\n> attempting to pack 1/3 more restart entries in a block by using\n> uint24, though.\n\nI don't think its worth the annoyance in code that has to deal with\nthis field. An example 87k ref repository with a 4k block size has ~9\nrestarts per block and ~19 bytes of padding. Using uint24 saves us 9\nbytes, yet the average ref here costs 27 bytes. We aren't likely to\nfill the block with another ref, or another restart point.\n\n\n>> #### ref record\n[...]\n>> The `value` follows. Its format is determined by `value_type`, one of\n>> the following:\n>>\n>> - `0x0`: deletion; no value data (see transactions, below)\n>> - `0x1`: one 20-byte object id; value of the ref\n>> - `0x2`: two 20-byte object ids; value of the ref, peeled target\n>> - `0x3`: symref and text: `varint( text_len ) text`\n>> - `0x4`: index record (see below)\n>> - `0x5`: log record (see below)\n[...]\n>> Types `0x6..0x7` are reserved for future use.\n>\n> I wondered if we regret the apparent limited extensibility later,\n> but giving 4 bits to value-type would limit suffix length that can\n> be represented by a single varint() only to 7, while the format\n> described would give us up to 15 bytes. We can say type 0x7 would\n> be followed by another varint() to record the extended type, or\n> something, to extend it, so probably what you did here strikes a\n> good balance.\n\nThanks. I think we actually have 0x4-0x7 available in value_type. I\nused 0x4 and 0x5 as above only as a suggestion from Stefan to help\nsomeone debug a reader. The block type differs where 0x0-0x3 and 0x4\nand 0x5 are used, so there is already sufficient information available\nto disambiguate the value_type such that we don't actually have to use\n0x4 and 0x5 as I have here.\n\nSo I agree with myself, and with you, 3 bits for value_type and 4 bits\nfor suffix_len is the right balance.\n\n\n>> ### Ref index\n>> ...\n>> An index block should only be written if there are at least 4 blocks\n>> in the file, as cold reads using the index requires 2 disk reads (read\n>> index, read block), and binary searching <= 4 blocks also requires <=\n>> 2 reads. Omitting the index block from smaller files saves space.\n>\n> I think the last \"<= 4\" should be \"< 4\" here. That is consistent\n> with an earlier part of the paragraph that requires at least 4\n> ref-blocks in the file, because a reftable with only 3 ref-blocks\n> still can be accessed with 2 reads (a reftable with 4 ref-blocks\n> without index may need 3 reads as there is no \"middle\" for binary\n> search).\n>\n> The first sentence should be \"if there are at least 4 ref-blocks\", I\n> guess.\n\nThanks, clarified.\n\n\n>> ### Obj block format\n>>\n>> Object blocks use unique, abbreviated 2-20 byte SHA-1 keys, mapping\n>> to ref blocks containing references pointing to that object directly,\n>> or as the peeled value of an annotated tag. Like ref blocks, object\n>> blocks use the file's standard `block_size`.\n>>\n>> To save space in small files, object blocks may be omitted if the ref\n>> index is not present. When missing readers should brute force a\n>> linear search of all references to lookup by SHA-1.\n>\n> I want a comma after \"When missing\".\n\nAdded comma.\n\n> It is a bit unclear why the presense of ref-index is linked to the\n> presense and/or need of this block. I first thought that the reason\n> is because the data in this table is to index into ref-index table,\n> in which case of course it would not make sense to have this table\n> if ref-index table is not present, but that is not the case. Am I\n> correct to read the above advice/suggestion to mean \"if the reftable\n> has so few blocks not to require ref-index blocks, we hypothesize\n> that it is not worth having obj-block table either\"?\n\nYes.\n\n\n>> #### obj record\n>>\n>> An `obj_record` describes a single object abbreviation, and the blocks\n>> containing references using that unique abbreviation:\n>>\n>> varint( prefix_length )\n>> varint( (suffix_length << 3) | cnt_3 )\n>> suffix\n>> varint( cnt_large )?\n>> varint( block_delta )+\n>>\n>> Like in reference blocks, abbreviations are prefix compressed within\n>> an obj block. On large reftables with many unique objects, higher\n>> block sizes (64k), and higher restart interval (128), a\n>> `prefix_length` of 2 or 3 and `suffix_length` of 3 may be common in\n>> obj records (unique abbreviation of 5-6 raw bytes, 10-12 hex digits).\n>\n> OK.\n>\n>> Each record contains `block_count` number of block identifiers for ref\n>> blocks. For 1-7 blocks the block count is stored in `cnt_3`. When\n>> `cnt_3 = 0` the actual block count follows in a varint, `cnt_large`.\n>\n> I feel a bit lost here. Is this about a single object pointed by\n> multiple refs, and that we expect to have not too many refs pointing\n> at a single object?\n\nYes, correct. I've added a paragraph to clarify:\n\n The use of `cnt_3` bets most objects are pointed to by only a single\n reference, some may be pointed to be a couple of references, and very\n few (if any) are pointed to by more than 7 references.\n\n\n>> The first `block_delta` is the absolute block identifier counting from\n>> the start of the file. The offset of that block can be obtained by\n>> `block_delta[0] * block_size`. Additional `block_delta` entries are\n>> relative to the prior entry, e.g. a reader would perform:\n>>\n>> block_id = block_delta[0]\n>> prior = block_id\n>> for (j = 1; j < block_count; j++) {\n>> block_id = prior + block_delta[j]\n>> prior = block_id\n>> }\n>>\n>> With a `block_id` in hand, a reader must linearly scan the ref block\n>> at `block_id * block_size` offset in the file, starting from the first\n>> `ref_record`, testing each reference's SHA-1s (for `value_type = 0x1`\n>> or `0x2`) for full equality. Faster searching by SHA-1 within a\n>> single ref block is not supported by the reftable format. Smaller\n>> block sizes reduces the number of candidates this step must consider.\n>\n> Assuming varint() yields an unsigned quantity, the writer needs to\n> sort the refs that point at the same object by their block numbers\n> first and record from the smallest one to the larger ones? Not a\n> complaint, but just seeking help to make sure I understood it.\n\nYes. I added a \"sorted ascending\" to the paragraph to clarify.\n\n Additional `block_delta` entries are sorted ascending and relative\n to the prior entry, e.g. a reader would perform:\n\n\n>> ### Log block format\n>>\n>> Unlike ref and obj blocks, log block sizes are variable in size, and\n>> do not match the `block_size` specified in the file header or footer.\n>> Writers should choose an appropriate buffer size to prepare a log block\n>> for deflation, such as `2 * block_size`.\n>>\n>> A log block is written as:\n>>\n>> 'g'\n>> uint24( block_len )\n>> zlib_deflate {\n>> log_record+\n>> int32( restart_offset )+\n>> int16( restart_count )\n>> }\n>>\n>> Log blocks look similar to ref blocks, except `block_type = 'g'`.\n>>\n>> The 4-byte block header is followed by the deflated block contents\n>> using zlib deflate. The `block_len` in the header is the inflated\n>> size (including 4-byte block header), and should be used by readers to\n>> preallocate the inflation output buffer. Offsets within the block\n>> (e.g. `restart_offset`) still include the 4-byte header. Readers may\n>> prefer prefixing the inflation output buffer with the 4-byte header.\n>\n> Is block_len allowed to exceed the file-global block_size?\n\nYes, clarified that with an additional sentence.\n\n\n>> #### log record\n>>\n>> Log record keys are structured as:\n>>\n>> ref_name '\\0' reverse_int64( update_index )\n>>\n>> where `update_index` is the unique transaction identifier. The\n>> `update_index` field must be unique within the scope of a `ref_name`.\n>> See the update index section below for further details.\n>>\n>> The `reverse_int64` function inverses the value so lexographical\n>> ordering the network byte order encoding sorts the more recent records\n>> with higher `update_index` values first:\n>>\n>> reverse_int64(int64 t) {\n>> return 0xffffffffffffffff - t;\n>> }\n>\n> OK, so this no longer is linked to timestamp, which makes things\n> simpler.\n>\n> All log records in a single reftable is sorted with the log record\n> key, so the reflog entries for a specific ref are adjacent to each\n> other and are ordered in reverse \"chronological\" order, assuming\n> that the update_index transaction numbers monotonically increase?\n\nCorrect.\n\n>> The value data following the key suffix is complex:\n>>\n>> - two 20-byte SHA-1s (old id, new id)\n>> - varint time in seconds since epoch (Jan 1, 1970)\n>> - 2-byte timezone offset (signed)\n>\n> \"offset in minutes\"\n\nFixed.\n\n>> - varint string of committer's name\n>> - varint string of committer's email\n>\n> We might want to clarify that this is without surrounding <>.\n\nGood idea, added.\n\n\n>> #### Importing logs\n>>\n>> When importing from `$GIT_DIR/logs` writers should globally order all\n>> log records roughly by timestamp while preserving file order, and\n>> assign unique, increasing `update_index` values for each log line.\n>\n> I am not quite sure why you need global order (I am assuming that\n> you mean \"consistency across multiple logs, e.g. $GIT_DIR/logs/HEAD\n> and $GIT_DIR/logs/refs/heads/master\"), as the resulting log table\n> sorts the entries essentially with refname as the first key and then\n> recentness of the entry as the second key. Wouldn't the resulting\n> log table in a reftable be sorted in the same way as\n>\n> cd $GIT_DIR/logs &&\n> find -type f -print |\n> sort |\n> xargs -n 1 tac\n>\n> anyway?\n>\n> ... Ah, you want to give the same (or at least close-enough)\n> transaction ID to two reflog entries that result from a commit while\n> 'master' branch is checked out, one for 'refs/heads/master' and the\n> other for HEAD. Then the suggestion makes sense. I wonder if the\n> existing log records that are migrated are known to have timestamps\n> that fit in int64_t, using the timestamp from the original is\n> sufficient?\n>\n> ... The answer is no; if the original records clock rewind, you'd\n> still want to assign the update_index number that is in line with\n> the order of the entries, not with the skewed clock value.\n>\n> OK.\n\nCorrect. :)\n\n\n>> ## Repository format\n>>\n>> ### Version 1\n>>\n>> A repository must set its `$GIT_DIR/config` to configure reftable:\n>>\n>> [core]\n>> repositoryformatversion = 1\n>> [extensions]\n>> reftable = 1\n>\n> The expectation is that this number matches the version number\n> recorded in the reftable itself?\n\nHonestly, I'm not sure why its \"1\" and not \"true\". I was asking myself\nthat yesterday before I posted this iteration to the list. I think we\ncan use \"true\" here.\n"},{"id":"325365","messageId":"CAMy9T_HCnyc1g8XWOOWhe7nN0aEFyyBskV2aOMb_fe+wGvEJ7A@mail.gmail.com","threadId":"46487","inReplyTo":"CAJo=hJv7scc1L0_MdRkFeLAJGjYm2UkTFNOgj2e4+9Zj7KSiiQ@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-08-01T06:41:54Z","receivedAt":"2017-08-01T06:45:34Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On Sun, Jul 30, 2017 at 8:51 PM, Shawn Pearce wrote:\n> 4th iteration of the reftable storage format.\n> [...]\n\nBefore we commit to Shawn's reftable proposal, I wanted to explore\nwhat a contrasting design that is not block based would look like. So\nI threw together a sketch of such a design. It is not as refined as\nShawn's, and I haven't had time to program an implementation or\ncollect statistics, but maybe it is interesting anyway.\n\nThe design benefits from a lot of Shawn's ideas, plus a lot of the\ndiscussion from the mailing list. First let me explain in words the\nmajor differences and why I think they might be promising.\n\nIt seems to me that the block-orientation of Shawn's spec adds a lot\nof complication to the design (e.g., padding, optional blocks, varying\nblock sizes for different parts of the file). It also seems that the\nformat has been heavily optimized to be read in 64k blocks, whereas\nmost users will be storing their references to local hard disks or\n(increasingly) to local SSDs. So I tried to come up with a design that\nis friendlier to the latter, hopefully without being much worse for\nthe former.\n\nOne thing that I realized is that, assuming that reference values and\nreflogs are usually compacted separately, there will basically be\nthree types of reftable files:\n\n1. Accumulated references and their values (potentially very large)\n\n2. Accumulated reflogs (potentially gigantic)\n\n3. Recent transaction(s), which include both refs and reflogs (usually\n quite small).\n\nThe first two types of file don't benefit from separating reference\ndata from reflog data in the file (because they only include one or\nthe other). The third kind of file doesn't care because such files\nwill be small.\n\nSo let's store all of the data related to a single reference in one\nspot. This simplifies the file format and removes the need for two\nseparate indexes and/or variants that special-case the omission of an\nindex. A disadvantage is that, it prevents compression of reflog\nentries across references. I think that is a reasonable tradeoff,\nbecause most reflog entries (in the repositories I checked; that might\ndiffer in Gerrit-managed repos) correspond to references that have\nbeen updated many times. To partly compensate for the resulting\nreduction in compression, I added some features to reduce the storage\nof redundant information in reflog entries.\n\nI also wanted to support multiple-level indexes, so that one isn't\nforced to choose rather large blocksizes for repositories with lots of\nreferences.\n\nOn the other hand, this design does not support binary searching for\nrefnames. Instead, the refnames are distributed into a multiple-level\ntree. When looking for a reference, each tree node on the way to the\nreference needs to be parsed serially. But the nodes are small enough\n(due to the multilevel indexing scheme) that I hope that isn't a\nproblem. I'd rather read less data at the expense of parsing a little\nbit more.\n\n\nThe primary data structure consists of `INDEX` and `REFS` chunks.\nBasically the `INDEX` chunks are interior nodes of the tree, and the\n`REFS` chunks are the leaf nodes. But both types of nodes are N-way.\n\n* Prefix compression occurs within a single node chunk, but not across\n nodes. In that way, the node chunks are analogous to a restart plus\n the subsequent prefix-compressed references in Shawn's design (but\n they will typically be bigger).\n\n* A chunk must be read and processed serially to make sense of it.\n Chunks are also the unit of addressing.\n\n* Indexes can be multi-level to keep each level of the tree small.\n This reduces the total amount of data that needs to be read to\n access a reference, but might require an additional seek if the\n required index chunks are not close together.\n\n* Node chunks can be read serially starting at any chunk without\n referring to any index. Also, data are always written in order by\n reference name, both within single chunks and regarding the ordering\n of multiple `REFS` chunks. So references can be iterated over\n without regard to the indexes.\n\n* I feel like the size of a chunk should be roughly 1-4 kiB, and will\n usually fit in one disk block (though it might cross disk blocks,\n requiring two to be read).\n\n* Multiple related chunks can be stored in a 64 kiB block (interesting\n for people who prefer to read files in 64k segments). By storing\n related chunks near each other, the number of seeks will probably\n typically be smaller than the number of chunks that have to be\n accessed.\n\n* Padding can be added between any two chunks (e.g., to avoid\n splitting chunks across 64 kiB blocks), but it is entirely optional\n and probably would not be used for data stored on local storage.\n\n* In many cases, cross-references between chunks are relative, so that\n they can be stored compactly using varint encoding. This is more\n important than in Shawn's proposal because we don't have block\n indexes, so we have to store arbitrary disk offsets.\n\n* The file can be written in two possible ways: with cross-references\n between chunks always pointing to later parts of the file (probably\n preferable if the data will be read from a local hard disk) or\n always pointing to earlier parts of the file (to accomodate writers\n who need to write their data in order). See the `offsets_negative`\n field in the header. (I'm not sure that the former variant is\n actually needed.)\n\nBecause we don't have blocks, it is more difficult to store the object\nreferences compactly. I've arranged them in a radix-256 tree with\nrelative references. The lowest internal nodes are stored sparsely,\nand contain absolute references that point at the containing chunk.\n\n\nDefinitions:\n\nVarint encoding is similar to the unsigned varint encoding used for\nprotocol buffers; i.e., a little-endian base-128 format where the most\nsignificant bit is used to indicate that another byte is coming.\nDecoding is as follows:\n\n```\nval = *ptr & 0x7f\nwhile (*ptr++ & 0x80) {\n val = (val << 7) | (*ptr & 0x7f)\n}\n```\n\nStrings are usually encoded using `varstr` encoding, which is the same\nas how strings are encoded in protocol buffers. A `varstr` consists of\na `varint` length followed by the specified number of bytes holding\nthe contents of the string. `varstr` strings are not intrinsically\nNUL-terminated.\n\nThe `chunk_length` fields encode the total size of the containing\nchunk, including its `chunk_type` field.\n\n```\nvarstr(s) = {\n varint(strlen(s))\n s\n}\n```\n\n```\nreftable = {\n header\n\n # The choice to order ref_chunks before obj_chunks is not crucial\n # to the design, but probably makes sense.\n [ref_chunk | padding]*\n [obj_chunk | padding]*\n\n footer\n}\n\nheader = {\n 'REFT'\n uint8( version_number = 1 )\n\n # if `contains_values` is false, this file *must not* contain any\n # reference values; i.e., `value_type` must always be `NO_VALUE`.\n contains_values : bool\n\n # if `contains_logs` is false, this file *must not* contain any\n # reflog entries; i.e., `log_type` must always be `NO_REFLOG`.\n\n contains_logs : bool\n\n # If `offsets_negative` is true, then all `*_offset` fields point\n # backwards in the file; i.e., the corresponding varint value is\n # negated before use.\n offsets_negative : bool\n\n min_update_index : uint64\n max_update_index : uint64\n\n # To accomodate systems that have to write files serially, the\n # following two entries can be zeroed out in the header to tell\n # the reader that it has to read the corresponding values from the\n # footer.\n\n # The file offset of the chunk containing the root of the\n # reference tree:\n ref_root_chunk_addr : uint64\n\n # The file offset of the chunk containing the root of the object\n # tree. This value must be zero if `contains_values` is false:\n obj_root_chunk_addr : uint64\n}\n\nfooter = {\n header\n uint32(CRC-32 of previous part of footer)\n}\n\nchunk = {\n # The `chunk_type` determines how to interpret the payload, and\n # influences how to compute its length (which is needed to advance\n # to the next chunk).\n\n chunk_type : enum PAD_BYTE | PADDING\n | INDEX | REFS\n | OBJS_INDEX | OBJS\n\n if chunk_type == PAD_BYTE {\n # This chunk type can be used to add a single byte of padding,\n # which would otherwise be impossible because a `PADDING`\n # chunk requires a minimum of two bytes.\n }\n elif chunk_type == PADDING {\n # A form of padding that's cheaper to skip over than\n # `PAD_BYTE`.\n\n # The total number of bytes in this chunk, including\n # `chunk_type`. The contents will otherwise be ignored:\n\n chunk_length : varint\n }\n elif chunk_type == INDEX {\n chunk_length : varint\n first_child : {\n refname : varstr\n index_payload\n }\n other_children : {\n # Length of prefix being carried over from the previous\n # record:\n prefix_len : varint\n suffix : varstr\n index_payload\n }*\n }\n elif chunk_type == REFS {\n chunk_length : varint\n first_ref : {\n refname : varstr\n ref_payload\n }*\n other_refs : {\n # Length of prefix being carried over from the previous\n # record:\n prefix_len : varint\n suffix : varstr\n ref_payload\n }*\n }\n elif chunk_type == OBJS_INDEX {\n chunk_length : varint\n\n # The offset, relative to the start of this chunk, of the\n # chunk containing the next level of the obj index, for each\n # of the possible \"next\" bytes in the SHA-1, or zero if there\n # are no references with the given next byte.\n child_offset : varint * 256\n }\n elif chunk_type == OBJS {\n chunk_length : varint\n obj_record*\n }\n}\n```\n\n```\nindex_payload = {\n # The number of bytes from the begining of this chunk to the child\n # chunk. If child_offset is zero, then there are no entries in\n # this reftable whose refnames start with the specified prefix.\n #\n # The child pointed at is of type INDEX (another index chunk\n # containing the next finer level of detail) or of type REFS. In\n # either case, the first record in the pointed-to chunk must have\n # `prefix_len == 0` and contain the entire key as `suffix`.\n child_offset : varint\n}\n\nref_payload = {\n value_type : enum NO_VALUE\n | DELETED\n | VALUE | VALUE_PEELED\n | SYMREF | SYMREF_PEELED\n | SPECIAL\n log_type : enum NO_REFLOG | REFLOG | REFLOG_COMPRESSED\n symref_target : bool\n\n if value_type == NO_VALUE {\n # This type is used if we need to store a reflog entry but\n # have no reference value to store in this file.\n }\n elif value_type == DELETED {\n # This type indicates that the reference has been deleted,\n # regardless of what any reftables deeper in the stack claim.\n }\n elif value_type == VALUE {\n # This is a normal (non-symbolic) reference.\n sha1 : uchar[20]\n }\n elif value_type == VALUE_PEELED {\n # This is a normal (non-symbolic) reference that points at a\n # tag. `peeled` is the reference peeled down to a non-tag.\n sha1 : uchar[20]\n peeled : uchar[20]\n }\n elif value_type == SYMREF {\n # This is a symref that points at a non-existent branch.\n target : varstr\n }\n elif value_type == SYMREF_PEELED {\n # This is a symref that points at a branch that has the\n # specified value.\n target : varstr\n peeled : uchar[20]\n }\n elif value_type == SPECIAL {\n # This is one of the special references (like FETCH_HEAD,\n # MERGE_HEAD). The contents are stored as they would be in a\n # loose reference file:\n contents : varstr\n }\n\n # This field is used to keep backwards links from references to\n # any symrefs that point at them, to make it tractable to update\n # the reflog of the symref if the reference is changed directly:\n if symref_target {\n referer : varstr\n varint(0)\n }\n\n if log_type == NO_REFLOG {\n }\n elif log_type == REFLOG {\n log_entry_length : varint\n log_entry\n elif log_type == REFLOGS_COMPRESSED {\n zlib_length : varint\n zlib_deflate(\n log_entry*\n )\n }\n}\n\n# Log entries are stored from oldest to newest. The \"chained\" variants\n# of `log_type` take their `new_id` from the current value of the\n# reference (if it is the first log entry for the references) or from\n# the preceding (i.e., next newest) log record's `old_id` value.\nlog_entry = {\n # `CREATE_CHAINED` and `UPDATE_CHAINED` take their `new_id` from\n # the preceding (i.e., next newest) record's `old_id` value.\n log_type : enum END_OF_LOG | LOG\n old_type : enum ABSENT | REF | SYMREF\n new_type : enum ABSENT | REF | SYMREF | CHAINED\n\n if log_type != END_OF_LOG {\n # The update_index of this entry, or 0 if there are no more entries:\n update_index : varint\n\n # `PUSHER_CHAINED` takes its `name` and `email` from the preceding\n # (i.e., next newest) record's fields.\n pusher_type : enum PUSHER_EXPLICIT | PUSHER_CHAINED\n\n if new_type == ABSENT {\n }\n elif new_type == REF {\n new_id : uchar[20]\n }\n elif new_type == SYMREF {\n new_ref : varstr\n }\n elif new_type == CHAINED {\n }\n\n if old_type == ABSENT {\n }\n elif old_type == REF {\n old_id : uchar[20]\n }\n elif old_type == SYMREF {\n old_ref : varstr\n }\n\n time_seconds : uint32\n tz_offset_minutes : sint16\n if pusher_type == PUSHER_EXPLICIT {\n name : varstr\n email : varstr\n }\n\n # The reflog message. For a bit more compression:\n#\n# * Many messages contain old/new SHA-1s for the reference\n# updates. That redundancy could be eliminated by replacing\n# the old SHA-1 with `%o`, the new one with `%n`, and `%`\n# with `%%`.\n #\n # * Some \"standard\" log messages (i.e., the ones generated by\n# Git itself) could be hard-coded as additional `log_type`\n# constants.\n message : varstr\n }\n}\n\nobj_record = {\n # The \"next\" two bytes of the SHA-1 being described:\n bytes : uchar[2]\n\n # The number of of child_addrs:\n count : varint\n\n # File offsets of the chunks containing references that point at\n # objects with this prefix:\n child_addr+ : varint\n}\n```\n\nMichael\n"},{"id":"325372","messageId":"CAD0k6qTFV2AAbWiKvi4=OoodoXEgxswLEbraC3xP1LzvtRRaGg@mail.gmail.com","threadId":"46487","inReplyTo":"CAJo=hJv7scc1L0_MdRkFeLAJGjYm2UkTFNOgj2e4+9Zj7KSiiQ@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Dave Borowitz","fromEmail":"dborowitz@google.com","sentAt":"2017-08-01T13:54:55Z","receivedAt":"2017-08-01T13:55:23Z","isPatch":false,"sender":{"key":"dborowitz@google.com","avatar":"https://avatars.githubusercontent.com/u/194927?v=4"},"body":"On Sun, Jul 30, 2017 at 11:51 PM, Shawn Pearce wrote:\n> - Ref-like files (FETCH_HEAD, MERGE_HEAD) also use type 0x3.\n\n> - Combine reflog storage with ref storage for small transactions.\n> - Separate reflog storage for base refs and historical logs.\n\nHow is the stash implemented in reftable? In particular, \"git stash\ndrop\" needs to be able to remove an arbitrary single entry from a\nreflog.\n\nI don't think the current proposal supports writing tombstones for\nreflog entries, so this maybe implies that \"stash drop\" would have to\nbe implemented by rewriting the whole reflog for the stash ref during\ncompaction. Can the current compaction algorithm support this?\n\nI suppose there are more exotic alternatives:\n* Go back to the normal ref(log) format for refs/stash. I figure you\nprobably don't want to do this, given that you already moved other\nref-like files into the reftable in a later revision of this proposal.\n* Implement the whole stash storage/command in some other way that\ndoesn't depend on reflog.\n"},{"id":"325373","messageId":"CAJo=hJvsBTDO-8OxrxwfV-=4XWW1w-616DGu31aVb5EU7DWcDA@mail.gmail.com","threadId":"46487","inReplyTo":"CAD0k6qTFV2AAbWiKvi4=OoodoXEgxswLEbraC3xP1LzvtRRaGg@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-08-01T15:27:26Z","receivedAt":"2017-08-01T15:27:54Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Tue, Aug 1, 2017 at 6:54 AM, Dave Borowitz wrote:\n> On Sun, Jul 30, 2017 at 11:51 PM, Shawn Pearce wrote:\n>> - Ref-like files (FETCH_HEAD, MERGE_HEAD) also use type 0x3.\n>\n>> - Combine reflog storage with ref storage for small transactions.\n>> - Separate reflog storage for base refs and historical logs.\n>\n> How is the stash implemented in reftable? In particular, \"git stash\n> drop\" needs to be able to remove an arbitrary single entry from a\n> reflog.\n>\n> I don't think the current proposal supports writing tombstones for\n> reflog entries, so this maybe implies that \"stash drop\" would have to\n> be implemented by rewriting the whole reflog for the stash ref during\n> compaction. Can the current compaction algorithm support this?\n\nYes, the reftable holding the stash would have to be completely\nrewritten for a \"stash drop\" command to be able to remove a reflog\nentry.\n\n> I suppose there are more exotic alternatives:\n> * Go back to the normal ref(log) format for refs/stash. I figure you\n> probably don't want to do this, given that you already moved other\n> ref-like files into the reftable in a later revision of this proposal.\n> * Implement the whole stash storage/command in some other way that\n> doesn't depend on reflog.\n\nI think the simplest is just put refs/stash in its own reftable, and\nput that reftable in the stack somewhere. Editing refs/stash reflog\nrequires rewriting and replacing that reftable in the stack, but\notherwise doesn't impact any other (possibly much larger) reflog.\n\nPushing things onto refs/stash would be creating new small transaction\nreftables on the top of the stack, which should be compacted with the\nlower refs/stash table. I guess that means refs/stash needs special\nhandling in some of the compaction code to keep it isolated.\n"},{"id":"325378","messageId":"CAJo=hJtVat6r6WCghSr3M8PBmEzdjpGt2tgdObvGFKPqQ=myOQ@mail.gmail.com","threadId":"46487","inReplyTo":"CAJo=hJurMO=eQP3xctwTX9cO3yTZogJsw5HMztWjB8JHHtJ=fQ@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-08-01T16:08:26Z","receivedAt":"2017-08-01T16:12:58Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Mon, Jul 31, 2017 at 4:43 PM, Shawn Pearce wrote:\n> On Mon, Jul 31, 2017 at 12:42 PM, Junio C Hamano wrote:\n>>\n>> As a block cannot be longer than 16MB, allocating uint32 to a\n>> restart offset may be a bit overkill. I do not know if it is worth\n>> attempting to pack 1/3 more restart entries in a block by using\n>> uint24, though.\n>\n> I don't think its worth the annoyance in code that has to deal with\n> this field. An example 87k ref repository with a 4k block size has ~9\n> restarts per block and ~19 bytes of padding. Using uint24 saves us 9\n> bytes, yet the average ref here costs 27 bytes. We aren't likely to\n> fill the block with another ref, or another restart point.\n\nI thought about this more. We can fit an additional ref per block in\nsome cases. It saves ~20 KiB for one of my example repositories if\nrestart_offset is a uint24.\n\nGiven that readers have to deal with these being unaligned loads\nanyway, its not significantly harder to work with uint24 vs. uint32.\nSo I've changed the definition to be uint24.\n"},{"id":"325401","messageId":"CAJo=hJtrdCOF-RxzXfyLx7R-1f2-7pZVO_UOg28J=wUDNdf3yw@mail.gmail.com","threadId":"46487","inReplyTo":"CAMy9T_HCnyc1g8XWOOWhe7nN0aEFyyBskV2aOMb_fe+wGvEJ7A@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-08-01T20:23:18Z","receivedAt":"2017-08-01T20:23:45Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Mon, Jul 31, 2017 at 11:41 PM, Michael Haggerty wrote:\n> On Sun, Jul 30, 2017 at 8:51 PM, Shawn Pearce wrote:\n>> 4th iteration of the reftable storage format.\n>> [...]\n>\n> Before we commit to Shawn's reftable proposal, I wanted to explore\n> what a contrasting design that is not block based would look like. So\n> I threw together a sketch of such a design. It is not as refined as\n> Shawn's, and I haven't had time to program an implementation or\n> collect statistics, but maybe it is interesting anyway.\n\nThanks for taking the time to write this out. Its constructive to see\nother possible approaches.\n\nI roughly implemented your proposed design in JGit for references\nonly. I skipped the object lookup and log handling for the sake of\nstudying the basics of this approach.\n\n | size | seek_cold | seek_hot |\nmh | 28.3 M | 24.5 usec | 14.5 usec |\nsp 4k | 29.2 M | 63.0 usec | 5.8 usec |\nsp 64k | 27.7 M | 35.6 usec | 23.3 usec |\n\nAll tests were run with a 4K chunk/block size on an 866k ref example.\nThe mh approach does not use padding between chunks, so chunks are\nvariable sized, but not exceeding 4K. The differences between cold and\nhot is whether or not the file was held open, and the root of the ref\nindex stays in memory.\n\nIn the mh approach with a 4K chunk size and 866k refs, the index is 2\nlevels deep. A cold seek needs to perform 3 disk reads to navigate the\nindex, hot seek is 2 disk reads.\n\n\n> It seems to me that the block-orientation of Shawn's spec adds a lot\n> of complication to the design (e.g., padding, optional blocks, varying\n> block sizes for different parts of the file). It also seems that the\n> format has been heavily optimized to be read in 64k blocks, whereas\n> most users will be storing their references to local hard disks or\n> (increasingly) to local SSDs. So I tried to come up with a design that\n> is friendlier to the latter, hopefully without being much worse for\n> the former.\n\nYes, my design is biased to run well on a 64k block size, where the\nunderlying disk is slow. Ideally reads require only one or two block\nreads. Torn blocks (where a range of data lies on two different\nblocks) are expensive, as both 64k blocks have to be loaded to acquire\ndata that lies across the boundary. Given how fast SSDs are, I don't\nthink this causes any problems for SSD users.\n\n\n> One thing that I realized is that, assuming that reference values and\n> reflogs are usually compacted separately, there will basically be\n> three types of reftable files:\n>\n> 1. Accumulated references and their values (potentially very large)\n>\n> 2. Accumulated reflogs (potentially gigantic)\n>\n> 3. Recent transaction(s), which include both refs and reflogs (usually\n> quite small).\n>\n> The first two types of file don't benefit from separating reference\n> data from reflog data in the file (because they only include one or\n> the other). The third kind of file doesn't care because such files\n> will be small.\n\nIn principal, I agree with your simplification. The important thing is\nkeeping the reflog away from the accumulated references, such that\nscans of references (e.g. current ls-remote advertisement) is\nefficient. I think I was also aiming to do this even for the\ntransaction log files, as ls-remote operations don't need the log\nrecord data.\n\n\n> So let's store all of the data related to a single reference in one\n> spot. This simplifies the file format and removes the need for two\n> separate indexes and/or variants that special-case the omission of an\n> index. A disadvantage is that, it prevents compression of reflog\n> entries across references. I think that is a reasonable tradeoff,\n> because most reflog entries (in the repositories I checked; that might\n> differ in Gerrit-managed repos) correspond to references that have\n> been updated many times. To partly compensate for the resulting\n> reduction in compression, I added some features to reduce the storage\n> of redundant information in reflog entries.\n\nI found the encoding of reflog entries below somewhat complicated, but\nI haven't been able to implement it to compare storage size vs. the\ndeflated block I proposed.\n\n\n> On the other hand, this design does not support binary searching for\n> refnames. Instead, the refnames are distributed into a multiple-level\n> tree. When looking for a reference, each tree node on the way to the\n> reference needs to be parsed serially. But the nodes are small enough\n> (due to the multilevel indexing scheme) that I hope that isn't a\n> problem. I'd rather read less data at the expense of parsing a little\n> bit more.\n\nLooking at the numbers above, the binary search within a 4k block does\nreduce lookup time. E.g. reftable has ~7 binary search restart points\nwithin each 4k block, vs. your approach needing to parse up to 119\nrefs in a 4k chunk.\n\n\n> * Multiple related chunks can be stored in a 64 kiB block (interesting\n> for people who prefer to read files in 64k segments). By storing\n> related chunks near each other, the number of seeks will probably\n> typically be smaller than the number of chunks that have to be\n> accessed.\n\nThis is difficult. The most related chunks are actually index chunks\nin the multi-level index. You want the next step(s) near the current\nstep to avoid an actual disk seek. But that is hard to do when the\nindex is several levels deep.\n\n\n> * The file can be written in two possible ways: with cross-references\n> between chunks always pointing to later parts of the file (probably\n> preferable if the data will be read from a local hard disk) or\n> always pointing to earlier parts of the file (to accomodate writers\n> who need to write their data in order). See the `offsets_negative`\n> field in the header. (I'm not sure that the former variant is\n> actually needed.)\n\nThis seems like unnecessary complexity. I'd prefer to just say the\noffsets are negative, and reference backwards.\n"},{"id":"325410","messageId":"CAJo=hJvFRJ7honjenB6sUofK14xiUXGwJ1DQHZyTauVKA5v5vw@mail.gmail.com","threadId":"46487","inReplyTo":"CAMy9T_HCnyc1g8XWOOWhe7nN0aEFyyBskV2aOMb_fe+wGvEJ7A@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-08-01T23:27:36Z","receivedAt":"2017-08-01T23:28:04Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Mon, Jul 31, 2017 at 11:41 PM, Michael Haggerty wrote:\n> On Sun, Jul 30, 2017 at 8:51 PM, Shawn Pearce wrote:\n>> 4th iteration of the reftable storage format.\n>> [...]\n>\n> Before we commit to Shawn's reftable proposal, I wanted to explore\n> what a contrasting design that is not block based would look like.\n\nI forgot to look at a 1k chunk size, as you suggested that might also\nbe suitable. Here is the more complete experiment table:\n\n | size | seek_cold | seek_hot |\nmh 1k | 36.6 M | 20.6 usec | 10.7 usec |\nmh 4k | 28.3 M | 24.5 usec | 14.5 usec |\nsp 4k | 29.2 M | 63.0 usec | 5.8 usec |\nsp 64k | 27.7 M | 35.6 usec | 23.3 usec |\n\n\nA couple of other notes about your contrasting design:\n\n> elif chunk_type == INDEX {\n> chunk_length : varint\n\nUsing a varint for the chunk length made for a complicated reader.\nJGit doesn't have the luxury of mmap to access the file, so we have to\nallocate a byte[] and read data from a file descriptor to do anything\nfancy like decoding a varint. For my experiment I wound up just\nhardcoding the IO to read 1k or 4k from whatever address.\n\nA \"real\" implementation would likely prefer to read a fixed width\nfield here such that chunks have a 3 byte header (1 byte chunk_type, 2\nbyte chunk_length), and then issue a second read to acquire the rest\nof the chunk. Given that encoding a chunk length of 1024 or 4096 both\nrequires 2 bytes of varint, its always going to be 2 bytes in your\ndesign anyway. With the way chunks are scanned, I don't think you want\nchunks as large as 16k, which would have caused the varint to go to 3\nbytes (but still fits in a fixed 2-byte chunk_length).\n\nMy reftable proposal should still do well in a mmap region. Most of\nthe cold start penalty for reftable is JGit copying the ref index from\nthe file descriptor to the memory block where we can parse the format.\nThat is why the cold_seek time declines for a larger block size, the\nindex is smaller.\n\n\n> first_child : {\n> refname : varstr\n> index_payload\n> }\n> other_children : {\n> # Length of prefix being carried over from the previous\n> # record:\n> prefix_len : varint\n> suffix : varstr\n> index_payload\n\nHaving no prefix_len on first_child made for a slightly funkier\nparser. It does save you a byte, but the parser has to know if its\nlooking at the first child, or an other_children to know if it should\nexpect the prefix_len. Its a simple condition, but it kind of grated\non me when I wrote that particular section of the experiment. For the\nmajority of records the parser considers, the prefix_len is always\npresent.\n\nThat is why I proposed the restart_offsets point to the prefix_len,\nand prefix_len = 0 at restart points. It slightly simplified the\nparser.\n\n\n> elif chunk_type == OBJS_INDEX {\n> chunk_length : varint\n>\n> # The offset, relative to the start of this chunk, of the\n> # chunk containing the next level of the obj index, for each\n> # of the possible \"next\" bytes in the SHA-1, or zero if there\n> # are no references with the given next byte.\n> child_offset : varint * 256\n\nThis is space saving and cute, but kind of annoying. If it was fixed\nwidth 32 bit you can address up to 4G away from this chunk's address,\nand you can directly jump to the byte of interest. By being varints\nyou do save a little space, as most files will probably only need 3\nbyte varints, and the 0s do collapse down to 1 byte, but you have to\nlinearly walk the list to find any specific byte.\n\n\n> ref_payload = {\n> value_type : enum NO_VALUE\n> | DELETED\n> | VALUE | VALUE_PEELED\n> | SYMREF | SYMREF_PEELED\n> | SPECIAL\n> log_type : enum NO_REFLOG | REFLOG | REFLOG_COMPRESSED\n> symref_target : bool\n\nFWIW I didn't implement log_type or symref_target in my experiment, so\nthe size per ref was maybe a few bytes smaller than what you outlined\nhere.\n\n\n> # This field is used to keep backwards links from references to\n> # any symrefs that point at them, to make it tractable to update\n> # the reflog of the symref if the reference is changed directly:\n> if symref_target {\n> referer : varstr\n> varint(0)\n> }\n\nI wonder how desirable this feature is. Most updates are done through\nHEAD, which is a symref and can therefore update both HEAD and the\ntarget's reflogs in the same operation. It seems to me its rare to\nissue an update directly on the ref that HEAD points at. Its even\nrarer to have a non-HEAD symbolic reference whose reflog you expect to\ntrack something else.\n\nIs this for refs/remotes/origin/HEAD to be a symref and have its\nreflog mirror the fetch operations that touched the underlying ref?\n"},{"id":"325411","messageId":"CAJo=hJv3O98t+GXDmh99EwXziapSmGKKNk075MhP6E0USyMXqQ@mail.gmail.com","threadId":"46487","inReplyTo":"CAJo=hJvFRJ7honjenB6sUofK14xiUXGwJ1DQHZyTauVKA5v5vw@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-08-01T23:54:55Z","receivedAt":"2017-08-01T23:55:28Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Tue, Aug 1, 2017 at 4:27 PM, Shawn Pearce wrote:\n> On Mon, Jul 31, 2017 at 11:41 PM, Michael Haggerty wrote:\n>> On Sun, Jul 30, 2017 at 8:51 PM, Shawn Pearce wrote:\n>>> 4th iteration of the reftable storage format.\n>>> [...]\n>>\n>> Before we commit to Shawn's reftable proposal, I wanted to explore\n>> what a contrasting design that is not block based would look like.\n>\n> I forgot to look at a 1k chunk size, as you suggested that might also\n> be suitable. Here is the more complete experiment table:\n>\n> | size | seek_cold | seek_hot |\n> mh 1k | 36.6 M | 20.6 usec | 10.7 usec |\n> mh 4k | 28.3 M | 24.5 usec | 14.5 usec |\n> sp 4k | 29.2 M | 63.0 usec | 5.8 usec |\n> sp 64k | 27.7 M | 35.6 usec | 23.3 usec |\n\nArgh. I got that mh 1k size wrong, its actually 29.4M (not 36.6M!).\nSorry for the noise.\n"},{"id":"325414","messageId":"CAMy9T_FA1RV+NFxaXR65gw7G6OxL7Z8Ve3VNLrF4oyCdqtdahg@mail.gmail.com","threadId":"46487","inReplyTo":"CAJo=hJtrdCOF-RxzXfyLx7R-1f2-7pZVO_UOg28J=wUDNdf3yw@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-08-02T00:49:47Z","receivedAt":"2017-08-02T00:49:57Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On Tue, Aug 1, 2017 at 1:23 PM, Shawn Pearce wrote:\n> On Mon, Jul 31, 2017 at 11:41 PM, Michael Haggerty wrote:\n>> On Sun, Jul 30, 2017 at 8:51 PM, Shawn Pearce wrote:\n>>> 4th iteration of the reftable storage format.\n>>> [...]\n>>\n>> Before we commit to Shawn's reftable proposal, I wanted to explore\n>> what a contrasting design that is not block based would look like. So\n>> I threw together a sketch of such a design. It is not as refined as\n>> Shawn's, and I haven't had time to program an implementation or\n>> collect statistics, but maybe it is interesting anyway.\n>\n> Thanks for taking the time to write this out. Its constructive to see\n> other possible approaches.\n>\n> I roughly implemented your proposed design in JGit for references\n> only. I skipped the object lookup and log handling for the sake of\n> studying the basics of this approach.\n\nWow, that's awesome, thanks!\n\n> | size | seek_cold | seek_hot |\n> mh | 28.3 M | 24.5 usec | 14.5 usec |\n> sp 4k | 29.2 M | 63.0 usec | 5.8 usec |\n> sp 64k | 27.7 M | 35.6 usec | 23.3 usec |\n\nOK, so it's at least in the right ballpark.\n\n>> * Multiple related chunks can be stored in a 64 kiB block (interesting\n>> for people who prefer to read files in 64k segments). By storing\n>> related chunks near each other, the number of seeks will probably\n>> typically be smaller than the number of chunks that have to be\n>> accessed.\n>\n> This is difficult. The most related chunks are actually index chunks\n> in the multi-level index. You want the next step(s) near the current\n> step to avoid an actual disk seek. But that is hard to do when the\n> index is several levels deep.\n\nGiven the 64k read size that you prefer, it seems to me that it would\nprobably be possible to keep pairs of index layers (i.e., one index\nnode and all of its direct children) in the same 64k range, though\nthis might require adjusting their sizes somewhat. And possibly to\nkeep the lowest index layer close to the reference chunks that it\ndescribes (analogous to your format, where the restart records form\nsomething like an index that is located close to the references). So I\nwould think that it is plausible to arrange things so that a reference\ncan be read within two 64k reads even if the index has three levels.\n\n>> * The file can be written in two possible ways: with cross-references\n>> between chunks always pointing to later parts of the file (probably\n>> preferable if the data will be read from a local hard disk) or\n>> always pointing to earlier parts of the file (to accomodate writers\n>> who need to write their data in order). See the `offsets_negative`\n>> field in the header. (I'm not sure that the former variant is\n>> actually needed.)\n>\n> This seems like unnecessary complexity. I'd prefer to just say the\n> offsets are negative, and reference backwards.\n\nMaybe. I just wasn't sure whether a hard disk would perform\nsignificantly worse when reading backwards rather than forwards\n(because of pre-fetch of blocks). It could very well be unnecessary.\n\nMichael\n"},{"id":"325415","messageId":"CAMy9T_HUoD4--s1gNTUjnCgdiAqfYbX-GSqygDwNO-JRwdh4NQ@mail.gmail.com","threadId":"46487","inReplyTo":"CAJo=hJvFRJ7honjenB6sUofK14xiUXGwJ1DQHZyTauVKA5v5vw@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-08-02T01:51:14Z","receivedAt":"2017-08-02T01:51:25Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On Tue, Aug 1, 2017 at 4:27 PM, Shawn Pearce wrote:\n> On Mon, Jul 31, 2017 at 11:41 PM, Michael Haggerty wrote:\n>> On Sun, Jul 30, 2017 at 8:51 PM, Shawn Pearce wrote:\n>>> 4th iteration of the reftable storage format.\n>>> [...]\n>>\n>> Before we commit to Shawn's reftable proposal, I wanted to explore\n>> what a contrasting design that is not block based would look like.\n>\n> I forgot to look at a 1k chunk size, as you suggested that might also\n> be suitable. Here is the more complete experiment table:\n>\n> | size | seek_cold | seek_hot |\n> mh 1k | 29.4 M | 20.6 usec | 10.7 usec | <== Row fixed\n> mh 4k | 28.3 M | 24.5 usec | 14.5 usec |\n> sp 4k | 29.2 M | 63.0 usec | 5.8 usec |\n> sp 64k | 27.7 M | 35.6 usec | 23.3 usec |\n\nAt least in this case, the 1k block size seems like a good tradeoff.\nDid 1k vs 4k change the number of index levels required?\n\n> A couple of other notes about your contrasting design:\n>\n>> elif chunk_type == INDEX {\n>> chunk_length : varint\n>\n> Using a varint for the chunk length made for a complicated reader.\n> JGit doesn't have the luxury of mmap to access the file, so we have to\n> allocate a byte[] and read data from a file descriptor to do anything\n> fancy like decoding a varint. For my experiment I wound up just\n> hardcoding the IO to read 1k or 4k from whatever address.\n>\n> A \"real\" implementation would likely prefer to read a fixed width\n> field here such that chunks have a 3 byte header (1 byte chunk_type, 2\n> byte chunk_length), and then issue a second read to acquire the rest\n> of the chunk. Given that encoding a chunk length of 1024 or 4096 both\n> requires 2 bytes of varint, its always going to be 2 bytes in your\n> design anyway. With the way chunks are scanned, I don't think you want\n> chunks as large as 16k, which would have caused the varint to go to 3\n> bytes (but still fits in a fixed 2-byte chunk_length).\n\nThat's a good point for INDEX and OBJS_INDEX blocks. Though for REFS\nblocks that include reflogs, the block size has to be large enough to\nhold the whole reflog for a reference, which can be arbitrarily large.\n(Maybe this is a weakness of the design?) OBJS blocks can also be\nunbounded in size if very many references point at the same object,\nthought that is perhaps only a theoretical problem.\n\n> My reftable proposal should still do well in a mmap region. Most of\n> the cold start penalty for reftable is JGit copying the ref index from\n> the file descriptor to the memory block where we can parse the format.\n> That is why the cold_seek time declines for a larger block size, the\n> index is smaller.\n>\n>\n>> first_child : {\n>> refname : varstr\n>> index_payload\n>> }\n>> other_children : {\n>> # Length of prefix being carried over from the previous\n>> # record:\n>> prefix_len : varint\n>> suffix : varstr\n>> index_payload\n>\n> Having no prefix_len on first_child made for a slightly funkier\n> parser. It does save you a byte, but the parser has to know if its\n> looking at the first child, or an other_children to know if it should\n> expect the prefix_len. Its a simple condition, but it kind of grated\n> on me when I wrote that particular section of the experiment. For the\n> majority of records the parser considers, the prefix_len is always\n> present.\n>\n> That is why I proposed the restart_offsets point to the prefix_len,\n> and prefix_len = 0 at restart points. It slightly simplified the\n> parser.\n\nYes, that seems like a reasonable compromise.\n\n>> elif chunk_type == OBJS_INDEX {\n>> chunk_length : varint\n>>\n>> # The offset, relative to the start of this chunk, of the\n>> # chunk containing the next level of the obj index, for each\n>> # of the possible \"next\" bytes in the SHA-1, or zero if there\n>> # are no references with the given next byte.\n>> child_offset : varint * 256\n>\n> This is space saving and cute, but kind of annoying. If it was fixed\n> width 32 bit you can address up to 4G away from this chunk's address,\n> and you can directly jump to the byte of interest. By being varints\n> you do save a little space, as most files will probably only need 3\n> byte varints, and the 0s do collapse down to 1 byte, but you have to\n> linearly walk the list to find any specific byte.\n\nThe reason I used varint here was mostly because I expect the lowest\nlevel of the OBJS_INDEX to be placed close to the OBJS chunks that it\nrefers to; hopefully within a 2-byte varint. Let me consider more\ncarefully whether that is realistic...\n\nAn OBJS_INDEX should be well under 1kB in size. The lowest-level\nOBJS_INDEX will presumably be relatively but not totally full\n(otherwise you'd add another OBJS_INDEX level); suppose 1/2 of its\nentries are filled. Most of those entries should contain only a single\nSHA-1.\n\nAn obj_record will typically be 3 bytes plus the size of one\n`child_addr`. The latter is in the earlier part of the file, but for\nyour 30 MB example, that will probably be 4 bytes per address. So the\ntotal size of the obj_records would be about 7 bytes * 128 which is\nalso less than a kB.\n\nSo a 2-byte varint should be more than enough for child_offset for the\nlowest-level OBJS_INDEXes (which in turn are by far the most common\ntypes of OBJS_INDEXes). And if the OBJ_INDEX is less full, the zeros\ncan be stored in one byte.\n\nIndeed, it might make sense to special-case the lowest-level\nOBJS_INDEX chunk type to use uint16 pointers and store the obj_records\ndirectly in the chunk, following the child_offsets.\n\nThe higher-level OBJS_INDEXes might have to point further away. I\nthink it would be a bad idea to limit reftable file sizes to 4 GB,\nthough maybe it's not unreasonable to limit the OBJS_INDEX part of the\nfile to that size so that a uint32 to be used?\n\nPeff and I discussed off-list whether the lookup-by-SHA-1 feature is\nso important in the first place. Currently, all references must be\nscanned for the advertisement anyway, so avoiding a second scan to vet\nSHA-1s received from the client is at best going to reduce the effort\nby a constant factor. Do you have numbers showing that this\noptimization is worth it?\n\nOTOH a mythical protocol v2 might reduce the need to scan the\nreferences for advertisement, so maybe this optimization will be more\nhelpful in the future?\n\n>> ref_payload = {\n>> value_type : enum NO_VALUE\n>> | DELETED\n>> | VALUE | VALUE_PEELED\n>> | SYMREF | SYMREF_PEELED\n>> | SPECIAL\n>> log_type : enum NO_REFLOG | REFLOG | REFLOG_COMPRESSED\n>> symref_target : bool\n>\n> FWIW I didn't implement log_type or symref_target in my experiment, so\n> the size per ref was maybe a few bytes smaller than what you outlined\n> here.\n\nBut value_type, log_type, and symref_target should all fit within a\nsingle byte, no?\n\n>> # This field is used to keep backwards links from references to\n>> # any symrefs that point at them, to make it tractable to update\n>> # the reflog of the symref if the reference is changed directly:\n>> if symref_target {\n>> referer : varstr\n>> varint(0)\n>> }\n>\n> I wonder how desirable this feature is. Most updates are done through\n> HEAD, which is a symref and can therefore update both HEAD and the\n> target's reflogs in the same operation. It seems to me its rare to\n> issue an update directly on the ref that HEAD points at. Its even\n> rarer to have a non-HEAD symbolic reference whose reflog you expect to\n> track something else.\n>\n> Is this for refs/remotes/origin/HEAD to be a symref and have its\n> reflog mirror the fetch operations that touched the underlying ref?\n\nWhat I was thinking is that we don't update symrefs' reflogs correctly\nif the pointed-to reference is updated (except for HEAD) and it would\nbe nice to fix that problem. Your case of `refs/remotes/origin/HEAD`\nis an example. Or on GitHub's servers, if we wanted to store all of\nthe forks of a repo in a single repository, we might want to use a\nnamespace for each fork, like `refs/forks/NNNN/*`, and store the\nfork's default branch in `refs/forks/NNNN/HEAD`. The current refs code\nwouldn't know to update such a symref's reflog (though of course it\ncould be special-cased in like HEAD is now).\n\nThat's what I was thinking. But I've yet to hear anybody complain\nabout missing reflogs for symrefs if the underlying reference is\nupdated directly, so maybe we should just leave that \"problem\"\nunsolved. It is certainly simpler and less brittle not to have to keep\nbackreferences like these in sync with the forward references.\n\nMichael\n"},{"id":"325416","messageId":"CAJo=hJv=zJvbzfAZwspxECXrnBJR4XfJbGZegsNUCx=6uheO2Q@mail.gmail.com","threadId":"46487","inReplyTo":"CAMy9T_HUoD4--s1gNTUjnCgdiAqfYbX-GSqygDwNO-JRwdh4NQ@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-08-02T02:38:37Z","receivedAt":"2017-08-02T02:39:04Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Tue, Aug 1, 2017 at 6:51 PM, Michael Haggerty wrote:\n> On Tue, Aug 1, 2017 at 4:27 PM, Shawn Pearce wrote:\n>> On Mon, Jul 31, 2017 at 11:41 PM, Michael Haggerty wrote:\n>>> On Sun, Jul 30, 2017 at 8:51 PM, Shawn Pearce wrote:\n>>>> 4th iteration of the reftable storage format.\n>>>> [...]\n>>>\n>>> Before we commit to Shawn's reftable proposal, I wanted to explore\n>>> what a contrasting design that is not block based would look like.\n>>\n>> I forgot to look at a 1k chunk size, as you suggested that might also\n>> be suitable. Here is the more complete experiment table:\n>>\n>> | size | seek_cold | seek_hot |\n>> mh 1k | 29.4 M | 20.6 usec | 10.7 usec | <== Row fixed\n>> mh 4k | 28.3 M | 24.5 usec | 14.5 usec |\n>> sp 4k | 29.2 M | 63.0 usec | 5.8 usec |\n>> sp 64k | 27.7 M | 35.6 usec | 23.3 usec |\n>\n> At least in this case, the 1k block size seems like a good tradeoff.\n> Did 1k vs 4k change the number of index levels required?\n\nYes. 1k needed 4 levels of index; 4k needed 2 levels.\nMore chunks, with smaller index chunks, forces a deeper index depth.\n\n\n>> A couple of other notes about your contrasting design:\n>>\n>>> elif chunk_type == INDEX {\n>>> chunk_length : varint\n>>\n>> Using a varint for the chunk length made for a complicated reader.\n>> JGit doesn't have the luxury of mmap to access the file, so we have to\n>> allocate a byte[] and read data from a file descriptor to do anything\n>> fancy like decoding a varint. For my experiment I wound up just\n>> hardcoding the IO to read 1k or 4k from whatever address.\n>>\n>> A \"real\" implementation would likely prefer to read a fixed width\n>> field here such that chunks have a 3 byte header (1 byte chunk_type, 2\n>> byte chunk_length), and then issue a second read to acquire the rest\n>> of the chunk. Given that encoding a chunk length of 1024 or 4096 both\n>> requires 2 bytes of varint, its always going to be 2 bytes in your\n>> design anyway. With the way chunks are scanned, I don't think you want\n>> chunks as large as 16k, which would have caused the varint to go to 3\n>> bytes (but still fits in a fixed 2-byte chunk_length).\n>\n> That's a good point for INDEX and OBJS_INDEX blocks. Though for REFS\n> blocks that include reflogs, the block size has to be large enough to\n> hold the whole reflog for a reference, which can be arbitrarily large.\n> (Maybe this is a weakness of the design?)\n\nGah. I missed that part about the whole reflog needing to fit in the\nsame chunk when I wrote the quoted text above. That is a pretty big\ndownside for very busy refs.\n\nEven when you isolate logs into their own file, the reflog for a busy\nref could be huge. A naive reader would want to \"page in\" the entire\nchunk_length before parsing. That isn't tenable if the reflog for a\nbusy ref was say 50 MiB. It complicates the reader more. My reftable\nproposal deals with this by breaking the log up with its special key\nstructure.\n\nRequiring the entire reflog of a single ref to fit into a single chunk\ndoes seem to have its downsides.\n\n\n> OBJS blocks can also be\n> unbounded in size if very many references point at the same object,\n> thought that is perhaps only a theoretical problem.\n\nGah, I missed that in reftable. The block id pointer list could cause\na single object id to exceed what fits in a block, and that will cause\nthe writer to fail unless its caller sets the block size larger. I\nbasically assumed this overflow condition is very unlikely, as its not\ncommon to have a huge number of refs pointing to the same object.\n\n\n>>> elif chunk_type == OBJS_INDEX {\n>>> chunk_length : varint\n>>>\n>>> # The offset, relative to the start of this chunk, of the\n>>> # chunk containing the next level of the obj index, for each\n>>> # of the possible \"next\" bytes in the SHA-1, or zero if there\n>>> # are no references with the given next byte.\n>>> child_offset : varint * 256\n>>\n>> This is space saving and cute, but kind of annoying. If it was fixed\n>> width 32 bit you can address up to 4G away from this chunk's address,\n>> and you can directly jump to the byte of interest. By being varints\n>> you do save a little space, as most files will probably only need 3\n>> byte varints, and the 0s do collapse down to 1 byte, but you have to\n>> linearly walk the list to find any specific byte.\n>\n> The reason I used varint here was mostly because I expect the lowest\n> level of the OBJS_INDEX to be placed close to the OBJS chunks that it\n> refers to; hopefully within a 2-byte varint. Let me consider more\n> carefully whether that is realistic...\n\nAh, ok. So you were expecting the writer to interleave OBJS and\nOBJS_INDEX chunks, with the OBJS_INDEX appearing every ~256 OBJS\nchunks. And then storing the next level of OBJS_INDEX consecutively.\n\nI think your math is still wrong about the lowest level OBJS_INDEX\nneeding only 2-byte varint for child_offset. Given a 1k chunk size,\nyou still have to address backwards about 256k, which requires a\n3-byte varint.\n\n\nGiven the uniform distribution of SHA-1, I think you still wind up\nwith most of the OBJS_INDEX populated. E.g. in my 866k ref/865k obj\nexample the unique object abbreviation is 6 raw bytes. The OBJS chunk\nstoring 2 bytes means we have 4 levels of OBJS_INDEX to cover the\nfirst 4 bytes. That leaves ~844 obj_records in each OBJS chunk. If\nthose are 7 bytes/obj_record, the OBJS chunk is ~5.7 KiB.\n\nForcing the OBJS chunk to stay under say 4 KiB will absolutely cause a\nlot more holes in the OBJS_INDEX levels.\n\n\n> Peff and I discussed off-list whether the lookup-by-SHA-1 feature is\n> so important in the first place. Currently, all references must be\n> scanned for the advertisement anyway,\n\nNot really. You can hide refs and allow-tip-sha1 so clients can fetch\na ref even if it wasn't in the advertisement. We really want to use\nthat wire protocol capability with Gerrit Code Review to hide the\nrefs/changes/ namespace from the advertisement, but allow clients to\nfetch any of those refs if they send its current SHA-1 in a want line\nanyway.\n\nSo a server could scan only the refs/{heads,tags}/ prefixes for the\nadvertisement, and then leverage the lookup-by-SHA1 to verify other\nSHA-1s sent by the client.\n\n> so avoiding a second scan to vet\n> SHA-1s received from the client is at best going to reduce the effort\n> by a constant factor. Do you have numbers showing that this\n> optimization is worth it?\n\nNo, but I don't think I need to do much to prove it. My 866k ref\nexample advertisement right now is >62 MiB. If we do what I'm\nsuggesting in the paragraphs above, the advertisement is ~51 KiB.\n\n> OTOH a mythical protocol v2 might reduce the need to scan the\n> references for advertisement, so maybe this optimization will be more\n> helpful in the future?\n\nYes, I'm hopeful we can get a v2 protocol built on the work Jonathan\nTan is doing, and switch the advertisement around to \"client speaks\nfirst\", so that we can be smarter on the server about which refs are\nread and sent. That is a long way off, lets say 3-5 years before its\nreally common in clients.\n\n\n>>> ref_payload = {\n>>> value_type : enum NO_VALUE\n>>> | DELETED\n>>> | VALUE | VALUE_PEELED\n>>> | SYMREF | SYMREF_PEELED\n>>> | SPECIAL\n>>> log_type : enum NO_REFLOG | REFLOG | REFLOG_COMPRESSED\n>>> symref_target : bool\n>>\n>> FWIW I didn't implement log_type or symref_target in my experiment, so\n>> the size per ref was maybe a few bytes smaller than what you outlined\n>> here.\n>\n> But value_type, log_type, and symref_target should all fit within a\n> single byte, no?\n\nYes. So my experiment was maybe ~866 KiB off in total file size. :)\n\n\n>>> # This field is used to keep backwards links from references to\n>>> # any symrefs that point at them, to make it tractable to update\n>>> # the reflog of the symref if the reference is changed directly:\n>>> if symref_target {\n>>> referer : varstr\n>>> varint(0)\n>>> }\n>>\n>> I wonder how desirable this feature is. Most updates are done through\n>> HEAD, which is a symref and can therefore update both HEAD and the\n>> target's reflogs in the same operation. It seems to me its rare to\n>> issue an update directly on the ref that HEAD points at. Its even\n>> rarer to have a non-HEAD symbolic reference whose reflog you expect to\n>> track something else.\n>>\n>> Is this for refs/remotes/origin/HEAD to be a symref and have its\n>> reflog mirror the fetch operations that touched the underlying ref?\n>\n> What I was thinking is that we don't update symrefs' reflogs correctly\n> if the pointed-to reference is updated (except for HEAD) and it would\n> be nice to fix that problem. Your case of `refs/remotes/origin/HEAD`\n> is an example. Or on GitHub's servers, if we wanted to store all of\n> the forks of a repo in a single repository, we might want to use a\n> namespace for each fork, like `refs/forks/NNNN/*`, and store the\n> fork's default branch in `refs/forks/NNNN/HEAD`. The current refs code\n> wouldn't know to update such a symref's reflog (though of course it\n> could be special-cased in like HEAD is now).\n\nServers today don't update HEAD reflog when a branch is pushed. I\nthink trying to record that is overkill, you have the reflog data in\nthe ref itself that the client sent the command to modify.\n\n> That's what I was thinking. But I've yet to hear anybody complain\n> about missing reflogs for symrefs if the underlying reference is\n> updated directly, so maybe we should just leave that \"problem\"\n> unsolved. It is certainly simpler and less brittle not to have to keep\n> backreferences like these in sync with the forward references.\n\nYup, that is my take on it, and why I didn't try to put this into\nreftable drafts, even though it was discussed between us on the list\nin earlier messages.\n"},{"id":"325419","messageId":"20170802092846.u4lyiogvvl7ezdfq@sigill.intra.peff.net","threadId":"46487","inReplyTo":"CAJo=hJv=zJvbzfAZwspxECXrnBJR4XfJbGZegsNUCx=6uheO2Q@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-08-02T09:28:46Z","receivedAt":"2017-08-02T09:28:54Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Aug 01, 2017 at 07:38:37PM -0700, Shawn Pearce wrote:\n\n> > OBJS blocks can also be\n> > unbounded in size if very many references point at the same object,\n> > thought that is perhaps only a theoretical problem.\n> \n> Gah, I missed that in reftable. The block id pointer list could cause\n> a single object id to exceed what fits in a block, and that will cause\n> the writer to fail unless its caller sets the block size larger. I\n> basically assumed this overflow condition is very unlikely, as its not\n> common to have a huge number of refs pointing to the same object.\n\nIt's actually quite common for us, as we have big shared-object repos\nthat contain a copy of the refs of all of their child repos (for\nreachability during packing, etc). So tags, where the value is the same\nin each fork, you have one ref per fork pointing to it.\n\nJust peeking at torvalds/linux, we have some objects with ~35K refs\npointing to them (e.g., the v2.6.11 tag).\n\n> > Peff and I discussed off-list whether the lookup-by-SHA-1 feature is\n> > so important in the first place. Currently, all references must be\n> > scanned for the advertisement anyway,\n> \n> Not really. You can hide refs and allow-tip-sha1 so clients can fetch\n> a ref even if it wasn't in the advertisement. We really want to use\n> that wire protocol capability with Gerrit Code Review to hide the\n> refs/changes/ namespace from the advertisement, but allow clients to\n> fetch any of those refs if they send its current SHA-1 in a want line\n> anyway.\n> \n> So a server could scan only the refs/{heads,tags}/ prefixes for the\n> advertisement, and then leverage the lookup-by-SHA1 to verify other\n> SHA-1s sent by the client.\n\nYeah, that makes sense (though I hope in the end that strategy will go\naway in favor of a better protocol, as getting the sha1 out-of-band has\nobvious UX complexities).\n\n> > OTOH a mythical protocol v2 might reduce the need to scan the\n> > references for advertisement, so maybe this optimization will be more\n> > helpful in the future?\n> \n> Yes, I'm hopeful we can get a v2 protocol built on the work Jonathan\n> Tan is doing, and switch the advertisement around to \"client speaks\n> first\", so that we can be smarter on the server about which refs are\n> read and sent. That is a long way off, lets say 3-5 years before its\n> really common in clients.\n\nI was actually planning to spend some time on this in the next month or\ntwo. I don't think it needs to be that complicated. We don't need a\nwhole protocol revamp. We just need a way to get a few bits from the\nclient before the advertisement, and from there we can bootstrap any\nmore radical protocol changes we want.\n\nI know it will take a while before it's something we can expect in\nclients, but it's definitely worth planning around. And sometimes a\nfeature like this can drive upgrades, if it's something that produces an\nimmediate and obvious benefit to the client.\n\n> Servers today don't update HEAD reflog when a branch is pushed. I\n> think trying to record that is overkill, you have the reflog data in\n> the ref itself that the client sent the command to modify.\n\nI think they do, at least for C git:\n\n $ git init --bare dst.git\n $ git -C dst.git config core.logallrefupdates\n $ git push dst.git\n ...\n To dst.git\n * [new branch] master -> master\n $ find dst.git/logs -type f | xargs wc -l\n 1 dst.git/logs/refs/heads/master\n 1 dst.git/logs/HEAD\n\nThe special logic for \"see if we're updating the ref that HEAD points\nto\" is deep in the ref machinery, so it gets triggered for all updates,\nincluding pushes.\n\nI agree it's not actually that interesting for a bare repo, where HEAD\nisn't that meaningful (and doesn't tend to change a lot anyway).\n\n> > That's what I was thinking. But I've yet to hear anybody complain\n> > about missing reflogs for symrefs if the underlying reference is\n> > updated directly, so maybe we should just leave that \"problem\"\n> > unsolved. It is certainly simpler and less brittle not to have to keep\n> > backreferences like these in sync with the forward references.\n> \n> Yup, that is my take on it, and why I didn't try to put this into\n> reftable drafts, even though it was discussed between us on the list\n> in earlier messages.\n\nYeah, I'd agree. It might be worth doing a better job of showing the\nbefore/after destinations in the reflog when updating a symbolic ref,\nwhich would let you reconstruct the state from the pointed-to reflogs if\nyou cared to. But that's orthogonal to the storage format (you can do it\nalready if you bother to pass a good message to \"symbolic-ref -m\").\n\n-Peff\n"},{"id":"325427","messageId":"CAD0k6qRTa6jSgEBBX1Ux5yg4QMMWPpyOGTa471cRhtzBaS-KjQ@mail.gmail.com","threadId":"46487","inReplyTo":"CAJo=hJv=zJvbzfAZwspxECXrnBJR4XfJbGZegsNUCx=6uheO2Q@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Dave Borowitz","fromEmail":"dborowitz@google.com","sentAt":"2017-08-02T12:20:44Z","receivedAt":"2017-08-02T12:21:11Z","isPatch":false,"sender":{"key":"dborowitz@google.com","avatar":"https://avatars.githubusercontent.com/u/194927?v=4"},"body":"On Tue, Aug 1, 2017 at 10:38 PM, Shawn Pearce wrote:\n>> Peff and I discussed off-list whether the lookup-by-SHA-1 feature is\n>> so important in the first place. Currently, all references must be\n>> scanned for the advertisement anyway,\n>\n> Not really. You can hide refs and allow-tip-sha1 so clients can fetch\n> a ref even if it wasn't in the advertisement. We really want to use\n> that wire protocol capability with Gerrit Code Review to hide the\n> refs/changes/ namespace from the advertisement, but allow clients to\n> fetch any of those refs if they send its current SHA-1 in a want line\n> anyway.\n>\n> So a server could scan only the refs/{heads,tags}/ prefixes for the\n> advertisement, and then leverage the lookup-by-SHA1 to verify other\n> SHA-1s sent by the client.\n>\n>> so avoiding a second scan to vet\n>> SHA-1s received from the client is at best going to reduce the effort\n>> by a constant factor. Do you have numbers showing that this\n>> optimization is worth it?\n>\n> No, but I don't think I need to do much to prove it. My 866k ref\n> example advertisement right now is >62 MiB. If we do what I'm\n> suggesting in the paragraphs above, the advertisement is ~51 KiB.\n\nThat being said, our bias towards minimizing the number of ref scans\nis rooted in our experience where scanning 866k refs takes 5 seconds\nto get the response from the storage backend into the git server.\nCutting ref scans from 2 to 1 (or 1 to 0) is a big deal in that case.\nBut that 5s number is based on our current, slow storage, not on\nreftable. If migrating to reftable turns each 5s scan into a 400ms\nscan, we might be able to live with that, even if we don't have fast\nlookup by SHA-1.\n\n>> OTOH a mythical protocol v2 might reduce the need to scan the\n>> references for advertisement, so maybe this optimization will be more\n>> helpful in the future?\n\nI haven't been following the status of the proposal, but I was\nassuming a client-speaks-first protocol would also imply the client\nasking for refnames, not SHA-1s, in which case lookup by SHA-1 is no\nlonger relevant.\n"},{"id":"325432","messageId":"CAJo=hJu1rud5pEZ93HDty1qyaCOHmwn89aEvPFe2ER0JD1ExwQ@mail.gmail.com","threadId":"46487","inReplyTo":"20170802092846.u4lyiogvvl7ezdfq@sigill.intra.peff.net","subject":"Re: reftable [v4]: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-08-02T15:17:29Z","receivedAt":"2017-08-02T15:17:58Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Wed, Aug 2, 2017 at 2:28 AM, Jeff King wrote:\n> On Tue, Aug 01, 2017 at 07:38:37PM -0700, Shawn Pearce wrote:\n>\n>> > OBJS blocks can also be\n>> > unbounded in size if very many references point at the same object,\n>> > thought that is perhaps only a theoretical problem.\n>>\n>> Gah, I missed that in reftable. The block id pointer list could cause\n>> a single object id to exceed what fits in a block, and that will cause\n>> the writer to fail unless its caller sets the block size larger. I\n>> basically assumed this overflow condition is very unlikely, as its not\n>> common to have a huge number of refs pointing to the same object.\n>\n> It's actually quite common for us, as we have big shared-object repos\n> that contain a copy of the refs of all of their child repos (for\n> reachability during packing, etc). So tags, where the value is the same\n> in each fork, you have one ref per fork pointing to it.\n>\n> Just peeking at torvalds/linux, we have some objects with ~35K refs\n> pointing to them (e.g., the v2.6.11 tag).\n\nOy. I'll bet that every occurrence winds up in its own block due to\nthe layout of the namespace, and so the obj block list needs 35k\nvarint pointers. That requires a larger block size if it has any\nchance of fitting into the reftable format.\n\nAnother option is disable the obj table for these shared-object repos.\nIts an optional part of the format and can be omitted if the reader\nisn't likely to need to lookup by SHA-1, or is willing to pay the\nbrute force cost of scanning every ref.\n"},{"id":"325441","messageId":"xmqqshh9diar.fsf@gitster.mtv.corp.google.com","threadId":"46487","inReplyTo":"CAJo=hJu1rud5pEZ93HDty1qyaCOHmwn89aEvPFe2ER0JD1ExwQ@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-08-02T16:51:40Z","receivedAt":"2017-08-02T16:51:47Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> On Wed, Aug 2, 2017 at 2:28 AM, Jeff King wrote:\n>> On Tue, Aug 01, 2017 at 07:38:37PM -0700, Shawn Pearce wrote:\n>>\n>>> > OBJS blocks can also be\n>>> > unbounded in size if very many references point at the same object,\n>>> > thought that is perhaps only a theoretical problem.\n>>>\n>>> Gah, I missed that in reftable. The block id pointer list could cause\n>>> a single object id to exceed what fits in a block, and that will cause\n>>> the writer to fail unless its caller sets the block size larger. I\n>>> basically assumed this overflow condition is very unlikely, as its not\n>>> common to have a huge number of refs pointing to the same object.\n>>\n>> It's actually quite common for us, as we have big shared-object repos\n>> that contain a copy of the refs of all of their child repos (for\n>> reachability during packing, etc). So tags, where the value is the same\n>> in each fork, you have one ref per fork pointing to it.\n>>\n>> Just peeking at torvalds/linux, we have some objects with ~35K refs\n>> pointing to them (e.g., the v2.6.11 tag).\n>\n> Oy. I'll bet that every occurrence winds up in its own block due to\n> the layout of the namespace, and so the obj block list needs 35k\n> varint pointers. That requires a larger block size if it has any\n> chance of fitting into the reftable format.\n>\n> Another option is disable the obj table for these shared-object repos.\n> Its an optional part of the format and can be omitted if the reader\n> isn't likely to need to lookup by SHA-1, or is willing to pay the\n> brute force cost of scanning every ref.\n\nI am wondering if we need the reverse look-up for a regular\nrepository that allows \"fetch anything at the tip\". It only needs\n\"I got this request for an object name--does it sit at the tip of\nany ref? Yes/No\". It does not need to know exactly which ref\npoints at the asked object.\n\nYes, I know Gerrit has its own ACL that limits the visibility of\nrefs so the question becomes \"does it sit at the tip of any ref that\nis visible to the current user?\". An Yes/No answer for \"any ref?\"\nmay still give you a short-cut when rejecting, but you'd then need\nto scan to give a positive answer without a full reverse mapping.\n\nFor the use of \"consolidated object store for all forks\", I do not\nthink it makes sense to even have \"Does it sit at a tip, Yes/No\"\ninformation. Even when Linus's repository and a fork share the same\nobject store, I do not think anybody expects to be able to fetch a\ncommit at the tip of a branch in the fork but not in Linus's\nrepository.\n\n"},{"id":"325442","messageId":"20170802171849.qwg36gahgrav3o25@sigill.intra.peff.net","threadId":"46487","inReplyTo":"CAD0k6qRTa6jSgEBBX1Ux5yg4QMMWPpyOGTa471cRhtzBaS-KjQ@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-08-02T17:18:49Z","receivedAt":"2017-08-02T17:18:58Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 02, 2017 at 08:20:44AM -0400, Dave Borowitz wrote:\n\n> >> OTOH a mythical protocol v2 might reduce the need to scan the\n> >> references for advertisement, so maybe this optimization will be more\n> >> helpful in the future?\n> \n> I haven't been following the status of the proposal, but I was\n> assuming a client-speaks-first protocol would also imply the client\n> asking for refnames, not SHA-1s, in which case lookup by SHA-1 is no\n> longer relevant.\n\nGood point. The hidden-refs thing Shawn described is a trick that would\nbe used because the current protocol is so lousy. It's not clear how a\nstateless-rpc request would work, but in theory the follow-up requests\ncould also say \"hey, I'm only interested in refs/{heads,tags}\" and the\nstateless server could limit is marking to that.\n\nBut that would still leave something like allowReachableSHA1InWant\nhaving to look at all refs (and I don't see why a client requesting by\nsha1 would give any limiting refspec at all). On the other hand, looking\nat the ref tips would probably be dominated by actually traversing the\ncommits in most cases. Of course one could come up with a pathological\ncase pretty easily (tons of refs, and people asking for submodules at\ntip commits).\n\nSo I do think there are cases where the optimization would help, but I\nstill not sure how much. If it's an optional bit of the design, we at\nleast have the option of just not generating if it turns out not to be\nuseful. My only concern would be if we make other protocol sacrifices or\ncomplications to include it.\n\n-Peff\n"},{"id":"325444","messageId":"20170802172844.pkwjovofrzarjrgn@sigill.intra.peff.net","threadId":"46487","inReplyTo":"CAJo=hJu1rud5pEZ93HDty1qyaCOHmwn89aEvPFe2ER0JD1ExwQ@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-08-02T17:28:45Z","receivedAt":"2017-08-02T17:28:51Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 02, 2017 at 08:17:29AM -0700, Shawn Pearce wrote:\n\n> > Just peeking at torvalds/linux, we have some objects with ~35K refs\n> > pointing to them (e.g., the v2.6.11 tag).\n> \n> Oy. I'll bet that every occurrence winds up in its own block due to\n> the layout of the namespace, and so the obj block list needs 35k\n> varint pointers. That requires a larger block size if it has any\n> chance of fitting into the reftable format.\n> \n> Another option is disable the obj table for these shared-object repos.\n> Its an optional part of the format and can be omitted if the reader\n> isn't likely to need to lookup by SHA-1, or is willing to pay the\n> brute force cost of scanning every ref.\n\nYeah, sorry, I meant to write a few more paragraphs. I think refusing to\ngenerate the object table for these repos would be OK. We don't serve\nany user-facing operations out of them directly[1].\n\nI'm also open to the argument that they're simply insane. Most of the\ntime we don't need them to be a real repository at all. They could exist\nas a bare \"objects/\" directory. It's only at repack time that we\nactually need to know which objects are reachable[2], so we could\ndo a special repack that generates the list on the fly from the child\nrepositories.\n\n-Peff\n\n[1] We actually disable the \".have\" advertisements, because the cost of\n showing all of the shared-storage ref tips is too high. One thing\n I'd like to do is be able to advertise a subset of the alternate\n refs (if you're a fork of torvalds/linux, then share _just_ the refs\n from there). But with the current ref code, I can't even ask for a\n subset of the refs without paying the cost to walk all of them.\n That's one of the things I'd like to build on top of the mmap'd\n packed-refs solution (and naturally would work with reftables, too).\n\n[2] It's a bit more complicated than just knowing the list of reachable\n objects. We also want to know which ones are reachable from which\n fork, as we do some trickery to avoid creating deltas across forks.\n So we really do want the whole ref-list, and not something like a\n de-duped set of reachable tips. I don't think that makes a\n difference for anything we're discussing here, but just a bit of\n trivia in case somebody is thinking about the shared-storage problem\n space.\n"},{"id":"325473","messageId":"xmqqh8xpsq9c.fsf@gitster.mtv.corp.google.com","threadId":"46487","inReplyTo":"CAJo=hJv7scc1L0_MdRkFeLAJGjYm2UkTFNOgj2e4+9Zj7KSiiQ@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-08-02T19:50:39Z","receivedAt":"2017-08-02T19:50:46Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> ### Layout\n>\n> The `$GIT_DIR/refs` path is a file when reftable is configured, not a\n> directory. This prevents loose references from being stored.\n>\n> A collection of reftable files are stored in the `$GIT_DIR/reftable/`\n> directory:\n>\n> 00000001_UF4paF\n> 00000002_bUVgy4\n>\n> where reftable files are named by a unique name such as produced by\n> the function:\n>\n> mktemp \"${update_index}_XXXXXX\"\n>\n> The stack ordering file is `$GIT_DIR/refs` and lists the current\n> files, one per line, in order, from oldest (base) to newest (most\n> recent):\n>\n> $ cat .git/refs\n> 00000001_UF4paF\n> 00000002_bUVgy4\n>\n> Readers must read `$GIT_DIR/refs` to determine which files are\n> relevant right now, and search through the stack in reverse order\n> (last reftable is examined first).\n>\n> Reftable files not listed in `refs` may be new (and about to be added\n> to the stack by the active writer), or ancient and ready to be pruned.\n\nI like the general idea, what the file format can represent and how\nit does so, but I am a bit uneasy about how well this \"stacked\" part\nwould work for desktop clients. The structure presented here is for\noptimizing the \"we want to learn about many (or all) refs\" access\npattern, which probably matters a lot on the server implementations,\nbut I do not feel comfortable without knowing how much it penalizes\n\"I want the current value of this single ref\" access pattern.\n\nWith the traditional \"packed-refs plus loose\" layout, no matter how\nmany times a handful of selected busy refs are updated during the\nday, you'd need to open at most two files to find out the current\nvalue of a single ref (admittedly, the accessing of the second file,\nafter we realize that there is no loose one, would be very costly).\nIf you make a few commits on a topic branch A, then build a 100\ncommit series on top of another topic branch B, finding the current\nvalue of A is still one open and read of refs/heads/A.\n\nWith the reftable format, we'd need to open and read all 100\nincremental transactions that touch branch B before realizing that\nnone of them talk about A, and read the next transaction file to\nfind the current value of A. To keep this number low, we'd need\nquite a frequent compaction.\n\nWe can just declare that reftable format is not for desktop clients\nbut for server implementations where frequent compaction would not\nbe an annoyance to the users, but I'd wish we do not have to.\n\n\n\n"},{"id":"325474","messageId":"CAGZ79kb5UjxQFpQWy-muCwkuQsmuxQcKfs4f5HGenGSb+SiOhw@mail.gmail.com","threadId":"46487","inReplyTo":"CAJo=hJv7scc1L0_MdRkFeLAJGjYm2UkTFNOgj2e4+9Zj7KSiiQ@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-08-02T19:54:39Z","receivedAt":"2017-08-02T19:54:47Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"> ### Ref block format\n>\n> A ref block is written as:\n>\n> 'r'\n> uint24( block_len )\n> ref_record+\n> uint32( restart_offset )+\n> uint16( restart_count )\n> padding?\n>\n\nSo I learned that your current writer is a two block pass,\ni.e. the block is first written into memory and then once\nthe block looks complete it is written out to disk.\n\nThis would allow us to shuffle the data around during\nthe actual out-to-disk-phase, such as this:\n\n 'r'\n uint24( restart_count )\n uint32( restart_offset )+\n ref_record+\n ref_record_endmarker\n padding?\n\n(A) In nearby emails we discussed to have the restart offsets\nto be 24 bit, but now they are 32-bit aligned to the start of a block\nso we could keep them 32 bit for simplicity of reading.\n\n(B) Note how there is no block_len encoding, which was originally\nonly needed to lookup the position of restart_count. (so even for that\nwe could rename it to padding_len, such that the position of\nrestart_count can be decoded easily)\n\nWe no longer need the block_len as the restart_count comes right\nafter the 'r'.\n\nInstead we'll have a ref_record_endmarker that reads as a ref\nwith both prefix and suffix to '0', type deletion (such that there is\nno further cost). The end marker would only need two '0's, which\nmakes it indistinguishable from padding.\n"},{"id":"325476","messageId":"20170802202850.y2gja3qnpw35olty@sigill.intra.peff.net","threadId":"46487","inReplyTo":"xmqqh8xpsq9c.fsf@gitster.mtv.corp.google.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-08-02T20:28:50Z","receivedAt":"2017-08-02T20:28:58Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 02, 2017 at 12:50:39PM -0700, Junio C Hamano wrote:\n\n> With the traditional \"packed-refs plus loose\" layout, no matter how\n> many times a handful of selected busy refs are updated during the\n> day, you'd need to open at most two files to find out the current\n> value of a single ref (admittedly, the accessing of the second file,\n> after we realize that there is no loose one, would be very costly).\n> If you make a few commits on a topic branch A, then build a 100\n> commit series on top of another topic branch B, finding the current\n> value of A is still one open and read of refs/heads/A.\n> \n> With the reftable format, we'd need to open and read all 100\n> incremental transactions that touch branch B before realizing that\n> none of them talk about A, and read the next transaction file to\n> find the current value of A. To keep this number low, we'd need\n> quite a frequent compaction.\n\nI think this is where compaction cleverness can come in.\n\nOne relatively easy optimization would be to note when the most recent\nreftable contains a subset of the refs we are currently updating (and\nthe obvious string-of-updates to a single ref falls under that), and do\na \"quick\" compaction where we simply drop[1] that reftable in favor of\nours. That compaction is essentially free, because we know those entries\naren't valid anymore anyway.\n\nI'm actually not sure if this is a strict \"drop\", though, because of\nreflogs. If the reflog is written into the same file as the ref update,\nthen you'd need to roll its entry into your new update, too. But see\nbelow anyway.\n\nFor more complicated cases, there's some cleverness you can do with\nsmall on-the-fly compactions. Even if there are entries in the last few\nreftables that we're not currently updating, it's pretty cheap to roll a\nfew of them up into our new reftable if it lets us drop some\nintermediate reftables. E.g., if we're writing a new reftable with a 4K\nblock size but only have 100 bytes of new data, we're probably best to\nroll up a previous 500-byte reftable.\n\nThat one's an obvious optimization because we know that the filesystem\nis going to make us spend 4K either way, so rounding up to that is\ngenerally free-ish.\n\nWhat's less obvious is when we should roll up a bunch of 4K tables into\none (let's say) 32K table. I think there's a formula for doing this\ngeometrically so that the amortized cost of writing stays under a\ncertain bound (linear?). But I haven't thought it through (or looked it\nup); I was hoping Shawn had already done so and could dump that wisdom\non us.\n\n> We can just declare that reftable format is not for desktop clients\n> but for server implementations where frequent compaction would not\n> be an annoyance to the users, but I'd wish we do not have to.\n\nYeah, I agree we should avoid that. I would love to eventually kill off\nthe loose/packed backend (or at least make it historical and read-only,\nso that a reasonable response to people complaining about its races and\nlack of atomicity is \"please upgrade to reftables\").\n\n-Peff\n"},{"id":"325498","messageId":"xmqqd18dqv0y.fsf@gitster.mtv.corp.google.com","threadId":"46487","inReplyTo":"xmqqh8xpsq9c.fsf@gitster.mtv.corp.google.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-08-03T01:50:37Z","receivedAt":"2017-08-03T01:50:54Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> I like the general idea, what the file format can represent and how\n> it does so, but I am a bit uneasy about how well this \"stacked\" part\n> would work for desktop clients.\n\nTwo more random things before I forget.\n\n * I understand that you would want to allow both a ref \"ref/D\" and\n \"ref/D/F\" to appear in the same reftable file. A refname is an\n uninterpreted sequence of bytes and refnames are sorted in the\n table.\n\n Would it benefit us if we define the sort order of bytes slightly\n different from the ASCII order, so that a slash '/' sorts between\n NUL '\\000' and SOH '\\001', which is the order we should have used\n when storing the entries in the index?\n\n * Even though readers can continue accessing, starting from the\n $GIT_DIR/refs, without locking and get consistent views, any\n transaction that groups one or more ref updates would need to\n take a global lock on $GIT_DIR/refs file. \n\n Would it become a problem in a busy repository?\n"},{"id":"325499","messageId":"CAJo=hJuWc-hLyTgtdO_AYjUhvRWFSY70bBPEgNtygs5ojJcKyQ@mail.gmail.com","threadId":"46487","inReplyTo":"xmqqd18dqv0y.fsf@gitster.mtv.corp.google.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-08-03T02:21:11Z","receivedAt":"2017-08-03T02:21:38Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Wed, Aug 2, 2017 at 6:50 PM, Junio C Hamano wrote:\n> Junio C Hamano writes:\n>\n>> I like the general idea, what the file format can represent and how\n>> it does so, but I am a bit uneasy about how well this \"stacked\" part\n>> would work for desktop clients.\n>\n> Two more random things before I forget.\n>\n> * I understand that you would want to allow both a ref \"ref/D\" and\n> \"ref/D/F\" to appear in the same reftable file. A refname is an\n> uninterpreted sequence of bytes and refnames are sorted in the\n> table.\n>\n> Would it benefit us if we define the sort order of bytes slightly\n> different from the ASCII order, so that a slash '/' sorts between\n> NUL '\\000' and SOH '\\001', which is the order we should have used\n> when storing the entries in the index?\n\nI'm not really with that. It complicates the compare routine, and\nmakes the data in reftable sorted differently than we announce in the\nwire protocol. That cuts off any sort of optimizations we were\nconsidering at $DAY_JOB to plumb the wire protocol code in JGit closer\nto reftable code so that a large advertisement is more or less just\ndumped straight from reftable to the wire protocol with only minimal\nformatting changes.\n\n> * Even though readers can continue accessing, starting from the\n> $GIT_DIR/refs, without locking and get consistent views, any\n> transaction that groups one or more ref updates would need to\n> take a global lock on $GIT_DIR/refs file.\n>\n> Would it become a problem in a busy repository?\n\nPotentially yes. Writers may need to use a randomized exponential\nbackoff while trying to acquire the lock. For big application servers,\nI recommended wrapping the file IO locking code with an application\nserver managed lock + fair wait queue. This is fairly straightforward\nfor JGit to implement within Gerrit Code Review.\n\nI'm not really sure how one could safely do the same thing with\ngit-core. Its certainly not going to be portable or safe on NFS if we\ntried to do anything fancy with flock(2), fcntl(F_SETLKW), or\nsemop(2).\n"},{"id":"325500","messageId":"xmqq8tj1qswl.fsf@gitster.mtv.corp.google.com","threadId":"46487","inReplyTo":"CAJo=hJuWc-hLyTgtdO_AYjUhvRWFSY70bBPEgNtygs5ojJcKyQ@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-08-03T02:36:26Z","receivedAt":"2017-08-03T02:36:34Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> On Wed, Aug 2, 2017 at 6:50 PM, Junio C Hamano wrote:\n> ...\n>> Would it benefit us if we define the sort order of bytes slightly\n>> different from the ASCII order, so that a slash '/' sorts between\n>> NUL '\\000' and SOH '\\001', which is the order we should have used\n>> when storing the entries in the index?\n>\n> I'm not really with that. It complicates the compare routine, and\n> makes the data in reftable sorted differently than we announce in the\n> wire protocol.\n\nFair enough. It was not like I had some operations in mind that\nwould benefit from such a sort order (i.e. walking two of these\nthings in parallel and merging them, which would have been the case\nfor the index when we walk it together with one or more trees); if\nthere is no such operation that benefit, there is no reason to try\nto be clever here.\n\n>> * Even though readers can continue accessing, starting from the\n>> $GIT_DIR/refs, without locking and get consistent views, any\n>> transaction that groups one or more ref updates would need to\n>> take a global lock on $GIT_DIR/refs file.\n>>\n>> Would it become a problem in a busy repository?\n> ...\n>\n> I'm not really sure how one could safely do the same thing with\n> git-core. Its certainly not going to be portable or safe on NFS if we\n> tried to do anything fancy with flock(2), fcntl(F_SETLKW), or\n> semop(2).\n\nYes.\n\nAnd for public record, another thing we privately discussed was that\nwe currently do not know if we would want to make this design mesh\nwell with the use of multiple worktrees (IIUC, HEAD and things\noutside refs/, and refs/bisect/, need to be per- worktree, while\nothers are to be common), and if so how.\n"},{"id":"325572","messageId":"CAMy9T_G5xorPGp=5=p_ku3RhB1E-c9+4mEgYhbyAhLdc1V=JBg@mail.gmail.com","threadId":"46487","inReplyTo":"CAJo=hJv=zJvbzfAZwspxECXrnBJR4XfJbGZegsNUCx=6uheO2Q@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-08-03T18:38:27Z","receivedAt":"2017-08-03T18:38:37Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On Tue, Aug 1, 2017 at 7:38 PM, Shawn Pearce wrote:\n> On Tue, Aug 1, 2017 at 6:51 PM, Michael Haggerty wrote:\n>> On Tue, Aug 1, 2017 at 4:27 PM, Shawn Pearce wrote:\n>>> On Mon, Jul 31, 2017 at 11:41 PM, Michael Haggerty wrote:\n>>>> [...]\n>>> A couple of other notes about your contrasting design:\n>>>\n>>>> elif chunk_type == INDEX {\n>>>> chunk_length : varint\n>>>\n>>> Using a varint for the chunk length made for a complicated reader.\n>>> JGit doesn't have the luxury of mmap to access the file, so we have to\n>>> allocate a byte[] and read data from a file descriptor to do anything\n>>> fancy like decoding a varint. For my experiment I wound up just\n>>> hardcoding the IO to read 1k or 4k from whatever address.\n>>>\n>>> A \"real\" implementation would likely prefer to read a fixed width\n>>> field here such that chunks have a 3 byte header (1 byte chunk_type, 2\n>>> byte chunk_length), and then issue a second read to acquire the rest\n>>> of the chunk. Given that encoding a chunk length of 1024 or 4096 both\n>>> requires 2 bytes of varint, its always going to be 2 bytes in your\n>>> design anyway. With the way chunks are scanned, I don't think you want\n>>> chunks as large as 16k, which would have caused the varint to go to 3\n>>> bytes (but still fits in a fixed 2-byte chunk_length).\n>>\n>> That's a good point for INDEX and OBJS_INDEX blocks. Though for REFS\n>> blocks that include reflogs, the block size has to be large enough to\n>> hold the whole reflog for a reference, which can be arbitrarily large.\n>> (Maybe this is a weakness of the design?)\n>\n> Gah. I missed that part about the whole reflog needing to fit in the\n> same chunk when I wrote the quoted text above. That is a pretty big\n> downside for very busy refs.\n>\n> Even when you isolate logs into their own file, the reflog for a busy\n> ref could be huge. A naive reader would want to \"page in\" the entire\n> chunk_length before parsing. That isn't tenable if the reflog for a\n> busy ref was say 50 MiB. It complicates the reader more. My reftable\n> proposal deals with this by breaking the log up with its special key\n> structure.\n>\n> Requiring the entire reflog of a single ref to fit into a single chunk\n> does seem to have its downsides.\n\nI was assuming that readers would uncompress the data streamily, in\nwhich case I don't think that it would be much of a problem: reflogs\nare usually read either in their entirety, or just the most recent few\nentries are read, either of which could be done efficiently despite\nthe whole reflog being in a single zlib-compressed blob. If streamy\nreading is thought to be too complicated for readers, it wouldn't be a\nbig deal to add a `log_type` of `REFLOG_COMPRESSED_SEGMENTED` and put\nthe entries into multiple, smaller zlib-compressed chunks.\n\n>> OBJS blocks can also be\n>> unbounded in size if very many references point at the same object,\n>> thought that is perhaps only a theoretical problem.\n>\n> Gah, I missed that in reftable. The block id pointer list could cause\n> a single object id to exceed what fits in a block, and that will cause\n> the writer to fail unless its caller sets the block size larger. I\n> basically assumed this overflow condition is very unlikely, as its not\n> common to have a huge number of refs pointing to the same object.\n\nGiven what Peff pointed out, let's just leave this as a varint for OBJS blocks.\n\n>>>> elif chunk_type == OBJS_INDEX {\n>>>> chunk_length : varint\n>>>>\n>>>> # The offset, relative to the start of this chunk, of the\n>>>> # chunk containing the next level of the obj index, for each\n>>>> # of the possible \"next\" bytes in the SHA-1, or zero if there\n>>>> # are no references with the given next byte.\n>>>> child_offset : varint * 256\n>>>\n>>> This is space saving and cute, but kind of annoying. If it was fixed\n>>> width 32 bit you can address up to 4G away from this chunk's address,\n>>> and you can directly jump to the byte of interest. By being varints\n>>> you do save a little space, as most files will probably only need 3\n>>> byte varints, and the 0s do collapse down to 1 byte, but you have to\n>>> linearly walk the list to find any specific byte.\n>>\n>> The reason I used varint here was mostly because I expect the lowest\n>> level of the OBJS_INDEX to be placed close to the OBJS chunks that it\n>> refers to; hopefully within a 2-byte varint. Let me consider more\n>> carefully whether that is realistic...\n>\n> Ah, ok. So you were expecting the writer to interleave OBJS and\n> OBJS_INDEX chunks, with the OBJS_INDEX appearing every ~256 OBJS\n> chunks. And then storing the next level of OBJS_INDEX consecutively.\n>\n> I think your math is still wrong about the lowest level OBJS_INDEX\n> needing only 2-byte varint for child_offset. Given a 1k chunk size,\n> you still have to address backwards about 256k, which requires a\n> 3-byte varint.\n\nI think that you would want the lowest OBJS_INDEX to be mostly\npopulated, meaning that the next level nodes in the tree would mostly\nonly have zero or one entry. The true distribution [1] would be close\nto a Poisson distribution with a mean of `λ ≲ 1` (where λ is basically\nthe filling factor), which looks like\n\n P(λ, n) = λⁿ exp(-λ) / n!\n\nFor `λ = 1`, that looks like\n\n P(1, 0) = 36.8%\n P(1, 1) = 36.8%\n P(1, 2) = 18.4%\n P(1, 3) = 06.1%\n P(1, 4) = 01.5%\n P(1, 5) = 00.3%\n P(1, 6) = 00.1%\n\nso almost all OBJS chunks would have fewer than five entries. And in\nfact the mean number of entries would be `λ`. So the total size of the\nOBJS chunks pointed at by a given OBJS_INDEX chunk should be something\nlike\n\n 256 * λ * sizeof(OBJS chunk) ≲ 1800 bytes.\n\n[1] This is assuming randomness of SHA-1s, which AFAIK is normally a\ngood approximation. It is of course possible that somebody would try\nto grief the system by creating a repository with lots of objects that\nhave similar SHA-1 prefixes, but I think the worst result would be\nthat some operations would scale like O(number of references) rather\nthan O(256), which isn't all that pathological, and the distinct\npattern would be clear evidence of malice that would justify banning\nthe user.\n\n> Given the uniform distribution of SHA-1, I think you still wind up\n> with most of the OBJS_INDEX populated. E.g. in my 866k ref/865k obj\n> example the unique object abbreviation is 6 raw bytes. The OBJS chunk\n> storing 2 bytes means we have 4 levels of OBJS_INDEX to cover the\n> first 4 bytes. That leaves ~844 obj_records in each OBJS chunk. If\n> those are 7 bytes/obj_record, the OBJS chunk is ~5.7 KiB.\n>\n> Forcing the OBJS chunk to stay under say 4 KiB will absolutely cause a\n> lot more holes in the OBJS_INDEX levels.\n\nI was thinking more about how to store the objects lookup table. Let's\nassume that we combine the lowest-level OBJS_INDEX chunk along with\nthe OBJS chunks that it points to into a new OBJS_LEAF chunk. I think\nthe goals are as follows:\n\n* The lowest OBJS_LEAF nodes should have a filling factor of\napproximately `λ = 1`.\n* It should be possible to adjust the size of the lowest OBJS_LEAF\nnodes based on the preferred read size. (This might mean that all of\nthe OBJS_LEAF nodes referred to by the next-higher node in the tree\nfit together with it in a single 64k block.)\n* That higher-level nodes also can be packed efficiently in blocks of\nroughly the preferred read size.\n* That false positives be the exception. If we ask a higher-level\nreftable whether it might contain a reference to $sha1, it would be\nnice to be able to get a \"no\" answer without having to read actual\nreferences. I think that is an argument why we *don't* want to store\nonly the largest unique prefix of the contained SHA-1s. I think we\nwant to *always* store enough bits of SHA-1 prefix to make the\nreferred-to SHA-1s represent only a small fraction (say, 1/256th) of\nthe total prefix space. E.g., if references in a particular repository\npoint to 2ⁿ distinct SHA-1s, then we'd want the prefix to include\nsomething like n+8 bits.\n\nTo achieve these goals, I think we it would be best to make the number\nof bits used in each level of the tree be variable rather than\nhard-coded to be 8. By changing the radix of different levels of the\ntree, I think you could arrange for block sizes that are optimal for\nyour filesystem at the same time that you ensure that the OBJS_LEAF\nnodes have the desired filling factor.\n\nIf anybody's interested, I can flesh out these ideas more next week\nwhen I have time.\n\n>> Peff and I discussed off-list whether the lookup-by-SHA-1 feature is\n>> so important in the first place. Currently, all references must be\n>> scanned for the advertisement anyway,\n>\n> Not really. You can hide refs and allow-tip-sha1 so clients can fetch\n> a ref even if it wasn't in the advertisement. We really want to use\n> that wire protocol capability with Gerrit Code Review to hide the\n> refs/changes/ namespace from the advertisement, but allow clients to\n> fetch any of those refs if they send its current SHA-1 in a want line\n> anyway.\n>\n> So a server could scan only the refs/{heads,tags}/ prefixes for the\n> advertisement, and then leverage the lookup-by-SHA1 to verify other\n> SHA-1s sent by the client.\n>\n>> so avoiding a second scan to vet\n>> SHA-1s received from the client is at best going to reduce the effort\n>> by a constant factor. Do you have numbers showing that this\n>> optimization is worth it?\n>\n> No, but I don't think I need to do much to prove it. My 866k ref\n> example advertisement right now is >62 MiB. If we do what I'm\n> suggesting in the paragraphs above, the advertisement is ~51 KiB.\n>\n>> OTOH a mythical protocol v2 might reduce the need to scan the\n>> references for advertisement, so maybe this optimization will be more\n>> helpful in the future?\n>\n> Yes, I'm hopeful we can get a v2 protocol built on the work Jonathan\n> Tan is doing, and switch the advertisement around to \"client speaks\n> first\", so that we can be smarter on the server about which refs are\n> read and sent. That is a long way off, lets say 3-5 years before its\n> really common in clients.\n\nMy takeaway from the discussion about whether object lookup is an\nimportant feature is that it should very much be optional, and by\nextension we should probably leave room for other optional extensions\nin the file format.\n\n> [...]\n>> That's what I was thinking. But I've yet to hear anybody complain\n>> about missing reflogs for symrefs if the underlying reference is\n>> updated directly, so maybe we should just leave that \"problem\"\n>> unsolved. It is certainly simpler and less brittle not to have to keep\n>> backreferences like these in sync with the forward references.\n>\n> Yup, that is my take on it, and why I didn't try to put this into\n> reftable drafts, even though it was discussed between us on the list\n> in earlier messages.\n\nYes, let's forget the idea of including backreferences from refs to\nthe symrefs that refer to them.\n\nMichael\n"},{"id":"325597","messageId":"CAJo=hJtXaDtouGU0noE0ueHJYr872OTfSt5Y9SmQ5xAA7g_CrA@mail.gmail.com","threadId":"46487","inReplyTo":"20170802202850.y2gja3qnpw35olty@sigill.intra.peff.net","subject":"Re: reftable [v4]: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-08-03T22:17:37Z","receivedAt":"2017-08-03T22:18:05Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Wed, Aug 2, 2017 at 1:28 PM, Jeff King wrote:\n> On Wed, Aug 02, 2017 at 12:50:39PM -0700, Junio C Hamano wrote:\n>\n>> With the traditional \"packed-refs plus loose\" layout, no matter how\n>> many times a handful of selected busy refs are updated during the\n>> day, you'd need to open at most two files to find out the current\n>> value of a single ref (admittedly, the accessing of the second file,\n>> after we realize that there is no loose one, would be very costly).\n>> If you make a few commits on a topic branch A, then build a 100\n>> commit series on top of another topic branch B, finding the current\n>> value of A is still one open and read of refs/heads/A.\n>>\n>> With the reftable format, we'd need to open and read all 100\n>> incremental transactions that touch branch B before realizing that\n>> none of them talk about A, and read the next transaction file to\n>> find the current value of A. To keep this number low, we'd need\n>> quite a frequent compaction.\n>\n> I think this is where compaction cleverness can come in.\n>\n> One relatively easy optimization would be to note when the most recent\n> reftable contains a subset of the refs we are currently updating (and\n> the obvious string-of-updates to a single ref falls under that), and do\n> a \"quick\" compaction where we simply drop[1] that reftable in favor of\n> ours. That compaction is essentially free, because we know those entries\n> aren't valid anymore anyway.\n>\n> I'm actually not sure if this is a strict \"drop\", though, because of\n> reflogs. If the reflog is written into the same file as the ref update,\n> then you'd need to roll its entry into your new update, too. But see\n> below anyway.\n>\n> For more complicated cases, there's some cleverness you can do with\n> small on-the-fly compactions. Even if there are entries in the last few\n> reftables that we're not currently updating, it's pretty cheap to roll a\n> few of them up into our new reftable if it lets us drop some\n> intermediate reftables. E.g., if we're writing a new reftable with a 4K\n> block size but only have 100 bytes of new data, we're probably best to\n> roll up a previous 500-byte reftable.\n>\n> That one's an obvious optimization because we know that the filesystem\n> is going to make us spend 4K either way, so rounding up to that is\n> generally free-ish.\n\nYes. I was trying to propose exactly this in the first draft of\nreftable, but someone on list didn't like the idea of an update\ntransaction stalling to perform a compaction, so I took that text out\nin later drafts.\n\nWhat I had envisioned is exactly what you mention; an update of\nrefs/heads/B that is just going to overlay another small reftable that\nalso recently updated refs/heads/B should just replace that table\ninstead of pushing onto the stack. Or if the combined top of stack +\nnew table is under 4K, they should just combine together instead of\npushing a new table onto the stack.\n\n\n> What's less obvious is when we should roll up a bunch of 4K tables into\n> one (let's say) 32K table. I think there's a formula for doing this\n> geometrically so that the amortized cost of writing stays under a\n> certain bound (linear?). But I haven't thought it through (or looked it\n> up); I was hoping Shawn had already done so and could dump that wisdom\n> on us.\n\nSorry, I haven't done that. :)\n\n\n>> We can just declare that reftable format is not for desktop clients\n>> but for server implementations where frequent compaction would not\n>> be an annoyance to the users, but I'd wish we do not have to.\n>\n> Yeah, I agree we should avoid that. I would love to eventually kill off\n> the loose/packed backend (or at least make it historical and read-only,\n> so that a reasonable response to people complaining about its races and\n> lack of atomicity is \"please upgrade to reftables\").\n\nI'd also really like reftable to be useful for \"desktop clients\". I'd\nconsider it something of a design failure if the format was horribly\nunsuitable in some way to that use case. I think the small compactions\nduring updates will be essential to supporting the typical developer's\nworkflow.\n"},{"id":"325600","messageId":"CAJo=hJvNgX06gkXp2Vsx=cSkcxRO9aRzOit6vvi4fqL3QeDsEg@mail.gmail.com","threadId":"46487","inReplyTo":"CAMy9T_G5xorPGp=5=p_ku3RhB1E-c9+4mEgYhbyAhLdc1V=JBg@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-08-03T22:26:22Z","receivedAt":"2017-08-03T22:26:48Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Thu, Aug 3, 2017 at 11:38 AM, Michael Haggerty wrote:\n> On Tue, Aug 1, 2017 at 7:38 PM, Shawn Pearce wrote:\n>> On Tue, Aug 1, 2017 at 6:51 PM, Michael Haggerty wrote:\n>>> On Tue, Aug 1, 2017 at 4:27 PM, Shawn Pearce wrote:\n>>>> On Mon, Jul 31, 2017 at 11:41 PM, Michael Haggerty wrote:\n>>>>> [...]\n>>>> A couple of other notes about your contrasting design:\n>>>>\n...\n>>> OBJS blocks can also be\n>>> unbounded in size if very many references point at the same object,\n>>> thought that is perhaps only a theoretical problem.\n>>\n>> Gah, I missed that in reftable. The block id pointer list could cause\n>> a single object id to exceed what fits in a block, and that will cause\n>> the writer to fail unless its caller sets the block size larger. I\n>> basically assumed this overflow condition is very unlikely, as its not\n>> common to have a huge number of refs pointing to the same object.\n>\n> Given what Peff pointed out, let's just leave this as a varint for OBJS blocks.\n\nWe discussed this at $DAY_JOB yesterday. We realized that if an obj\nblock has that many ref pointers present, it may be more efficient for\na reader to scan all references instead of chasing those pointers\nindividually. Latest draft of reftable now omits the ref pointer list\nin an obj block if it exceeds the obj block size, which only occurs\nwhen a high proportion of the ref blocks contain that SHA-1.\n"},{"id":"325602","messageId":"CAMy9T_EU6hPbnnB72ouRAd0yNvWn6_Ef8Bh2iPxChpmDt1qmFw@mail.gmail.com","threadId":"46487","inReplyTo":"CAJo=hJvNgX06gkXp2Vsx=cSkcxRO9aRzOit6vvi4fqL3QeDsEg@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-08-03T22:48:26Z","receivedAt":"2017-08-03T22:48:36Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"I've revised the blockless reftable proposal to address some feedback:\n\n* Don't omit `prefix_len` for the first ref and first child in a\nblock. It doesn't save much but makes the reader more complicated.\n* Get rid of `symref_target` (the backlink from a reference to the\nsymlink(s) that point at it). It is a solution to a problem that is\nnot worth solving.\n* Get rid of the `SYMREF_PEELED` type. It is impossible to maintain\nthis field affordably without `symref_target`, but it seems fragile\nand unnecessary anyway.\n* Add a way to mark a reflog entry \"deleted\" without having to rewrite\neverything. This is mostly meant to deal with `refs/stash`.\n* Define an extension mechanism.\n* Define the SHA-1 → object mapping as an extension rather than as\npart of the main spec. My gut feeling is that it will never be\nimplemented for git-core.\n* Revise how the SHA-1 → object mapping works:\n * Merge the bottommost OBJ_INDEX node with the old OBJ nodes to\nform a new OBJ_LEAF node.\n * Allow the branching factor of each node to be specified\nindependently (to allow the node sizes to be matched more closely to\nthe preferred read sizes).\n* Rename some fields for clarity.\n\nI currently lean towards the opinion that we should store pseudorefs\n(like `FETCH_HEAD`, `MERGE_HEAD` *outside of* reftables, except for\n`HEAD` (which behaves more like a normal reference, which is\nconsidered for reachability, and for which we want to retain reflogs),\nwhich we should store *in* reftables.\n\nI don't talk at all about how individual reftable files are stacked\ntogether, because that is pretty much unchanged from Shawn's proposal.\nThe only thing I would suggest is to give the reftable files names\nthat indicate whether they include reference values, reflogs, or both,\nso that readers can tell from the table of contents which files they\nhave to open.\n\nThe new proposal follows:\n\nDefinitions:\n\nVarint encoding is similar to the unsigned varint encoding used for\nprotocol buffers; i.e., a little-endian base-128 format where the most\nsignificant bit is used to indicate that another byte is coming.\nDecoding is as follows:\n\n```\nval = *ptr & 0x7f\nwhile (*ptr++ & 0x80) {\n val = (val << 7) | (*ptr & 0x7f)\n}\n```\n\nStrings are usually encoded using `varstr` encoding, which is the same\nas how strings are encoded in protocol buffers. A `varstr` consists of\na `varint` length followed by the specified number of bytes holding\nthe contents of the string. `varstr` strings are not intrinsically\nNUL-terminated.\n\nThe `chunk_length` fields encode the total size of the containing\nchunk, including its `chunk_type` field.\n\n```\nvarstr(s) = {\n varint(strlen(s))\n s\n}\n```\n\n```\nreftable = {\n header\n [chunk | padding]*\n footer\n}\n\nheader = {\n 'REFT'\n uint8( version_number = 1 )\n\n # The length of the whole header, in bytes:\n header_length : uint16\n\n metadata\n}\n\nfooter = {\n 'REFT'\n uint8( version_number = 1 )\n metadata\n\n # The length of the whole footer, in bytes:\n footer_length : uint16\n\n uint32(CRC-32 of previous part of footer)\n}\n\nmetadata = {\n # if `contains_values` is false, this file *must not* contain any\n # reference values; i.e., `value_type` must always be `NO_VALUE`.\n contains_values : bool\n\n # if `contains_logs` is false, this file *must not* contain any\n # reflog entries; i.e., `log_type` must always be `NO_REFLOG`.\n\n contains_logs : bool\n\n # If `offsets_negative` is true, then all `*_offset` fields point\n # backwards in the file; i.e., the corresponding varint value is\n # negated before use.\n offsets_negative : bool\n\n # update_index is a counter that is incremented by one for each\n # atomic reference update affecting a stack of reftables (even if\n # the reference update changes multiple references). Counting\n # starts at 1 (0 is used as a special value). The following two\n # fields indicate that this reftable file covers update_indexes in\n # the range\n #\n # min_update_index < update_index <= max_update_index\n #\n # , with the possible exception of LOG_DELETED entries.\n\n max_update_index : uint64\n min_update_index : uint64\n\n # To accomodate systems that have to write files serially, the\n # following two entries can be zeroed out in the header to tell\n # the reader that it has to read the corresponding values from the\n # footer.\n\n # The file offset of the chunk containing the root of the\n # reference tree:\n ref_root_chunk_addr : uint64\n\n # This space can be used to add extensions to the file format. It\n # is included in `header_length` / `footer_length` to allo older\n # readers to skip over any extensions that it doesn't understand.\n extension*\n}\n\nextension = {\n # The name of the extension:\n extension_name : varstr\n\n # The address of the first block of data associated with the extension:\n extension_root_chunk_addr : uint64\n}\n\nchunk = {\n # The `chunk_type` determines how to interpret the payload, and\n # influences how to compute its length (which is needed to advance\n # to the next chunk).\n\n chunk_type : enum PAD_BYTE | PADDING\n | INDEX | REFS\n | EXTENSION\n\n if chunk_type == PAD_BYTE {\n # This chunk type can be used to add a single byte of padding,\n # which would otherwise be impossible because a `PADDING`\n # chunk requires a minimum of two bytes.\n }\n elif chunk_type == PADDING {\n # A form of padding that's cheaper to skip over than\n # `PAD_BYTE`.\n\n # The total number of bytes in this chunk, including\n # `chunk_type`. The contents will otherwise be ignored:\n\n chunk_length : varint\n }\n elif chunk_type == INDEX {\n chunk_length : varint\n children : {\n # Length of prefix being carried over from the previous\n # record (always zero for the first child in a chunk):\n prefix_len : varint\n suffix : varstr\n index_payload\n }*\n }\n elif chunk_type == REFS {\n chunk_length : varint\n refs : {\n # Length of prefix being carried over from the previous\n # record (always zero for the first reference in a chunk):\n prefix_len : varint\n suffix : varstr\n ref_payload\n }*\n }\n elif chunk_type == EXTENSION {\n chunk_length : varint\n # Additional data may be present here. It should be ignored by\n # readers that don't know about the extension.\n }\n}\n\nindex_payload = {\n # The number of bytes from the begining of this chunk to the child\n # chunk. If child_offset is zero, then there are no entries in\n # this reftable whose refnames start with the specified prefix.\n #\n # The child pointed at is of type INDEX (another index chunk\n # containing the next finer level of detail) or of type REFS. In\n # either case, the first record in the pointed-to chunk must have\n # `prefix_len == 0` and contain the entire key as `suffix`.\n child_offset : varint\n}\n\nref_payload = {\n value_type : enum NO_VALUE\n | DELETED\n | VALUE | VALUE_PEELED\n | SYMREF\n | SPECIAL\n log_type : enum NO_REFLOG | REFLOG | REFLOG_COMPRESSED\n\n if value_type == NO_VALUE {\n # This type is used if we need to store a reflog entry but\n # have no reference value to store in this file.\n }\n elif value_type == DELETED {\n # This type indicates that the reference has been deleted,\n # regardless of what any reftables deeper in the stack claim.\n }\n elif value_type == VALUE {\n # This is a normal (non-symbolic) reference.\n sha1 : uchar[20]\n }\n elif value_type == VALUE_PEELED {\n # This is a normal (non-symbolic) reference that points at a\n # tag. `peeled` is the reference peeled down to a non-tag.\n sha1 : uchar[20]\n peeled : uchar[20]\n }\n elif value_type == SYMREF {\n # This is a symref that points at a non-existent branch.\n target : varstr\n }\n elif value_type == SPECIAL {\n # This is one of the special references (like FETCH_HEAD,\n # MERGE_HEAD). The contents are stored as they would be in a\n # loose reference file:\n contents : varstr\n }\n\n if log_type == NO_REFLOG {\n }\n elif log_type == REFLOG {\n log_entry_length : varint\n log_entry\n }\n elif log_type == REFLOGS_COMPRESSED {\n compressed_length : varint\n zlib_deflate(\n log_entry*\n )\n }\n}\n\n# Log entries are stored from oldest to newest. The \"chained\" variants\n# of `log_type` take their `new_id` from the current value of the\n# reference (if it is the first log entry for the references) or from\n# the preceding (i.e., next newest) log record's `old_id` value.\nlog_entry = {\n # `CREATE_CHAINED` and `UPDATE_CHAINED` take their `new_id` from\n # the preceding (i.e., next newest) record's `old_id` value.\n log_type : enum END_OF_LOG | LOG\n old_type : enum ABSENT | REF | SYMREF\n new_type : enum ABSENT | REF | SYMREF | CHAINED\n\n if log_type == LOG {\n # The update_index of this entry, or 0 if there are no more\n # entries. log_entries are always stored in order from largest\n # to smallest update_index.\n update_index : varint\n\n # `PUSHER_CHAINED` takes its `name` and `email` from the preceding\n # (i.e., next newest) record's fields.\n pusher_type : enum PUSHER_EXPLICIT | PUSHER_CHAINED\n\n if new_type == ABSENT {\n }\n elif new_type == REF {\n new_id : uchar[20]\n }\n elif new_type == SYMREF {\n new_ref : varstr\n }\n elif new_type == CHAINED {\n }\n\n if old_type == ABSENT {\n }\n elif old_type == REF {\n old_id : uchar[20]\n }\n elif old_type == SYMREF {\n old_ref : varstr\n }\n\n time_seconds : uint32\n tz_offset_minutes : sint16\n if pusher_type == PUSHER_EXPLICIT {\n name : varstr\n email : varstr\n }\n\n # The reflog message. For a bit more compression:\n #\n # * Many messages contain old/new SHA-1s for the reference\n # updates. That redundancy could be eliminated by replacing\n # the old SHA-1 with `%o`, the new one with `%n`, and `%`\n # with `%%`.\n #\n # * Some \"standard\" log messages (i.e., the ones generated by\n # Git itself) could be hard-coded as additional `log_type`\n # constants.\n message : varstr\n } else if log_type == LOG_DELETED {\n # An entry of this type indicates that any reflog entries for\n # this reference in reftables with `update_index >\n # next_retained_update_index` should be ignored (either they\n # have been deleted or they have been superseded by entries in\n # this reftable). This feature will mainly be used for `git\n # stash drop` and related commands. Such an entry, if it\n # exists, must be the last (or only) log_entry in the\n # ref_payload.\n next_retained_update_index : varint\n } else if log_type == END_OF_LOG {\n }\n}\n```\n\n\n## Object → reference lookup extension\n\nThis extension allows one to determine efficiently which references\n(if any) point at an object with a specified name.\n\nThis data is structured as an N-way trie whose branching factors can\nvary from level to level. There are two kinds of nodes:\n\n* Internal nodes (composed of chunks of type `OBJ_INDEX`): always\n point to other chunks of type `OBJ_INDEX` or `OBJ_LEAF`.\n\n* Leaf nodes (composed of chunks of type `OBJ_LEAF`): can also include\n branching, but the individual items point at `obj_record`s within\n the same `OBJ_LEAF`.\n\nEach `obj_record` within an `OBJ_LEAF` node points at one or more\n`REFS` chunks that contain references that point at an object whose\nname starts with the indicated prefix. To find the name(s) of\nreference(s) that point at your SHA-1, you have to read the `REFS`\nchunk and compare the target SHA-1s to yours.\n\n```\nobjref_extension = {\n extension_name : varstr(\"objref\")\n\n # The file offset of the chunk containing the root of the object\n # trie. This value must be zero (or the extension must be absent)\n # if `contains_values` is false:\n obj_root_chunk_addr : uint64\n}\n\nobjref_chunk = {\n chunk_length : varint\n\n objref_chunk_type = OBJ_INDEX | OBJ_LEAF\n\n # The degree of branching at this node is `1 << radix_bits`. For\n # `OBJ_LEAF` nodes, it is allowed for this to be zero:\n radix_bits : uint4\n\n if objref_chunk_type == OBJ_INDEX {\n # The offset, relative to the start of this chunk, of the\n # chunk containing the next level of the obj index, for each\n # of the possible \"next\" bytes in the SHA-1, or zero if there\n # are no references with the given next byte.\n child_offset : varint * (1 << radix_bits)\n }\n elif objref_chunk_type == OBJ_LEAF {\n # The total number of SHA-1 bytes that are included in the\n # SHA-1 prefixes corresponding to each child, including those\n # accounted for by the `radix_bits` of all of the ancestor\n # nodes:\n prefix_bytes : uint4\n\n # The relative address, within this chunk, of the obj_record\n # for each combination of the next `radix_bits` bits of the\n # SHA-1, or zero if there are no references with the given\n # next byte.\n obj_record_addr : varint[1 << radix_bits]\n\n # The object records for the SHA-1 prefixes referred to above:\n obj_record*\n }\n}\n\nobj_record = {\n # The bytes `sha1[floor(sum(radix_bits) / 8) : prefix_bytes]` of\n # the SHA-1 being described (see below):\n prefix : uchar[n]\n\n # The number of child_addrs:\n count : varint\n\n # File offsets of the chunks containing references that point at\n # objects with this prefix:\n child_addr+ : varint\n}\n```\n\nOn Thu, Aug 3, 2017 at 3:26 PM, Shawn Pearce wrote:\n> On Thu, Aug 3, 2017 at 11:38 AM, Michael Haggerty wrote:\n>> On Tue, Aug 1, 2017 at 7:38 PM, Shawn Pearce wrote:\n>>> On Tue, Aug 1, 2017 at 6:51 PM, Michael Haggerty wrote:\n>>>> On Tue, Aug 1, 2017 at 4:27 PM, Shawn Pearce wrote:\n>>>>> On Mon, Jul 31, 2017 at 11:41 PM, Michael Haggerty wrote:\n>>>>>> [...]\n>>>>> A couple of other notes about your contrasting design:\n>>>>>\n> ...\n>>>> OBJS blocks can also be\n>>>> unbounded in size if very many references point at the same object,\n>>>> thought that is perhaps only a theoretical problem.\n>>>\n>>> Gah, I missed that in reftable. The block id pointer list could cause\n>>> a single object id to exceed what fits in a block, and that will cause\n>>> the writer to fail unless its caller sets the block size larger. I\n>>> basically assumed this overflow condition is very unlikely, as its not\n>>> common to have a huge number of refs pointing to the same object.\n>>\n>> Given what Peff pointed out, let's just leave this as a varint for OBJS blocks.\n>\n> We discussed this at $DAY_JOB yesterday. We realized that if an obj\n> block has that many ref pointers present, it may be more efficient for\n> a reader to scan all references instead of chasing those pointers\n> individually. Latest draft of reftable now omits the ref pointer list\n> in an obj block if it exceeds the obj block size, which only occurs\n> when a high proportion of the ref blocks contain that SHA-1.\n"},{"id":"325603","messageId":"CAJo=hJvw3UBP7p-5Yxni++_CL8c3JC3etPkYqxSQiaBiKPQWww@mail.gmail.com","threadId":"46487","inReplyTo":"CAMy9T_EU6hPbnnB72ouRAd0yNvWn6_Ef8Bh2iPxChpmDt1qmFw@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-08-04T02:50:28Z","receivedAt":"2017-08-04T02:50:55Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Thu, Aug 3, 2017 at 3:48 PM, Michael Haggerty wrote:\n> I've revised the blockless reftable proposal to address some feedback:\n\nI've been thinking more about your blockless proposal.\n\nI experimentally modified my reftable implementation to omit padding\nbetween blocks, bringing it a tiny bit closer to your blockless\nproposal. Unfortunately this slightly increased latency for lookups on\na 4k chunk size. I speculate this is because chunks are no longer\naligned with the filesystem page, and I'm forcing Mac OS X to give me\ntwo pages out of the filesystem. Using padding to align to a 4k block\nis slightly faster, and the average wasted per block is <=20 bytes,\ntoo small to fit another ref.\n\nThe restart table and binary search within the 4k block is a\nperformance win. Disabling the restart table significantly increased\nlookup latency.\n\ntl;dr: I think the block alignment and restart table are wins vs. the\nmulti-level index.\n\n\nA suggested downside of my reftable design is the ref index at 4k\nblock size for 866k refs is 199 KiB, and must be paged in for binary\nsearch to locate the correct block for any lookup. The pack idx for\nthe two main packs in this repository is 210 MiB. We think fairly\nlittle of mmap'ing 210 MiB to perform binary search to find object\ndata. 199 KiB for ref data seems to be a bargain. An advantage of the\nsingle level index is its only one page touched after the index is\nloaded.\n\nHot reftable reads (5.6 usec) are faster than loose ref reads (6.5\nusec). Once the ref index is loaded, reftable can read a ref more\nquickly than the time required to open-read-close a loose ref.\nAdmittedly, a large index slows down a cold read.\n\ntl;dr: I just don't think the size of the index is a concern.\n\n\nI really favor the reflog data in a different section from the ref\nvalues themselves. Even for smaller transaction files, it improves\nscan and lookup time by allowing readers who just care about the name\nand SHA-1 value of a ref to not be paging in or skipping over log\nrecord payloads. However, I also agree that the aggregates may benefit\nfrom ref and log being separate files.\n\n\n> * Add a way to mark a reflog entry \"deleted\" without having to rewrite\n> everything. This is mostly meant to deal with `refs/stash`.\n\nThis is an interesting idea. Given how I implemented reftable in JGit,\njust inserting a deletion record for the same (ref,update_index) tuple\nwould make it trivial to hide the prior entry.\n\n> * Define an extension mechanism.\n> * Define the SHA-1 → object mapping as an extension rather than as\n> part of the main spec. My gut feeling is that it will never be\n> implemented for git-core.\n\nWhile the SHA-1 -> object mapping may never be implemented for\ngit-core, I'd still prefer to see it as an optional part of the file\nspecification, rather than an extension that is specified. IMHO the\nextension stuff in DIRC has made it unnecessarily complicated, and\nwe've still revved that file through many revisions.\n\n> * Revise how the SHA-1 → object mapping works:\n> * Merge the bottommost OBJ_INDEX node with the old OBJ nodes to\n> form a new OBJ_LEAF node.\n> * Allow the branching factor of each node to be specified\n> independently (to allow the node sizes to be matched more closely to\n> the preferred read sizes).\n\nI'm not sure objects warrant this kind of complexity. The obj support\nin reftable is nearly identical to the ref support. I have a\nsignificant amount of code that is common between them. Your approach\nhas objects different enough from refs that they need their own code,\nincreasing complexity in both the writer and reader.\n\n\n> I currently lean towards the opinion that we should store pseudorefs\n> (like `FETCH_HEAD`, `MERGE_HEAD` *outside of* reftables, except for\n> `HEAD` (which behaves more like a normal reference, which is\n> considered for reachability, and for which we want to retain reflogs),\n> which we should store *in* reftables.\n\nI'm on the fence, and don't really have a strong opinion about where\nwe store the pseudorefs. Happy to keep them in $GIT_DIR, happy to have\nthem supported inside a reftable.\n"},{"id":"325643","messageId":"CAJo=hJszDQ2N8cAjSqbJTTja03ke=i5H323U2Af+sZhviG9m-A@mail.gmail.com","threadId":"46487","inReplyTo":"CAMy9T_HUoD4--s1gNTUjnCgdiAqfYbX-GSqygDwNO-JRwdh4NQ@mail.gmail.com","subject":"Re: reftable [v4]: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-08-05T21:00:41Z","receivedAt":"2017-08-05T21:01:08Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Tue, Aug 1, 2017 at 6:51 PM, Michael Haggerty wrote:\n> On Tue, Aug 1, 2017 at 4:27 PM, Shawn Pearce wrote:\n>> On Mon, Jul 31, 2017 at 11:41 PM, Michael Haggerty wrote:\n>>> On Sun, Jul 30, 2017 at 8:51 PM, Shawn Pearce wrote:\n>>>> 4th iteration of the reftable storage format.\n>>>> [...]\n>>>\n>>> Before we commit to Shawn's reftable proposal, I wanted to explore\n>>> what a contrasting design that is not block based would look like.\n>>\n>> I forgot to look at a 1k chunk size, as you suggested that might also\n>> be suitable. Here is the more complete experiment table:\n>>\n>> | size | seek_cold | seek_hot |\n>> mh 1k | 29.4 M | 20.6 usec | 10.7 usec | <== Row fixed\n>> mh 4k | 28.3 M | 24.5 usec | 14.5 usec |\n>> sp 4k | 29.2 M | 63.0 usec | 5.8 usec |\n>> sp 64k | 27.7 M | 35.6 usec | 23.3 usec |\n\nI modified reftable to use a mutli-level index as recommended by\nMichael Haggerty, and re-ran the above table:\n\nfmt | bs | idx | size | seek_cold | seek_hot |\n----|-----|------|--------|-----------|-----------|\n mh | 1k | 4 lv | 29.4 M | 20.1 usec | 7.1 usec |\n sp | 1k | 4 lv | 30.7 M | 21.0 usec | 5.5 usec |\n\n mh | 4k | 2 lv | 28.3 M | 23.4 usec | 11.2 usec |\n sp | 4k | 2 lv | 29.2 M | 19.9 usec | 5.4 usec |\n\n sp | 4k | 1 lv | 29.2 M | 62.9 usec | 5.6 usec |\n sp | 64k | 1 lv | 27.7 M | 35.6 usec | 21.6 usec |\n\nfmt: mh = Michael's proposal, sp = Shawn's reftable\nbs: chunk size or block size in bytes\nidx: how many levels of index\nsize: total file size in bytes\n\nI can't explain the slightly slower sp-1k-4lv vs. mh-1k-4lv cold_seek\nin the first two rows. It might simply be the larger footer read\nslowing down JGit. Its reliably flipped in the next two (at 4k).\n\nreftable is more efficient in seek_hot at finding and parsing a\nreference. For multi-level indexes both sp and mh implementations used\na lazy caching strategy that caches index blocks along the path to the\nref, but doesn't cache the final ref block. The tests amortized this\nby performing 60,000 lookups on the same ref.\n\n>> At least in this case, the 1k block size seems like a good tradeoff.\n\nWith the multi-level index now in reftable, it seems like reftable at\n4k, 2 level index is a better tradeoff. It aligns with the most common\nfilesystem block size, and has lower seek times, both cold and hot.\nIts slightly larger than Michael's alternative proposal (+921 K), but\ncompresses better than reftable at 1k (-1.5 M).\n"}]}