{"thread":{"id":"39699","subject":"RFC/Pull Request: Refs db backend","startedAt":"2015-06-23T00:50:56Z","lastAt":"2015-06-25T01:08:15Z","messageCount":26,"participants":["David Turner","Junio C Hamano","Duy Nguyen","Jeff King","Michael Haggerty","Stefan Beller","Randall S. Becker","Shawn Pearce","brian m. carlson"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"264611","messageId":"1435020656.28466.8.camel@twopensource.com","threadId":"39699","inReplyTo":null,"subject":"RFC/Pull Request: Refs db backend","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-06-23T00:50:56Z","receivedAt":"2015-06-23T00:50:56Z","isPatch":false,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"I've revived and modified Ronnie Sahlberg's work on the refs db\nbackend.  \n\nThe work is on top of be3c13e5564, Junio's \"First batch for 2.5 cycle\".\nI recognize that there have been changes to the refs code since then,\nand that there are some further changes in-flight from e.g. Michael\nHaggerty.  If there is interest in this, I can rebase once Michael's\nchanges land.\n\nThe changes can be found here:\nhttps://github.com/dturner-tw/git.git on the dturner/pluggable-backends\nbranch\n\nThe db backend code was added in the penultimate commit; the rest is\njust code rearrangement and minor changes to make alternate backends\npossible.  There ended up being a fair amount of this rearrangement, but\nthe end result is that almost the entire git test suite runs under the\ndb backend without error (see below for details).\n\nThe db backend runs git for-each-ref about 30% faster than the files\nbackend with fully-packed refs on a repo with ~120k refs.  It's also\nabout 4x faster than using fully-unpacked refs.  In addition, and\nperhaps more importantly, it avoids case-conflict issues on OS X.\n\nI chose to use LMDB for the database.  LMDB has a few features that make\nit suitable for usage in git:\n\n1. It is relatively lightweight; it requires only one header file, and\nthe library itself is under 300k (as opposed to 700k for\ne.g. sqlite).\n\n2. It is well-tested: it's been used in OpenLDAP for years.\n\n3. It's very fast.  LMDB's benchmarks show that it is among\nthe fastest key-value stores.\n\n4. It has a relatively simple concurrency story; readers don't\nblock writers and writers don't block readers.\n\nRonnie Sahlberg's original version of this patchset used tdb.  The\nadvantage of tdb is that it's smaller (~125k).  The disadvantages are\nthat tdb is hard to build on OS X.  It's also not in homebrew.  So lmdb\nseemed simpler.\n\nTo test this backend's correctness, I hacked test-lib.sh and\ntest-lib-functions.sh to run all tests under the refs backend. Dozens\nof tests use manual ref/reflog reading/writing, or create submodules\nwithout passing --refs-backend-type to git init.  If those tests are\nchanged to use the update-ref machinery or test-refs-be-db (or, in the\ncase of packed-refs, corrupt refs, and dumb fetch tests, are skipped),\nthe only remaining failing tests are the git-new-workdir tests and the\ngitweb tests.  \n\nPlease let me know how it would be best to proceed. \n"},{"id":"264613","messageId":"xmqqvbefdm0d.fsf@gitster.dls.corp.google.com","threadId":"39699","inReplyTo":"1435020656.28466.8.camel@twopensource.com","subject":"Re: RFC/Pull Request: Refs db backend","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-06-23T05:36:18Z","receivedAt":"2015-06-23T05:36:18Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Turner <dturner@twopensource.com> writes:\n\n> I've revived and modified Ronnie Sahlberg's work on the refs db\n> backend.  \n>\n> The work is on top of be3c13e5564, Junio's \"First batch for 2.5 cycle\".\n> I recognize that there have been changes to the refs code since then,\n> and that there are some further changes in-flight from e.g. Michael\n> Haggerty.  If there is interest in this, I can rebase once Michael's\n> changes land.\n> ...\n> The db backend runs git for-each-ref about 30% faster than the files\n> backend with fully-packed refs on a repo with ~120k refs.  It's also\n> about 4x faster than using fully-unpacked refs.  In addition, and\n> perhaps more importantly, it avoids case-conflict issues on OS X.\n>\n> I chose to use LMDB for the database...\n> ...\n> Ronnie Sahlberg's original version of this patchset used tdb.  The\n> advantage of tdb is that it's smaller (~125k).  The disadvantages are\n> that tdb is hard to build on OS X.  It's also not in homebrew.  So lmdb\n> seemed simpler.\n\n\"If there is interest\"?  Shut up and take my money ;-)\n\nMore seriously, that's great that you stepped up to resurrect this\ntopic.  In a sense, the choice of sample database backend does not\nmatter.  I do not care if it is tdb, lmdb, or even Berkeley DB as\nlong as it functions. ;-)\n\nAs long as the interface between ref-transaction system on the Git\nside and the database backend is designed right, your lmdb thing can\nserve as a reference implementation for other people to plug other\ndatabase backends to the same interface, right?  As one step to\nvalidate the interface to the database backends, it would be nice to\neventually have at least two backends that talk to meaningfully\ndifferent systems, but we have to start somewhere, and \"for now we\nhave lmdb\" is as good a place to start as any other db backend.\n\nI wonder if we can do a \"filesystem\" backend on top of the same\nbackend interface---is that too much impedance mismatch to make it\nunpractical?\n\nThanks.\n"},{"id":"264618","messageId":"CACsJy8DA3oOt8QRsztdJXwmfUwDvY_nGALQrOpSA3M_eNSuT8g@mail.gmail.com","threadId":"39699","inReplyTo":"xmqqvbefdm0d.fsf@gitster.dls.corp.google.com","subject":"Re: RFC/Pull Request: Refs db backend","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2015-06-23T10:23:09Z","receivedAt":"2015-06-23T10:23:09Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Jun 23, 2015 at 12:36 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> \"If there is interest\"?  Shut up and take my money ;-)\n\nYeah. This may be the next big thing since pack bitmap. It's even\nbetter if it enters 'master' hand in hand with pack protocol v2, but I\nthink v2 needs more time.\n\nOn Tue, Jun 23, 2015 at 7:50 AM, David Turner <dturner@twopensource.com> wrote:\n> To test this backend's correctness, I hacked test-lib.sh and\n> test-lib-functions.sh to run all tests under the refs backend.\n\nNow we have two. split-index also benefits from running through full\ntest suite like this. I propose we make \"make test\" run the test suite\ntwice. The first run is with default configuration, no split index, no\nfancy ref backend. The second run enables split-index and switches to\nnew backend, running through all test cases. In future we can also\nenable packv4 in this second run. There won't be a third run.\n\nWhen the second ref backend comes, we can switch between the two\nbackends using a random number generator where we control both\nalgorithm and seed, so that when a test fails, the user can give us\ntheir seed and we can re-run with the same configuration.\n\n> Dozens of tests use manual ref/reflog reading/writing, or create submodules\n> without passing --refs-backend-type to git init.  If those tests are\n> changed to use the update-ref machinery or test-refs-be-db (or, in the\n> case of packed-refs, corrupt refs, and dumb fetch tests, are skipped),\n> the only remaining failing tests are the git-new-workdir tests and the\n> gitweb tests.\n\nI haven't read the series, but I guess you should also add a few tests\nto run on the first run, so new code is exercised a bit even if people\nskip the second run.\n-- \nDuy\n"},{"id":"264626","messageId":"20150623114716.GC12518@peff.net","threadId":"39699","inReplyTo":"1435020656.28466.8.camel@twopensource.com","subject":"Re: RFC/Pull Request: Refs db backend","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-06-23T11:47:16Z","receivedAt":"2015-06-23T11:47:16Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jun 22, 2015 at 08:50:56PM -0400, David Turner wrote:\n\n> The db backend runs git for-each-ref about 30% faster than the files\n> backend with fully-packed refs on a repo with ~120k refs.  It's also\n> about 4x faster than using fully-unpacked refs.  In addition, and\n> perhaps more importantly, it avoids case-conflict issues on OS X.\n\nNeat.\n\nCan you describe a bit more about the reflog handling?\n\nOne of the problems we've had with large-ref repos is that the reflog\nstorage is quite inefficient. You can pack all the refs, but you may\nstill be stuck with a bunch of reflog files with one entry, wasting a\nwhole inode. Doing a \"git repack\" when you have a million of those has\nhorrible cold-cache performance. Basically anything that isn't\none-file-per-reflog would be a welcome change. :)\n\nIt has also been a dream of mine to stop tying the reflogs specifically\nto the refs. I.e., have a spot for reflogs of branches that no longer\nexist, which allows us to retain them for deleted branches. Then you can\npossibly recover from a branch deletion, whereas now you have to dig\nthrough \"git fsck\"'s dangling output. And the reflog, if you don't\nexpire it, becomes a suitable audit log to find out what happened to\neach branch when (whereas now it is full of holes when things get\ndeleted).\n\nDoes your solution handle something like that?\n\nI was thinking of actually moving to a log-structured ref storage.\nSomething like:\n\n  - any ref write puts a line at the end of a single logfile that\n    contains the ref name, along with the normal reflog data\n\n  - the logfile is the source of truth for the ref state. If you want to\n    know the value of any ref, you can read it backwards to find the\n    last entry for the ref. Everything else is an optimization.\n\n    Let's call the number of refs N, and the number of ref updates in\n    the log U.\n\n  - we keep a key/value index mapping the name of any branch that exists\n    to the byte offset of its entry in the logfile. This would probably\n    be in some binary key/value store (like LMDB). Without this,\n    resolving a ref is O(U), which is horrible. With it, it should be\n    O(1) or O(lg N), depending on the index data structure.\n\n  - the index can also contain other optimizations. E.g., rather than\n    point to the entry in the logfile, it can include the sha1 directly\n    (to avoid an extra level of indirection). It may want to include the\n    \"peeled\" value, as the current packed-refs file does.\n\n  - Reading all of the reflogs (e.g., for repacking) is O(U), just like\n    it is today. Except the storage for the logfile is a lot more\n    compact than what we store today, with one reflog per file.\n\n  - Reading a single reflog is _also_ O(U), which is not as good as\n    today. But if each log entry contains a byte offset of the previous\n    entry, you can follow the chain (it is still slightly worse, because\n    you are jumping all over the file, rather than reading a compact set\n    of lines).\n\n  - Pruning the reflog entries from the logfile requires rewriting the\n    whole thing. That's similar to today, where we rewrite each of the\n    reflog files.\n\nOne of the nice properties of this system is that it should be very\nresilient to corruption and races. Most of the operations are either\nappending to a file, or writing to a tempfile and renaming in place.\nThe exception is the key/value index, but if we run into any problems\nthere, it can be rebuilt by walking over the logfile (for a cost of\nO(U)).\n\nI dunno. Maybe I am overthinking it. But it really feels like the _refs_\nare a key/value thing, but the _reflogs_ are not. You can cram them into\na key/value store, but you're probably operating on them as a big blob,\nthen.\n\n> I chose to use LMDB for the database.  LMDB has a few features that make\n> it suitable for usage in git:\n\nOne of the complaints that Shawn had about sqlite is that there is no\nnative Java implementation, which makes it hard for JGit to ship a\ncompatible backend. I suspect the same is true for LMDB, but it is\nprobably a lot simpler than sqlite (so reimplementation might be\npossible).\n\nBut it may also be worth going with a slightly slower database if we can\nget wider compatibility for free.\n\n> To test this backend's correctness, I hacked test-lib.sh and\n> test-lib-functions.sh to run all tests under the refs backend. Dozens\n> of tests use manual ref/reflog reading/writing, or create submodules\n> without passing --refs-backend-type to git init.  If those tests are\n> changed to use the update-ref machinery or test-refs-be-db (or, in the\n> case of packed-refs, corrupt refs, and dumb fetch tests, are skipped),\n> the only remaining failing tests are the git-new-workdir tests and the\n> gitweb tests.\n\nI think we'll need to bump core.repositoryformatversion, too. See the\npatches I just posted here:\n\n  http://thread.gmane.org/gmane.comp.version-control.git/272447\n\n-Peff\n"},{"id":"264629","messageId":"CACsJy8B=jthxn_E-zWnDfua29FGGgz221N-cLw=NxeVOKadUxA@mail.gmail.com","threadId":"39699","inReplyTo":"20150623114716.GC12518@peff.net","subject":"Re: RFC/Pull Request: Refs db backend","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2015-06-23T13:10:03Z","receivedAt":"2015-06-23T13:10:03Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Jun 23, 2015 at 6:47 PM, Jeff King <peff@peff.net> wrote:\n> I was thinking of actually moving to a log-structured ref storage.\n> Something like:\n>\n>   - any ref write puts a line at the end of a single logfile that\n>     contains the ref name, along with the normal reflog data\n>\n>   - the logfile is the source of truth for the ref state. If you want to\n>     know the value of any ref, you can read it backwards to find the\n>     last entry for the ref. Everything else is an optimization.\n>\n>     Let's call the number of refs N, and the number of ref updates in\n>     the log U.\n>\n>   - we keep a key/value index mapping the name of any branch that exists\n>     to the byte offset of its entry in the logfile. This would probably\n\nOne key/value mapping per branch, pointing to the latest reflog entry,\nor one key/valye mapping for each reflog entry?\n\n>     be in some binary key/value store (like LMDB). Without this,\n>     resolving a ref is O(U), which is horrible. With it, it should be\n>     O(1) or O(lg N), depending on the index data structure.\n\nI'm thinking of the user with small or medium repos, in terms of refs,\nwho does not want an extra dependency. If we store one mapping per\nbranch, then the size of this mapping is small enough that the index\nin a text file is ok. If we also store the offset to the previous\nreflog entry of the same branch in the current reflog entry, like a\nback pointer, then we could jump back faster.\n\nOr do you have something else in mind? Current reflog structure won't\nwork because I think you bring back the reflog graveyard with this,\nand I don't want to lose that\n\n>   - the index can also contain other optimizations. E.g., rather than\n>     point to the entry in the logfile, it can include the sha1 directly\n>     (to avoid an extra level of indirection). It may want to include the\n>     \"peeled\" value, as the current packed-refs file does.\n>\n>   - Reading all of the reflogs (e.g., for repacking) is O(U), just like\n>     it is today. Except the storage for the logfile is a lot more\n>     compact than what we store today, with one reflog per file.\n>\n>   - Reading a single reflog is _also_ O(U), which is not as good as\n>     today. But if each log entry contains a byte offset of the previous\n>     entry, you can follow the chain (it is still slightly worse, because\n>     you are jumping all over the file, rather than reading a compact set\n>     of lines).\n>\n>   - Pruning the reflog entries from the logfile requires rewriting the\n>     whole thing. That's similar to today, where we rewrite each of the\n>     reflog files.\n-- \nDuy\n"},{"id":"264631","messageId":"55898073.4010105@alum.mit.edu","threadId":"39699","inReplyTo":"1435020656.28466.8.camel@twopensource.com","subject":"Re: RFC/Pull Request: Refs db backend","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2015-06-23T15:51:15Z","receivedAt":"2015-06-23T15:51:15Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 06/23/2015 02:50 AM, David Turner wrote:\n> I've revived and modified Ronnie Sahlberg's work on the refs db\n> backend.  \n> \n> The work is on top of be3c13e5564, Junio's \"First batch for 2.5 cycle\".\n> I recognize that there have been changes to the refs code since then,\n> and that there are some further changes in-flight from e.g. Michael\n> Haggerty.  If there is interest in this, I can rebase once Michael's\n> changes land.\n\nIt's awesome that you are working on this!\n\nI'm reading through your commits and will add comments as they pop into\nmy head...\n\n* I initially read \"refs-be-files\" to be a short version of \"references,\nthey be files\". I might never be able to get that pronunciation out of\nmy head :-)\n\n* It would be more modest to call the files implementing the LMDB\nbackend \"refs-be-lmdb.[c,h]\" rather than \"refs-be-db.[c,h]\".\n\n* I wonder whether `refname_is_safe()` might eventually have to become\nbackend-specific. For example, maybe one backend will have to impose a\nlimit of 128 characters or something? No matter, though...it can be\nmoved later.\n\n* You have put `format_reflog_msg()` in the public interface. It\nprobably makes sense, because more than one backend might want to use\nit. But another backend might want to store (refname, old_sha1,\nnew_sha1, ...) as separate columns in a database. As long as\n`format_reflog_msg()` is seen as a helper function and is not called by\nany of the shared code, it shouldn't be a problem.\n\n* I wonder whether `init_backend()` will be general enough. I'm thinking\nby analogy with object constructors, which usually need class-specific\narguments during their initialization even though afterwards objects of\ndifferent classes can be used interchangeably. So I guess the idea is\nthat a typical `init_backend()` function will have to dig around itself\nto find whatever additional information that it needs (e.g., from the\ngit configuration or the filesystem or whatever). So I think this is OK.\n\n* Your \"methods for bulk updates\" are I think analogous to the\n`initial_ref_transaction_commit()` function that I recently submitted\n[1]. Either way, the goal is to abstract away the fact that the\nfile-based backend uses packed and loose references with tradeoffs that\ncallers currently have to know about.\n\n* I don't like the fact that you have replaced `struct ref_transaction\n*` with `void *` in the public interface. On a practical level, I like\nthe bit of type-safety that comes with the more specific declaration.\nBut on a more abstract level, I think that the concept of a transaction\ncould be useful across backends, for example in utility functions that\nverify that a proposed set of updates are internally consistent. I would\nrather see either\n\n  * backends \"extend\" a basic `struct ref_transaction` to suit their\nneeds, and upcast/downcast pointers at the module boundary, or\n\n  * `struct ref_transaction` itself gets a `void *` member that backends\ncan use for whatever purposes they want.\n\n* Regarding MERGE_HEAD: you take the point of view that it must continue\nto be stored as a file. And yet it must also behave somewhat like a\nreference; for example, `git rev-parse MERGE_HEAD` works today.\nMERGE_HEAD is also used for reachability, right?\n\nAnother point of view is that MERGE_HEAD is a plain old boring\nreference, but there is some other metadata related to it that the refs\nbackend has to store. The file-based backend would have special-case\ncode to read the additional data from the tail of the loose refs file\n(and be sure to write the metadata when writing the reference), but\nother backends could store the reference with the rest but do their own\nthing with the metadata. So I guess I'm wondering whether the refs API\nneeds a MERGE_HEAD-specific way to read and write MERGE_HEAD along with\nits metadata.\n\n* Don't the same considerations that apply to MERGE_HEAD also apply to\nFETCH_HEAD?\n\n* I'm showing my ignorance of LMDB, but I don't see where the LMDB\nbackend initializes its database during `git init-db`. Is that what\n`init_env()` does? But it looks like `init_env()` is called on every git\ninvocation (via `git_config_early()`). Puzzled.\n\n* Meanwhile, `create_default_files()` (in `builtin/init-db`) still\ncreates directories `refs`, `refs/heads`, and `refs/tags`.\n\n* Rehash of the last two points: I expected one backend function that is\nused to initialize the refs backend when a new repository is created\n(e.g., in `git init`). The file-based backend would use this function to\ncreate the `refs`, `refs/heads`, and `refs/tags` directories. I expected\na second function that is called once every time git runs in an existing\nrepository (this one might, for example, open a database connection).\nAnd maybe even a third one that closes down the database connection\nbefore git exits. Would you please explain how this actually works?\n\n* `lmdb_init_backend()` leaks `path` if `env` is already set (in which\ncase it needn't compute `path` in the first place).\n\n* You have the constraint that submodules need to use the same reference\nbackend as the main repository. But it looks like each submodule has its\nown independent database. So why the restriction?\n\nIt might be a sign that the design is not optimal if it is only able to\nhandle one *type* of reference backend in a single run.\n\nIn object-oriented language, I would expect a `Refs` object to represent\nthe reference storage for a single repository or submodule. The VTABLE\nfor the object would be a `struct ref_be`. But the object should also\nhave an object pointer that can store per-instance data. I think the\nper-instance data is missing in your design.\n\nWhen I start up, I would instantiate a `Refs` instance for the main\nrepository, which creates either a `FileRefs` or a `LMDBRefs` instance.\nThis instance would be used to access the refs for the main repository.\nIt could be stored in a global variable, similarly to how `ref_cache` is\ncurrently stored. (Indeed, `struct ref_cache` would be subsumed into\n`FileRefs`.)\n\nIf I want to access references in a submodule, there would again be an\ninitialization process for that sub-repository, which checks the type of\nreferences backend that the repository uses and instantiates either a\n`FileRefs` or a `LMDBRefs` instance to represent *that* repository. The\nsubmodule instances could be stored by submodule name in a lookup table,\nlike submodule_ref_caches is currently stored. Since it has its own\ninstance data, the `Refs` instance for a submodule can coexist with the\n`Refs` instance for the main repository even if they are of different types.\n\nBut even aside from supporting heterogeneous submodules, I think adding\ninstance data to the design would make it quite a bit more flexible,\nbecause it would also allow reference backends to be composed. For\nexample, one could implement a reference backend that maps\n`refs/remotes/origin` to a namespace in another repository, for a\ntransparent view of an upstream repo (using alternates to share objects)\nthat doesn't have to be updated when references are updated in the\norigin. Or we could implement loose and packed references as two\nseparate backends that are layered on each other. Or we could implement\na lightweight \"mirror\" clone with copy-on-write semantics for\nreferences. We could arrange to store all of the references for a\ntop-level repo and its submodules in a single database, potentially\nallowing atomic upgrades across repositories [2].\n\n* You explain in the docstring to `lmdb_transaction_begin_flags()` that\nit is dangerous to call a callback function while a write transaction is\nopen if the callback function might want to initiate another write\ntransaction. This would obviously also apply to running hooks. This is a\nlimitation of LMDB because writers block each other. I can't think of\nanyplace that this would be a problem in our codebase. But if it were,\nit seems to me that you could take an approach like the file-based\nbackend, which collects the transaction in a `ref_transaction` data\nstructure, and executes the entire transaction within a single call to\n`ref_transaction_commit()`. This approach would prevent callers outside\nof the refs module from ever bumping against this limitation.\n\nSo, that was my stream-of-consciousness about your patch series. Overall\nI like it very much. I have only skimmed it so far, and hardly read the\nlast two patches at all, but what I saw all looked good and well-organized.\n\nPlease CC me on future versions of this patch series, because it is very\nclose to my interests. I've put a lot of effort into encapsulating and\nabstracting the refs module with the goal of getting to pluggable\nreference backends (plus some other stuff), so it's great to see what\nyou have accomplished!\n\nLet me know if you need any help rebasing your work onto my recent\nchanges. It would probably work best if you break your patch series into\nsmaller pieces to make them easier for the mailing list to digest. For\nexample, the first installment could be the patches that make sense even\nindependent of the plan to add support for multiple backends: the first\ntwo patches, plus the ones related to CHERRY_PICK_HEAD and its cousins,\nthe abstraction of the reflog functions, and the `git reflog create` and\n`git reflog exists` subcommands.\n\nMichael\n\n[1] http://article.gmane.org/gmane.comp.version-control.git/272362\n[2] To implement this feature, it might be necessary to make the `Refs`\ninstance for the main repository responsible for instantiating the\n`Refs` instance for submodules.\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\n"},{"id":"264634","messageId":"CAGZ79kap++fZx3X0D95d35XioRURU468xATDZpWHDOAPapAh+Q@mail.gmail.com","threadId":"39699","inReplyTo":"1435020656.28466.8.camel@twopensource.com","subject":"Re: RFC/Pull Request: Refs db backend","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2015-06-23T17:16:26Z","receivedAt":"2015-06-23T17:16:26Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"[+<ronniesahlberg@gmail.com>, FYI]\n\nOn Mon, Jun 22, 2015 at 5:50 PM, David Turner <dturner@twopensource.com> wrote:\n> I've revived and modified Ronnie Sahlberg's work on the refs db\n> backend.\n\nAwesome!\n\n>\n> The work is on top of be3c13e5564, Junio's \"First batch for 2.5 cycle\".\n> I recognize that there have been changes to the refs code since then,\n> and that there are some further changes in-flight from e.g. Michael\n> Haggerty.  If there is interest in this, I can rebase once Michael's\n> changes land.\n\nOriginally I wanted to continue on Ronnies work, but because of the churn\nin refs I stopped it for a while and took care of other projects (and wanted\nto come back eventually). Thanks for reviving this topic!\n\n> The changes can be found here:\n> https://github.com/dturner-tw/git.git on the dturner/pluggable-backends\n> branch\n>\n> The db backend code was added in the penultimate commit; the rest is\n> just code rearrangement and minor changes to make alternate backends\n> possible.  There ended up being a fair amount of this rearrangement, but\n> the end result is that almost the entire git test suite runs under the\n> db backend without error (see below for details).\n\nLooking at the end result in refs-be-db.c it feels like there are more\nfunctions in the refs_be_db struct, did this originate from other design\nchoices? IIRC Ronnie wanted to have as least functions in there as\npossible, and share as much of the code between the databases, such\nthat the glue between the db and the refs code is minimal.\n\nSome random comments from looking over the branch briefly:\n\nIn the latest commit, (refs: tests for db backend), I am unsure about the\ncopyright annotations. At least a sole \"Copyright (c) 2007 Junio C Hamano\"\ndoesn't make sense to me. ;)\n\nTypo in commit message \"bisect: use refs insfrastructure for BISECT_START\"\n\nSome commits contain a ChangeId, which is a Gerrit leftover. :(\n\nThanks,\nStefan\n\n>\n> The db backend runs git for-each-ref about 30% faster than the files\n> backend with fully-packed refs on a repo with ~120k refs.  It's also\n> about 4x faster than using fully-unpacked refs.  In addition, and\n> perhaps more importantly, it avoids case-conflict issues on OS X.\n>\n> I chose to use LMDB for the database.  LMDB has a few features that make\n> it suitable for usage in git:\n>\n> 1. It is relatively lightweight; it requires only one header file, and\n> the library itself is under 300k (as opposed to 700k for\n> e.g. sqlite).\n>\n> 2. It is well-tested: it's been used in OpenLDAP for years.\n>\n> 3. It's very fast.  LMDB's benchmarks show that it is among\n> the fastest key-value stores.\n>\n> 4. It has a relatively simple concurrency story; readers don't\n> block writers and writers don't block readers.\n>\n> Ronnie Sahlberg's original version of this patchset used tdb.  The\n> advantage of tdb is that it's smaller (~125k).  The disadvantages are\n> that tdb is hard to build on OS X.  It's also not in homebrew.  So lmdb\n> seemed simpler.\n>\n> To test this backend's correctness, I hacked test-lib.sh and\n> test-lib-functions.sh to run all tests under the refs backend. Dozens\n> of tests use manual ref/reflog reading/writing, or create submodules\n> without passing --refs-backend-type to git init.  If those tests are\n> changed to use the update-ref machinery or test-refs-be-db (or, in the\n> case of packed-refs, corrupt refs, and dumb fetch tests, are skipped),\n> the only remaining failing tests are the git-new-workdir tests and the\n> gitweb tests.\n>\n> Please let me know how it would be best to proceed.\n>\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n"},{"id":"264636","messageId":"1435080541.28466.13.camel@twopensource.com","threadId":"39699","inReplyTo":"xmqqvbefdm0d.fsf@gitster.dls.corp.google.com","subject":"Re: RFC/Pull Request: Refs db backend","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-06-23T17:29:01Z","receivedAt":"2015-06-23T17:29:01Z","isPatch":false,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Mon, 2015-06-22 at 22:36 -0700, Junio C Hamano wrote:\n> David Turner <dturner@twopensource.com> writes:\n> \n> > I've revived and modified Ronnie Sahlberg's work on the refs db\n> > backend.  \n> >\n> > The work is on top of be3c13e5564, Junio's \"First batch for 2.5 cycle\".\n> > I recognize that there have been changes to the refs code since then,\n> > and that there are some further changes in-flight from e.g. Michael\n> > Haggerty.  If there is interest in this, I can rebase once Michael's\n> > changes land.\n> > ...\n> > The db backend runs git for-each-ref about 30% faster than the files\n> > backend with fully-packed refs on a repo with ~120k refs.  It's also\n> > about 4x faster than using fully-unpacked refs.  In addition, and\n> > perhaps more importantly, it avoids case-conflict issues on OS X.\n> >\n> > I chose to use LMDB for the database...\n> > ...\n> > Ronnie Sahlberg's original version of this patchset used tdb.  The\n> > advantage of tdb is that it's smaller (~125k).  The disadvantages are\n> > that tdb is hard to build on OS X.  It's also not in homebrew.  So lmdb\n> > seemed simpler.\n> \n> \"If there is interest\"?  Shut up and take my money ;-)\n> \n> More seriously, that's great that you stepped up to resurrect this\n> topic.  In a sense, the choice of sample database backend does not\n> matter.  I do not care if it is tdb, lmdb, or even Berkeley DB as\n> long as it functions. ;-)\n> \n> As long as the interface between ref-transaction system on the Git\n> side and the database backend is designed right, your lmdb thing can\n> serve as a reference implementation for other people to plug other\n> database backends to the same interface, right? \n\nYes.\n\n>  As one step to\n> validate the interface to the database backends, it would be nice to\n> eventually have at least two backends that talk to meaningfully\n> different systems, but we have to start somewhere, and \"for now we\n> have lmdb\" is as good a place to start as any other db backend.\n> \n> I wonder if we can do a \"filesystem\" backend on top of the same\n> backend interface---is that too much impedance mismatch to make it\n> unpractical?\n\nThe patch series does include a filesystem backend, which is simply the\ncurrent ref infrastructure with extremely minor changes.  \n"},{"id":"264647","messageId":"1435083516.28466.24.camel@twopensource.com","threadId":"39699","inReplyTo":"20150623114716.GC12518@peff.net","subject":"Re: RFC/Pull Request: Refs db backend","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-06-23T18:18:36Z","receivedAt":"2015-06-23T18:18:36Z","isPatch":false,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Tue, 2015-06-23 at 07:47 -0400, Jeff King wrote:\n> On Mon, Jun 22, 2015 at 08:50:56PM -0400, David Turner wrote:\n> \n> > The db backend runs git for-each-ref about 30% faster than the files\n> > backend with fully-packed refs on a repo with ~120k refs.  It's also\n> > about 4x faster than using fully-unpacked refs.  In addition, and\n> > perhaps more importantly, it avoids case-conflict issues on OS X.\n> \n> Neat.\n> \n> Can you describe a bit more about the reflog handling?\n> \n> One of the problems we've had with large-ref repos is that the reflog\n> storage is quite inefficient. You can pack all the refs, but you may\n> still be stuck with a bunch of reflog files with one entry, wasting a\n> whole inode. Doing a \"git repack\" when you have a million of those has\n> horrible cold-cache performance. Basically anything that isn't\n> one-file-per-reflog would be a welcome change. :)\n\nReflogs are stored in the database as well.  There is one header entry\nper ref to indicate that a reflog is present, and then one database\nentry per reflog entry; the entries are stored consecutively and\nimmediately following the header so that it's fast to iterate over them.\n\n> It has also been a dream of mine to stop tying the reflogs specifically\n> to the refs. I.e., have a spot for reflogs of branches that no longer\n> exist, which allows us to retain them for deleted branches. Then you can\n> possibly recover from a branch deletion, whereas now you have to dig\n> through \"git fsck\"'s dangling output. And the reflog, if you don't\n> expire it, becomes a suitable audit log to find out what happened to\n> each branch when (whereas now it is full of holes when things get\n> deleted).\n\nThat would be cool, and I don't think it would be hard to add to my\ncurrent code; we could simply replace the header with a \"tombstone\".\nBut I would prefer to wait until the series is merged; then we can build\non top of it.\n\n> I dunno. Maybe I am overthinking it. But it really feels like the _refs_\n> are a key/value thing, but the _reflogs_ are not. You can cram them into\n> a key/value store, but you're probably operating on them as a big blob,\n> then.\n\nReflogs are, conceptually, queues. I agree that a raw key-value store is\nnot a good way to store queues, but a B-Tree is not so terrible, since\nit offers relatively fast iteration (amortized constant time IIRC).\n\n> > I chose to use LMDB for the database.  LMDB has a few features that make\n> > it suitable for usage in git:\n> \n> One of the complaints that Shawn had about sqlite is that there is no\n> native Java implementation, which makes it hard for JGit to ship a\n> compatible backend. I suspect the same is true for LMDB, but it is\n> probably a lot simpler than sqlite (so reimplementation might be\n> possible).\n> \n> But it may also be worth going with a slightly slower database if we can\n> get wider compatibility for free.\n\nThere's a JNI interface to LMDB, which is, of course, not native.  I\ndon't think it would be too hard to entirely rewrite LMDB in Java, but\nI'm not going to have time to do it for the forseeable future.  I've\nasked Howard Chu if he knows of any efforts in progress.\n\n> > To test this backend's correctness, I hacked test-lib.sh and\n> > test-lib-functions.sh to run all tests under the refs backend. Dozens\n> > of tests use manual ref/reflog reading/writing, or create submodules\n> > without passing --refs-backend-type to git init.  If those tests are\n> > changed to use the update-ref machinery or test-refs-be-db (or, in the\n> > case of packed-refs, corrupt refs, and dumb fetch tests, are skipped),\n> > the only remaining failing tests are the git-new-workdir tests and the\n> > gitweb tests.\n> \n> I think we'll need to bump core.repositoryformatversion, too. See the\n> patches I just posted here:\n> \n>   http://thread.gmane.org/gmane.comp.version-control.git/272447\n\nThanks, that's valuable.  For the refs backend, opening the LMDB\ndatabase for writing is sufficient to block other writers.  Do you think\nit would be valuable to provide a git hold-ref-lock command that simply\nreads refs from stdin and keeps them locked until it reads EOF from\nstdin?  That would allow cross-backend ref locking. \n"},{"id":"264650","messageId":"1435085226.28466.37.camel@twopensource.com","threadId":"39699","inReplyTo":"CACsJy8DA3oOt8QRsztdJXwmfUwDvY_nGALQrOpSA3M_eNSuT8g@mail.gmail.com","subject":"Re: RFC/Pull Request: Refs db backend","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-06-23T18:47:06Z","receivedAt":"2015-06-23T18:47:06Z","isPatch":false,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Tue, 2015-06-23 at 17:23 +0700, Duy Nguyen wrote:\n> On Tue, Jun 23, 2015 at 7:50 AM, David Turner\n<dturner@twopensource.com> wrote:\n> > To test this backend's correctness, I hacked test-lib.sh and\n> > test-lib-functions.sh to run all tests under the refs backend.\n> \n> Now we have two. split-index also benefits from running through full\n> test suite like this. I propose we make \"make test\" run the test suite\n> twice. The first run is with default configuration, no split index, no\n> fancy ref backend. The second run enables split-index and switches to\n> new backend, running through all test cases. In future we can also\n> enable packv4 in this second run. There won't be a third run.\n> \n> When the second ref backend comes, we can switch between the two\n> backends using a random number generator where we control both\n> algorithm and seed, so that when a test fails, the user can give us\n> their seed and we can re-run with the same configuration.\n\nI'm not in love with this idea, because it makes it hard to do\nexhaustive testing efficiently.  I would rather have make test run\nthrough all tests under all combinations -- or at least all relevant\ntests.  We could perhaps mark tests with a list of features that they\nexercise, so that we don't have to run e.g. t8xxx with alternate refs\nbackends.  \n\n> Dozens of tests use manual ref/reflog reading/writing, or create\nsubmodules\n> > without passing --refs-backend-type to git init.  If those tests are\n> > changed to use the update-ref machinery or test-refs-be-db (or, in\nthe\n> > case of packed-refs, corrupt refs, and dumb fetch tests, are\nskipped),\n> > the only remaining failing tests are the git-new-workdir tests and\nthe\n> > gitweb tests.\n> \n> I haven't read the series, but I guess you should also add a few tests\n> to run on the first run, so new code is exercised a bit even if people\n> skip the second run.\n\nI did this already, yes.\n"},{"id":"264662","messageId":"1435089205.28466.56.camel@twopensource.com","threadId":"39699","inReplyTo":"55898073.4010105@alum.mit.edu","subject":"Re: RFC/Pull Request: Refs db backend","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-06-23T19:53:25Z","receivedAt":"2015-06-23T19:53:25Z","isPatch":false,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Tue, 2015-06-23 at 17:51 +0200, Michael Haggerty wrote:\n> On 06/23/2015 02:50 AM, David Turner wrote:\n> > I've revived and modified Ronnie Sahlberg's work on the refs db\n> > backend.  \n> > \n> > The work is on top of be3c13e5564, Junio's \"First batch for 2.5 cycle\".\n> > I recognize that there have been changes to the refs code since then,\n> > and that there are some further changes in-flight from e.g. Michael\n> > Haggerty.  If there is interest in this, I can rebase once Michael's\n> > changes land.\n> \n> It's awesome that you are working on this!\n> \n> I'm reading through your commits and will add comments as they pop into\n> my head...\n> \n> * I initially read \"refs-be-files\" to be a short version of \"references,\n> they be files\". I might never be able to get that pronunciation out of\n> my head :-)\n\nThat's OK so long as I can keep pronouncing \"reflog\" as \"re-flog\". ;)\n\n> * It would be more modest to call the files implementing the LMDB\n> backend \"refs-be-lmdb.[c,h]\" rather than \"refs-be-db.[c,h]\".\n\nAgreed.  Will fix.\n\n> * I wonder whether `refname_is_safe()` might eventually have to become\n> backend-specific. For example, maybe one backend will have to impose a\n> limit of 128 characters or something? No matter, though...it can be\n> moved later.\n\nI think it would be an error to allow backends to impose additional\nlimits on ref names.  The limits imposed by the current backend have\nbeen the cause of much sadness here at Twitter (primarily,\ncase-conflicts combined with d/f conflicts).\n\n> * You have put `format_reflog_msg()` in the public interface. It\n> probably makes sense, because more than one backend might want to use\n> it. But another backend might want to store (refname, old_sha1,\n> new_sha1, ...) as separate columns in a database. As long as\n> `format_reflog_msg()` is seen as a helper function and is not called by\n> any of the shared code, it shouldn't be a problem.\n\nAgreed.\n\n> * I wonder whether `init_backend()` will be general enough. \n\nWe can always upgrade it later.\n\n> * Your \"methods for bulk updates\" are I think analogous to the\n> `initial_ref_transaction_commit()` function that I recently submitted\n> [1]. Either way, the goal is to abstract away the fact that the\n> file-based backend uses packed and loose references with tradeoffs that\n> callers currently have to know about.\n\nYes, I saw your work after I had already started mine.\n\n> * I don't like the fact that you have replaced `struct ref_transaction\n> *` with `void *` in the public interface. On a practical level, I like\n> the bit of type-safety that comes with the more specific declaration.\n> But on a more abstract level, I think that the concept of a transaction\n> could be useful across backends, for example in utility functions that\n> verify that a proposed set of updates are internally consistent. I would\n> rather see either\n> \n>   * backends \"extend\" a basic `struct ref_transaction` to suit their\n> needs, and upcast/downcast pointers at the module boundary, or\n> \n>   * `struct ref_transaction` itself gets a `void *` member that backends\n> can use for whatever purposes they want.\n\nThere are no common fields between refs-be-file transactions and\nrefs-be-lmdb transactions.  I don't see much gain from adding an empty\nref_transaction that backends could extend, since we would have to\nexplicitly upcast/downcast all over the place.\n\n> * Regarding MERGE_HEAD: you take the point of view that it must continue\n> to be stored as a file. And yet it must also behave somewhat like a\n> reference; for example, `git rev-parse MERGE_HEAD` works today.\n> MERGE_HEAD is also used for reachability, right?\n> \n> Another point of view is that MERGE_HEAD is a plain old boring\n> reference, but there is some other metadata related to it that the refs\n> backend has to store. The file-based backend would have special-case\n> code to read the additional data from the tail of the loose refs file\n> (and be sure to write the metadata when writing the reference), but\n> other backends could store the reference with the rest but do their own\n> thing with the metadata. So I guess I'm wondering whether the refs API\n> needs a MERGE_HEAD-specific way to read and write MERGE_HEAD along with\n> its metadata.\n\nYou are probably right that this is a good idea.\n\n> * Don't the same considerations that apply to MERGE_HEAD also apply to\n> FETCH_HEAD?\n\nAll of the tests pass without any special handling of FETCH_HEAD.\n\n> * I'm showing my ignorance of LMDB, but I don't see where the LMDB\n> backend initializes its database during `git init-db`. Is that what\n> `init_env()` does? But it looks like `init_env()` is called on every git\n> invocation (via `git_config_early()`). Puzzled.\n\nThere is no need to explicitly create the database (other than with\nmkdir); init_env does everything for you.\n\n> * Meanwhile, `create_default_files()` (in `builtin/init-db`) still\n> creates directories `refs`, `refs/heads`, and `refs/tags`.\n\nYeah, that's legit.  I'll create a backend initdb function, and rename\ninit to setup.\n\n> * Rehash of the last two points: I expected one backend function that is\n> used to initialize the refs backend when a new repository is created\n> (e.g., in `git init`). The file-based backend would use this function to\n> create the `refs`, `refs/heads`, and `refs/tags` directories. I expected\n> a second function that is called once every time git runs in an existing\n> repository (this one might, for example, open a database connection).\n> And maybe even a third one that closes down the database connection\n> before git exits. Would you please explain how this actually works?\n\nLMDB doesn't really have the concept of a \"connection\".  It's basically\njust a couple of files that communicate using shared memory (and maybe\nsome other locking that I haven't paid attention to).  There is the\nconcept of a \"transaction\", which is the unit of concurrency (each\nthread may only have one open transaction).  Transactions are either\nread-only or read-write, and there can only be one read-write\ntransaction open at a time (across the entire system).  Read-only\ntransactions take a snapshot of the DB state at transaction start time.\nThis combination of features means that we need to be a bit clever about\nread-only transactions; if a read-write transaction occurs in a separate\nprocess, we need to restart any read-only transactions to pick up its\nchanges.\n\nRequiring an explicit disconnect from the database would be problematic\nbecause of the number of situations in which git just calls die(). If a\nbackend desires a disconnect, it would be best to just call atexit().\n\n> * `lmdb_init_backend()` leaks `path` if `env` is already set (in which\n> case it needn't compute `path` in the first place).\n\nWill fix, thanks.\n\n> * You have the constraint that submodules need to use the same reference\n> backend as the main repository. But it looks like each submodule has its\n> own independent database. So why the restriction?\n>\n> It might be a sign that the design is not optimal if it is only able to\n> handle one *type* of reference backend in a single run.\n\nYes, that is the reason.  I think it would be rather difficult to fix\nthis, but I guess it's possible.\n\n> In object-oriented language, I would expect a `Refs` object to represent\n> the reference storage for a single repository or submodule. The VTABLE\n> for the object would be a `struct ref_be`. But the object should also\n> have an object pointer that can store per-instance data. I think the\n> per-instance data is missing in your design.\n\nFor some of the code, that's the transaction.  But since we only ever\nhave one transaction, we could just move all that to the `Refs` object.\n\n<snip arguments for this> \n\nI'll try to write some code and see what this looks like.\n\n> * You explain in the docstring to `lmdb_transaction_begin_flags()` that\n> it is dangerous to call a callback function while a write transaction is\n> open if the callback function might want to initiate another write\n> transaction. This would obviously also apply to running hooks.\n\nI carefully limit the scope of write transactions to avoid problems like\nthis.\n\n>  This is a\n> limitation of LMDB because writers block each other. I can't think of\n> anyplace that this would be a problem in our codebase. But if it were,\n> it seems to me that you could take an approach like the file-based\n> backend, which collects the transaction in a `ref_transaction` data\n> structure, and executes the entire transaction within a single call to\n> `ref_transaction_commit()`. This approach would prevent callers outside\n> of the refs module from ever bumping against this limitation.\n\nThe file-based backend does per-ref locking early, and then applies the\ntransactions. Here, taking the write transaction is how the lmdb backend\ndoes locking.  So the situations are not quite the same.  But I think\nkeeping the scope of transactions small is the best plan.\n\n> So, that was my stream-of-consciousness about your patch series. Overall\n> I like it very much. I have only skimmed it so far, and hardly read the\n> last two patches at all, but what I saw all looked good and well-organized.\n\nThanks.  A fair amount of it is Ronnie's work, and I tried to copy his\napproach as much as possible.\n\n> Please CC me on future versions of this patch series, because it is very\n> close to my interests. I've put a lot of effort into encapsulating and\n> abstracting the refs module with the goal of getting to pluggable\n> reference backends (plus some other stuff), so it's great to see what\n> you have accomplished!\n\nWill do!\n\n> Let me know if you need any help rebasing your work onto my recent\n> changes. It would probably work best if you break your patch series into\n> smaller pieces to make them easier for the mailing list to digest. For\n> example, the first installment could be the patches that make sense even\n> independent of the plan to add support for multiple backends: the first\n> two patches, plus the ones related to CHERRY_PICK_HEAD and its cousins,\n> the abstraction of the reflog functions, and the `git reflog create` and\n> `git reflog exists` subcommands.\n\nI would love some help rebasing. I'll break out the patches you suggest\nand send them to the list, then create a new branch with the rest of the\nchanges.  Would that be a good place for you to start?\n"},{"id":"264663","messageId":"1435089895.28466.65.camel@twopensource.com","threadId":"39699","inReplyTo":"CAGZ79kap++fZx3X0D95d35XioRURU468xATDZpWHDOAPapAh+Q@mail.gmail.com","subject":"Re: RFC/Pull Request: Refs db backend","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-06-23T20:04:55Z","receivedAt":"2015-06-23T20:04:55Z","isPatch":false,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Tue, 2015-06-23 at 10:16 -0700, Stefan Beller wrote:\n> > The db backend code was added in the penultimate commit; the rest is\n> > just code rearrangement and minor changes to make alternate backends\n> > possible.  There ended up being a fair amount of this \n> > rearrangement,  but the end result is that almost the entire git \n> > test suite runs under the db backend without error (see below for \n> details).\n> \n> Looking at the end result in refs-be-db.c it feels like there are more\n> functions in the refs_be_db struct, did this originate from other \n> design choices? IIRC Ronnie wanted to have as least functions in \n> there as possible, and share as much of the code between the \n> databases, such that the glue between the db and the refs code is \n> minimal.\n\nI didn't actually spend that much time reading Ronnie's backend code.\nMy code aims to be extremely thoroughly compatible.  I spent a ton of\ntime making sure that the git test suite passed.  I don't know if an\nalternate approach would have been as compatible.\n\nThe requirement for reflog storage did complicate things a bit.\n\nI also didn't see a strong need to abstract the database, since LMDB is\ncommon, widely compatible, and tiny.  \n\n> Some random comments from looking over the branch briefly:\n> \n> In the latest commit, (refs: tests for db backend), I am unsure about \n> the copyright annotations. At least a sole \"Copyright (c) 2007 Junio C\n> Hamano\" doesn't make sense to me. ;)\n\nWill fix, thanks.\n\n> Typo in commit message \"bisect: use refs insfrastructure for \n> BISECT_START\"\n\nWill fix, thanks.\n\n> Some commits contain a ChangeId, which is a Gerrit leftover. :(\n\nThose were leftover from Ronnie's patches; since you are a Googler and\nyou think we don't need them, I'll remove them. \n"},{"id":"264665","messageId":"005101d0adf0$964bca10$c2e35e30$@nexbridge.com","threadId":"39699","inReplyTo":"1435089895.28466.65.camel@twopensource.com","subject":"RE: RFC/Pull Request: Refs db backend","fromName":"Randall S. Becker","fromEmail":"rsbecker@nexbridge.com","sentAt":"2015-06-23T20:10:01Z","receivedAt":"2015-06-23T20:10:01Z","isPatch":false,"sender":{"key":"randall.becker@nexbridge.ca","avatar":"https://avatars.githubusercontent.com/u/28956764?v=4"},"body":"> -----Original Message-----\n> From: git-owner@vger.kernel.org [mailto:git-owner@vger.kernel.org] On\n> Behalf Of David Turner\n> Sent: June 23, 2015 4:05 PM\n> To: Stefan Beller\n> Cc: git mailing list; ronnie sahlberg\n> Subject: Re: RFC/Pull Request: Refs db backend\n> \n> On Tue, 2015-06-23 at 10:16 -0700, Stefan Beller wrote:\n> > > The db backend code was added in the penultimate commit; the rest is\n> > > just code rearrangement and minor changes to make alternate backends\n> > > possible.  There ended up being a fair amount of this rearrangement,\n> > > but the end result is that almost the entire git test suite runs\n> > > under the db backend without error (see below for\n> > details).\n> >\n> > Looking at the end result in refs-be-db.c it feels like there are more\n> > functions in the refs_be_db struct, did this originate from other\n> > design choices? IIRC Ronnie wanted to have as least functions in there\n> > as possible, and share as much of the code between the databases, such\n> > that the glue between the db and the refs code is minimal.\n> \n> I didn't actually spend that much time reading Ronnie's backend code.\n> My code aims to be extremely thoroughly compatible.  I spent a ton of time\n> making sure that the git test suite passed.  I don't know if an alternate\n> approach would have been as compatible.\n> \n> The requirement for reflog storage did complicate things a bit.\n> \n> I also didn't see a strong need to abstract the database, since LMDB is common,\n> widely compatible, and tiny.\n\nJust to beg a request: LMDB is not available on some MPP architectures to which git has been ported. If it comes up, I beg you not to add this as a dependency to base git components.\n\nThanks,\nRandall\n\n-- Brief whoami: NonStop&UNIX developer since approximately UNIX(421664400)/NonStop(211288444200000000)\n-- In my real life, I talk too much.\n"},{"id":"264669","messageId":"1435090937.28466.68.camel@twopensource.com","threadId":"39699","inReplyTo":"005101d0adf0$964bca10$c2e35e30$@nexbridge.com","subject":"Re: RFC/Pull Request: Refs db backend","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-06-23T20:22:17Z","receivedAt":"2015-06-23T20:22:17Z","isPatch":false,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"> Just to beg a request: LMDB is not available on some MPP architectures to which git has been ported. If it comes up, I beg you not to add this as a dependency to base git components.\n\nMy changes make `configure` check for the presence of liblmdb. The LMDB\ncode is only built if liblmdb is present.  So, I think we're good.\n"},{"id":"264671","messageId":"005e01d0adf3$117eb880$347c2980$@nexbridge.com","threadId":"39699","inReplyTo":"1435090937.28466.68.camel@twopensource.com","subject":"RE: RFC/Pull Request: Refs db backend","fromName":"Randall S. Becker","fromEmail":"rsbecker@nexbridge.com","sentAt":"2015-06-23T20:27:46Z","receivedAt":"2015-06-23T20:27:46Z","isPatch":false,"sender":{"key":"randall.becker@nexbridge.ca","avatar":"https://avatars.githubusercontent.com/u/28956764?v=4"},"body":"> -----Original Message-----\n> From: git-owner@vger.kernel.org [mailto:git-owner@vger.kernel.org] On\n> Behalf Of David Turner\n> Sent: June 23, 2015 4:22 PM\n> To: Randall S. Becker\n> Cc: 'Stefan Beller'; 'git mailing list'; 'ronnie sahlberg'\n> Subject: Re: RFC/Pull Request: Refs db backend\n> \n> > Just to beg a request: LMDB is not available on some MPP architectures to\n> which git has been ported. If it comes up, I beg you not to add this as a\n> dependency to base git components.\n> \n> My changes make `configure` check for the presence of liblmdb. The LMDB\n> code is only built if liblmdb is present.  So, I think we're good.\n\nThanks :) You have no idea how much, in a \"burnt by that in other projects\" POV.\n\nCheers,\nRandall\n"},{"id":"264692","messageId":"5589CF56.2010309@alum.mit.edu","threadId":"39699","inReplyTo":"1435089205.28466.56.camel@twopensource.com","subject":"Re: RFC/Pull Request: Refs db backend","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2015-06-23T21:27:50Z","receivedAt":"2015-06-23T21:27:50Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 06/23/2015 09:53 PM, David Turner wrote:\n> On Tue, 2015-06-23 at 17:51 +0200, Michael Haggerty wrote:\n> [...]\n>> * I don't like the fact that you have replaced `struct ref_transaction\n>> *` with `void *` in the public interface. On a practical level, I like\n>> the bit of type-safety that comes with the more specific declaration.\n>> But on a more abstract level, I think that the concept of a transaction\n>> could be useful across backends, for example in utility functions that\n>> verify that a proposed set of updates are internally consistent. I would\n>> rather see either\n>>\n>>   * backends \"extend\" a basic `struct ref_transaction` to suit their\n>> needs, and upcast/downcast pointers at the module boundary, or\n>>\n>>   * `struct ref_transaction` itself gets a `void *` member that backends\n>> can use for whatever purposes they want.\n> \n> There are no common fields between refs-be-file transactions and\n> refs-be-lmdb transactions.  I don't see much gain from adding an empty\n> ref_transaction that backends could extend, since we would have to\n> explicitly upcast/downcast all over the place.\n\nIf you ask me, it would be better to do a bunch of up/downcasts within\nthe single module (via two helper functions that could even do\nconsistency checks) than have no help from the compiler in preventing\npeople from passing unrelated pointer types into the `void *transaction`\nargument. Plus the `struct ref_transaction *` variables scattered\nthroughout the code are a lot more self-explanatory than `void *`.\n\n>> * Regarding MERGE_HEAD: you take the point of view that it must continue\n>> to be stored as a file. And yet it must also behave somewhat like a\n>> reference; for example, `git rev-parse MERGE_HEAD` works today.\n>> MERGE_HEAD is also used for reachability, right?\n>>\n>> Another point of view is that MERGE_HEAD is a plain old boring\n>> reference, but there is some other metadata related to it that the refs\n>> backend has to store. The file-based backend would have special-case\n>> code to read the additional data from the tail of the loose refs file\n>> (and be sure to write the metadata when writing the reference), but\n>> other backends could store the reference with the rest but do their own\n>> thing with the metadata. So I guess I'm wondering whether the refs API\n>> needs a MERGE_HEAD-specific way to read and write MERGE_HEAD along with\n>> its metadata.\n> \n> You are probably right that this is a good idea.\n> \n>> * Don't the same considerations that apply to MERGE_HEAD also apply to\n>> FETCH_HEAD?\n> \n> All of the tests pass without any special handling of FETCH_HEAD.\n\nThat's odd. From git-fetch.txt:\n\n    The names of refs that are fetched, together with the object names\n    they point at, are written to `.git/FETCH_HEAD`.  This information\n    may be used by scripts or other git commands, such as\n    linkgit:git-pull[1].\n\nIt seems like the test suite is reading FETCH_HEAD via the refs API in a\ncouple of places. I don't understand why these don't fail when LMDB is\nbeing used...\n\n>> * I'm showing my ignorance of LMDB, but I don't see where the LMDB\n>> backend initializes its database during `git init-db`. Is that what\n>> `init_env()` does? But it looks like `init_env()` is called on every git\n>> invocation (via `git_config_early()`). Puzzled.\n> \n> There is no need to explicitly create the database (other than with\n> mkdir); init_env does everything for you.\n\nOK.\n\n>> * Rehash of the last two points: I expected one backend function that is\n>> used to initialize the refs backend when a new repository is created\n>> (e.g., in `git init`). The file-based backend would use this function to\n>> create the `refs`, `refs/heads`, and `refs/tags` directories. I expected\n>> a second function that is called once every time git runs in an existing\n>> repository (this one might, for example, open a database connection).\n>> And maybe even a third one that closes down the database connection\n>> before git exits. Would you please explain how this actually works?\n> \n> LMDB doesn't really have the concept of a \"connection\".  It's basically\n> just a couple of files that communicate using shared memory (and maybe\n> some other locking that I haven't paid attention to).  There is the\n> concept of a \"transaction\", which is the unit of concurrency (each\n> thread may only have one open transaction).  Transactions are either\n> read-only or read-write, and there can only be one read-write\n> transaction open at a time (across the entire system).  Read-only\n> transactions take a snapshot of the DB state at transaction start time.\n> This combination of features means that we need to be a bit clever about\n> read-only transactions; if a read-write transaction occurs in a separate\n> process, we need to restart any read-only transactions to pick up its\n> changes.\n\nIf you are thinking about an *unrelated* separate process, then Git's\nphilosophy is that if our process is reading *some* valid state of the\nreferences, it's all good even if that state is not quite the newest.\nAfter all, who's to say whether our process ran before or after the\nother process? As long as each process sees self-consistent views of the\nworld as it existed at some recent time, we're satisfied.\n\nTo be sure, we even fail at that unambitious goal, because loose\nreference reads are not atomic. It is possible that we read some\nreferences in the state they had before the other process ran, and\nothers in the state they had after the other process was finished. This\ncan get ugly if, for example, the other process renamed a reference,\nbecause we might not see the reference under either its old *or* its new\nname. We might therefore conclude that the objects reachable from that\nreference are dangling and garbage-collect them.\n\nIf the other process is one that we started ourselves, then that is a\ndifferent situation and we would want, for example, to invalidate our\nreference cache after the other process is done.\n\nOne of the long-standing hopes of a DB-backed reference backend would be\nto improve this situation--allowing atomic writes *and* reads.\n\n> [...]\n> \n>> * You explain in the docstring to `lmdb_transaction_begin_flags()` that\n>> it is dangerous to call a callback function while a write transaction is\n>> open if the callback function might want to initiate another write\n>> transaction. This would obviously also apply to running hooks.\n> \n> I carefully limit the scope of write transactions to avoid problems like\n> this.\n> \n>>  This is a\n>> limitation of LMDB because writers block each other. I can't think of\n>> anyplace that this would be a problem in our codebase. But if it were,\n>> it seems to me that you could take an approach like the file-based\n>> backend, which collects the transaction in a `ref_transaction` data\n>> structure, and executes the entire transaction within a single call to\n>> `ref_transaction_commit()`. This approach would prevent callers outside\n>> of the refs module from ever bumping against this limitation.\n> \n> The file-based backend does per-ref locking early, and then applies the\n> transactions. Here, taking the write transaction is how the lmdb backend\n> does locking.  So the situations are not quite the same.  But I think\n> keeping the scope of transactions small is the best plan.\n\nThe file-based backend locks the references early *within\nref_transaction_commit()*, not as the transaction is being built up\nusing ref_transaction_update() etc. This is a big difference, because\ncode anywhere can call\n\n    ref_transaction_begin(...);\n    ANYTHING\n    ref_transaction_update(...);\n    ANYTHING\n    ref_transaction_commit(...);\n\nThe only way to be sure that ANYTHING can't create a deadlock with the\nopen transaction (for example by calling a hook script that runs a git\ncommand) is to audit all of that code now and in the future. Whereas the\nfile-based backend doesn't do anything that is externally observable or\ndeadlocky except within the single ref_transaction_commit() function\ncall, so only that one function has to be audited for actions that could\ncause a deadlock.\n\n> [...]\n>> Let me know if you need any help rebasing your work onto my recent\n>> changes. It would probably work best if you break your patch series into\n>> smaller pieces to make them easier for the mailing list to digest. For\n>> example, the first installment could be the patches that make sense even\n>> independent of the plan to add support for multiple backends: the first\n>> two patches, plus the ones related to CHERRY_PICK_HEAD and its cousins,\n>> the abstraction of the reflog functions, and the `git reflog create` and\n>> `git reflog exists` subcommands.\n> \n> I would love some help rebasing. I'll break out the patches you suggest\n> and send them to the list, then create a new branch with the rest of the\n> changes.  Would that be a good place for you to start?\n\nThat sounds like a good next step, maybe after waiting a day or so to\nsee if there are any fundamental objections to what you have done so far.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\n"},{"id":"264694","messageId":"1435095301.28466.76.camel@twopensource.com","threadId":"39699","inReplyTo":"1435089205.28466.56.camel@twopensource.com","subject":"Re: RFC/Pull Request: Refs db backend","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-06-23T21:35:01Z","receivedAt":"2015-06-23T21:35:01Z","isPatch":false,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Tue, 2015-06-23 at 15:53 -0400, David Turner wrote:\n> > * Regarding MERGE_HEAD: you take the point of view that it must continue\n> > to be stored as a file. And yet it must also behave somewhat like a\n> > reference; for example, `git rev-parse MERGE_HEAD` works today.\n> > MERGE_HEAD is also used for reachability, right?\n> > \n> > Another point of view is that MERGE_HEAD is a plain old boring\n> > reference, but there is some other metadata related to it that the refs\n> > backend has to store. The file-based backend would have special-case\n> > code to read the additional data from the tail of the loose refs file\n> > (and be sure to write the metadata when writing the reference), but\n> > other backends could store the reference with the rest but do their own\n> > thing with the metadata. So I guess I'm wondering whether the refs API\n> > needs a MERGE_HEAD-specific way to read and write MERGE_HEAD along with\n> > its metadata.\n> \n> You are probably right that this is a good idea.\n\nOn reflection, I think it might make sense to keep MERGE_HEAD as a file.\nThe problem is that not only would refs backends have to add new\nMERGE_HEAD-handling functions, but we would also need new plumbing\ncommands to allow scripts to access the complete contents of MERGE_HEAD.\nThat seems more complicated to me.  \n"},{"id":"264695","messageId":"xmqqwpyuayrv.fsf@gitster.dls.corp.google.com","threadId":"39699","inReplyTo":"1435095301.28466.76.camel@twopensource.com","subject":"Re: RFC/Pull Request: Refs db backend","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-06-23T21:41:08Z","receivedAt":"2015-06-23T21:41:08Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Turner <dturner@twopensource.com> writes:\n\n> On Tue, 2015-06-23 at 15:53 -0400, David Turner wrote:\n>> > * Regarding MERGE_HEAD: you take the point of view that it must continue\n>> > to be stored as a file. And yet it must also behave somewhat like a\n>> > reference; for example, `git rev-parse MERGE_HEAD` works today.\n>> > MERGE_HEAD is also used for reachability, right?\n>> > \n>> > Another point of view is that MERGE_HEAD is a plain old boring\n>> > reference, but there is some other metadata related to it that the refs\n>> > backend has to store. The file-based backend would have special-case\n>> > code to read the additional data from the tail of the loose refs file\n>> > (and be sure to write the metadata when writing the reference), but\n>> > other backends could store the reference with the rest but do their own\n>> > thing with the metadata. So I guess I'm wondering whether the refs API\n>> > needs a MERGE_HEAD-specific way to read and write MERGE_HEAD along with\n>> > its metadata.\n>> \n>> You are probably right that this is a good idea.\n>\n> On reflection, I think it might make sense to keep MERGE_HEAD as a file.\n> The problem is that not only would refs backends have to add new\n> MERGE_HEAD-handling functions, but we would also need new plumbing\n> commands to allow scripts to access the complete contents of MERGE_HEAD.\n> That seems more complicated to me.  \n\nI think you are talking about FETCH_HEAD, but I tend to agree.\n"},{"id":"264705","messageId":"CAJo=hJsu2b0kmpjOhGwvgRsG3yGK56+U_2RANDi2qoEg7V_PmQ@mail.gmail.com","threadId":"39699","inReplyTo":"20150623114716.GC12518@peff.net","subject":"Re: RFC/Pull Request: Refs db backend","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2015-06-24T06:09:40Z","receivedAt":"2015-06-24T06:09:40Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Tue, Jun 23, 2015 at 4:47 AM, Jeff King <peff@peff.net> wrote:\n>\n> One of the problems we've had with large-ref repos is that the reflog\n> storage is quite inefficient.\n\nYup. We ran into this with Gerrit Code Review years ago. The\nrefs/changes/... namespace created by Gerrit Code Review is 1 ref per\nsnapshot per code review, and never modified. Reflogs for these are\nalways exactly one record. We broke down and modified JGit to add an\nAPI that allowed Gerrit Code Review to disable recording reflogs for\nspecific updates just to avoid creating reflogs under refs/changes/.\n\nIn our JGit DFS implementation we store reflogs in databases to\neliminate these overheads. It works well for us. Hopefully the feature\ncan come to git-core through this series.\n\n> It has also been a dream of mine to stop tying the reflogs specifically\n> to the refs. I.e., have a spot for reflogs of branches that no longer\n> exist, which allows us to retain them for deleted branches. Then you can\n> possibly recover from a branch deletion, whereas now you have to dig\n> through \"git fsck\"'s dangling output. And the reflog, if you don't\n> expire it, becomes a suitable audit log to find out what happened to\n> each branch when (whereas now it is full of holes when things get\n> deleted).\n\nYes. $DAY_JOB's DFS implementation never expires reflogs, allowing it\nto be used as a history to inspect what happened. Its been useful a\ncouple of times to investigate and recover from a few accidental\ndeletions.\n\nOnce you never expire reflog records you now have to consider at what\npoint do you stop paying attention to the reflog entries for graph\nreachability during repack and fsck. Users still expect to be able to\nforce push or delete a branch and have a set of objects disappear from\nthe repository.\n\nI am looking forward to something like this in git-core. I delete\nbranches in my local repos and then regret that. Then remember HEAD\nhas a reflog and hope I can find it somewhere in there. Usually I\nfail, and am sad. :(\n\n> I was thinking of actually moving to a log-structured ref storage.\n> Something like:\n>\n>   - any ref write puts a line at the end of a single logfile that\n>     contains the ref name, along with the normal reflog data\n>\n>   - the logfile is the source of truth for the ref state. If you want to\n>     know the value of any ref, you can read it backwards to find the\n>     last entry for the ref. Everything else is an optimization.\n>\n>     Let's call the number of refs N, and the number of ref updates in\n>     the log U.\n>\n>   - we keep a key/value index mapping the name of any branch that exists\n>     to the byte offset of its entry in the logfile. This would probably\n>     be in some binary key/value store (like LMDB). Without this,\n>     resolving a ref is O(U), which is horrible. With it, it should be\n>     O(1) or O(lg N), depending on the index data structure.\n\nThis ... would be fantastic.\n\nThere are some issues with append. Before appending we would need to\nverify the last record actually ends with an LF. If there was a power\nfailure and only part of the last record wrote, you can't append\nwithout that record separator in place.\n\nIf that last record was truncated, and an LF was wedged in to do a new\nappend, we can't trust that intermediate record. A CRC at the end of\nthe record might make it safer to know the record is intact or bogus\ndue to an earlier failed write that wasn't completed.\n\nWhat about the case of never expiring the reflog? This log would grow\nforever. You may eventually need to archive old sections of it (e.g. 1\nyear ago?) to maintain an audit log, while keeping the \"latest\" entry\nfor each ref to rebuild the index.\n\n>   - the index can also contain other optimizations. E.g., rather than\n>     point to the entry in the logfile, it can include the sha1 directly\n>     (to avoid an extra level of indirection). It may want to include the\n>     \"peeled\" value, as the current packed-refs file does.\n\n+1 to always storing the peeled value. This was a major improvement\nfor $DAY_JOB's Git servers as peeling tags on the fly can be costly\nwhen your storage is something remote, such as NFS. Unfortunately the\ncurrent wire protocol demands peeled information to serve a ref\nadvertisement.\n\nOne thing we do is always peel all refs. We record a bit to state its\nbeen peeled, but there is no peeled value because the ref is pointing\nto a non-tag object (e.g. refs/heads/master points to a commit).\n\nI guess this puts an index structure at something like:\n\n  refname \\0 log_idx_4 sha1_20 ('n' | 'p' sha1_20)\n\nOr refname + 26 bytes for heads and refname + 46 bytes for tags.\n\n\nUpdating the index on updates to a ref would be costly, as its O(N).\nYou could skip some index updates. Record in the header of the index\nthe length of the reflog file used to build it. When reading the\nindex, scan the reflog from that position to the end and patch those\nupdates in memory. Rewrites of the index could then be deferred until\nthe scan delta on the log is high, or the next gc.\n\n>   - Reading all of the reflogs (e.g., for repacking) is O(U), just like\n>     it is today. Except the storage for the logfile is a lot more\n>     compact than what we store today, with one reflog per file.\n>\n>   - Reading a single reflog is _also_ O(U), which is not as good as\n>     today. But if each log entry contains a byte offset of the previous\n>     entry, you can follow the chain (it is still slightly worse, because\n>     you are jumping all over the file, rather than reading a compact set\n>     of lines).\n\nBut this is like saying reading `git log` is bad because we jump all\nover the pack file to parse ancestors and insert them into the\nrevqueue at the correct position. Feh.\n\nI think given the typical size of reflogs, this is irrelevant.\n\n>   - Pruning the reflog entries from the logfile requires rewriting the\n>     whole thing. That's similar to today, where we rewrite each of the\n>     reflog files.\n>\n> One of the nice properties of this system is that it should be very\n> resilient to corruption and races. Most of the operations are either\n> appending to a file, or writing to a tempfile and renaming in place.\n> The exception is the key/value index, but if we run into any problems\n> there, it can be rebuilt by walking over the logfile (for a cost of\n> O(U)).\n>\n> I dunno. Maybe I am overthinking it.\n\nNot really. Your idea is quite simple. I like it.\n\n> But it really feels like the _refs_\n> are a key/value thing, but the _reflogs_ are not. You can cram them into\n> a key/value store, but you're probably operating on them as a big blob,\n> then.\n\n+1. Refs are key/value but you need all of the key/value pairs fast\nfor the current wire protocol.\n\nReflogs are a long queue that is more or less just table scanned when\nits accessed.\n\n>> I chose to use LMDB for the database.  LMDB has a few features that make\n>> it suitable for usage in git:\n>\n> One of the complaints that Shawn had about sqlite is that there is no\n> native Java implementation, which makes it hard for JGit to ship a\n> compatible backend. I suspect the same is true for LMDB, but it is\n> probably a lot simpler than sqlite (so reimplementation might be\n> possible).\n\nYes. Whatever the default standard format is for git-core, we need\nthat format to be easily supportable from JGit. Loading code via JNI\nis not \"easily supportable\".\n\nNon-default formats that the user can opt-into (and opt-out of) don't\nneed JGit compatibility. Users can choose to use $FANCY_DB or JGit and\nmake the tradeoff that is best for them. If JGit is also able to do\n$FANCY_DB, great. If not, that's fine too. Not everyone needs JGit.\nNot everyone needs $FANCY_DB.\n\nIIRC some part of Ronnie's series was about setting up a socket\nprotocol between Git and the ref backend. If non-default backends are\nlike this, JGit could spawn the backend binary and then speak the\nsocket protocol just like git-core. This would be preferable to\nlinking JNI into the JVM.\n\nThink remote helper protocol between transport.c and the helpers. JGit\ndoesn't yet speak that, but it should, and there is no technical\nreason why it can't. Same for a ref helper protocol.\n"},{"id":"264713","messageId":"20150624085141.GA5436@peff.net","threadId":"39699","inReplyTo":"CACsJy8B=jthxn_E-zWnDfua29FGGgz221N-cLw=NxeVOKadUxA@mail.gmail.com","subject":"Re: RFC/Pull Request: Refs db backend","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-06-24T08:51:41Z","receivedAt":"2015-06-24T08:51:41Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jun 23, 2015 at 08:10:03PM +0700, Duy Nguyen wrote:\n\n> >   - we keep a key/value index mapping the name of any branch that exists\n> >     to the byte offset of its entry in the logfile. This would probably\n> \n> One key/value mapping per branch, pointing to the latest reflog entry,\n> or one key/valye mapping for each reflog entry?\n\nYeah, sorry, I meant to point only to the latest entry (and then from\nthere if you want to actually walk the reflog, you can do so by\nfollowing the backreference to the previous entry).\n\n> >     be in some binary key/value store (like LMDB). Without this,\n> >     resolving a ref is O(U), which is horrible. With it, it should be\n> >     O(1) or O(lg N), depending on the index data structure.\n> \n> I'm thinking of the user with small or medium repos, in terms of refs,\n> who does not want an extra dependency. If we store one mapping per\n> branch, then the size of this mapping is small enough that the index\n> in a text file is ok. If we also store the offset to the previous\n> reflog entry of the same branch in the current reflog entry, like a\n> back pointer, then we could jump back faster.\n> \n> Or do you have something else in mind? Current reflog structure won't\n> work because I think you bring back the reflog graveyard with this,\n> and I don't want to lose that\n\nI hadn't really thought about having multiple formats for the index. But\nin theory, yes, you could, and the lowest common denominator could just\nuse the filesystem. Or even something similar to the packed-refs file,\nwhere we have to write the whole thing to make a single update. That\ndoesn't perform well, but it's dirt simple and might be OK if you have\nonly a handful of refs.\n\n-Peff\n"},{"id":"264714","messageId":"20150624091417.GB5436@peff.net","threadId":"39699","inReplyTo":"1435083516.28466.24.camel@twopensource.com","subject":"Re: RFC/Pull Request: Refs db backend","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-06-24T09:14:17Z","receivedAt":"2015-06-24T09:14:17Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jun 23, 2015 at 02:18:36PM -0400, David Turner wrote:\n\n> > Can you describe a bit more about the reflog handling?\n> > \n> > One of the problems we've had with large-ref repos is that the reflog\n> > storage is quite inefficient. You can pack all the refs, but you may\n> > still be stuck with a bunch of reflog files with one entry, wasting a\n> > whole inode. Doing a \"git repack\" when you have a million of those has\n> > horrible cold-cache performance. Basically anything that isn't\n> > one-file-per-reflog would be a welcome change. :)\n> \n> Reflogs are stored in the database as well.  There is one header entry\n> per ref to indicate that a reflog is present, and then one database\n> entry per reflog entry; the entries are stored consecutively and\n> immediately following the header so that it's fast to iterate over them.\n\nOK, that make sense. I did notice that the storage for the refdb grows\nrapidly. If I add a millions refs (like refs/tags/$i) with a simple\nreflog message \"foo\", I ended up with a 500MB database file.\n\nThat's _probably_ OK, because a million is getting into crazy\nterritory[1].  But it's 500 bytes per ref, each with one reflog entry.\nOur ideal lower bound is probably something like 100 bytes per reflog\nentry:\n\n  - 20 bytes for old sha1\n  - 20 bytes for new sha1\n  - ~50 bytes for name, email, timestamp\n  - ~6 bytes for refname (1000000 is the longest unique part)\n\nThat assumes we store binary[2] (and not just the raw reflog lines), and\nreconstruct the reflog lines on the fly. It also assumes we use some\nkind of trie-like storage (where we can amortize the cost of storing\n\"refs/tags/\" across all of the entries).\n\nOf course that neglects lmdb's overhead, and the storage of the ref tip\nitself. But it would hopefully give us a ballpark for an optimal\nsolution. We don't have to hit that, of course, but it's food for\nthought.\n\n[1] The homebrew/homebrew repository on GitHub has almost half a million\n    ref updates. Since this is storing not just refs but all ref\n    updates, that's actually the interesting number (and optimizing the\n    per-reflog-entry size is more interesting than the per-ref size).\n\n[2] I'm hesitant to suggest binary formats in general, but given that\n    this is a blob embedded inside lmdb, I think it's OK. If we were to\n    pursue the log-structured idea I suggested earlier, I'm torn on\n    whether it should be binary or not.\n\n> > It has also been a dream of mine to stop tying the reflogs specifically\n> > to the refs. I.e., have a spot for reflogs of branches that no longer\n> > exist, which allows us to retain them for deleted branches.\n> [...]\n> That would be cool, and I don't think it would be hard to add to my\n> current code; we could simply replace the header with a \"tombstone\".\n> But I would prefer to wait until the series is merged; then we can build\n> on top of it.\n\nYeah, I think you can add it easily to basically any system that does\nnot have the filesystem D/F conflicts in its storage (i.e., having\n\"refs/foo\" does not block data under \"refs/foo/bar\").\n\n> > But it may also be worth going with a slightly slower database if we can\n> > get wider compatibility for free.\n> \n> There's a JNI interface to LMDB, which is, of course, not native.  I\n> don't think it would be too hard to entirely rewrite LMDB in Java, but\n> I'm not going to have time to do it for the forseeable future.  I've\n> asked Howard Chu if he knows of any efforts in progress.\n\nYeah, I think JNI is not enough for Eclipse folks. I don't think this is\na task that you would necessarily need to take on. More just something\nto think about for the future when picking a format.\n\n> Thanks, that's valuable.  For the refs backend, opening the LMDB\n> database for writing is sufficient to block other writers.  Do you think\n> it would be valuable to provide a git hold-ref-lock command that simply\n> reads refs from stdin and keeps them locked until it reads EOF from\n> stdin?  That would allow cross-backend ref locking.\n\nI'm not sure what you would use it for. If you want to update the refs,\nthen you can specify a whole transaction with \"git update-ref --stdin\",\nand that should work whatever backend you choose. Is there some other\noperation you want where you hold the lock for a longer period of time?\n\n-Peff\n"},{"id":"264715","messageId":"20150624094919.GC5436@peff.net","threadId":"39699","inReplyTo":"CAJo=hJsu2b0kmpjOhGwvgRsG3yGK56+U_2RANDi2qoEg7V_PmQ@mail.gmail.com","subject":"Re: RFC/Pull Request: Refs db backend","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-06-24T09:49:20Z","receivedAt":"2015-06-24T09:49:20Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jun 23, 2015 at 11:09:40PM -0700, Shawn Pearce wrote:\n\n> Yes. $DAY_JOB's DFS implementation never expires reflogs, allowing it\n> to be used as a history to inspect what happened. Its been useful a\n> couple of times to investigate and recover from a few accidental\n> deletions.\n> \n> Once you never expire reflog records you now have to consider at what\n> point do you stop paying attention to the reflog entries for graph\n> reachability during repack and fsck. Users still expect to be able to\n> force push or delete a branch and have a set of objects disappear from\n> the repository.\n\nYeah, we face this problem at GitHub. We actually write every single ref\nwrite to $GIT_DIR/audit_log, which is essentially a reflog with the\nrefname prepended. The key, though, is that it isn't ever _read_ by git\nfor reachability. So it becomes an immutable log of what happened, and\nwe can happily prune the reflog to drop objects.\n\nIn a log-structured ref storage world, I think I'd include a single bit\nper entry for \"use this for reachability\". Then you could \"soft-expire\"\nreflog entries by dropping their reachability bit, but still retain them\nin your audit_log. The alternative is to just copy the entries to an\narchival log.\n\n> There are some issues with append. Before appending we would need to\n> verify the last record actually ends with an LF. If there was a power\n> failure and only part of the last record wrote, you can't append\n> without that record separator in place.\n\nYeah, I think that is straightforward. You have to take a lock on the\nwhole log anyway, so it's OK to \"fixup\" the previous entry.\n\n> If that last record was truncated, and an LF was wedged in to do a new\n> append, we can't trust that intermediate record. A CRC at the end of\n> the record might make it safer to know the record is intact or bogus\n> due to an earlier failed write that wasn't completed.\n\nI suspect you could get by with just realizing that the entry doesn't\nparse (that's what we do now for reflogs). But the idea of per-entry\nconsistency checks is appealing. You could also include the CRC for the\n\"previous\" entry (remember that we would probably have a back-pointer to\nsome byte offset to say \"this is the current ref state that I am\nbuilding on\"). Then you can walk back the whole chain to know that it\nhasn't been damaged.\n\nIf you want to get very fancy, replace your CRC with a cryptographically\nstrong hash, and you've just reinvented a blockchain. :)\n\n> What about the case of never expiring the reflog? This log would grow\n> forever. You may eventually need to archive old sections of it (e.g. 1\n> year ago?) to maintain an audit log, while keeping the \"latest\" entry\n> for each ref to rebuild the index.\n\nYeah, that's certainly an option. I'd say that's somewhat outside the\nscope of git. If git provides the ability to prune entries completely\n(i.e., what \"reflog expire\" does now) and to soft-expire them, then that\nis enough for anyone to build whatever sort of archival system they want\n(e.g., soft-expire for reachability as desired, and then occasionally\n\"git reflog show >your-archive && git reflog expire\").\n\n> +1 to always storing the peeled value. This was a major improvement\n> for $DAY_JOB's Git servers as peeling tags on the fly can be costly\n> when your storage is something remote, such as NFS. Unfortunately the\n> current wire protocol demands peeled information to serve a ref\n> advertisement.\n\nEven on good disks, it makes the initial ref advertisement from\ngit-upload-pack _way_ cheaper, because we don't have to actually touch\nthe object database at all. It's basically just blitting out the\npacked-refs file.\n\n> One thing we do is always peel all refs. We record a bit to state its\n> been peeled, but there is no peeled value because the ref is pointing\n> to a non-tag object (e.g. refs/heads/master points to a commit).\n\nYeah, since c29c46f (pack-refs: add fully-peeled trait, 2013-03-18) we\nimplicitly do this in packed-refs; if there's no peel line after the\nentry, it cannot be peeled. We could do the same here, but I think I\nfavor being more implicit (I'd probably add a few bits of \"flags\" to\neach entry, and this could be one such flag).\n\n> Updating the index on updates to a ref would be costly, as its O(N).\n\nIt depends how you implement the index. A straight text index would be\nO(N). Replacing the index with a real key/value store should be very\nfast. But unless we are going to write our own, that's going to\nintroduce a dependency (possibly one we can ship as we do with xdiff,\nbut the whole JGit thing is an open question).\n\n> You could skip some index updates. Record in the header of the index\n> the length of the reflog file used to build it. When reading the\n> index, scan the reflog from that position to the end and patch those\n> updates in memory. Rewrites of the index could then be deferred until\n> the scan delta on the log is high, or the next gc.\n\nYeah, basically use the log as a journal. You save (or at least\namortize) O(# of refs) work for the writers, at the cost of O(# of\nrecent updates) work for the readers. That might be worth doing. It's\nalso complicated, and I was hoping to avoid complicated things. :)\n\n> >   - Reading a single reflog is _also_ O(U), which is not as good as\n> >     today. But if each log entry contains a byte offset of the previous\n> >     entry, you can follow the chain (it is still slightly worse, because\n> >     you are jumping all over the file, rather than reading a compact set\n> >     of lines).\n> \n> But this is like saying reading `git log` is bad because we jump all\n> over the pack file to parse ancestors and insert them into the\n> revqueue at the correct position. Feh.\n\nYeah, I agree it's probably not worth caring too much about. Reading the\nreflogs at all is not that common an operation, and it's a tradeoff I'd\nbe happy to make. I was just trying to be upfront about the tradeoffs\nversus the current storage format.\n\n> IIRC some part of Ronnie's series was about setting up a socket\n> protocol between Git and the ref backend. If non-default backends are\n> like this, JGit could spawn the backend binary and then speak the\n> socket protocol just like git-core. This would be preferable to\n> linking JNI into the JVM.\n\nI am not excited about contacting an already-running program, which is\nwhat I thought Ronnie's patches did. That's one more thing to go wrong\nor become confusing doing basic operations.  If we have to do an\nexternal program, I'd much rather it be something we spawn once (more\nlike the remote-helper, which I think is what you are proposing).\n\nI don't know how much that helps for the JGit situation. It punts the\nnative code out of JGit, but people using JGit still have to have the\nnative helper from git on their system.  I have no problems at all with\npluggable $FANCY_DB that not everybody supports.  But I think we would\nwant _some_ baseline that is reasonably performant, and that everybody\nwill support. I'm not sure putting the index into a flat file is\nperformant enough. Is there any basic key/value store that is has both a\nC and a pure-Java version (e.g., berkeley db)?\n\n-Peff\n"},{"id":"264717","messageId":"CACsJy8CZqpAARwYpj6g7fR-qiKcV6UeWZaei5Yqh-0oSV8DW6Q@mail.gmail.com","threadId":"39699","inReplyTo":"CAJo=hJsu2b0kmpjOhGwvgRsG3yGK56+U_2RANDi2qoEg7V_PmQ@mail.gmail.com","subject":"Re: RFC/Pull Request: Refs db backend","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2015-06-24T10:18:34Z","receivedAt":"2015-06-24T10:18:34Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Jun 24, 2015 at 1:09 PM, Shawn Pearce <spearce@spearce.org> wrote:\n>>> I chose to use LMDB for the database.  LMDB has a few features that make\n>>> it suitable for usage in git:\n>>\n>> One of the complaints that Shawn had about sqlite is that there is no\n>> native Java implementation, which makes it hard for JGit to ship a\n>> compatible backend. I suspect the same is true for LMDB, but it is\n>> probably a lot simpler than sqlite (so reimplementation might be\n>> possible).\n>\n> Yes. Whatever the default standard format is for git-core, we need\n> that format to be easily supportable from JGit. Loading code via JNI\n> is not \"easily supportable\".\n\nI'm under the impression that this will be opt-in, not completely\nreplacing fs-based ref backend. Anyway, any recommendation about\ndatabase format or engine that is more friendly to Java and JGit (and\npreferably has good C support too)?\n-- \nDuy\n"},{"id":"264742","messageId":"1435166999.26709.12.camel@twopensource.com","threadId":"39699","inReplyTo":"20150624091417.GB5436@peff.net","subject":"Re: RFC/Pull Request: Refs db backend","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-06-24T17:29:59Z","receivedAt":"2015-06-24T17:29:59Z","isPatch":false,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Wed, 2015-06-24 at 05:14 -0400, Jeff King wrote:\n> On Tue, Jun 23, 2015 at 02:18:36PM -0400, David Turner wrote:\n> \n> > > Can you describe a bit more about the reflog handling?\n> > > \n> > > One of the problems we've had with large-ref repos is that the reflog\n> > > storage is quite inefficient. You can pack all the refs, but you may\n> > > still be stuck with a bunch of reflog files with one entry, wasting a\n> > > whole inode. Doing a \"git repack\" when you have a million of those has\n> > > horrible cold-cache performance. Basically anything that isn't\n> > > one-file-per-reflog would be a welcome change. :)\n> > \n> > Reflogs are stored in the database as well.  There is one header entry\n> > per ref to indicate that a reflog is present, and then one database\n> > entry per reflog entry; the entries are stored consecutively and\n> > immediately following the header so that it's fast to iterate over them.\n> \n> OK, that make sense. I did notice that the storage for the refdb grows\n> rapidly. If I add a millions refs (like refs/tags/$i) with a simple\n> reflog message \"foo\", I ended up with a 500MB database file.\n> \n> That's _probably_ OK, because a million is getting into crazy\n> territory[1].  But it's 500 bytes per ref, each with one reflog entry.\n> Our ideal lower bound is probably something like 100 bytes per reflog\n> entry:\n> \n>   - 20 bytes for old sha1\n>   - 20 bytes for new sha1\n>   - ~50 bytes for name, email, timestamp\n>   - ~6 bytes for refname (1000000 is the longest unique part)\n> \n> That assumes we store binary[2] (and not just the raw reflog lines), and\n> reconstruct the reflog lines on the fly. It also assumes we use some\n> kind of trie-like storage (where we can amortize the cost of storing\n> \"refs/tags/\" across all of the entries).\n> \n> Of course that neglects lmdb's overhead, and the storage of the ref tip\n> itself. But it would hopefully give us a ballpark for an optimal\n> solution. We don't have to hit that, of course, but it's food for\n> thought.\n> \n> [1] The homebrew/homebrew repository on GitHub has almost half a million\n>     ref updates. Since this is storing not just refs but all ref\n>     updates, that's actually the interesting number (and optimizing the\n>     per-reflog-entry size is more interesting than the per-ref size).\n> \n> [2] I'm hesitant to suggest binary formats in general, but given that\n>     this is a blob embedded inside lmdb, I think it's OK. If we were to\n>     pursue the log-structured idea I suggested earlier, I'm torn on\n>     whether it should be binary or not.\n\nI could try a binary format.  I was optimizing for simplicity,\ndebuggability, recoverability, compatibility with the choice of the text\nformat, but I wouldn't have to.  I don't know how much this will save.\nUnfortunately, given the way LMDB works, a trie-like storage to save\nrefs/tags does not seem possible (of course, we could hard-code some\nhacks like \\001=refs/rags, \\002=refs/heads, etc but that is a\nmicro-optimization that might not be worth it.\n\nAlso, the reflog header has some overhead (it's an entire extra record\nper ref). The header exists to implement reflog creation/existence\nchecking.  I didn't really try to understand why we have the distinction\nbetween empty and nonexistent reflogs; I just copied it.  If we didn't\nhave that distinction, we could eliminate that overhead.\n\n> > Thanks, that's valuable.  For the refs backend, opening the LMDB\n> > database for writing is sufficient to block other writers.  Do you think\n> > it would be valuable to provide a git hold-ref-lock command that simply\n> > reads refs from stdin and keeps them locked until it reads EOF from\n> > stdin?  That would allow cross-backend ref locking.\n> \n> I'm not sure what you would use it for. If you want to update the refs,\n> then you can specify a whole transaction with \"git update-ref --stdin\",\n> and that should work whatever backend you choose. Is there some other\n> operation you want where you hold the lock for a longer period of time?\n\nI'm sure I had a reason for this at the time I wrote it, but now I can't\nthink of what it was.  Nevermind!\n"},{"id":"264743","messageId":"1435167089.26709.14.camel@twopensource.com","threadId":"39699","inReplyTo":"5589CF56.2010309@alum.mit.edu","subject":"Re: RFC/Pull Request: Refs db backend","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-06-24T17:31:29Z","receivedAt":"2015-06-24T17:31:29Z","isPatch":false,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Tue, 2015-06-23 at 23:27 +0200, Michael Haggerty wrote:\n> On 06/23/2015 09:53 PM, David Turner wrote:\n> > On Tue, 2015-06-23 at 17:51 +0200, Michael Haggerty wrote:\n> > [...]\n> >> * I don't like the fact that you have replaced `struct ref_transaction\n> >> *` with `void *` in the public interface. On a practical level, I like\n> >> the bit of type-safety that comes with the more specific declaration.\n> >> But on a more abstract level, I think that the concept of a transaction\n> >> could be useful across backends, for example in utility functions that\n> >> verify that a proposed set of updates are internally consistent. I would\n> >> rather see either\n> >>\n> >>   * backends \"extend\" a basic `struct ref_transaction` to suit their\n> >> needs, and upcast/downcast pointers at the module boundary, or\n> >>\n> >>   * `struct ref_transaction` itself gets a `void *` member that backends\n> >> can use for whatever purposes they want.\n> > \n> > There are no common fields between refs-be-file transactions and\n> > refs-be-lmdb transactions.  I don't see much gain from adding an empty\n> > ref_transaction that backends could extend, since we would have to\n> > explicitly upcast/downcast all over the place.\n> \n> If you ask me, it would be better to do a bunch of up/downcasts within\n> the single module (via two helper functions that could even do\n> consistency checks) than have no help from the compiler in preventing\n> people from passing unrelated pointer types into the `void *transaction`\n> argument. Plus the `struct ref_transaction *` variables scattered\n> throughout the code are a lot more self-explanatory than `void *`.\n\nI'll take a look at what that would look like.\n\n> >> * Regarding MERGE_HEAD: you take the point of view that it must continue\n> >> to be stored as a file. And yet it must also behave somewhat like a\n> >> reference; for example, `git rev-parse MERGE_HEAD` works today.\n> >> MERGE_HEAD is also used for reachability, right?\n> >>\n> >> Another point of view is that MERGE_HEAD is a plain old boring\n> >> reference, but there is some other metadata related to it that the refs\n> >> backend has to store. The file-based backend would have special-case\n> >> code to read the additional data from the tail of the loose refs file\n> >> (and be sure to write the metadata when writing the reference), but\n> >> other backends could store the reference with the rest but do their own\n> >> thing with the metadata. So I guess I'm wondering whether the refs API\n> >> needs a MERGE_HEAD-specific way to read and write MERGE_HEAD along with\n> >> its metadata.\n> > \n> > You are probably right that this is a good idea.\n> > \n> >> * Don't the same considerations that apply to MERGE_HEAD also apply to\n> >> FETCH_HEAD?\n> > \n> > All of the tests pass without any special handling of FETCH_HEAD.\n> \n> That's odd. From git-fetch.txt:\n> \n>     The names of refs that are fetched, together with the object names\n>     they point at, are written to `.git/FETCH_HEAD`.  This information\n>     may be used by scripts or other git commands, such as\n>     linkgit:git-pull[1].\n> \n> It seems like the test suite is reading FETCH_HEAD via the refs API in a\n> couple of places. I don't understand why these don't fail when LMDB is\n> being used...\n\nYou are right; I did add some special-case code for FETCH_HEAD.\n\n> >> * Rehash of the last two points: I expected one backend function that is\n> >> used to initialize the refs backend when a new repository is created\n> >> (e.g., in `git init`). The file-based backend would use this function to\n> >> create the `refs`, `refs/heads`, and `refs/tags` directories. I expected\n> >> a second function that is called once every time git runs in an existing\n> >> repository (this one might, for example, open a database connection).\n> >> And maybe even a third one that closes down the database connection\n> >> before git exits. Would you please explain how this actually works?\n> > \n> > LMDB doesn't really have the concept of a \"connection\".  It's basically\n> > just a couple of files that communicate using shared memory (and maybe\n> > some other locking that I haven't paid attention to).  There is the\n> > concept of a \"transaction\", which is the unit of concurrency (each\n> > thread may only have one open transaction).  Transactions are either\n> > read-only or read-write, and there can only be one read-write\n> > transaction open at a time (across the entire system).  Read-only\n> > transactions take a snapshot of the DB state at transaction start time.\n> > This combination of features means that we need to be a bit clever about\n> > read-only transactions; if a read-write transaction occurs in a separate\n> > process, we need to restart any read-only transactions to pick up its\n> > changes.\n> \n> If you are thinking about an *unrelated* separate process, then Git's\n> philosophy is that if our process is reading *some* valid state of the\n> references, it's all good even if that state is not quite the newest.\n> After all, who's to say whether our process ran before or after the\n> other process? As long as each process sees self-consistent views of the\n> world as it existed at some recent time, we're satisfied.\n\nNo, I'm thinking about a subprocess that we stared ourself here.\nUnrelated separate processes are fine, I think.\n\n> To be sure, we even fail at that unambitious goal, because loose\n> reference reads are not atomic. It is possible that we read some\n> references in the state they had before the other process ran, and\n> others in the state they had after the other process was finished. This\n> can get ugly if, for example, the other process renamed a reference,\n> because we might not see the reference under either its old *or* its new\n> name. We might therefore conclude that the objects reachable from that\n> reference are dangling and garbage-collect them.\n> \n> If the other process is one that we started ourselves, then that is a\n> different situation and we would want, for example, to invalidate our\n> reference cache after the other process is done.\n\nYep, my code does this.\n\n> One of the long-standing hopes of a DB-backed reference backend would be\n> to improve this situation--allowing atomic writes *and* reads.\n\nReads are atomic across renames, since we do renames within a single\nwrite transaction. \n\n> > [...]\n> > \n> >> * You explain in the docstring to `lmdb_transaction_begin_flags()` that\n> >> it is dangerous to call a callback function while a write transaction is\n> >> open if the callback function might want to initiate another write\n> >> transaction. This would obviously also apply to running hooks.\n> > \n> > I carefully limit the scope of write transactions to avoid problems like\n> > this.\n> > \n> >>  This is a\n> >> limitation of LMDB because writers block each other. I can't think of\n> >> anyplace that this would be a problem in our codebase. But if it were,\n> >> it seems to me that you could take an approach like the file-based\n> >> backend, which collects the transaction in a `ref_transaction` data\n> >> structure, and executes the entire transaction within a single call to\n> >> `ref_transaction_commit()`. This approach would prevent callers outside\n> >> of the refs module from ever bumping against this limitation.\n> > \n> > The file-based backend does per-ref locking early, and then applies the\n> > transactions. Here, taking the write transaction is how the lmdb backend\n> > does locking.  So the situations are not quite the same.  But I think\n> > keeping the scope of transactions small is the best plan.\n> \n> The file-based backend locks the references early *within\n> ref_transaction_commit()*, not as the transaction is being built up\n> using ref_transaction_update() etc. This is a big difference, because\n> code anywhere can call\n> \n>     ref_transaction_begin(...);\n>     ANYTHING\n>     ref_transaction_update(...);\n>     ANYTHING\n>     ref_transaction_commit(...);\n> \n> The only way to be sure that ANYTHING can't create a deadlock with the\n> open transaction (for example by calling a hook script that runs a git\n> command) is to audit all of that code now and in the future. Whereas the\n> file-based backend doesn't do anything that is externally observable or\n> deadlocky except within the single ref_transaction_commit() function\n> call, so only that one function has to be audited for actions that could\n> cause a deadlock.\n\nA deadlock is impossible; a second writer will simply be unable to\nacquire the lock and will die (same as in the file-based backend if two\nwriters try to update the same ref at the same time).\n\nIt's true that the scope for this is potentially larger.  On the other\nhand, the file-based backend might fail in the same cases -- it would\nfail when trying to verify refs that had changed out from under it. The \nfailure is less likely, since it would only happen on conflicting refs.\n"},{"id":"264804","messageId":"20150625010814.GA263667@vauxhall.crustytoothpaste.net","threadId":"39699","inReplyTo":"20150624094919.GC5436@peff.net","subject":"Re: RFC/Pull Request: Refs db backend","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2015-06-25T01:08:15Z","receivedAt":"2015-06-25T01:08:15Z","isPatch":false,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"On Wed, Jun 24, 2015 at 05:49:20AM -0400, Jeff King wrote:\n> I don't know how much that helps for the JGit situation. It punts the\n> native code out of JGit, but people using JGit still have to have the\n> native helper from git on their system.  I have no problems at all with\n> pluggable $FANCY_DB that not everybody supports.  But I think we would\n> want _some_ baseline that is reasonably performant, and that everybody\n> will support. I'm not sure putting the index into a flat file is\n> performant enough. Is there any basic key/value store that is has both a\n> C and a pure-Java version (e.g., berkeley db)?\n\nBerkeley DB has switched to the AGPLv3 for new versions.  Besides being\nunpalatable for many people, it's also incompatible with the GPLv2.  I\ndo otherwise like Berkeley DB: it performs reasonably well and is\navailable on most systems.\n-- \nbrian m. carlson / brian with sandals: Houston, Texas, US\n+1 832 623 2791 | http://www.crustytoothpaste.net/~bmc | My opinion only\nOpenPGP: RSA v4 4096b: 88AC E9B2 9196 305B A994 7552 F1BA 225C 0223 B187\n"}]}