Single-sided distributed cache system

• US 9,164,702 B1
• Filed: 09/07/2012
• Issued: 10/20/2015
• Est. Priority Date: 09/07/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Nesbit, Kyle, Diehl, Scott Fredrick
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): LI, HEWY H
• Application Number:
  US13/607,179
• Time in Patent Office: 1,138 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• 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 15/17331 Distributed shared memory [DSM], e.g. remote direct memory access [RDMA]
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/264 Remote server
• CPC Class Codes: G06F 2212/284 being distributed
• CPC Class Codes: G06F 2212/303 In peripheral interface, e.g. I/O adapter or channel
• CPC Class Codes: G06F 2212/463 File
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 9/466 Transaction processing
• 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 distributed cache system including a data storage portion, a data control portion, and a cache logic portion in communication with the data storage and data control portions. The data storage portion includes memory hosts, each having non-transitory memory and a network interface controller in communication with the memory for servicing remote direct memory access requests. The data control portion includes a curator in communication with the memory hosts. The curator manages striping of data across the memory hosts. The cache logic portion executes at least one memory access request to implement a cache operation. In response to each memory access request, the curator provides the cache logic portion a file descriptor mapping data stripes and data stripe replications of a file on the memory hosts for remote direct memory access of the file on the memory hosts through the corresponding network interface controllers.

Claims

1. A distributed cache system comprising:

a data storage portion having memory hosts, each memory host comprising;

non-transitory memory; and

a network interface controller in communication with the non-transitory memory for servicing remote direct memory access requests;

a data control portion having a curator separate and remote from the memory hosts and in communication with the memory hosts, the curator managing striping of data across the memory hosts by;

dividing a file into data stripes and replicating each data stripe; and

allocating storage of the data stripes and data stripe replications on the memory hosts; and

a cache logic portion in communication with the data storage and data control portions, the cache logic portion executing at least one memory access request to implement a cache operation, the cache logic portion comprising a cache service having a cache data layer storing cache data in files and a cache indexing layer indexing the cache data stored in the files, the cache service sharding the cache data into the files, each file storing cache entries, each cache entry comprising cache entry data, a cache tag, and a cache fingerprint, at least one of the files comprising a circular data file having a fixed size, a first-in-first-out queue having a front and a back, and a tail pointer providing an offset to the front of the queue;

wherein in response to the at least one memory access request to access the file, the curator providing the cache logic portion a file descriptor mapping location information of the data stripes and the data stripe replications of the file on the memory hosts for remote direct memory access of the file on the memory hosts and a key to allow access to the file on the memory hosts through the corresponding network interface controllers.

2. The distributed cache system of claim 1, wherein the cache indexing layer comprises a set associative tag map indexing the cache data stored in the files.

3. The distributed cache system of claim 2, wherein the set associative tag map maps cache tag fingerprints to locations of the corresponding cache data in the files.

4. The distributed cache system of claim 1, wherein the cache logic portion comprises:

a transaction interface for executing an atomic transaction including at least one of a read operation or a write operation on files stored on the memory hosts; and

a cache interface interfacing between a client and the transaction interface for executing at least one of a look up operation, an insert operation, or a remove operation using a transaction of the transaction interface.

5. The distributed cache system of claim 4, wherein the transaction executes a commit operation comprising:

for data chunks of a read set of the transaction;

reading data of the data chunks of the read set through remote direct memory access; and

determining a validity of the read data by evaluating a version and a lock of each data chunk of the read set; and

for data chunks of a write set of the transaction;

setting locks on the data chunks of the write set;

writing data to the locked data chunks through remote direct memory access;

releasing the locks of the locked data chunks; and

incrementing a version number of each released data chunk.

6. The distributed cache system of claim 5, wherein the transaction aborts the commit operation when at least one data chunk of the write set fails to receive a lock or when the read data is invalid.

7. The distributed cache system of claim 5, wherein, for any data chunks having an unreleased lock, the curator resets those data chunks to an uninitialized state and releases their locks.

8. The distributed storage system of claim 5, wherein the commit operation comprises:

reading existing data of the data chunks of the write set before writing new data to the data chunks of the write set; and

writing the existing data of the data chunks of the write set to a durable intent log.

9. The distributed cache system of claim 1, wherein the curator stores a file map mapping files to file descriptors.

10. The distributed cache system of claim 1, wherein the file descriptor includes at least one of a file state attribute providing a state of a file, a data chunks attribute providing a number of stripe replicas per stripe, a stripe length attribute providing a number of bytes per stripe, or a sub-stripe length attribute providing a number of bytes per sub-stripe.

11. The distributed cache system of claim 1, wherein the file descriptor includes an array of stripe protocol buffers, each describing a data stripe replica within a data stripe.

12. The distributed cache system of claim 11, wherein each stripe protocol buffer includes at least one of a stripe replica handle, an identity of the memory host holding the stripe replica, or a current state of the stripe replica.

13. A method of accessing a distributed cache system comprising memory hosts, the method comprising:

dividing, using a curator separate and remote from the memory hosts, a file into data stripes and replicating each data stripe;

allocating, using the curator, storage of the data stripes and data stripe replications on the memory hosts, each memory host comprising non-transitory memory and a network interface controller in communication with the non-transitory memory for servicing remote direct memory access requests;

storing data in files on the memory hosts and indexing the data stored in the files;

sharding the data into the files, each file storing cache entries, each cache entry comprising cache entry data, a cache tag, and a cache fingerprint, at least one of the files comprising a circular data file having a fixed size, a first-in-first-out queue having a front and a back, and a tail pointer providing an offset to the front of the queue;

receiving a cache operation from a client;

executing at least one memory access request;

for each memory access request to access the file, returning a file descriptor mapping location information of the data stripes and the data stripe replications of the file on the memory hosts for remote direct memory access of the file on the memory hosts and a key to allow access to the file on the memory hosts through the corresponding network interface controllers; and

executing on a computing processor a transaction comprising at least one of a read operation or a write operation on files stored on the memory hosts to implement the cache operation.

14. The method of claim 13, wherein the cache operation comprises at least one of a look up operation, an insert operation, or a remove operation.

15. The method of claim 13, further comprising mapping cache tag fingerprints to locations of the corresponding cache data in the files.

16. The method of claim 15, wherein the insert operation comprises:

receiving data;

receiving a cache tag associated with the data;

selecting a file for insertion of the data; and

executing a push back operation to add a cache entry including the data and the cache tag at a back of a queue of the selected circular file, the queue having a first-in-first-out eviction policy.

17. The method of claim 16, wherein the push back operation comprises:

reading an offset of a back of the queue of the file from a corresponding tail pointer;

writing the cache entry to the file at the offset; and

updating the offset in the tail pointer.

18. The method of claim 17, further comprising:

reading a region of the file being overwritten;

identifying overwritten cache tags; and

updating a set associative tag map.

19. The method of claim 18, wherein updating the set associative tag map comprises:

reading a set of the tag map corresponding to the cache tag of the written cache entry;

inserting an entry corresponding to the tag at a back of the set; and

dropping an entry at a front of the set.

20. The method of claim 18, wherein updating the set associative tag map comprises:

reading a set of the tag map corresponding to the evicted cache tags; and

removing entries from the set corresponding to the evicted cache tags.

21. The method of claim 13, further comprising:

receiving a cache tag;

reading a set of a tag map containing a fingerprint of the cache tag; and

removing an entry from the set of the tag map corresponding to the fingerprint.

22. The method of claim 13, further comprising accessing a file map mapping files to file descriptors to return the file descriptor in response to the memory access request.

23. The method of claim 13, further comprising:

for data chunks of a read set of the transaction;

reading data of the data chunks of the read set through remote direct memory access; and

determining a validity of the read data by evaluating a version and a lock of each data chunk of the read set; and

for data chunks of a write set of the transaction;

setting locks on the data chunks of the write set;

writing data to the locked data chunks through remote direct memory access;

releasing the locks of the locked data chunks; and

incrementing a version number of each released data chunk.

24. The method of claim 23, further comprising aborting the transaction when at least one data chunk of the write set fails to receive a lock or when the read data is invalid.

25. The method of claim 23, further comprising, for any data chunks having an unreleased lock, resetting those data chunks to an uninitialized state and releasing their locks.

26. The method of claim 23, further comprising rereading the data of the data chunks of the read set when the previous read is invalid.

27. The method of claim 23, further comprising

reading existing data of the data chunks of the write set before writing new data to the data chunks of the write set;

and

writing the existing data of the data chunks of the write set to a durable intent log.