{"thread":{"id":"46370","subject":"reftable: new ref storage format","startedAt":"2017-07-13T00:18:26Z","lastAt":"2017-07-23T23:04:08Z","messageCount":25,"participants":["Shawn Pearce","Jeff King","Stefan Beller","Eric Wong","Dave Borowitz","Johannes Sixt","Michael Haggerty","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"324329","messageId":"CAJo=hJtyof=HRy=2sLP0ng0uZ4=S-DpZ5dR1aF+VHVETKG20OQ@mail.gmail.com","threadId":"46370","inReplyTo":null,"subject":"reftable: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-07-13T00:17:58Z","receivedAt":"2017-07-13T00:18:26Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"We've been having scaling problems with insane number of references\n(>866k), so I started thinking a lot about improving ref storage.\n\nI've written a simple approach, and implemented it in JGit.\nPerformance is promising:\n\n - 62M packed-refs compresses to 27M\n - 42.3 usec lookup\n\nYou can read a rendered version of this here:\nhttps://googlers.googlesource.com/sop/jgit/+/reftable/Documentation/technical/reftable.md\n\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. This negatively affects the number of inodes\navailable when a large number of repositories are stored on the same\nfilesystem. Readers are also penalized due to the larger number of\nsyscalls required to traverse and 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- Occupy less disk space for large repositories.\n- Support atomic pushes with lower copying penalities.\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\n-----------|------------:|---------:|-----------:|---------:\nandroid | 62.2 M | 27.7 M | 44.4% | 33 bytes\nrails | 1.8 M | 896.2 K | 47.6% | 29 bytes\ngit | 78.7 K | 27.9 K | 40.0% | 43 bytes\ngit (heads)| 332 b | 204 b | 61.4% | 34 bytes\n\nScan (read 866k refs) and lookup (single ref from 866k refs):\n\nformat | scan | lookup\n------------|--------:|---------------:\npacked-refs | 380 ms | 375420.0 usec\nreftable | 125 ms | 42.3 usec\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### Ordering\n\nBlocks are lexicographically ordered by their first reference.\n\n\n## File format\n\n### Header\n\nA 8-byte header appears at the beginning of each file:\n\n- 4-byte magic is: `\\'1', 'R', 'E', 'F'`\n- 1-byte version number, `1`.\n- 3-byte `block_size` in bytes (network byte order).\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 used in the repository, as references cannot\nspan blocks.\n\n### First block\n\nThe first block shares the same block as the file header, and is 8\nbytes smaller than all other blocks in the file. The first block\nimmediately begins after the file header, at offset 8.\n\n### Block format\n\nA block is written as:\n\n ref_record*\n padding?\n int32( restart_offset )*\n int32( record_end_offset )\n int32( number_of_restarts )\n\nBlocks begin with a variable number of `ref_record`, describing\nreference names and values. The format is described below.\n\nThe middle of the record may be filled with `padding` NUL bytes to\nfill out the block to the common `block_size` as specified in the file\nheader. Padding may be necessary to ensure `number_of_restarts`\noccupies the last 4 bytes of the block. Padding may be omitted if the\nblock is the last block of the file, and there is no index block.\nThis allows reftable to efficiently scale down to a small number of\nrefs.\n\nA variable number of 4-byte, network byte order `restart_offset`\nvalues follows the padding. Offsets are relative to the start of the\nblock and refer to the first byte of any `ref_record` whose name has\nnot been prefixed compressed. Readers can start linear scans from any\nof these records.\n\nThe 4-byte, network byte order `record_end_offset` follows, providing\nthe block-relative offset after the end of the last `ref_record`. If\n`padding` is present this is the offset of the first byte of padding,\nor the first byte of the first `restart_offset` entry.\n\nThe 4-byte, network byte order `number_of_restarts` stores the number\nof entries in the `restart_offset` list. Readers can use the restart\ncount to binary search between restarts before starting a linear scan.\nThis field must be the last 4 bytes of the block; the `padding` field\nmust be used to ensure this is true.\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 << 2) | 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 second varint carries both `suffix_length` and `type`. The\n`suffix_length` value provides the number of bytes to copy from\n`suffix` to complete the reference name.\n\nThe `value` immediately follows. Its format is determined by `type`,\na 2 bit code, one of 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`: symbolic reference: `varint( target_len ) target`\n\nSymbolic references use a varint length followed by a variable number\nof bytes to encode the complete reference target. No compression is\napplied to the target name.\n\n### Index block\n\nThe index stores the name of the last reference from every block in\nthe file, enabling constant O(1) disk seeks for all lookups. Any\nreference can be found by binary searching the index, identifying the\ncontaining block, and searching within that block.\n\nIf present, the index block appears after the last block of the file.\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, and\nbinary searching <= 4 blocks also requires <= 2 reads. Omitting the\nindex block from smaller files saves space.\n\nIndex block format:\n\n '\\1' 'i'\n index_record*\n int32( restart_offset )*\n int32( record_end_offset )\n int32( number_of_restarts )\n\nIndex blocks begin with a magic prefix, `\\1i`, where other blocks\nwould have started with `\\0` for the first ref record's prefix length.\nThis supports stopping sequential scans at the index block, without\nprior knowledge of its position.\n\nUnlike other blocks, the index block is not padded.\n\nThe `restart_offset`, `record_end_offset`, and `number_of_restarts`\nfields are identical in format, meaning and usage as in `ref_record`.\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\nits a time-space tradeoff in both file size, and reader memory.\nIncreasing the block size in the writer decreases the index size.\n\n#### index record\n\nAn index record describes the last reference of another block.\nIndex records are written as:\n\n varint( prefix_length )\n varint( (suffix_length << 2) )\n suffix\n varint( block_idx )\n\nIndex records use prefix compression exactly like `ref_record`. The\n`suffix_length` is shifted 2 bits without a `type` to simplify unified\nreader/writer code for both block types.\n\nIndex records store `block_idx` after the suffix, specifying which\nblock of the file ends with this reference. The block is located at\nposition `block_idx * block_size`.\n\n### Reading the index\n\nReaders loading the index must first read the footer (below) to\ndetermine `index_size`. The index is located at position:\n\n file_length - (index_size + 16)\n\n### Footer\n\nAfter the last block of the file (or index block, if present), a file\nfooter is written. This is similar in structure to the file header,\nbut extended with additional data.\n\nA 16-byte footer appears at the end:\n\n- 4-byte magic is: `\\'1', 'R', 'E', 'F'`\n- 1-byte version number, 1.\n- 3-byte `block_size` in bytes (network byte order).\n- 4-byte `index_size` in bytes (network byte order).\n- 4-byte CRC-32 of the preceding 12 bytes (network byte order).\n\nLike the index block magic header, the footer begins with `\\1R` to\nallow sequential scans to recognize the end of file has been reached.\n\n#### Reading the footer\n\nReaders must seek to `file_length - 16` 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 12 bytes read\n\nOnce verified, the `block_size` and `index_size` may be accessed from\nthe footer.\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++\n val = val << 7\n val = val | (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 should appear.\n\nEach reference identified by a `restart_offset` stores the complete\nreference name in the `suffix` field of the `ref_record`, making the\ncompare operation during the binary search straightforward.\n\nOnce a restart point lexicographically before the sought reference has\nbeen identified, readers can linearly scan through the following\n`ref_record` entries to locate the sought reference, stopping when the\ncurrent `ref_record` sorts after (and therefore the sought reference\nis 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 references 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 will increase the\noverall file size.\n\nLess frequent restart points makes prefix compression more effective,\ndecreasing overall file size, with increased penalities for readers\nwho must walk through more references after the binary search step.\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) uses\nonly 204 bytes for reftable vs. 332 bytes for packed-refs. This\nsupports reftable scaling down, to be used for transaction logs\n(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 able to\ncompress against 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## Repository format\n\nWhen reftable is stored in a file-backed Git repository, the stack is\nrepresented as a series of reftable files:\n\n $GIT_DIR/reftable\n $GIT_DIR/reftable.1\n $GIT_DIR/reftable.2\n $GIT_DIR/reftable.3\n ...\n $GIT_DIR/reftable.10\n\nwhere a larger suffix ordinal indicates a more recent table.\n\n### Transactions\n\nAlthough reftables are immutable, they can be stacked in a search\npattern, with each reference transaction adding a new reftable to the\ntop of the stack. Readers scan down the reftable stack from\nmost-recent (`reftable.10`) to the base file (`reftable`).\n\n### Update process\n\nUpdating references follows an update protocol:\n\n1. Atomically create `$GIT_DIR/reftable.lock`.\n2. `readdir($GIT_DIR)` to determine the highest suffix ordinal, `n`.\n3. Compute the update transaction (e.g. compare expected values).\n4. Write only modified references as a reftable to `reftable.lock`.\n5. Rename `reftable.lock` to `reftable.${n + 1}`.\n\nBecause a single `reftable.lock` file is used to manage locking, the\nrepository is single-threaded for writers. Writers may have to\nbusy-spin (with some small backoff) around creating `reftable.lock`,\nfor up to an acceptable wait period, aborting if the repository is too\nbusy to mutate. Application servers wrapped around repositories (e.g.\nGerrit Code Review) can layer their own in memory thread lock/wait\nqueue to provide fairness.\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 lower files in the stack.\n\n### Compaction\n\nA stack of reftables can be compacted by merging references using a\nstraightforward merge join across all reftables, selecting the most\nrecent value for output, and omitting deleted references that do not\nappear in remaining, lower reftables.\n\nThe stack can be collapsed as part of any update transaction. If the\ncurrent number of files is larger than a threshold (e.g. 4), writers\ncan perform an lstat(2) on each reftable file to determine how many\nbytes would have to be read/copied from an existing file into the\nnew file, enabling deletion of the existing file.\n\nWriters can select to collapse the most recent files (e.g. 10, 9, 8,\n...), up to a collapse IO threshold (e.g. 4 MiB). Each file selected\nfor collapse must have its references merged into the new reftable\nthat is being prepared.\n\nCompaction is similar to the update process, but an explicit temporary\nfile must be used:\n\n1. Atomically create `$GIT_DIR/reftable.lock`.\n2. `readdir($GIT_DIR)` to determine the highest suffix ordinal, `n`.\n3. Compute the update transaction (e.g. compare expected values).\n4. Select files from (2) to collapse as part of this transaction.\n5. Create temp file by `mktemp(\"$GIT_DIR/.reftableXXXXXX\")`.\n6. Write modified and collapsed references to temp file.\n7. Rename temp file to `reftable.${n + 1}`.\n8. Delete collapsed files `reftable.${n}`, `reftable.${n - 1}`, ...\n9. Delete `reftable.lock`.\n\nBecause `reftable.9` can disappear after `reftable.10` is created,\nreaders receiving ENOENT when opening `reftable.9` must peform\nanother readdir to look for new reftables.\n\nRebuilding the base `$GIT_TABLE/reftable` follows the same protocol,\nexcept in step 7 the temp file is renamed to `reftable`, and step 8\nremoves all files with an ordinal suffix.\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 ratios achieved by reftable's simple encoding\n(e.g. 44%), without using a standard compression algorithm, it does\nnot seem 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 hositing 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":"324423","messageId":"20170713193234.fkxf73t6jevj4svg@sigill.intra.peff.net","threadId":"46370","inReplyTo":"CAJo=hJtyof=HRy=2sLP0ng0uZ4=S-DpZ5dR1aF+VHVETKG20OQ@mail.gmail.com","subject":"Re: reftable: new ref storage format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-07-13T19:32:34Z","receivedAt":"2017-07-13T19:32:42Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 12, 2017 at 05:17:58PM -0700, Shawn Pearce wrote:\n\n> We've been having scaling problems with insane number of references\n> (>866k), so I started thinking a lot about improving ref storage.\n> \n> I've written a simple approach, and implemented it in JGit.\n> Performance is promising:\n> \n> - 62M packed-refs compresses to 27M\n> - 42.3 usec lookup\n\nExciting. I'd love for us to have a simple-ish on-disk structure that\nscales well and doesn't involve a dependency on a third-party database\nstructure.\n\nLet me see what holes I can poke in your proposal, though. :)\n\n> ### Problem statement\n> \n> Some repositories contain a lot of references (e.g. android at 866k,\n> rails at 31k). The existing packed-refs format takes up a lot of\n> space (e.g. 62M), and does not scale with additional references.\n> Lookup of a single reference requires linearly scanning the file.\n\nI think the linear scan is actually an implementation short-coming. Even\nthough the records aren't fixed-length, the fact that newlines can only\nappear as end-of-record is sufficient to mmap and binary search a\npacked-refs file (you just have to backtrack a little when you land in\nthe middle of a record).\n\nI wrote a proof of concept a while ago, but got stuck on integrating it\ninto the ref code, because of some of the assumptions that it made.\nMichael Haggerty has been doing several rounds of refactors to remove\nthose assumptions. I think we're pretty close (I've actually seen the\nendgame where packed-refs is fully binary searched, but I think there\nare a few more cleanups necessary to cover all cases).\n\n> Atomic pushes modifying multiple references require copying the\n> entire packed-refs file, which can be a considerable amount of data\n> moved (e.g. 62M in, 62M out) for even small transactions (2 refs\n> modified).\n\nI think your definition of atomic here doesn't match what git.git does.\n\nOur atomic push just takes the lock on all of the refs, and then once it\nhas all of them, commits all of the locks. So it's atomic in the sense\nthat you either get all or none of the writes (modulo a commit failure\nin the middle, which we naturally have no rollback plan for). But it can\nbe done without touching the packed-refs file at all.\n\nI imagine that you're looking at atomicity from the perspective of a\nreader. In the git.git scheme, the reader may see a half-committed\ntransaction. If you dispense with loose refs entirely and treat the\npacked-refs file as a single poorly-implemented key/value database, then\nyou get reader atomicity (but O(size_of_database) write performance).\n\n> Repositories with many loose references occupy a large number of disk\n> blocks from the local file system, as each reference is its own file\n> storing 41 bytes. This negatively affects the number of inodes\n> available when a large number of repositories are stored on the same\n> filesystem. Readers are also penalized due to the larger number of\n> syscalls required to traverse and read the `$GIT_DIR/refs` directory.\n\nIn my experience, the syscalls involved in loose refs aren't usually a\nbig deal. If you have 800k refs, they're not all changing constantly. So\na single pack-refs \"fixes\" performance going forward. What _is_ a big\ndeal is that the packing process is complicated, readers have a very\nun-atomic view because of the myriad of files involved, and you get\nannoying lock contention during packing, as well as between deletions\nthat have to rewrite packed-refs.\n\nBut I'm not sure if you meant to contrast here a system where we didn't\nuse packed-refs at all (though of course such a system is very much not\natomic by the definition above).\n\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\nGood goal, though TBH I'd be happy with O(log n).\n\nA related one is being able to traverse a subset of refs in\nO(nr_traversed). E.g., \"git tag -l\" should not have to do work\nproportional to what is in refs/changes. That falls out of most\nproposals that allow fast lookups, but notably not a straight\nhash-table.\n\n> - Occupy less disk space for large repositories.\n\nGood goal. Just to play devil's advocate, the simplest way to do that\nwith the current code would be to gzip packed-refs (and/or store sha1s\nas binary). That works against the \"mmap and binary search\" plan,\nthough. :)\n\n> - Support atomic pushes with lower copying penalities.\n\n\"Lower\" is vague. I'd hope we could do updates with effort linear to the\nnumber of updated refs (it's OK if there's a constant factor, like\nwriting extra blocks, as long as a single-ref update is about as\nexpensive in a 10-ref repo as in a 10K-ref repo).\n\n> Scan (read 866k refs) and lookup (single ref from 866k refs):\n> \n> format | scan | lookup\n> ------------|--------:|---------------:\n> packed-refs | 380 ms | 375420.0 usec\n> reftable | 125 ms | 42.3 usec\n\nDon't forget in git.git that the memory usage for packed-refs is\natrocious (because we parse the whole thing into RAM).\n\n> ### Peeling\n> \n> References in a reftable are always peeled.\n\nGood. This is a very important optimization to retain.\n\n> ### Reference name encoding\n> \n> Reference names should be encoded with UTF-8.\n\nDon't we usually treat refnames as byte sequences (subject to a few\nrules, as in check_ref_format())? It seems like the encoding should be\nout-of-scope for the storage format.\n\n> ## File format\n\nOK, let me try to summarize to see if I understand.\n\nThe reftable file is a sequence of blocks, each of which contains a\nfinite set of heavily-compressed refs. You have to read each block\nsequentially, but since they're a fixed size, that's still a\nconstant-time operation (I'm ignoring the \"restarts\" thing for now). You\nfind the right block by reading the index. So lookup really is more\nlike O(block_size * log(n/block_size)), but block_size being a constant,\nit drops out to O(log n).\n\nLinear scans are easy, because everything is in sorted order. So you\njust find the first entry via binary search, and then walk forward.\n\nUpdates are where things get dicier. It looks like you just write a new\npartial reftable file with your updates. And then if there are N\nreftables present, readers actually have to do a list-merge of the\nresults they get from all of them (where the results from reftable.5\ntrump ones from reftable.4).\n\nSo basically we're just journaling updates into a directory of atomic\nreftable updates. And then to keep the reader's job from getting too\npainful, a write occasionally has to compact into a single reftable,\nrewriting the entire ref store. That's what I see as the biggest\nweakness here. If you keep too large a reftable stack, then readers have\nto spend a lot of extra effort on lookups. But if you keep too small a\nstack, then you are frequently rewriting the whole database.\n\nTechnically writes are still O(n). Because of the journaling you\namortize the whole-rewrite cost across several updates, but it's still\nO(n/c). That seems like the biggest weakness of the scheme to me.\n\nI think there's some cleverness you can use with compacting in a\ngeometric scheme, though, to amortize up to a certain bound. I didn't\nsee any discussion of that, though.\n\nIt's also possible I'm misunderstanding the writes. See below.\n\n> Compaction is similar to the update process, but an explicit temporary\n> file must be used:\n> \n> 1. Atomically create `$GIT_DIR/reftable.lock`.\n> 2. `readdir($GIT_DIR)` to determine the highest suffix ordinal, `n`.\n> 3. Compute the update transaction (e.g. compare expected values).\n> 4. Select files from (2) to collapse as part of this transaction.\n> 5. Create temp file by `mktemp(\"$GIT_DIR/.reftableXXXXXX\")`.\n> 6. Write modified and collapsed references to temp file.\n> 7. Rename temp file to `reftable.${n + 1}`.\n> 8. Delete collapsed files `reftable.${n}`, `reftable.${n - 1}`, ...\n> 9. Delete `reftable.lock`.\n\nI had originally assumed you'd just compact back down to the reftable\nfile after some N updates (say, 10). But here, it looks like you'd\nalways compact 0-9 into 10, and then 10-19 into 20, and so on, and the\nordinal would go up forever.\n\nI think that's OK, as it would take a long time to get unwieldy. And I\nthink you have to do it that way, as you can't atomically replace\n\"reftable\" and delete .1-.9 at the same time.\n\n> Because `reftable.9` can disappear after `reftable.10` is created,\n> readers receiving ENOENT when opening `reftable.9` must peform\n> another readdir to look for new reftables.\n\nBut after compaction, won't having \"reftable.10\" but no \".9\" be the\nsteady state? As a reader, how can I tell the difference between these\ntwo cases:\n\n 1. Somebody created .10 and deleted .9 and lower.\n\n 2. Somebody created .11 and deleted .10 and lower, while I was trying\n to read .9.\n\nIs basically every read going to require:\n\n 1. readdir to find the highest ordinal\n\n 2. keep walking down the stack until you get ENOENT\n\n 3. readdir again to make sure there's not a new ordinal\n\nBut in that case, if step 3 turns up a new reftable.11, how do I know\nwhether it's a compaction (in which case I need to restart my read from\n.11) or if it's just another update-on-top? In a busy repository, you\nmight see a lot of update-on-tops.\n\n> [...specifics...]\n\nI liked a lot of what I saw in the rest of it (e.g., handling symrefs,\nwhich packed-refs does not). Some bits seemed complicated. E.g., I\nactually wonder how much restarts help in practice if you have\nreasonably-sized blocks, and they complicate things a lot). Likewise\nsome bits are optional for very small reftable files to reduce overhead.\nBut if you have very small reftables, it's going to be fast either way.\nIf you waste 4K to store 200 bytes, that's fine as long as you're still\nwasting only 4K when you store 200 megabytes.\n\nThat's all hand-waving, of course. But all things being equal, I'd\nprefer to focus on algorithmic speedups, focusing on the simplest thing\nthat could work, and then seeing real experimental numbers from\nadditions.\n\nI also realize that beggars can't be choosers. If you have a working\nsystem that performs well, I should consider shutting up. :)\n\nOne thing I didn't see is reflogs. They don't strictly have to be part\nof a ref-storage solution. But they do still consume at least one inode\nper ref in the current system. If you reflog everything, which in my\nopinion you should. Having an audit trail of ref updates is very useful\nfor debugging (both bugs in Git, and trying to figure out what went\nwrong when a user goes berserk with \"git push --prune\").\n\n-Peff\n"},{"id":"324430","messageId":"CAGZ79kbY_t=Xtpb7fy0sZ9TWOy-UOUx8X5+_qLx60Dtg48Ok-g@mail.gmail.com","threadId":"46370","inReplyTo":"20170713193234.fkxf73t6jevj4svg@sigill.intra.peff.net","subject":"Re: reftable: new ref storage format","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-07-13T19:56:54Z","receivedAt":"2017-07-13T19:57:00Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Thu, Jul 13, 2017 at 12:32 PM, Jeff King wrote:\n> On Wed, Jul 12, 2017 at 05:17:58PM -0700, Shawn Pearce wrote:\n>\n>> We've been having scaling problems with insane number of references\n>> (>866k), so I started thinking a lot about improving ref storage.\n>>\n>> I've written a simple approach, and implemented it in JGit.\n>> Performance is promising:\n>>\n>> - 62M packed-refs compresses to 27M\n>> - 42.3 usec lookup\n>\n> Exciting. I'd love for us to have a simple-ish on-disk structure that\n> scales well and doesn't involve a dependency on a third-party database\n> structure.\n>\n> Let me see what holes I can poke in your proposal, though. :)\n>\n>> ### Problem statement\n>>\n>> Some repositories contain a lot of references (e.g. android at 866k,\n>> rails at 31k). The existing packed-refs format takes up a lot of\n>> space (e.g. 62M), and does not scale with additional references.\n>> Lookup of a single reference requires linearly scanning the file.\n>\n> I think the linear scan is actually an implementation short-coming. Even\n> though the records aren't fixed-length, the fact that newlines can only\n> appear as end-of-record is sufficient to mmap and binary search a\n> packed-refs file (you just have to backtrack a little when you land in\n> the middle of a record).\n\nExcept that a record is a \"delta\" to the previous record, so it's not\njust finding a record, but reconstructing it. Example for records:\n\n varint( prefix_length )\n varint( (suffix_length << 2) | type )\n suffix\n value?\n\nFirst record:\n\n 0,\n 16 << 2 | 0x01,\n \"refs/heads/maint\"\n 08f9c32463bf9e578acb7ac5f77afd36e803c6bc\n\nnext record (refs/heads/master):\n\n 13\n 4 << 2 | 0x01\n \"ster\",\n 80145b1e412719c960036c8c62a9e35dd23a5b2d\n\nNow if you found the second one, you cannot reconstruct its\nreal name (refs/heads/master) without knowing the name\nof the first. The name of the first is easy because the prefix_length\nis 0. If it also had a prefix length != 0 you'd have to go back more.\n\n\n>> - Occupy less disk space for large repositories.\n>\n> Good goal. Just to play devil's advocate, the simplest way to do that\n> with the current code would be to gzip packed-refs (and/or store sha1s\n> as binary). That works against the \"mmap and binary search\" plan,\n> though. :)\n\nGiven the compression by delta-ing the name to the previous change and\nthe fact that Gerrit has\n\n refs/heads/changes/1\n refs/heads/changes/2\n refs/heads/changes/3\n ...\n\nI think this format would trump a \"dumb\" zip.\n(Github having sequentially numbered pull requests would also\nbenefit here)\n\n>> ## File format\n>\n> OK, let me try to summarize to see if I understand.\n\nWhen Shawn presented the proposal, a couple of colleagues here\nwere as excited as I was, but the daring question is, why Shawn\ndid not give the whole thing in BNF format from top down:\n\n initial-block\n content-blocks*\n (index-block)\n footer\n\n> The reftable file is a sequence of blocks, each of which contains a\n> finite set of heavily-compressed refs. You have to read each block\n> sequentially,\n\nEach block may have restarting points, that allow for intra-block\nbinary search.\n\n> but since they're a fixed size, that's still a\n> constant-time operation (I'm ignoring the \"restarts\" thing for now). You\n> find the right block by reading the index.\n\nor by reading the footer at the end. If the footer and the index differ\nin block size (one bit flipped), we can ask the CRC of the footer\nfor more guidance.\n\n> So lookup really is more\n> like O(block_size * log(n/block_size)), but block_size being a constant,\n> it drops out to O(log n).\n\nThere is also an index block such that you can binary search across\nblocks, so\n\nO( log(block_count) + log(intra_block_restarting_points) + small linear scan)\n\nThere are 2 binary searches, and the block size is an interesting\nthing to look at when making up trade offs.\n"},{"id":"324439","messageId":"20170713203533.vcfyf5iei46g4tcf@sigill.intra.peff.net","threadId":"46370","inReplyTo":"CAGZ79kbY_t=Xtpb7fy0sZ9TWOy-UOUx8X5+_qLx60Dtg48Ok-g@mail.gmail.com","subject":"Re: reftable: new ref storage format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-07-13T20:35:33Z","receivedAt":"2017-07-13T20:35:40Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jul 13, 2017 at 12:56:54PM -0700, Stefan Beller wrote:\n\n> >> ### Problem statement\n> >>\n> >> Some repositories contain a lot of references (e.g. android at 866k,\n> >> rails at 31k). The existing packed-refs format takes up a lot of\n> >> space (e.g. 62M), and does not scale with additional references.\n> >> Lookup of a single reference requires linearly scanning the file.\n> >\n> > I think the linear scan is actually an implementation short-coming. Even\n> > though the records aren't fixed-length, the fact that newlines can only\n> > appear as end-of-record is sufficient to mmap and binary search a\n> > packed-refs file (you just have to backtrack a little when you land in\n> > the middle of a record).\n> \n> Except that a record is a \"delta\" to the previous record, so it's not\n> just finding a record, but reconstructing it. Example for records:\n\nI was still talking about the existing packed-refs implementation here.\n\nI agree that a full binary search of a reftable is harder because of the\nprefix compression (it may still be possible by scanning backwards, but\nI think there are ambiguities when you land in the middle of a record,\nsince there's no unambiguous end-of-record character). But I don't think\nit matters. If you binary-search to a constant-sized block, then a\nlinear scan of the block is acceptable.\n\n> >> - Occupy less disk space for large repositories.\n> >\n> > Good goal. Just to play devil's advocate, the simplest way to do that\n> > with the current code would be to gzip packed-refs (and/or store sha1s\n> > as binary). That works against the \"mmap and binary search\" plan,\n> > though. :)\n> \n> Given the compression by delta-ing the name to the previous change and\n> the fact that Gerrit has\n> \n> refs/heads/changes/1\n> refs/heads/changes/2\n> refs/heads/changes/3\n> ...\n> \n> I think this format would trump a \"dumb\" zip.\n> (Github having sequentially numbered pull requests would also\n> benefit here)\n\nYou may be surprised. Let's imagine that you have a set of 4096 refs in\nrefs/changes/1, refs/changes/2, etc:\n\n for i in $(seq 1 4096)\n do\n echo refs/changes/$i\n done >input\n\nNow let's do a prefix compression, with a single byte for \"how many\ncharacters to reuse from the last entry\":\n\n perl -lne '\n my $common;\n if (defined $last) {\n chop $last while !/\\Q$last\\E/;\n $common = length($last);\n } else {\n $common = 0;\n }\n print chr($common), substr($_, $common);\n $last = $_;\n ' prefix\n\nAnd a gzip:\n\n gzip -c -9 zip\n\nAnd the results:\n\n $ wc -c prefix; wc -c zip\n 12754 prefix\n 10116 zip\n\nThe secret sauce is most likely that gzip is bit-packing, using only a\nfew bits per character and not aligning with byte boundaries.\n\nNot that I'm recommending just gzipping the whole packed-refs file. It\nruins the fast-lookup. We _could_ consider gzipping individual blocks of\na reftable (or any structure that allows you to search to a\nconstant-sized block and do a linear search from there). But given that\nthey're in the same ballpark, I'm happy with whatever ends up the\nsimplest to code and debug. ;)\n\nJust for fun, here's the decoding script for the prefix-compression:\n\n perl -e '\n while (read(STDIN, $common, 1)) {\n $common = ord($common);\n $rest = ;\n if ($common > 0) {\n $rest = substr($last, 0, $common) . $rest\n }\n print $rest;\n $last = $rest}' > OK, let me try to summarize to see if I understand.\n> \n> When Shawn presented the proposal, a couple of colleagues here\n> were as excited as I was, but the daring question is, why Shawn\n> did not give the whole thing in BNF format from top down:\n> \n> initial-block\n> content-blocks*\n> (index-block)\n> footer\n\nYeah, I agree it took me a bit to figure out what was going on. A\nhigh-level overview of the format would have been nice.\n\n> > So lookup really is more\n> > like O(block_size * log(n/block_size)), but block_size being a constant,\n> > it drops out to O(log n).\n> \n> There is also an index block such that you can binary search across\n> blocks, so\n> \n> O( log(block_count) + log(intra_block_restarting_points) + small linear scan)\n> \n> There are 2 binary searches, and the block size is an interesting\n> thing to look at when making up trade offs.\n\nRight, the cross-block index was what I was trying to account for.\nEither way, from a big-O perspective the block size and the number of\nrestarts are constants with respect to the total number of entries. I'm\nhappy with log(n), though. It's hard to do better.\n\n-Peff\n"},{"id":"324455","messageId":"20170713215147.GA31153@starla","threadId":"46370","inReplyTo":"20170713203533.vcfyf5iei46g4tcf@sigill.intra.peff.net","subject":"Re: reftable: new ref storage format","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2017-07-13T21:51:47Z","receivedAt":"2017-07-13T21:51:54Z","isPatch":false,"sender":{"key":"e@80x24.org","avatar":null},"body":"Jeff King wrote:\n> I agree that a full binary search of a reftable is harder because of the\n> prefix compression (it may still be possible by scanning backwards, but\n> I think there are ambiguities when you land in the middle of a record,\n> since there's no unambiguous end-of-record character). But I don't think\n> it matters. If you binary-search to a constant-sized block, then a\n> linear scan of the block is acceptable.\n\nFor a new packed-refs, I think an intrusive critbit tree would\nbe a good way to store refs which have many common prefixes and\nI've always wanted to apply critbit to an on-disk storage\nformat...\n\nSeveral years ago, I started writing one in Perl using\npwrite/pread to provide Message-ID <=> NNTP article number\nmapping several years ago, but gave up on it out of laziness:\n\n https://80x24.org/spew/1441508596-19511-1-git-send-email-e@80x24.org/raw\n\nThe end goal would've been to have two tries sharing the same\nstorage struct: one keyed by Message-ID, the other keyed by NNTP\narticle number (and figuring out the node using offsets like\nwe do with (container_of|list_entry) in list.h.\n\nFor git, being able to do an O(hashlength) prefix search based\non the object_id from the reftable would speed up decorations, I\nthink. And of course, the O(refnamelength) prefix search would\nalso apply to the refnames themselves.\n"},{"id":"324484","messageId":"CAJo=hJts=wY4vBaLsOtoH8+LBFK_drBhHMxPvKoQcqtpOfJOog@mail.gmail.com","threadId":"46370","inReplyTo":"20170713193234.fkxf73t6jevj4svg@sigill.intra.peff.net","subject":"Re: reftable: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-07-14T00:11:52Z","receivedAt":"2017-07-14T00:12:20Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Thu, Jul 13, 2017 at 12:32 PM, Jeff King wrote:\n> On Wed, Jul 12, 2017 at 05:17:58PM -0700, Shawn Pearce wrote:\n>\n>> ### Problem statement\n>>\n>> Some repositories contain a lot of references (e.g. android at 866k,\n>> rails at 31k). The existing packed-refs format takes up a lot of\n>> space (e.g. 62M), and does not scale with additional references.\n>> Lookup of a single reference requires linearly scanning the file.\n>\n> I think the linear scan is actually an implementation short-coming. Even\n> though the records aren't fixed-length, the fact that newlines can only\n> appear as end-of-record is sufficient to mmap and binary search a\n> packed-refs file (you just have to backtrack a little when you land in\n> the middle of a record).\n>\n> I wrote a proof of concept a while ago, but got stuck on integrating it\n> into the ref code, because of some of the assumptions that it made.\n> Michael Haggerty has been doing several rounds of refactors to remove\n> those assumptions. I think we're pretty close (I've actually seen the\n> endgame where packed-refs is fully binary searched, but I think there\n> are a few more cleanups necessary to cover all cases).\n\nYou are correct, this is possible with the current packed-refs format.\nIt just hasn't materialized in a shipping implementation yet.\n\n\n>> Atomic pushes modifying multiple references require copying the\n>> entire packed-refs file, which can be a considerable amount of data\n>> moved (e.g. 62M in, 62M out) for even small transactions (2 refs\n>> modified).\n>\n> I think your definition of atomic here doesn't match what git.git does.\n\n:-(\n\n\n> Our atomic push just takes the lock on all of the refs, and then once it\n> has all of them, commits all of the locks. So it's atomic in the sense\n> that you either get all or none of the writes (modulo a commit failure\n> in the middle, which we naturally have no rollback plan for). But it can\n> be done without touching the packed-refs file at all.\n>\n> I imagine that you're looking at atomicity from the perspective of a\n> reader. In the git.git scheme, the reader may see a half-committed\n> transaction. If you dispense with loose refs entirely and treat the\n> packed-refs file as a single poorly-implemented key/value database, then\n> you get reader atomicity (but O(size_of_database) write performance).\n\nYes, I was hoping for reader atomicity. But I may OK foregoing that if\nthe transaction either all goes through, or all fails. A partially\nstuck transaction because the process died in the middle of the commit\nstep creates a mess for an administrator to undo. Does she rename\n\"foo.lock\" to \"foo\"? Or delete \"foo.lock\"?\n\n\n>> Repositories with many loose references occupy a large number of disk\n>> blocks from the local file system, as each reference is its own file\n>> storing 41 bytes. This negatively affects the number of inodes\n>> available when a large number of repositories are stored on the same\n>> filesystem. Readers are also penalized due to the larger number of\n>> syscalls required to traverse and read the `$GIT_DIR/refs` directory.\n>\n> In my experience, the syscalls involved in loose refs aren't usually a\n> big deal. If you have 800k refs, they're not all changing constantly. So\n> a single pack-refs \"fixes\" performance going forward. What _is_ a big\n> deal is that the packing process is complicated, readers have a very\n> un-atomic view because of the myriad of files involved, and you get\n> annoying lock contention during packing, as well as between deletions\n> that have to rewrite packed-refs.\n>\n> But I'm not sure if you meant to contrast here a system where we didn't\n> use packed-refs at all (though of course such a system is very much not\n> atomic by the definition above).\n\nNo, I really did mean the current system. Gerrit Code Review servers\ncreate a lot of references throughout the day. Its easy to accumulate\na few thousand new loose references in a 24 hour period. Even if you\nhave 600k existing refs in packed-refs, you still have 2k new/modified\nrefs since last nightly cron ran git gc.\n\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>\n> Good goal, though TBH I'd be happy with O(log n).\n>\n> A related one is being able to traverse a subset of refs in\n> O(nr_traversed). E.g., \"git tag -l\" should not have to do work\n> proportional to what is in refs/changes. That falls out of most\n> proposals that allow fast lookups, but notably not a straight\n> hash-table.\n\nThanks, I missed that in this list, even though it was an explicit\nobjective going into this work. I added:\n\n- Efficient lookup of an entire namespace, such as `refs/tags/`.\n\n\n>> - Occupy less disk space for large repositories.\n>\n> Good goal. Just to play devil's advocate, the simplest way to do that\n> with the current code would be to gzip packed-refs (and/or store sha1s\n> as binary). That works against the \"mmap and binary search\" plan,\n> though. :)\n\nYes it does. I tried to cover that later under \"Alternatives\nconsidered > bzip\". :)\n\n\n>> ### Reference name encoding\n>>\n>> Reference names should be encoded with UTF-8.\n>\n> Don't we usually treat refnames as byte sequences (subject to a few\n> rules, as in check_ref_format())? It seems like the encoding should be\n> out-of-scope for the storage format.\n\nTrue that git-core treats them as byte sequences, but JGit treats them as UTF-8.\n\n\n>> ## File format\n>\n> OK, let me try to summarize to see if I understand.\n>\n> The reftable file is a sequence of blocks, each of which contains a\n> finite set of heavily-compressed refs. You have to read each block\n> sequentially, but since they're a fixed size, that's still a\n> constant-time operation (I'm ignoring the \"restarts\" thing for now). You\n> find the right block by reading the index. So lookup really is more\n> like O(block_size * log(n/block_size)), but block_size being a constant,\n> it drops out to O(log n).\n\nYes. My \"near constant time\" claim was because I had my head buried\nthinking about disk IO operations when I wrote this, not the algorithm\nthat happens on the CPU. One of the applications for reftable is on a\nslower-than-usual storage system, where reading a block of a file\ncosts enough milliseconds that it doesn't matter how good or bad the\nCPU algorithm is.\n\n\n> Linear scans are easy, because everything is in sorted order. So you\n> just find the first entry via binary search, and then walk forward.\n\nYup.\n\n\n> Updates are where things get dicier. It looks like you just write a new\n> partial reftable file with your updates. And then if there are N\n> reftables present, readers actually have to do a list-merge of the\n> results they get from all of them (where the results from reftable.5\n> trump ones from reftable.4).\n\nCorrect.\n\n\n> So basically we're just journaling updates into a directory of atomic\n> reftable updates. And then to keep the reader's job from getting too\n> painful, a write occasionally has to compact into a single reftable,\n> rewriting the entire ref store.\n\nCorrect.\n\n\n> That's what I see as the biggest\n> weakness here. If you keep too large a reftable stack, then readers have\n> to spend a lot of extra effort on lookups. But if you keep too small a\n> stack, then you are frequently rewriting the whole database.\n\nBut you say this yourself below, you can do this using a geometric\nscheme or something to bound the cost of these rewrites such that you\naren't frequently rewriting the whole database.\n\n\n> Technically writes are still O(n). Because of the journaling you\n> amortize the whole-rewrite cost across several updates, but it's still\n> O(n/c). That seems like the biggest weakness of the scheme to me.\n>\n> I think there's some cleverness you can use with compacting in a\n> geometric scheme, though, to amortize up to a certain bound. I didn't\n> see any discussion of that, though.\n\nI think I left this as an exercise to the implementer. The\n\"Transactions > Compaction\" section talks about the compaction\nalgorithm being applied only near the top of the stack, ignoring the\nbase table(s).\n\n\n>> Compaction is similar to the update process, but an explicit temporary\n>> file must be used:\n>>\n>> 1. Atomically create `$GIT_DIR/reftable.lock`.\n>> 2. `readdir($GIT_DIR)` to determine the highest suffix ordinal, `n`.\n>> 3. Compute the update transaction (e.g. compare expected values).\n>> 4. Select files from (2) to collapse as part of this transaction.\n>> 5. Create temp file by `mktemp(\"$GIT_DIR/.reftableXXXXXX\")`.\n>> 6. Write modified and collapsed references to temp file.\n>> 7. Rename temp file to `reftable.${n + 1}`.\n>> 8. Delete collapsed files `reftable.${n}`, `reftable.${n - 1}`, ...\n>> 9. Delete `reftable.lock`.\n>\n> I had originally assumed you'd just compact back down to the reftable\n> file after some N updates (say, 10). But here, it looks like you'd\n> always compact 0-9 into 10, and then 10-19 into 20, and so on, and the\n> ordinal would go up forever.\n>\n> I think that's OK, as it would take a long time to get unwieldy. And I\n> think you have to do it that way, as you can't atomically replace\n> \"reftable\" and delete .1-.9 at the same time.\n>\n>> Because `reftable.9` can disappear after `reftable.10` is created,\n>> readers receiving ENOENT when opening `reftable.9` must peform\n>> another readdir to look for new reftables.\n>\n> But after compaction, won't having \"reftable.10\" but no \".9\" be the\n> steady state?\n\nYes, it will be. You'd have maybe \"reftable\" and \"reftable.10\", and\nnothing else.\n\n\n> As a reader, how can I tell the difference between these\n> two cases:\n>\n> 1. Somebody created .10 and deleted .9 and lower.\n>\n> 2. Somebody created .11 and deleted .10 and lower, while I was trying\n> to read .9.\n>\n> Is basically every read going to require:\n>\n> 1. readdir to find the highest ordinal\n>\n> 2. keep walking down the stack until you get ENOENT\n>\n> 3. readdir again to make sure there's not a new ordinal\n>\n> But in that case, if step 3 turns up a new reftable.11, how do I know\n> whether it's a compaction (in which case I need to restart my read from\n> .11) or if it's just another update-on-top? In a busy repository, you\n> might see a lot of update-on-tops.\n\nI think I was imaging updates are less frequent than reads, and a\nreader is going to readdir(), and then immediately open every file in\nthe stack to setup the merge-join iteration. If the reader retains the\nfile descriptor, the reader can keep that file in their stack.\n\nThere is risk of a reader live-locking; the reader might have done a\nreaddir, starts opening the stack, sees ENOENT. In which case the\nreader starts over. If an updater is performing compactions faster\nthan a reader can readdir and open paths, its live-lock for the\nreader. That certainly is one motivation to not always perform a\ncompaction.\n\n\n>> [...specifics...]\n>\n> I liked a lot of what I saw in the rest of it (e.g., handling symrefs,\n> which packed-refs does not). Some bits seemed complicated. E.g., I\n> actually wonder how much restarts help in practice if you have\n> reasonably-sized blocks, and they complicate things a lot).\n\nMy implementation lets me tweak the restart table with a command line\noption, so I was able to run a number of experiments for you. A 64k\nblock doesn't fit more than a few thousand references, so restart 4000\neffectively disables restarts.\n\nblock restart size lookup\n4k 16 29M 90.2 usec\n8k 16 29M 76.4 usec\n\n64k 16 29M 147.7 usec\n64k 64 28M 134.3 usec\n64k 256 27M 143.4 usec\n\n4k 4000 28M 104.0 usec\n8k 4000 28M 117.1 usec\n64k 4000 27M 288.5 usec\n\nTurning off restarts shrinks the file, and increases lookup time.\n\nFor $REASONS, I favor a larger block size in some cases, even though\nthe lookup times get worse. For example, being able to use 64k/64 may\nbe a sweet spot for that particular IO system I mentioned above.\n\nFun fact: gzip packed-refs for this data set is 27M. The 64k/256 is\nonly 432 KiB larger than gzip (default compression).\n\n\n> Likewise\n> some bits are optional for very small reftable files to reduce overhead.\n> But if you have very small reftables, it's going to be fast either way.\n> If you waste 4K to store 200 bytes, that's fine\n\nNot really. I store a lot of very small pack files, the 1k idx v2\nheader is pretty annoying for these. It dwarfs the rest of the\ninformation, in cases it dwarfs the pack file itself. Not being able\nto forgo the fanout table when you have a pack of 4 objects of 3 trees\nand 1 commit is pretty damn annoying.\n\n> as long as you're still\n> wasting only 4K when you store 200 megabytes.\n\nI don't think this is fair. Its better thought of as a ratio.\n\nIt depends on the parameters to the writer, but reftable was \"wasting\"\nanywhere between 20K-44K of NUL byte padding for the various\nexperiments above, and the index was anywhere from 12K-185K, depending\non the block size (smaller block size == larger index).\n\nWasting 44K on padding, 12K on index, to compress 62M down to 27M...\na penalty of 0.2% of that 27M. That seems acceptable.\n\n5 refs in reftable is ~204 bytes, because of the optional features\nbeing disabled on small files. If reftable was forced to fill out to a\nfull 4K block, that is a penalty of 1907%. This might seem like\nnothing, but for cases where the table has to travel on the network,\nor is being stored in a tail-block-optimized filesystem, its a huge\nwaste to pad the file out.\n\n\n> I also realize that beggars can't be choosers. If you have a working\n> system that performs well, I should consider shutting up. :)\n\nI have it in Java for JGit; I don't yet have a C implementation.\n\n\n> One thing I didn't see is reflogs. They don't strictly have to be part\n> of a ref-storage solution. But they do still consume at least one inode\n> per ref in the current system. If you reflog everything, which in my\n> opinion you should. Having an audit trail of ref updates is very useful\n> for debugging (both bugs in Git, and trying to figure out what went\n> wrong when a user goes berserk with \"git push --prune\").\n\nYea, I glossed over that and ignored them. Mostly because one system\nwhere I want to use reftable already has a separate database handling\nthe reflogs. In another (Gerrit Code Review), we disable reflogs for\nthe insane refs/changes/ namespace, as nearly every reference is\ncreated once, and never modified.\n\nOne could abuse the reftable format to store a reflog. If the refname\nfield is just a sequence of bytes, one could store keys like refname +\n'\\0' + timestamp, and reuse the symbolic ref value format to store the\nold/new/message, as its just a length delimited string.\n\nI'm loath to allocate more bits to denote a reflog entry vs. ref entry\nin the same file, but I could see some advantages to that. Commits\nwould only have to write one new reftable for the combined update +\nlog record.\n"},{"id":"324486","messageId":"CAJo=hJv7kaT3m6k1nz1-tGuVAMmgnrS0dcfycGfE3PyXjG3xRA@mail.gmail.com","threadId":"46370","inReplyTo":"20170713203533.vcfyf5iei46g4tcf@sigill.intra.peff.net","subject":"Re: reftable: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-07-14T00:27:44Z","receivedAt":"2017-07-14T00:28:10Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Thu, Jul 13, 2017 at 1:35 PM, Jeff King wrote:\n> On Thu, Jul 13, 2017 at 12:56:54PM -0700, Stefan Beller wrote:\n>\n> I agree that a full binary search of a reftable is harder because of the\n> prefix compression (it may still be possible by scanning backwards, but\n> I think there are ambiguities when you land in the middle of a record,\n> since there's no unambiguous end-of-record character).\n\nIts impossible to safely binary search this reftable format using a\nnaive divide byte count in half and find record boundary approach. I\nactually did design an earlier version of reftable that was safe to\nuse this approach for its binary search within blocks, and wound up\ndiscarding it. It was slower and more complex implementation than the\nformat I shared with the list.\n\n\n> But I don't think\n> it matters. If you binary-search to a constant-sized block, then a\n> linear scan of the block is acceptable.\n\nDepends on the block size. :)\n\n\n> Not that I'm recommending just gzipping the whole packed-refs file. It\n> ruins the fast-lookup.\n\nAs I just mentioned elsewhere in the thread:\n\n src file 65306185\n gzip 28338906\n reftable 28782292\n\nThe reftable format (for 64k block, 256 restart) is within spitting\ndistance (432 KiB) of a default level gzip of packed-refs. We can get\nfast-lookup, and OK compression.\n\n\n> We _could_ consider gzipping individual blocks of\n> a reftable (or any structure that allows you to search to a\n> constant-sized block and do a linear search from there). But given that\n> they're in the same ballpark, I'm happy with whatever ends up the\n> simplest to code and debug. ;)\n\nThis does help to shrink the file, e.g. it drops from 28M to 23M.\n\nIt makes it more CPU costly to access a block, as we have to inflate\nthat to walk through the records. It also messes with alignment. When\nyou touch a block, that may be straddling two virtual memory pages in\nyour kernel/filesystem.\n\nI'm not sure those penalties are worth the additional 16% reduction in size.\n\n\n>> When Shawn presented the proposal, a couple of colleagues here\n>> were as excited as I was, but the daring question is, why Shawn\n>> did not give the whole thing in BNF format from top down:\n>>\n>> initial-block\n>> content-blocks*\n>> (index-block)\n>> footer\n>\n> Yeah, I agree it took me a bit to figure out what was going on. A\n> high-level overview of the format would have been nice.\n\nNoted, I've added this to my writeup.\n"},{"id":"324508","messageId":"CAD0k6qRdq7n=LM7TFJYKvC4uiMMCus8kff-Lm28GiC_G-Feb2Q@mail.gmail.com","threadId":"46370","inReplyTo":"CAJo=hJts=wY4vBaLsOtoH8+LBFK_drBhHMxPvKoQcqtpOfJOog@mail.gmail.com","subject":"Re: reftable: new ref storage format","fromName":"Dave Borowitz","fromEmail":"dborowitz@google.com","sentAt":"2017-07-14T14:27:24Z","receivedAt":"2017-07-14T14:27:56Z","isPatch":false,"sender":{"key":"dborowitz@google.com","avatar":"https://avatars.githubusercontent.com/u/194927?v=4"},"body":"On Thu, Jul 13, 2017 at 8:11 PM, Shawn Pearce wrote:\n> In another (Gerrit Code Review), we disable reflogs for\n> the insane refs/changes/ namespace, as nearly every reference is\n> created once, and never modified.\n\nApologies for the tangent, but this is not true in the most recent\nGerrit implementation. We update refs/changes/CD/ABCD/1 and\nrefs/changes/CD/ABCD/meta in a single BatchRefUpdate, and we set a\nreflog message on the BatchRefUpdate instance, which updates the\nreflog for all refs in the batch. The reflog message on /meta is\nimportant, and arguably it's useful to be able to correlate that with\nthe reflog on /1.\n\nIf you think storing reflogs on patch set refs is going to be a\nproblem wrt on-disk storage, we should discuss this offline :)\n"},{"id":"324532","messageId":"CAJo=hJupQAgYsJfeDhtVDtqoA30OpGiuR5o=ZnuRK3CaGo+ZeQ@mail.gmail.com","threadId":"46370","inReplyTo":"CAD0k6qRdq7n=LM7TFJYKvC4uiMMCus8kff-Lm28GiC_G-Feb2Q@mail.gmail.com","subject":"Re: reftable: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-07-14T15:31:12Z","receivedAt":"2017-07-14T15:31:39Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Fri, Jul 14, 2017 at 7:27 AM, Dave Borowitz wrote:\n> On Thu, Jul 13, 2017 at 8:11 PM, Shawn Pearce wrote:\n>> In another (Gerrit Code Review), we disable reflogs for\n>> the insane refs/changes/ namespace, as nearly every reference is\n>> created once, and never modified.\n>\n> Apologies for the tangent, but this is not true in the most recent\n> Gerrit implementation. We update refs/changes/CD/ABCD/1 and\n> refs/changes/CD/ABCD/meta in a single BatchRefUpdate, and we set a\n> reflog message on the BatchRefUpdate instance, which updates the\n> reflog for all refs in the batch. The reflog message on /meta is\n> important, and arguably it's useful to be able to correlate that with\n> the reflog on /1.\n>\n> If you think storing reflogs on patch set refs is going to be a\n> problem wrt on-disk storage, we should discuss this offline :)\n\nReflog storage is a problem for Gerrit. It was a problem in early 2009\nwhen servers had a lot less changes. Its going to be even more of a\nproblem now. Sounds like we have to support reflogs in reftable, or\nsomething like it.\n"},{"id":"324550","messageId":"20170714200830.iks5drqu72cypkny@sigill.intra.peff.net","threadId":"46370","inReplyTo":"CAJo=hJts=wY4vBaLsOtoH8+LBFK_drBhHMxPvKoQcqtpOfJOog@mail.gmail.com","subject":"Re: reftable: new ref storage format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-07-14T20:08:31Z","receivedAt":"2017-07-14T20:08:39Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jul 13, 2017 at 05:11:52PM -0700, Shawn Pearce wrote:\n\n> Yes, I was hoping for reader atomicity. But I may OK foregoing that if\n> the transaction either all goes through, or all fails. A partially\n> stuck transaction because the process died in the middle of the commit\n> step creates a mess for an administrator to undo. Does she rename\n> \"foo.lock\" to \"foo\"? Or delete \"foo.lock\"?\n\nAgreed, there's no real rollback or recovery process. I do think\nshooting for reader atomicity is worth doing. Lack of atomicity can\ncause odd things to happen with operations like pruning, for example. If\nI'm trying to get a list of all of the reachable objects, for example, I\nmight have to readdir() a bunch of directories (let's forget even that a\nsingle readdir() is not necessarily atomic). If I try to atomically move\n\"refs/heads/z/foo\" to \"refs/heads/a/foo\" there is a reasonable chance\nthat a reader may see only the deletion and not the addition.\n\nI don't have any known cases of this biting anyone, but it's somewhat\nscary.\n\n> > But I'm not sure if you meant to contrast here a system where we didn't\n> > use packed-refs at all (though of course such a system is very much not\n> > atomic by the definition above).\n> \n> No, I really did mean the current system. Gerrit Code Review servers\n> create a lot of references throughout the day. Its easy to accumulate\n> a few thousand new loose references in a 24 hour period. Even if you\n> have 600k existing refs in packed-refs, you still have 2k new/modified\n> refs since last nightly cron ran git gc.\n\nI do think you'd be better served by just calling pack-refs more\nfrequently, then. Nightly is too infrequent for a busy repo. And under\nsomething like reftables, you'd end up doing the equivalent of a\npack-refs every N updates anyway.\n\nWe actually pack refs quite aggressively at GitHub. Way more than I\nwould consider reasonable, but it's never been a big bottleneck, so I've\nnever looked into it. We don't do it for every update, but every update\ntriggers a \"consider syncing objects into shared storage\" job, which\nwill pack the refs. So in a hypothetical repo that's constantly updating\nwe probably pack refs at least once a minute.\n\nBut we're generally on low-latency local disks. It sounds like you\nemphatically are not.\n\n> > Good goal. Just to play devil's advocate, the simplest way to do that\n> > with the current code would be to gzip packed-refs (and/or store sha1s\n> > as binary). That works against the \"mmap and binary search\" plan,\n> > though. :)\n> \n> Yes it does. I tried to cover that later under \"Alternatives\n> considered > bzip\". :)\n\nYeah, sorry, I read and responded to the document a bit out of order. I\nagree it's a dead-end. :)\n\n> >> Reference names should be encoded with UTF-8.\n> >\n> > Don't we usually treat refnames as byte sequences (subject to a few\n> > rules, as in check_ref_format())? It seems like the encoding should be\n> > out-of-scope for the storage format.\n> \n> True that git-core treats them as byte sequences, but JGit treats them as UTF-8.\n\nI think we can probably stick with that, unless the UTF-8ness is really\nimportant? I guess it might matter if it impacts the sorting order.\n\n> Yes. My \"near constant time\" claim was because I had my head buried\n> thinking about disk IO operations when I wrote this, not the algorithm\n> that happens on the CPU. One of the applications for reftable is on a\n> slower-than-usual storage system, where reading a block of a file\n> costs enough milliseconds that it doesn't matter how good or bad the\n> CPU algorithm is.\n\nOK, that explains a lot of the decisions better. If you're planning on\nevolving this proposal document, I think it would make sense to talk\nabout that in the objectives section. (I say \"if\" because I am happy for\nthe mailing list discussion to serve as a rationale document).\n\n> But you say this yourself below, you can do this using a geometric\n> scheme or something to bound the cost of these rewrites such that you\n> aren't frequently rewriting the whole database.\n\nRight, but that sounds like math. I wanted you to spoonfeed me the\ngeometric algorithm (and its bound proof). ;)\n\n> >> Compaction is similar to the update process, but an explicit temporary\n> >> file must be used:\n> >>\n> >> 1. Atomically create `$GIT_DIR/reftable.lock`.\n> >> 2. `readdir($GIT_DIR)` to determine the highest suffix ordinal, `n`.\n> >> 3. Compute the update transaction (e.g. compare expected values).\n> >> 4. Select files from (2) to collapse as part of this transaction.\n> >> 5. Create temp file by `mktemp(\"$GIT_DIR/.reftableXXXXXX\")`.\n> >> 6. Write modified and collapsed references to temp file.\n> >> 7. Rename temp file to `reftable.${n + 1}`.\n> >> 8. Delete collapsed files `reftable.${n}`, `reftable.${n - 1}`, ...\n> >> 9. Delete `reftable.lock`.\n\nI think the \"stack\" implementation is what makes me most uncomfortable\nwith this proposal. Atomicity with filesystem operations and especially\nreaddir() is one of the things I think is most flaky about the current\nsystem. Here's an idea for an alternative implementation.\n\n 1. Write out reftables to files named after the hash of their content\n (e.g., $GIT_DIR/reftables/1234abcd...).\n\n 2. The first block of the each reftable has a backpointer to the\n previous table.\n\n 3. There's a well-known name (e.g., $GIT_DIR/reftable) that represents\n the current state. We update it with the usual .lock/rename dance.\n\nThat gives readers an easy atomic view; once they've called open() on\n\"reftable\", they follow back-pointers instead of computing the names\n(n-1, n-2, etc). They may still find that a compaction has removed a\nfile they need, but:\n\n - they only have to restart due to an actual compaction. They'll never\n be tricked by a regular update.\n\n - you can compact without immediately deleting the old reftables. So\n you might compact, and then delete the reftables N seconds later. Any\n reader which completes the read within N seconds wouldn't have to\n restart.\n\nI think I can anticipate your answer, though. If you have a system where\nthe latency to open and read a file is high, then you've just serialized\nthe latencies as you walk the chain. Whereas with predictable names, you\ncan pre-fetch refname.i through refname.j in parallel.\n\nHow deep would you anticipate stacks getting? Would it be feasible for\nthe tip to contain the names of the tables in the entire chain? If we're\ntalking about 20 (or even 32) bytes per name, you could still fit over a\nhundred names in a 4K inode.\n\nIt doesn't escape me that I'm basically reinventing RefTree here, with\nreftables instead of tree objects. But I think breaking away from using\nreal Git objects opens up a lot of efficiency tricks (like the prefix\ncompression, and the parallel-fetch thing above). And it removes a lot\nof the gc complexity.\n\n> I think I was imaging updates are less frequent than reads, and a\n> reader is going to readdir(), and then immediately open every file in\n> the stack to setup the merge-join iteration. If the reader retains the\n> file descriptor, the reader can keep that file in their stack.\n> \n> There is risk of a reader live-locking; the reader might have done a\n> readdir, starts opening the stack, sees ENOENT. In which case the\n> reader starts over. If an updater is performing compactions faster\n> than a reader can readdir and open paths, its live-lock for the\n> reader. That certainly is one motivation to not always perform a\n> compaction.\n\nI guess I don't have much faith in the atomicity of readdir(). And it\nwould be nice if we could tell the difference between \"oops, reftable.5\nwas racily deleted\" and \"it is not supposed to be there due to a\nprevious compaction\". So I foresee always walking back to 0, stopping at\nthe first ENOENT, and then doing a final readdir() to see if any new\nitems appeared. If one has, we can't tell if it's a compaction in\nprogress or a regular update, and we have to restart.\n\nSo I'm worried about live-locking with a regular updater, not even a\ncompacting one.\n\n> > I liked a lot of what I saw in the rest of it (e.g., handling symrefs,\n> > which packed-refs does not). Some bits seemed complicated. E.g., I\n> > actually wonder how much restarts help in practice if you have\n> > reasonably-sized blocks, and they complicate things a lot).\n> \n> My implementation lets me tweak the restart table with a command line\n> option, so I was able to run a number of experiments for you. A 64k\n> block doesn't fit more than a few thousand references, so restart 4000\n> effectively disables restarts.\n> \n> block restart size lookup\n> 4k 16 29M 90.2 usec\n> 8k 16 29M 76.4 usec\n> \n> 64k 16 29M 147.7 usec\n> 64k 64 28M 134.3 usec\n> 64k 256 27M 143.4 usec\n> \n> 4k 4000 28M 104.0 usec\n> 8k 4000 28M 117.1 usec\n> 64k 4000 27M 288.5 usec\n\nThanks for these numbers. I was really thinking that blocks would be on\nthe order of 4K (where you can see that the restarts help very little).\nFor local disk that's a pretty reasonable size. For high-latency fetches\nto a specialized database, maybe not.\n\n> For $REASONS, I favor a larger block size in some cases, even though\n> the lookup times get worse. For example, being able to use 64k/64 may\n> be a sweet spot for that particular IO system I mentioned above.\n\nRight, that makes a lot more sense.\n\n> > as long as you're still\n> > wasting only 4K when you store 200 megabytes.\n> \n> I don't think this is fair. Its better thought of as a ratio.\n> [...]\n> 5 refs in reftable is ~204 bytes, because of the optional features\n> being disabled on small files. If reftable was forced to fill out to a\n> full 4K block, that is a penalty of 1907%. This might seem like\n> nothing, but for cases where the table has to travel on the network,\n> or is being stored in a tail-block-optimized filesystem, its a huge\n> waste to pad the file out.\n\nYeah, my assumption was that anything under 4K is basically going to\ntake 4K. But I agree it's very dependent on the underlying storage\nmechanism.\n\n> > I also realize that beggars can't be choosers. If you have a working\n> > system that performs well, I should consider shutting up. :)\n> \n> I have it in Java for JGit; I don't yet have a C implementation.\n\nI'm a beggar; I'll take even a well-developed plan. :)\n\nThe implementation on this doesn't seem overly complex. My main concerns\nare what we're asking from the filesystem in terms of atomicity, and\nwhat possible races there are.\n\n> > One thing I didn't see is reflogs. They don't strictly have to be part\n> > of a ref-storage solution. But they do still consume at least one inode\n> > per ref in the current system. If you reflog everything, which in my\n> > opinion you should. Having an audit trail of ref updates is very useful\n> > for debugging (both bugs in Git, and trying to figure out what went\n> > wrong when a user goes berserk with \"git push --prune\").\n> \n> Yea, I glossed over that and ignored them. Mostly because one system\n> where I want to use reftable already has a separate database handling\n> the reflogs. In another (Gerrit Code Review), we disable reflogs for\n> the insane refs/changes/ namespace, as nearly every reference is\n> created once, and never modified.\n\nEven for created-once refs, I've found an audit trail of created when,\nby whom, using what program to be quite valuable. Long ago we tried to\nuse reflogs for that, but these days we literally just write the refname\nand its reflog entry to an \"audit_log\" file. It's not used for\nreachability and it's never pruned. It just grows forever without bound.\n\nI think some variant of that could work for reflog storage (with\nreachability and whole-file-rewrite expiration, obviously). The biggest\ndrawback is that traversing the reflogs for one ref requires walking\nover the entries for all refs. But I'm not sure how much that would hurt\nin practice. Many reflog operations look at all the reflogs anyway\n(e.g., reachability, expiration). And finding the entry for a single ref\n(e.g., ref@{1.day.ago}) is bounded in far back it has to walk.\n\n> One could abuse the reftable format to store a reflog. If the refname\n> field is just a sequence of bytes, one could store keys like refname +\n> '\\0' + timestamp, and reuse the symbolic ref value format to store the\n> old/new/message, as its just a length delimited string.\n\nGross, but it could work. I actually think David's LMDB proposal did\nsomething similar (encoding the entries in the keyname), but I'd have to\ndouble-check.\n\n> I'm loath to allocate more bits to denote a reflog entry vs. ref entry\n> in the same file, but I could see some advantages to that. Commits\n> would only have to write one new reftable for the combined update +\n> log record.\n\nYes, but I'd worry that the reflog entries (which would have to hang\naround in the reftable until being expired) would slow performance for\nnormal ref lookups. In my experience ref lookups are very frequent, and\nreflog lookups are not. It's OK to segment them and have worse\nperformance for the reflogs.\n\n-Peff\n"},{"id":"324551","messageId":"20170714201040.hwrr5gwrc23lp3jt@sigill.intra.peff.net","threadId":"46370","inReplyTo":"CAJo=hJv7kaT3m6k1nz1-tGuVAMmgnrS0dcfycGfE3PyXjG3xRA@mail.gmail.com","subject":"Re: reftable: new ref storage format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-07-14T20:10:41Z","receivedAt":"2017-07-14T20:10:49Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jul 13, 2017 at 05:27:44PM -0700, Shawn Pearce wrote:\n\n> > We _could_ consider gzipping individual blocks of\n> > a reftable (or any structure that allows you to search to a\n> > constant-sized block and do a linear search from there). But given that\n> > they're in the same ballpark, I'm happy with whatever ends up the\n> > simplest to code and debug. ;)\n> \n> This does help to shrink the file, e.g. it drops from 28M to 23M.\n> \n> It makes it more CPU costly to access a block, as we have to inflate\n> that to walk through the records. It also messes with alignment. When\n> you touch a block, that may be straddling two virtual memory pages in\n> your kernel/filesystem.\n> \n> I'm not sure those penalties are worth the additional 16% reduction in size.\n\nYeah, I don't really care about a 16% reduction in size. I care much\nmore about simplicity of implementation and debugging. Using zlib is\nkind-of simple to implement. But if you've ever had to debug it (or\nfigure out what is going on with maybe-corrupted output), it's pretty\nnasty.\n\nSo I don't mind a more readable custom compression if it's not too\ncomplicated. And especially if it buys us extra performance by being\nable to jump around non-sequentially in the block.\n\n-Peff\n"},{"id":"324598","messageId":"CAJo=hJtMo4OSxcYbq4oecTQYnwTR0zK8HgyqVEhOYZ-4eu4S9w@mail.gmail.com","threadId":"46370","inReplyTo":"20170714200830.iks5drqu72cypkny@sigill.intra.peff.net","subject":"Re: reftable: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-07-16T06:01:47Z","receivedAt":"2017-07-16T06:02:15Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Fri, Jul 14, 2017 at 1:08 PM, Jeff King wrote:\n> On Thu, Jul 13, 2017 at 05:11:52PM -0700, Shawn Pearce wrote:\n>\n> I think the \"stack\" implementation is what makes me most uncomfortable\n> with this proposal. Atomicity with filesystem operations and especially\n> readdir() is one of the things I think is most flaky about the current\n> system. Here's an idea for an alternative implementation.\n>\n> 1. Write out reftables to files named after the hash of their content\n> (e.g., $GIT_DIR/reftables/1234abcd...).\n>\n> 2. The first block of the each reftable has a backpointer to the\n> previous table.\n>\n> 3. There's a well-known name (e.g., $GIT_DIR/reftable) that represents\n> the current state. We update it with the usual .lock/rename dance.\n>\n> That gives readers an easy atomic view; once they've called open() on\n> \"reftable\", they follow back-pointers instead of computing the names\n> (n-1, n-2, etc). They may still find that a compaction has removed a\n> file they need, but:\n>\n> - they only have to restart due to an actual compaction. They'll never\n> be tricked by a regular update.\n>\n> - you can compact without immediately deleting the old reftables. So\n> you might compact, and then delete the reftables N seconds later. Any\n> reader which completes the read within N seconds wouldn't have to\n> restart.\n>\n> I think I can anticipate your answer, though. If you have a system where\n> the latency to open and read a file is high, then you've just serialized\n> the latencies as you walk the chain. Whereas with predictable names, you\n> can pre-fetch refname.i through refname.j in parallel.\n>\n> How deep would you anticipate stacks getting? Would it be feasible for\n> the tip to contain the names of the tables in the entire chain? If we're\n> talking about 20 (or even 32) bytes per name, you could still fit over a\n> hundred names in a 4K inode.\n\nI think we'd want to keep the stacks under 32, which is a reasonable\namount of space used in the header of each reftable. I don't have this\nyet in my updated document + implementation, but I'll look at trying\nto add it over the next couple of days. Your idea to hold the explicit\nlist of the stack in each reftable makes for a very safe atomic reader\nview.\n\n\n> It doesn't escape me that I'm basically reinventing RefTree here, with\n> reftables instead of tree objects. But I think breaking away from using\n> real Git objects opens up a lot of efficiency tricks (like the prefix\n> compression, and the parallel-fetch thing above). And it removes a lot\n> of the gc complexity.\n\nYes, I agree. Also RefTree has trouble scaling due to the flat tree\nobject format. It depends on the user to sensibly break up the\nreference space with '/' characters sprinkled about. This reftable\nproposal does not suffer from that limitation, a user can use any\nvalid ref name structuring.\n\n\n> So I'm worried about live-locking with a regular updater, not even a\n> compacting one.\n\nOk. I think your idea of tracking an explicit list of the stack in the\ntop of every reftable solves this in a very neat way, so I'll look to\nswitch to that.\n\n\n>> block restart size lookup\n>> 4k 16 29M 90.2 usec\n>> 8k 16 29M 76.4 usec\n>\n> Thanks for these numbers. I was really thinking that blocks would be on\n> the order of 4K (where you can see that the restarts help very little).\n> For local disk that's a pretty reasonable size. For high-latency fetches\n> to a specialized database, maybe not.\n...\n>> > One thing I didn't see is reflogs. They don't strictly have to be part\n>> > of a ref-storage solution. But they do still consume at least one inode\n>> > per ref in the current system. If you reflog everything, which in my\n>> > opinion you should. Having an audit trail of ref updates is very useful\n>> > for debugging (both bugs in Git, and trying to figure out what went\n>> > wrong when a user goes berserk with \"git push --prune\").\n>>\n>> Yea, I glossed over that and ignored them. Mostly because one system\n>> where I want to use reftable already has a separate database handling\n>> the reflogs. In another (Gerrit Code Review), we disable reflogs for\n>> the insane refs/changes/ namespace, as nearly every reference is\n>> created once, and never modified.\n>\n> Even for created-once refs, I've found an audit trail of created when,\n> by whom, using what program to be quite valuable.\n\nDave Borowitz agrees with you, Gerrit Code Review should be recording\nreflog data, even for create-once refs. Its a limitation of the\ncurrent $GIT_DIR/logs that has forced it to be disabled. I'd really\nlike something like reftable, so we can record reflog.\n\n\n>> One could abuse the reftable format to store a reflog. If the refname\n>> field is just a sequence of bytes, one could store keys like refname +\n>> '\\0' + timestamp, and reuse the symbolic ref value format to store the\n>> old/new/message, as its just a length delimited string.\n>\n> Gross, but it could work. I actually think David's LMDB proposal did\n> something similar (encoding the entries in the keyname), but I'd have to\n> double-check.\n\nI added log support to the reftable format. I updated [1] to reflect\nlog blocks at the end of the file. I ran a year's worth of log\nrecords, 149,932 log entries on 43,061 refs to test:\n\nformat size\n$GIT_DIR/logs 173 M\nreftable 4 M (avg 30 bytes)\n\n[1]: https://googlers.googlesource.com/sop/jgit/+/reftable/Documentation/technical/reftable.md\n\nreftable gets these kinds of savings by packing many logs into a\nsingle file (so no disk block overheads), clustering log records by\nref name, prefix compressing, and deflating log records using 128k\ninput blocks. I'm OK with using deflate for log records (and bigger\nblock sizes), as log records are infrequently accessed compared to\ncurrent refs.\n\nThere is a log index to perform efficient point-in-time lookup for a\nsingle ref, and then iterate over its log records from that time, and\nolder. That answers most reflog queries quickly. Large batch log reads\nlike gc reachability can simply iterate through all log records,\nclustered by ref, ordered by time descending.\n"},{"id":"324599","messageId":"4dbe06d0-9a65-7bf5-eb82-6371d9ad7e9b@kdbg.org","threadId":"46370","inReplyTo":"20170714200830.iks5drqu72cypkny@sigill.intra.peff.net","subject":"Re: reftable: new ref storage format","fromName":"Johannes Sixt","fromEmail":"j6t@kdbg.org","sentAt":"2017-07-16T08:07:57Z","receivedAt":"2017-07-16T08:08:07Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 14.07.2017 um 22:08 schrieb Jeff King:\n> The implementation on this doesn't seem overly complex. My main concerns\n> are what we're asking from the filesystem in terms of atomicity, and\n> what possible races there are.\n\nOne of the failure modes is that on Windows a file cannot be deleted \nwhile it is open in any process. It can happen that a compacting updater \nwants to remove a reftable file that is still open in a reader.\n\n-- Hannes\n"},{"id":"324600","messageId":"20170716100141.h4skqqod6lq5s5cc@sigill.intra.peff.net","threadId":"46370","inReplyTo":"CAJo=hJtMo4OSxcYbq4oecTQYnwTR0zK8HgyqVEhOYZ-4eu4S9w@mail.gmail.com","subject":"Re: reftable: new ref storage format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-07-16T10:01:41Z","receivedAt":"2017-07-16T10:01:48Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Jul 15, 2017 at 11:01:47PM -0700, Shawn Pearce wrote:\n\n> > How deep would you anticipate stacks getting? Would it be feasible for\n> > the tip to contain the names of the tables in the entire chain? If we're\n> > talking about 20 (or even 32) bytes per name, you could still fit over a\n> > hundred names in a 4K inode.\n> \n> I think we'd want to keep the stacks under 32, which is a reasonable\n> amount of space used in the header of each reftable. I don't have this\n> yet in my updated document + implementation, but I'll look at trying\n> to add it over the next couple of days. Your idea to hold the explicit\n> list of the stack in each reftable makes for a very safe atomic reader\n> view.\n\nGreat. I was thinking about this a bit and have one more possible\ntweak.\n\nIf you store the names of the dependent reftables in each table, then\nyou end up using storage quadratic in the size of the stack. Because\nthe bottom-most table has 0 pointers, then the next one has 1, and then\nnext one has 2, and so on, until the nth one has n.\n\nNow we're talking about n=32 here, so that's probably OK.\n\nBut one variant is that the reftables _don't_ know about their\nancestors. Instead, the list of reftables is kept in a top-level pointer\nfile, and it's that pointer file which is rewritten on update. I.e., a\nwrite is something like:\n \n 1. Take reftable.lock\n\n 2. Write reftables/1234abcd to represent your update.\n\n 3. Copy the old reftable to reftable.lock, then append \"1234abcd\".\n\n 4. Atomic rename into place.\n\nAnd the reader is just:\n\n 1. Open reftable, read the list of tables.\n\n 2. In parallel, open/fetch each of the tables and find your starting\n pointer for iteration/lookup.\n\n 3. Do a list-merge on the open tables.\n\nThe one thing you lose is that \"unreachable\" reftables no longer form a\nmeaningful hierarchy. With the pointers inside the reftables themselves,\nif your \"reftable\" file got corrupted, you could find the dangling table\nat the apex of the graph and have a good guess at the ref state.\nWithout, you just have a jumble of states and you don't know which takes\nprecedence (though you could probably make a good guess from mtimes).\n\n> I added log support to the reftable format. I updated [1] to reflect\n> log blocks at the end of the file. I ran a year's worth of log\n> records, 149,932 log entries on 43,061 refs to test:\n\nCool. I'll be on vacation for the next week, so apologies if I don't\nkeep the discussion going. But I'm very excited about the overall\ndirection. :)\n\n-Peff\n"},{"id":"324601","messageId":"20170716100321.3jj4pdz7jqoa3dr4@sigill.intra.peff.net","threadId":"46370","inReplyTo":"4dbe06d0-9a65-7bf5-eb82-6371d9ad7e9b@kdbg.org","subject":"Re: reftable: new ref storage format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-07-16T10:03:21Z","receivedAt":"2017-07-16T10:03:27Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Jul 16, 2017 at 10:07:57AM +0200, Johannes Sixt wrote:\n\n> Am 14.07.2017 um 22:08 schrieb Jeff King:\n> > The implementation on this doesn't seem overly complex. My main concerns\n> > are what we're asking from the filesystem in terms of atomicity, and\n> > what possible races there are.\n> \n> One of the failure modes is that on Windows a file cannot be deleted while\n> it is open in any process. It can happen that a compacting updater wants to\n> remove a reftable file that is still open in a reader.\n\nGood point. I think the explicit pointers I mentioned are an improvement\nthere, because a compacting updater _can_ leave the file in place if the\ndelete fails (and later, another compaction can clean up cruft that was\nleft).\n\nI assume that's more or less how pack deletion works on Windows.\n\n-Peff\n"},{"id":"324602","messageId":"4c2b03e6-cd29-6dec-e816-ce2c847355c4@kdbg.org","threadId":"46370","inReplyTo":"20170716100321.3jj4pdz7jqoa3dr4@sigill.intra.peff.net","subject":"Re: reftable: new ref storage format","fromName":"Johannes Sixt","fromEmail":"j6t@kdbg.org","sentAt":"2017-07-16T10:10:29Z","receivedAt":"2017-07-16T10:10:37Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 16.07.2017 um 12:03 schrieb Jeff King:\n> On Sun, Jul 16, 2017 at 10:07:57AM +0200, Johannes Sixt wrote:\n> \n>> Am 14.07.2017 um 22:08 schrieb Jeff King:\n>>> The implementation on this doesn't seem overly complex. My main concerns\n>>> are what we're asking from the filesystem in terms of atomicity, and\n>>> what possible races there are.\n>>\n>> One of the failure modes is that on Windows a file cannot be deleted while\n>> it is open in any process. It can happen that a compacting updater wants to\n>> remove a reftable file that is still open in a reader.\n> \n> Good point. I think the explicit pointers I mentioned are an improvement\n> there, because a compacting updater _can_ leave the file in place if the\n> delete fails (and later, another compaction can clean up cruft that was\n> left).\n\nYes, I think so, too. The pointers make things so much simpler.\n\n> I assume that's more or less how pack deletion works on Windows.\n\nCorrect.\n\n-- Hannes\n"},{"id":"324629","messageId":"CAMy9T_GsgDewHhe1heH7t2qPZuE3XQOKzoxc50-fLmOqm=6ZzQ@mail.gmail.com","threadId":"46370","inReplyTo":"CAJo=hJtyof=HRy=2sLP0ng0uZ4=S-DpZ5dR1aF+VHVETKG20OQ@mail.gmail.com","subject":"Re: reftable: new ref storage format","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-07-16T17:33:55Z","receivedAt":"2017-07-16T17:34:08Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Thanks for your reftable proposal. It would solve a lot of scalability\nproblems that we currently have, and do it in a way that is\nimplementable in both C and Java, which is very nice.\n\nThere are two mostly orthogonal components to your proposal:\n\n1. What does a single reftable file look like?\n2. How can multiple reftable files be used together to avoid having to\nrewrite data more than necessary?\n\nFor example (just for the sake of argument), many of the goals could\nbe achieved by stacking traditional packed-refs files together (i.e.,\ncomponent 2 of your proposal), with the single extension that a\npacked-refs file can assign some \"nil\" value to a reference to\nindicate that the reference has been deleted. As long as references\nare sought in packed-refs files using binary search, lookup and\niteration would both be O(n + lg N) (where N is the total number of\nreferences and n is the number being iterated over), and updates would\n(I think) be amortized O(n), where n is the number of references being\nupdated or deleted. Stacked packed-refs files would, of course, not\nyield the compression benefits of your reftable proposal.\n\nOverall comments/questions:\n\n* Do you propose to store *all* references (i.e., including the\nreferences that we call pseudorefs, like `HEAD`, `FETCH_HEAD`, etc) in\nreftables, or only the references under `refs/`? If the former, then\nyou need to consider that some pseudorefs contain additional\ninformation besides the SHA-1 or linked-to reference. If the latter,\nthen you could get some additional compression by making the `refs/`\nprefix implicit rather than storing it in the \"restart\" records\nexplicitly.\n\n Personally, I don't think it makes sense to store pseudorefs in\nreftables. HEAD, though it doesn't include any supplemental\ninformation, is read so frequently that it seems like a bad idea to\nhave to go through the lookup process rather than storing it in a\nseparate flat file. Moreover, HEAD is written very *infrequently*, so\n(absent special treatment) it would tend to sink deep in the reftable\nstack, making reads even more expensive.\n\n* You have obviously designed your proposal to be friendly to whatever\nnon-local storage system you are using at Google. It would probably\nhelp us understand your design tradeoffs better if you could tell us a\nlittle about that storage system.\n\nSo let's examine the components one after the other...\n\n1. The structure of a single reftable file\n\n* You use int32 and int24 values in a number of places. Couldn't these\nbe uint32 and uint24?\n\n* You use int32 values in a number of places where a smaller size\nwould suffice. For example, the block size is limited to 24 bits, so\nsurely restart_offset, record_end_offset, and number_of_restarts\nneedn't be larger than 24 bits?\n\n OK, actually the *index* block size is not limited to 24 bits, so\nit's not a no-brainer.\n\n* I'm a little bit concerned that the structure is fixed to be a one-\nor two-level indexing scheme; i.e., the (optional) index block plus\nthe restart index table within a block. This forces (as I understand\nit) the block size to be chosen based on the overall file size to\nprevent the index block from becoming too large, whereas for a\nlow-latency local filesystem implementation like SSDs it would\nprobably be preferable to set the block size to agree with the page\nsize to minimize reads and memory usage.\n\n So I ask myself whether it might be worthwhile to allow deeper\nlevels of indexing. The main index block could divide the namespace\ninto as many segments as fit in one block, but if necessary point at a\nsecond-level index block that further divides the namespace before\npointing at the ref block that ultimately contains the value. Those of\nus using local SSDs might tune the system to use 4k block sizes\nthroughout, basically preferring to read three or even four disjoint\n4k blocks rather than two disjoint 64k blocks.\n\n* The tuning parameter number_of_restarts currently trades off space\n(for the full refnames and the restart_offsets) against the need to\nread and parse more ref_records to get the full refnames. ISTM that\nthis tradeoff could be made less painful by defining a blockwide\nprefix that is omitted from the refnames as used in the restarts. So\nthe full refname would change from\n\n this_name = prior_name[0..prefix_length] + suffix\n\n to\n\n this_name = block_prefix + prior_name[0..prefix_length] + suffix\n\n I would expect this to allow more frequent restarts at lower space\ncost. Combining this idea with the previous idea, non-top-level index\nblocks could also have a block_prefix to make their restarts cheaper,\ntoo.\n\n If we are willing to force all reads to consider the indexes, the\nblock_prefix could be taken from the index_record that points at it.\n\n* Does the format need to insist on fixed-size blocks? The alternative\nwould be to allow index_records to point at arbitrary offsets in the\nfile. Admittedly, the file offsets would take more bits to store them\nthan the block_idx. But it would allow the blocks to be matched better\nto the logical structure of the refs namespace, making the\nblock_prefix work better and making it easier to find a particular\nnamespace in one jump. For example, you could add an extra top-level\nindex entry for the HEAD branch, on the assumption that it will be\nread frequently. You could also add an entry for `refs/replace`, which\nis read for almost every command invocation. You could even add an\nentry for `refs/replace` and an entry for the first reference\nfollowing `refs/replace`, which would allow the client to determine\nthat there are zero `refs/replace` references (the usual case) from\nthe top-level index alone by seeing that the two offsets are\nidentical.\n\n BTW, just because the file format doesn't insist on fixed-size\nblocks wouldn't mean that particular implementations couldn't choose\nto write fixed-size blocks, as your implementation might do. If this\nis an important use case, the extra bits needed to store arbitrary\nfile offsets could be avoided by allowing a filewide offset_multiplier\nto be defined.\n\n* What is the rationale for the footer? Is it important for the file\nto be written as a stream, as opposed to seeking back to the beginning\nof the file to add the index_size there? The CRC, I suppose, is meant\nto make it possible to detect a file that has been truncated\naccidentally?\n\n2. The stacking of multiple reftable files together\n\n* I like the ideas later in the thread to have a file of pointers to\nthe files that make up the stack. (I think of it as a \"table of\ncontents\"). I think without it there will be unavoidable races\ninvolving readdir().\n\n* The spec should describe the protocol for reading references. The\nonly interesting thing here is that\n\n* I think that geometric repacking of reftable files will be essential\nto performance for very active repositories with many references, and\nthat the steady state of such a repository will involve O(lg N)\nretable files.\n\n* I would like to propose adding another design goal: that reference\nrepacking can be done without blocking other *writers* (let alone\nreaders, obviously). I think that something like this could work:\n\n Suppose the stack currently consists of reftable files (from oldest\nto newest) A, B, C, and D, with table-of-contents file reftable. If I\nwant to repack files B and C together, then I\n\n * Obtain lock reftable.lock and read the file.\n * Obtain locks B.lock and C.lock. My ownership of these locks\nprevents other processes from trying to repack these files.\n * Release reftable.lock.\n * Repack B and C into a new file, X.lock.\n * Obtain lock reftable.lock.\n * Verify that B, and C are still in the stack, in that order. This\nshould always be the case, assuming that other processes are adhering\nto the locking protocol.\n * Rename X.lock to X.\n * Write the new stack to reftable.lock, replacing B and C with X.\n * Rename reftable.lock on top of reftable.\n * Delete B and C (perhaps after a short sleep to avoid forcing\nreaders to backtrack).\n\n I think that this algorithm would allow reference updates to\ncontinue while the repack is happening, and would even allow reftables\nhigher or lower in the stack than B and C to be repacked at the same\ntime (though maybe that won't be necessary).\n\n* A very frequent operation will be to read a single reference. This\ncould get expensive if a reftable stack grows deep, because every\nsingle reftable might have to be inspected. One way to reduce this\ncost might be to store a bloom filter in large reftable files. This\ncould allow a quick determination that the file doesn't contain the\nreference being sought.\n\nI haven't reviewed your proposal for storing reflogs in reftables in\nany detail, though I must say that my first reaction is surprise that\nyou want to store reflogs (which are mostly immutable, rarely read,\nand can be an order of magnitude bigger) in the same files as\nreferences.\n\nMichael\n\nOn Wed, Jul 12, 2017 at 5:17 PM, Shawn Pearce wrote:\n> We've been having scaling problems with insane number of references\n> (>866k), so I started thinking a lot about improving ref storage.\n>\n> I've written a simple approach, and implemented it in JGit.\n> Performance is promising:\n>\n> - 62M packed-refs compresses to 27M\n> - 42.3 usec lookup\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> ## Overview\n>\n> ### Problem statement\n>\n> Some repositories contain a lot of references (e.g. android at 866k,\n> rails at 31k). The existing packed-refs format takes up a lot of\n> space (e.g. 62M), and does not scale with additional references.\n> Lookup of a single reference requires linearly scanning the file.\n>\n> Atomic pushes modifying multiple references require copying the\n> entire packed-refs file, which can be a considerable amount of data\n> moved (e.g. 62M in, 62M out) for even small transactions (2 refs\n> modified).\n>\n> Repositories with many loose references occupy a large number of disk\n> blocks from the local file system, as each reference is its own file\n> storing 41 bytes. This negatively affects the number of inodes\n> available when a large number of repositories are stored on the same\n> filesystem. Readers are also penalized due to the larger number of\n> syscalls required to traverse and 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> - Occupy less disk space for large repositories.\n> - Support atomic pushes with lower copying penalities.\n>\n> ### Description\n>\n> A reftable file is a portable binary file format customized for\n> reference storage. References are sorted, enabling linear scans,\n> binary search lookup, and range scans.\n>\n> Storage in the file is organized into blocks. Prefix compression\n> is used within a single block to reduce disk space. Block size is\n> tunable by the writer.\n>\n> ### Performance\n>\n> Space used, packed-refs vs. reftable:\n>\n> repository | packed-refs | reftable | % original | avg ref\n> -----------|------------:|---------:|-----------:|---------:\n> android | 62.2 M | 27.7 M | 44.4% | 33 bytes\n> rails | 1.8 M | 896.2 K | 47.6% | 29 bytes\n> git | 78.7 K | 27.9 K | 40.0% | 43 bytes\n> git (heads)| 332 b | 204 b | 61.4% | 34 bytes\n>\n> Scan (read 866k refs) and lookup (single ref from 866k refs):\n>\n> format | scan | lookup\n> ------------|--------:|---------------:\n> packed-refs | 380 ms | 375420.0 usec\n> reftable | 125 ms | 42.3 usec\n>\n> ## Details\n>\n> ### Peeling\n>\n> References in a reftable are always peeled.\n>\n> ### Reference name encoding\n>\n> Reference names should be encoded with UTF-8.\n>\n> ### Ordering\n>\n> Blocks are lexicographically ordered by their first reference.\n>\n>\n> ## File format\n>\n> ### Header\n>\n> A 8-byte header appears at the beginning of each file:\n>\n> - 4-byte magic is: `\\'1', 'R', 'E', 'F'`\n> - 1-byte version number, `1`.\n> - 3-byte `block_size` in bytes (network byte order).\n>\n> ### Block size\n>\n> The `block_size` is arbitrarily determined by the writer, and does not\n> have to be a power of 2. The block size must be larger than the\n> longest reference name used in the repository, as references cannot\n> span blocks.\n>\n> ### First block\n>\n> The first block shares the same block as the file header, and is 8\n> bytes smaller than all other blocks in the file. The first block\n> immediately begins after the file header, at offset 8.\n>\n> ### Block format\n>\n> A block is written as:\n>\n> ref_record*\n> padding?\n> int32( restart_offset )*\n> int32( record_end_offset )\n> int32( number_of_restarts )\n>\n> Blocks begin with a variable number of `ref_record`, describing\n> reference names and values. The format is described below.\n>\n> The middle of the record may be filled with `padding` NUL bytes to\n> fill out the block to the common `block_size` as specified in the file\n> header. Padding may be necessary to ensure `number_of_restarts`\n> occupies the last 4 bytes of the block. Padding may be omitted if the\n> block is the last block of the file, and there is no index block.\n> This allows reftable to efficiently scale down to a small number of\n> refs.\n>\n> A variable number of 4-byte, network byte order `restart_offset`\n> values follows the padding. Offsets are relative to the start of the\n> block and refer to the first byte of any `ref_record` whose name has\n> not been prefixed compressed. Readers can start linear scans from any\n> of these records.\n>\n> The 4-byte, network byte order `record_end_offset` follows, providing\n> the block-relative offset after the end of the last `ref_record`. If\n> `padding` is present this is the offset of the first byte of padding,\n> or the first byte of the first `restart_offset` entry.\n>\n> The 4-byte, network byte order `number_of_restarts` stores the number\n> of entries in the `restart_offset` list. Readers can use the restart\n> count to binary search between restarts before starting a linear scan.\n> This field must be the last 4 bytes of the block; the `padding` field\n> must be used to ensure this is true.\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> varint( (suffix_length << 2) | 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 second varint carries both `suffix_length` and `type`. The\n> `suffix_length` value provides the number of bytes to copy from\n> `suffix` to complete the reference name.\n>\n> The `value` immediately follows. Its format is determined by `type`,\n> a 2 bit code, one of 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`: symbolic reference: `varint( target_len ) target`\n>\n> Symbolic references use a varint length followed by a variable number\n> of bytes to encode the complete reference target. No compression is\n> applied to the target name.\n>\n> ### Index block\n>\n> The index stores the name of the last reference from every block in\n> the file, enabling constant O(1) disk seeks for all lookups. Any\n> reference can be found by binary searching the index, identifying the\n> containing block, and searching within that block.\n>\n> If present, the index block appears after the last block of the file.\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, and\n> binary searching <= 4 blocks also requires <= 2 reads. Omitting the\n> index block from smaller files saves space.\n>\n> Index block format:\n>\n> '\\1' 'i'\n> index_record*\n> int32( restart_offset )*\n> int32( record_end_offset )\n> int32( number_of_restarts )\n>\n> Index blocks begin with a magic prefix, `\\1i`, where other blocks\n> would have started with `\\0` for the first ref record's prefix length.\n> This supports stopping sequential scans at the index block, without\n> prior knowledge of its position.\n>\n> Unlike other blocks, the index block is not padded.\n>\n> The `restart_offset`, `record_end_offset`, and `number_of_restarts`\n> fields are identical in format, meaning and usage as in `ref_record`.\n>\n> To reduce the number of reads required for random access in very large\n> files, the index block may be larger than the other blocks. However,\n> readers must hold the entire index in memory to benefit from this, so\n> its a time-space tradeoff in both file size, and reader memory.\n> Increasing the block size in the writer decreases the index size.\n>\n> #### index record\n>\n> An index record describes the last reference of another block.\n> Index records are written as:\n>\n> varint( prefix_length )\n> varint( (suffix_length << 2) )\n> suffix\n> varint( block_idx )\n>\n> Index records use prefix compression exactly like `ref_record`. The\n> `suffix_length` is shifted 2 bits without a `type` to simplify unified\n> reader/writer code for both block types.\n>\n> Index records store `block_idx` after the suffix, specifying which\n> block of the file ends with this reference. The block is located at\n> position `block_idx * block_size`.\n>\n> ### Reading the index\n>\n> Readers loading the index must first read the footer (below) to\n> determine `index_size`. The index is located at position:\n>\n> file_length - (index_size + 16)\n>\n> ### Footer\n>\n> After the last block of the file (or index block, if present), a file\n> footer is written. This is similar in structure to the file header,\n> but extended with additional data.\n>\n> A 16-byte footer appears at the end:\n>\n> - 4-byte magic is: `\\'1', 'R', 'E', 'F'`\n> - 1-byte version number, 1.\n> - 3-byte `block_size` in bytes (network byte order).\n> - 4-byte `index_size` in bytes (network byte order).\n> - 4-byte CRC-32 of the preceding 12 bytes (network byte order).\n>\n> Like the index block magic header, the footer begins with `\\1R` to\n> allow sequential scans to recognize the end of file has been reached.\n>\n> #### Reading the footer\n>\n> Readers must seek to `file_length - 16` to access the footer. A\n> trusted 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 12 bytes read\n>\n> Once verified, the `block_size` and `index_size` may be accessed from\n> the footer.\n>\n> ### Varint encoding\n>\n> Varint encoding is identical to the ofs-delta encoding method used\n> within pack files.\n>\n> Decoder works such as:\n>\n> val = buf[ptr] & 0x7f\n> while (buf[ptr] & 0x80) {\n> ptr++\n> val++\n> val = val << 7\n> val = val | (buf[ptr] & 0x7f)\n> }\n>\n> ### Binary search\n>\n> Binary search within a block is supported by the `restart_offset`\n> fields at the end of the block. Readers can binary search through the\n> restart table to locate between which two restart points the sought\n> reference should appear.\n>\n> Each reference identified by a `restart_offset` stores the complete\n> reference name in the `suffix` field of the `ref_record`, making the\n> compare operation during the binary search straightforward.\n>\n> Once a restart point lexicographically before the sought reference has\n> been identified, readers can linearly scan through the following\n> `ref_record` entries to locate the sought reference, stopping when the\n> current `ref_record` sorts after (and therefore the sought reference\n> is not present).\n>\n> #### Restart point selection\n>\n> Writers determine the restart points at file creation. The process is\n> arbitrary, but every 16 or 64 references is recommended. Every 16 may\n> be more suitable for smaller block sizes (4k or 8k), every 64 for\n> larger block sizes (64k).\n>\n> More frequent restart points reduces prefix compression and increases\n> space consumed by the restart table, both of which will increase the\n> overall file size.\n>\n> Less frequent restart points makes prefix compression more effective,\n> decreasing overall file size, with increased penalities for readers\n> who must walk through more references after the binary search step.\n>\n> ## Considerations\n>\n> ### Lightweight refs dominate\n>\n> The reftable format assumes the vast majority of references are single\n> SHA-1 valued with common prefixes, such as Gerrit Code Review's\n> `refs/changes/` namespace, GitHub's `refs/pulls/` namespace, or many\n> lightweight tags in the `refs/tags/` namespace.\n>\n> Annotated tags storing the peeled object cost only an additional 20\n> bytes per reference.\n>\n> ### Low overhead\n>\n> A reftable with very few references (e.g. git.git with 5 heads) uses\n> only 204 bytes for reftable vs. 332 bytes for packed-refs. This\n> supports reftable scaling down, to be used for transaction logs\n> (below).\n>\n> ### Block size\n>\n> For a Gerrit Code Review type repository with many change refs, larger\n> block sizes (64 KiB) and less frequent restart points (every 64) yield\n> better compression due to more references within the block able to\n> compress against the prior reference.\n>\n> Larger block sizes reduces the index size, as the reftable will\n> require fewer blocks to store the same number of references.\n>\n> ### Minimal disk seeks\n>\n> Assuming the index block has been loaded into memory, binary searching\n> for any single reference requires exactly 1 disk seek to load the\n> containing block.\n>\n> ## Repository format\n>\n> When reftable is stored in a file-backed Git repository, the stack is\n> represented as a series of reftable files:\n>\n> $GIT_DIR/reftable\n> $GIT_DIR/reftable.1\n> $GIT_DIR/reftable.2\n> $GIT_DIR/reftable.3\n> ...\n> $GIT_DIR/reftable.10\n>\n> where a larger suffix ordinal indicates a more recent table.\n>\n> ### Transactions\n>\n> Although reftables are immutable, they can be stacked in a search\n> pattern, with each reference transaction adding a new reftable to the\n> top of the stack. Readers scan down the reftable stack from\n> most-recent (`reftable.10`) to the base file (`reftable`).\n>\n> ### Update process\n>\n> Updating references follows an update protocol:\n>\n> 1. Atomically create `$GIT_DIR/reftable.lock`.\n> 2. `readdir($GIT_DIR)` to determine the highest suffix ordinal, `n`.\n> 3. Compute the update transaction (e.g. compare expected values).\n> 4. Write only modified references as a reftable to `reftable.lock`.\n> 5. Rename `reftable.lock` to `reftable.${n + 1}`.\n>\n> Because a single `reftable.lock` file is used to manage locking, the\n> repository is single-threaded for writers. Writers may have to\n> busy-spin (with some small backoff) around creating `reftable.lock`,\n> for up to an acceptable wait period, aborting if the repository is too\n> busy to mutate. Application servers wrapped around repositories (e.g.\n> Gerrit Code Review) can layer their own in memory thread lock/wait\n> queue to provide fairness.\n>\n> ### Reference deletions\n>\n> Deletion of any reference can be explicitly stored by setting the\n> `type` to `0x0` and omitting the `value` field of the `ref_record`.\n> This entry shadows the reference in lower files in the stack.\n>\n> ### Compaction\n>\n> A stack of reftables can be compacted by merging references using a\n> straightforward merge join across all reftables, selecting the most\n> recent value for output, and omitting deleted references that do not\n> appear in remaining, lower reftables.\n>\n> The stack can be collapsed as part of any update transaction. If the\n> current number of files is larger than a threshold (e.g. 4), writers\n> can perform an lstat(2) on each reftable file to determine how many\n> bytes would have to be read/copied from an existing file into the\n> new file, enabling deletion of the existing file.\n>\n> Writers can select to collapse the most recent files (e.g. 10, 9, 8,\n> ...), up to a collapse IO threshold (e.g. 4 MiB). Each file selected\n> for collapse must have its references merged into the new reftable\n> that is being prepared.\n>\n> Compaction is similar to the update process, but an explicit temporary\n> file must be used:\n>\n> 1. Atomically create `$GIT_DIR/reftable.lock`.\n> 2. `readdir($GIT_DIR)` to determine the highest suffix ordinal, `n`.\n> 3. Compute the update transaction (e.g. compare expected values).\n> 4. Select files from (2) to collapse as part of this transaction.\n> 5. Create temp file by `mktemp(\"$GIT_DIR/.reftableXXXXXX\")`.\n> 6. Write modified and collapsed references to temp file.\n> 7. Rename temp file to `reftable.${n + 1}`.\n> 8. Delete collapsed files `reftable.${n}`, `reftable.${n - 1}`, ...\n> 9. Delete `reftable.lock`.\n>\n> Because `reftable.9` can disappear after `reftable.10` is created,\n> readers receiving ENOENT when opening `reftable.9` must peform\n> another readdir to look for new reftables.\n>\n> Rebuilding the base `$GIT_TABLE/reftable` follows the same protocol,\n> except in step 7 the temp file is renamed to `reftable`, and step 8\n> removes all files with an ordinal suffix.\n>\n> ## Alternatives considered\n>\n> ### bzip packed-refs\n>\n> `bzip2` can significantly shrink a large packed-refs file (e.g. 62\n> MiB compresses to 23 MiB, 37%). However the bzip format does not support\n> random access to a single reference. Readers must inflate and discard\n> while performing a linear scan.\n>\n> Breaking packed-refs into chunks (individually compressing each chunk)\n> would reduce the amount of data a reader must inflate, but still\n> leaves the problem of indexing chunks to support readers efficiently\n> locating the correct chunk.\n>\n> Given the compression ratios achieved by reftable's simple encoding\n> (e.g. 44%), without using a standard compression algorithm, it does\n> not seem 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\n> references inside Git tree objects stored as part of the repository's\n> object database.\n>\n> The RefTree format adds additional load on the object database storage\n> layer (more loose objects, more objects in packs), and relies heavily\n> on the packer's delta compression to save space. Namespaces which are\n> flat (e.g. thousands of tags in refs/tags) initially create very\n> large loose objects, and so RefTree does not address the problem of\n> copying many references to modify a handful.\n>\n> Flat namespaces are not efficiently searchable in RefTree, as tree\n> objects in canonical formatting cannot be binary searched. This fails\n> the need to handle a large number of references in a single namespace,\n> such 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>\n> David Turner proposed [using LMDB][dt-lmdb], as LMDB is lightweight\n> (64k of runtime code) and GPL-compatible license.\n>\n> A downside of LMDB is its reliance on a single C implementation. This\n> makes embedding inside JGit (a popular reimplemenation of Git)\n> difficult, and hositing onto virtual storage (for JGit DFS) virtually\n> impossible.\n>\n> A 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>\n> Version will bump (e.g. 2) to indicate `value` uses a different\n> object id length other than 20. The length could be stored in an\n> expanded file header, or hardcoded as part of the version.\n"},{"id":"324632","messageId":"CAJo=hJv36tYuxHuso7NrPkfE9hApGfn=iP8g_8+MeM8L91h09g@mail.gmail.com","threadId":"46370","inReplyTo":"CAMy9T_GsgDewHhe1heH7t2qPZuE3XQOKzoxc50-fLmOqm=6ZzQ@mail.gmail.com","subject":"Re: reftable: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-07-16T19:43:59Z","receivedAt":"2017-07-16T19:44:26Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Sun, Jul 16, 2017 at 10:33 AM, Michael Haggerty wrote:\n> Thanks for your reftable proposal.\n\nThanks for your time reading the proposal. I really was looking\nforward to your insights on this project.\n\n> It would solve a lot of scalability\n> problems that we currently have, and do it in a way that is\n> implementable in both C and Java, which is very nice.\n>\n> There are two mostly orthogonal components to your proposal:\n>\n> 1. What does a single reftable file look like?\n> 2. How can multiple reftable files be used together to avoid having to\n> rewrite data more than necessary?\n>\n> For example (just for the sake of argument), many of the goals could\n> be achieved by stacking traditional packed-refs files together (i.e.,\n> component 2 of your proposal),\n\nAgreed. I actually started from stacked packed-refs as the format\nproposal and iterated on that several times before starting to draft\nreftable. I like that packed-refs is already a format, and its human\nreadable. It unfortunately still didn't solve enough other objectives,\nwhich led me towards reftable.\n\n\n> * Do you propose to store *all* references (i.e., including the\n> references that we call pseudorefs, like `HEAD`, `FETCH_HEAD`, etc) in\n> reftables, or only the references under `refs/`? If the former, then\n> you need to consider that some pseudorefs contain additional\n> information besides the SHA-1 or linked-to reference. If the latter,\n> then you could get some additional compression by making the `refs/`\n> prefix implicit rather than storing it in the \"restart\" records\n> explicitly.\n\nGreat question I didn't have an answer for. I was planning to store\nHEAD, but not FETCH_HEAD/MERGE_HEAD/etc. Mostly because our storage\nsystem at $DAY_JOB doesn't have a place to store HEAD itself, its\nburied down in the reference system. So reftable has to do the job.\n\nThe file format for reftable describes a type 0x3 which is just a\nlength delimited byte string. Provided that the data fits into a\nsingle block, reftable can store these larger files with their\nauxiliary data.\n\nI'm open to the idea of HEAD and friends being outside of reftable in\na git-core accessed repository, but the backend storage I want to run\nreftable on would likely need to store HEAD inside reftable.\n\n\n> Personally, I don't think it makes sense to store pseudorefs in\n> reftables. HEAD, though it doesn't include any supplemental\n> information, is read so frequently that it seems like a bad idea to\n> have to go through the lookup process rather than storing it in a\n> separate flat file. Moreover, HEAD is written very *infrequently*, so\n> (absent special treatment) it would tend to sink deep in the reftable\n> stack, making reads even more expensive.\n\nThat is a very fair argument for keeping HEAD outside.\n\nA counter argument is HEAD is written very frequently by following its\nindirect pointer to the branch (e.g. refs/heads/master). HEAD is\nconsequently reflogged very frequently. reftable stores the logs\ninside the table shards. HEAD could be floated onto the top on every\nwrite to accompany its log record.\n\n\n> * You have obviously designed your proposal to be friendly to whatever\n> non-local storage system you are using at Google. It would probably\n> help us understand your design tradeoffs better if you could tell us a\n> little about that storage system.\n\nRemote network attached disk. Random 64k seeks are O(40ms).\nSmaller seeks cost about the same as 64k.\nLarger seeks start to see the block size increase latency.\n\nCaching is the responsibility of the application (e.g. JGit).\n\nTail-block packing is available for small files (ResierFS-ish, but its\nnot ResierFS). A 4k minimum file size occupies the entire 4k, and has\nto transfer between the CPU and the disk. A 300 byte file occupies 300\nbytes. To the extent the file scales down with its content, the better\n(for this system).\n\n\n> So let's examine the components one after the other...\n>\n> 1. The structure of a single reftable file\n>\n> * You use int32 and int24 values in a number of places. Couldn't these\n> be uint32 and uint24?\n\nYes. I'll clarify that in the document.\n\n\n> * You use int32 values in a number of places where a smaller size\n> would suffice. For example, the block size is limited to 24 bits, so\n> surely restart_offset, record_end_offset, and number_of_restarts\n> needn't be larger than 24 bits?\n>\n> OK, actually the *index* block size is not limited to 24 bits, so\n> it's not a no-brainer.\n\nRight, its the index block that really pushes the restart_offsets to\n32 bits. And I wanted to leverage code between the multiple block\nformats as much as possible, as the structure is similar.\n\n\n> * I'm a little bit concerned that the structure is fixed to be a one-\n> or two-level indexing scheme; i.e., the (optional) index block plus\n> the restart index table within a block. This forces (as I understand\n> it) the block size to be chosen based on the overall file size to\n> prevent the index block from becoming too large, whereas for a\n> low-latency local filesystem implementation like SSDs it would\n> probably be preferable to set the block size to agree with the page\n> size to minimize reads and memory usage.\n\nTrue... but... in my \"android\" example repository we have 866,456 live\nrefs. A block size of 64k needs only 443 blocks, and a 12k index, to\nget the file to compress to 28M (vs. 62M packed-refs).\n\nIndex records are averaging 28 bytes per block. That gives us room for\nabout 1955 blocks, or 4,574,700 refs before the index block exceeds\n64k.\n\nIn other words, I'm happy with this. Given my storage is network\nattached, by the time I bring in 4k I might as well bring in 64k.\nGiven that a 64k index lets refs grow 5.2x before I start to see\nlonger read times to load the index, I'm OK with that.\n\nIf you are assuming local attached SSD with a quality kernel (Linux),\nI think you can mmap the reftable, and basically nearly about IO\ncosts. reftable is still more disk friendly for random seeks than pack\nidx v2, or v2.\n\n\n> So I ask myself whether it might be worthwhile to allow deeper\n> levels of indexing. The main index block could divide the namespace\n> into as many segments as fit in one block, but if necessary point at a\n> second-level index block that further divides the namespace before\n> pointing at the ref block that ultimately contains the value. Those of\n> us using local SSDs might tune the system to use 4k block sizes\n> throughout, basically preferring to read three or even four disjoint\n> 4k blocks rather than two disjoint 64k blocks.\n\nI did consider this, and discarded it as unnecessary complexity. See\nsome of my discussion above. Nobody is complaining about pack idx\nv1/v2 lookup speeds right now, and they are worse to disks.\n\n\n> * The tuning parameter number_of_restarts currently trades off space\n> (for the full refnames and the restart_offsets) against the need to\n> read and parse more ref_records to get the full refnames. ISTM that\n> this tradeoff could be made less painful by defining a blockwide\n> prefix that is omitted from the refnames as used in the restarts. So\n> the full refname would change from\n>\n> this_name = prior_name[0..prefix_length] + suffix\n>\n> to\n>\n> this_name = block_prefix + prior_name[0..prefix_length] + suffix\n>\n> I would expect this to allow more frequent restarts at lower space\n> cost.\n\nI've been on the fence about the value of this. It makes the search\nwith restarts more difficult to implement, but does allow shrinking a\nhandful of very popular prefixes like \"refs/\" and \"refs/pulls/\" in\nsome blocks.\n\nAn older format of reftable used only a block_prefix, and could not\nget nearly as good compression as too many blocks contained references\nwith different prefixes.\n\n\n> If we are willing to force all reads to consider the indexes, the\n> block_prefix could be taken from the index_record that points at it.\n\nNo, its important to be able to scan the file sequentially without\ntouching the index. Ref advertisement for the current wire protocol\ndemands all references. Being able to scan from the start of the file\nto the end of the last ref block and more-or-less just dump those to\nthe client is a really nice gain.\n\nHaving to load the index first to walk the blocks in order and\nassemble them with data from the index detracts from the simplicity of\njust walking the ref blocks.\n\n\n> * Does the format need to insist on fixed-size blocks?\n\nUnfortunately, yes. For my network storage to perform efficient random\naccess to data, I need the block sizes fixed. I'm willing to trade off\ninefficient torn block reads for the index and the log blocks/index,\nbut not the ref blocks.\n\n\n> * What is the rationale for the footer? Is it important for the file\n> to be written as a stream, as opposed to seeking back to the beginning\n> of the file to add the index_size there?\n\nYes, my storage doesn't allow me to overwrite a prior section. Its\nwrite-once. So I can't patch this data into the header.\n\n> The CRC, I suppose, is meant\n> to make it possible to detect a file that has been truncated\n> accidentally?\n\nCorrect, or that the file footer is somehow otherwise damaged, or that\nthe file was accidentally appended to and now the footer location no\nlonger contains footer bits.\n\n\n> 2. The stacking of multiple reftable files together\n>\n> * I like the ideas later in the thread to have a file of pointers to\n> the files that make up the stack. (I think of it as a \"table of\n> contents\"). I think without it there will be unavoidable races\n> involving readdir().\n\nI do too. Its a fantastic idea I am going to steal from Peff and work\ninto this document and implementation.\n\n\n> * The spec should describe the protocol for reading references. The\n> only interesting thing here is that\n>\n> * I think that geometric repacking of reftable files will be essential\n> to performance for very active repositories with many references, and\n> that the steady state of such a repository will involve O(lg N)\n> retable files.\n>\n> * I would like to propose adding another design goal: that reference\n> repacking can be done without blocking other *writers* (let alone\n> readers, obviously). I think that something like this could work:\n[...]\n> I think that this algorithm would allow reference updates to\n> continue while the repack is happening, and would even allow reftables\n> higher or lower in the stack than B and C to be repacked at the same\n> time (though maybe that won't be necessary).\n\nI agree, this is clever. I'll work that into the document. Thank you.\n\n\n> * A very frequent operation will be to read a single reference. This\n> could get expensive if a reftable stack grows deep, because every\n> single reftable might have to be inspected. One way to reduce this\n> cost might be to store a bloom filter in large reftable files. This\n> could allow a quick determination that the file doesn't contain the\n> reference being sought.\n\nYes, of course. But I'm torn on that premise. My gut theory says most\nreferences that are read individually were/are recently modified. Thus\nthey should be higher in the reftable stack, and a reader will\nterminate with its result. Its only the not-founds that will have a\npenalty of reaching the base of the stack.\n\nI'd also really like to see repositories holding stacks <4 deep, not\n32 deep. If we can get the compaction working well, we should be able\nto see most repositories with 1 large base file, 1 medium-ish\ncompaction, 2 recent updates.\n\nAt $DAY_JOB we can do this successfully with pack files, which are\nlarger and more costly to combine than reftable. I think we can get\nreftable to do support a reasonable stack depth.\n\n\n> I haven't reviewed your proposal for storing reflogs in reftables in\n> any detail, though I must say that my first reaction is surprise that\n> you want to store reflogs (which are mostly immutable, rarely read,\n> and can be an order of magnitude bigger) in the same files as\n> references.\n\nreftable compressed 87,393 references into 3M, and a year's worth of\ntheir log updates into another 4M. Keeping them together actually\nsimplifies a lot of nasty corner cases in Git.\n\nD/F conflicts (\"refs/heads/foo\", \"refs/heads/foo/bar\") go away, but\nassuming we continue to reject these to protect existing clients, we\ncan also still retain logs for deleted names that were cleared out.\n\nLogs can be written in the same atomic filesystem operation as the\nrefs are mutated, avoiding any skew about the log being dropped or\nlogged early. Logs are now searchable in reverse time order, which\naccelerates log queries.\n\nI really think its worth storing the logs inside the reftable. I'm\npretty sold on that part of the design at this point. There are many\nadvantages, and I've been able to sufficiently push off the downsides\nby storing the logs in a separate region of the reftable.\n"},{"id":"324633","messageId":"CAJo=hJuOOuv_TFtqXSWUqrrGc2BT01mKj39_Jepv2cyUYF4Z4A@mail.gmail.com","threadId":"46370","inReplyTo":"CAJo=hJv36tYuxHuso7NrPkfE9hApGfn=iP8g_8+MeM8L91h09g@mail.gmail.com","subject":"Re: reftable: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-07-16T21:12:07Z","receivedAt":"2017-07-16T21:12:34Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Sun, Jul 16, 2017 at 12:43 PM, Shawn Pearce wrote:\n> On Sun, Jul 16, 2017 at 10:33 AM, Michael Haggerty wrote:\n>\n>> * The tuning parameter number_of_restarts currently trades off space\n>> (for the full refnames and the restart_offsets) against the need to\n>> read and parse more ref_records to get the full refnames. ISTM that\n>> this tradeoff could be made less painful by defining a blockwide\n>> prefix that is omitted from the refnames as used in the restarts. So\n>> the full refname would change from\n>>\n>> this_name = prior_name[0..prefix_length] + suffix\n>>\n>> to\n>>\n>> this_name = block_prefix + prior_name[0..prefix_length] + suffix\n>>\n>> I would expect this to allow more frequent restarts at lower space\n>> cost.\n>\n> I've been on the fence about the value of this. It makes the search\n> with restarts more difficult to implement, but does allow shrinking a\n> handful of very popular prefixes like \"refs/\" and \"refs/pulls/\" in\n> some blocks.\n>\n> An older format of reftable used only a block_prefix, and could not\n> get nearly as good compression as too many blocks contained references\n> with different prefixes.\n\n\nI ran an experiment on my 866k ref data set. Using a block_prefix gets\nless compression, and doesn't improve packing in the file. Given the\nadditional code complexity, it really isn't worth it:\n\nformat | size | blocks | avg ref/blk\n------------------|----------|-----------|----------------\noriginal | 28 M | 443 | 1955\nblock_prefix | 29 M | 464 | 1867\n\n:-(\n"},{"id":"324634","messageId":"CAD0k6qSpNTWkn-97nQQ1DJrh=sd3dppTXytfbafqj-eVsWDTFg@mail.gmail.com","threadId":"46370","inReplyTo":"CAJo=hJv36tYuxHuso7NrPkfE9hApGfn=iP8g_8+MeM8L91h09g@mail.gmail.com","subject":"Re: reftable: new ref storage format","fromName":"Dave Borowitz","fromEmail":"dborowitz@google.com","sentAt":"2017-07-16T21:13:51Z","receivedAt":"2017-07-16T21:14:17Z","isPatch":false,"sender":{"key":"dborowitz@google.com","avatar":"https://avatars.githubusercontent.com/u/194927?v=4"},"body":"On Sun, Jul 16, 2017 at 3:43 PM, Shawn Pearce wrote:\n> True... but... in my \"android\" example repository we have 866,456 live\n> refs. A block size of 64k needs only 443 blocks, and a 12k index, to\n> get the file to compress to 28M (vs. 62M packed-refs).\n>\n> Index records are averaging 28 bytes per block. That gives us room for\n> about 1955 blocks, or 4,574,700 refs before the index block exceeds\n> 64k.\n\nThat's only a 5x increase over the current number of refs in this\nandroid repo. I would not be so sure this repo doesn't grow another 5x\nin the next few years. Especially as the other optimizations for\nworking with large repos start to be applied, so it won't be\nprohibitively painful to work with such a repo.\n\nAre we ok with increasing the block size when this eventually happens?\n(At least I think that's what we would have to do, I haven't been\nfollowing closely the discussion on scaling limits.)\n"},{"id":"324635","messageId":"CAJo=hJue2MYcE-xc9qjRXfMCf5f5+QPzmZQwHtqgr_zALeQziA@mail.gmail.com","threadId":"46370","inReplyTo":"CAD0k6qSpNTWkn-97nQQ1DJrh=sd3dppTXytfbafqj-eVsWDTFg@mail.gmail.com","subject":"Re: reftable: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-07-16T21:31:20Z","receivedAt":"2017-07-16T21:31:46Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Sun, Jul 16, 2017 at 2:13 PM, Dave Borowitz wrote:\n> On Sun, Jul 16, 2017 at 3:43 PM, Shawn Pearce wrote:\n>> True... but... in my \"android\" example repository we have 866,456 live\n>> refs. A block size of 64k needs only 443 blocks, and a 12k index, to\n>> get the file to compress to 28M (vs. 62M packed-refs).\n>>\n>> Index records are averaging 28 bytes per block. That gives us room for\n>> about 1955 blocks, or 4,574,700 refs before the index block exceeds\n>> 64k.\n>\n> That's only a 5x increase over the current number of refs in this\n> android repo. I would not be so sure this repo doesn't grow another 5x\n> in the next few years. Especially as the other optimizations for\n> working with large repos start to be applied, so it won't be\n> prohibitively painful to work with such a repo.\n>\n> Are we ok with increasing the block size when this eventually happens?\n> (At least I think that's what we would have to do, I haven't been\n> following closely the discussion on scaling limits.)\n\nI think I'd try letting the index grow to 4 blocks (256k) before I\nconsidered increasing the block size. Remember pack idx files are much\nlarger, and are loaded wholesale into memory by JGit. A ref idx at\n256k might not be problematic.\n"},{"id":"324696","messageId":"CAMy9T_Fuf3YoHzsLgx-fcX5OQBNXw8xOvrPEpffkYjWGBpNsMQ@mail.gmail.com","threadId":"46370","inReplyTo":"CAJo=hJv36tYuxHuso7NrPkfE9hApGfn=iP8g_8+MeM8L91h09g@mail.gmail.com","subject":"Re: reftable: new ref storage format","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-07-18T01:43:35Z","receivedAt":"2017-07-18T01:43:49Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On Sun, Jul 16, 2017 at 12:43 PM, Shawn Pearce wrote:\n> On Sun, Jul 16, 2017 at 10:33 AM, Michael Haggerty wrote:\n>> * Do you propose to store *all* references (i.e., including the\n>> references that we call pseudorefs, like `HEAD`, `FETCH_HEAD`, etc) in\n>> reftables, or only the references under `refs/`? If the former, then\n>> you need to consider that some pseudorefs contain additional\n>> information besides the SHA-1 or linked-to reference. If the latter,\n>> then you could get some additional compression by making the `refs/`\n>> prefix implicit rather than storing it in the \"restart\" records\n>> explicitly.\n>\n> Great question I didn't have an answer for. I was planning to store\n> HEAD, but not FETCH_HEAD/MERGE_HEAD/etc. Mostly because our storage\n> system at $DAY_JOB doesn't have a place to store HEAD itself, its\n> buried down in the reference system. So reftable has to do the job.\n>\n> The file format for reftable describes a type 0x3 which is just a\n> length delimited byte string. Provided that the data fits into a\n> single block, reftable can store these larger files with their\n> auxiliary data.\n>\n> I'm open to the idea of HEAD and friends being outside of reftable in\n> a git-core accessed repository, but the backend storage I want to run\n> reftable on would likely need to store HEAD inside reftable.\n>\n>> Personally, I don't think it makes sense to store pseudorefs in\n>> reftables. HEAD, though it doesn't include any supplemental\n>> information, is read so frequently that it seems like a bad idea to\n>> have to go through the lookup process rather than storing it in a\n>> separate flat file. Moreover, HEAD is written very *infrequently*, so\n>> (absent special treatment) it would tend to sink deep in the reftable\n>> stack, making reads even more expensive.\n>\n> That is a very fair argument for keeping HEAD outside.\n>\n> A counter argument is HEAD is written very frequently by following its\n> indirect pointer to the branch (e.g. refs/heads/master). HEAD is\n> consequently reflogged very frequently. reftable stores the logs\n> inside the table shards. HEAD could be floated onto the top on every\n> write to accompany its log record.\n\nOn second thought, the idea of having HEAD (or maybe all pseudorefs)\nin the same system would open a few interesting possibilities that\nderive from having a global, atomic view of all references:\n\n1. We could store backlinks from references to the symbolic references\nthat refer to them. This would allow us to update the reflogs for\nsymbolic refs properly. (Currently, there is special-case code to\nupdate the reflogs for HEAD when the reference that it points at is\nmodified, but not for other symrefs.)\n\n2. We could store \"peeled\" versions of symbolic refs. These would have\nto be updated whenever the pointed-at reference is updated, but that\nwould have two nice advantages: HEAD would usually be resolvable based\non the top reftable in the stack, and it would be resolvable in one\nstep (without having the follow the symref explicitly).\n\n> [...]\n>> * The tuning parameter number_of_restarts currently trades off space\n>> (for the full refnames and the restart_offsets) against the need to\n>> read and parse more ref_records to get the full refnames. ISTM that\n>> this tradeoff could be made less painful by defining a blockwide\n>> prefix that is omitted from the refnames as used in the restarts. So\n>> the full refname would change from\n>>\n>> this_name = prior_name[0..prefix_length] + suffix\n>>\n>> to\n>>\n>> this_name = block_prefix + prior_name[0..prefix_length] + suffix\n>>\n>> I would expect this to allow more frequent restarts at lower space\n>> cost.\n>\n> I've been on the fence about the value of this. It makes the search\n> with restarts more difficult to implement, but does allow shrinking a\n> handful of very popular prefixes like \"refs/\" and \"refs/pulls/\" in\n> some blocks.\n>\n> An older format of reftable used only a block_prefix, and could not\n> get nearly as good compression as too many blocks contained references\n> with different prefixes.\n\nIt's clear that using *only* a block_prefix wouldn't yield as good\ncompression as your proposed scheme. And it feels plausible that when\nusing 64k blocks, a block_prefix wouldn't help much.\n\nI'm still not quite resigned to non-Google users wanting to use blocks\nas large as 64k, but (short of doing actual experiments, yuck!) I\ncan't estimate whether it would make any detectable difference in the\nreal world.\n\nOn the other end of the spectrum, I might mention that the\nshared-storage \"network.git\" repositories that we use at GitHub often\nhave a colossal number of references (basically, the sum of the number\nof references in all of the forks in a \"repository network\", including\nsome hidden references that users don't see). For example, one\n\"network.git\" repository has 56M references(!) Mercifully, we\ncurrently only have to access these repositories for batch jobs, but,\ngiven a better reference storage backend, that might change.\n\n> [...]\n>> 2. The stacking of multiple reftable files together\n>>\n>> * A very frequent operation will be to read a single reference. This\n>> could get expensive if a reftable stack grows deep, because every\n>> single reftable might have to be inspected. One way to reduce this\n>> cost might be to store a bloom filter in large reftable files. This\n>> could allow a quick determination that the file doesn't contain the\n>> reference being sought.\n>\n> Yes, of course. But I'm torn on that premise. My gut theory says most\n> references that are read individually were/are recently modified. Thus\n> they should be higher in the reftable stack, and a reader will\n> terminate with its result. Its only the not-founds that will have a\n> penalty of reaching the base of the stack.\n>\n> I'd also really like to see repositories holding stacks <4 deep, not\n> 32 deep. If we can get the compaction working well, we should be able\n> to see most repositories with 1 large base file, 1 medium-ish\n> compaction, 2 recent updates.\n>\n> At $DAY_JOB we can do this successfully with pack files, which are\n> larger and more costly to combine than reftable. I think we can get\n> reftable to do support a reasonable stack depth.\n\nAre you saying that you merge subsets of packfiles without merging all\nof them? Does this work together with bitmaps, or do you only have\nbitmaps for the biggest packfile?\n\nWe've thought about merging packfiles in that way, but don't want to\ngive up the benefits of bitmaps.\n\n>> I haven't reviewed your proposal for storing reflogs in reftables in\n>> any detail, though I must say that my first reaction is surprise that\n>> you want to store reflogs (which are mostly immutable, rarely read,\n>> and can be an order of magnitude bigger) in the same files as\n>> references.\n>\n> reftable compressed 87,393 references into 3M, and a year's worth of\n> their log updates into another 4M. Keeping them together actually\n> simplifies a lot of nasty corner cases in Git.\n>\n> D/F conflicts (\"refs/heads/foo\", \"refs/heads/foo/bar\") go away, but\n> assuming we continue to reject these to protect existing clients, we\n> can also still retain logs for deleted names that were cleared out.\n>\n> Logs can be written in the same atomic filesystem operation as the\n> refs are mutated, avoiding any skew about the log being dropped or\n> logged early. Logs are now searchable in reverse time order, which\n> accelerates log queries.\n>\n> I really think its worth storing the logs inside the reftable. I'm\n> pretty sold on that part of the design at this point. There are many\n> advantages, and I've been able to sufficiently push off the downsides\n> by storing the logs in a separate region of the reftable.\n\nThose sizes don't sound that scary. Do your reflogs include\nsignificant information in the log messages, or are they all \"push\"\n\"push\" \"push\"? We record quite a bit of information in our audit_log\nentries (our equivalent of reflogs), so I would expect ours to\ncompress much less well.\n\nWe also tend to use our audit_logs to see what was happening in a\nrepository; e.g., around the time that a problem occurred. So for us\nit is useful that the entries are in chronological order across\nreferences, as opposed to having the entries for each reference\ngrouped together. We might be the oddballs here though, and in fact it\nis possible that this would be an argument for us to stick to our\naudit_log scheme rather than use reflogs stored in reftables.\n\nI agree that it would be nice to have logs in the same atomic store as\nthe references, so if it can be made efficient, I'm all for it.\n\nI've since read over the reflog part of your proposal. Comments:\n\n* With file-based reflogs, the presence or absence of a reflog file\n(even if it is empty) is sometimes used to decide whether to log new\nupdates for the corresponding reference [1]. Is there an equivalent\nfor reftable-based reflogs?\n\n[1] https://github.com/git/git/blob/f3da2b79be9565779e4f76dc5812c68e156afdf0/refs/files-backend.c#L1976-L1991\n\n* It is not clear from your proposal whether\nrefname+reverse_int32(time_sec) is meant to be a unique key.\n * If yes, think again. It is not at all unusual for a reference to\nbe updated more than once in a second.\n * If no, then how can reflogs be expired? It seems that there would\noften be no alternative to rewriting all of the reftable files.\n\n* As reflog entries accumulate and reftable files are compacted, it\nwill often be the case that compacted reftable files will contain many\nreflog entries for the some references. Normally (though not always),\nthe old_id of one entry should be identical to the new_id of the next.\nIt seems that it should be possible to save quite a bit of space by\nrepresenting such entries as a group rather than singly.\n\nRegarding your updated proposal for how to name and stack reftable files:\n\n* You say that \".ref files are named by the SHA-1 hash of the contents\nof the reftable\". I assume that means \"the contents of that particular\nfile\". However, this is not entirely straightforward. It is thinkable\nfor two reftable files to have the exact same contents. For example,\nif reflogs are turned off, and I (1) make commit A; (2) make commit B;\n(3) reset the branch back to commit A; then I think that the first and\nthird reftable files would have identical contents. This would not\n*necessarily* be a problem—given that the two reftable files would\nhave identical contents, the same file could serve for both of them.\nBut it could very easily lead to confusion, for example if some\nprocess that is compacting the first two reftables decides that it can\ndelete the file at the same moment that the `git reset` process has\njust rewritten the file or decided that it doesn't have to rewrite the\nfile.\n\n We could avoid this situation by including the name of the\npredecessor reftable file in the body of each new reftable, or even by\nincluding it in the SHA-1 without writing it into the file.\n\n It *seems* as if it would be an advantage to include the name of the\npredecessor reftable in a new reftable, but that info would become\nobsolete if some deeper reftables are compacted while new reftables\nare being written (which I think is a more useful design goal than\nbeing able to chain the reftable files to each other ab initio).\n\n We could have both properties if the SHA-1 of a reftable file were a\nhash of the *logical* contents of the whole stack of\nreferences+reflogs, including its predecessors. That hash would be\ninvariant under compaction, so if we compact files A, B, and C, the\nresults would necessarily have the same hash as file C did previously.\nHowever, it would be expensive to compute the hash of the whole\ncontents, because to do so one would have to iterate through all of\nthe references and reflog entries. Moreover, IIUC, on Windows it would\nnot be possible to rename the \"new C\" file on top of the \"old C\" file\nif any reader has that file open.\n\nBut I don't think there is any reason that the files have to be named\nusing the hash of their contents. As far as I understand, any unique\nfilename (i.e., even something as simple as `mktemp XXXXXX.ref`) would\nserve just fine. It might also be convenient to embed the timestamp or\nN+1 of the predecessor file in the filename for human consumption.\n\nSome other random comments:\n\n* Do we really want to use Git-style varints here? It seems to me that\nprotocol-buffer-style varints are more familiar and are a lot easier\nto understand (albeit a miniscule bit larger on average). They also\nhave the advantage that they can be padded by inserting 0x80 bytes, a\nproperty that would have come in handy in a packfile-related project\nthat we were working on internally.\n\n* What would you think about being extravagant and making the\nvalue_type a full byte? It would make the format a tiny bit easier to\nwork with, and would leave room for future enhancements (e.g.,\npseudorefs, peeled symrefs, support for the successors of SHA-1s)\nwithout having to change the file format dramatically.\n\n* Speaking of the successors of SHA-1s, if you haven't already, it\nwould make sense for somebody to read the proposal for the transition\nto a post-SHA-1 world with an eye to considering whether the reftable\nfile should play a role, and whether that should have an effect on the\ncurrent design. I'm not saying we should build in support already, but\nit would be a pity if the format had to be changed radically at the\ntime of the transition.\n\n* The transition to reftable will require a new repository format\nversion and an extension [2]. You might as well mention that in your\nproposal and suggest a name.\n\n[2] https://github.com/git/git/commit/00a09d57eb8a041e6a6b0470c53533719c049bab\n\n* Current versions of git look for `$GIT_DIR/refs` as part of\ndetermining whether a directory might be a plausible git directory\n[3]. Although current versions of Git won't be able to read a\nreftable-based repository, they *should* be able to recognize the\ndirectory as a plausible Git directory. So ISTM that a reftable-based\nGit repository should put *something* at that path. For example, that\npath could be used as the name of the \"stack\" file. The fact that it\nis a file rather than a directory shouldn't bother is_git_directory()\nbut should be enough to prevent it from accidentally being used as a\nloose refs directory.\n\n[3] https://github.com/git/git/blob/f3da2b79be9565779e4f76dc5812c68e156afdf0/setup.c#L335-L339\n\nYours,\nMichael\n"},{"id":"324714","messageId":"xmqqa841poea.fsf@gitster.mtv.corp.google.com","threadId":"46370","inReplyTo":"CAMy9T_Fuf3YoHzsLgx-fcX5OQBNXw8xOvrPEpffkYjWGBpNsMQ@mail.gmail.com","subject":"Re: reftable: new ref storage format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-07-18T18:53:49Z","receivedAt":"2017-07-18T18:53:58Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty writes:\n\n> On second thought, the idea of having HEAD (or maybe all pseudorefs)\n> in the same system would open a few interesting possibilities that\n> derive from having a global, atomic view of all references:\n>\n> 1. We could store backlinks from references to the symbolic references\n> that refer to them. This would allow us to update the reflogs for\n> symbolic refs properly. (Currently, there is special-case code to\n> update the reflogs for HEAD when the reference that it points at is\n> modified, but not for other symrefs.)\n>\n> 2. We could store \"peeled\" versions of symbolic refs. These would have\n> to be updated whenever the pointed-at reference is updated, but that\n> would have two nice advantages: HEAD would usually be resolvable based\n> on the top reftable in the stack, and it would be resolvable in one\n> step (without having the follow the symref explicitly).\n\nInteresting. I think FETCH_HEAD is the only thing that would not\nmesh well with the \"one ref records one object name, or refers to\nanother ref\" paradigm, and I think it is OK to leave it that way,\neven in the new pluggable ref backend world order.\n\nIt still bothers me that the way refs.c special-cases what you call\npseudo refs seems somewhat inconsistent, which I found by accident\nthe other day while running t1405 and reported in a separate thread.\nWhen we start adding a reftable backend, I suspect we'd need to dig\nfurther, but if I recall the symptom correctly, writing them out is\nstill passed to the main (i.e. files) backend, while reading them is\ndone directly in refs.c layer without consulting any backend, and\nthat made it impossible to optionally tweak the filename used to\nstore refs in the files backend.\n\n\n\n\n"},{"id":"324925","messageId":"CAJo=hJvm5P6fq4KzZsO0h879xU4pV05MOscCWBPy_gCCYSxobQ@mail.gmail.com","threadId":"46370","inReplyTo":"CAMy9T_Fuf3YoHzsLgx-fcX5OQBNXw8xOvrPEpffkYjWGBpNsMQ@mail.gmail.com","subject":"Re: reftable: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-07-23T22:56:49Z","receivedAt":"2017-07-23T22:57:17Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"+git@vger.kernel.org. I originally sent the below reply privately by mistake.\n\nOn Mon, Jul 17, 2017 at 6:43 PM, Michael Haggerty wrote:\n> On Sun, Jul 16, 2017 at 12:43 PM, Shawn Pearce wrote:\n>> On Sun, Jul 16, 2017 at 10:33 AM, Michael Haggerty wrote:\n>\n> On second thought, the idea of having HEAD (or maybe all pseudorefs)\n> in the same system would open a few interesting possibilities that\n> derive from having a global, atomic view of all references:\n>\n> 1. We could store backlinks from references to the symbolic references\n> that refer to them. This would allow us to update the reflogs for\n> symbolic refs properly. (Currently, there is special-case code to\n> update the reflogs for HEAD when the reference that it points at is\n> modified, but not for other symrefs.)\n\nThis is a good idea, but makes for some difficult transition code. We\nhave to keep the special case for HEAD, but other symrefs would log\nwhen in a reftable.\n\n> 2. We could store \"peeled\" versions of symbolic refs. These would have\n> to be updated whenever the pointed-at reference is updated, but that\n> would have two nice advantages: HEAD would usually be resolvable based\n> on the top reftable in the stack, and it would be resolvable in one\n> step (without having the follow the symref explicitly).\n\nGreat observation. I wish I saw that sooner. Its a pain in the neck to\nresolve symrefs, and has caused us a few bugs in JGit on our current\nnon-standard storage. It depends on the back pointer being present and\naccurate to ensure an update of master also updates the cached HEAD.\n\nI'll have to mull on these a bit. I'm not folding them into my\ndocumentation and implementation just yet.\n\n\n[...]\n> I'm still not quite resigned to non-Google users wanting to use blocks\n> as large as 64k, but (short of doing actual experiments, yuck!) I\n> can't estimate whether it would make any detectable difference in the\n> real world.\n\nI think it is only likely to matter with NFS, and then its a balancing\nact of how much of that block did you need vs. not need. :)\n\n> On the other end of the spectrum, I might mention that the\n> shared-storage \"network.git\" repositories that we use at GitHub often\n> have a colossal number of references (basically, the sum of the number\n> of references in all of the forks in a \"repository network\", including\n> some hidden references that users don't see). For example, one\n> \"network.git\" repository has 56M references(!) Mercifully, we\n> currently only have to access these repositories for batch jobs, but,\n> given a better reference storage backend, that might change.\n\nA larger block size right now has the advantage of a smaller index,\nwhich could make a single ref lookup more efficient. Otherwise, the\nblock size doesn't have a big impact on streaming through many\nreferences.\n\n\n>>> 2. The stacking of multiple reftable files together\n[...]\n>> At $DAY_JOB we can do this successfully with pack files, which are\n>> larger and more costly to combine than reftable. I think we can get\n>> reftable to do support a reasonable stack depth.\n>\n> Are you saying that you merge subsets of packfiles without merging all\n> of them? Does this work together with bitmaps, or do you only have\n> bitmaps for the biggest packfile?\n>\n> We've thought about merging packfiles in that way, but don't want to\n> give up the benefits of bitmaps.\n\nYes. We compact smaller pack files together into a larger pack file,\nand try to keep a repository at:\n\n - 2 compacted packs, each <20 MiB\n - 1 base pack + bitmap\n\nWe issue a daily GC for any repository that isn't just 1 base pack.\nBut during a business day this compacting process lets us handle most\nread traffic quite well, despite the bitmaps being incomplete.\n\n\n>>> I haven't reviewed your proposal for storing reflogs in reftables in\n[...]\n>\n> Those sizes don't sound that scary. Do your reflogs include\n> significant information in the log messages, or are they all \"push\"\n> \"push\" \"push\"? We record quite a bit of information in our audit_log\n> entries (our equivalent of reflogs), so I would expect ours to\n> compress much less well.\n\nThese were pretty sparse in the comment field, and frequent reuse of a\nmessage. So it may not be representative of what you are storing.\n\n> We also tend to use our audit_logs to see what was happening in a\n> repository; e.g., around the time that a problem occurred. So for us\n> it is useful that the entries are in chronological order across\n> references, as opposed to having the entries for each reference\n> grouped together. We might be the oddballs here though, and in fact it\n> is possible that this would be an argument for us to stick to our\n> audit_log scheme rather than use reflogs stored in reftables.\n\nI think of reflogs about a single ref, not the whole repository. So\nI'm inclined to say the reftable storage of them should be by ref,\nthen time. Anyone who wants a repository view must either scan the\nentire log segment, or should roll their own log with an\nupdate/post-receive hook.\n\n\n> I've since read over the reflog part of your proposal. Comments:\n>\n> * With file-based reflogs, the presence or absence of a reflog file\n> (even if it is empty) is sometimes used to decide whether to log new\n> updates for the corresponding reference [1]. Is there an equivalent\n> for reftable-based reflogs?\n>\n> [1] https://github.com/git/git/blob/f3da2b79be9565779e4f76dc5812c68e156af=\ndf0/refs/files-backend.c#L1976-L1991\n\nNo, I was going to store everything. The flag you are talking about\nwas added because IIRC Gerrit Code Review was making a lot of\ncreate-only references that were never modified and the reflogs were\ngrowing out of control in terms of inodes used. So disabling reflogs\nby default and then explicitly creating files for refs under\nrefs/heads/ provided an escape hatch.\n\nWith integrated storage in reftable, these problems go away.\n\n\n> * It is not clear from your proposal whether\n> refname+reverse_int32(time_sec) is meant to be a unique key.\n> * If yes, think again. It is not at all unusual for a reference to\n> be updated more than once in a second.\n> * If no, then how can reflogs be expired? It seems that there would\n> often be no alternative to rewriting all of the reftable files.\n\nGreat catch, I missed that. I've expanded the format to be int64(\ntime_usec ) using microseconds since the epoch, with the requirement\nthat the time be unique.\n\nWriters working with a second precision clock (e.g. current reflog)\nshould pad the timestamp with a suffix of 999999, and decrement a\nmicrosecond from each older log record that would otherwise have a\nduplicate time.\n\n\n> * As reflog entries accumulate and reftable files are compacted, it\n> will often be the case that compacted reftable files will contain many\n> reflog entries for the some references. Normally (though not always),\n> the old_id of one entry should be identical to the new_id of the next.\n> It seems that it should be possible to save quite a bit of space by\n> representing such entries as a group rather than singly.\n\nI'm betting on grouping of log records by ref and time, and then libz\ndeflate over the log block to reduce duplications. I actually tried\nadding a flag byte to recycle the id across records, and it was\nslightly larger than letting libz handle it.\n\n\n> Regarding your updated proposal for how to name and stack reftable files:\n>\n> * You say that \".ref files are named by the SHA-1 hash of the contents\n> of the reftable\". I assume that means \"the contents of that particular\n> file\". However, this is not entirely straightforward. It is thinkable\n> for two reftable files to have the exact same contents. For example,\n> if reflogs are turned off, and I (1) make commit A; (2) make commit B;\n> (3) reset the branch back to commit A; then I think that the first and\n> third reftable files would have identical contents. This would not\n> *necessarily* be a problem=E2=80=94given that the two reftable files woul=\nd\n> have identical contents, the same file could serve for both of them.\n> But it could very easily lead to confusion, for example if some\n> process that is compacting the first two reftables decides that it can\n> delete the file at the same moment that the `git reset` process has\n> just rewritten the file or decided that it doesn't have to rewrite the\n> file.\n\nYikes! Good catch.\n\n> We could avoid this situation by including the name of the\n> predecessor reftable file in the body of each new reftable, or even by\n> including it in the SHA-1 without writing it into the file.\n>\n> It *seems* as if it would be an advantage to include the name of the\n> predecessor reftable in a new reftable, but that info would become\n> obsolete if some deeper reftables are compacted while new reftables\n> are being written (which I think is a more useful design goal than\n> being able to chain the reftable files to each other ab initio).\n\nI agree. We don't want to embed the predecessor table names into the\ntable itself.\n\n> We could have both properties if the SHA-1 of a reftable file were a\n> hash of the *logical* contents of the whole stack of\n> references+reflogs, including its predecessors. That hash would be\n> invariant under compaction, so if we compact files A, B, and C, the\n> results would necessarily have the same hash as file C did previously.\n> However, it would be expensive to compute the hash of the whole\n> contents, because to do so one would have to iterate through all of\n> the references and reflog entries. Moreover, IIUC, on Windows it would\n> not be possible to rename the \"new C\" file on top of the \"old C\" file\n> if any reader has that file open.\n>\n> But I don't think there is any reason that the files have to be named\n> using the hash of their contents. As far as I understand, any unique\n> filename (i.e., even something as simple as `mktemp XXXXXX.ref`) would\n> serve just fine. It might also be convenient to embed the timestamp or\n> N+1 of the predecessor file in the filename for human consumption.\n\nYes, you've sold me on this. We don't want to name them by SHA-1 of\ncontents, instead any suitable unique name is fine, such as one\nconstructed by mktemp.\n\n\n> * Do we really want to use Git-style varints here? It seems to me that\n> protocol-buffer-style varints are more familiar and are a lot easier\n> to understand (albeit a miniscule bit larger on average). They also\n> have the advantage that they can be padded by inserting 0x80 bytes, a\n> property that would have come in handy in a packfile-related project\n> that we were working on internally.\n\nYes, I would prefer to stick with a varint already in use in the git\nproject, vs. introducing yet another varint format. Its bad enough we\nhave 2 varint types in the pack file format. And I really don't see a\nreason to support people doing weird things with a reftable, like\npadding a file by inserting no-op 0x80 varint bytes.\n\n> * What would you think about being extravagant and making the\n> value_type a full byte? It would make the format a tiny bit easier to\n> work with, and would leave room for future enhancements (e.g.,\n> pseudorefs, peeled symrefs, support for the successors of SHA-1s)\n> without having to change the file format dramatically.\n\nI reran my 866k file with full byte value_type. It pushes up the\naverage bytes per ref from 33 to 34, but the overall file size is\nstill 28M (with 64 block size). I think its reasonable to expand this\nto the full byte as you suggest.\n\n\n> * The transition to reftable will require a new repository format\n> version and an extension [2]. You might as well mention that in your\n> proposal and suggest a name.\n>\n> [2] https://github.com/git/git/commit/00a09d57eb8a041e6a6b0470c53533719c0=\n49bab\n\nThanks, documented.\n\n> * Current versions of git look for `$GIT_DIR/refs` as part of\n> determining whether a directory might be a plausible git directory\n> [3]. Although current versions of Git won't be able to read a\n> reftable-based repository, they *should* be able to recognize the\n> directory as a plausible Git directory. So ISTM that a reftable-based\n> Git repository should put *something* at that path. For example, that\n> path could be used as the name of the \"stack\" file. The fact that it\n> is a file rather than a directory shouldn't bother is_git_directory()\n> but should be enough to prevent it from accidentally being used as a\n> loose refs directory.\n>\n> [3] https://github.com/git/git/blob/f3da2b79be9565779e4f76dc5812c68e156af=\ndf0/setup.c#L335-L339\n\nThanks, documented.\n"},{"id":"324926","messageId":"CAJo=hJty4nWBVBmxOJn5HEi9-9uY8kYEt6H6Sk9_c6nNWqJLUQ@mail.gmail.com","threadId":"46370","inReplyTo":"CAJo=hJvm5P6fq4KzZsO0h879xU4pV05MOscCWBPy_gCCYSxobQ@mail.gmail.com","subject":"Re: reftable: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-07-23T23:03:43Z","receivedAt":"2017-07-23T23:04:08Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Sun, Jul 23, 2017 at 3:56 PM, Shawn Pearce wrote:\n> On Mon, Jul 17, 2017 at 6:43 PM, Michael Haggerty wrote:\n>> On Sun, Jul 16, 2017 at 12:43 PM, Shawn Pearce wrote:\n>>> On Sun, Jul 16, 2017 at 10:33 AM, Michael Haggerty wrote:\n>\n>> * What would you think about being extravagant and making the\n>> value_type a full byte? It would make the format a tiny bit easier to\n>> work with, and would leave room for future enhancements (e.g.,\n>> pseudorefs, peeled symrefs, support for the successors of SHA-1s)\n>> without having to change the file format dramatically.\n>\n> I reran my 866k file with full byte value_type. It pushes up the\n> average bytes per ref from 33 to 34, but the overall file size is\n> still 28M (with 64 block size). I think its reasonable to expand this\n> to the full byte as you suggest.\n\nFYI, I went back on this in the v3 draft I posted on Jul 22 in\nhttps://public-inbox.org/git/CAJo=hJvxWg2J-yRiCK3szux=eYM2ThjT0KWo-SFFOOc1RkxXzg@mail.gmail.com/\n\nI expanded value_type from 2 bits to 3 bits, but kept it as a bit\nfield in a varint. I just couldn't justify the additional byte per ref\nin these large files. The prefix compression works well enough that\nmany refs are still able to use only a single byte for the\nsuffix_length << 3 | value_type varint, keeping the average at 33\nbytes per ref.\n\nThe reftable format uses values 0-3, leaving 4-7 available. I reserved\n4 for an arbitrary payload like MERGE_HEAD type files.\n"}]}