Management of cached object mapping information corresponding to a distributed storage system

• US 8,639,724 B1
• Filed: 07/31/2009
• Issued: 01/28/2014
• Est. Priority Date: 07/31/2009
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Sorenson, James Christopher III, Kakulapati, Gunavardhan, McHugh, Jason G., Vermeulen, Allan H.
• Primary Examiner(s): Perveen, Rehana
• Assistant Examiner(s): Waldron, Scott A
• Application Number:
  US12/533,873
• Time in Patent Office: 1,642 Days
• Field of Search: 707/796, 707/694, 707/770, 707/792
• US Class Current: 707/796
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 15/17331 Distributed shared memory [DSM], e.g. remote direct memory access [RDMA]
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 2212/154 Networked environment

Abstract

Systems and methods for managing mapping information for objects maintained in a distributed storage system are provided. The distributed storage system can include a keymap subsystem that manages the mapping information according to object keys. Requests for specific object mapping information are directed to specific keymap coordinators within the keymap subsystem. Each keymap coordinator can maintain a cache for caching mapping information maintained at various information sources. To manage the cache, the keymap system can utilize generation identifiers that identify the component within the distributed storage system that last updated information sources. Each keymap coordinator can determine whether cached version of keymap information is valid based on an analysis of generation identifiers.

Claims

1. A method of managing information associated with a stored object, the object represented by a key, the information including a keymap corresponding to the mapping of the key to one or more locators, each of the one or more locators associated with an instance of the object, the method comprising:

obtaining, at a keymap coordinator, an identifier associated with the keymap coordinator, wherein keymap information including the identifier associated with the keymap coordinator indicates that the keymap coordinator has most recently modified the keymap information;

obtaining a read request at the keymap coordinator for keymap information associated with a first key;

obtaining cached keymap information, at the keymap coordinator, corresponding to the read request, the cached keymap information including at least one generations identifier associated with the cached keymap information, each of the at least one generations identifiers identifying a component that accessed the keymap information associated with the first key at a time corresponding to creation of the generations identifier;

determining that the identifier associated with the keymap coordinator matches the most recent generations identifier of the at least one generations identifier associated with the cached keymap information, and in response to said determination, processing the obtained cached keymap information responsive to the read request;

determining that the identifier associated with the keymap coordinator does not match the most recent generations identifier of the at least one generations identifier associated with the cached keymap information, and in response to said determination;

transmitting a request from the keymap coordinator to a keymap information source for keymap information;

obtaining responsive keymap information at the keymap coordinator from the keymap information source;

updating the cached keymap information to correspond to the obtained responsive keymap information; and

processing the updated cached keymap information responsive to the read request.

2. The method as recited in claim 1, wherein the keymap information further includes a locator mapped to the first key.

3. The method as recited in claim 1, wherein the at least one generations identifier comprises two or more generations identifiers.

4. The method as recited in claim 1 further comprising:

responsive to obtaining the read request at the keymap coordinator, initiating a request for the cached keymap information to a cache component associated with the keymap coordinator.

5. A method of managing information associated with a stored object, the object represented by a key, the information including a keymap corresponding to the mapping of the key to one or more locators, each of the one or more locators associated with an instance of the object, the method comprising:

obtaining, at a keymap coordinator, an identifier associated with the keymap coordinator, wherein keymap information including the identifier associated with the keymap coordinator indicates that the keymap coordinator has most recently accessed the keymap information;

obtaining a read request at the keymap coordinator for keymap information associated with a first key;

obtaining cached keymap information, at the keymap coordinator from an associated cache component, corresponding to the read request, the cached keymap information including at least one generations identifier, the at least one generations identifier identifying at least a component that last accessed the keymap information associated with the first key;

determining whether the at least one generations identifier included within the cached keymap information matches the identifier associated with the keymap coordinator; and

if the at least one generations identifier included within the cached keymap information matches the identifier associated with the keymap coordinator, processing the obtained cached keymap information responsive to the read request; and

if the at least one generations identifier included within the cached keymap information does not match the identifier associated with the keymap coordinator, updating the cached keymap information and processing the updated cached keymap information responsive to the read request.

6. The method as recited in claim 5, wherein the keymap information further includes a locator mapped to the first key.

7. The method as recited in claim 5, wherein the at least one generations identifier comprises two or more generations identifiers.

8. The method as recited in claim 5, wherein keymap information including the identifier associated with the keymap coordinator further indicates that the keymap coordinator last modified said keymap information.

9. The method as recited in claim 5 further comprising:

prior to obtaining the cached keymap information, initiating a request to the cache component associated with the keymap coordinator for the cached keymap information.

10. The method as recited in claim 5, wherein updating the cached keymap information comprises:

transmitting a request from the keymap coordinator to a keymap information source for keymap information associated with the first key;

obtaining responsive keymap information at the keymap coordinator;

updating the cached keymap information at the cache component with the obtained responsive keymap information.

11. A method of managing information associated with a stored object, the object represented by a key, the information including a keymap corresponding to the mapping of the key to one or more locators, each of the one or more locators associated with an instance of the object, the method comprising:

obtaining a caller identifier, wherein keymap information including the caller identifier indicates that a caller associated with the caller identifier has most recently accessed the keymap information;

obtaining a modification request for modifying keymap information associated with a first key;

obtaining a generations identifier associated with the first key identifying a component that most recently accessed the keymap information associated with the first key;

determining whether the generations identifier associated with the first key matches the caller identifier;

if the generations identifier associated with the first key matches the caller identifier, processing the modification request; and

if the generations identifier associated with the first key does not match the caller identifier, generating a new generations identifier for the keymap information associated with the first key, wherein the new generations identifier identifies the caller as the component that most recently accessed the keymap information associated with the first key.

12. The method as recited in claim 11, wherein the keymap information associated with the first key further includes a locator mapped to the first key.

13. The method as recited in claim 11, wherein the caller is a keymap coordinator.

14. The method as recited in claim 11, wherein keymap information including the caller identifier further indicates that the caller most recently modified the keymap information.

15. The method as recited in claim 11, wherein the modification request comprises one of a write request and a delete request.

16. The method as recited in claim 11, wherein the new generations identifier comprises an identifier matching the caller identifier.

17. The method as recited in claim 11 further comprising associating the new generations identifier with the keymap information associated with the first key.

18. The method as recited in claim 11, wherein processing the modification request comprises processing the keymap information associated with the first key responsive to the modification request.

19. The method as recited in claim 18, wherein processing the keymap information comprises updating the keymap information associated with the first key responsive to the modification request.

20. A system of managing information associated with a stored object, the object represented by a key, the information including a keymap corresponding to the mapping of the key to one or more locators, each of the one or more locators associated with an instance of the object, the system comprising:

one or more computing devices configured to implement;

a keymap coordinator associated with a keymap identifier, wherein the keymap coordinator obtains a read request for keymap information associated with a first key, and wherein keymap information including the identifier associated with the keymap coordinator indicates that the keymap coordinator has most recently modified the keymap information including the identifier; and

a cache component that obtains a read request from the keymap coordinator for cached keymap information associated with the first key, the cached keymap information including at least one generations identifier associated with the first key, the at least one generations identifier identifying at least a component that last accessed the keymap information associated with the first key;

wherein the keymap coordinator is further operable to;

obtain the cached keymap information; and

determine whether the obtained generations identifier matches the keymap identifier;

if the obtained generations identifier matches the keymap identifier, process the obtained cached keymap information responsive to the read request; and

if the obtained generations identifier does not match the keymap identifier, update the cached keymap information and process the updated keymap information responsive to the read request.

21. A system of managing information associated with a stored object, the object represented by a key, the information including a keymap corresponding to the mapping of the key to one or more locators, each of the one or more locators associated with an instance of the object, the system comprising:

one or more computing devices configured to implement;

a caller associated with a caller identifier, wherein the caller obtains a modification request associated with a first key; and

a manager component that;

obtains the modification request associated with the first key from the caller, the modification request for modifying keymap information associated with the first key;

obtains a generations identifier identifying a component that most recently accessed the keymap information associated with the first key;

determines whether the obtained generations identifier matches the caller identifier;

if the obtained generations identifier matches the caller identifier, processes the modification request; and

if the obtained generations identifier does not match the caller identifier, generates a new generations identifier for the keymap information, the new generations identifier matching the caller identifier.

22. The system as recited in claim 21, wherein the caller comprises a keymap coordinator.