Cache object store

• US 6,542,967 B1
• Filed: 06/22/1999
• Issued: 04/01/2003
• Est. Priority Date: 04/12/1999
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Major, Robert Drew
• Primary Examiner(s): Yoo, Do Hyun
• Assistant Examiner(s): PEUGH, BRIAN R
• Application Number:
  US09/337,241
• Time in Patent Office: 1,379 Days
• Field of Search: 711/160, 711/161, 711/133, 711/135, 711/136, 711/116, 711/113, 711/118, 711/112, 711/122, 711/4, 711/206, 711/128, 707/103, 707/104, 706/16, 710/30
• US Class Current: 711/134
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 12/127 using additional replacement algorithms
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

A cache object store is organized to provide fast and efficient storage of data as cache objects organized into cache object groups. The cache object store preferably embodies a multi-level hierarchical storage architecture comprising a primary memory-level cache store and, optionally, a secondary disk-level cache store, each of which is configured to optimize access to the cache object groups. These levels of the cache object store further exploit persistent and non-persistent storage characteristics of the inventive architecture.

Claims

1. A cache object store organized to provide fast and efficient storage of data as cache objects organized into cache object groups, the cache object store comprising:

a primary-level store and a secondary-level store;

a cache grouper for logically associating cache objects into cache object groups; and

a cache object manager cooperatively coupled to the cache grouper and configured to implement an aging policy, the aging policy maintaining a first cache object groups on the primary-level store and a second cache object groups on the secondary-level store;

a cache directory manager cooperatively coupled to the cache object manager to implement a storage management policy that moves certain first cache object groups from the primary-level store for storage on the secondary-level store as second cache object groups, and the aging policy is a modified least recently used (LRU) algorithm that marks each cache object group with (i) a time of last access (TLA) factor within the cache object store, and (ii) a cost of reacquisition (COA) factor used to determine which cache object group to delete or move.

2. The cache object store of claim 1 further comprising a tertiary-level store cooperatively coupled to the primary and secondary level stores.

3. The cache object store of claim 2 wherein the tertiary-level store comprises bubble memory.

4. The cache object store of claim 1 further comprising an aging table structure maintained by the cache object manager to track the TLA and COA factors during implementation of the modified LRU by the cache object manager.

5. A cache object store, comprising:

a primary-level store having random access memory;

a secondary-level store coupled to the primary-level store, the secondary-level store having at least one non-volatile disk;

a cache grouper for logically associating cache objects into cache object groups;

a cache object manager cooperatively coupled to the cache grouper and configured to implement an aging policy that maintains a first cache object groups on the primary-level store, the aging policy further maintaining a second cache object groups on the secondary-level store; and

,

a cache directory manager cooperatively coupled to the cache object manager to implement a storage management policy that moves certain of the first cache object groups from the primary-level store for storage on the secondary-level store as the second cache object groups, the storage management policy substantially improving storage of the second cache object groups on the secondary-level store by avoiding fragmentation of the second cache object groups on the secondary-level store, and wherein the storage management policy moves the first cache object groups from the primary-level store to the secondary-level store by first searching the secondary-level store at a location in proximity to where the secondary-level store was last accessed.

6. The cache object store of claim 5 further comprising a list of cache object groups maintained by the cache object manager that specifies those first cache object groups, by cache object group size, to move from the primary-level store to the secondary-level store.

7. The cache object store of claim 6 wherein the cache directory manager comprises a memory directory submanager and a disk directory submanager adapted to manage organizations of the primary-level and secondary-level stores, respectively, to thereby implement the storage management policy.

8. A method for efficiently storing data as cache objects on a cache object store, the method comprising the steps of:

providing a primary-level volatile store coupled to a secondary-level non-volatile store;

organizing the cache objects into cache object groups;

implementing an aging policy that maintains first, frequently-accessed cache object groups on the primary-level store and second, less-frequently-accessed cache object groups on the secondary-level store; and

implementing a storage management policy that efficiently moves certain first cache object groups from the primary-level store for storage on the secondary-level store as second cache object groups, and the aging policy is a modified least recently used (LRU) algorithm for marking each cache object group with (i) a time of last access (TLA) factor indicating a frequency at which the cache object group is accessed within the cache object store, and (ii) a cost of reacquisition (COA) factor used to determine which cache object group to delete or move.

9. The method of claim 8 wherein the step of implementing the modified LRU aging policy further comprises the step of empirically determining the COA factor by measuring the turnaround time needed to acquire a cache object group, wherein the turnaround time is defined as time elapsed from when a request is issued to acquire the cache object group to when the cache object group is retrieved.

10. The method of claim 8 wherein the step of implementing the modified LRU aging policy further comprises the step of targeting those objects for movement or deletion based on relative computation of the TLA and COA factors.

11. A node for carrying out the method according to claim 8.

12. A computer network comprising at least one node for carrying out the method according to claim 8.

13. A computer-readable medium comprising:

instructions for execution on a processor and data written thereon, said instructions and data containing information for the practice of the method of claim 8.

14. Electromagnetic signals traveling over a computer network comprising:

said electromagnetic signals carrying information including instructions for execution on a processor for the practice of the method of claim 8.

15. A method for storing data as cache objects on a cache object store, the method comprising the steps of:

providing a primary-level volatile store coupled to a secondary-level non-volatile store;

organizing the cache objects into cache object groups;

implementing an aging policy that maintains first, frequently-accessed cache object groups on the primary-level store and second, less-frequently-accessed cache object groups on the secondary-level store; and

,

implementing a storage management policy that moves certain first cache object groups from the primary-level store for storage on the secondary-level store as second cache object groups, the management policy by avoiding fragmentation to each certain cache object group on the secondary-level, non-volatile store, and wherein and wherein the management policy moves the first cache object groups from the primary-level store to the secondary-level store by first searching the secondary-level store at a location in proximity to where the secondary-level store was last accessed.

16. The method of claim 15 wherein the secondary-level, non-volative store comprises a disk and wherein the step of implementing the storage management policy further comprises the steps of:

conducting a search for a preconfigured level of free space around an area of the disk that is last accessed; and

upon discovering the preconfigured level of free space, storing the certain cache object group on the free space.

17. The method of claim 16 wherein the step of implementing the storage management policy further comprises the steps of:

if the preconfigured level of free space is not discovered, generating a list of all free spaces on the disk; and

generating a list of available spaces on the disk.

18. The method of claim 17 wherein the step of implementing the storage management policy further comprises the steps of:

comparing combinations of certain cache object groups that fit the listed free spaces; and

if combinations of certain cache object groups are found that fit the free spaces, storing those certain cache object groups on the free disk spaces.

19. The method of claim 18 wherein the step of implementing the storage management policy further comprises the steps of:

if combinations of certain cache object groups are not found that fit the free spaces, comparing combinations of certain cache object groups that fit the listed available spaces; and

storing the remaining certain cache object groups on the available disk spaces.

20. The method of claim 19 wherein the step of comparing combinations of certain cache object groups that fit the listed available spaces comprises the step of calculating the available spaces by coalescing boundaries between the two lists of spaces.

21. A cache object store, comprising:

a primary-level store;

a secondary-level store coupled to the primary-level store;

a cache grouper for logically associating cache objects into cache object groups;

a cache object manager cooperatively coupled to the cache grouper and configured to implement an aging policy that maintains a first cache object groups on the primary-level store, the aging policy further maintaining a second cache object groups on the secondary-level store; and

,

a cache directory manager cooperatively coupled to the cache object manager to implement a storage management policy that moves certain of the first cache object groups from the primary-level store for storage on the secondary-level store as the second cache object groups, the storage management policy substantially improving storage of the second cache object groups on the secondary-level store by avoiding fragmentation of the second cache object groups on the secondary-level store, and wherein the storage management policy moves the first cache object groups from the primary-level store to the secondary-level store by first searching the secondary-level store at a location in proximity to where the secondary-level store was last accessed.

22. A method for storing data as cache objects on a cache object store, the method comprising the steps of:

providing a primary-level store coupled to a secondary-level;

organizing the cache objects into cache object groups;

implementing an aging policy that maintains first, frequently-accessed cache object groups on the primary-level store and second, less-frequently-accessed cache object groups on the secondary-level store; and

,

implementing a storage management policy that moves certain first cache object groups from the primary-level store for storage on the secondary-level store as second cache object groups, the management policy by avoiding fragmentation to each certain cache object group on the secondary-level, non-volatile store, and wherein the storage management policy moves the first cache object groups from the primary-level store to the secondary-level store by first searching the secondary-level store at a location in proximity to where the secondary-level store was last accessed.