Systems and methods for adaptive partitioning in distributed cache memories

• US 9,832,277 B2
• Filed: 11/13/2015
• Issued: 11/28/2017
• Est. Priority Date: 11/13/2015
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Misra, Pulkit Ambikanandan, No, Daniel Peter
• Primary Examiner(s): Bui, Jonathan
• Application Number:
  US14/941,125
• Publication Number:
  US 20170142217A1
• Time in Patent Office: 746 Days
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 12/0846 Cache with multiple tag or data arrays being simultaneously accessible
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/154 Networked environment
• CPC Class Codes: G06F 2212/502 using adaptive policy
• CPC Class Codes: G06F 2212/604 Details relating to cache allocation
• 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]
• CPC Class Codes: H04L 67/133 Protocols for remote procedure calls [RPC]
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching

Abstract

Methods and systems for performing adaptive partitioning of a distributed cache partitioned in cache slices are provided. The slices of the distributed cache are assigned to different computer nodes of the cluster based on a routing table. After a pre-determined period of time, the cache slices can be re-assigned to other computer nodes of the cluster based on access statistics and a new routing table is provided that corresponds to the re-assignment of the cache slices to the computer nodes of the cluster.

Claims

1. A method for adaptive partitioning of a distributed cache in a cluster comprising a plurality of computer nodes interconnected by a network, the distributed cache partitioned in cache slices, the method comprising:

assigning a first plurality of the cache slices to a first computer node based on a first routing table;

re-assigning, after a first period of time, based on access statistics for the cache slices of the computer nodes, a second plurality of the cache slices to the first computer node and a first subset of the first plurality of the cache slices to at least one computer node other than the first computer node; and

providing a second routing table according to the re-assigning of the cache slices to the computer nodes after the first period of time.

2. The method of claim 1, wherein the access statistics comprise transfer rates for the cache slices that are based on the access size for each of the cache slices and a period of time.

3. The method of claim 1, wherein the re-assigning of the second plurality of the cache slices and the first subset of the first plurality of the cache slices results in reduced network utilization.

4. The method of claim 1, further comprising comparing the first routing table and the second routing table to determine the second plurality of the cache slices and the first subset of the first plurality of the cache slices.

5. The method of claim 4, further comprising:

(a) flushing dirty data from the first subset of the first plurality of the cache slices;

(b) making the first subset of the first plurality of the cache slices write-through cache slices; and

(c) deleting pre-existing data from the second plurality of the cache slices.

6. The method of claim 5, further comprising determining whether a first error has occurred during at least one of (a), (b), and (c).

7. The method of claim 6, further comprising re-assigning the first plurality of the cache slices to the first computer node based on the first routing table, if the first error has occurred.

8. The method of claim 6, further comprising stopping, at the first computer node, servicing data requests, if the first error has not occurred.

9. The method of claim 8, further comprising determining, at the first computer node, destinations of data requests based on the second routing table.

10. The method of claim 9, further comprising determining whether a second error has occurred during the determining of the destinations of data requests based on the second routing table.

11. The method of claim 10, further comprising re-assigning the first plurality of the cache slices to the first computer node based on the first routing table, if the second error has occurred.

12. The method of claim 11, further comprising resuming at the first computer node, servicing data requests, if the first error has not occurred.

13. A system for adaptive partitioning of a distributed cache in a cluster comprising a plurality of computer nodes interconnected by a network, the system comprising:

the distributed cache partitioned in cache slices; and

a first computer node configured to;

assign a first plurality of the cache slices to the first computer node based on a first routing table;

re-assign, after a first period of time, based on access statistics for the cache slices of the computer nodes, a second plurality of the cache slices to the first computer node and a first subset of the first plurality of the cache slices to at least one computer node other than the first computer node; and

provide a second routing table according to the re-assigning of the cache slices to the computer nodes after the first period of time.

14. The system of claim 13, wherein the access statistics comprise transfer rates for the cache slices that are based on the access size for each of the cache slices and a period of time.

15. The system of claim 13, wherein the re-assigning of the second plurality of the cache slices and the first subset of the first plurality of the cache slices results in reduced network utilization.

16. The system of claim 13, wherein the first computer node is further configured to compare the first routing table and the second routing table to determine the second plurality of the cache slices and the first subset of the first plurality of the cache slices.

17. The system of claim 16, wherein the first computer node is further configured to:

(a) flush dirty data from the first subset of the first plurality of the cache slices;

(b) make the first subset of the first plurality of the cache slices write-through cache slices; and

(c) delete pre-existing data from the second plurality of the cache slices.

18. The system of claim 17, wherein the first computer node is further configured to determine whether a first error has occurred during at least one of (a), (b), and (c).

19. The system of claim 18, wherein the first computer node is further configured to re-assign the first plurality of the cache slices to the first computer node based on the first routing table, if the first error has occurred.

20. The system of claim 18, wherein the first computer node is further configured to stop servicing data requests, if the first error has not occurred.

21. The system of claim 20, wherein the first computer node is further configured to determine destinations of data requests based on the second routing table.

22. The system of claim 21, wherein the first computer node is further configured to determine whether a second error has occurred during the determining of the destinations of data requests based on the second routing table.

23. The system of claim 22, wherein the first computer node is further configured to re-assign the first plurality of the cache slices to the first computer node based on the first routing table, if the second error has occurred.

24. The system of claim 23, wherein the first computer node is further configured to resume servicing data requests, if the first error has not occurred.