Systems and methods for cache coherence protocol

• US 9,298,624 B2
• Filed: 05/14/2014
• Issued: 03/29/2016
• Est. Priority Date: 05/14/2014
• Status: Expired due to Fees

• Current Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Original Assignee: HGST Netherlands B.V. (Western Digital Corporation)
• Inventors: Ren, Jin, Yang, Ken Qing, Fedynyshyn, Gregory Evan
• Primary Examiner(s): SCOTT, RANDY A
• Application Number:
  US14/277,492
• Publication Number:
  US 20150331794A1
• Time in Patent Office: 685 Days
• Field of Search: 709/214, 709/202, 709/246, 709/238, 711/136, 711/138, 711/117, 711/118
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/0833 in combination with broadcast means (e.g. for invalidation or updating)
• CPC Class Codes: G06F 12/122 of the least frequently used [LFU] type, e.g. with individual count value
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel
• CPC Class Codes: G06F 15/167 using a common memory, e.g. mailbox
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 2212/1021 Hit rate improvement
• CPC Class Codes: G06F 2212/154 Networked environment
• CPC Class Codes: G06F 2212/163 Server or database system
• CPC Class Codes: G06F 2212/222 Non-volatile memory
• CPC Class Codes: G06F 2212/254 Distributed memory
• CPC Class Codes: G06F 2212/264 Remote server
• CPC Class Codes: G06F 2212/282 Partitioned cache
• CPC Class Codes: G06F 2212/286 Mirrored cache memory
• CPC Class Codes: G06F 2212/314 In storage network, e.g. network attached cache
• CPC Class Codes: G06F 2212/621 Coherency control relating to peripheral accessing, e.g. from DMA or I/O device
• CPC Class Codes: G06F 3/06 Digital input from, or digital output to, record carriers , e.g. RAID, emulated record carriers or networked record carriers
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/064 Management of blocks
• 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]
• CPC Class Codes: H04L 65/40 : Support for services or applications
• CPC Class Codes: H04L 67/1095 : Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/1097 : for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

The present disclosure relates to systems, methods, and computer program products for keeping multiple caches updated, or coherent, on multiple servers when the multiple caches contain independent copies of cached data. Example methods may include receiving a request to write data to a block of a first cache associated with a first server in a clustered server environment. The methods may also include identifying a second cache storing a copy of the block, where the second cache is associated with a second server in the clustered environment. The methods may further include transmitting a request to update the second cache with the received write data, and upon receiving a subsequent request to write subsequent data, identifying a third cache for invalidating based on access patterns of the blocks, where the third cache is associated with a third server in the clustered environment.

Claims

1. A method of updating a cache in a clustered server environment, the method comprising:

receiving a request to write data to a block of a first cache associated with a first server in the clustered server environment, wherein a plurality of servers in the clustered environment have an associated cache;

identifying a second cache storing a copy of the block, wherein the second cache is associated with a second server in the clustered environment;

transmitting a request to update the second cache with the received write data, whereby future requests are able to process the received write data from the second cache; and

upon receiving a subsequent request to write subsequent data, identifying a third cache for invalidating based at least in part on access patterns of the blocks, wherein the third cache is associated with a third server in the clustered environment.

2. The method of claim 1, further comprising transmitting a request to invalidate the third cache based at least in part on the access patterns of the blocks.

3. The method of claim 1, wherein the access patterns comprise at least one of a frequency of access of the block and a recency of access of the block.

4. The method of claim 1,

wherein the identifying the second cache comprises looking up the received block from one or more cache coherence tables tracking blocks and associated servers;

and

wherein the one or more cache coherence tables are distributed across a plurality of servers.

5. The method of claim 4, wherein the one or more cache coherence tables are partitioned into subtables according to a hash function.

6. The method of claim 4, wherein the transmitting the request to update the second cache comprises:

identifying a corresponding row of the one or more cache coherence tables based on the received block;

updating the corresponding cache status of the corresponding row; and

transmitting the request to update the block of the second cache with the received write data.

7. The method of claim 1,

wherein the block comprises a logical block address (LBA), and

wherein the cache is implemented using a solid state drive (SSD).

8. A server for updating a cache in a clustered environment, the server comprising:

a network interface configured to transmit and receive a plurality of requests;

a cache configured to store a plurality of blocks and data associated with the blocks; and

a processor in communication with the network and to the cache, wherein the processor is configured to;

receive, over the network interface, a request to write data to a block of the cache;

identify a second cache storing a copy of the block, wherein the second cache is associated with a second server in the clustered environment;

transmit, over the network interface, a request to update the second cache with the received write data, whereby future requests are able to process the received write data from the second cache; and

upon receiving, over the network interface, a subsequent request to write subsequent data, identify a third cache for invalidating based at least in part on access patterns of the blocks, wherein the third cache is associated with a third server in the clustered environment.

9. The server of claim 8, wherein the processor is further configured to transmit a request to invalidate the third cache, based at least in part on the access patterns of the blocks.

10. The server of claim 8, wherein the access patterns comprise at least one of a frequency of access of the block and a recency of access of the block.

11. The server of claim 8,

wherein the identifying the second cache comprises looking up the received block from one or more cache coherence tables tracking blocks and associated servers;

and

wherein the one or more cache coherence tables are distributed across a plurality of servers.

12. The server of claim 11, wherein the one or more cache coherence tables are partitioned into subtables according to a hash function.

13. The server of claim 11, wherein the processor configured to transmit the request to update the second cache comprises the processor being configured to:

identify a corresponding row of the one or more cache coherence tables based on the received block;

update the corresponding cache status of the corresponding row; and

transmit the request to update the block of the second cache with the received write data.

14. The server of claim 8,

wherein the block comprises a logical block address (LBA), and

wherein the cache is implemented using a solid state drive (SSD).

15. A non-transitory computer program product for updating a cache in a clustered environment, tangibly embodied in a computer-readable medium, the computer program product including instructions operable to cause a data processing apparatus to:

receive a request to write data to a block of a first cache associated with a first server in the clustered server environment, wherein a plurality of servers in the clustered environment have an associated cache;

identify a second cache storing a copy of the block, wherein the second cache is associated with a second server in the clustered environment;

transmit a request to update the second cache with the received write data, whereby future requests are able to process the received write data from the second cache; and

upon receiving a subsequent request to write subsequent data, identify a third cache for invalidating based at least in part on access patterns of the blocks, wherein the third cache is associated with a third server in the clustered environment.

16. The computer program product of claim 15, further comprising instructions operable to cause the data processing apparatus to transmit a request to invalidate the third cache based at least in part on the access patterns of the blocks.

17. The computer program product of claim 15, wherein the access patterns comprise at least one of a frequency of access of the block and a recency of access of the block.

18. The computer program product of claim 15,

wherein the instructions operable to cause the data processing apparatus to identify the second cache comprise instructions operable to cause the data processing apparatus to look up the received block from one or more cache coherence tables tracking blocks and associated servers;

and

wherein the one or more cache coherence tables are distributed across a plurality of servers.

19. The computer program product of claim 18, wherein the one or more cache coherence tables are partitioned into subtables according to a hash function.

20. The computer program product of claim 15, wherein the instructions operable to cause the data processing apparatus to transmit the request to update the second cache comprise instructions operable to cause the data processing apparatus to:

identify a corresponding row of the one or more cache coherence tables based on the received block;

update the corresponding cache status of the corresponding row; and

transmit the request to update the block of the second cache with the received write data.