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

• US 8,650,156 B1
• Filed: 12/23/2010
• Issued: 02/11/2014
• Est. Priority Date: 12/23/2010
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: McHugh, Jason G., Gattu, Praveen K., Ten-Pow, Michael A., Denny-Brown, Derek E. II
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): VU, THONG H
• Application Number:
  US12/978,256
• Time in Patent Office: 1,146 Days
• Field of Search: 707/737, 707/203, 707/728, 707/202, 726/5, 726/8
• US Class Current: 707/638
• 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 an instance of a data object, wherein storing the instance of the data object comprises;

receiving, from an entity other than the distributed storage system, a request to store the instance of the data object in the distributed storage system, wherein the request comprises a user key for the data object and a version identifier for the instance of the data object;

generating keymap information for the instance of the data object that maps the user key to a locator and the locator to the instance of the data object;

caching the keymap information at a keymap coordinator in the distributed storage system;

caching a latest symbolic key entry at the keymap coordinator, wherein the latest symbolic key entry comprises the version identifier for the instance of the data object and indicates that the instance of the data object is the latest version of the data object stored in the distributed storage system;

providing, responsive to a request to retrieve the latest version of the data object, the latest version of the data object, wherein the request does not specify the version of the data object to be obtained, wherein providing the latest version of the data object comprises;

receiving, from an entity other than the distributed storage system, the request to retrieve the 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;

determining the version identifier of the latest version of the data object dependent on the cached latest symbolic key entry; and

returning, based on the determined version identifier, the latest version of the data object having the user key.

2. The method of claim 1, wherein said determining the version identifier of the latest version of the data object comprises obtaining the version identifier from the latest symbolic key entry cached at the keymap coordinator.

3. The method of claim 1, further comprising:

prior to said caching the latest symbolic key entry at the keymap coordinator, determining that the instance of the data object is the latest version of the data object stored in the distributed storage system.

4. The method of claim 3, further comprising:

setting a flag to indicate that the latest symbolic key entry should be updated;

wherein said determining that the instance of the data object is the latest version of the data object is performed in response to the flag being set.

5. The method of claim 1, further comprising, prior to said receiving a request to retrieve the latest version of the data object:

receiving a request to store another instance of the data object in the distributed storage system, wherein the request comprises the user key for the data object and a version identifier for the other instance of the data object;

generating keymap information for the other instance of the data object;

caching the keymap information for the other instance of the data object at the keymap coordinator; and

updating the cached latest symbolic key entry at the keymap coordinator, wherein the updated latest symbolic key entry comprises the version identifier for the other instance of the data object and indicates that the other instance of the data object is the latest version of the data object stored in the distributed storage system;

wherein said determining the version identifier of the latest version of the data object comprises obtaining the version identifier from the updated latest symbolic key entry cached at the keymap coordinator.

6. A method, comprising:

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

caching keymap entries for one or more data object instances stored in the distributed storage system, wherein each keymap entry maps a user key to a locator and the locator to an instance of a data object having the user key, wherein multiple versions of the instance of the data object have the same user key;

caching a latest symbolic key entry for at least one of the user keys, wherein each latest symbolic key entry includes a version identifier for the latest version of the data objects stored in the distributed storage system having a particular user key;

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

determining the version identifier of the latest version of the data object dependent on whether a latest symbolic key entry for the specified user key is cached in the distributed storage system; and

returning keymap information for the latest version of the data object.

7. The method of claim 6,

wherein a latest symbolic key entry for the specified user key is cached in the distributed storage system;

and

wherein said determining the version identifier of the latest version of the data object comprises obtaining the version identifier from the latest symbolic key entry.

8. The method of claim 6, further comprising storing the keymap entries for one or more data object instances in persistent storage in the distributed storage system.

9. The method of claim 6,

wherein no latest symbolic key entry for the specified user key is cached in the distributed storage system;

and

wherein said determining the version identifier of the latest version of the data object comprises examining two or more keymap entries stored in persistent storage in the distributed storage system.

10. The method of claim 6, further comprising:

receiving a request to store keymap information for an instance of a data object having a new user key;

storing the keymap information for the instance of the data object having the new user key in persistent storage in the distributed storage system; and

creating a latest symbolic key entry for the new user key, wherein the latest symbolic key entry for the new user key comprises a version identifier for the instance of the data object having the new user key and indicates that the instance of the data object having the new user key is the latest version of the data object having the new user key stored in the distributed storage system.

11. The method of claim 6,

receiving a request to store keymap information for an instance of a data object having an existing user key;

determining whether it is possible that the instance of the data object having the existing user key is the latest version of the data objects stored in the distributed storage system having the existing user key; and

in response to determining that it is possible that the instance of the data object having the existing user key is the latest version of the data objects stored in the distributed storage system having the existing user key, setting a flag to indicate that a calculation of the latest version of the data objects stored in the distributed storage system having the existing user key should be attempted.

12. The method of claim 11,

wherein attempting to calculate the latest version of the data objects stored in the distributed storage system having the existing user key comprises:

storing a special sentinel value in a latest symbolic key entry for the existing user key;

examining one or more keymap entries stored in persistent storage; and

returning a response to the attempt.

13. The method of claim 12,

wherein the response includes an indication that the instance of the data object having the existing user key is the latest version of the data objects stored in the distributed storage system having the existing user key;

and

wherein the method further comprises;

replacing the special sentinel value stored in the latest symbolic key entry for the existing user key with a value indicating the version identifier of the instance of the data object having the existing user key.

14. The method of claim 12,

wherein the response includes an indication that the instance of the data object having the existing user key is not the latest version of the data objects stored in the distributed storage system having the existing user key or that it is unknown whether the instance of the data object having the existing user key is the latest version of the data objects stored in the distributed storage system having the existing user key;

and

wherein the method further comprises;

removing the latest symbolic key entry for the existing user key from the cache.

15. The method of claim 14, wherein said removing the latest symbolic key entry for the existing user key from the cache is performed in response to determining that there are no pending requests to access keymap information for data objects having the existing user key.

16. The method of claim 11, further comprising

prior to determining that it is possible that the instance of the data object having the existing user key is the latest version of the data objects stored in the distributed storage system having the existing user key, creating a cache entry for the instance of the data object having the existing user key, and storing a special sentinel value in the cache entry;

and

in response to determining that the instance of the data object having the existing user key is the latest version of the data objects stored in the distributed storage system having the existing user key, replacing the special sentinel value stored in the cache entry for the instance of the data object with keymap information for the instance of the data object.

17. The method of claim 6, wherein said caching keymap entries comprises storing the keymap entries on two or more computing 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.

18. The method of claim 17, wherein keymap entries for two or more data object instances having the same user key are stored on the same computing node in the distributed hash table.

19. 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 perform:

caching keymap entries for one or more data object instances stored in a distributed storage system, wherein each keymap entry maps a user key to a locator and the locator to an instance of a data object having the user key, wherein multiple versions of the instance of the data object have the same user key;

caching a latest symbolic key entry for at least one of the user keys, wherein each latest symbolic key entry includes a version identifier for the latest version of the data objects stored in the distributed storage system having a particular user key;

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

determining the version identifier of the latest version of the data object dependent on whether a latest symbolic key entry for the specified user key is cached in the distributed storage system; and

returning keymap information for the latest version of the data object.

20. The storage medium of claim 19,

wherein a latest symbolic key entry for the specified user key is cached in the distributed storage system;

and

wherein said determining the version identifier of the latest version of the data object comprises obtaining the version identifier from the latest symbolic key entry.

21. The storage medium of claim 19,

wherein when executed on the one or more computers, the program instructions further cause the one or more computers to perform storing the keymap entries for one or more data object instances in persistent storage in the distributed storage system;

wherein no latest symbolic key entry for the specified user key is cached in the distributed storage system; and

wherein said determining the version identifier of the latest version of the data object comprises examining two or more keymap entries stored in persistent storage in the distributed storage system.

22. The storage medium of claim 19, wherein when executed on the one or more computers, the program instructions further cause the one or more computers to perform:

receiving a request to store keymap information for an instance of a data object having a new user key;

storing the keymap information for the instance of the data object having the new user key in persistent storage in the distributed storage system; and

creating a latest symbolic key entry for the new user key, wherein the latest symbolic key entry for the new user key comprises a version identifier for the instance of the data object having the new user key and indicates that the instance of the data object having the new user key is the latest version of the data object having the new user key stored in the distributed storage system.

23. The storage medium of claim 19, wherein when executed on the one or more computers, the program instructions further cause the one or more computers to perform:

receiving a request to store keymap information for an instance of a data object having an existing user key;

determining whether it is possible that the instance of the data object having the existing user key is the latest version of the data objects stored in the distributed storage system having the existing user key; and

in response to determining that it is possible that the instance of the data object having the existing user key is the latest version of the data objects stored in the distributed storage system having the existing user key, setting a flag to indicate that a calculation of the latest version of the data objects stored in the distributed storage system having the existing user key should be attempted.

24. The storage medium of claim 23,

wherein attempting to calculate the latest version of the data objects stored in the distributed storage system having the existing user key comprises:

storing a special sentinel value in a latest symbolic key entry for the existing user key;

examining one or more keymap entries stored in persistent storage; and

returning a response to the attempt.

25. The storage medium of claim 24,

wherein the response includes an indication that the instance of the data object having the existing user key is the latest version of the data objects stored in the distributed storage system having the existing user key;

and

wherein when executed on the one or more computers, the program instructions further cause the one or more computers to perform;

replacing the special sentinel value stored in the latest symbolic key entry for the existing user key with a value indicating the version identifier of the instance of the data object having the existing user key.

26. The storage medium of claim 24,

wherein the response includes an indication that the instance of the data object having the existing user key is not the latest version of the data objects stored in the distributed storage system having the existing user key or that it is unknown whether the instance of the data object having the existing user key is the latest version of the data objects stored in the distributed storage system having the existing user key;

and

wherein when executed on the one or more computers, the program instructions further cause the one or more computers to perform;

removing the latest symbolic key entry for the existing user key from the cache.

27. The storage medium of claim 26, wherein said removing the latest symbolic key entry for the existing user key from the cache is performed in response to determining that there are no pending requests to access keymap information for data objects having the existing user key.

28. The storage medium of claim 23, wherein when executed on the one or more computers, the program instructions further cause the one or more computers to perform:

prior to determining that it is possible that the instance of the data object having the existing user key is the latest version of the data objects stored in the distributed storage system having the existing user key, creating a cache entry for the instance of the data object having the existing user key, and storing a special sentinel value in the cache entry; and

in response to determining that the instance of the data object having the existing user key is the latest version of the data objects stored in the distributed storage system having the existing user key, replacing the special sentinel value stored in the cache entry for the instance of the data object with keymap information for the instance of the data object.

29. A system, comprising:

a persistent data store that stores a plurality of data objects, wherein each of the plurality of data objects comprises a user key and a version identifier;

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 perform;

receiving a request to store keymap information for an instance of a data object to be stored in the persistent data store, wherein the request comprises a user key for the data object and a version identifier for the instance of the data object, and wherein the keymap information maps the user key to a locator and the locator to the instance of the data object, wherein multiple versions of the instance of the data object have the same user kev;

storing the keymap information in an entry in the cache for the instance of the data object;

storing a latest symbolic key entry in the cache, wherein the latest symbolic key entry comprises the version identifier for the instance of the data object and indicates that the instance of the data object is the latest version of the data object stored in the distributed storage system;

receiving a request to retrieve the 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;

determining the version identifier of the latest version of the data object dependent on the cached latest symbolic key entry; and

returning keymap information for the latest version of the data object.

30. The system of claim 29, wherein said determining the version identifier of the latest version of the data object comprises obtaining the version identifier from the latest symbolic key entry stored in the cache.

31. The system of claim 29, wherein when executed by the one or more processors, the program instructions further cause the one or more processors to perform:

prior to said caching the latest symbolic key entry at the keymap coordinator, determining that the instance of the data object is the latest version of the data object stored in the distributed storage system.

32. The system of claim 31, wherein when executed by the one or more processors, the program instructions further cause the one or more processors to perform:

setting a flag to indicate that the latest symbolic key entry should be updated;

wherein said determining that the instance of the data object is the latest version of the data object is performed in response to the flag being set.

33. The system of claim 29, wherein when executed by the one or more processors, the program instructions further cause the one or more processors to perform, prior to said receiving a request to retrieve the latest version of the data object:

receiving a request to store keymap information for another instance of the data object to be stored in the persistent data store, wherein the request comprises the user key for the data object and a version identifier for the instance of the data object, and wherein the keymap information maps the user key to a locator and the locator to the instance of the data object;

storing the keymap information for the other instance of the data object in an entry in the cache; and

updating the latest symbolic key entry in the cache, wherein the updated latest symbolic key entry comprises the version identifier for the other instance of the data object and indicates that the other instance of the data object is the latest version of the data object stored in the distributed storage system;

wherein said determining the version identifier of the latest version of the data object comprises obtaining the version identifier from the updated latest symbolic key entry stored in the cache.