ALLOCATING DELEGATES FOR MODIFICATION OF AN INDEX STRUCTURE

• US 20170126805A1
• Filed: 10/26/2016
• Published: 05/04/2017
• Est. Priority Date: 10/30/2015
• Status: Abandoned Application

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Dhuse, Greg R., Gray, Adam M., Horan, Scott M., Khadiwala, Ravi V., Reid, Tyler K., Scholl, Daniel J., Volvovski, Ilya
• Application Number:
  US15/334,549
• Publication Number:
  US 20170126805A1
• Time in Patent Office: Days
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 11/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 12/0646 Configuration or reconfiguration
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency
• CPC Class Codes: G06F 2212/1008 Correctness of operation, e.g. memory ordering
• CPC Class Codes: G06F 2212/657 Virtual address space management
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0622 in relation to access
• CPC Class Codes: G06F 3/0623 in relation to content
• CPC Class Codes: G06F 3/0635 by changing the path, e.g. traffic rerouting, path reconfiguration
• 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 9/4856 resumption being on a different machine, e.g. task migration, virtual machine migration G06F9/5088 takes precedence
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• CPC Class Codes: H04L 41/0816 : the condition being an adaptation, e.g. in response to network events
• CPC Class Codes: H04L 47/803 : Application aware
• CPC Class Codes: H04L 63/0428 : wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/0457 : wherein the sending and receiving network entities apply dynamic encryption, e.g. stream encryption cryptographic mechanisms or cryptographic arrangements for stream encryption H04L9/065
• CPC Class Codes: H04L 63/06 : for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 63/068 : using time-dependent keys, e.g. periodically changing keys cryptographic mechanisms or cryptographic arrangements for controlling usage of secret information H04L9/088
• CPC Class Codes: H04L 63/08 : for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 63/101 : Access control lists [ACL]
• 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]
• CPC Class Codes: H04L 9/0861 : Generation of secret information including derivation or calculation of cryptographic keys or passwords
• CPC Class Codes: H04L 9/14 : using a plurality of keys or algorithms

Abstract

A method to assign delegate devices for updating a hierarchical index structure includes determining a number of delegate devices to assign for updating the hierarchical index structure, wherein the hierarchical index structure is a self-balancing structure. The method further includes determining a node layer of the hierarchical index structure that has at least an equivalent number of nodes as the number of delegate devices. The method further includes, for the node layer, assigning each delegate device of the number of delegate devices a unique one or more nodes of the node layer and corresponding child nodes thereof. The method further includes generating a list of delegate device responsibilities based on the assigning.

Claims

1. A method for a computing device to assign delegate devices for updating a hierarchical index structure that is usable for identifying data stored in memory of a dispersed storage network (DSN), the method comprises:

determining a number of delegate devices to assign for updating the hierarchical index structure, wherein the hierarchical index structure is a self-balancing structure;

identifying a node layer of the hierarchical index structure that has at least an equivalent number of nodes as the number of delegate devices;

for the node layer, assigning each delegate device of the number of delegate devices a unique one or more nodes of the node layer and corresponding child nodes thereof; and

generating a list of delegate device responsibilities based on the assigning.

2. The method of claim 1, wherein a delegate device of the number of delegate devices comprises one or more of:

a computing device of the DSN;

a managing unit of the DSN;

a storage unit of the memory of the DSN;

an index update module; and

an integrity unit of the DSN.

3. The method of claim 1, wherein the determining the number of delegate devices comprises one or more of:

accessing a list of devices of the DSN designated as the delegate devices;

implementing a query and response protocol with a plurality of devices of the DSN; and

receiving a message that identifies the number of delegate devices.

4. The method of claim 1, wherein the determining the number of delegate devices comprises:

determining a size of the hierarchical index structure;

determining a use volume of the hierarchical index structure; and

determining the number of delegate devices based on the size and use volume of the hierarchical index structure.

5. The method of claim 1 further comprises:

sending the list of delegate device responsibilities to one or more of;

devices of the DSN and the delegate devices.

6. The method of claim 1, wherein the assigning comprises:

when the number of nodes in the node layer equals the number of delegate devices;

assigning a first delegate device of the number of delegate devices to a first node of the number of nodes; and

assigning a second delegate device of the number of delegate devices to a second node of the number of nodes.

7. The method of claim 1, wherein the assigning comprises:

when the number of nodes in the node layer is greater than the number of delegate devices;

identifying additional delegate devices to increase the number of delegate devices to substantially match the number of nodes to produce an updated number of delegate devices;

assigning a first delegate device of the updated number of delegate devices to a first node of the number of nodes; and

assigning a second delegate device of the updated number of delegate devices to a second node of the number of nodes.

8. The method of claim 1, wherein the assigning comprises:

when the number of nodes in the node layer is greater than the number of delegate devices;

identifying a first delegate device of the number of delegate devices having a higher level of processing capabilities than other delegate devices of the number of delegate devices;

assigning each delegate device of the other delegate devices one node of the number of nodes; and

assigning the first delegate device at least two nodes of remaining nodes of the number of nodes, wherein the remaining nodes corresponds to a total number of nodes in the number of nodes less a number of nodes individually assigned to the other delegate devices.

9. The method of claim 1 further comprises:

determining that a new node is added to the number of nodes of the node layer;

determining whether to assign the new node to one of the number of delegate devices or to add a new delegate device to the number of delegate devices;

when determined to assign the new node to one of the number of delegate devices, selecting the one of the number of delegate devices based on the one of the number of delegate devices having a higher level of processing capabilities than other delegate devices of the number of delegate devices; and

when determined to add the new delegate device, selecting a device of the DSN to function as the new delegate device and assigning the new node to the new delegate device.

10. A computing device of a dispersed storage network (DSN) comprises:

a network interface;

memory; and

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

determine a number of delegate devices to assign for updating a hierarchical index structure, wherein the hierarchical index structure is a self-balancing structure;

identify a node layer of the hierarchical index structure that has at least an equivalent number of nodes as the number of delegate devices;

for the node layer, assign each delegate device of the number of delegate devices a unique one or more nodes of the node layer and corresponding child nodes thereof; and

generate a list of delegate device responsibilities based on the assigning.

11. The computing device of claim 10, wherein a delegate device of the number of delegate devices comprises one or more of:

a computing device of the DSN;

a managing unit of the DSN;

a storage unit of the memory of the DSN;

an index update module; and

an integrity unit of the DSN.

12. The computing device of claim 10, wherein the processing module is further operable to determine the number of delegate devices by one or more of:

accessing a list of devices of the DSN designated as the delegate devices;

implementing a query and response protocol with a plurality of devices of the DSN; and

receiving a message that identifies the number of delegate devices.

13. The computing device of claim 10, wherein the processing module is further operable to determine the number of delegate devices comprises:

determining a size of the hierarchical index structure;

determining a use volume of the hierarchical index structure; and

determining the number of delegate devices based on the size and use volume of the hierarchical index structure.

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

send, via the network interface, the list of delegate device responsibilities to one or more of;

devices of the DSN and the delegate devices.

15. The computing device of claim 10, wherein the processing module is further operable to assign by:

when the number of nodes in the node layer equals the number of delegate devices;

assigning a first delegate device of the number of delegate devices to a first node of the number of nodes; and

assigning a second delegate device of the number of delegate devices to a second node of the number of nodes.

16. The computing device of claim 10, wherein the processing module is further operable to assign by:

when the number of nodes in the node layer is greater than the number of delegate devices;

identifying additional delegate devices to increase the number of delegate devices to substantially match the number of nodes to produce an updated number of delegate devices;

assigning a first delegate device of the updated number of delegate devices to a first node of the number of nodes; and

assigning a second delegate device of the updated number of delegate devices to a second node of the number of nodes.

17. The computing device of claim 10, wherein the processing module is further operable to assign by:

when the number of nodes in the node layer is greater than the number of delegate devices;

identifying a first delegate device of the number of delegate devices having a higher level of processing capabilities than other delegate devices of the number of delegate devices;

assigning each delegate device of the other delegate devices one node of the number of nodes; and

assigning the first delegate device at least two nodes of remaining nodes of the number of nodes, wherein the remaining nodes corresponds to a total number of nodes in the number of nodes less a number of nodes individually assigned to the other delegate devices.

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

determine that a new node is added to the number of nodes of the node layer;

determine whether to assign the new node to one of the number of delegate devices or to add a new delegate device to the number of delegate devices;

when determined to assign the new node to one of the number of delegate devices, select the one of the number of delegate devices based on the one of the number of delegate devices having a higher level of processing capabilities than other delegate devices of the number of delegate devices; and

when determined to add the new delegate device, select a device of the DSN to function as the new delegate device and assigning the new node to the new delegate device.