Consistent data storage in an object cache

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.

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.

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.

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.