US 10,757,171 B1 · Merge trees for collaboration

Abstract

Disclosed embodiments provide for collaborative access to a distributed data structure. The disclosed embodiments include collaboration participant devices or instances that each represent a distributed data structure via a tree data structure. The collaboration participants perform operations on the distributed data structure and communicate these operations to each other via a serialization service. The tree structure maintained by each of the collaboration participants stores unacknowledged operations and also collaboration participant specific length information for collaboration participants. Once a particular operation has been acknowledged by each of the collaboration participants, this is communicated to all of the participants by the serialization service. The collaboration participants may then perform maintenance on a portion of the tree structure represented the acknowledged operation. For example, nodes of the tree representing adjacent data in the distributed data structure may be combined, or data removed by an acknowledged operation may be removed from the tree.

Claims20

Dependent claims

A first device, comprising:

hardware processing circuitry;
and
an electronic memory storing instructions that when executed configure the hardware processing circuitry to perform operations comprising:
receiving a notification of a second device operation on a distributed data structure, the second device operation indicating a position within the distributed data structure associated with the second device operation;
identifying a first node of a tree, the first node representing a portion of the distributed data structure;
first determining, based on the first node, a minimum length of the represented portion;
identifying, based on the first node, a partial length of the represented portion that is specific to the second device;
second determining, based on the minimum length and the partial length, a size of the represented portion;
third determining, based on the size, the position within the distributed data structure is included in the represented portion;
identifying, based on the third determination, a leaf node below the first node in the tree;
and
representing, based on the identified leaf node, the second device operation on the distributed data structure.

9 more elements

A method performed by a device, comprising:

joining a collaboration, the collaboration providing access to a distributed data structure;
receiving a plurality of indications of a serialized plurality of corresponding operations on a distributed data structure, each indication further indicating a corresponding originating device associated with each of the corresponding operations;
representing the serialized plurality of operations and resulting corresponding portions of the distributed data structure in leaf nodes of a tree data structure;
representing, in a non-leaf node of the tree, and based on a specific operation of the serialized plurality of operations, an originating device specific length of a portion of the distributed data structure represented by leaf nodes below the non-leaf node;
receiving an additional indication of an additional operation on the distributed data structure, and a further indication of a particular originating device associated with the additional operation, the additional indication further indicating a position within the distributed data structure associated with the additional operation;
determining based on the originating device specific length of the portion and the particular originating device associated with the additional operation, a leaf node of the tree associated with the position;
and
modifying the determined leaf node based on the additional operation.

5 more elements

Dependencies are inferred from the claim text.

Merge trees for collaboration

Life of this patent

Merge trees for collaboration

Life of this patent

Abstract

Claims20