Cached data replication for cache recovery

Patent metadata

Field	Value
Publication number	US-9880909-B2
Application number	US-201615159710-A
Country	US
Kind code	B2
Filing date	May 19, 2016
Priority date	Dec 19, 2012
Publication date	Jan 30, 2018
Grant date	Jan 30, 2018

Abstract

Processes are disclosed for embodiments of a caching system to utilize a snapshot file or other limited size data structure to store a portion of the data stored in a cache. The snapshot file can be stored on persistent or otherwise non-transitory storage so that, even in case of a restart, crash or power loss event, the data stored in the snapshot file persists and can be used by the caching system after starting up. The snapshot file can then be used to restore at least some data into the cache in cases where the cached data in the cache is lost. For example, in cases of a cold-start or restart, the caching system can load data from the snapshot file into the empty cache. This can increase the number of cache hits since the cache is repopulated with useful data at startup.

First claim

What is claimed is:

1. Non-transitory computer storage having stored thereon instructions that, when executed by a computer system, cause the computer system to perform operations comprising:
identifying, by a computing system, a subset of cached data in a caching structure, the caching structure residing in memory on the computing system;
storing the identified subset of the cached data in a snapshot file in a persistent storage, wherein in response to a restart of the computing system, data stored in the snapshot file can be loaded into the caching structure;
determining a percentage of cached data items stored in the snapshot file that exceed a measure of age; and
updating at least a portion of the data stored in the snapshot file in response to the percentage exceeding a threshold value.

2. The non-transitory computer storage of claim 1 , wherein the snapshot file persists in the persistent storage after a system crash or power loss event.

3. The non-transitory computer storage of claim 1 , wherein the persistent storage corresponds to an external cache accessible by the computer system via a network.

4. The non-transitory computer storage of claim 1 , wherein the measure of age associated with the determined amount of data corresponds to a likelihood that the determined amount of data may generate cache hits.

5. The non-transitory computer storage of claim 1 , wherein a size of the snapshot file is based at least in part on a rate differential between throughput of the memory on the computing system and the persistent non-transitory storage.

6. A computer-implemented method for managing cache recovery in a caching structure residing in memory of a computing system, the method comprising:
identifying a subset of cached data in the caching structure;
storing the identified subset of the cached data in a snapshot file in a data repository separate from the memory of the computing system, wherein in response to a restart of the computing system, data stored in the snapshot file can be loaded into the caching structure;
determining a percentage of cached data items stored in the snapshot file that exceed a measure of age; and
updating at least a portion of the data stored in the snapshot file in response to the percentage exceeding a threshold value,
wherein the method is implemented by a computing device under control of computer-executable code.

7. The computer-implemented method of claim 6 , wherein the caching structure comprises a first data structure configured to track a prioritization order of data in the caching structure.

8. The computer-implemented method of claim 7 , wherein the first data structure includes a doubly-linked list.

9. The computer-implemented method of claim 7 , wherein identifying the subset of cached data comprises traversing the first data structure in accordance with a size of the snapshot file.

10. The computer-implemented method of claim 7 , wherein updating at least a portion of the data stored in the snapshot file comprises traversing updated first data structure.

11. The computer-implemented method of claim 10 , wherein the updated first data structure includes data updated during cache accesses.

12. The computer-implemented method of claim 6 , wherein the caching structure comprises a second data structure configured to map key/value pairs, each key/value pair comprising a key portion and a value portion.

13. The computer-implemented method of claim 12 , wherein storing the identified subset of the cached data in the snapshot file comprises writing target data to the snapshot file in conjunction with a read lock on a target entry of the second data structure.

14. The computer-implemented method of claim 13 further comprising creating a new entry for temporarily storing new data to be added to the target entry.

15. The computer-implemented method of claim 14 further comprising merging the new entry with the caching structure after writing the target data to the snapshot file.

16. A system for cache recovery management, the system comprising:
computer memory for storing a caching structure, the caching structure including a plurality of entries for cached data; and
one or more processors configured to:
identify a subset of the cached data in the caching structure;
store the identified subset of the cached data in a snapshot file in a persistent data storage, wherein in response to a restart of a computing system associated with the caching structure, data stored in the snapshot file can be loaded into the caching structure;
determine a percentage of cached data items stored in the snapshot file that exceed a measure of age; and
update at least a portion of the data stored in the snapshot file in response to the percentage exceeding a threshold value.

17. The system of claim 16 , wherein the persistent storage is a storage device of the computing system.

18. The system of claim 16 , wherein the persistent storage is a storage device of another computing system.

19. The system of claim 16 , wherein the caching structure comprises at least one linked list indicating storage blocks for storing the cached data.

20. The system of claim 16 , wherein the measure of age associated with the determined amount of data corresponds to a likelihood that the determined amount of data may generate cache hits.

Assignees

• Amazon Tech Inc

Inventors

• Parakh Vishal
• Kanawati Antoun Joubran

Classifications

• G06F11/1441

  Resetting or repowering · CPC title

• G06F11/1451

  by selection of backup contents · CPC title

• G06F2201/84

  Using snapshots, i.e. a logical point-in-time copy of the data · CPC title

• G06F12/0804

  with main memory updating (G06F12/0806 takes precedence) · CPC title

• G06F2212/1032

  Reliability improvement, data loss prevention, degraded operation etc · CPC title