Persistent data structures on a dispersed storage network memory

• US 10,169,392 B2
• Filed: 03/08/2017
• Issued: 01/01/2019
• Est. Priority Date: 03/08/2017
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Khadiwala, Ravi V.
• Primary Examiner(s): Peach, Polina G
• Application Number:
  US15/453,575
• Publication Number:
  US 20180260427A1
• Time in Patent Office: 664 Days
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2322 using timestamps
• CPC Class Codes: G06F 16/24562 Pointer or reference processing operations
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor

Abstract

Systems and Methods for dispersed data structures (DDS) in a distributed storage network are disclosed. A dispersed storage processing unit handling a request to insert a key value pair into a DDS could lookup what the most up to date DDS is, which could be held by a single source with a pointer to the current DDS root. The processing unit could then descend the DDS until it finds the leaf node that owns the requester'"'"'s key and make a copy of the leaf with the key inserted. The processing unit could then make a copy of the parent of the node, replacing the pointer to the copied node with a pointer to the new copy, repeat this step until the root is reached, and make a copy of the root in a similar fashion but also including a pointer to the original DDS root.

Claims

1. A method of updating a dispersed data structure (DDS) in a dispersed storage network (DSN) having a plurality of dispersed storage (DS) units, wherein the DDS is stored as a plurality of encoded data slices in one or more of the plurality of DS units, and wherein the DDS includes an original root node, at least one original internal node including an original first internal node, and an original leaf node, the method comprising:

retrieving one or more first encoded data slices of the plurality of encoded data slices, the one or more first encoded data slices containing the original root node, the original root node including an original first internal node pointer related to the original first internal node;

retrieving one or more second encoded data slices of the plurality of encoded data slices, the one or more second encoded data slices containing the at least one original internal node including the original first internal node and the original leaf node;

wherein the at least one original internal node includes an original leaf node pointer related to the original leaf node and a respective original internal node pointer related to each original internal node beyond the original first internal node;

wherein the step of retrieving one or more second encoded data slices of the plurality of encoded data slices is based on the original first internal node pointer, the respective original internal node pointer related to each original internal node beyond the original first internal node and the original leaf node pointer;

storing a modified leaf node in the DSN based on a first modification to the original leaf node; and

storing at least one modified internal node including a modified first internal node in the DSN based on one or more second modifications to the at least one original internal node including the original first internal node;

wherein the at least one modified internal node includes a respective modified internal node pointer related to each of the at least one modified internal nodes beyond the modified first internal node and a modified leaf node pointer related to the modified leaf node; and

storing a modified root node in the DSN based on a third modification to the original root node; and

wherein the modified root node includes a modified first internal node pointer related to the modified first internal node and an original root node pointer related to the original root node.

2. The method of claim 1, wherein the first modification includes inserting a key value pair.

3. The method of claim 1, further comprising determining a current version of the DDS prior to the step of retrieving one more first encoded data slices of the plurality of data slices.

4. The method of claim 3, wherein determining the current version includes assessing the original root node pointer.

5. The method of claim 1, further including storing metadata relating to the first modification, the one or more second modifications, and the third modification.

6. The method of claim 5, wherein the metadata includes a timestamp.

7. The method of claim 1, wherein the step of storing the modified root node further comprises merging the modified root node with another modified root node, wherein the another modified root node is based on a fourth modification to the original root node.

8. The method of claim 1, further comprising modifying the modified root node such that the modified first internal node pointer is replaced with the original first internal node pointer.

9. The method of claim 1, further comprising deleting the original root node, the at least one original internal node including the original first internal node, and the original leaf node.

10. A dispersed storage processing unit for updating a dispersed data structure (DDS) in a dispersed storage network (DSN) having a plurality of dispersed storage (DS) units, wherein the DDS is stored as a plurality of encoded data slices in one or more of the plurality of DS units, and wherein the DDS includes an original root node, at least one original internal node including an original first internal node, and an original leaf node, the dispersed storage processing unit comprising:

a communications interface;

a memory; and

a computer processor;

where the memory includes instructions for causing the computer processor to;

retrieve one or more first encoded data slices of the plurality of encoded data slices, the one or more first encoded data slices containing the original root node, the original root node including an original first internal node pointer related to the original first internal node;

retrieve one or more second encoded data slices of the plurality of encoded data slices based on an original first internal node pointer, a respective original internal node pointer related to each original internal node beyond the original first internal node and an original leaf node pointer, wherein the one or more second encoded data slices contain the at least one original internal node including the original first internal node and the original leaf node and wherein the at least one original internal node includes the original leaf node pointer related to the original leaf node and the respective original internal node pointer related to each original internal node beyond the original first internal node;

store a modified leaf node in the DSN based on a first modification to the original leaf node;

store at least one modified internal node including a modified first internal node in the DSN based on one or more second modifications to the at least one original internal node including the original first internal node, wherein the at least one modified internal node includes a respective modified internal node pointer related to each of the at least one modified internal nodes beyond the modified first internal node and a modified leaf node pointer related to the modified leaf node; and

store a modified root node in the DSN based on a third modification to the original root node, wherein the modified root node includes a modified first internal node pointer related to the modified first internal node and an original root node pointer related to the original root node.

11. The dispersed storage processing unit of claim 10, wherein the first modification includes inserting a key value pair.

12. The dispersed storage processing unit of claim 10, wherein the memory further comprises instructions for causing the computer processor to determine a current version of the DDS.

13. The dispersed storage processing unit of claim 12, wherein the memory further comprises instructions for causing the computer processor to determine the current version by assessing the original root node pointer.

14. The dispersed storage processing unit of claim 10, wherein the memory further comprises instructions for causing the computer processor to store metadata relating to the first modification, the one or more second modifications, and the third modification.

15. The dispersed storage processing unit of claim 14, wherein the metadata includes a timestamp.

16. The dispersed storage processing unit of claim 10, wherein the memory further comprises instructions for causing the computer processor to merge the modified root node with another modified root node, wherein the another modified root node is based on a fourth modification to the original root node.

17. The dispersed storage processing unit of claim 10, wherein the memory further comprises instructions for causing the computer processor to modify the modified root node such that the modified first internal node pointer is replaced with the original first internal node pointer.

18. The dispersed storage processing unit of claim 10, wherein the memory further comprises instructions for causing the computer processor to delete the original root node, the at least one original internal node including the original first internal node, and the original leaf node.

19. A dispersed storage network (DSN) for updating a dispersed data structure (DDS), comprising:

a plurality of dispersed storage (DS) units, and a DS processing unit, wherein the DDS is stored as a plurality of encoded data slices in one or more of the plurality of DS units, and wherein the DDS includes an original root node, at least one original internal node including an original first internal node, and an original leaf node, the dispersed storage processing unit including;

a communications interface;

a memory; and

a computer processor;

where the memory includes instructions for causing the computer processor to;

retrieve one or more first encoded data slices of the plurality of encoded data slices, the one or more first encoded data slices containing the original root node, the original root node including an original first internal node pointer related to the original first internal node;

retrieve one or more second encoded data slices of the plurality of encoded data slices based on an original first internal node pointer, a respective original internal node pointer related to each original internal node beyond the original first internal node and an original leaf node pointer, wherein the one or more second encoded data slices contain the at least one original internal node including the original first internal node and the original leaf node and wherein the at least one original internal node includes the original leaf node pointer related to the original leaf node and the respective original internal node pointer related to each original internal node beyond the original first internal node;

store a modified leaf node in the DSN based on a first modification to the original leaf node;

store at least one modified internal node including a modified first internal node in the DSN based on one or more second modifications to the at least one original internal node including the original first internal node, wherein the at least one modified internal node includes a respective modified internal node pointer related to each of the at least one modified internal nodes beyond the modified first internal node and a modified leaf node pointer related to the modified leaf node; and

store a modified root node in the DSN based on a third modification to the original root node, wherein the modified root node includes a modified first internal node pointer related to the modified first internal node and an original root node pointer related to the original root node.

20. The dispersed storage network of claim 19, wherein the first modification includes inserting a key value pair.