Management of object mapping information corresponding to a distributed storage system

• US 8,621,182 B1
• Filed: 07/31/2009
• Issued: 12/31/2013
• 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.
• Primary Examiner(s): MACKALL, LARRY T
• Application Number:
  US12/533,869
• Time in Patent Office: 1,614 Days
• Field of Search: 711/216, 711/E12.018
• US Class Current: 711/216
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or 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. Additionally, the keymap coordinators can optimize cache entries by maintaining selected mapping information while identifying object sources that correspond to differences from the selected mapping information.

Claims

1. A system for managing objects stored in a distributed storage system comprising:

a computing device, having a processor and a memory, the computing device implementing a service interface component for managing requests associated with objects maintained by the distributed storage system;

a computing device, having a processor and a memory, the computing device implementing a keymap subsystem, the keymap subsystem obtaining requests for keymap information, wherein the keymap information corresponds to a mapping of a key associated with an object with one or more identifiers of instances of the object on the distributed storage system, the keymap subsystem including;

a plurality of managers for maintaining the keymap information, wherein a first manager maintains a first identifier of an instance of the object on the storage distributed system, wherein a second manager maintains a second identifier of an instance of the object on the distributed storage system, and wherein the first and second identifiers are distinct, and

one or more keymap coordinators for processing requests associated with object keys, each keymap coordinator maintaining a cache corresponding to the keymap information, wherein the cache includes the first identifier and an indication of a difference between the first identifier and the second identifier without maintaining the second identifier;

wherein the keymap coordinators, in response to a request for the keymap information, utilize at least the first identifier and the indication of the difference between the first identifier and the second identifier to determine keymap information responsive to the request;

a computing device, having a processor and a memory, the computing device implementing one or more consistent based hashing components for generating a consistent based hashing scheme assigning the one or more keymap coordinators to ranges of hash values derived from object keys; and

a computing device, having a processor and a memory, the computing device implemented a storage node interface for interfacing with one or more storage nodes associated with the distributed storage system.

2. The system as recited in claim 1, wherein the one or more consistent based hashing components further update modifications to the consistent based hashing scheme.

3. The system as recited in claim 1, wherein the cache further includes an indication that a third manager also maintains the first identifier.

4. The system as recited in claim 3, wherein the keymap coordinators further utilize a quorum based analysis to determine keymap information responsive to the request.

5. The system as recited in claim 4, wherein the keymap coordinators refresh the cache based at least in part on a result of the quorum based analysis.

6. The system as recited in claim 4, wherein the keymap coordinators utilize a quorum based analysis by comparing an indication of a number of managers that maintain the first identifier and an indication of a number of managers that maintain an identifier different than the first identifier.

7. The system as recited in claim 6, wherein the keymap coordinator determines a quorum value if the number of managers that maintain the first identifier exceeds the number of managers that maintain an identifier different than the first identifier.

8. The system as recited in claim 6, wherein the first identifier corresponds to a most recent location of an instance of the object on the storage distributed system.

9. A system for managing objects stored in a distributed storage system comprising:

a computing device, having a processor and a memory, the computing device implementing;

a plurality of managers for maintaining keymap information mapping a key associated with an object with one or more identifiers of instances of the object on the distributed storage system, wherein a first manager maintains a first identifier of an instance of the object on the distributed storage system, wherein a second manager maintains a second identifier of an instance of the object on the distributed storage system, and wherein the first and second identifiers are distinct; and

one or more keymap coordinators for processing requests associated with object keys, each keymap coordinator maintaining a proxy cache corresponding to cached keymap information, the cached keymap information comprising the first identifier and an indication of a difference between the first identifier and the second identifier without maintaining the second identifier.

10. The system as recited in claim 9, wherein the cache further includes an indication of a number of managers that maintain the first identifier.

11. The system as recited in claim 9, wherein the keymap coordinators utilize a quorum based analysis to determine keymap information based at least in part on the number of managers that maintain the first identifier.

12. The system as recited in claim 11, wherein the keymap coordinators refresh the cached keymap information based at least in part on a result of the quorum based analysis.

13. The system as recited in claim 11, wherein the keymap coordinator utilizes a quorum based analysis at least in part by comparing the number of managers that maintain the first identifier and a number of managers that maintain an identifier different than the first identifier.

14. The system as recited in claim 13, wherein the keymap coordinators determine a quorum value if the number of managers that maintain the first identifier exceeds the number of managers that maintain an identifier different than the first identifier.

15. The system as recited in claim 9, wherein the keymap coordinators initiate a synchronization for all managers that maintain an identifier different than the first identifier.

16. A method for managing objects stored in a distributed storage system comprising:

obtaining a request for modifying keymap information associated with an object, the keymap information corresponds to a mapping of a key associated with an object with one or more identifiers of instances of the object on the distributed storage system, the request identifying a key associated with the object;

identifying cached keymap information responsive to the request, the cached keymap information representative of a logical cache of manager components, wherein the cached keymap information includes;

a first identifier of an instance of the object on the distributed storage system, wherein the first identifier is maintained by at least a first manager component, and

an indication of a difference between the first identifier and a second identifier of an instance of the object on the distributed storage system, wherein the indication is not independently representative of the second identifier, and wherein the second identifier is maintained by at least a second manager component; and

transmitting responsive information utilizing the cached keymap information.

17. The method as recited in claim 16 further comprising transmitting consistent based hashing information to at least one additional component in the distributed storage system.

18. The method as recited in claim 16, wherein identifying the cached keymap information responsive to the request includes utilizing a quorum based analysis based at least in part on the first identifier and the indication of a difference between the first identifier and the second identifier.

19. The method as recited in claim 16, wherein the logical cache corresponds to a logical cache for each manager maintaining keymap information.

20. The method as recited in claim 16 further comprising causing a refresh of the cached keymap information based at least in part on the indication of the difference between the first identifier and a second identifier.

21. The method as recited in claim 16, wherein identifying cached keymap information responsive to the request includes identifying a single identifier of an instance of the object on the distributed storage system identifier of an instance of the object on the distributed storage system responsive to the request.

22. The method as recited in claim 16, wherein identifying cached keymap information responsive to the request includes conducting a quorum based analysis based at least in part on a number of indications of a difference between the first identifier and at least one additional identifier.

23. The method as recited in claim 22, wherein conducting a quorum based analysis includes selecting the first identifier as a quorum value if a number of managers associated with the first identifier exceeds the number of indications of a difference between the first identifier and at least one additional identifier.

24. The method as recited in claim 16 further comprising:

selecting a keymap coordinator from one or more keymap coordinators based in accordance a consistent based hashing scheme assigning the one or more keymap coordinators to ranges of hash values derived from object keys; and

causing the transmission of the request to the selected keymap coordinator.

25. The method as recited in claim 16 further comprising initiating a synchronization of the manager components based at least in part on the indication of a difference between the first identifier and the second identifier.