Bi-temporal key value cache system

Patent metadata

Field	Value
Publication number	US-9742860-B2
Application number	US-201213406758-A
Country	US
Kind code	B2
Filing date	Feb 28, 2012
Priority date	Feb 28, 2012
Publication date	Aug 22, 2017
Grant date	Aug 22, 2017

Abstract

Described herein are techniques for supporting bi-temporal data in a key value cache system. An embodiment provides bi-temporal data as the basic functionality of a key value cache system. An embodiment provides a redesign of the core data structures of a key value cache system, adds bi-temporal data storage in the key value hashing structure, and provides a temporality-aware memory space manager. Embodiments can achieve the same performance as current key value cache systems for regular queries (that is, the queries that only access the current versions of data) while supporting bi-temporal data.

First claim

What is claimed is:

1. A method for providing a bi-temporal key value cache system, comprising:
storing a key directory having a plurality of key elements, wherein each key element points to a data object;
receiving a query request having an associated system time for one of said plurality of data objects, said data object being stored in a key value cache comprising bi-temporal data stored in a current table and a historical table and wherein said current table stores current versions of a plurality of data objects and said historical table stores historical versions of the plurality of data objects, each version having an associated input time, wherein the associated input time of the data objects within the current table comprise a start time and are sorted by start time and wherein the associated input time of the data objects within the historical table comprise an end time and are sorted by the end time;
responsive to receiving said query request having an associated system time, searching said key directory for at least one key element pointing to said data object, wherein said at least one key element comprises a hash chain element comprising two pointers which point, respectively, to a current version of said data object and at least one historical version of said data object;
responsive to finding said at least one key element, searching said current table and said historical table for said data object requested and finding both said current version of said data object and said at least one historical version of said data object;
determining from said current version and said at least one historical version of said data object which version is to be returned, wherein said determining comprises identifying a version from said current version and said at least one historical version where the input time associated with the version matches the system time associated with the query request;
reading said determined version of said data object having an input time matching the system time from said key value cache using a pointer to said determined version of said data object; and
returning said determined version of said data object having an input time matching the system time in response to said query request.

2. The method of claim 1 , wherein said key directory is a hash directory.

3. The method of claim 1 , wherein said searching a current table and a historical table further comprises:
searching the current table based on a valid from time; and
searching the historical table based on an update time.

4. The method of claim 1 , further comprising:
responsive to a request to delete a data object in said key value cache, moving all data objects matching a key of the request to delete a data object to a non-infinite container and updating said current table and said historical table.

5. The method of claim 1 , further comprising:
responsive to a request to update a data object in said key value cache, copying a current version of a data object matching a key of the request to update a data object from an infinite container to a non-infinite container, adding an entry to said historical table, modifying an entry in said current table, and storing an updated data object in an infinite container.

6. The method of claim 5 , wherein said modifying an entry in said current table further comprises one of:
removing an entry for the data object matching a key of the request to update a data object from the current table; and
updating an entry for the data object matching a key of the request to update a data object in the current table by modifying create time and valid from time for said data object matching a key of the request to update a data object.

7. The method of claim 1 , wherein said data object is a cached web page.

8. The method of claim 1 , wherein said method is implemented at least in part using software provided as a service in a cloud environment.

9. A computer program product for providing a bi-temporal key value cache system, comprising:
a non-transitory computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising:
computer readable program code configured to store a key directory having a plurality of key elements, wherein each key element points to a data object;
computer readable program code configured to receive a query request having an associated system time for one of said plurality of data objects, said data object being stored in a key value cache comprising bi-temporal data stored in a current table and a historical table and wherein said current table stores current versions of a plurality of data objects and said historical table stores historical versions of the plurality of data objects, each version having an associated input time, wherein the associated input time of the data objects within the current table comprise a start time and are sorted by start time and wherein the associated input time of the data objects within the historical table comprise an end time and are sorted by the end time;
computer readable program code configured to, responsive to receiving said query request having an associated system time, search said key directory for at least one key element pointing to said data object, wherein said at least one key element comprises a hash chain element comprising two pointers which point, respectively, to a current version of said data object and at least one historical version of said data object;
computer readable program code configured to responsive to finding said at least one key element, search said current table and said historical table for said data object requested and finding both said current version of said data object and said at least one historical version of said data object;
computer readable program code configured to determine from said current version and said at least one historical version of said data object which version is to be returned, wherein said determining comprises identifying a version from said current version and said at least one historical version where the input time associated with the version matches the system time associated with the query request;
computer readable program code configured to read said determined version of said data object having an input time matching the system time from said key value cache using a pointer to said determined version of said data object; and
computer readable program code configured to return said determined version of said data object having an input time matching the system time in response to said query request for said data object.

10. The computer program product of claim 9 , wherein said key directory is a hash directory.

11. The computer program product of claim 9 , wherein to search a current table and a historical table further comprises:
searching the current table based on a valid from time; and
searching the historical table based on an update time.

12. The computer program product of claim 9 , further comprising computer readable program code configured to:
responsive to a request to delete a data object in said key value cache, move all data objects matching a key of the request to delete a data object to a non-infinite container and updating said current table and said historical table.

13. The computer program product of claim 9 , further comprising computer readable program code configured to:
responsive to a request to update a data object in said key value cache, copy a current version of a data object matching a key of the request to update a data object from an infinite container to a non-infinite container, ad

Assignees

• Fang Ru
• He Bin
• Hsiao Hui-I
• Mohan Chandrasekaran
• Mueller Rene
• IBM

Inventors

• Fang Ru
• He Bin
• Hsiao Hui-I
• Mohan Chandrasekaran
• Mueller Rene

Classifications

• H04L67/2842 Primary

  Electricity · mapped topic

• H04L67/568 Primary

  Storing data temporarily at an intermediate stage, e.g. caching · CPC title