Implementing availability domain aware replication policies
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.
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.
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.
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.