Data management using writeable snapshots in multi-versioned distributed B-trees

摘要

A method for managing data using writeable snapshots in a multi-versioned, distributed B-tree comprising nodes distributed over a plurality of servers, includes receiving a transaction request specifying a transaction type, the transaction having a transaction snapshot id, and determining the transaction type. If the transaction type is an update transaction, the method includes determining a node to update, which is defined by a node snapshot id, and if the transaction snapshot id is greater that the node snapshot id, the method copies the node and updates the copy to create a writeable snapshot, assigns the transaction snapshot id as a node snapshot id of the copy, and places a pointer from the node to the copy.

主权项

1. A method for managing data using writeable snapshots in a multi-versioned, distributed B-tree comprising nodes distributed over a plurality of servers, comprising:
receiving a transaction request specifying a transaction type, the transaction having a transaction snapshot id, wherein the transaction snapshot id comprises an identification of a snapshot the transaction applies to; and determining the transaction type, wherein: the transaction type is an update transaction:
determining a node to update, wherein the node comprises a node snapshot id and a copy snapshot id, wherein the node snapshot id comprises a snapshot id at which the node was created and the copy snapshot id comprises a snapshot id of the first copy of the node, andif the transaction snapshot id is greater than or equal to the node snapshot id and less than the copy snapshot id:
copying the node and updating the copy to create a writeable snapshot, wherein a snapshot comprises a point-in-time view of data and the node includes a read only snapshot;assigning the transaction snapshot id as a node snapshot id of the copy;incrementing sequence numbers of the node and the copy; andplacing a pointer from the node to the copy.