Back to results
US 11,455,304 B2Granted
Graph-based predictive cache
AssigneeSap SE
InventorYang Peng
Life of this patent
Estimating the term…
Abstract
A predictive cache system learns data access patterns to build a graph of related data items. A main cache hosted by a cache server is accessed by a cache client having a local cache. A request to the cache server for one of the related data items generates a response including some or all of the related data items, which are stored in the local cache and can be served locally for subsequent requests. Predictive cache behavior coexists with legacy non-predictive cache operation. Load on the cache server and aggregate latency are considerably reduced. Graphs can be specific to a particular context. Locally cached content can be distributed and reused by other cache clients. The predictive cache system is suitable for large-scale web applications. Variations are described.
Claims20
A method comprising:
- maintaining a graph specific to a first context, wherein the graph comprises a plurality of vertices, corresponding to respective data items including a first data item, and a plurality of edges;
- constructing an edge of the plurality of edges between a first vertex and a second vertex of the plurality of vertices, based on an observed first association between first past requests for the respective data items of the first and second vertices in the first context;
- subsequent to the constructing, receiving, from an application instance, a first request having the first context and identifying the first data item to be returned in response to the first request;
- responsive to the first request:
- based on the first context, identifying the graph specific to the first context;
- traversing the plurality of vertices to identify one or more additional data items beyond the first request, that are linked, in the graph, to the first data item, wherein the one or more additional data items are linked based on associations observed between respective past requests, the associations including the first association between the first past requests;
- retrieving a plurality of data items, comprising the first data item and the one or more additional data items, from a first cache;
- and
- storing the retrieved plurality of data items in a second cache distinct from the first cache;
- subsequently receiving a second request from the application instance for a second data item distinct from the first data item, the second data item being one of the one or more additional data items linked in the graph specific to the first context;
- and
- responsive to the second request:
- retrieving the second data item from the second cache;
- and
- fulfilling the second request with the retrieved second data item.
12 more elements
Computer-readable storage media storing instructions which, when executed by one or more hardware processors, cause the one or more hardware processors to perform operations comprising:
- maintaining a graph stored in a graph repository, wherein the graph comprises a plurality of vertices, corresponding to respective data items including a given data item, and a plurality of edges;
- constructing an edge of the plurality of edges between a first vertex and a second vertex of the plurality of vertices, based on an observed first association between first past requests for the respective data items of the first and second vertices;
- subsequent to the constructing, receiving, from a client, a request comprising information describing a context of a requesting application instance and further information describing the given data item to be returned in response to the request;
- mapping the context to the graph;
- traversing the plurality of vertices to identify one or more additional data items that are linked to the given data item in the graph, wherein the one or more additional data items are linked based on associations observed between respective past requests, the associations including the first association between the first past requests;
- collecting a plurality of data items, including the given data item and the one or more additional data items, from a data cache;
- and
- returning the collected plurality of data items to the client in response to the request.
5 more elements
A system comprising:
- a plurality of servers including a cache server and one or more application servers, each server of the plurality of servers comprising one or more processors with memory coupled thereto and a network connection, wherein the cache server is coupled to the one or more application servers via the respective network connections of the one or more application servers;
- wherein each of the one or more application servers is configured to execute instructions of:
- an application cache client hosting a local cache;
- and
- one or more instances of an application;
- wherein the cache server is configured to execute instructions of an application cache service hosting a shared application data cache and a graph store;
- wherein the application cache client is configured to forward a first request for a first data item, received from a first instance of the one or more instances of the application, to the application cache service together with an application context of the first instance of the application;
- and
- wherein the application cache service is configured to:
- map the application context of the first instance of the application to a corresponding graph in the graph store;
- collect a plurality of data items, specified by the corresponding graph and including the first data item, from the shared application data cache, wherein the plurality of data items are linked in the corresponding graph based on associations observed between past requests for the plurality of data items;
- and
- return the collected data items to the forwarding application cache client to be stored in the local cache.
10 more elements
Dependencies are inferred from the claim text.