Optimistic Concurrency Control by Melding Trees
In this paper, the authors describe a new optimistic concurrency control algorithm for tree-structured data called meld. Each transaction executes on a snapshot of a multi-version database and logs a record with its intended updates. Meld processes log records in log order on a cached partial-copy of the last committed state to determine whether each transaction commits. If so, it merges the transaction's updates into that state. Meld is used in the Hyder transaction system and enables Hyder to scale out without partitioning. Since meld is on the critical path of transaction execution, it must be very fast.