Management of object mapping information corresponding to a distributed storage system

• US 8,285,925 B1
• Filed: 07/31/2009
• Issued: 10/09/2012
• Est. Priority Date: 07/31/2009
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Sorenson, James Christopher III, Kakulapati, Gunavardhan, Vermeulen, Allan H., McHugh, Jason G.
• Primary Examiner(s): Campos, Yaima
• Assistant Examiner(s): Ahmed, Hamdy S
• Application Number:
  US12/533,978
• Time in Patent Office: 1,166 Days
• Field of Search: 711/118
• US Class Current: 711/113
• CPC Class Codes: G06F 3/0605 by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/0667 at data level, e.g. file, record or object virtualisation
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

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 information placeholders that replace previously cached keymap information while a request to modify keymap information is being processed by the information sources. Each keymap coordinator can process subsequently received keymap information read requests in the event an information placeholder is cached as the current cached keymap information.

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 a modification request at a keymap coordinator for modification of keymap information associated with a first key, wherein the keymap coordinator is associated with at least one keymap information source storing information mapping the first key to one or more locators;

transmitting the modification request to at least one keymap information source;

generating at least one keymap value placeholder associated with the keymap information requested to be modified, the at least one keymap value placeholder indicative of an unacknowledged request to modify keymap information associated with the first key;

initiating a storage request to a cache component associated with the keymap coordinator to store the at least one keymap value placeholder in cached keymap information associated with the first key, the cache component storing cached information associated with the at least one keymap information source;

determining whether the at least one keymap value placeholder in the cached keymap information associated with the first key may be updated with a value associated with the modification request, wherein the at least one keymap value placeholder is configured to be updated after completion of the modification request by the at least one keymap information source; and

if so, initiating an update request to the cache component to update the cached keymap information with the value associated with the modification request.

2. The method as recited in claim 1, wherein the modification request comprises a write request.

3. The method as recited in claim 2, wherein the write request comprises a request to change a value associated with the first key.

4. The method as recited in claim 2, wherein the write request comprises a request to change a value associated with the one or more of the locators mapped to the first key.

5. The method as recited in claim 1, wherein the modification request comprises a delete request.

6. The method as recited in claim 1, wherein the at least one keymap value placeholder corresponds to a null pointer.

7. The method as recited in claim 1, wherein the request to store the at least one keymap value placeholder in cached keymap information associated with the first key comprises a request to replace a current value in the cached keymap information with the at least one keymap value placeholder.

8. The method as recited in claim 1, wherein determining whether the at least one keymap value placeholder in the cached keymap information associated with the first key may be updated with a value associated with the modification request comprises determining whether keymap information at the at least one keymap information source has been modified in accordance with the modification request.

9. 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 read request at a keymap coordinator for keymap information associated with a first key, wherein the keymap coordinator is associated with at least one keymap information source storing information mapping the first key to one or more locators;

obtaining cached keymap information, at the keymap coordinator from an associated cache component, corresponding to the read request;

determining whether the obtained cached keymap information includes a keymap value placeholder, wherein a keymap value placeholder included within the cached keymap information is indicative of a prior unacknowledged request to modify keymap information associated with the first key in the at least one keymap information source and wherein the at least one keymap value placeholder is configured to be updated after completion of the modification request by the at least one keymap information source; and

if not, providing the obtained cached keymap information responsive to the read request.

10. The method as recited in claim 9, wherein the keymap value placeholder corresponds to a null pointer.

11. The method as recited in claim 9, wherein the prior unacknowledged request corresponds to a prior request to the at least one keymap information source to modify in the keymap information.

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

if the obtained cached keymap information includes a keymap value placeholder, processing the read request in view of the keymap value placeholder.

13. The method as recited in claim 12, wherein the keymap value placeholder is associated with timing information.

14. The method as recited in claim 13, wherein processing the read request in view of the keymap value placeholder comprises:

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

obtaining responsive keymap information at the keymap coordinator from the at least one keymap information source; and

comparing timing information associated with the obtained responsive keymap information with the timing information associated with the keymap value placeholder.

15. The method as recited in claim 14, wherein processing the read request in view of the keymap value placeholder further comprises:

if the timing information associated with the obtained responsive keymap information is greater than or equal to the timing information associated with the keymap value placeholder;

updating the cached keymap information at the cache component based on the obtained responsive keymap information; and

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

16. The method as recited in claim 14, wherein transmitting a request from the keymap coordinator to the at least one keymap information source for keymap information associated with the first key occurs after a predetermined lapse of time.

17. The method as recited in claim 12, wherein processing the read request in view of the keymap value placeholder comprises:

providing updated cached keymap information responsive to the read request once the keymap coordinator receives acknowledgement that the keymap information source has been updated with modified keymap information in response to a prior modification request.

18. 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:

a keymap coordinator that obtains a read request associated with a first key wherein the keymap coordinator is associated with at least one keymap information source storing keymap information mapping the first key to one or more locators; and

a cache component that stores cached keymap information associated with the at least one keymap information source, wherein the cache component obtains a request from the keymap coordinator for cached keymap information associated with the first key;

the keymap coordinator further operable to;

obtain the cached keymap information associated with the first key stored by the cache component;

determine whether the obtained cached keymap information includes a keymap value placeholder, wherein the keymap value placeholder is indicative of a previous modification request that has not been satisfied, wherein the previous modification request corresponds to a previous request to the at least one keymap information source to modify keymap information associated with the first key;

if not, provide the obtained cached keymap information responsive to the read request; and

if so, process the read request in view of the keymap value placeholder.

19. The system as recited in claim 18, wherein the keymap value placeholder corresponds to a null pointer.

20. The system as recited in claim 18, wherein the keymap value placeholder is associated with timing information.

21. The system as recited in claim 20, wherein processing the read request in view of the keymap value placeholder comprises:

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

obtaining responsive keymap information at the keymap coordinator from the at least one keymap information source; and

comparing timing information associated with the obtained responsive keymap information with the timing information associated with the keymap value placeholder.

22. The system as recited in claim 21, wherein processing the read request in view of the keymap value placeholder further comprises:

if the timing information associated with the obtained responsive keymap information is greater than or equal to the timing information associated with the keymap value placeholder;

updating the cached keymap information at the cache component based on the obtained responsive keymap information; and

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

23. The system as recited in claim 21, wherein transmitting a request from the keymap coordinator to the at least one keymap information source for keymap information associated with the first key occurs after a predetermined lapse of time.

24. The system as recited in claim 18, wherein processing the read request in view of the keymap value placeholder comprises:

providing updated cached keymap information responsive to the read request once the keymap coordinator receives acknowledgement that the keymap information source has been updated with modified keymap information in response to a prior modification request.