Preventing race condition from causing stale data items in cache

Patent metadata

Field	Value
Publication number	US-9674296-B2
Application number	US-201313927027-A
Country	US
Kind code	B2
Filing date	Jun 25, 2013
Priority date	Jul 9, 2012
Publication date	Jun 6, 2017
Grant date	Jun 6, 2017

Abstract

A data cache server may process requests from a data cache client to put, get, and delete data items into or from the data cache server. Each data item may be based on data in a data store. In response to each request to put a data item into the data cache server, the data cache server may determine whether any of the data in the data store on which the data item is based has or may have changed; put the data item into the data cache memory if none of the data in the data store on which the data item is based has been determined to have or maybe to have changed, and not put the data item into the data cache memory if data in the data store on which the data item is based has been determined to have or maybe to have changed.

First claim

The invention claimed is:

1. A data cache server for processing requests from a data cache client to put, get, and delete data items into or from the data cache server, each data item being based on data in a data store, the data cache server comprising:
a data cache memory that has a configuration that stores data items; and
a processing system, including a processor, that has a configuration that:
in response to each request to put a data item into the data cache server:
determines whether any of the data in the data store on which the data item is based has changed;
puts the data item into the data cache memory if none of the data in the data store on which the data item is based has been determined to have changed; and
does not put the data item into the data cache memory if data in the data store on which the data item is based has been determined to have changed;

in response to each request to get a data item from the data cache server, reads the requested data item from the data cache memory and delivers it to the data cache client that requested the data item, if the requested data item is present in the data cache memory; and
in response to each request to delete a data item from the data cache server, deletes the requested data item from the data cache memory, if it is present in the data cache memory,
wherein the processing system has a configuration that, in response to each request to get a data item from the data cache server, determines whether the requested data items is in the data cache memory and, if not, reports the miss to the data cache client that sent the request to get the data item, along with the miss time at which the miss occurred.

2. The data cache server of claim 1 wherein the processing system has a configuration that, in response to each request to delete a data item, stores a delete time at which the request to delete the data item is processed.

3. The data cache server of claim 2 wherein the processing system has a configuration that, in response to each request to delete a data item, checks whether an earlier delete time for that data item is in cache memory and, if so, changes the stored delete time for that data item to the current time.

4. The data cache server of claim 2 wherein the processing system has a configuration that deletes each delete time from cache memory when the difference between the current time and the stored delete time exceeds a pre-determined threshold.

5. The data cache server of claim 4 wherein the processing system has a configuration that dynamically adjusts the pre-determined threshold based on real time measurements of the time it takes a data item to be created from data in the data store and delivered to the data cache server.

6. The data cache server of claim 2 wherein:
one request to put a data item into the data cache server includes a miss time indicative of a time at which a previously request to get the data item from the data cache server was unsuccessful; and
the processing system has a configuration that, in response to the one request to put, does not put the data item into the data cache memory if the miss time is before a stored delete time for the data item.

7. The data cache server of claim 2 wherein the processing system has a configuration that deletes delete times from cache memory when needed to free up storage.

8. The data cache server of claim 1 wherein:
one request to put a data item into the data cache server includes a miss time indicative of a time at which a previously request to get the data item from the data cache server was unsuccessful; and
each data item in the data cache memory is stored along with a key value and a storage time at which the data item was stored in the data cache memory; and
the processing system has a configuration that, in response to the one request to put, does not put the data item into memory if:
there is another data item in the data cache memory with the same key value as the data item that is requested to be put; and
the miss time of the data item that is requested to be put is before the storage time of the other data item with the same key value.

9. The data cache server of claim 1 wherein:
one request to put a data item into the data cache server includes a miss time indicative of a time at which a previously request to get the data item from the data cache server was unsuccessful; and
the processing system has a configuration that, in response to the request to put, stores the miss time with the data item in the data cache memory.

10. The data cache server of claim 1 wherein the processing system has a configuration that deletes data items in the data cache memory to free up space in the data cache memory and, when it does, saves the time at which each data item is deleted.

11. A non-transitory, tangible, computer-readable storage medium containing a program of instructions that causes a data cache server running the program of instructions to process requests from a data cache client to put, get, and delete data items into or from the data cache server, each data item being based on data in a data store, including:
in response to each request to put a data item into the data cache server:
determine whether any of the data in the data store on which the data item is based has changed;
put the data item into a data cache memory if none of the data in the data store on which the data item is based has been determined to have changed; and
not put the data item into the data cache memory if data in the data store on which the data item is based has been determined to have changed;

in response to each request to get a data item from the data cache server, read the requested data item from the data cache memory and deliver it to the data cache client that requested the data item, if the requested data item is present in the data cache memory; and
in response to each request to delete a data item from the data cache server, delete the requested data item from the data cache memory, if it is present in the data cache memory,
wherein the program of instructions causes the data cache server running the program of instructions to, in response to each request to get a data item from the data cache server, determine whether the requested data items is in the data cache memory and, if not, report the miss to the data cache client that sent the request to get the data item, along with the miss time at which the miss occurred.

12. The computer-readable storage medium of claim 11 wherein the program of instructions causes the data cache server running the program of instructions to, in response to each request to delete a data item, store a delete time at which the request to delete the data item is processed.

13. The computer-readable storage medium of claim 12 wherein the program of instructions causes the data cache server running the program of instructions to, in response to each request to delete a data item, check whether an earlier delete time for that data item is in cache memory and, if so, change the stored delete time for that data item to the current time.

14. The computer-readable storage medium of claim 12 wherein the program of instructions causes the data cache server running the program of instructions to delete each delete time from cache memory when the difference between the current time and the stored delete time exceeds a predetermined threshold.

15. The computer-readable storage medium of claim 14 wherein the program of instructions causes the data cache server running the program of instructions to dynamically adjust the pre-determined thres

Assignees

• Ghandeharizadeh Shahram
• Yap Jason
• Univ Southern California

Inventors

• Ghandeharizadeh Shahram
• Yap Jason

Classifications

• H04L67/2852 Primary

  Electricity · mapped topic

• H04L67/5682 Primary

  Policies or rules for updating, deleting or replacing the stored data · CPC title