Methods and systems of cache memory management and snapshot operations

• US 7,124,243 B2
• Filed: 05/16/2003
• Issued: 10/17/2006
• 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
• Primary Examiner(s): Choi, Woo H.
• Application Number:
  US10/440,347
• Publication Number:
  US 20040230737A1
• Time in Patent Office: 1,250 Days
• Field of Search: 711/113, 711/216
• US Class Current: 711/113
• 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 first request for data to index to a first hash table pointer and a second request for data to index to a second hash table pointer in the hash table, wherein the first hash table pointer points to a first hash table element and the second hash table pointer points to a second hash table element of a linked list of hash table elements in the cache directory, wherein the first hash table element and the second hash table element point 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, and stages the requested data from the source VLUN to the first cache line.

3. The system of claim 1, wherein the cache manager receives the second request for data from a snapshot application.

4. The system of claim 1, wherein the cache manager receives a request 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, further comprising a source VLUN and a target VLUN, 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 6, 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 6, 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 6, wherein the data storage system destages the data and the 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 a data storage subsystem coupled to the cache manager, the 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 each of the first and second hash table elements include a cache line descriptor pointer and 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 or a dirty bitmap.

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

15. The system of claim 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, or 12, further comprising cache list functional pointers that point to the first hash table element, wherein the cache list functional pointers include a dirty list entry pointer, a least-recently-used pointer, a map list pointer, or a pinned list entry pointer.

44. The system of claim 1, wherein the cache manager receives a request to store updated data, wherein the cache manager converts the request to index to the second hash table pointer that points to the second 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.

45. The system of claim 44, 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.

46. The system of claim 44, further comprising a source VLUN and a target VLUN, 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.

47. The system of claim 46, 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.

48. The system of claim 46, 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.

49. The system of claim 46, 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.

50. The system of claim 44, 45, 46, 47, 48, or 49, wherein the first and second hash table elements each include a cache line descriptor pointer and 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, or a dirty bitmap.

51. The system of claim 44, 45, 46, 47, 48, or 49, wherein the first and second cache line descriptors each include a cache line pointer and a valid flag, a reader count, a writer count, a pending list, a valid bitmap, a modification in process bitmap, or a mirror pointer.

52. The system of claim 44, 45, 46, 47, 48, or 49, further comprising cache list functional pointers that point to the first hash table element, wherein the cache list functional pointers include a dirty list entry pointer, a least-recently-used pointer, a map list pointer, or a pinned list entry pointer.

65. The system of claim 4, 5, 6, 7, 8, or 9, wherein the second cache line descriptor includes a cache line pointer and a valid flag, a reader count, a writer count, a pending list, a valid bitmap, a modification in process bitmap, or a mirror 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;

a cache manager receiving a plurality of requests for data and using a search algorithm to locate a first search element and a second search element that point to the first cache line descriptor

a source VLUN that includes a storage space corresponding to the first cache line; and

a target VLUN pointing to the storage space of the source VLUN corresponding to the first cache line.

17. The system of claim 16, wherein the cache manager determines the requested data is not in the cache memory and stages the requested data from the source VLUN to the first cache line.

18. The system of claim 16, wherein the cache manager receives a request to store updated data, wherein the cache manager converts the request to locate a third search 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.

19. The system of claim 18, 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.

20. The system of claim 18, 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, wherein the target VLUN no longer points to the storage space of the source VLUN corresponding to the first cache line.

21. The system of claim 20, 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.

22. The system of claim 20, 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.

23. The system of claim 20, 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.

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

25. The system of claim 16, 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.

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

27. The system of claim 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, or 26, wherein the first and second search elements each include a cache line descriptor pointer and a search element forward pointer, a search 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, or a dirty bitmap.

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

29. The system of claim 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, or 26, further comprising cache list functional pointers that point to the first search element, wherein the cache list functional pointers include a dirty list entry pointer, a least-recently-used pointer, a map list pointer, or a pinned list entry pointer.

53. The system of claim 16, wherein the cache manager receives a request to store updated data, wherein the cache manager converts the request to locate the second search element to point to a second cache line descriptor associated with a second cache line and writes the updated data to the second cache line.

54. The system of claim 53, 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.

55. The system of claim 53, 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.

56. The system of claim 55, 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.

57. The system of claim 55, 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.

58. The system of claim 55, 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.

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

converting a first request for data to a first 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 data;

determining the data is not in cache memory;

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

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

converting a second request from a snapshot application for the data to a second input to the hashing function;

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

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

determining the data is in cache memory; and

allocating a second hash table element that points to the first cache line descriptor.

31. The method of claim 30, 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.

32. The method of claim 31, 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.

33. The method of claim 31, 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.

34. The method of claim 33, 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.

35. The method of claim 33, 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.

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

59. The method of claim 30, further comprising the steps of:

requesting to store updated data;

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

outputting a second index to the hash table;

allocating a second hash table element CLD pointer 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.

60. The method of claim 59, 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.

61. The method of claim 59, 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.

62. The method of claim 61, 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.

63. The method of claim 61, 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.

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

37. 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;

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

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

receiving another request for the data from a snapshot application; and

allocating a second search element, wherein the second search element and the

first cache line descriptor associate with the first cache line in cache memory.

38. The method of claim 37, 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.

39. The method of claim 38, 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.

40. The method of claim 38, 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.

41. The method of claim 40, 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.

42. The method of claim 40, 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.

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