{"thread":{"id":"33787","subject":"Thoughts about eliminating reachability races","startedAt":"2013-05-11T09:47:39Z","lastAt":"2013-05-11T09:47:39Z","messageCount":1,"participants":["Michael Haggerty"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"216982","messageId":"518E13BB.8000009@alum.mit.edu","threadId":"33787","inReplyTo":null,"subject":"Thoughts about eliminating reachability races","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-11T09:47:39Z","receivedAt":"2013-05-11T09:47:39Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"How to get rid of reachability races?\n\nThis email is meant more as a basis for discussion (including at the\nGitMerge conference that is currently running) than as a fully-baked\nproposal.\n\nA lot of reachability-related races have been discussed recently:\n\n* If a reference is renamed while a prune is reading the loose\n  references, it could be that prune sees neither the old nor the new\n  version of the reference and could prune the objects referred to by\n  the reference.\n\n* If a process is building a tree, it could find that some objects are\n  already in the DB, in which case it will refer to the existing\n  objects.  But these objects might be unreachable, and could be\n  pruned before the process gets around to creating a root reference\n  that makes them reachable.\n\n* Other races involving packed refs vs. loose refs.\n\nThese races are most critical for busy hosting sites like GitHub but\ncould theoretically impact anybody.\n\nIt has been discussed that we should offer, as an alternative to\npacked-refs/loose refs in the filesystem, a way to store refs in a\nsingle database store of some kind that offers ACID guarantees.  This\nwould solve the first and last kind of race in one step.\n\nOther mechanisms are being discussed to address the second race, maybe\ninvolving moving pruned objects into a kind of purgatory for a period\nof time before they are finally deleted.\n\nBut I have the feeling that these races could also be solved via the\nuse of the same database.\n\nI am thinking of a scheme in which the database stores two more things\nduring prunes:\n\n1. The names of objects that are being pruned.  Such objects are\n   considered deleted (even though they might not yet have been\n   deleted from the object database) and no new references may be made\n   to them.\n\n2. The names of objects to which new links have been added.  Prune is\n   not allowed to delete this objects or objects to which they refer.\n\nlike those used for incremental garbage\ncollection of memory, in which *during* a garbage collection the VM\nkeeps tracks of new references that are made to objects that are in\nthe generation that is currently being garbage collected.  The garbage\ncollector has to consider these links in its reachability analysis.\n\nOur situation is a little bit more complicated, because it is not easy\nto inform a git process that a prune has been started.  At best, the\nprocess can check occasionally whether a prune is running.  On the\nother hand, it *is* permissible for Git processes to fail in\nexceptional circumstances, as long as it happens rarely and leaves the\nobject store in a valid state.\n\nSo I'm thinking of a scheme in which\n\n1. prune has to list \"doomed\" objects to the database before deleting\n   them.  Such objects are considered deleted by other processes (*if*\n   they know that a prune is running).\n\n2. If a process knows that a prune is running, then it records to the\n   database any new links that it makes to existing objects.  Prune is\n   not allowed to prune such objects.\n\n3. To catch the situation that a process didn't know that a prune is\n   running, we keep a prune generation number.  If that number changes\n   between the beginning/end of a process, then the process fails\n   without recording any new references.\n\n\nDesign goals:\n\n* Correctness\n\n* \"Normal processes\" don't block on each other or on prune.\n\n* Normal processes don't get significantly slower in the usual case\n  (but are allowed to get slower during pruning).\n\n\nAssumptions:\n\n* There is a store with atomic transactions.\n\n* Most normal processes run more quickly than a prune.  It will be\n  rare for an entire prune to run while a normal process is running\n  (though even if it does we must behave correctly).\n\n* Normal processes are allowed to fail occasionally as long as they\n  leave the DB in a valid state.\n\n\nIn the store, record the following values:\n\n* Git references -- (refname, object_name) pairs\n\n* prune_in_progress (boolean) -- a destructive operation is running\n\n* prune_generation (integer) -- incremented each time objects are\n  invalidated\n\n* doomed_objects -- a list of the names of objects that a prune is in\n  the process of deleting.  These objects *are considered deleted* and\n  may not be referred to.  Only used when prune_in_progress.\n\n* new_links -- a list of the names of objects newly created or newly\n  referenced during a prune.  These objects are considered referenced\n  and *may not be pruned*.  Only used when prune_in_progress.\n\n\n\nA nondestructive operation will usually have two interactions with the\nstore.  At start::\n\n    def record_new_link(sha1):\n        \"\"\"Record that there is a new link to object sha1.\"\"\"\n\n        if prune_in_progress:\n            if sha1 in doomed_objects:\n                die()\n            append sha1 to new_links (RAM copy)\n\n\n    with transaction:\n        read prune_generation\n        read prune_in_progress\n        if prune_in_progress:\n            read doomed_objects\n        read any needed Git refs\n\n    for each new object or new link to an old object:\n        record_new_link(object_name)\n\n    with transaction:\n        if prune_generation has changed:\n            die()\n        if prune_in_progress:\n            read current doomed_objects:\n            if any of new_links are in doomed_objects:\n                die()\n            append list of new git references to new_links\n        write changes to git references\n\n    # From this moment on, the new_links are considered to be\n    # reachable and neither they nor any objects that they refer to\n    # may be pruned.\n\n\n\nA destructive operation will have at least three interactions with the\nstore::\n\n    with transaction:\n        if prune_in_progress:\n            abort\n        prune_in_progress = True\n        clear doomed_objects list\n        clear new_links list\n        known_links = list of all object references\n\n    doomed_objects = compute list of objects unreachable from known_links\n\n    while True:\n        with transaction:\n            write current version of doomed_objects\n            read new_links from store\n            clear new_links in store\n\n        # From this moment on, objects in doomed_objects are\n        # considered deleted.\n\n        if new_links is empty:\n            break\n        else:\n            remove objects reachable from new_links from doomed_objects\n\n    delete doomed objects from filesystem\n\n    with transaction:\n        clear list of doomed objects\n        increment stored value of prune_generation\n        prune_in_progress = False\n\n\nI hope that's clear; please poke holes in it.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"}]}