Implementing hierarchical availability domain aware replication policies

• US 10,802,749 B2
• Filed: 05/29/2019
• Issued: 10/13/2020
• Est. Priority Date: 08/05/2016
• Status: Active Grant

• Current Assignee: Nutanix Incorporated
• Original Assignee: Nutanix Incorporated
• Inventors: Mahmood, Mohammad, Menon, Anoop, Thennaram Vakkayil, Ashwin, Madanala, Sandeep Kumar, Shukla, Shubham, Cheah, Chern Yih
• Primary Examiner(s): Ly, Anh Vu H
• Application Number:
  US16/425,022
• Publication Number:
  US 20190278483A1
• Time in Patent Office: 503 Days
• Field of Search: None
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• 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

A method commences upon accessing a set of data items that describe computing nodes to be organized into failure-tolerant configuration. The failure-tolerant configuration is characterized by system availability characteristics such as a replication factor and such as a hierarchical distribution of computing nodes. Characteristics of the topology include boundaries that define two or more hierarchically-related availability domain levels. Computing nodes are situated within these boundaries. Instances of a target hierarchical availability domain level are sorted, and instances of a hierarchically lower availability domain level are also sorted to form a multi-level sort order of computing nodes. Computing entities are mapped onto the computing nodes by observing the multi-level sort order.

Claims

1. A method in a computing cluster having a plurality of computing nodes distributed within two or more hierarchical availability domains:

receiving a replication factor requirement for a computing entity in the computing cluster, the replication factor requirement comprising an integer of at least two and indicating a number of copies of the computing entity to be replicated in the computing cluster;

receiving a target hierarchical availability domain level, the target hierarchical availability domain level indicating a particular level of the hierarchical availability domains;

forming a multi-level sort order for the plurality of computing nodes that are in the target hierarchical availability domain level and also in a hierarchically lower availability domain level; and

mapping a computing entity to the computing cluster to satisfy the replication factor requirement, wherein the computing entity is mapped according to the multi-level sort order.

2. The method of claim 1, wherein the mapping of the computing entity onto the plurality of computing nodes achieves the replication factor requirement at the target hierarchical availability domain level and at the hierarchically lower availability domain level.

3. The method of claim 1, wherein the mapping of the computing entity onto the plurality of computing nodes achieves the replication factor requirement at a further level that is lower than the hierarchically lower availability domain level.

4. The method of claim 1, wherein the replication factor requirement comprises a number of replicas of the computing entity.

5. The method of claim 4, wherein the number of replicas of the computing entity are distributed across at least two different ones of the hierarchical availability domains.

6. The method of claim 1, wherein at least one computing entity corresponds to a ring node that comprise metadata.

7. The method of claim 1, wherein at least one computing entity corresponds to a replicated data extent.

8. The method of claim 1, wherein at least one computing entity corresponds to a server.

9. The method of claim 1, wherein a first node of the target hierarchical availability domain is connected to a first power supply and a second node of the hierarchically lower availability domain is connected to a second power supply, and wherein the first power supply and the second power supply are different.

10. The method of claim 1, further comprising, detecting a failure event that affects at least one of the nodes from within one of the hierarchical availability domains.

11. The method of claim 1, wherein the target hierarchical availability domain level is at least one of, a site level, a rack level, or a block level.

12. The method of claim 1, wherein the multi-level sort order is formed by forming a first level sort key based on a first number of nodes in the target hierarchical availability domain level, and by forming a second level sort key based on a second number of nodes in the hierarchically lower availability domain level.

13. A non-transitory computer readable medium having stored thereon a sequence of instructions which, when stored in memory and executed by one or more processors causes the one or more processors to perform a set of acts in a computing cluster having a plurality of computing nodes distributed within two or more hierarchical availability domains, the set of acts comprising:

receiving a replication factor requirement for a computing entity in the computing cluster, the replication factor requirement comprising an integer of at least two and indicating a number of copies of the computing entity to be replicated in the computing cluster;

receiving a target hierarchical availability domain level, the target hierarchical availability domain level indicating a particular level of the hierarchical availability domains;

forming a multi-level sort order for the plurality of computing nodes that are in the target hierarchical availability domain level and also in a hierarchically lower availability domain level; and

mapping a computing entity to the computing cluster to satisfy the replication factor requirement, wherein the computing entity is mapped according to the multi-level sort order.

14. The non-transitory computer readable medium of claim 13, wherein the mapping of the computing entity onto the nodes achieves the replication factor requirement at the target hierarchical availability domain level and at the hierarchically lower availability domain level.

15. The non-transitory computer readable medium of claim 13, wherein the mapping of the computing entity onto the nodes achieves the replication factor requirement at a further level that is lower than the hierarchically lower availability domain level.

16. The non-transitory computer readable medium of claim 13, wherein the replication factor requirement comprises a number of replicas of the computing entity.

17. The non-transitory computer readable medium of claim 16, wherein the number of replicas of the computing entity are distributed across at least two different ones of the hierarchical availability domains.

18. The non-transitory computer readable medium of claim 16, wherein at least one computing entity corresponds to a ring node that comprise metadata.

19. A system comprising:

a storage medium having stored thereon a sequence of instructions; and

one or more processors that execute the instructions to cause the one or more processors to perform a set of acts in a computing cluster having a plurality of computing nodes distributed within two or more hierarchical availability domains, the set of acts comprising,

receiving a replication factor requirement for a computing entity in the computing cluster, the replication factor requirement comprising an integer of at least two and indicating a number of copies of the computing entity to be replicated in the computing cluster;

receiving a target hierarchical availability domain level, the target hierarchical availability domain level indicating a particular level of the hierarchical availability domains;

forming a multi-level sort order for the plurality of computing nodes that are in the target hierarchical availability domain level and also in a hierarchically lower availability domain level; and

mapping a computing entity to the computing cluster to satisfy the replication factor requirement, wherein the computing entity is mapped according to the multi-level sort order.

20. The system of claim 19, wherein the mapping of the computing entity onto the nodes achieves the replication factor requirement at the target hierarchical availability domain level and at the hierarchically lower availability domain level.