Poll based cache event notifications in a distributed cache

• US 8,108,623 B2
• Filed: 05/11/2009
• Issued: 01/31/2012
• Est. Priority Date: 10/26/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Krishnaprasad, Muralidhar, Krishan, Gopal, Goduguluru, Lakshmi Suresh, Agrawal, Ankur, Pavadaisamy, Balachandar
• Primary Examiner(s): Lam, David
• Application Number:
  US12/463,745
• Publication Number:
  US 20100106915A1
• Time in Patent Office: 995 Days
• Field of Search: 711/144, 711/141, 711/133, 711/118, 711/143, 711/113, 711/130, 711/E12.037, 709/218, 709214-216, 707/202
• US Class Current: 711/144
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0873 Mapping of cache memory to specific storage devices or parts thereof
• CPC Class Codes: G06F 2212/264 Remote server
• CPC Class Codes: G06F 2212/284 being distributed

Abstract

Systems and methods that supply poll based notification system in a distributed cache, for tracking changes to cache items. Local caches on the client can employ the notification system to keep the local objects in sync with the backend cache service; and can further dynamically adjust the “scope” of notifications required based on the number and distribution of keys in the local cache. The server can maintain the changes in an efficient fashion (in blocks) and returns the changes to clients that perform the appropriate filtering. Notifications can be associated with a session and/or an application.

Claims

1. A computer implemented method comprising:

employing a processor to execute computer executable instructions stored on a computer readable medium to perform the following acts;

tracking changes to cached data in a distributed store via a filtering sub-system;

employing a Common Availability Substrate (CAS) to maintain availability of operations for the distributed data store during the tracking act; and

dynamically adjusting scope of notifications for tracked changes.

2. The computer implemented method of claim 1 further comprising notifying a client(s) of the distributed store regarding tracked changes based on polling a cluster of nodes that form the distributed store.

3. The computer implemented method of claim 2 further comprising registering the client(s) for receiving notifications from a named cache, or a region, or a key or a combination thereof.

4. The computer implemented method of claim 1, the polling further comprising a pull or push model for the distributed store.

5. The computer implemented method of claim 1, the tracking act further comprising maintaining track of:

key operations;

or values of data;

or a combination thereof.

6. The computer implemented method of claim 1, further comprising tracking change sequence numbers per partition.

7. The computer implemented method of claim 1, further comprising maintaining cache events as blocks for optimal transport or processing.

8. The computer implemented method of claim 1, further comprising propagating notifications when a primary node of a partition fails.

9. The computer implemented method of claim 1, further comprising employing routing table to correspond keys with nodes of the distributed store.

10. The computer implemented method of claim 1 further comprising implementing a session based notification that associates a notifying act with a session in the distributed store.

11. A computer implemented system that facilitates tracking data changes in a distributed store comprising:

a processor;

a memory communicatively coupled to the processor, the memory having stored therein computer-executable instructions configured to implement the computer implemented system including;

a plurality of nodes that form a distributed store; and

a notification component that tracks changes to data cached in the distributed store based on a session or an application or a combination thereof; and

a Logical Sequence Number (LSN) generated as part of a replication process associated with a Common Availability Substrate (CAS).

12. The computer implemented system of claim 11, the notification component further comprising a filtering system that adjusts scope of notification.

13. The computer implemented system of claim 11 further comprising a routing table that directs replicated data to a plurality of nodes that form the distributed store.

14. The computer implemented system of claim 11 further comprising a selection component that designates a subset of nodes or servers based on partitions or keys partitioned therein.

15. The computer implemented system of claim 11 the distributed store further comprising

a layering arrangement that supplies an explicit aggregated cache for applications associated therewith, the layering arrangement includes:

a distributed object manager component that facilitates abstraction of the explicit aggregated cache in a distributed environment, to a single unified cache; and

an object manager component that manages policies associated with objects stored in each of nodes that form the single unified cache.

16. The computer implemented system of claim 15 further comprising a data manager component that supplies storage data structures for the objects.

17. The computer implemented system of claim 15 further comprising a clustering substrate that establishes clustering protocols between nodes that form the single unified cache.

18. A computer implemented system that facilitates tracking data changes in a distributed store comprising:

a processor;

a memory communicatively coupled to the processor, the memory having stored therein computer-executable instructions configured to implement the computer implemented system including;

a plurality of nodes that form a distributed store; and

a notification component that tracks changes to data cached in the distributed store based on a session or an application or a combination thereof, the distributed store further comprising

a layering arrangement that supplies an explicit aggregated cache for applications associated therewith, the layering arrangement includes;

a distributed object manager component that facilitates abstraction of the explicit aggregated cache in a distributed environment, to a single unified cache; and

an object manager component that manages policies associated with objects stored in each of nodes that form the single unified cache.

19. A computer-implemented method for implementing event notification in a distributed store that includes a plurality of different stores of a plurality of different nodes, each node storing data of the distributed stored that is associated with corresponding keys, comprising:

partitioning the distributed store into a hierarchically partitioned store having a plurality of different hierarchical levels, including at least a key level, a region level and a partition level;

hashing and mapping keys associated with data items of the distributed store into a routing table that maps the location of the data items having particular keys to different node stores and that identifies which partition and region each key corresponds to, wherein at least one region in the region level includes reference to a plurality of keys, and wherein at least one partition in the partition level includes reference to a plurality of regions;

maintaining a logical sequence number for changes occurring to the data items, for each level of the hierarchically partitioned store;

receiving a key level request from a client, which includes a specified logical sequence number and a specified key, for notifications corresponding to changes that have occurred to at least one data item associated with the specified key and corresponding to logical sequence numbers that sequentially follow the specified logical sequence number;

providing a block of one or more changes for the key level request to the client corresponding to key level changes that have been made to the key level associated with the specified key and specified logical sequence number of the hierarchically partitioned store; and

upon determining that a quantity of keys in a partition exceeds a predetermined threshold, switching to a partition level notification and subsequently providing a block of one or more changes corresponding to the partition level changes that have been made to the partition level associated with the specified key and specified logical sequence number of the hierarchically partitioned store.