US 11,537,516 B1Granted

Multi-tier cache for a distributed storage system

AssigneeAmazon Technologies, Inc.

InventorsTyler Michael Jung, Slavcho Georgiev Slavchev, Nishant Jain, Vishwas Narendra, Nikhil Shah, James Zuber, Sameer Choudhary, Christopher A. Stephens, Suchindra Yogendra Agarwal, Phillip H. Pruett

Life of this patent

Estimating the term…

patentgrep

Loading patent…

Abstract

Systems and methods are provided for using a distributed cache architecture with different methods to load balance requests depending upon whether a requested data item is a freely-requested item (e.g., a “hot key”). The cache may be implemented as a consistent hash ring, and most keys may be assigned to particular node based on a consistent hash. For hot key requests, the requests may be distributed among a subset of nodes rather than being assigned to a specific node using consistent hashing. When a witness service is used to ensure that cached data is fresh, verification requests for data regarding hot keys may be batched to avoid overloading the witness service with hot key requests.

Claims20

Dependent claims

A distributed storage system comprising:

a first caching layer comprising a load balancer and a plurality of hot key cache nodes;
a second caching layer comprising a management subsystem and consistent hash ring of a plurality of cache nodes;
and
a witness service storing a hash table comprising freshness data that associates a key of a data object with a sequence number representing a most recent change to the data object;
wherein the management subsystem comprises one or more computing devices and is configured to at least:
receive, from the first caching layer, a first request for a first data object, wherein the first request comprises a first key;
identify a first cache node, of the plurality of cache nodes, mapped to the first key based at least partly on a hash function;
send the first request to the first cache node;
receive, from the first caching layer, a second request for a second data object, wherein the second request comprises a second key, and wherein the second request is tagged as a hot key request;
identify a subset of the plurality of cache nodes based at least partly on one or more hashes of the second key;
select a second cache node of the subset of the plurality of cache nodes based at least partly on a pseudo-random number generator;
and
send the second request to the second cache node.

10 more elements

A computer-implemented method comprising:

under control of a computing system comprising memory and one or more computing devices configured to execute specific instructions:
receiving a first request for a first data object of a plurality of data objects, wherein the first request comprises a first key corresponding to the first data object;
identifying a first cache node of a consistent hash ring comprising a plurality of cache nodes, wherein the first cache node is identified based on a first mapping of the first key to the first cache node;
sending the first request to the first cache node;
receiving a second request for a second data object of the plurality of data objects, wherein the second request comprises a second key corresponding to the second data object, and wherein the second key is one of a plurality of hot keys;
selecting a second cache node of a subset of the plurality of cache nodes based at least partly on randomized selection data, wherein the subset of the plurality of cache nodes is associated with the second key;
and
sending the second request to the second cache node.

5 more elements

A system comprising:

a plurality of cache nodes;
and
one or more computing devices programmed by executable instructions to at least:
receive a first request for a first data object of a plurality of data objects, wherein the first request is associated with a first key corresponding to the first data object;
identify a first cache node of the plurality of cache nodes, wherein the first cache node is identified based on a first mapping of the first key to the first cache node;
send the first request to the first cache node;
receive a second request for a second data object of the plurality of data objects, wherein the second request is associated with a second key corresponding to the second data object, and wherein the second key is one of a plurality of hot keys;
select a second cache node of a subset of the plurality of cache nodes based at least partly on randomized selection data, wherein the subset of the plurality of cache nodes is associated with the second key;
and
send the second request to the second cache node.

7 more elements

Dependencies are inferred from the claim text.