MEMOIZATION BUCKETS FOR CACHED FUNCTION RESULTS

• US 20150074350A1
• Filed: 09/06/2013
• Published: 03/12/2015
• Est. Priority Date: 09/06/2013
• Status: Abandoned Application

• Current Assignee: Apperian, Inc (Digital.ai Software, Inc.)
• Original Assignee: Apperian, Inc (Digital.ai Software, Inc.)
• Inventors: Chiang, Frank Feng-Chun, Nasseri, Ashkan
• Application Number:
  US14/019,734
• Publication Number:
  US 20150074350A1
• Time in Patent Office: Days
• US Class Current: 711/118
• CPC Class Codes: G06F 12/0808 with cache invalidating means G06F12/0815 takes precedence
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 2212/452 Instruction code

Abstract

A memoization system and method arranges cached function results into groups, or buckets, to identify related cache values to invalidate upon obsolescence (staleness) of any one of the cached values in the group. A wrapper function in coded invocations to the cached functions identifies a group to which the function result belongs. Values in a cache group are denoted as a bucket, and subsequent functions that render the cached values obsolete are also invoked via a wrapper function indicating the bucket. The invalidate wrapper results in invalidation of all of the obsolete values in the bucket such that subsequent invocations will not attempt to employ the outdated values.

Claims

1. A method of caching computational results, comprising:

issuing a cache grouping command in conjunction with an invocation of function resulting in a cached function result;

associating the cached function result with a cache group;

issuing an invalidate command indicative of the cache group; and

invalidating all cached function results in the cache group.

2. The method of claim 1 wherein the cache grouping command is a wrapper function encapsulating the invoked function.

3. The method of claim 2 wherein the invalidate comment is a wrapper function encapsulating a function potentially rendering the cached function results in the cache group obsolete.

4. In a managed application environment, a method of managed application environment comprising:

identifying a cached entity, the cached entity generated by execution of a function;

labeling the cached entity with a group, the group indicative of a plurality of related cached entities;

receiving a request to invalidate at least one cached entity in the labeled group; and

invalidating the cached entity and each related cached entity in the labeled group.

5. The method of claim 4 further comprising:

computing a value for the cached entity based on a received request for a function invocation, the function having a name and parameters.

6. The method of claim 5 wherein the cached entity is responsive to a successive function invocation based on a correspondence between the name and the parameters of the invoked function.

7. The method of claim 6 further comprising computing a cache key based on the function name and parameters of the received request, the cache key indicative of the cached entity and the group of the cached entity.

8. The method of claim 4 further comprising identifying complementary functions in the group, the complementary functions for associating cached values with the group and invalidating the associated cached entities storing the cached values in the group.

9. The method of claim 5 further comprising:

computing a match key from the successive function invocation, the match key computed from the name of the invoked function and the parameters of the invoked function; and

mapping the match key to a group corresponding to the related cached entities.

10. The method of claim 5 further comprising storing the cached entity in a tree based on a hash generated from the parameters and the name of the invoked function, the tree defining a hierarchy of the groups.

11. The method of claim 10 further comprising

identifying the related cached entities based on a branch of the tree in which the cached entity is stored;

and

traversing toward the root of the tree to identify the other cached entities in the group.

12. The method of claim 11 further comprising traversing the tree of cached entities based on the generated hash to identify the corresponding cached entity for invalidation.

13. The method of claim 4 further comprising:

receiving a request to invalidate the cached entity; and

matching a match key corresponding to the request to a cache key of the cached entity for invalidation.

14. The method of claim 4 wherein receiving the invalidate command further includes receiving a group to which the cached entity belongs, the group indicative of a related set of cached values.

15. The method of claim 4 wherein the group of cached entities defines a bucket, the bucket based on a type of entity to which the function pertains, wherein labeling and invalidating refers to the bucket.

16. The method of claim 15 further comprising

receiving the type of entity with the request to invalidate the cached entity;

and

invalidating other cached entities in the same bucket as the cached entity.

17. The method of claim 15 further comprising determining the bucket based on the executed function, the bucket based on a type of entity to which the function pertains.

18. The method of claim 4 further comprising receiving a request to invoke the function using a wrapper function, the wrapper function associating the function result with a cache entity in the group.

19. A computer apparatus for caching function results, comprising:

a cache memory configured to store a cached entity, the cached entity generated by execution of a function;

a wrapper function operable to label the cached entity with a group, the group indicative of a plurality of related cached entities; and

a cache server configured to receive a request to invalidate at least one cached entity in the labeled group, the cache server operable to invalidate the cached entity and each related cached entity in the labeled group.

20. A computer program product on a non-transitory computer readable storage medium having instructions for performing a method for caching computed results, the method comprising:

identifying a set of cached entities as a group, the group related by usage of cached values in the group;

determining that at least one of the cached entities is stale; and

invalidating all of the cached entities in the group corresponding to the determined stale entity.