Systems and methods for providing distributed cache coherence

1. A method of providing cache coherence between caches in a distributed set of caching data access nodes sharing access to shared data of a data storage volume, the method comprising:

maintaining at least a portion of a directory in a first one of the access nodes, said directory storing locations of copies of the shared data among respective caches of the plurality of access nodes;

receiving, at the first access node, a data access request from a host system, said data access request identifying data of the shared data to be processed,

determining whether the first access node has the identified data stored in its cache, and if not:

(a) determining, using the portion of the directory, whether another node in the plurality of access nodes has a copy of the identified data stored in its cache;

(b) if another node does not have a copy of the identified data in its cache, then satisfying the data access request by obtaining the data from a storage device on which the shared data of the data storage volume is stored; and

(c) if another node has a copy of the identified data stored in its cache, then sending one of a share request to that node to share the identified data so that the requesting node does not have to access the identified data from storage or an invalidate request to invalidate the copy of the data stored in that node's cache,

wherein the one of a share request or the invalidate request is used to provide cache coherence between the caches;

and if the first access node has the identified data stored in its cache, then (d) satisfying the data access request using the identified data in the cache of the first access node, and (e) if the data access is a read request, then refraining from sending the share request to any of the other access nodes having a copy of the identified data as indicated by the portion of the directory,

wherein the directory is divided into chunks associated with corresponding sets of pages of the shared memory, and the portion of the directory in the first access node includes a chunk having a directory entry storing the locations of copies of the identified data among the caches of the access nodes,

and further including participating in locality-conscious directory migration by which the chunks of the directory are dynamically distributed among the access nodes, the participating including:

prior to the satisfying of the data access request, obtaining ownership of the chunk so as to enable the first access node to use the portion of the directory to determine whether another of the access nodes has a copy of the identified data, the obtaining including:

(i) sending a directory query message to one of the access nodes functioning as a global directory chunk coordinator responsible for tracking and granting ownership of the chunks of the directory, the directory query message identifying the chunk;

(ii) receiving a directory reply message from the global directory chunk coordinator identifying a current owner of the chunk; and

(iii) communicating with the identified current owner of the chunk to obtain the ownership of the chunk; and

after the satisfying of the data access request, transferring ownership of the chunk to another of the access nodes.

2. The method of claim 1 , wherein the data access request is a data read request, and wherein if none of the access nodes has a copy of the identified data stored in cache, the method further comprises:

creating a new entry in the directory identifying the requesting node as an owner of the identified data.

3. The method of claim 1 , wherein the data access request is a write request, and wherein if none of the access nodes has a copy of the identified data stored in cache, the method further comprises:

committing written data to the requesting node's cache.

4. The method of claim 1 , wherein the data access request is a write request, and wherein if one or more other nodes has a copy of the identified data stored in cache, the method further comprises:

sending an invalidate request to the other nodes that have a copy of the identified data stored in cache.

5. The method of claim 1 , wherein the data access request is an update request, and if the requesting node has a copy of the identified data stored in cache, and wherein if one or more other nodes has a copy of the identified data stored in cache, the method further comprises:

sending an invalidate request to the other nodes that have a copy of the identified data stored in cache.

6. The method of claim 1 , wherein the data access request is an update request, and if the requesting node has no copy of the identified data stored in cache, and wherein if one or more other nodes has a copy of the identified data stored in cache, the method further comprises:

sending a share-invalidate request to the node that last wrote the data; and

sending an invalidate request to the other nodes that have a copy of the identified data stored in cache.

7. The method of claim 1 , further comprising:

determining whether another node has a directory lock on the data identified by the data access request;

if no node has a directory lock on the data, granting a directory lock on the identified data to the first access node; and

if a node has a directory lock on the data, waiting for the lock to be released before granting it to the first access node.

8. The method of claim 1 , wherein an unowned directory entry is placed local to the first access node to access the corresponding data page, and wherein the first access node is given ownership of the directory entry.

9. The method of claim 1 , wherein the data access request identifies one of a page of data, a sub-page of data, or multiple pages of data.

10. The method of claim 1 , wherein the data access request is one of a data read request, a data write request and a data update request.

11. The method of claim 1 , wherein the first access node maintains the portion of the directory as a table in memory, and wherein determining includes performing a lookup in the directory table.

12. The method of claim 1 , further comprising:

placing a first copy of the set of cacheable memory pages in a local cache of the first data access node while a second copy of the set of cacheable memory pages resides in a local cache of a second data access node;

writing new data into the first copy of the set of cacheable memory pages in the local cache of the first data access node and concurrently inhibiting writing to the second copy of the set of cacheable memory pages in the local cache of the second data access node; and

after the new data is written into the first copy of the set of cacheable memory pages in the local cache of the first data access node, conveying the new data from the first data access node to the second copy of the set of cacheable memory pages in the local cache of the second data access node to directly share the new data with the second data access node prior to synchronizing the new data to a common storage resource externally coupled to the first and second data access nodes.

13. The method of claim 12 wherein a directory manager node manages a directory having page ownership entries corresponding to cacheable memory pages of the data storage network; and wherein writing the new data into the first copy of the set of cacheable memory pages in the local cache of the first data access node and concurrently inhibiting writing to the second copy of the set of cacheable memory pages in the local cache of the second data access node includes:

providing ownership of a particular page ownership entry to the first data access node and not to the second data access node, the particular page ownership entry corresponding to the set of cacheable memory pages, and

storing the new data into the first copy of the set of cacheable memory pages in the local cache of the first data access node in response to ownership of the particular page ownership entry being provided to the first data access node.

14. The method of claim 13 , further comprising:

after conveying the new data from the first data access node to the second copy of the set of cacheable memory pages in the local cache of the second data access node, transferring ownership of the particular page ownership entry of the directory from the first data access node to the second data access node to enable the second data access node to write to the second copy of the set of cacheable memory pages in the local cache of the second data access node.

15. The method of claim 1 wherein determining whether the first access node has the identified data stored in cache, and if not: determining, using the directory whether another node in the plurality of access nodes has a copy of the identified data stored in cache includes:

identifying a second data access node as having a copy of the identified data stored in cache based on performance of a directory look-up in a manner which reduces network traffic among the plurality of access nodes.

16. The method of claim 15 wherein the data access request is a read request;

wherein determining whether the first access node has the identified data stored in cache, and if not: determining, using the directory whether another node in the plurality of access nodes has a copy of the identified data stored in cache further includes: detecting, by the first data access node, a local cache miss in response to the read request; and

wherein sending one of the share request or an invalidate request includes: sending the share request exclusively to the second data access node in a point-to-point manner in response to the local cache miss, the second data access node sending the identified data directly to the host system and bypassing the first data access node in response to the share request, to reduce network traffic among the plurality of access nodes.

17. The method of claim 15 wherein the data access request is a write request;

wherein determining whether the first access node has the identified data stored in cache, and if not: determining, using the directory whether another node in the plurality of access nodes has a copy of the identified data stored in cache further includes: detecting that the host system is a sole owner of the data in response to the write request; and

wherein sending one of the share request or an invalidate request includes: sending, in response to detection that the host system is the sole owner of the data, the invalidate request exclusively to the second data access node in a point-to-point manner to invalidate the copy of the identified data stored in cache at the second data access node and reduce network traffic among the plurality of access nodes.

18. The method of claim 1 , wherein the share request and invalidate request are outgoing requests, and further comprising:

receiving incoming share requests and incoming invalidate requests from the other access nodes with respect to locally cached data of the shared data, the locally cached data being stored in the cache of the first access node;

in response to each received incoming invalidate request, invalidating the locally cached data; and

in response to each received incoming share request, sending a copy of the locally cached data to another of the access nodes identified in the share request.

19. Apparatus for use as a first access node of a distributed set of caching data access nodes sharing access to shared data of a data storage volume, comprising:

a cache;

interface circuitry providing connections to (a) a host computer, (b) a storage device on which the shared data is stored, and (c) other access nodes of the distributed set of caching data access nodes; and

a processor operative to execute instructions causing the apparatus to:

maintain at least a portion of a directory storing locations of copies of the shared data among respective caches of the access nodes;

receive a data access request from the host system identifying data of the shared data to be processed,

determine whether the identified data is stored in the cache of the first access node, and if not, to:

(a) determine, using the portion of the directory, whether another of the access nodes has a copy of the identified data stored in its cache;

(b) if another of the access nodes does not have a copy of the identified data in its cache, then satisfy the data access request by obtaining the data from the storage device; and

(c) if another of the access nodes has a copy of the identified data stored in its cache, then send one of a share request to that node to share the identified data so that the first access node does not have to access the identified data from the storage device or an invalidate request to invalidate the copy of the data stored in that node's cache, wherein the one of a share request or the invalidate request is used to provide cache coherence between the caches; and

if the identified data is stored in the cache of the first access node, then to (d) satisfy the data access request using the identified data in the cache of the first access node, and (e) if the data access is a read request, refrain from sending the share request to any of the other access nodes having a copy of the identified data as indicated by the portion of the directory,

wherein the directory is divided into chunks associated with corresponding sets of pages of the shared memory, and the portion of the directory includes a chunk having a directory entry storing the locations of copies of the identified data among the caches of the access nodes,

and wherein the instructions further cause the apparatus to participate in locality-conscious directory migration by which the chunks of the directory are dynamically distributed among the access nodes, the participating including:

prior to the satisfying of the data access request, obtaining ownership of the chunk so as to enable the first access node to use the portion of the directory to determine whether another of the access nodes has a copy of the identified data, the obtaining including:

(i) sending a directory query message to one of the access nodes functioning as a global directory chunk coordinator responsible for tracking and granting ownership of the chunks of the directory, the directory query message identifying the chunk;

(ii) receiving a directory reply message from the global directory chunk coordinator identifying a current owner of the chunk; and

(iii) communicating with the identified current owner of the chunk to obtain the ownership of the chunk; and

after the satisfying of the data access request, transferring ownership of the chunk to another of the access nodes.

20. The apparatus of claim 19 , wherein the plurality of access nodes comprises a requester node, a directory node, and a sharerthatdies node, the directory node being the first access node, and wherein the instructions further cause the apparatus to participate in the following operations performed in a failed reading of data to the requester node:

receiving at the directory node a read request message from the requestor node;

identifying, by the directory node, the sharerthatdies node among the access nodes of the system;

sending from the directory node to the sharerthatdies node a share request message;

determining by the directory node that the requester did not receive data from the sharerthatdies node; and

sending from the directory node to the requester node a read failed message;

wherein the messages are adapted to maintaining fault tolerance in the system.

21. The apparatus of claim 19 , wherein the plurality of nodes comprises a requester node, a directory node, and a pageowner node, the directory node being the first access node, and wherein the instructions further cause the apparatus to participate in the following operations performed in writing data from the requester node to the requester node cache:

receiving at the directory node a write request message from the requestor node;

determining by the directory node the pageowner node having a copy of the data;

sending from the directory node to the pageowner node an invalidate request message indicating the copy is invalid;

receiving from the pageowner node at the directory node a message in response to the invalidate request message; and

sending from the directory node to the requester node a message in response to the write request message;

wherein the messages are adapted to maintaining cache coherency between the data nodes after a writing of data to the requester node cache.

22. A computer program product comprising a non-transitory storage medium having computer instructions recorded thereon, the computer instructions being operative when executed by a computerized device to cause the computerized device to perform a method of providing cache coherence between caches in a distributed set of caching data access nodes sharing access to shared data of a data storage volume, the method including:

maintaining at least a portion of a directory storing locations of copies of the shared data among respective caches of the access nodes;

receiving a data access request from the host system identifying data of the shared data to be processed,

determining whether the identified data is stored in the cache of the first access node, and if not:

(a) determining, using the portion of the directory, whether another of the access nodes has a copy of the identified data stored in its cache;

(b) if another of the access nodes does not have a copy of the identified data in its cache, then satisfying the data access request by obtaining the data from the storage device; and

(c) if another of the access nodes has a copy of the identified data stored in its cache, then sending one of a share request to that node to share the identified data so that the first access node does not have to access the identified data from the storage device or an invalidate request to invalidate the copy of the data stored in that node's cache, wherein the one of a share request or the invalidate request is used to provide cache coherence between the caches; and

if the identified data is stored in the cache of the first access node, then (d) satisfying the data access request using the identified data in the cache of the first access node, and (e) if the data access is a read request, refraining from sending the share request to any of the other access nodes having a copy of the identified data as indicated by the portion of the directory,

wherein the directory is divided into chunks associated with corresponding sets of pages of the shared memory, and the portion of the directory includes a chunk having a directory entry storing the locations of copies of the identified data among the caches of the access nodes,

and wherein the instructions further cause the computerized device to participate in locality-conscious directory migration by which the chunks of the directory are dynamically distributed among the access nodes, the participating including:

prior to the satisfying of the data access request, obtaining ownership of the chunk so as to enable the first access node to use the portion of the directory to determine whether another of the access nodes has a copy of the identified data, the obtaining including:

(i) sending a directory query message to one of the access nodes functioning as a global directory chunk coordinator responsible for tracking and granting ownership of the chunks of the directory, the directory query message identifying the chunk;

(ii) receiving a directory reply message from the global directory chunk coordinator identifying a current owner of the chunk; and

(iii) communicating with the identified current owner of the chunk to obtain the ownership of the chunk; and

after the satisfying of the data access request, transferring ownership of the chunk to another of the access nodes.