git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 00/17] Remove assumptions about refname lifetimes

From
Johan Herland <johan@herland.net>
Date
May 20, 2013, 17:03 UTC
Message-ID
<CALKQrgd3=5Rb5wbDGTV7PQfcingimYf08yEHcbfSCkjGDUU_Ng@mail.gmail.com>
In-Reply-To
<7vfvxhwqt1.fsf@alter.siamese.dyndns.org>
On Mon, May 20, 2013 at 6:37 PM, Junio C Hamano <gitster@pobox.com> wrote:
Show 23 quoted lines
> Johan Herland <johan@herland.net> writes:
>> For server-class installations we need ref storage that can be read
>> (and updated?) atomically, and the current system of loose + packed
>> files won't work since reading (and updating) more than a single file
>> is not an atomic operation. Trivially, one could resolve this by
>> dropping loose refs, and always using a single packed-refs file, but
>> that would make it prohibitively expensive to update refs (the entire
>> packed-refs file must be rewritten for every update).
>>
>> Now, observe that we don't have these race conditions in the object
>> database, because it is an add-only immutable data store.
>>
>> What if we stored the refs as a tree object in the object database,
>> referenced by a single (loose) ref?
>
> What is the cost of updating a single branch with that scheme?
>
> Doesn't it end up recording roughly the same amount of information
> as updating a single packed-refs file that is flat, but with the
> need to open a few tree objects (top-level, refs/, and refs/heads/),
> writing out a blob that stores the object name at the tip, computing
> the updated trees (refs/heads/, refs/ and top-level), and then
> finally doing the compare-and-swap of that single loose ref?

Yes, except that when you update packed-refs, you have to write out the _entire_ file, whereas with this scheme you only have to write out the part of the refs hierarchy you actually touched (e.g. rewriting refs/heads/foo would not have to write out anything inside refs/tags/*). If you have small number of branches, and a huge number of tags, this scheme might end up being cheaper than writing the entire packed-refs. But in general, it's probably much more expensive to go via the odb.

> You may guarantee atomicity but it is the same granularity of
> atomicity as a single packed-refs file.

Yes, as I argued elsewhere in this thread: It seems that _any_ filesystem-based solution must resort to having all updates depend on a single file in order to guarantee atomicity.

Show 9 quoted lines
> When you are updating a
> branch while somebody else is updating a tag, of course you do not
> have to look at refs/tags/ in your operation and you can write out
> your final packed-refs equivalent tree to the object database
> without racing with the other process, but the top-level you come up
> with and the top-level the other process comes up with (which has
> an up-to-date refs/tags/ part, but has a stale refs/heads/ part from
> your point of view) have to race to update that single loose ref,
> and one of you have to back out.
True.
Show 10 quoted lines
> That "backing out" can be made more intelligently than just dying
> with "compare and swap failed--please retry" message, e.g. you at
> that point notice what you started with, what the other party did
> while you were working on (i.e. updating refs/tags/), and three-way
> merge the refs tree, and in cases where "all refs recorded as loose
> refs" scheme wouldn't have resulted in problematic conflict, such a
> three-way merge would resolve trivially (you updated refs/heads/ and
> the update by the other process to refs/tags/ would not conflict
> with what you did).  But the same three-way merge scheme can be
> employed with the current flat single packed-refs scheme, can't it?

Yes. (albeit without reusing the machinery we already have for doing three-way merges)

> Even worse, what is the cost of looking up the value of a single
> branch?  You would need to open a few tree objects and the leaf blob
> that records the object name the ref points at, wouldn't you?

Yes. Probably a showstopper, although single branch/ref lookup might not be so common on server side, as it is on the user side.

Show 6 quoted lines
> Right now, such a look-up is either opening a single small file and
> reading the first 41 bytes off of it, and falling back (when the ref
> in question is packed) to read a single packed-refs file and finding
> the ref you want from it.
>
> So...
Yep...
...Johan
-- 
Johan Herland, <johan@herland.net>
www.herland.net
Previous: Junio C HamanoNext: Junio C Hamano
Message 41 of 42 in “Remove assumptions about refname lifetimes”
  1. 00/17 Remove assumptions about refname lifetimesMichael Haggerty, May 19, 2013
  2. 01/17 describe: make own copy of refnameMichael Haggerty, May 19, 2013
  3. 02/17 fetch: make own copies of refnamesMichael Haggerty, May 19, 2013
  4. 03/17 add_rev_cmdline(): make a copy of the name argumentMichael Haggerty, May 19, 2013
  5. 04/17 builtin_diff_tree(): make it obvious that function wants two entriesMichael Haggerty, May 19, 2013
  6. Junio C HamanoMay 21, 2013
  7. Michael HaggertyMay 23, 2013
  8. 05/17 cmd_diff(): use an object_array for holding treesMichael Haggerty, May 19, 2013
  9. Junio C HamanoMay 21, 2013
  10. Michael HaggertyMay 23, 2013
  11. 06/17 cmd_diff(): rename local variable "list" -> "entry"Michael Haggerty, May 19, 2013
  12. 07/17 cmd_diff(): make it obvious which cases are exclusive of each otherMichael Haggerty, May 19, 2013
  13. 08/17 revision: split some overly-long linesMichael Haggerty, May 19, 2013
  14. Junio C HamanoMay 21, 2013
  15. Michael HaggertyMay 23, 2013
  16. Junio C HamanoMay 23, 2013
  17. 09/17 gc_boundary(): move the check "alloc <= nr" to callerMichael Haggerty, May 19, 2013
  18. Junio C HamanoMay 21, 2013
  19. Michael HaggertyMay 23, 2013
  20. Junio C HamanoMay 23, 2013
  21. 10/17 get_revision_internal(): make check less mysteriousMichael Haggerty, May 19, 2013
  22. Junio C HamanoMay 21, 2013
  23. Michael HaggertyMay 23, 2013
  24. 11/17 object_array: add function object_array_filter()Michael Haggerty, May 19, 2013
  25. 12/17 object_array_remove_duplicates(): rewrite to reduce copyingMichael Haggerty, May 19, 2013
  26. 13/17 fsck: don't put a void*-shaped peg in a char*-shaped holeMichael Haggerty, May 19, 2013
  27. 14/17 find_first_merges(): initialize merges variable using initializerMichael Haggerty, May 19, 2013
  28. 15/17 find_first_merges(): remove unnecessary codeMichael Haggerty, May 19, 2013
  29. 16/17 object_array_entry: copy name before storing in name fieldMichael Haggerty, May 19, 2013
  30. Johan HerlandMay 20, 2013
  31. Michael HaggertyMay 20, 2013
  32. Jeff KingMay 20, 2013
  33. Michael HaggertyMay 20, 2013
  34. 17/17 refs: document the lifetime of the refname passed to each_ref_fnMichael Haggerty, May 19, 2013
  35. Johan HerlandMay 20, 2013
  36. Michael HaggertyMay 20, 2013
  37. Junio C HamanoMay 20, 2013
  38. Jeff KingMay 20, 2013
  39. Johan HerlandMay 20, 2013
  40. Junio C HamanoMay 20, 2013
  41. Johan HerlandMay 20, 2013
  42. Junio C HamanoMay 21, 2013

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.