Managing cached information corresponding to a distributed storage system

• US 9,875,212 B1
• Filed: 01/27/2014
• Issued: 01/23/2018
• 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, III, James Christopher, Kakulapati, Gunavardhan, McHugh, Jason G., Vermeulen, Allan H.
• Primary Examiner(s): Waldron, Scott A
• Application Number:
  US14/165,441
• Time in Patent Office: 1,457 Days
• 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 cached information maintained in a distributed storage system are provided. Requests for information within the distributed storage system are directed to specific coordinators. Each coordinator can maintain cached version of information maintained at various information sources within the distributed storage system. To manage the cache, the system can utilize generation identifiers that identify the component within the distributed storage system that last updated information sources. Each coordinator can determine whether cached version of information is valid based on an analysis of generation identifiers.

Claims

1. A system comprising:

non-transitory data storage comprising a data cache, the data cache including a cached version of a first information item stored within a distributed storage system; and

a first coordinator computing device comprising a processor, the first coordinator computing device being included within a plurality of coordinators configured to facilitate access to data on the distributed storage system, the first coordinator computing device in communication with the data cache and associated with a first coordinator identifier identifying information on the distributed storage system that the first coordinator computing device has most recently modified, the first coordinator computing device configured to;

receive a request from a client computing device for the first information item;

obtain a generations identifier identifying one of the plurality of coordinators that most recently modified the first information item;

process the generations identifier to determine that the generations identifier matches the first coordinator identifier; and

in response to the determination that the generations identifier matches the first coordinator identifier, transmit the cached version of the first information item to the client computing device.

2. The system of claim 1, wherein the first coordinator computing device is further configured to:

process the generations identifier to determine that the generations identifier does not match the first coordinator identifier; and

in response to the determination that the generations identifier does not match the first coordinator identifier;

retrieve an updated version of the first information item from the distributed storage system; and

transmit the updated version of the first information item to the client computing device.

3. The system of claim 2, wherein the first coordinator computing device is further configured to update the data cache based at least in part on the updated version of the first information.

4. The system of claim 1, wherein the first information item comprises a keymap mapping a key to an instance of a data object on the distributed storage system.

5. The system of claim 4, wherein the first coordinator computing device is a keymap coordinator computing device associated with the key.

6. The system of claim 5, wherein the first coordinator computing device is further associated with a range of additional keys.

7. The system of claim 1, wherein the first information item is further associated with additional generation identifiers identifying individual coordinators computing devices that have previously modified the first information item.

8. A computer-implemented method comprising:

maintaining a first coordinator identifier at a first coordinator of a plurality of coordinators configured to facilitate access to data on a distributed storage system, wherein the first coordinator identifier identifies information on the distributed storage system that the first coordinator has most recently modified;

receiving a request from a computing device for a first information item stored within the distributed storage system;

obtaining a generations identifier identifying one of the plurality of information coordinators that most recently modified the first information item;

processing the generations identifier to determine that the generations identifier matches the first coordinator identifier; and

in response to the determination that the generations identifier matches the first coordinator identifier;

retrieving a cached version of the first information item from a storage cache of the first coordinator; and

transmitting the cached version of the first information item to the computing device.

9. The computer-implemented method of claim 8 further comprising:

processing the generations identifier to determine that the generations identifier does not match the first coordinator identifier; and

in response to the determination that the generations identifier does not match the first coordinator identifier, transmitting a version of the first information item retrieved from the distributed storage system to the computing device.

10. The computer-implemented method of claim 9 further comprising updating the storage cache of the first coordinator based at least in part on the version of the first information item retrieved from the distributed storage system.

11. The computer-implemented method of claim 8 further comprising:

receiving a request to modify the first information item; and

generating an updated generations identifier for the first information item, the updated generations identifier identifying the first coordinator as last modifying the first information item.

12. The computer-implemented method of claim 11, wherein

the request to modify the first information item comprises at least one of a write request or a delete request.

13. The computer-implemented method of claim 8, wherein the first information item comprises a keymap mapping a key to an instance of a data object on the distributed storage system.

14. The computer-implemented method of claim 13, wherein the first coordinator is a keymap coordinator associated with the key.

15. Non-transitory computer-readable storage media including computer-executable instructions comprising:

first computer-executable instructions that, when executed by a processor of a first coordinator, cause the processor to maintain, within a storage cache, a cached version of a first information item stored within a distributed storage system; and

second computer-executable instructions that, when executed by the processor, cause the processor to;

receive a request from a computing device for the first information item;

obtain a generations identifier identifying one of a plurality of coordinators associated with the distributed storage system that most recently modified the first information item on the distributed storage system;

process the generations identifier to determine that the generations identifier matches a coordinator identifier associated with the first coordinator, the coordinator identifier identifying information on the distributed storage system that the first coordinator has most recently modified; and

in response to the determination that the generations identifier matches the coordinator identifier, transmit the cached version of the first information item to the computing device.

16. The non-transitory computer-readable storage media of claim 15, wherein the second computer-executable instructions further cause the processor to:

process the generations identifier to determine that the generations identifier does not match the first coordinator identifier; and

in response to the determination that the generations identifier does not match the first coordinator identifier, transmit a version of the first information item retrieved from the distributed storage system to the computing device.

17. The non-transitory computer-readable storage media of claim 15, wherein the second computer-executable instructions further cause the processor to update the storage cache based at least in part on the version of the first information item retrieved from the distributed storage system.

18. The non-transitory computer-readable storage media of claim 15, wherein the first information item is further associated with additional generation identifiers identifying individual coordinators that have previously modified the first information item.

19. The non-transitory computer-readable storage media of claim 15, wherein the computer-executable instructions further comprise third computer-executable instructions that, when executed by the processor, cause the processor to:

receive a request to modify the first information item; and

generate an updated generations identifier for the first information item, the updated generations identifier identifying the first coordinator as last modifying the first information item.

20. The non-transitory computer-readable storage media of claim 15, wherein the third computer-executable instructions further cause the processor to verify, prior to generation of the updated generations identifier, that a current generations identifier for the first information item does not match the coordinator identifier.

21. The non-transitory computer-readable storage media of claim 15, wherein the first information item comprises a keymap mapping a key to an instance of a data object on the distributed storage system.