Cached data replication for cache recovery

• US 9,348,752 B1
• Filed: 12/19/2012
• Issued: 05/24/2016
• Est. Priority Date: 12/19/2012
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Parakh, Vishal, Kanawati, Antoun Joubran
• Primary Examiner(s): Queler, Adam M
• Assistant Examiner(s): Chan, Tracy
• Application Number:
  US13/720,919
• Time in Patent Office: 1,252 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1441 Resetting or repowering
• CPC Class Codes: G06F 11/1446 Point-in-time backing up or restoration of persistent data
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• 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/24552 Database cache management
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G06F 2212/281 Single cache
• CPC Class Codes: G06F 2212/284 being distributed
• CPC Class Codes: G06F 2212/313 In storage device
• CPC Class Codes: G06F 2212/314 In storage network, e.g. network attached cache
• CPC Class Codes: G06F 2212/608 Details relating to cache mapping

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.

Claims

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.