Distributed in-memory buffer cache system using buffer cache nodes

• US 9,880,933 B1
• Filed: 11/20/2013
• Issued: 01/30/2018
• Est. Priority Date: 11/20/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Gupta, Anurag Windlass, Allen, Matthew David
• Primary Examiner(s): Kim, Hong
• Application Number:
  US14/085,668
• Time in Patent Office: 1,532 Days
• Field of Search: 711120, 711129, 711143, 711113, 712 28
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 16/1858 Parallel file systems, i.e. file systems supporting multiple processors
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 2212/154 Networked environment
• CPC Class Codes: G06F 2212/263 Network storage, e.g. SAN or NAS
• CPC Class Codes: G06F 2212/284 being distributed
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• 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]
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching

Abstract

A separate distributed buffer cache system may be implemented for a storage client of a distributed storage system. Storage I/O requests may be sent from a storage client to one or more buffer cache nodes in a distributed buffer cache system that maintain portions of an in-memory buffer cache to which the requests pertain. The distributed buffer cache system may send the write requests on to the distributed storage system to be completed, and in response to receiving acknowledgements from the storage system, sending a completion acknowledgement back to the storage client. Buffer cache nodes may update buffer cache entries for received requests such that they are not available for reads until complete at the distributed storage system. For read requests where the buffer cache entries at the buffer cache node are invalid, valid data may be obtained from the distributed storage system and sent to the storage client.

Claims

1. A system, comprising:

a plurality of storage nodes, each comprising one or more respective processors, implementing a distributed storage system that maintains data for at least one storage client;

a plurality of buffer cache nodes, each comprising one or more respective processors, implementing a distributed buffer cache system that maintains an in-memory, write-through buffer cache for access operations directed toward the data maintained for the at least one storage client at the distributed storage system, wherein the buffer cache nodes are configured to access the data stored for the at least one storage client at the distributed storage system and maintain different portions of the buffer cache;

at least one compute node implementing the at least one storage client, configured to;

determine a storage I/O (Input/Output) write request to be performed at the distributed storage system;

identify one or more buffer cache nodes of the plurality of buffer cache nodes to send the storage I/O write request, wherein the identified one or more buffer cache nodes maintains at least a portion of the write-through buffer cache to which the write request pertains and buffer cache metadata reflecting a state of the portion of the buffer cache in a respective system memory of the one or more buffer cache nodes;

send the storage I/O write request to the one or more buffer cache nodes; and

receive from at least one of the one or more buffer cache nodes an acknowledgment that the storage I/O write is complete at the distributed storage system.

2. The system of claim 1, wherein the at least one node implementing the storage client is further configured to:

determine a storage I/O read request for specified data of the data maintained for the at least one storage client at the distributed storage system;

determine one or more buffer cache nodes of the plurality of buffer cache nodes to send the storage I/O read request, wherein the determined one or more buffer cache nodes maintain at least a portion of the write-through buffer cache to which the storage I/O read request pertains;

send the storage I/O read request to the determined one or more buffer cache nodes; and

receive from at least one of the one or more buffer cache nodes the specified data in order to service the storage I/O read request.

3. The system of claim 2, wherein at least one of the plurality of buffer cache nodes is configured to:

receive the storage I/O read request for the specified data from the at least one compute node implementing the at least one storage client;

determine that one or more buffer cache entries for the specified data are valid; and

respond to the at least one storage client with the specified data obtained from the one or more buffer cache entries.

4. The system of claim 2, wherein at least one of the plurality of buffer cache nodes is configured to:

receive the storage I/O read request for the specified data from the at least one compute node implementing the at least one storage client;

determine that one or more buffer cache entries for the specified data are invalid;

in response to determining that the one or more buffer cache entries for the specified data are invalid;

request the specified data from one or more storage nodes maintaining the specified data in the distributed storage system;

receive the specified data from the one or more storage nodes;

update the one or more buffer cache entries with the received specified data such that the one or more buffer cache entries are available for reads; and

respond to the at least one storage client with the received specified data.

5. The system of claim 1, wherein the storage client is a network-based database service, wherein the distributed storage system is a log-structured data store, and wherein the write request is a log record indicating an update to the data maintained at the log-structured data store for the network-based database service.

6. A method, comprising:

performing, by a plurality of computing devices;

maintaining an in-memory buffer cache among one or more buffer cache nodes, each comprising one or more respective processors, in a distributed buffer cache system for access operations received from at least one storage client and directed toward data stored at a distributed storage system for the storage client, each buffer cache node maintaining a plurality of buffer cache entries of a different portion of buffer cache and buffer cache metadata reflecting a respective state of buffer cache entries;

receiving, at a buffer cache node of the one or more buffer cache nodes, a storage I/O (input/output) write request to be performed at the distributed storage system from the at least one storage client;

in response to receiving the storage I/O write request;

sending the storage I/O write request to the distributed storage system to be performed;

based, at least in part, on one or more acknowledgments received for the storage I/O write request from the distributed storage system, determining that the storage I/O write request is complete at the distributed storage system;

updating one or more buffer cache entries and respective buffer cache metadata maintained at the buffer cache node according to the storage I/O write request, wherein the updated one or more buffer cache entries are not available for reads until the storage I/O write request is determined to be complete at the distributed storage system; and

acknowledging the completion of the write request to the at least one storage client.

7. The method of claim 6, wherein the distributed storage system comprises a plurality of storage nodes, wherein the one or more acknowledgements are received from one or more different storage nodes of the plurality of storage nodes, and wherein said determining that the storage I/O write request is complete at the distributed storage system, comprises determining that the one or more acknowledgments satisfy a write quorum requirement for the storage I/O write request.

8. The method of claim 6, further comprising:

identifying the one or more buffer cache entries as write-in-progress such that subsequent storage I/O read requests for data maintained in the one or more buffer cache entries are blocked;

in response to determining that the storage I/O write request is complete at the distributed storage system, identifying the one or more buffer cache entries as available for servicing subsequent storage I/O read requests.

9. The method of claim 6, further comprising:

receiving, at the buffer cache node, a storage I/O read request from the at least one storage client for specified data of the data maintained at the distributed storage system;

in response to receiving the storage I/O read request;

determining that one or more buffer cache entries for the specified data are valid; and

responding to the at least one storage client with the specified data obtained from the one or more buffer cache entries.

10. The method of claim 6, further comprising:

receiving, at the buffer cache node, a storage I/O read request for specified data of the data maintained at the distributed storage system;

in response to receiving the storage I/O read request;

determining that one or more buffer cache entries for the specified data are invalid;

requesting the specified data from the distributed storage system;

receiving the specified data from the distributed storage system;

updating the one or more buffer cache entries corresponding to the received specified data such that the one or more buffer cache entries are available for reads; and

responding to the at least one storage client with the specified data obtained from the distributed storage system.

11. The method of claim 10,

wherein the distributed storage system comprises a plurality of storage nodes, wherein the one or more acknowledgements are received from one or more different storage nodes of the plurality of storage nodes;

wherein the buffer cache metadata indicates particular storage nodes out of the plurality of storage nodes that have completed a particular storage I/O write request; and

wherein said requesting the specified data from the distributed storage system, comprises;

based, at least in part, on the buffer cache metadata, identifying one or more storage nodes of the plurality of storage nodes maintaining a particular view of the specified data associated with the storage I/O read request.

12. The method of claim 6, wherein the distributed storage system is a log-structured data store, wherein the storage I/O write request comprises a log record, and wherein said updating the one or more buffer cache entries, comprises applying the log record to data stored in the one or more buffer cache entries.

13. The method of claim 6, wherein the storage I/O write request comprises a data page, and wherein said updating the one or more buffer cache entries, comprises storing the data page in the one or more buffer cache entries.

14. The method of claim 6, wherein the distributed buffer cache system is a multi-tenant distributed buffer cache system such that a given buffer cache node caches different data for a plurality of different storage clients.

15. The method of claim 6, further comprising:

sending a request to a separate distributed computing system for one or more compute nodes in order to provision respective system memory of the one or more compute nodes for the distributed buffer cache system;

allocating respective portions of the in-memory buffer cache to the provisioned respective system memory of the one or more compute nodes; and

making the one or more compute nodes available for processing storage I/O requests from the at least one storage client.

16. The method of claim 15, further comprising:

receiving a reclamation request from the separate distributed computing system reclaiming at least one of the one or more compute nodes from the distributed buffer cache system;

in response to receiving the reclamation request from the separate distributed computing system reclaiming the at least one of the one or more compute nodes from the distributed buffer cache system;

de-allocating the respective portion of the in-memory buffer cache for the at least one of the one or more compute nodes to be reclaimed; and

making the at least one of the one or more compute nodes unavailable for processing storage I/O requests for the at least one storage client.

17. A non-transitory, computer-readable storage medium, storing program instructions that when executed by a plurality of computing devices cause the plurality of computing devices to implement at least one storage client that implements:

determining a storage I/O (input/output) write request to be performed at a distributed storage system maintaining data for the at least one storage client;

identifying one or more buffer cache nodes of a plurality of buffer cache nodes, each comprising one or more respective processors, that together implement a distributed buffer cache system to send the storage I/O write request, wherein the distributed buffer cache system maintains an in-memory buffer cache for access operations directed toward the data maintained for the at least one storage client at the distributed storage system, wherein the identified one or more buffer cache nodes maintain a different portion of the in-memory buffer cache and buffer cache metadata reflecting a state of the portion of the buffer cache;

sending the storage I/O write request to the one or more buffer cache nodes; and

receiving from at least one of the one or more buffer cache nodes an acknowledgment that the storage I/O write is complete at the distributed storage system.

18. The non-transitory, computer-readable storage medium of claim 17, wherein the in-memory buffer cache is apportioned among the plurality of buffer cache nodes according to a hashing scheme, and wherein, in said identifying the one or more buffer cache nodes in the distributed buffer cache system to send the storage I/O write request, the at least one storage client further implements determining the one or more buffer cache nodes according to the hashing scheme.

19. The non-transitory, computer-readable storage medium of claim 17, wherein the plurality of buffer cache nodes implementing the distributed caching system are a plurality of compute nodes providing reserve computing capacity for a separate distributed system.

20. The non-transitory, computer-readable storage medium of claim 17, wherein the at least one storage client further implements:

determining a storage I/O read request for specified data of the data maintained for the at least one storage client at the distributed storage system;

determining one or more buffer cache nodes of the plurality of buffer cache nodes to send the storage I/O read request, wherein the determined one or more buffer cache nodes maintain at least a portion of the in-memory buffer cache to which the storage I/O read request pertains;

sending the storage I/O read request to the determined one or more buffer cache nodes; and

receiving from at least one of the one or more buffer cache nodes the specified data in order to service the storage I/O read request.

21. The non-transitory, computer-readable storage medium of claim 17, wherein the at least one storage client further implements:

prior to receiving from the at least one of the one or more buffer cache nodes the specified data;

determining that a read latency threshold for the storage I/O read request is exceeded; and

in response to said determining, sending the storage I/O read request to the distributed storage system.

22. The non-transitory, computer-readable storage medium of claim 17, wherein another storage I/O write request to be performed at the distributed storage system maintaining the data for the storage client is received, wherein said identifying, said sending, and said receiving are performed for the other storage I/O write request, wherein at least one of the one or more buffer cache nodes sent the other storage I/O write request is different from the one or more buffer cache nodes sent the storage I/O write request.

23. The non-transitory, computer-readable storage medium of claim 17, wherein the storage client is a network-based database service and wherein the distributed storage system is a network-based, multi-tenant distributed storage service such that different respective data is stored for a plurality of different users of the network-based database service.