Cached data replication for cache recovery

• US 9,880,909 B2
• Filed: 05/19/2016
• Issued: 01/30/2018
• 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): Peugh, Brian
• Assistant Examiner(s): CHAN, TRACY C
• Application Number:
  US15/159,710
• Publication Number:
  US 20160328301A1
• Time in Patent Office: 621 Days
• Field of Search: None
• 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. 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.