System and method for fetching the latest versions of stored data objects

• US 10,528,537 B2
• Filed: 01/22/2018
• Issued: 01/07/2020
• Est. Priority Date: 12/23/2010
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: McHugh, Jason G., Gattu, Praveen Kumar, Ten-Pow, Michael A., Denny-Brown, II, Derek Ernest
• Primary Examiner(s): Spieler, William
• Application Number:
  US15/877,126
• Publication Number:
  US 20180189336A1
• Time in Patent Office: 715 Days
• Field of Search: 707638
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/1873 Versioning file systems, temporal file systems, e.g. file system supporting different historic versions of files
• CPC Class Codes: G06F 16/219 Managing data history or versioning querying versioned data G06F16/2474; querying temporal data G06F16/2477

Abstract

A distributed storage system may store data object instances in persistent storage and may cache keymap information for those data object instances. The system may cache a latest symbolic key entry for some user keys of the data object instances. When a request is made for the latest version of stored data object instances having a specified user key, the latest version may be determined dependent on whether a latest symbolic key entry exists for the specified user key, and keymap information for the latest version may be returned. When storing keymap information, a flag may be set to indicate that a corresponding latest symbolic key entry should be updated. The system may delete a latest symbolic key entry for a particular user key from the cache in response to determining that no other requests involving the keymap information for data object instances having the particular user key are pending.

Claims

1. A method, comprising:

performing, by a computer system that stores a plurality of data objects in a distributed storage system;

storing keymap entries for a plurality of data object versions stored in the distributed storage system, wherein keymap entries map a user key for a respective data object to a locator and the locator to a particular version of the data object;

wherein when a new version of a respective data object is created, associating the new version with a version identifier indicating an ordering of the new version with other versions of the respective data object;

wherein the keymap entries for versions of a data object are ordered according to respective version identifiers;

receiving a request to retrieve a latest version of a data object, wherein the request specifies a user key for the requested data object but does not include a version identifier of the latest version of the requested data object;

in response to receiving the request;

locating the latest version of the requested data object based on the ordering of keymap entries associated with versions of the requested data object; and

returning, in response to the request, the latest version of the data object.

2. The method of claim 1, wherein the version identifier comprises a generation time for the respective data object version and wherein the keymap entries are ordered according to respective generation times for data object versions.

3. The method of claim 2, wherein said locating the latest version of the requested data object comprises locating the latest version of the requested data object based on the leading entry of the ordered keymap entries.

4. The method of claim 2, further comprising ordering keymap entries for a plurality of versions of the requested data object, comprising:

ensuring that the leading entry of the sorted keymap entries identifies an implicit version stored in the distributed storage system prior to versioning being enabled for the data object; and

ordering one or more other versions according to their respective version identifiers;

wherein said locating the version identifier of the latest version comprises locating the latest version according to a next keymap entry following the key map entry identifying the implicit version.

5. The method of claim 1, wherein said locating the latest version of the requested data object is performed in response to determining that a latest symbolic key entry for the user key is not cached in the distributed storage system.

6. The method of claim 1, further comprising caching, subsequent to said locating the latest version of the requested data object, a latest symbolic key entry for the user key, wherein the latest symbolic key entry includes a version identifier for the latest version of the data object.

7. The method of claim 6, further comprising:

receiving another request to retrieve a latest version of the data object, wherein the request comprises the user key for the data object but does not include a version identifier of the latest version of the data object; and

in response to determining the latest symbolic key entry is stored in the cache for the user key, returning keymap information stored in the cache for the latest version of the data object.

8. The method of claim 1, further comprising caching the keymap entries in a plurality of caches each of which caches a subset of the keymap entries for the distributed storage system.

9. The method of claim 1, wherein said locating the latest version of the requested data object comprises:

sending, to one or more storage nodes in a distributed storage system, a request specifying the user key; and

wherein said determining the version identifier of the latest version of the requested data object is performed by the one or more storage nodes.

10. The method of claim 9, further comprising:

wherein said storing keymap entries comprises storing the keymap entries on two or more storage nodes of the computer system in a distributed hash table, and wherein each keymap entry is indexed in the distributed hash table by hash value generated from at least a portion of a composite key that includes the user key and that uniquely identifies a data object instance stored in the distributed storage system;

identifying the one or more storage nodes based at least in part on a hash value generated from at least a portion of a composite key that includes the user key; and

wherein said sending the request specifying the user key to one or more storage nodes in a distributed storage system comprises sending the request to the identified one or more storage nodes.

11. A non-transitory, computer-readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to implement:

storing keymap entries for a plurality of data object versions stored in the distributed storage system, wherein keymap entries map a user key for a respective data object to a locator and the locator to a particular version of the data object;

wherein when a new version of a respective data object is created, associating the new version with a version identifier indicating an ordering of the new version with other versions of the respective data object;

wherein the keymap entries for versions of a data object are ordered according to respective version identifiers;

receiving a request to retrieve a latest version of a data object, wherein the request specifies a user key for the requested data object but does not include a version identifier of the latest version of the requested data object;

in response to receiving the request;

locating the latest version of the requested data object based on the ordering of keymap entries associated with versions of the requested data object;

returning, in response to the request, the latest version of the data object.

12. The non-transitory, computer-readable storage medium of claim 11, wherein the version identifier comprises a generation time for the respective data object version and wherein the keymap entries are ordered according to respective generation times for data object versions.

13. The non-transitory, computer-readable storage medium of claim 12, wherein said locating the latest version of the requested data object comprises locating the latest version of the requested data object based on the leading entry of the ordered keymap entries.

14. The non-transitory, computer-readable storage medium of claim 11, wherein said locating the latest version of the requested data object is performed in response to determining that a latest symbolic key entry for the user key is not cached in the distributed storage system.

15. The non-transitory, computer-readable storage medium of claim 11, further comprising:

caching, subsequent to said locating the latest version of the requested data object, a latest symbolic key entry for the user key, wherein the latest symbolic key entry includes a version identifier for the latest version of the data object.

16. A system, comprising:

a distributed data store that stores a plurality of data objects;

a cache;

one or more processors; and

a memory coupled to the one or more processors and storing program instructions that when executed by the one or more processors cause the one or more processors to;

store keymap entries for a plurality of data object versions stored in the distributed storage system, wherein keymap entries map a user key for a respective data object to a locator and the locator to a particular version of the data object;

wherein when a new version of a respective data object is created, associating the new version with a version identifier indicating an ordering of the new version with other versions of the respective data object;

wherein the keymap entries for versions of a data object are ordered according to respective version identifiers;

receive a request to retrieve a latest version of a data object, wherein the request specifies a user key for the requested data object but does not include a version identifier of the latest version of the requested data object;

in response to receiving the request;

locate the latest version of the requested data object based on the ordering of keymap entries associated with versions of the requested data object; and

return, in response to the request, the latest version of the data object.

17. The system of claim 16, wherein the version identifier comprises a generation time for the respective data object version and wherein the program instructions further cause the one or more processors to:

sort the keymap entries according to respective generation times for data object versions.

18. The system of claim 17, wherein to locate the latest version of the requested data object, the program instructions further cause the one or more processors to:

locate the latest version of the requested data object based on the leading entry of the ordered keymap entries.

19. The system of claim 16, further comprising a cache configured to store a plurality of caches each configured to cache a subset of the keymap entries for the distributed storage system.

20. The system of claim 16, further comprising:

one or more storage nodes;

wherein to locate the latest version of the requested data object, the program instructions further cause the one or more processors to send, to the one or more storage nodes, a request specifying the user key; and

wherein the one or more storage nodes are configured to determine the version identifier of the latest version of the data object dependent on an ordering of the keymap entries for the plurality of versions of the data object.