Methods and systems of cache memory management and snapshot operations

• US 20040230737A1
• Filed: 05/16/2003
• Published: 11/18/2004
• Est. Priority Date: 05/16/2003
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Pillar Data Systems, Inc. (Oracle Corporation)
• Inventors: Burton, David Alan, Otterness, Noel Simen
• Granted Patent: US 7,124,243 B2
• Time in Patent Office: Days
• US Class Current: 711/3
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 2212/284 being distributed
• CPC Class Codes: G06F 2212/285 Redundant cache memory
• CPC Class Codes: G06F 2212/311 In host system

Abstract

The present invention relates to a cache memory management system suitable for use with snapshot applications. The system includes a cache directory including a hash table, hash table elements, cache line descriptors, and cache line functional pointers, and a cache manager running a hashing function that converts a request for data from an application to an index to a first hash table pointer in the hash table. The first hash table pointer in turn points to a first hash table element in a linked list of hash table elements where one of the hash table elements of the linked list of hash table elements points to a first cache line descriptor in the cache directory and a cache memory including a plurality of cache lines, wherein the first cache line descriptor has a one-to-one association with a first cache line. The present invention also provides for a method converting a request for data to an input to a hashing function, addressing a hash table based on a first index output from the hashing function, searching the hash table elements pointed to by the first index for the requested data, determining the requested data is not in cache memory, and allocating a first hash table element and a first cache line descriptor that associates with a first cache line in the cache memory.

Claims

1. A cache memory management system in a data storage system, comprising:

a cache memory including a cache directory including a hash table, hash table elements, and cache line descriptors and a plurality of cache lines, wherein a first cache line descriptor has a one-to-one association with a first cache line; and

a cache manager using a hashing function to convert a request for data from an application to index to a first hash table pointer in the hash table, wherein the first hash table pointer points to a linked list of hash table elements in the cache directory, wherein a first hash table element of the linked list of hash table elements points to the first cache line descriptor in the cache directory.

2. The system of claim 1, further comprising a source VLUN and a target VLUN, wherein the cache manager determines the requested data is not in the cache memory, allocates the first hash table element and the first cache line descriptor, and stages the requested data from the source VLUN to the first cache line.

3. The system of claim 2, wherein the cache manager receives a request from a snapshot application and converts the request to an index to a second hash table pointer, wherein the second hash table pointer points to a second hash table element that points to the first cache line descriptor.

4. The system of claim 3, wherein the cache manager receives a request from the application to store updated data, wherein the cache manager converts the request to index to a third hash table pointer that points to a third hash table element that points to a second cache line descriptor associated with a second cache line for storing the updated data and writes the updated data to the second cache line.

5. The system of claim 4, wherein the data storage system writes the updated data from the second cache line and the data from the first cache line to one or more nonvolatile storage devices.

6. The system of claim 4, wherein the data storage system destages the updated data from the second cache line to the source VLUN and destages the data from the first cache line to the target VLUN.

7. The system of claim 4, wherein the data storage system destages the updated data from the second cache line to the source VLUN before the system destages the data from the first cache line to the target VLUN.

8. The system of claim 4, wherein the data storage system destages the updated data from the second cache line to the source VLUN after the system destages the data from the first cache line to the target VLUN.

9. The system of claim 4, wherein the data storage system destages the data and updated data from the first and second cache lines to the target and source VLUNs as a background activity.

10. The system of claim 2, further comprising a host coupled to one or more data storage subsystems, wherein the host contains the cache manager and cache memory, and the one or more data storage subsystems correspond to the source VLUN and the target VLUN.

11. The system of claim 2, further comprising a host coupled to one or more data storage subsystems, and wherein the host is coupled to the cache manager and the cache memory, and the one or more data storage subsystems correspond to the source VLUN and the target VLUN.

12. The system of claim 2, further comprising one or more data storage subsystems that include the cache manager, cache memory, the source VLUN, and the target VLUN.

13. The system of claim 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, or 12, wherein the hash table elements include items selected from the list of a hash table element forward pointer, a hash table element backward pointer, a map list forward pointer, a map list backward pointer, a dirty list forward pointer, a dirty list backward pointer, a usage list forward pointer, a usage list backward pointer, a pinned list forward pointer, a pinned list backward pointer, a VLUN identifier, a logical block address, a use count, a dirty bitmap, and a cache line descriptor pointer.

14. The system of claim 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, or 12, wherein the cache line descriptors includes items selected from the list of a valid flag, a reader count, a writer count, a pending list, a valid bitmap, a modification in process bitmap, a cache line pointer, and a mirror pointer.

15. The system of claim 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, or 12, wherein the cache line functional pointers include items selected from list of a dirty list entry pointer, a least-recently-used pointer, a map list pointer, and a pinned list entry pointer.

16. A cache memory management system in a data storage system, comprising:

a cache memory including a cache directory including search elements and cache line descriptors and a plurality of cache lines, wherein a first cache line descriptor has a one-to-one association with a first cache line; and

a cache manager receiving a request for data from an application and using a search algorithm to locate a first search element that points to the first cache line descriptor.

17. The system of claim 16, further comprising a source VLUN and a target VLUN, wherein the cache manager determines the requested data is not in the cache memory, allocates the first hash table element and the first cache line descriptor, and stages the requested data from the source VLUN to the first cache line.

18. The system of claim 17, wherein the cache manager receives a request from a snapshot application and converts the request to locate a second hash table element that points to the first cache line descriptor.

19. The system of claim 18, wherein the cache manager receives a request from the application to store updated data, wherein the cache manager converts the request to locate a third hash table element that points to a second cache line descriptor associated with a second cache line for storing the updated data and writes the updated data to the second cache line.

20. The system of claim 19, wherein the data storage system writes the updated data from the second cache line and the data from the first cache line to one or more nonvolatile storage devices.

21. The system of claim 19, wherein the data storage system destages the updated data from the second cache line to the source VLUN and destages the data from the first cache line to the target VLUN.

22. The system of claim 19, wherein the data storage system destages the updated data from the second cache line to the source VLUN before the system destages the data from the first cache line to the target VLUN.

23. The system of claim 19, wherein the data storage system destages the updated data from the second cache line to the source VLUN after the system destages the data from the first cache line to the target VLUN.

24. The system of claim 19, wherein the data storage system destages the data and updated data from the first and second cache lines to the target and source VLUNs as a background activity.

25. The system of claim 17, further comprising a host coupled to one or more data storage subsystems, wherein the host contains the cache manager and cache memory, and the one or more data storage subsystems correspond to the source VLUN and the target VLUN.

26. The system of claim 17, further comprising a host coupled to one or more data storage subsystems, and wherein the host is coupled to the cache manager and the cache memory, and the one or more data storage subsystems correspond to the source VLUN and the target VLUN.

27. The system of claim 17, further comprising one or more data storage subsystems that include the cache manager, cache memory, the source VLUN, and the target VLUN.

28. The system of claim 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, or 27, wherein the hash table elements include items selected from the list of a hash table element forward pointer, a hash table element backward pointer, a map list forward pointer, a map list backward pointer, a dirty list forward pointer, a dirty list backward pointer, a usage list forward pointer, a usage list backward pointer, a pinned list forward pointer, a pinned list backward pointer, a VLUN identifier, a logical block address, a use count, a dirty bitmap, and a cache line descriptor pointer.

29. The system of claim 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, or 27, wherein the cache line descriptors includes items selected from the list of a valid flag, a reader count, a writer count, a pending list, a valid bitmap, a modification in process bitmap, a cache line pointer, and a mirror pointer.

30. The system of claim 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, or 27, wherein the cache line functional pointers include items selected from list of a dirty list entry pointer, a least-recently-used pointer, a map list pointer, and a pinned list entry pointer.

31. A method in a cache memory management system, comprising:

converting a request for data to an input to a hashing function;

addressing a hash table based on a first index output from the hashing function;

searching the hash table elements pointed to by the first index for the requested data;

determining the requested data is not in cache memory; and

allocating a first hash table element and a first cache line descriptor that associates with a first cache line in cache memory.

32. The method of claim 31, further comprising the steps of:

staging the data from a source VLUN to the first cache line;

receiving a request from a snapshot application;

converting the request to a second input to the hashing function;

providing a second index to a second hash table pointer based on the second input; and

pointing to a second hash table element in a linked list of hash table elements based on the second index, wherein the second hash table element points to the first cache line descriptor.

33. The method of claim 32, further comprising the steps of:

requesting to store updated data;

converting the request into a third input to the hashing function;

outputting a third index to the hash table;

allocating a third hash table element and a second cache line descriptor to point to a second cache line for the updated data;

updating the data; and

writing the updated data into the second cache line.

34. The method of claim 33, further comprising writing the updated data from the second cache line and the data from the first cache line to one or more nonvolatile storage devices.

35. The method of claim 33, further comprising the steps of:

destaging the updated data from the second cache line to the source VLUN; and

destaging the data from the first cache line to a target VLUN.

36. The method of claim 35, wherein the destaging of the updated data from the second cache line to the source VLUN precedes the destaging of the data from the first cache line to the target VLUN.

37. The method of claim 35, wherein the destaging of the data from the first cache line to the target VLUN precedes the destaging of the updated data from the second cache line to the source VLUN.

38. The method of claim 35, wherein the destaging of the updated data and the data from the cache memory to the source and target VLUNs is a background activity.

39. A method in a cache memory management system, comprising:

receiving a request for data from a first application;

determining the requested data is not in cache memory; and

allocating a first search element and a first cache line descriptor that associate with a first cache line in cache memory.

40. The method of claim 39, further comprising the steps of:

staging the data from a source VLUN to the first cache line;

receiving a request for data from a snapshot application;

allocating a second search element, wherein the second search element and a first cache line descriptor associate with a first cache line in cache memory.

41. The method of claim 40, further comprising the steps of:

receiving a request from the first application to store updated data;

allocating a third search element and a second cache line descriptor that associate with a second cache line for the updated data; and

writing the updated data into the second cache line.

42. The method of claim 41, further comprising writing the updated data from the second cache line and the data from the first cache line to one or more nonvolatile storage devices.

43. The method of claim 41, further comprising the steps of:

destaging the updated data from the second cache line to the source VLUN; and

destaging the data from the first cache line to a target VLUN.

44. The method of claim 43, wherein the destaging of the updated data from the second cache line to the source VLUN precedes the destaging of the data from the first cache line to the target VLUN.

45. The method of claim 43, wherein the destaging of the data from the first cache line to the target VLUN precedes the destaging of the updated data from the second cache line to the source VLUN.

46. The method of claim 43, wherein the destaging of the updated data and the data from the cache memory to the source and target VLUNs is a background activity.