Key invalidation in cache systems

• US 10,642,745 B2
• Filed: 01/04/2018
• Issued: 05/05/2020
• Est. Priority Date: 01/04/2018
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Hansen, Nick
• Primary Examiner(s): Chery, Mardochee
• Application Number:
  US15/862,142
• Publication Number:
  US 20190205255A1
• Time in Patent Office: 852 Days
• Field of Search: 711113, 711118, 711122
• CPC Class Codes: G06F 12/0808 with cache invalidating means G06F12/0815 takes precedence
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 2212/608 Details relating to cache mapping

Abstract

Techniques are disclosed relating to invalidating keys in a cache. In some embodiments, a computer system may implement a cache for a data store, where the cache stores a data set and is organized such that a stored data item of the data set is specified by a corresponding key having one or more portions. The computer system may store metadata for the cache, where the metadata includes nodes organized in a hierarchy. The computer system may receive a request to invalidate one or more keys of the cache, and may invalidate a particular node within the metadata based on a key value corresponding to the request.

Claims

1. A method, comprising:

implementing, by a computer system, a cache for a database system, wherein the cache stores a data set and is organized such that data items of the data set are specified by corresponding keys having one or more portions;

storing, by the computer system, metadata for the cache, wherein the metadata includes nodes organized in a hierarchy in which different levels of the hierarchy correspond to different portions of the corresponding keys for the data set;

receiving, by the computer system, a request to invalidate one or more keys of the cache; and

based on a key value corresponding to the request, invalidating, by the computer system, a particular node within the metadata, wherein the invalidating results in a cache miss for a subsequent request for data corresponding to a key having a portion corresponding to the particular node.

2. The method of claim 1, wherein the database system is a multi-tenant database system, and wherein the data set includes data items for a plurality of tenants of the multi-tenant database system.

3. The method of claim 2, wherein the request to invalidate one or more keys is a request to invalidate keys for all data items associated with a first tenant of the multi-tenant database system.

4. The method of claim 3, further comprising:

identifying within the hierarchy, by the computer system, a root node for the first tenant; and

invalidating, by the computer system, the root node for the first tenant such that a subsequent request for a data item associated with the first tenant results in a cache miss within the cache.

5. The method of claim 2, wherein the request to invalidate one or more keys is a request to invalidate keys for all data items associated with a first user of a first tenant of the multi-tenant database system.

6. The method of claim 5, further comprising:

identifying within the hierarchy, by the computer system, a root node for the first user associated with the first tenant; and

invalidating, by the computer system, the root node for the first user such that a subsequent request for a data item associated with the first user results in a cache miss within the cache.

7. The method of claim 1, wherein the metadata includes the nodes structured as a directed acyclic graph.

8. The method of claim 7, wherein the directed acyclic graph is arranged as a tree structure;

and wherein a given leaf node of the tree structure includes a pointer to a given hash value, wherein the given hash value is usable to retrieve a given data item of the data set.

9. The method of claim 1, wherein the particular node is a root node in the hierarchy relative to a portion that is common to each of the one or more keys;

and wherein invalidating the one or more keys of the cache is performed without scanning all keys associated with the cache.

10. A non-transitory, computer-readable medium having computer instructions stored thereon that are capable of being executed by a computer system to cause operations comprising:

implementing a cache for a database system, wherein the cache stores a data set and is organized such that data items of the data set are specified by corresponding keys having one or more portions;

storing metadata for the cache, wherein the metadata includes nodes organized in a hierarchy in which different levels of the hierarchy correspond to different portions of the corresponding keys for the data set;

receiving a request to invalidate one or more keys of the cache; and

based on a key value corresponding to the request, invalidating a particular node within the metadata, wherein the invalidating results in a cache miss for a subsequent request for data corresponding to a key having a portion corresponding to the particular node.

11. The non-transitory, computer-readable medium of claim 10, wherein the request to invalidate the one or more keys is a request to invalidate all keys for data items associated with a given application.

12. The non-transitory, computer-readable medium of claim 10, wherein the database system is a multi-tenant database system, and wherein the data set includes data items for a plurality of tenants of the multi-tenant database system.

13. The non-transitory, computer-readable medium of claim 12, wherein the request to invalidate one or more keys is a request to invalidate keys for all data items associated with a first tenant of the multi-tenant database system.

14. The non-transitory, computer-readable medium of claim 13, further comprising:

identifying within the hierarchy, by the computer system, a root node for the first tenant; and

invalidating, by the computer system, the root node for the first tenant such that a subsequent request for a data item associated with the first tenant results in a cache miss within the cache.

15. The non-transitory, computer-readable medium of claim 12, wherein the request to invalidate one or more keys is a request to invalidate keys for all data items associated with a first user of a first tenant of the multi-tenant database system.

16. The non-transitory, computer-readable medium of claim 15, further comprising:

identifying within the hierarchy, by the computer system, a root node for the first user associated with the first tenant; and

invalidating, by the computer system, the root node for the first user such that a subsequent request for a data item associated with the first user results in a cache miss within the cache.

17. A method, comprising:

maintaining, by a computer system, a distributed cache that stores a data set corresponding to a data store, wherein the cache is organized such that data items of the data set are specified by corresponding keys having one or more portions;

storing, in the cache, metadata corresponding to the cache, the metadata including a plurality of nodes organized in a hierarchy in which different levels of the hierarchy correspond to different portions of the corresponding keys for the data set;

receiving, by the computer system, a request to invalidate a set of keys of the cache;

identifying, by the computer system based on a key value associated with the request, a particular node in the metadata, wherein the particular node is a root node in the hierarchy relative to a portion that is common to all keys in the set of keys; and

based on the particular node, invalidating, by the computer system, the set of keys of the cache such that subsequent requests for data items specified by the set of keys results in a cache miss.

18. The method of claim 17, further comprising:

subsequent to invalidating the set of keys, retrieving, by the computer system, program code associated with a first key of the set of keys;

executing, by the computer system, the program code, wherein the executing includes retrieving data from the data store;

storing, by the computer system, the retrieved data in the cache; and

updating, by the computer system, the metadata to include one or more nodes in the hierarchy corresponding to the first key.

19. The method of claim 17, further comprising:

subsequent to invalidating the set of keys, the computer system deleting, from the data set, data items corresponding to the set of keys.

20. The method of claim 17, wherein the data set stored by the cache includes data items for a plurality of tenants;

and wherein the request to invalidate the set of keys is a request to invalidate all keys associated with a first tenant of the plurality of tenants.