Method and system for maintaining consistency for I/O operations on metadata distributed amongst nodes in a ring structure

• US 9,772,784 B2
• Filed: 03/14/2016
• Issued: 09/26/2017
• Est. Priority Date: 08/10/2011
• Status: Active Grant

• Current Assignee: Nutanix Incorporated
• Original Assignee: Nutanix Incorporated
• Inventors: Bhardwaj, Rishi, Guturi, Venkata Ranga Radhanikanth
• Primary Examiner(s): Woo, Isaac M
• Application Number:
  US15/069,961
• Publication Number:
  US 20160196082A1
• Time in Patent Office: 561 Days
• Field of Search: 707600-899
• CPC Class Codes: G06F 16/188 Virtual file systems
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0614 Improving the reliability of storage systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• 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 for maintaining consistency for I/O operations on metadata distributed amongst a plurality of nodes forming a ring structure.

Claims

1. A method for maintaining consistency for read requests on data distributed amongst a plurality of nodes forming a ring structure, comprising:

receiving a read request for data on a first node after the first node performed a previous write operation and after a new node has been inserted into the ring structure following the first node, the new node being placed into a transition state while data values for the new node are not up to date;

identifying a first set of nodes to perform the read request for data comprises selecting the first node and one or more nodes immediately following the first node in the ring structure such that a total number of nodes in the first set is equal to a current replication factor;

upon determination that the first set of nodes include the new node in the transition state, increasing the current replication factor to establish a new replication factor; and

establishing quorum by identifying a second set of nodes based on the new replication factor.

2. The method of claim 1, wherein the new node is introduced at a location immediately following the first node identified for the previous write operation of data.

3. The method of claim 1, wherein the first set of nodes on which to perform the read request includes at least one node without a most up to date data value.

4. The method of claim 1, wherein the current replication factor is 3 and the new replication factor is 4.

5. The method of claim 4, wherein quorum is 3.

6. The method of claim 1, wherein the first set of nodes on which to perform the read request is a subset of nodes from the plurality of nodes forming the ring structure.

7. The method of claim 1, wherein any subset of the second set of nodes may be selected to establish quorum.

8. The method of claim 7, wherein at least one node of the subset of the second set of nodes includes a most up to date data value.

9. The method of claim 8, wherein establishing quorum comprises updating a data value for a node of the subset not including the most up to date data value using the at least one node of the subset that includes the most up to date data value.

10. The method of claim 1, wherein a background process updates the data values for the new node while the new node is in the transition state.

11. The method of claim 10, wherein the new node transitions from the transition state to a normal operating state once the background process completes updating the data values for the new node.

12. The method of claim 11, wherein the new replication factor reverts back to the current replication factor once the new node transitions to the normal operating state.

13. A system for maintaining consistency for read requests on data distributed amongst a plurality of nodes forming a ring structure, comprising:

a processor for;

receiving a read request for data on a first node after the first node performed a previous write operation and after a new node has been inserted into the ring structure following the first node, the new node being placed into a transition state while data values for the new node are not up to date;

identifying a first set of nodes to perform the read request for data comprises selecting the first node and one or more nodes immediately following the first node in the ring structure such that a total number of nodes in the first set is equal to a current replication factor;

upon determination that the first set of nodes include the new node in the transition state, increasing the current replication factor to establish a new replication factor; and

establishing quorum by identifying a second set of nodes based on the new replication factor.

14. The system of claim 13, wherein the new node is introduced at a location immediately following the first node identified for the previous write operation of data.

15. The system of claim 13, wherein the first set of nodes on which to perform the read request includes at least one node without a most up to date data value.

16. The system of claim 13, wherein the current replication factor is 3 and the new replication factor is 4.

17. The system of claim 16, wherein quorum is 3.

18. The system of claim 13, wherein the first set of nodes on which to perform the read request is a subset of nodes from the plurality of nodes forming the ring structure.

19. The system of claim 13, wherein any subset of the second set of nodes may be selected to establish quorum.

20. The system of claim 19, wherein at least one node of the subset of the second set of nodes includes a most up to date data value.

21. The system of claim 20, wherein establishing quorum comprises updating a data value for a node of the subset not including the most up to date data value using the at least one node of the subset that includes the most up to date data value.

22. The system of claim 13, wherein a background process updates the data values for the new node while the new node is in the transition state.

23. The system of claim 22, wherein the new node transitions from the transition state to a normal operating state once the background process completes updating the data values for the new node.

24. The system of claim 23, wherein the new replication factor reverts back to the current replication factor once the new node transitions to the normal operating state.

25. A computer program product comprising a non-transitory computer usable medium having executable code to execute a method for maintaining consistency for read requests on data distributed amongst a plurality of nodes forming a ring structure, the method comprising:

receiving a read request for data on a first node after the first node performed a previous write operation and after a new node has been inserted into the ring structure following the first node, the new node being placed into a transition state while data values for the new node are not up to date;

identifying a first set of nodes to perform the read request for data comprises selecting the first node and one or more nodes immediately following the first node in the ring structure such that a total number of nodes in the first set is equal to the current replication factor;

upon determination that the first set of nodes include the new node in the transition state, increasing the current replication factor to establish a new replication factor; and

establishing quorum by identifying a second set of nodes based on the new replication factor.

26. The computer program product of claim 25, wherein the new node is introduced at a location immediately following the first node identified for the previous write operation of data.

27. The computer program product of claim 25, wherein the first set of nodes on which to perform the read request includes at least one node without a most up to date data value.

28. The computer program product of claim 25, wherein the current replication factor is 3 and the new replication factor is 4.

29. The computer program product of claim 28, wherein quorum is 3.

30. The computer program product of claim 25, wherein the first set of nodes on which to perform the read request is a subset of nodes from the plurality of nodes forming the ring structure.

31. The computer program product of claim 25, wherein any subset of the second set of nodes may be selected to establish quorum.

32. The computer program product of claim 31, wherein at least one node of the subset of the second set of nodes includes a most up to date data value.

33. The computer program product of claim 32, wherein establishing quorum comprises updating a data value for a node of the subset not including the most up to date data value using the at least one node of the subset that includes the most up to date data value.

34. The computer program product of claim 25, wherein a background process updates the data values for the new node while the new node is in the transition state.

35. The computer program product of claim 34, wherein the new node transitions from the transition state to a normal operating state once the background process completes updating the data values for the new node.

36. The computer program product of claim 35, wherein the new replication factor reverts back to the current replication factor once the new node transitions to the normal operating state.