Batching modifications to nodes in a dispersed index

• US 10,318,549 B2
• Filed: 11/17/2017
• Issued: 06/11/2019
• Est. Priority Date: 09/13/2012
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Dhuse, Greg R., Volvovski, Ilya
• Primary Examiner(s): Giardino, Jr., Mark A
• Application Number:
  US15/816,813
• Publication Number:
  US 20180075121A1
• Time in Patent Office: 571 Days
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/2386 Bulk updating operations data conversion details G06F16/258
• 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
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A method includes queuing a plurality of changes to a hierarchical index construct including a plurality of index structures. An index structure includes a plurality of nodes and a node is dispersed storage error encoded to produce a set of encoded data slices (EDSs). The method further includes, when triggered, determining a plurality of affected nodes of the plurality of index structures based on the plurality of changes. The method further includes retrieving a threshold number of EDSs and dispersed storage error decoding the threshold number of EDSs to produce the plurality of affected nodes. The method further includes, for a change of the plurality of changes, identifying one or more nodes of the plurality of affected nodes for which the change is applicable and updating each of the one or more nodes based on the change to produce updated one or more nodes.

Claims

1. A method comprises:

queuing, by a computing device of a dispersed storage network (DSN), a plurality of changes to a hierarchical index construct that includes a plurality of index structures, wherein an index structure of the plurality of index structures includes a plurality of nodes, wherein a node of the plurality of nodes is dispersed storage error encoded to produce a set of encoded data slices, and wherein the set of encoded data slices is stored in a set of storage units of the DSN;

when triggered, determining, by the computing device, a plurality of affected nodes of pluralities of nodes of the plurality of index structures based on the plurality of changes queued when triggered;

retrieving, by the computing device, a threshold number of encoded data slices for each of the plurality of affected nodes from storage units of the DSN;

dispersed storage error decoding, by the computing device, the threshold number of encoded data slices for each of the plurality of affected nodes to produce the plurality of affected nodes; and

for a change of the plurality of changes;

identifying, by the computing device, one or more nodes of the plurality of affected nodes for which the change is applicable; and

updating, by the computing device, each of the one or more nodes based on the change to produce updated one or more nodes.

2. The method of claim 1 further comprises:

dispersed storage error encoding, by the computing device, the updated one or more nodes to produce a threshold number of updated encoded data slices for each of the updated one or more nodes; and

sending, by the computing device, the threshold number of updated encoded data slices for each of the updated one or more nodes to the storage units for storage therein.

3. The method of claim 1 further comprises:

for a second change of the plurality of changes;

identifying, by the computing device, a second one or more nodes of the plurality of affected nodes for which the second change is applicable; and

updating, by the computing device, each of the second one or more nodes based on the change to produce second updated one or more nodes.

4. The method of claim 1, wherein the plurality of nodes of the index structure comprises:

a root index node;

a plurality of leaf nodes; and

a plurality of intervening index nodes.

5. The method of claim 1, wherein the identifying the one or more nodes of the plurality of affected nodes for which the change is applicable comprises:

identifying, by the computing device, a first particular index structure of the plurality of index structures based on a pre-change data element of a data object;

identifying, by the computing device, a first node of the plurality of nodes of the first particular index structure based on the pre-change data element;

identifying, by the computing device, a second particular index structure of the plurality of index structures based on a post-change data element of a data object; and

identifying, by the computing device, a second node of the plurality of nodes of the second particular index structure based on the post-change data element.

6. A computing device of a dispersed storage network (DSN), the computing device comprises:

an interface;

memory; and

a processing module operably coupled to the memory and the interface, wherein the processing module is operable to;

queue a plurality of changes to a hierarchical index construct that includes a plurality of index structures, wherein an index structure of the plurality of index structures includes a plurality of nodes, wherein a node of the plurality of nodes is dispersed storage error encoded to produce a set of encoded data slices, and wherein the set of encoded data slices is stored in a set of storage units of the DSN;

when triggered, determine a plurality of affected nodes of pluralities of nodes of the plurality of index structures based on the plurality of changes queued when triggered;

retrieve a threshold number of encoded data slices for each of the plurality of affected nodes from storage units of the DSN;

dispersed storage error decode the threshold number of encoded data slices for each of the plurality of affected nodes to produce the plurality of affected nodes; and

for a change of the plurality of changes;

identify one or more nodes of the plurality of affected nodes for which the change is applicable; and

update each of the one or more nodes based on the change to produce updated one or more nodes.

7. The computing device of claim 6, wherein the processing module is further operable to:

dispersed storage error encode the updated one or more nodes to produce a threshold number of updated encoded data slices for each of the updated one or more nodes; and

send the threshold number of updated encoded data slices for each of the updated one or more nodes to the storage units for storage therein.

8. The computing device of claim 6, wherein the processing module is further operable to:

for a second change of the plurality of changes;

identify a second one or more nodes of the plurality of affected nodes for which the second change is applicable; and

update each of the second one or more nodes based on the change to produce second updated one or more nodes.

9. The computing device of claim 6, wherein the plurality of nodes of the index structure comprises:

a root index node;

a plurality of leaf nodes; and

a plurality of intervening index nodes.

10. The computing device of claim 6, wherein the processing module is operable to identify the one or more nodes of the plurality of affected nodes for which the change is applicable by:

identifying a first particular index structure of the plurality of index structures based on a pre-change data element of a data object;

identifying a first node of the plurality of nodes of the first particular index structure based on the pre-change data element;

identifying a second particular index structure of the plurality of index structures based on a post-change data element of a data object; and

identifying a second node of the plurality of nodes of the second particular index structure based on the post-change data element.

11. A computer readable memory comprises:

a first memory that stores operational instructions that, when executed by a computing device of a dispersed storage network (DSN), causes the computing device to;

queue a plurality of changes to a hierarchical index construct that includes a plurality of index structures, wherein an index structure of the plurality of index structures includes a plurality of nodes, wherein a node of the plurality of nodes is dispersed storage error encoded to produce a set of encoded data slices, and wherein the set of encoded data slices is stored in a set of storage units of the DSN;

when triggered, determine a plurality of affected nodes of pluralities of nodes of the plurality of index structures based on the plurality of changes queued when triggered;

retrieve a threshold number of encoded data slices for each of the plurality of affected nodes from storage units of the DSN;

dispersed storage error decode the threshold number of encoded data slices for each of the plurality of affected nodes to produce the plurality of affected nodes; and

for a change of the plurality of changes;

identify one or more nodes of the plurality of affected nodes for which the change is applicable; and

update each of the one or more nodes based on the change to produce updated one or more nodes.

12. The computer readable memory of claim 11, wherein the first memory further stores operational instructions that, when executed by the computing device, causes the computing device to:

dispersed storage error encode the updated one or more nodes to produce a threshold number of updated encoded data slices for each of the updated one or more nodes; and

send the threshold number of updated encoded data slices for each of the updated one or more nodes to the storage units for storage therein.

13. The computer readable memory of claim 11, wherein a second memory that stores operational instructions that, when executed by the computing device, causes the computing device to:

for a second change of the plurality of changes;

identify a second one or more nodes of the plurality of affected nodes for which the second change is applicable; and

update each of the second one or more nodes based on the change to produce second updated one or more nodes.

14. The computer readable memory of claim 11, wherein the plurality of nodes of the index structure comprises:

a root index node;

a plurality of leaf nodes; and

a plurality of intervening index nodes.

15. The computer readable memory of claim 11, wherein the first memory further stores operational instructions that, when executed by the computing device, causes the computing device to identify the one or more nodes of the plurality of affected nodes for which the change is applicable by:

identifying a first particular index structure of the plurality of index structures based on a pre-change data element of a data object;

identifying a first node of the plurality of nodes of the first particular index structure based on the pre-change data element;

identifying a second particular index structure of the plurality of index structures based on a post-change data element of a data object; and

identifying a second node of the plurality of nodes of the second particular index structure based on the post-change data element.