Data updates in distributed system with data coherency

• US 9,430,541 B1
• Filed: 04/29/2009
• Issued: 08/30/2016
• Est. Priority Date: 04/29/2009
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Johnson, Archna Kalra, Vohra, Madhumita, Powell, Paul
• Primary Examiner(s): Gofman, Alex
• Assistant Examiner(s): Gurmu, Muluemebet
• Application Number:
  US12/432,570
• Time in Patent Office: 2,680 Days
• Field of Search: 707/999.201, 707/704, 707/636, 707/620, 707/623
• US Class Current: 1/1
• 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

Abstract

Updating data in a distributed system, in which a data coordinator receives a proposed change to a data element, locks the data element, and sends an invalidation command to nodes in the distributed system. If all nodes acknowledge the invalidation command, the data coordinator updates the data element locally and unlocks the data element. If not all nodes acknowledge the invalidation command, the data coordinator terminates the proposed change and unlocks the data element. Each node that invalidated the data element requests the data element. The data coordinator returns its current value. If the value is changed, all nodes request and receive the update. If a node did not invalidate, it will not request an update, but the value will not have changed so all requesting nodes receive the previous value. Thus, all nodes have the same value for the data element and consistency is maintained throughout the system.

Claims

1. A method comprising:

receiving by a device incorporating a data coordinator a proposed change to a data element of a distributed system, the distributed system having multiple nodes storing a copy of the data element, each node coupled to, and in communication with, the data coordinator;

locking the data element at the device to prevent access to the data element in response to receiving the proposed change;

sending, after locking the data element at the device, an invalidation of the data element to the nodes of the distributed system storing a copy of the data element to invalidate copies of the data element stored at the nodes;

receiving, by the device, any acknowledgements of the invalidation sent by the nodes storing a copy of the data element;

updating the data element in accordance with the proposed change if all nodes in the distributed system storing a copy of the data element acknowledge the invalidation of the data element, otherwise,

terminating the proposed change to the data element to prevent the proposed change from being made, including maintaining an unchanged value of the data element, wherein the updating the data element if all nodes acknowledge the invalidation otherwise terminating the proposed change prevents valid data from becoming inconsistent across the nodes,

the updated or unchanged data element then being a current, valid value of the data element; and

unlocking the data element after either updating the data element or terminating the proposed change to the data element to allow access to the data element.

2. The method of claim 1, wherein receiving the proposed change comprises:

receiving the proposed change at a central management entity of the distributed system, and wherein sending the invalidation comprises sending the invalidation from the central management entity to the nodes of the distributed system.

3. The method of claim 1, wherein receiving the proposed change comprises:

receiving the proposed change at one node of the distributed system, and wherein sending the invalidation comprises sending the invalidation from the one node of the distributed system to the other nodes of the distributed system.

4. The method of claim 3, wherein the database is a replicated database, and wherein receiving the proposed change comprises receiving the proposed change at a data coordinator on the one node;

and wherein sending the invalidation comprises sending the invalidation to the other nodes from the data coordinator of the one node.

5. The method of claim 1, wherein the distributed system comprises a cluster of caches, where each cache of the cluster is a node of the distributed system.

6. The method of claim 1, wherein locking the data element comprises one or more of listing the data element in a lock table, adding a lock bit to the data element, changing a value of a field of the data element to indicate the data element is locked, or modifying a state of a reference representing the data element.

7. The method of claim 1, wherein unlocking the data element comprises one or more of removing the data element from a lock table, removing a lock bit from the data element, changing a value of a field of the data element to indicate the data element is unlocked, or modifying a state of a reference representing the data element.

8. The method of claim 1, wherein sending the invalidation to the nodes comprises:

sending a request to each node to cause each node to mark a copy of the data element at the node as invalid, and cause the node to request the data element prior to subsequent access to the data element at the node.

9. The method of claim 1, wherein terminating the proposed change further comprises:

allowing the data element to remain invalid at any node that invalidated the data element, until the node requests a synchronization of the data element, instead of pushing a synchronization of the data element from the data coordinator.

10. The method of claim 1, further comprising:

receiving a request for the data element from a node that invalidated a local copy of the data element; and

sending the current value of the data element to the node.

11. An apparatus comprising:

a storage device that stores a distributed database in a distributed system, the distributed database to store a data element, the distributed system having a network of multiple nodes that store a copy of the data element, each node coupled to, and in communication with, the data coordinator; and

a data coordinator to

receive a request to modify the data element of the distributed system,

lock the data element at the device to prevent access to the data element in response to receiving the proposed change,

send, after locking the data element at the device, an invalidation of the data element to the nodes of the distributed system storing a copy of the data element to invalidate copies of the data element stored at the nodes,

receive by the device zero or more acknowledgements of the invalidation by the nodes storing a copy of the data element,

update the data element in accordance with the requested modification if all nodes in the distributed system storing a copy of the data element acknowledge the invalidation of the data element, otherwise, terminate the requested modification to the data element to prevent the proposed change from being made, including maintaining an unchanged value of the data element, wherein the updating the data element if all nodes acknowledge the invalidation otherwise terminating the proposed change prevents valid data from becoming inconsistent across the nodes, the updated or unchanged data element then being a current, valid value of the data element in the database, and

unlock the data element after either updating the data element or terminating the proposed change to the data element to make the data element available for access.

12. The apparatus of claim 11, wherein the apparatus comprises a central management entity of the distributed system, and wherein the data coordinator is to send the invalidation to cohort nodes of the distributed system.

13. The apparatus of claim 11, wherein the apparatus comprises one node of the distributed system, and wherein the data coordinator is to send the invalidation to the other nodes of the distributed system.

14. The apparatus of claim 11, wherein the distributed system comprises a cluster of cache devices, where each cache device of the cluster is a node of the distributed system.

15. The apparatus of claim 11, wherein the data coordinator is to send a request to each node to cause each node to mark a copy of the data element at the node as invalid, the request to cause the node to request the data element prior to subsequent use of the data element at the node.

16. The apparatus of claim 11, wherein the data coordinator is to terminate the proposed change, including allowing the data element to remain invalid at any node that invalidated the data element, until the node requests a synchronization of the data element, instead of pushing a synchronization of the data element.

17. The apparatus of claim 11, wherein the data coordinator further receives a request from a node that invalidated the data element for the data element, and sends the current value of the data element to the node.

18. An article of manufacture comprising a computer-readable storage medium having instructions stored thereon, which when executed, cause a processor to:

receive at a device incorporating a data coordinator a proposed change to a data element of a distributed system, the distributed system having multiple nodes storing a copy of the data element, each node coupled to, and in communication with, the data coordinator;

lock the data element at the device to prevent access to the data element in response to receiving the proposed change;

send, after locking the data element at the device, an invalidation of the data element to the nodes of the distributed system storing a copy of the data element to invalidate copies of the data element stored at the nodes;

receive by the device zero or more acknowledgements of the invalidation by the nodes storing a copy of the data element;

update the data element in accordance with the proposed change if all nodes in the distributed system storing a copy of the data element acknowledge the invalidation of the data element, otherwise,

terminate the proposed change to the data element to prevent the proposed change from being made, including maintaining an unchanged value of the data element, wherein the updating the data element if all nodes acknowledge the invalidation otherwise terminating the proposed change prevents valid data from becoming inconsistent across the nodes,

the updated or unchanged data element then being a current, valid value of the data element; and

unlock the data element after either updating the data element or terminating the proposed change to the data element to allow access to the data element.

19. The article of manufacture of claim 18, wherein the instructions for receiving the proposed change comprises instructions for receiving the proposed change at one node of the distributed system, and wherein the instructions for sending the invalidation comprises instructions for sending the invalidation from the one node of the distributed system to the other nodes of the distributed system.

20. The article of manufacture of claim 19, wherein the database is a replicated database, and wherein the instructions for receiving the proposed change comprises instructions for receiving the proposed change at a data coordinator on the one node;

and wherein the instructions for sending the invalidation comprises instructions for sending the invalidation to the other nodes from the data coordinator of the one node.

21. The article of manufacture of claim 18, wherein the instructions for sending the invalidation to the nodes comprises instructions for sending a request to each node to cause each node to mark a copy of the data element at the node as invalid, and cause the node to request the data element prior to subsequent access to the data element at the node.

22. The article of manufacture of claim 18, further comprising instructions for receiving a request from a node that invalidated the data element for the data element, and sending the current value of the data element to the node.