[GitHub] kocolosk opened a new issue #1957: Data model for storing revision history in FoundationDB

[GitBox <gi...@apache.org>]

kocolosk opened a new issue #1957: Data model for storing revision history in FoundationDB
URL: https://github.com/apache/couchdb/issues/1957
 
 
   [NOTE]: # ( ^^ Provide a general summary of the RFC in the title above. ^^ )
   
   # Introduction
   
   This is a proposal for the storage of document revision history metadata as a set of KVs in FoundationDB.
   
   ## Abstract
   
   This design stores each edit branch as its own KV, and all of the edit branches are stored separately from the actual document data. Document reads can avoid retrieving this information, while writes can avoid retrieving the document body.
   
   ## Requirements Language
   
   [NOTE]: # ( Do not alter the section below. Follow its instructions. )
   
   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED",  "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC 2119](https://www.rfc-editor.org/rfc/rfc2119.txt).
   
   ## Terminology
   
   [TIP]:  # ( Provide a list of any unique terms or acronyms, and their definitions here.)
   
   ---
   
   # Detailed Description
   
   The size limits in FoundationDB preclude storing the entire revision tree as a single value; in pathological situations the tree could exceed 100KB. Rather, we propose to store each edit *branch* as a separate KV. Specifically, we create a "revisions" subdirectory in each database directory to store the revision trees with keys and values that look like
   
   `(“revisions”, DocID, NotDeleted, RevFormat, RevPosition, RevHash) = (VersionstampForCurrentRev, [ParentRev, GrandparentRev, …])`
   
   where the individual elements of the key and value are defined as follows:
   - `DocID`: the document ID
   - `NotDeleted`: `\x00` if the leaf of the edit branch is deleted, `\x01` otherwise
   - `RevFormat`: enum for the revision encoding being used, start at `\x01` with this proposal
   - `RevPosition`: positive integer encoded using standard tuple layer encoding (signed, variable-length, order-preserving)
   - `RevHash`: 16 bytes uniquely identifying this revision
   - `VersionstampForCurrentRev`: the FoundationDB [versionstamp](https://apple.github.io/foundationdb/api-python.html#fdb.tuple.Versionstamp) associated with the transaction that created this revision
   - `[ParentRev, GrandparentRev, ...]`: 16 byte identifiers of ancestors, up to 1000 by default
   
   In order to stay compatible with FoundationDB size limits we need to prevent administrators from increasing `_revs_limit` beyond what we can fit into a single value. Suggest **4000** as a max.
   
   # Advantages
   
   We can apply an interactive edit without retrieving the entire conflicted revision tree; we need only retrieve and modify the single branch against which the edit is being applied. 
   
   We also ensure that a document update only needs to read the edit branch KV against which the update is being applied, and it can read that branch immediately knowing only the content of the edit that is being attempted (i.e., it does not need to read the current version of the document itself).
   
   Interactively updating a document with a large number of edit branches is dramatically cheaper, as only one edit branch is read or modified regardless of the number of branches that exist.
   
   Including `NotDeleted` in the key ensures that we can efficiently accept the case where we upload a new document with the same ID where all previous edit branches have been deleted; i.e. we can construct a key selector which automatically tells us there are no `deleted=false` edit branches. An interactive edit that supplies a revision identifier of a deleted leaf will fail with a conflict, which matches current behavior.
   
   The `RevFormat` enum gives us the ability to evolve revision history storage over time, and to support alternative conflict resolution policies like Last Writer Wins.
   
   Access to `VersionstampForCurrentRev` ensures we can clear the old entry in the `by_seq` space during an edit. The `set_versionstamped_value` API is used to store this value automatically.
   
   The key structure above naturally sorts so that the "winning" revision is the last one in the list. This is a small optimization for reads with `?revs=true` or `?revs_info=true`, where we want the details of the winning edit branch but don't actually know the `RevPosition` and `RevHash` of that branch.
   
   # Disadvantages
   
   Historical revision identifiers shared by multiple edit branches are duplicated.
   
   # Key Changes
   
   Administrators cannot set `_revs_limit` larger than 4,000 (previously unlimited?). Default stays the same at 1,000.
   
   ## Modules affected
   
   TBD depending on exact code layout going forward, but the `couch_key_tree` module contains the current revision tree implementation.
   
   ## HTTP API additions
   
   None.
   
   ## HTTP API deprecations
   
   None.
   
   # References
   
   [Original mailing list discussion](https://lists.apache.org/thread.html/853b86f3a83108745af510959bb381370a99988af4528617bdbe1be4@%3Cdev.couchdb.apache.org%3E)
   
   # Acknowledgements
   
   Thanks to @iilyak, @davisp, @janl, @garrensmith and @rnewson for comments on the mailing list discussion.

----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on GitHub and use the
URL above to go to the specific comment.
 
For queries about this service, please contact Infrastructure at:
users@infra.apache.org


With regards,
Apache Git Services