Implementing availability domain aware replication policies

• US 10,698,780 B2
• Filed: 08/05/2016
• Issued: 06/30/2020
• Est. Priority Date: 08/05/2016
• Status: Active Grant

• Current Assignee: Nutanix Incorporated
• Original Assignee: Nutanix Incorporated
• Inventors: Mahmood, Mohammad, Liao, Roger Sean
• Primary Examiner(s): Ly, Anh Vu H
• Application Number:
  US15/230,147
• Publication Number:
  US 20200034257A1
• Time in Patent Office: 1,425 Days
• Field of Search: None
• CPC Class Codes: G06F 11/008 Reliability or availability analysis
• CPC Class Codes: G06F 11/1425 by reconfiguration of node membership
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064
• 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/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Systems for distributed data storage. A method commences upon accessing a set of data items that describe computing nodes to be organized into a ring topology. The ring topology and distributed data storage policies are characterized by quantitative failure-resilient characteristics such as a replication factor. Various characteristics of the topology serve to bound two or more availability domains of the ring into which the computing nodes can be mapped. A set of quantitative values pertaining to respective quantitative failure-resilient characteristics are used for enumerating candidate ring topologies where the computing nodes are mapped into the availability domains. Using the quantitative failure-resilient characteristics, alternative candidate ring topologies are evaluated so as to determine a configuration score for candidate ring topologies. A candidate ring topology is configured based on a computed configuration score surpassing a threshold score. When a failure event is detected, the ring is reevaluated, remapped, and considered for reconfiguration.

Claims

1. A method comprising:

accessing a data item describing a plurality of computing nodes in a distributed system, the plurality of computing nodes to be organized into a ring topology, wherein the ring topology exhibits a quantitative failure-resilient characteristic;

identifying two or more availability domains into which the plurality of computing nodes can be mapped;

receiving a metric that comprises a quantitative value pertaining to the quantitative failure-resilient characteristic;

enumerating a plurality of candidate ring topologies, wherein the plurality of computing nodes is mapped into the two or more availability domains;

evaluating, using the quantitative failure-resilient characteristic, at least some of the plurality of candidate ring topologies to determine a configuration score for a set of scored candidate ring topologies; and

selecting a scored candidate ring topology from the set of scored candidate ring topologies based at least in part on the configuration score surpassing a configuration threshold score.

2. The method of claim 1, further comprising detecting a failure event that affects a node of the plurality of computing nodes from within an availability domain.

3. The method of claim 2, further comprising performing a second enumeration of remedial ring topologies that do not include the node of the plurality of computing nodes from within the availability domain.

4. The method of claim 1, further comprising receiving, over a network, one or more node topology attributes describing at least in part one or more availability domains in the distributed system, the one or more availability domains associated with a respective portion of the plurality of computing nodes, wherein a selected replication configuration is selected based at least in part on the one or more availability domains.

5. The method of claim 4, wherein receiving the selected replication configuration or the one or more node topology attributes is responsive to one or more node topology changes.

6. The method of claim 4, wherein the one or more node topology attributes comprise at least one of a node identifier, an availability domain identifier, a site identifier, a host identifier, an IP address, or a node state.

7. The method of claim 1, wherein an individual one of the two or more availability domains is a node, or a block, or a host, or a site, or an appliance, or a rack, or a data center.

8. A non-transitory computer readable medium having stored thereon a sequence of instructions which, when stored in memory and executed by a processor causes the processor to perform a set of acts, the set of acts comprising:

accessing a data item describing a plurality of computing nodes in a distributed system, the plurality of computing nodes to be organized into a ring topology, wherein the ring topology exhibits a quantitative failure-resilient characteristic;

identifying two or more availability domains into which the plurality of computing nodes can be mapped;

receiving a metric that comprises a quantitative value pertaining to the quantitative failure-resilient characteristic;

enumerating a plurality of candidate ring topologies, wherein the plurality of computing nodes is mapped into the two or more availability domains;

evaluating, using the quantitative failure-resilient characteristic, at least some of the plurality of candidate ring topologies to determine a configuration score for a set of scored candidate ring topologies; and

selecting a scored candidate ring topology from the set of scored candidate ring topologies based at least in part on the configuration score surpassing a configuration threshold score.

9. The computer readable medium of claim 8, further comprising instructions which, when stored in the memory and executed by the processor, causes the processor to perform acts of receiving, over a network, one or more node topology attributes describing at least in part one or more availability domains, the one or more availability domains associated with a respective portion of the plurality of computing nodes, wherein a selected replication configuration is selected based at least in part on the one or more availability domains.

10. The computer readable medium of claim 9, wherein the selected replication configuration comprises at least one of a node identifier, a token identifier, an IP address, a data center, a rack identifier, a predecessor node identifier, or a successor node identifier.

11. The computer readable medium of claim 9, wherein one or more neighboring replication configurations or the selected replication configuration comprises a ring structure.

12. The computer readable medium of claim 11, wherein at least two of a current replication configuration, the one or more neighboring replication configurations, or the selected replication configuration differ by a changed node position.

13. The computer readable medium of claim 9, wherein receiving the selected replication configuration or the one or more node topology attributes is responsive to one or more node topology changes.

14. The computer readable medium of claim 9, wherein the one or more node topology attributes comprise at least one of a node identifier, an availability domain identifier, a site identifier, a host identifier, an IP address, or a node state.

15. The computer readable medium of claim 8, wherein the metric is based at least in part on at least one of a replication factor, a configuration score, a node score, a maximum consecutive node score, a transition score, a block aware score, a rack aware score, or a heuristic function.

16. The computer readable medium of claim 15, wherein the heuristic function is at least one of an admissible heuristic function or a non-admissible heuristic function.

17. The computer readable medium of claim 8, wherein the set of scored candidate ring topologies is based at least in part on at least one of an A* search algorithm, or a breadth first search algorithm, or a best first search algorithm, or a greedy approach, or a pruning technique, or any combination thereof.

18. The computer readable medium of claim 8, further comprising instructions which, when stored in the memory and executed by the processor, causes the processor to perform acts of detecting a failure event that affects a node of the plurality of computing nodes from within an availability domain.

19. The computer readable medium of claim 18, further comprising instructions which, when stored in the memory and executed by the processor, causes the processor to perform acts of performing a second enumeration of remedial ring topologies that do not include the node of the plurality of computing nodes from within the availability domain.

20. The computer readable medium of claim 8, wherein an individual one of the two or more availability domains is a node, or a block, or a host, or a site, or an appliance, or a rack, or a data center.

23. The system of claim 19, wherein an individual one of the two or more availability domains is a node, or a block, or a host, or a site, or an appliance, or a rack, or a data center.

21. A system:

a non-transitory storage medium having stored thereon a sequence of instructions; and

a processor or processors that execute the sequence of instructions to cause the processor or processors to perform a set of acts, the set of acts comprising;

accessing a data item describing a plurality of computing nodes in a distributed system, the plurality of computing nodes to be organized into a ring topology, wherein the ring topology exhibits a quantitative failure-resilient characteristic;

identifying two or more availability domains into which the plurality of computing nodes can be mapped;

receiving a metric that comprises a quantitative value pertaining to the quantitative failure-resilient characteristic;

enumerating a plurality of candidate ring topologies, wherein the plurality of computing nodes is mapped into the two or more availability domains;

evaluating, using the quantitative failure-resilient characteristic, at least some of the plurality of candidate ring topologies to determine a configuration score for a set of scored candidate ring topologies; and

selecting a scored candidate ring topology from the set of scored candidate ring topologies based at least in part on the configuration score surpassing a configuration threshold score.

22. The system of claim 21, wherein the set of acts further comprise detecting a failure event that affects a node of the plurality of computing nodes from within an availability domain.