US Patent No. 10,558,638

PERSISTENT DATA STRUCTURES ON A DISPERSED STORAGE NETWORK MEMORY


Patent No. 10,558,638
Issue Date February 11, 2020
Title Persistent Data Structures On A Dispersed Storage Network Memory
Inventorship Ravi V. Khadiwala, Bartlett, IL (US)
Assignee INTERNATIONAL BUSINESS MACHINES CORPORATION, Armonk, NY (US)

Claim of US Patent No. 10,558,638

1. A method of rolling back an updated 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; and
rolling back to a previous version of the DDS by modifying a current root node pointer to a root node pointer of a previous version of the DDS.