Providing a distributed balanced tree across plural servers

• US 8,909,677 B1
• Filed: 04/27/2007
• Issued: 12/09/2014
• Est. Priority Date: 04/27/2007
• Status: Expired due to Fees

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Aguilera, Marcos K., Shah, Mehul A., Golab, Wojciech
• Primary Examiner(s): Mofiz, Apu
• Assistant Examiner(s): Nguyen, Thu Nga
• Application Number:
  US11/796,198
• Time in Patent Office: 2,783 Days
• Field of Search: None
• US Class Current: 707/797
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees

Abstract

To access data, a distributed balanced tree having nodes distributed across plural servers is accessed. Version information is associated with the nodes of the distributed balanced tree. During an operation that accesses the distributed balanced tree, the version information is checked to determine whether content of one or more nodes of the distributed balanced tree has changed during the operation.

Claims

1. A method, executed by at least one processor, of accessing data, comprising:

accessing, by the at least one processor during an operation, a distributed balanced tree having a plurality of nodes distributed across plural servers;

accessing, by the at least one processor, version information associated with the nodes of the distributed balanced tree;

during the operation, checking, by the at least one processor, the version information to determine whether content of one or more nodes of the distributed balanced tree has changed during the operation;

in response to determining based on checking the version information that the content of the one or more nodes of the distributed balanced tree has changed, aborting the operation; and

replicating the version information of at least a particular one of the nodes of the distributed balanced tree on multiple servers, wherein replicating the version information comprises replicating version information of higher-level nodes in the distributed balanced tree on a greater number of servers than version information of lower-level nodes in the distributed balanced tree.

2. The method of claim 1, wherein accessing the distributed balanced tree comprises accessing a distributed B-tree.

3. The method of claim 1, wherein checking the version information is part of a protocol that performs a batch of actions atomically.

4. The method of claim 3, wherein the protocol comprises a two-phase protocol that places locks on certain nodes of the distributed balanced tree.

5. The method of claim 4, wherein checking the version information is part of a first phase of the two-phase protocol,

wherein performing the aborting is part of a second phase of the two-phase protocol.

6. The method of claim 5, further comprising committing the operation in response to the version information check indicating that the content of the one or more nodes of the distributed balanced tree has not changed during the operation, wherein the committing is performed as part of the second phase of the two-phase protocol.

7. The method of claim 1, further comprising:

caching information of certain nodes of the distributed balanced tree in a client computer,

wherein the operation is performed in response to a request by the client computer.

8. The method of claim 1, further comprising:

in response to a change of the particular node, updating the version information by each of the multiple servers on which the version information is replicated.

9. The method of claim 1, further comprising:

storing a first data structure identifying servers on which the version information of the particular node of the distributed balanced tree is stored.

10. The method of claim 9, wherein the particular node has a parent node, the method further comprising:

storing a second data structure identifying servers on which the version information of the parent node is stored,

wherein the second data structure identifies a greater number of servers than the first data structure.

11. The method of claim 1, wherein the version information of each of leaf nodes of the distributed balanced tree are kept in a single respective server.

12. The method of claim 1, further comprising:

performing plural modification operations that access nodes of the distributed balanced tree in a multi-operation transaction that performs the plural modification operations atomically.

13. The method of claim 12, further comprising:

identifying version information that has to be validated;

identifying nodes of the distributed balanced tree that have to be modified by the multi-operation transaction; and

performing the version information validating and modification of identified nodes atomically.

16. The method of claim 1, further comprising:

in response to determining based on checking the version information that the content of the one or more nodes of the distributed balanced tree has not changed, committing the operation.

14. A method comprising:

storing a distributed B-tree across plural servers;

storing version information associated with nodes of the distributed B-tree;

receiving, by at least one processor, a request, during an operation that accesses the distributed B-tree, to validate version information of the nodes;

providing feedback, to a client computer, regarding the validating of the version information;

receiving, from the client computer, an indication whether to abort or commit a modification of one or more nodes of the distributed B-tree performed by the operation, wherein the indication is responsive to the feedback;

checking for at least one server that is hanging due to no receipt of the indication; and

causing an abort or commit of the modification if the checking finds the at least one server that is hanging.

17. The method of claim 14, wherein the indication is an indication to abort the operation if the feedback indicates that a portion of the distributed B-tree has changed during the operation.

18. The method of claim 17, wherein the indication is an indication to complete the operation if the feedback indicates that the distributed B-tree has not changed during the operation.

15. A non-transitory computer-usable storage medium containing instructions that when executed cause at least one computer to:

access, during an operation, a distributed balanced tree having a plurality of nodes distributed across plural servers;

access version information associated with the nodes of the distributed balanced tree;

during the operation, check the version information to determine whether content of one or more nodes of the distributed balanced tree has changed during the operation;

in response to determining based on checking the version information that the content of the one or more nodes of the distributed balanced tree has changed, abort the operation; and

replicate the version information of at least a particular one of the nodes of the distributed balanced tree on multiple servers, wherein replicating the version information comprises replicating version information of higher-level nodes in the distributed balanced tree on a greater number of servers than version information of lower-level nodes in the distributed balanced tree.

19. The non-transitory computer-usable storage medium of claim 15, which wherein the instructions when executed cause the at least one computer to further:

in response to determining based on checking the version information that the content of the one or more nodes of the distributed balanced tree has not changed, allowing the operation to complete.