Consistent data storage in an object cache

• US 6,128,627 A
• Filed: 04/15/1998
• Issued: 10/03/2000
• Est. Priority Date: 04/15/1998
• Status: Expired due to Term

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Inktomi Corporation (Apollo Global Management, Inc.)
• Inventors: Beguelin, Adam, Gourley, David, Totty, Brian, Mattis, Peter, Plevyak, John, Haines, Matthew
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US09/060,974
• Time in Patent Office: 902 Days
• Field of Search: 707/206, 707/10, 707/202, 707/203, 395/200, 395/610
• US Class Current: 1/1
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method for consistently storing cached objects in the presence of failures is provided. This method ensures atomic object consistency--in the event of failure and restart, an object will either be completely present or completely absent from the cache, never truncated or corrupted. Furthermore, this consistency comes without any time-consuming data structure reconstruction on restart. In this scheme, objects are indexed by a directory table that is stored in main memory and mapped to non-volatile storage, and changes to the directory table are buffered into an open directory that is stored in main memory. Cache objects are either stored in volatile aggregation buffers or in segments of non-volatile disk storage called arenas. Objects are first coalesced into memory-based aggregation buffers, and later committed to disk. Locking is used to control parallel storage to aggregation buffers. Directory entries pointing to objects are only permitted to be written to persistent disk storage after the target objects are themselves committed to disk, preventing dangling pointers. Periodically, when the contents of open directory entries point to objects that are stably stored on disk, the open directory entries are copied into the directory table and committed to non-volatile storage. The disclosure also encompasses a computer program product, computer apparatus, and computer data signal configured similarly.

Claims

1. In a cache for information objects that comprises a directory table that indexes each of the information objects in one of a plurality of buckets, an open directory comprising a list of changes associated with each of the buckets, a set of volatile object aggregation buffers, and a set of disk-based object pools, a method for ensuring the integrity of cache storage in the presence of software failures, comprising the steps of:

copying blocks of the open directory to the directory table and

synchronizing those blocks to disk;

wherein the steps of copying and synchronizing are performed if and only if objects that are referenced in the blocks have been written and synchronized to disk;

whereby after a cache restart, all previously cached objects are consistent, in that pre-failure objects are either completely present or completely absent from the cache, and there is no truncation, corruption, or false aliasing of cache content.

2. In a cache for information objects that comprises a directory table that indexes each of the information objects in one of a plurality of buckets, an open directory comprising a list of changes associated with each of the buckets, a set of volatile object aggregation buffers, and a set of disk-based object pools, a method for ensuring the integrity of cache storage in the presence of software failures, comprising the steps of:

periodically carrying out a garbage collection task in which undesirable fragments of objects are deleted from storage arenas, by deleting the metadata that references the undesirable fragments from the open directory and synchronizing to disk the metadata that references new locations of fragments that result from the garbage collection task;

whereby after a cache restart, all previously cached objects are consistent, in that pre-failure objects are either completely present or completely absent from the cache, and there is no truncation, corruption, or false aliasing of cache content.

3. The method recited in claim 2, further comprising the steps of making an arena available for subsequent use by marking the arena free in a pool header in volatile storage, and writing and synchronizing the pool header to non-volatile storage.

4. In a cache for information objects that comprises a directory table that indexes each of the information objects in one of a plurality of buckets, an open directory comprising a list of changes associated with each of the buckets, a set of volatile object aggregation buffers, and a set of disk-based object pools, a method for ensuring the integrity of cache storage in the presence of software failures, comprising the steps of:

periodically carrying out a garbage collection task that includes

evacuating desirable fragments of objects from arenas by deleting the metadata that references undesirable fragments of objects from the open directory;

synchronizing to disk metadata that references new locations of fragments of objects that result from the garbage collection task; and

evacuating the desirable fragments to an aggregation buffer;

whereby after a cache restart, all previously cached objects are consistent, in that pre-failure objects are either completely present or completely absent from the cache, and there is no truncation, corruption, or false aliasing of cache content.

5. In a cache for information objects comprising a directory table that indexes each of the information objects in one of a plurality of buckets, an open directory comprising a list of changes associated with each of the buckets, a set of volatile object aggregation buffers, and a set of disk-based object pools, a method of synchronizing the cache, comprising the steps of:

writing an information object to the cache by creating meta-data in the open directory and by writing and synchronizing data of the information object to non-volatile storage by performing the steps of

for each piece of meta-data in the open directory, determining whether the data the meta-data points to is already synchronized, and if so, then copying the piece of meta-data from the open directory to the directory table;

carrying out garbage collection on an arena by, for each fragment in the arena, deleting the meta-data that points to an undesirable fragment and synchronizing the meta-data that references new locations of fragments that result from the garbage collection;

modifying a pool header so as to mark the arena empty; and

writing and synchronizing the pool header to disk.

6. The method recited in claim 5, further comprising the steps of:

obtaining a length of the fragment from a message of a client that requests the information object from the cache;

identifying a selected arena having free space sufficient greater than the length of the fragment;

obtaining a lock on a selected aggregation buffer;

allocating space for the fragment in the selected arena; and

releasing the lock from the selected aggregation buffer; and

storing the fragment in the selected arena.

7. In a cache for information objects comprising a directory table that indexes each of the information objects in one of a plurality of blocks that is stored in one of a plurality of buckets, and an open directory comprising a list of changes associated with each of the buckets, a method of managing the cache, comprising the steps of:

(A) receiving a key that identifies an information object requested by a client of the cache;

(B) identifying a selected bucket from among the plurality of buckets that corresponds to the key and identifying a selected block from among the plurality of blocks that corresponds to the key;

(C) when the selected block is not being created or destroyed, storing a reader count of processes that are reading the selected block, and providing a copy of the selected block to the client.

8. The method recited in claim 7, further comprising the steps of:

(D) when the selected block is not being created or destroyed,

(D1) storing a writer count of processes that are writing the selected block;

(D2) marking a copy of the selected block as being modified; and

(D3) providing the copy of the selected block to the client.

9. The method recited in claim 8, further comprising the steps of:

(E) when the selected block is not deleted and the writer count and the reader count are zero,

(E1) initializing the selected block based on the key;

(E2) incrementing the writer count and the reader count; and

(E3) providing the copy of the selected block to the client.

10. The method recited in claim 9, further comprising the steps of:

(F) checking in the copy of the selected block to the cache by the steps of;

(F1) decrementing the writer count when the selected block is being modified, and decrementing the reader count otherwise;

(F2) storing the copy of the selected block in the open directory; and

(F3) marking the selected block as deleted when a delete checkin value is provided.

11. A method for maintaining the integrity of a cache, comprising the steps of:

in an open directory, storing meta-data that references object data that is to be written to non-volatile storage; and

for each piece of the meta-data in the open directory,

determining if the object data that the piece of the meta-data references has been synchronized to the non-volatile storage; and

if the object data that the piece of the meta-data references has been synchronized to the non-volatile storage, then writing the piece of the meta-data to a directory table that is associated with the cache.

12. The method recited in claim 11 wherein the object data is synchronized to the non-volatile storage by the steps of:

writing to an arena the object data that the piece of the meta-data references; and

moving an arena pointer associated with the area to reflect that the object data has been written to the arena.

13. The method recited in claim 11 further comprising the step of postponing updating an arena on the non-volatile storage until the changes taken by a garbage collection process in volatile storage are committed to the non-volatile storage.

14. The method of claim 13 wherein the garbage collection process comprises the steps of:

scanning target arenas;

identifying active fragments in the target arenas;

writing the active fragments contiguously to new arenas;

updating the directory table to reference new locations of the active fragments in the new areas.

15. A method for implementing a cache of objects, the method comprising the steps of:

concurrently maintaining (A) a first structure that stores meta-data for accessing objects durably stored in non-volatile storage, and (B) a second structure that stores meta-data for accessing objects durably stored in the non-volatile storage;

wherein the meta-data in the first structure includes meta-data that reflects modifications to objects made by operations (A) that durably store objects to the non-volatile storage, and (B) whose successful completion has not yet been verified;

wherein the meta-data in the second structure includes meta-data that reflects modifications to objects made by operations (A) that durably store objects to the non-volatile storage and (B) whose successful completion has been verified; and

moving, from the first structure to the second structure, meta-data that indicates that an object has been durably stored in the non-volatile storage in response to verifying successful completion of an operation that durably stores the object in the non-volatile storage.