Invalidation and refresh of multi-tier distributed caches

• US 10,007,607 B2
• Filed: 05/31/2016
• Issued: 06/26/2018
• Est. Priority Date: 05/31/2016
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Pack, III, Richard Perry
• Primary Examiner(s): Song, Jasmine
• Application Number:
  US15/169,568
• Publication Number:
  US 20170344481A1
• Time in Patent Office: 756 Days
• Field of Search: 711130
• CPC Class Codes: G06F 12/0833 in combination with broadcast means (e.g. for invalidation or updating)
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 2212/314 In storage network, e.g. network attached cache
• CPC Class Codes: G06F 2212/621 Coherency control relating to peripheral accessing, e.g. from DMA or I/O device
• CPC Class Codes: G06F 9/54 Interprogram communication
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching

Abstract

To deliver up-to-date, coherent user data to applications upon request, the disclosed technology includes systems and methods for caching data and metadata after it has been synchronously loaded—for future retrieval with a page load time close to zero milliseconds. To provide this experience, data needs to be stored as locally to a user as possible, in the cache on the local device or in an edge cache located geographically nearby, for use in responding to requests. Applications which maintain caches of API results can be notified of their invalidation, and can detect the invalidation, propagate the invalidation to any further client tiers with the appropriate derivative type mapping, and refresh their cached values so that clients need not synchronously make the API requests again—ensuring that the client has access to the most up-to-date copy of data as inexpensively as possible—in terms of bandwidth and latency.

Claims

1. A method of caching derived data, including:

a shared cache manager, running on a caching system, receiving information regarding core data instances of interest requested from a data source and regarding requests for derived data of interest, wherein at least one application program running on a server accessed by a data consuming application via an application program interface (abbreviated API) receives the core data as input and returns the derived data;

the shared cache manager;

monitoring and detecting changes to the core data instances of interest;

inferring impact on the derived data of the changed core data instances;

pre-caching an updated version of the impacted derived data by replaying at least one API access that is dependent on the changed core data instances; and

informing a local cache manager, running on a same user device as or connected by a bus or local area network to the data consuming application, of the changes to the core data instances of interest and of the impact on derived data returned by the at least one API; and

the shared cache manager, responsive to requests from the local cache manager regarding the changes to the core data instances of interest and to the impacted derived data, determining whether follow-up requests from the local cache manager for the changed core data instances and the impacted derived data can be satisfied by the shared cache manager without accessing the data source and satisfying the requests for the changed core data and the impacted derived data from cache memory.

2. The method of claim 1, further including the shared cache manager monitoring a time to live counter or timestamp for the impacted derived data in the cache memory to determine whether the impacted derived data can be used to satisfy follow-up requests from the local cache manager.

3. The method of claim 1, further including the shared cache manager relying on an invalidation listener to monitor and detect the changes to the core data instances of interest;

and the invalidation listener receiving invalidation messages reflecting changes to the core data at the data source.

4. The method of claim 1, wherein the inferring of impact on the derived data, at least in part, includes determining from an impact map one or more API calls that use the changed core data as API input.

5. The method of claim 1, wherein the inferring of impact on the derived data, at least in part, includes determining from cache memory one or more API calls made by the data consuming application using the changed core data instances.

6. The method of claim 1, wherein the inferring of impact on the derived data, at least in part, includes using a user-specific key to access cache memory and retrieve one or more API calls made by the data consuming application that used the changed core data instances as API input.

7. The method of claim 1, further including the local cache manager sending API access replay requests automatically without user initiation and receiving data satisfying the requests for the changed core data and the impacted derived data cached by the shared cache manager.

8. The method of claim 7, further including the local cache manager updating its local cache memory with the received data and making updated data available for updating a display on a mobile user device.

9. The method of claim 1, wherein the local cache manager runs on a mobile device.

10. A system of computing devices, including:

a data consuming application running on a user device that consumes both core data and derived data, wherein the derived data is generated by passing some of the core data to at least one application program interface (abbreviated API) and receiving the derived data in return;

a data source from which the core data is obtained;

at least one application program running on a server accessed by the data consuming application via the API, wherein the application program receives the core data as input and returns the derived data;

a local cache manager, running on the same user device as or connected by a bus or local area network to the data consuming application, wherein the local cache manager refreshes a local cache of data used by the data consuming application; and

a shared cache manager running on a caching system that

accesses interest indications of core data instances and derived data of interest to the data consuming application;

monitors and detects changes to the core data instances of interest;

infers impact on the derived data of the changed core data instances;

pre-caches an updated version of the impacted derived data by replaying at least one API access that is dependent on the changed core data instances; and

informs the local cache manager of the changes to the core data instances of interest and of the impact on derived data returned by the at least one API; and

wherein the local cache manager, responsive to information from the shared cache manager regarding the changes to the core data instances of interest and to the impacted derived data, determines whether the impacted derived data is of continuing interest and, if so, replays the at least one API access with the changed core data to refresh cached derived data from the API access.

11. The system of claim 10, wherein the shared cache manager further includes monitoring of a time to live counter or timestamp for the impacted derived data in cache memory to determine whether the impacted derived data can be used to satisfy follow-up requests from the local cache manager.

12. The system of claim 10, wherein the shared cache manager further includes an invalidation listener that monitors and detects the changes to the core data instances of interest;

and the invalidation listener receives invalidation messages reflecting changes to the core data at the data source.

13. The system of claim 10, wherein the shared cache manager infers impact on the derived data, at least in part, by determining from an impact map one or more API calls that use the changed core data as API input.

14. The system of claim 10, wherein the shared cache manager infers impact on the derived data, at least in part, by determining from cache memory one or more API calls made by the data consuming application dependent on the changed core data instances.

15. The system of claim 10, wherein the shared cache manager infers impact on the derived data, at least in part, by using a user-specific key to access cache memory and retrieve one or more API calls made by the data consuming application that used the changed core data instances as API input.

16. The system of claim 10, wherein the local cache manager runs on a mobile device.

17. The system of claim 10, wherein the local cache manager generates API access replay requests automatically without user initiation and receives data satisfying the requests for the changed core data and the impacted derived data from the shared cache manager.

18. The system of claim 10, further including the local cache manager that updates its local cache memory with the received data and makes updated data available for updating a display on a mobile user device.

19. A non-transitory computer readable storage medium loaded with computer instructions that, when executed, cause a shared cache manager running on a caching system to cache derived data to take actions including:

the shared cache manager receiving information regarding core data instances of interest requested from a data source and regarding requests for derived data of interest, wherein at least one application program running on a server accessed by a data consuming application via an application program interface (abbreviated API) receives the core data as input and returns the derived data;

the shared cache manager;

monitoring and detecting changes to the core data instances of interest;

inferring impact on the derived data of the changed core data instances;

pre-caching an updated version of the impacted derived data by replaying at least one API access that is dependent on the changed core data instances; and

informing a local cache manager, running on the same device as or connected by a bus or local area network to the data consuming application, of the changes to the core data instances of interest and of the impact on derived data returned by the at least one API; and

the shared cache manager, responsive to requests from the local cache manager regarding the changes to the core data instances of interest and to the impacted derived data, determining whether follow-up requests from the local cache manager for the changed core data instances and the impacted derived data can be satisfied by the shared cache manager without accessing the data source and satisfying the requests for the changed core data and the impacted derived data from cache memory.

20. The non-transitory computer readable storage medium of claim 19, causing the shared cache manager to take actions further including the shared cache manager monitoring a time to live counter or timestamp for the impacted derived data in the cache memory to determine whether the impacted derived data can be used to satisfy follow-up requests from the local cache manager.

21. The non-transitory computer readable storage medium of claim 19, causing the shared cache manager to take actions further including the shared cache manager relying on an invalidation listener to monitor and detect the changes to the core data instances of interest;

and the invalidation listener receiving invalidation messages reflecting changes to the core data at the data source.

22. The non-transitory computer readable storage medium of claim 19, wherein the inferring of impact on the derived data, at least in part, includes determining from an impact map one or more API calls that use the changed core data as API input.

23. The non-transitory computer readable storage medium of claim 19, wherein the inferring of impact on the derived data, at least in part, includes determining from cache memory one or more API calls made by the data consuming application using the changed core data instances.

24. The non-transitory computer readable storage medium of claim 19, wherein the shared cache manager infers impact on the derived data, at least in part, by using a user-specific key to access cache memory and retrieve one or more API calls made by the data consuming application that used the changed core data instances as API input.

25. A shared cache manager running on an edge caching system that includes a processor and computer instructions that when executed the processor cause the shared cache manager to carry out a method including:

accessing interest indications of core data instances and derived data of interest to a data consuming application;

monitoring and detecting changes to the core data instances of interest;

inferring impact on the derived data of the changed core data instances;

pre-caching an updated version of the impacted derived data by replaying at least one API access that is dependent on the changed core data instances to generate the derived data; and

informing a local cache manager, running on the same device as or connected by a bus or local area network to the data consuming application, of the changes to the core data instances of interest and of the impact on derived data returned by the at least one API;

responding to an update request from the local cache manager for the updated version of the impacted derived data.