Cache-failure-tolerant data storage system storing data objects with version code equipped metadata tokens

• US 6,502,108 B1
• Filed: 10/25/1999
• Issued: 12/31/2002
• Est. Priority Date: 10/25/1999
• Status: Expired due to Term

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Kishi, Gregory Tad, Day, III, Kenneth Fairclough, Dewey, Douglas William
• Primary Examiner(s): Kindred, Alford W.
• Application Number:
  US09/426,449
• Time in Patent Office: 1,163 Days
• Field of Search: 707/1-2, 707/6-10, 707/100, 707/103, 707/104, 707/201-206, 711/100-101, 711/108-135, 711/138, 711/161, 711/162
• US Class Current: 1/1
• CPC Class Codes: G06F 11/0751 Error or fault detection not based on redundancy power supply failures G06F1/30; network fault management H04L41/06
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

A data storage system stores data with a corresponding encapsulated metadata token in cache and/or base storage to protect against recalling stale data from base storage in the event of a cache failure and subsequent cache miss. A controller is coupled to a cache, base storage, and token database. After receiving a data object and associated write request, the controller assigns a version code to the data object. If the data object already exists, the controller advances the data object'"'"'s version code. A token, including the version code along with other items of metadata, is encapsulated for storage. Then, the controller stores the data object and encapsulated token in cache and/or base storage and updates the token database to cross-reference the data object with its version code. When the controller experiences a cache miss, there is danger in blindly retrieving the data object from base storage since the cache miss may have occurred due to cache failure before the data was de-staged, leaving a down-level version of the data object on base storage. This problem is avoided by comparing the data object'"'"'s version code contained in base storage to the version code listed for the data object in the token database. Only if the compared version codes match, the data object is read from base storage and provided as output.

Claims

1. A method of managing a data storage system that includes a cache, base storage, and token database, where the method comprises operations of:

responsive to the data storage system receiving a data object and an associated write request, performing operations including;

assigning a version code to the data object;

in at least one of the cache and the base storage, storing the data object along with information including the version code;

storing the version code in the token database in association with the data object; and

responsive to receiving a read request for the data object, performing operations including;

if the data object is present in the cache, reading the data object from the cache and providing the data object as output;

if the data object is not present in the cache,

reading the version code of the data object contained in the base storage and comparing said version code to the version code associated with the data object in the token database; and

only if the compared version codes match, reading the data object from the data object contained in the base storage and providing the data object as output.

2. The method of claim 1, where:

the operations further include encapsulating the data object with the information including the version code; and

the storing operation comprises storing the encapsulated data object.

3. The method of claim 1, where the operations further include encapsulating said information including the version code prior to the storing operation.

4. The method of claim 1, the operations further comprising:

if the compared version codes do not match, providing an error message.

5. The method of claim 1, the operation of assigning a version code to the data object comprising:

if a previous version of the received data object does not already reside in the data storage system, generating a new version code for the data object;

if a previous version of the received data object already resides in the data storage system, said previous version of the data object having an existing version code, advancing an existing version code of the data object.

6. The method of claim 5, where:

each version code corresponds to one level from a predetermined sequence of increasing levels;

the operation of advancing the existing version code comprises incrementing the version code to the next level in the sequence.

7. The method of claim 1, where:

each version code includes a data subpart and a properties subpart; and

the operations include changing the data subpart only when content of the data object is updated in the cache or the base storage, and changing the properties subpart only when prescribed characteristics of the data object are updated without affecting content of the data object in storage.

8. The method of claim 4, where the operation of comparing the version code of the data object contained in storage to the version code associated with the data object in the token database comprises:

comparing the version codes'"'"' data subparts without regard to the version codes'"'"' properties subparts.

9. The method of claim 1, the base storage being one or more serially accessible data storage media.

10. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for managing a data storage system that includes a cache, base storage, and token database, where the method comprises operations of:

responsive to the data storage system receiving a data object and an associated write request, performing operations including;

assigning a version code to the data object;

in at least one of the cache and the base storage, storing the data object along with information including the version code;

storing the version code in the token database in association with the data object; and

responsive to receiving a read request for the data object, performing operations including;

if the data object is present in the cache, reading the data object from the cache and providing the data object as output;

if the data object is not present in the cache,

reading the version code of the data object contained in the base storage and comparing said version code to the version code associated with the data object in the token database; and

only if the compared version codes match, reading the data object from the data object contained in the base storage and providing the data object as output.

11. The medium of claim 10, where:

the operations further include encapsulating the data object with the information including the version code; and

the storing operation comprises storing the encapsulated data object.

12. The medium of claim 10, where the operations further include encapsulating said information including the version code prior to the storing operation.

13. The medium of claim 10, the operations further comprising:

if the compared version codes do not match, providing an error message.

14. The medium of claim 10, the operation of assigning a version code to the data object comprising:

if a previous version of the received data object does not already reside in the data storage system, generating a new version code for the data object;

if a previous version of the received data object already resides in the data storage system, said previous version of the data object having an existing version code, advancing an existing version code of the data object.

15. The medium of claim 14, where:

each version code corresponds to one level from a predetermined sequence of increasing levels;

the operation of advancing the existing version code comprises incrementing the version code to the next level in the sequence.

16. The medium of claim 10, where:

each version code includes a data subpart and a properties subpart; and

the operations include changing the data subpart only when content of the data object is updated in the cache or the base storage, and changing the properties subpart only when prescribed characteristics of the data object are updated without affecting content of the data object in storage.

17. The medium of claim 13, where the operation of comparing the version code of the data object contained in storage to the version code associated with the data object in the token database comprises:

comparing the version codes'"'"' data subparts without regard to the version codes'"'"' properties subparts.

18. The medium of claim 10, the base storage being one or more serially accessible data storage media.

19. A logic circuit of multiple interconnected electrically conductive elements configured to perform a method to manage a data storage system that includes a cache, base storage, and token database, the method comprising operations of:

responsive to the data storage system receiving a data object and an associated write request, performing operations including;

assigning a version code to the data object;

in at least one of the cache and the base storage, storing the data object along with information including the version code;

storing the version code in the token database in association with the data object; and

responsive to receiving a read request for the data object, performing operations including;

if the data object is present in the cache, reading the data object from the cache and providing the data object as output;

if the data object is not present in the cache,

reading the version code of the data object contained in the base storage and comparing said version code to the version code associated with the data object in the token database; and

only if the compared version codes match, reading the data object from the data object contained in the base storage and providing the data object as output.

20. A data storage system, comprising:

cache storage;

base storage;

a token database; and

a controller coupled to the cache storage, base storage, and token database, where the controller is configured to perform operations to manage data storage in the cache and base storage, the operations comprising;

responsive to the data storage system receiving a data object and an associated write request, performing operations including;

assigning a version code to the data object;

in at least one of the cache and the base storage, storing the data object along with information including the version code;

storing the version code in the token database in association with the data object; and

responsive to receiving a read request for the data object, performing operations including;

if the data object is present in the cache, reading the data object from the cache and providing the data object as output;

if the data object is not present in the cache,

reading the version code of the data object contained in the base storage and comparing said version code to the version code associated with the data object in the token database; and

only if the compared version codes match, reading the data object from the data object contained in the base storage and providing the data object as output.

21. The system of claim 20, where the controller is configured such that:

the operations further include encapsulating the data object with the information including the version code; and

the storing operation comprises storing the encapsulated data object.

22. The system of claim 20, where the controller is configured such that the operations further include encapsulating said information including the version code prior to the storing operation.

23. The system of claim 20, the controller being configured such that the operations further comprise:

if the compared version codes do not match, providing an error message.

24. The system of claim 20, the controller being configured such that the operation of assigning a version code to the data object comprises:

if a previous version of the received data object does not already reside in the data storage system, generating a new version code for the data object,

if a previous version of the received data object already resides in the data storage system, said previous version of the data object having an existing version code, advancing an existing version code of the data object.

25. The system of claim 24, where the controller is configured such that:

each version code corresponds to one level from a predetermined sequence of increasing levels;

the operation of advancing the existing version code comprises incrementing the version code to the next level in the sequence.

26. The system of claim 20, where the controller is configured such that:

each version code includes a data subpart and a properties subpart; and

the operations include changing the data subpart only when content of the data object is updated in the cache or the base storage, and changing the properties subpart only when prescribed characteristics of the data object are updated without affecting content of the data object in storage.

27. The system of claim 23, where the controller is configured such that the operation of comparing the version code of the data object contained in storage to the version code associated with the data object in the token database comprises:

comparing the version codes'"'"' data subparts without regard to the version codes'"'"' properties subpart.

28. The system of claim 20, the base storage being one or more serially accessible data storage media.

29. A data storage system, comprising:

cache storage;

base storage;

a token database; and

controller means, coupled to the cache storage, base storage, and token database, for managing data storage in the cache and base storage by;

responsive to the data storage system receiving a data object and an associated write request, performing operations including;

assigning a version code to the data object;

in at least one of the cache and the base storage, storing the data object along with information including the version code;

storing the version code in the token database in association with the data object; and

responsive to receiving a read request for the data object, performing operations including;

if the data object is present in the cache, reading the data object from the cache and providing the data object as output;

if the data object is not present in the cache,

reading the version code of the encapsulated data object contained in the base storage and comparing said version code to the version code associated with the data object in the token database; and

only if the compared version codes match, reading the data object from the encapsulated data object contained in the base storage and providing the data object as output.

30. A method of managing a data storage system that includes a cache and base storage to prevent recalling stale data from the base storage in the event of a cache failure, the method comprising operations of:

responsive to the data storage system receiving data objects and associated write requests from one or more hosts, performing the following operations for each subject data object;

assigning a version code to the subject data object, the version code distinguishing the data object from other data objects that comprise versions of the same item of data as the subject data object;

in at least one of the cache and the base storage, storing the subject data object along with information including the version code;

storing the version code in a version-code-database in association with the subject data object; and

responsive to receiving one or more hosts'"'"' read requests for data objects, performing the following operations for each such read request;

if the requested data object is present in the cache, reading the requested data object from the cache and outputting the requested data object to the requesting host;

if the requested data object is not present in the cache,

reading the version code stored along with the requested data object contained in the base storage and comparing said version code to the version code associated with the requested data object in the version-code-database; and

only if the compared version codes match, reading the requested data object from the base storage and providing the requesting host with an output of the data object read from the base storage.

31. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform operations for managing a data storage system that includes a cache and base storage to prevent recalling stale data from the base storage in the event of a cache failure, the operations comprising:

responsive to the data storage system receiving data objects and associated write requests from one or more hosts, performing the following operations for each subject data object;

assigning a version code to the subject data object, the version code distinguishing the data object from other data objects that comprise versions of the same item of data as the subject data object;

in at least one of the cache and the base storage, storing the subject data object along with information including the version code;

storing the version code in a version-code-database in association with the subject data object; and

responsive to receiving one or more hosts'"'"' read requests for data objects, performing the following operations for each such read request;

if the requested data object is present in the cache, reading the requested data object from the cache and outputting the requested data object to the requesting host;

if the requested data object is not present in the cache,

reading the version code stored along with the requested data object contained in the base storage and comparing said version code to the version code associated with the requested data object in the version-code-database; and

only if the compared version codes match, reading the requested data object from the base storage and providing the requesting host with an output of the data object read from the base storage.

32. A data storage system, comprising:

cache storage;

base storage;

a version-code-database;

a controller programmed to perform operations to prevent recalling stale data from the base storage in the event of a cache failure, the operations comprising;

responsive to receiving data objects and associated write requests from one or more hosts, performing the following operations for each subject data object;

assigning a version code to the subject data object, the version code distinguishing the data object from other data objects that comprise versions of the same item of data as the subject data object;

in at least one of the cache and the base storage, storing the subject data object along with information including the version code;

storing the version code in the version-code-database in association with the subject data object; and

responsive to receiving one or more hosts'"'"' read requests for data objects, performing the following operations for each such read request;

if the requested data object is present in the cache, reading the requested data object from the cache and outputting the requested data object to the requesting host;

if the requested data object is not present in the cache,

reading the version code stored along with the requested data object contained in the base storage and comparing said version code to the version code associated with the requested data object in the version-code-database; and

only if the compared version codes match, reading the requested data object from the base storage and providing the requesting host with an output of the data object read from the base storage.