Cached data replication for cache recovery

Patent metadata

Field	Value
Publication number	US-9348752-B1
Application number	US-201213720919-A
Country	US
Kind code	B1
Filing date	Dec 19, 2012
Priority date	Dec 19, 2012
Publication date	May 24, 2016
Grant date	May 24, 2016

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. A system for cache recovery, the system comprising:
computer memory storing a caching structure, the caching structure including a plurality of entries for cached data; and
one or more processors configured to:
identify portions of the cached data deemed most valuable based in part on a deterministic evaluation algorithm;
store the portions of the cached data in a snapshot file on persistent non-transitory storage, the persistent non-transitory storage separate from the computer memory; and
update the cached data stored in the snapshot file based, at least in part, on when a time-to-live value associated with a determined number of entries stored in the snapshot file is above a threshold value;
wherein, in response to a restart of the system, the one or more processors are configured to load the portions of the cached data from the snapshot file stored on the persistent non-transitory storage into the caching structure on the computer memory.

2. The system of claim 1 , wherein the one or more processors are configured to identify the portions of the cached data by:
accessing a data structure that reflects a prioritization order of cached data in the caching structure; and
selecting, based in part on the prioritization order reflected in the data structure, an amount of the cached data that corresponds to a target size for the snapshot file.

3. The system of claim 1 , wherein the cached data deemed most valuable are most recently accessed data in the caching structure.

4. The system of claim 1 , wherein the cached data deemed most valuable are most accessed data in the caching structure.

5. The system of claim 1 , wherein a total size of the portions of the cached data in the snapshot file is significantly smaller than a total size of the cached data in the caching structure.

6. The system of claim 1 , wherein snapshot file size is determined based in part on a differential between throughput of the computer memory and the non-transitory storage.

7. The system of claim 1 , wherein the non-transitory storage is a mass storage device.

8. The system of claim 1 , wherein the snapshot file is stored on a mass storage device local to the system.

9. The system of claim 1 , wherein the snapshot file is stored on an external cache remote from the system.

10. A method for cache recovery, the method comprising:
identifying, by a computing system, portions of cached data in a caching structure deemed most valuable, the caching structure residing in memory on the computing system;
storing the identified portions of the cached data in a snapshot file on persistent non-transitory storage, the non-transitory storage separate from the memory on the computing system;
updating the cached data stored in the snapshot file based, at least in part, on when a time-to-live value associated with a determined number of entries stored in the snapshot file is above a threshold value; and
in response to a restart of the computing system, loading data from the snapshot file stored on the non-transitory storage into the caching structure residing in the memory on the computing system.

11. The method of claim 10 , wherein storing the identified portions of the cached data is performed by the computing system when a threshold value is reached.

12. The method of claim 10 , wherein storing the identified portions of the cached data is performed continuously by the computing system.

13. The method of claim 10 , wherein storing the identified portions of the cached data is performed by the computing system in response to an event.

14. The method of claim 10 , wherein the non-transitory storage is a storage device of the computing system.

15. The method of claim 10 , wherein the non-transitory storage is a storage device of another computing system.

16. The method of claim 10 , wherein the caching structure comprises:
a hash table configured to map key/value pairs, each key/value pair comprising a key portion and a value portion;
a doubly-linked list that reflects a prioritization order of data in the cache; and
one or more linked lists of storage blocks for storing data, wherein each value portion references a linked-list of one or more storage blocks.

17. The method of claim 10 , wherein identifying the portions of the cached data comprises:
accessing a data structure that reflects the prioritization order of cached data in the caching structure; and
selecting, based in part on the prioritization order reflected in the data structure, an amount of the cached data that corresponds to a target size for the snapshot file.

18. The method of claim 10 , wherein the cached data deemed valuable are most recently accessed data in the caching structure.

19. The method of claim 10 , wherein the cached data deemed most valuable are most accessed data in the caching structure.

20. The method of claim 10 , wherein a total size of the portions of the cached data in the snapshot file is significantly smaller than a total size of the cached data in the caching structure.

21. 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 persistent non-transitory storage, the persistent non-transitory storage separate from the memory on the computing system;
updating the cached data stored in the snapshot file based, at least in part, on when a time-to-live value associated with a determined number of entries stored in the snapshot file is above a threshold value; and
in response to a restart of the computing system, loading data from the snapshot file stored on the persistent non-transitory storage into the caching structure residing in memory on the computing system.

22. The non-transitory computer storage of claim 21 , wherein the caching structure further comprises:
a first data structure configured to track a prioritization order of data in the caching structure;
a second data structure configured to map key/value pairs, each key/value pair comprising a key portion and a value portion; and
one or more of a third data structure configured to track storage blocks for storing data.

23. The non-transitory computer storage of claim 21 , wherein the subset of cached data is no more than 10% of the cached data in the caching structure.

24. The non-transitory computer storage of claim 21 , wherein the subset of cached data is no more than 5% of the cached data in the caching structure.

25. The non-transitory computer storage of claim 21 , wherein the subset of cached data comprises most recently accessed data in the caching structure.

Assignees

• Amazon Tech Inc

Inventors

• Parakh Vishal
• Kanawati Antoun Joubran

Classifications

• G06F11/1451

  by selection of backup contents · CPC title

• G06F11/1441

  Resetting or repowering · CPC title

• G06F2201/84

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

• G06F2201/805

  Real-time · CPC title

• G06F12/0802 Primary

  Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches · CPC title