Fallback delegates for modification of an index structure

• US 10,176,044 B2
• Filed: 10/26/2016
• Issued: 01/08/2019
• Est. Priority Date: 10/30/2015
• Status: Active Grant

• 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., Resch, Jason K., Scholl, Daniel J., Volvovski, Ilya
• Primary Examiner(s): Lottich, Joshua P
• Application Number:
  US15/334,604
• Publication Number:
  US 20170123948A1
• Time in Patent Office: 804 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 includes determining that a primary delegate device is unavailable. The method continues by identifying a fallback delegate device for changing a node of a hierarchical index structure using a deterministic function. The deterministic function includes performing a first modification of global namespace address of the unavailable primary delegate device to produce a first modified address identifier. The deterministic function further includes determining whether another delegate device of the plurality of delegate devices has a global namespace address corresponding to the first modified address identifier. When the global namespace address of other delegate device corresponds to the first modified address identifier, the method further includes processing a change to a node of the one or more nodes via the other delegate device as the fallback delegate device.

Claims

1. A method for execution by a device of a dispersed storage network (DSN), the method comprises:

determining that a primary delegate device is unavailable, wherein the primary delegate device is responsible for changing one or more nodes of a plurality of nodes of a hierarchical index structure, wherein the hierarchical index structure is used to identify particular data stored in the DSN and wherein the plurality of nodes includes a root index node, a plurality of index nodes, and a plurality of leaf index nodes arranged in a related hierarchical manner; and

identifying a fallback delegate device for changing the one or more nodes using a deterministic function that includes;

performing a first modification of global namespace address of the unavailable primary delegate device to produce a first modified address identifier, wherein each delegate device of a plurality of delegate devices is assigned an individual global namespace address that is partially based on location within the DSN;

determining whether another delegate device of the plurality of delegate devices has a global namespace address corresponding to the first modified address identifier; and

when the global namespace address of other delegate device corresponds to the first modified address identifier, processing a change to a node of the one or more nodes via the other delegate device as the fallback delegate device.

2. The method of claim 1 further comprises:

modifying most significant bits (MSB) of the global namespace address of the unavailable primary delegate device to produce a modified MSB; and

determining whether the MSB of the global namespace address of the other delegate device substantially matches the modified MSB; and

when the MSB of the global namespace address of the other delegate device substantially matches the modified MSB, identifying the other delegate device as the fallback delegate device for the one or more nodes.

3. The method of claim 2, wherein the individual global namespace address comprises:

the MSB corresponding to a geographic region of the DSN that is partially based on location within the DSN; and

less significant bits (LSB) corresponding to a unique identifier of a particular delegate device within the geographic region.

4. The method of claim 1, determining whether another delegate device of the plurality of delegate devices has a global namespace address corresponding to the first modified address identifier comprises at least one of:

determining that the global namespace address of the other delegate device substantially matches the first modified address identifier and determining that the other delegate device is available to become the primary delegate device; and

determining that the global namespace address of the other delegate device is a best-available match to the first modified address identifier and determining that the other delegate device is available to become the primary delegate device.

5. The method of claim 1, wherein the determining whether another delegate device of the plurality of delegate devices has a global namespace address corresponding to the first modified address identifier comprises:

identifying two other delegate devices as potential fallback delegate devices using a first pass of a modified address of the unavailable primary delegate device; and

changing the first pass modified address to the first modified address identifier to select the other delegate device from the two delegate devices.

6. The method of claim 1 further comprises:

inverting most significant bits (MSB) of the global namespace address of the unavailable primary delegate device to produce the first modified address identifier;

when the global namespace address of the other delegate device does not correspond to the first modified address identifier;

performing a second modification to the first modified address identifier to produce a second modified address identifier; and

determining that a second other delegate device of the plurality of delegate devices has a global namespace address corresponding to the second modified address identifier; and

processing a change to a node of the one or more nodes via the second other delegate device as the fallback delegate device.

7. The method of claim 6 further comprises:

when the global namespace address of the second other delegate device does not correspond to the second modified address identifier;

continuing to perform modifications of a current modified address identifier until one of the plurality of delegate devices is identified as the fallback delegate device or until the modifications have been exhausted; and

when the modifications have been exhausted, processing, by the device, the change to a node of the one or more nodes.

8. The method of claim 1, wherein the processing the change to the node of the one or more nodes via the other delegate device comprises:

sending, by the device, a request to the other delegate device regarding the change to the node of the one or more nodes;

determining, by the other delegate device, whether the other delegate device is responsible for executing the change type specific request; and

when the other delegate device is responsible for executing the request;

sending, by the other delegate device, a response message to the device indicating that the other delegate device is responsible for executing the request; and

executing, by the other delegate device, the change to the node of the one or more nodes.

9. The method of claim 8, wherein the determining whether the other delegate device is responsible for executing the change type specific request comprises:

performing the first modification of the global namespace address of the unavailable primary delegate device to produce the first modified address identifier; and

determining that the other delegate device has the global namespace address corresponding to the first modified address identifier.

10. A non-transitory computer readable memory comprises:

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

determine that a primary delegate device is unavailable, wherein the primary delegate device is responsible for changing one or more nodes of a plurality of nodes of a hierarchical index structure, wherein the hierarchical index structure is used to identify particular data stored in the DSN and wherein the plurality of nodes includes a root index node, a plurality of index nodes, and a plurality of leaf index nodes arranged in a related hierarchical manner; and

a second memory element that stores operational instructions that, when executed by the device, causes the device to;

identify a fallback delegate device for changing the one or more nodes using a deterministic function that includes;

perform a first modification of global namespace address of the unavailable primary delegate device to produce a first modified address identifier, wherein each delegate device of a plurality of delegate devices is assigned an individual global namespace address that is partially based on location within the DSN;

determine whether another delegate device of the plurality of delegate devices has a global namespace address corresponding to the first modified address identifier; and

when the global namespace address of other delegate device corresponds to the first modified address identifier, process a change to a node of the one or more nodes via the other delegate device as the fallback delegate device.

11. The non-transitory computer readable memory of claim 10, wherein the second memory element further stores operational instructions that, when executed by the device, causes the device to:

modify most significant bits (MSB) of the global namespace address of the unavailable primary delegate device to produce a modified MSB; and

determine whether the MSB of the global namespace address of the other delegate device substantially matches the modified MSB; and

when the MSB of the global namespace address of the other delegate device substantially matches the modified MSB, identify the other delegate device as the fallback delegate device for the one or more nodes.

12. The non-transitory computer readable memory of claim 11, wherein the individual global namespace address comprises:

the MSB corresponding to a geographic region of the DSN that is partially based on location within the DSN; and

less significant bits (LSB) corresponding to a unique identifier of a particular delegate device within the geographic region.

13. The non-transitory computer readable memory of claim 10, wherein the second memory element further stores operational instructions that, when executed by the device, causes the device to determine whether another delegate device of the plurality of delegate devices has the global namespace address corresponding to the first modified address identifier by at least one of:

determining that the global namespace address of the other delegate device substantially matches the first modified address identifier and determining that the other delegate device is available to become the primary delegate device; and

determining that the global namespace address of the other delegate device is a best-available match to the first modified address identifier and determining that the other delegate device is available to become the primary delegate device.

14. The non-transitory computer readable memory of claim 10, wherein the second memory element further stores operational instructions that, when executed by the device, causes the device to determine whether another delegate device of the plurality of delegate devices has the global namespace address corresponding to the first modified address identifier comprises:

identifying two other delegate devices as potential fallback delegate devices using a first pass of a modified address of the unavailable primary delegate device; and

changing the first pass modified address to the first modified address identifier to select the other delegate device from the two delegate devices.

15. The non-transitory computer readable memory of claim 10, wherein the second memory element further stores operational instructions that, when executed by the device, causes the device to:

invert most significant bits (MSB) of the global namespace address of the unavailable primary delegate device to produce the first modified address identifier;

when the global namespace address of the other delegate device does not correspond to the first modified address identifier;

perform a second modification to the first modified address identifier to produce a second modified address identifier;

determine that a second other delegate device of the plurality of delegate devices has a global namespace address corresponding to the second modified address identifier; and

process a change to a node of the one or more nodes via the second other delegate device as the fallback delegate device.

16. The non-transitory computer readable memory of claim 15, wherein the second memory element further stores operational instructions that, when executed by the device, causes the device to:

when the global namespace address of the second other delegate device does not correspond to the second modified address identifier;

continue to perform modifications of a current modified address identifier until one of the plurality of delegate devices is identified as the fallback delegate device or until the modifications have been exhausted; and

when the modifications have been exhausted, process, by the device, the change to a node of the one or more nodes.

17. The non-transitory computer readable memory of claim 10 further comprises:

the second memory element further stores operational instructions that, when executed by the device, causes the device to process the change to the node of the one or more nodes via the other delegate device by;

send a request to the other delegate device regarding the change to the node of the one or more nodes; and

a third memory element that stores operational instructions that, when executed by the other delegate device, causes the other delegate device to;

determine whether the other delegate device is responsible for executing the change type specific request; and

when the other delegate device is responsible for executing the request;

send a response message to the device indicating that the other delegate device is responsible for executing the request; and

execute the change to the node of the one or more nodes.

18. The non-transitory computer readable memory of claim 17, wherein the third memory element further stores operational instructions that, when executed by the other delegate device, causes the other delegate device to determine whether the other delegate device is responsible for executing the change type specific request by:

performing the first modification of the global namespace address of the unavailable primary delegate device to produce the first modified address identifier; and

determining that the other delegate device has the global namespace address corresponding to the first modified address identifier.