{"thread":{"id":"46597","subject":"Re: reftable [v6]: new ref storage format","startedAt":"2017-08-15T22:48:24Z","lastAt":"2017-08-18T09:24:28Z","messageCount":2,"participants":["Shawn Pearce","Michael Haggerty"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"326466","messageId":"CAJo=hJum2boTfcXOaZVhxmbGB9Dygoc5=TM8RD2nqxo-Ahjv9g@mail.gmail.com","threadId":"46597","inReplyTo":null,"subject":"Re: reftable [v6]: new ref storage format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2017-08-15T22:47:56Z","receivedAt":"2017-08-15T22:48:24Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Mon, Aug 14, 2017 at 5:13 AM, Michael Haggerty <mhagger@alum.mit.edu> wrote:\n> On 08/07/2017 03:47 AM, Shawn Pearce wrote:\n>> 6th iteration of the reftable storage format.\n>\n> Thanks!\n>\n>> Changes from v5:\n>> - extensions.refStorage = reftable is used to select this format.\n>>\n>> - Log records can be explicitly deleted (for refs/stash).\n>> - Log records may use Michael Haggerty's chained idea to compress before zlib.\n>>   This saved ~5.8% on one of my example repositories.\n>\n> Meh. Do you think that's worth the complexity? The percentage savings\n> will presumably be even lower for repositories that store significant\n> information in their reflog messages.\n\nNo, I don't. I'm quite happy to remove the chained compression. I'll\nkeep the explicit deletion support for refs/stash.\n\n\n>> [...]\n>> #### ref record\n>> - `0x3`: symref and text: `varint( text_len ) text`\n[...]\n> I'm still relatively negative on storing \"other\" references (except\n> `HEAD`) in reftable. Here are my thoughts:\n>\n> * \"Other\" references are not considered for reachability, so there\n>   is no need for their modification to be done atomically.\n>\n> * \"Other\" references don't have or need reflogs.\n>\n> * The refs API would have to provide a way for other Git code to\n>   read and write \"other\" references including their extra\n>   information, and the users of that information would have to\n>   be rewritten to use the new API.\n>\n> * Presumably there are other programs in the wild (e.g., scripts)\n>   that want to read that information. They wouldn't be able to\n>   extract it from reftable files themselves, so we would also have\n>   to provide a command-line tool to read (and write?) such files.\n>\n> Regardless, I suggest allocating separate `value_type`s for generic\n> symrefs (which then wouldn't need a `ref: ` prefix) vs. for \"other\"\n> references.\n\nAck, I agree with you. Lets only store symrefs as 0x3, without the\n\"ref: \" prefix nonsense, and don't support the \"other\" ref types. You\nmake good arguments above about why those would not be stored in a\nreftable.\n\n\n>> [...]\n>> ### Ref index\n>\n> It wasn't clear to me whether (in the case of a multi-level index) ref\n> index blocks have to be aligned in `block_size` blocks (both their\n> maximum size and their alignment). I don't see a reason for that to be\n> required, though of course a compactor implementation might choose to\n> block-align these blocks based on the filesystem that is in use.\n>\n> For that matter, I don't see an intrinsic reason that object blocks or\n> object index blocks need to be block aligned.\n\nYea, you are correct. There isn't an actual need for alignment.\n\n> In fact, the only way I can see that the current reftable proposal makes\n> use of `block_size` is so that `obj_record`s can record `block_delta` in\n> units of `block_size` rather than in units of bytes. (And given that I'm\n> skeptical about the value of the object index, that justification seems\n> thin.)\n\nThis use of block_size in the obj_record also has been bothering me.\nI'm changing it to use position, which removes any requirement on\nalignment. It does cost a bit more space, but I'm willing to trade\nthat for simplification in the format definition.\n\n> I totally accept that *you* want to align your blocks, and I'm totally\n> supportive of a format that permits a reftable compactor to write\n> reftables that are block-aligned. It just still seems to me that it\n> imposes more complexity than necessary on *other* reftable compactor\n> implementations that don't care about block alignment.\n>\n> Aside from the object index, I think it would be straightforward to\n> write a reftable reader that is totally ignorant of `block_size`.\n\nYup, I think you are right. So I'll try to rework the document to make\nit so alignment and padding are writer-local decisions. A writer can\nchoose to align, or choose to skip alignment. Readers should be\nprepared for either.\n\n\n>> [...]\n>> #### index record\n>>\n>> An index record describes the last entry in another block.\n>> Index records are written as:\n>>\n>>     varint( prefix_length )\n>>     varint( (suffix_length << 3) | 0 )\n>>     suffix\n>>     varint( block_position )\n>>\n>> Index records use prefix compression exactly like `ref_record`.\n>>\n>> Index records store `block_position` after the suffix, specifying the\n>> absolute position in bytes (from the start of the file) of the block\n>> that ends with this reference.\n>\n> Is there a reason that the index lists the *last* refname that is\n> contained in a block rather than the *first* refname? I can't think of a\n> reason to choose one vs. the other, but your choice was initially\n> surprising. I don't think it matters either way; I was just curious.\n\nYes, there is a reason. When a reader is searching the index block and\ndiscovers a key that is greater than their search needle, they are now\nsitting on a record with the block_position for that greater key. By\nusing the *last* refname the current block_position is the one to seek\nto.\n\nIf instead we used *first* refname, the reader would now have to\nbacktrack to the prior index record to get the block_position out of\nthat record. Or it has to keep a running \"prior_position\" local\nvariable.\n\nUsing last simplifies the reader's code.\n\n\n> Do I understand correctly that all `block_position`s are *byte*\n> addresses, even in the `ref_index` where they should all be multiples of\n> the block size (except the zeroth one)? I think that's OK, but note that\n> it will waste more than a byte per `ref_index` and `obj_index` record,\n> on average.\n\nYes, because it simplifies a lot of code, especially if we do away\nwith any sort of requirement for alignment.\n\n\n>> Readers must examine the block header at `block_position` to determine\n>> if the next block is another level index block, or the leaf-level ref\n>> block.\n>\n> For scanning through a whole namespace, like `refs/tags/`, I guess you\n> only need to use a binary search to find the beginning of the range.\n> Then you would read serially forwards from there, continuing from one\n> `ref_block` to the next, until you find a refname that doesn't start\n> with `refs/tags/`. In other words, there is no reason to binary search\n> to find the end of the namespace, correct?\n\nCorrect.\n\n\n>> [...]\n>> #### Importing logs\n>>\n>> When importing from `$GIT_DIR/logs` writers should globally order all\n>> log records roughly by timestamp while preserving file order, and\n>> assign unique, increasing `update_index` values for each log line.\n>> Newer log records get higher `update_index` values.\n>>\n>> Although an import may write only a single reftable file, the reftable\n>> file must span many unique `update_index`, as each log line requires\n>> its own `update_index` to preserve semantics.\n>\n> Thinking out loud here: A really high-quality importer might want to\n> group together, under the same `update_index`, ref updates that are\n> thought originally to have been done in the same transaction.\n[...]\n> But I doubt that it is worth the effort. (The whole idea gives me nasty\n> flashbacks from working on cvs2svn/cvs2git.)\n\nYup, that is why I didn't go down writing a description like that here. :)\n"},{"id":"326682","messageId":"CAMy9T_EKLs7vDyRi=jNH47fuCaKcxSvcpK27mKB-7P2EtdBeoQ@mail.gmail.com","threadId":"46597","inReplyTo":"CAJo=hJum2boTfcXOaZVhxmbGB9Dygoc5=TM8RD2nqxo-Ahjv9g@mail.gmail.com","subject":"Re: reftable [v6]: new ref storage format","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-08-18T09:24:18Z","receivedAt":"2017-08-18T09:24:28Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On Wed, Aug 16, 2017 at 12:47 AM, Shawn Pearce <spearce@spearce.org> wrote:\n> On Mon, Aug 14, 2017 at 5:13 AM, Michael Haggerty <mhagger@alum.mit.edu> wrote:\n>> On 08/07/2017 03:47 AM, Shawn Pearce wrote:\n>>> 6th iteration of the reftable storage format.\n> [...]\n>>> #### index record\n>>>\n>>> An index record describes the last entry in another block.\n>>> Index records are written as:\n>>>\n>>>     varint( prefix_length )\n>>>     varint( (suffix_length << 3) | 0 )\n>>>     suffix\n>>>     varint( block_position )\n>>>\n>>> Index records use prefix compression exactly like `ref_record`.\n>>>\n>>> Index records store `block_position` after the suffix, specifying the\n>>> absolute position in bytes (from the start of the file) of the block\n>>> that ends with this reference.\n>>\n>> Is there a reason that the index lists the *last* refname that is\n>> contained in a block rather than the *first* refname? I can't think of a\n>> reason to choose one vs. the other, but your choice was initially\n>> surprising. I don't think it matters either way; I was just curious.\n>\n> Yes, there is a reason. When a reader is searching the index block and\n> discovers a key that is greater than their search needle, they are now\n> sitting on a record with the block_position for that greater key. By\n> using the *last* refname the current block_position is the one to seek\n> to.\n>\n> If instead we used *first* refname, the reader would now have to\n> backtrack to the prior index record to get the block_position out of\n> that record. Or it has to keep a running \"prior_position\" local\n> variable.\n>\n> Using last simplifies the reader's code.\n\nAh, OK. I was thinking of this as being a binary search, in which case\nyou *must* see both bracketing records before you are done, and the\nchances are 50-50 which one you see first. But this search is a little\nbit different, because the index records within a restart block have\nto be scanned linearly. So it is much more likely that you see the\n\"before\" record followed by the \"after\" record.\n\nThanks for the explanation.\n\nMichael\n"}]}