Cache map with sequential tracking for invalidation

Patent metadata

Field	Value
Publication number	US-11106593-B2
Application number	US-201916506102-A
Country	US
Kind code	B2
Filing date	Jul 9, 2019
Priority date	Mar 25, 2016
Publication date	Aug 31, 2021
Grant date	Aug 31, 2021

Abstract

The described technology is directed towards efficiently invalidating cached data (e.g., expired data) in a hash-mapped cache, e.g., on a timed basis. As a result, data is able returned from the cache without checking for whether that data is expired, (if desired and acceptable), because if expired, the data is only briefly expired since the last invalidation run. To this end, a data structure such as a linked list is maintained to track information representative of hash-mapped cache locations of a hash-mapped cache, in which the information tracks a sequential order of entering data into each hash-mapped cache location. An invalidation run is performed on part of the hash mapped cache, including using the tracking information to invalidate a sequence of one or more cache locations, e.g., only the sequence of those locations that contain expired data.

First claim

What is claimed is:

1. A system comprising,
a processor; and
a memory that stores executable instructions that, when executed by the processor, facilitate performance of operations, the operations comprising:
maintaining information representative of hash-mapped cache locations of a hash-mapped cache, in which the information tracks a sequential order of entering data into the hash-mapped cache locations; and
performing an invalidation run on at least part of the hash mapped cache, the performing comprising using the information representative of the hash-mapped cache locations to invalidate data in one or more hash-mapped cache locations based on respective expiration time values associated with respective ones of the one or more hash mapped cache locations,
wherein the using the information representative of the hash-mapped cache locations to invalidate the data the in one or more hash-mapped cache locations comprises using the information to invalidate a set of cache data entries that are expired, and
wherein the performing the invalidation run comprises stopping the invalidation run when the information points to a hash-mapped cache location having a cache data entry that is not expired.

2. The system of claim 1 , wherein the performing the invalidation run comprises using the information to invalidate a set of cache data entries that will be expired within a certain time.

3. The system of claim 1 , wherein the performing the invalidation run comprises using the information to invalidate a set of cache data entries that are within an expiration time window, or using the information to invalidate a set of cache data entries based upon a number of cache entries or a fraction of total cache entries.

4. The system of claim 1 , wherein the maintaining the information representative of the cache locations comprises maintaining a doubly linked list having a plurality of nodes, including maintaining a node for each cache location having valid data, each node including one node pointer to a next node, a cache pointer to its corresponding cache location in the hash-mapped cache, and another node pointer to a previous node.

5. The system of claim 1 , wherein the maintaining the information representative of the cache locations comprises maintaining a linked list having a plurality of nodes, including maintaining a node for each cache location having valid data, each node including a node pointer to a next node and a cache pointer to its corresponding cache location in the hash-mapped cache.

6. The system of claim 5 , wherein the performing the invalidation run comprises:
a) selecting a node representing an oldest position in the in the sequential order as a currently selected node,
b) using the cache pointer in the currently selected node to find a corresponding cache location,
c) determining whether the cache data entry at the corresponding cache location is expired, and
in response to determining that the cache data entry at the corresponding cache location is expired, invalidating the cache data entry at the corresponding cache location, using the node pointer in the currently selected node to select a next node as the currently selected node, and returning to step b), and
in response to determining that the cache data entry at the corresponding cache location is not expired, maintaining information of the currently selected node to represent the oldest position in the in the sequential order, and ending the invalidation run.

7. The system of claim 1 , wherein the performing the invalidation run comprises triggering the invalidation run based upon one or more criteria.

8. The system of claim 1 , wherein the operations further comprise receiving a request to access data in the hash-mapped cache, and in response to the request, performing a hash computation based upon at least part of the request to determine a location in the hash-mapped cache, and if data exists in the location, returning the data from the location, without checking for expiration of that data.

9. The system of claim 1 , wherein the operations further comprise receiving a request to access data in the hash-mapped cache, and in response to the request, performing a hash computation based upon at least part of the request to determine a location in the hash-mapped cache, and if data exists in the location and is not expired, returning the data from the location.

10. A system, comprising:
a hash-mapped data cache containing data entries;
a tracking data structure that maintains an order of locations of the data entries as entered into the hash-mapped data cache; and
an invalidator, the invalidator configured to access the tracking data structure to invalidate a set of one or more data entries based upon an expiration time value associated with each data entry and the order that the data entries were entered into the cache, wherein the invalidator is triggered at a rate that is selectable to not impact performance of data lookup in the hash-mapped data cache or to reduce any impact of the performance of the data lookup in the hash-mapped data cache.

11. The system of claim 10 , wherein the tracking data structure comprises a doubly linked list of nodes having cache pointers to locations of the data entries in the hash mapped data cache.

12. The system of claim 10 , wherein the tracking data structure comprises a singly linked list of nodes having cache pointers to locations of the data entries in the hash mapped data cache.

13. The system of claim 10 , wherein the hash-mapped data cache comprises an in-memory cache, and further comprising a request handler that requests data from the hash-mapped data cache, including data that is expired based on an associated expiration value but has not yet invalidated by the invalidator.

14. The system of claim 10 wherein the invalidator comprises an asynchronous process.

15. One or more machine-readable storage media having machine-executable instructions, which when executed perform operations, the operations comprising:
a) maintaining a hash-mapped cache with locations for cached data;
b) maintaining a data structure having a plurality of nodes, including maintaining a node for each cache location having valid data, each node including a node pointer to a next node and a cache pointer to its corresponding cache location in the hash-mapped cache, in which the node order in the data structure corresponds to an order of entering data into the hash-mapped cache locations;
c) performing an invalidation run, including selecting a starting node as a currently selected node;
d) using the cache pointer in the currently selected node to find a corresponding cache location;
e) determining whether the cache data entry at the corresponding cache location, based on an expiration time value associated with the cache data entry, is to be invalidated, comprising determining whether the cache data entry is a cache data entry corresponding to data entered within a specified time window, and
in response to determining that the cache data entry at the corresponding cache location is to be invalidated, invalidating the cache data entry at the corresponding cache location, using the node pointer in the currently selected node to select a next node as the currently selected node, and returning to step d), and
in response to determining that the cache data entry at the corresponding cache location is not to be invalidated, ending the invalidation run.

16. The one or more machine-readable storage media of claim 15 , wherein the determining whether the cache data entry at the corresponding cache location is t

Assignees

• Home Box Office Inc

Inventors

• Busayarat Sata

Classifications

• G06F2212/1016

  Performance improvement · CPC title

• G06F12/0864

  using pseudo-associative means, e.g. set-associative or hashing · CPC title

• G06F12/0891 Primary

  using clearing, invalidating or resetting means · CPC title

• G06F12/121

  using replacement algorithms · CPC title

• G06F12/123

  with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list · CPC title