Methods and systems for multi-caching

• US 20090049237A1
• Filed: 08/11/2008
• Published: 02/19/2009
• Est. Priority Date: 08/10/2007
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Sivakumar, Raghupathy, Velayutham, Aravind, Zhuang, Zhenyun
• Granted Patent: US 8,397,027 B2
• Time in Patent Office: Days
• US Class Current: 711/113
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning
• CPC Class Codes: G06F 2212/502 using adaptive policy
• CPC Class Codes: H04L 67/288 Distributed intermediate devices, i.e. intermediate devices for interaction with other intermediate devices on the same level
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching

Abstract

Provided are methods and systems for multi-caching. The methods and systems provided can enhance network content delivery performance in terms of reduced response time and increased throughput, and can reduce communication overhead by decreasing the amount of data that have to be transmitted over the communication paths.

Claims

1. A method for data multi-caching comprising:

receiving data;

generating a unique identifier for the data;

determining which of a plurality of node caches contains the unique identifier, wherein each of the plurality of node caches comprises a cache of stored unique identifiers corresponding to stored data on one of a plurality of nodes; and

transmitting the unique identifier a selected one of the plurality of nodes associated with a selected node cache of the plurality of node caches that contains the unique identifier.

2. The method of claim 1, wherein receiving data comprises receiving a request for data.

3. The method of claim 1, wherein generating a unique identifier comprises generating a hash value.

4. The method of claim 3, wherein the hash value comprises a prioritization factor.

5. The method of claim 1, wherein the data comprises a plurality of data packets.

6. A method for data multi-caching comprising:

receiving a plurality of data packets;

generating a unique identifier for the plurality of data packets;

determining which of a plurality of node caches contains the unique identifier, wherein each of the plurality of node caches comprises a cache of unique identifiers corresponding to data stored on one of a plurality of associated nodes; and

transmitting the unique identifier to the node associated with the node cache that contains the unique identifier.

7. The method of claim 6, wherein receiving data comprises receiving a request for data.

8. The method of claim 6, wherein generating a unique identifier comprises generating a hash value.

9. The method of claim 8, wherein the hash value comprises a prioritization factor.

10. The method of claim 6, wherein the plurality of packets comprises a first partial packet, at least one full packet, and a second partial packet.

11. A method for data multi-caching, comprising:

receiving a unique identifier from a first node at a second node;

determining data corresponding to the unique identifier;

if the data corresponding to the unique identifier is present, transmitting the data to a third node; and

if the data corresponding to the unique identifier is not present, transmitting a cache mismatch error to the first node.

12. The method of claim 11, wherein receiving a unique identifier from a first node comprises receiving a hash value.

13. The method of claim 11, wherein determining data corresponding to the unique identifier comprises searching a local cache.

14. The method of claim 11, wherein transmitting the data to a third node comprises transmitting the unique identifier.

15. The method of claim 11, further comprising:

if the data corresponding to the unique identifier is present and the second node is the destination node, retrieving the data.

16. A method for multi-caching, comprising:

a. allocating disk space for a first cache, wherein a plurality of cache entries are stored on the allocated disk space; and

b. allocating random access memory for the first cache, wherein the random access memory stores a subset of the disk cache.

17. The method of claim 16, further comprising repeating steps a and b for a second cache, wherein the first cache represents data and associated unique identifiers stored on a first node and the second cache represents data and associated unique identifiers stored on a second node.

18. The method of claim 17, wherein only one instance of overlapping data between the first cache and the second cache is stored on disk space.

19. The method of claim 16, comprising:

generating a main cache on the allocated disk space; and

implementing an adaptive cache replacement policy.

20. The method of claim 19, wherein the adaptive cache replacement policy comprises monitoring a cache entry size parameter “

S”

, a cache entry age parameter “

A”

, and a peer performance history parameter “

P”

.

21. The method of claim 20, further comprising:

monitoring a maximum cache size and a maximum bucket size for the main cache; and

replacing a cache entry when either the maximum cache size or the maximum bucket size is reached.

22. The method of claim 21, wherein the adaptive cache replacement policy replaces a cache entry according to the cache entry size parameter, the cache entry age parameter, and the peer performance history parameter.

23. The method of claim 22, wherein the cache entry is replaced is the cache entry with a maximum value of a plurality of tuples.

24. The method of claim 23, wherein the plurality of tuples comprises:

(A, S, 1/P), (A, 1/P, S), (S, A, 1/P), (S, 1/P, A), (1/P, S, A), and (1/P, A, S).

25. The method of claim 16, wherein the first cache comprises a first cache structure comprising a size of buckets array (K) attribute, a maximum bucket size (MAX_BUCKET_SIZE) attribute, a maximum caching size (MAX_CACHE_SIZE) attribute, and a cache replacement algorithm.

26. The method of claim 25, further comprising transmitting the first cache structure and receiving a second cache structure from a remote node.

27. A method for data multi-caching, comprising:

receiving a data packet; and

generating a first unique identifier for the data packet, wherein the first unique identifier comprises a cryptographic hash and a prioritization factor.

28. The method of claim 27, wherein generating a first unique identifier comprises generating a hash value.

29. The method of claim 28, wherein generating a hash value comprises the MD5 algorithm.

30. The method of claim 27, further comprising, transmitting a set of unique identifiers in a single data packet.

31. The method of claim 27, wherein generating a first unique identifier for the data packet, comprises:

generating a plurality of unique identifiers for a first plurality of data packets; and

generating a second unique identifier for the first plurality of unique identifiers.

32. The method of claim 31, further comprising:

receiving a third unique identifier for a second plurality of data packets; and

determining if the third unique identifier matches the second unique identifier.

33. A method for data multi-caching, comprising:

receiving a data packet;

applying a granularity adjustment to the data packet; and

generating a unique identifier for the adjusted data packet, wherein the unique identifiers comprise a cryptographic hash and a prioritization factor.

34. The method of claim 33, wherein applying a granularity adjustment to the data packet comprises segmenting the data packet into a plurality of segments.

35. The method of claim 34, wherein generating a unique identifier for the adjusted data packet comprises generating a unique identifier for the data packet and for each of the plurality of segments.

36. The method of claim 33, wherein segmenting the data packet into a plurality of segments comprises dividing the data packet based on a Rabin polynomial.

37. The method of claim 33, wherein applying a granularity adjustment to the data packet comprises grouping the data packet into a plurality of data packets.

38. The method of claim 34, wherein generating a unique identifier for the adjusted data packet comprises generating a unique identifier for the data packet and for the plurality of data packets.

39. The method of claim 33, wherein the prioritization factor comprises one or more of, bandwidth, frequency of access for a data pattern, importance of peer, and performance history.

40. A method for data multi-caching, comprising:

receiving data;

generating a unique identifier for the data;

determining a data route comprising a plurality of nodes;

searching, according to the data route, a plurality of node caches using the unique identifier, wherein each of the plurality of node caches comprises a cache of unique identifiers corresponding to data stored on one of a plurality of associated nodes; and

transmitting, according to the data route, the unique identifier to the node associated with the node cache that contains the unique identifier.

41. The method of claim 40, wherein receiving data comprises receiving a request for data.

42. The method of claim 40, wherein determining a data route comprising a plurality of nodes comprises determining one or more data route optimization parameters.

43. The method of claim 40, wherein determining a data route comprising a plurality of nodes comprises receiving a pre-defined data route.

44. A method for multi-caching, comprising:

determining an inconsistency between a first cache map on a first node and a second cache map on a second node;

transmitting a first set of unique identifiers from the first cache map to the second node;

comparing the first set of unique identifiers from the first cache map to a second set of unique identifiers from the second cache map;

identifying one or more unique identifiers to be discarded from the first cache map; and

transmitting the one or more unique identifiers to be discarded to the first node.

45. The method of claim 44, wherein the first cache map comprises data and unique identifiers associated with the data stored on the first node and the second cache map comprises data and unique identifiers associated with the data stored on the second node.

46. The method of claim 44, wherein determining an inconsistency between a first cache map on a first node and a second cache map on a second node comprises:

generating a first unique identifier for a for a first cache map at a first node;

transmitting the unique identifier to a second node;

generating a second unique identifier for a second cache map at the second node; and

comparing the first unique identifier and the second unique identifier to determine consistency of the first cache map and the second cache map.