CACHE CLEANUP AND LATCHING

• US 20100293338A1
• Filed: 05/20/2009
• Published: 11/18/2010
• Est. Priority Date: 05/13/2009
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Muhammed, Sharique, Jorwekar, Sudhir Mohan, Krishnaprasad, Muralidhar, Muralidhar, Subramanian, Nori, Anil K.
• Application Number:
  US12/468,871
• Publication Number:
  US 20100293338A1
• Time in Patent Office: Days
• US Class Current: 711/136
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 16/9014 hash tables

Abstract

A low priority queue can be configured to list low priority removal candidates to be removed from a cache, with the low priority removal candidates being sorted in an order of priority for removal. A high priority queue can be configured to list high priority removal candidates to be removed from the cache. In response to receiving a request for one or more candidates for removal from the cache, one or more high priority removal candidates from the high priority queue can be returned if the high priority queue lists any high priority removal candidates. If no more high priority removal candidates remain in the high priority queue, then one or more low priority removal candidates from the low priority queue can be returned in the order of priority for removal. Write-only latches can also be used during write operations in a cache lookup data structure.

Claims

1. A computer-implemented method, comprising:

maintaining a low priority cleanup queue that is configured to list low priority removal candidates to be removed from a cache, with the low priority removal candidates being sorted in an order of priority for removal;

maintaining a high priority cleanup queue that is configured to list high priority removal candidates to be removed from the cache; and

in response to receiving a request for one or more candidates for removal from the cache;

if the high priority cleanup queue lists any high priority removal candidates, returning one or more candidates from the high priority cleanup queue; and

if no more high priority removal candidates remain in the high priority cleanup queue, then returning one or more low priority removal candidates from the low priority cleanup queue in the order of priority for removal.

2. The method of claim 1, wherein the high priority removal candidates are identified as being expired.

3. The method of claim 1, wherein the low priority removal candidates are sorted according to a least recently used policy.

4. The method of claim 1, wherein the low priority removal candidates are sorted according to a least frequently used policy.

5. The method of claim 1, further comprising maintaining a to-be-sorted queue that is configured to list candidates to be sorted in the low priority cleanup queue.

6. The method of claim 5, wherein maintaining the low priority cleanup queue, the high priority cleanup queue, and the to-be-sorted queue comprises:

identifying in the low priority cleanup queue and the to-be-sorted queue eligible candidates for listing in the high priority queue;

listing the eligible candidates in the high priority queue;

sorting removal candidates listed in the to-be-sorted queue; and

merging the candidates listed in the to-be-sorted queue with the low priority candidates in the low priority queue.

7. The method of claim 6, wherein the cache is a distributed partitioned cache, wherein the low priority removal candidates are sorted according to a least recently used policy, and wherein the high priority removal candidates are identified as being expired.

8. The method of claim 1, further comprising deleting the returned removal candidates from the cache in an order in which the returned removal candidates are returned.

9. A computer system comprising:

means for receiving a request for one or more candidates for removal from a cache;

means for returning one or more candidates for removal from the cache in response to the request, the means for returning comprising;

means for returning one or more candidates for removal that are identified as being expired;

means for determining when all candidates for removal that are identified as being expired have been returned; and

means for returning candidates for removal according to a priority policy when all candidates for removal that are identified as being expired have been returned.

10. The computer system of claim 9, wherein the priority policy comprises a least recently used policy.

11. The computer system of claim 9, wherein the means for returning one or more candidates for removal that are identified as being expired comprises returning candidates from a high priority queue, and wherein the means for returning candidates for removal according to the priority policy comprises returning candidates from a low priority queue.

12. The computer system of claim 9, further comprising means for deleting one or more returned candidates from the cache in an order in which the one or more returned candidates are returned.

13. The computer system of claim 9, wherein the means for returning one or more candidates for removal that are identified as being expired comprises means for maintaining a high priority queue listing high priority candidates that are identified as being expired.

14. The computer system of claim 13, wherein the means for returning candidates for removal according to a priority policy comprises maintaining a low priority queue listing low priority candidates for removal, the low priority candidates being sorted according to the priority policy.

15. One or more computer-readable storage media having computer-executable instructions embodied thereon that, when executed, perform acts comprising:

performing a write operation on an existing cache unit that is pointed to by an existing committed pointer in a cache directory slot; and

latching the slot to prevent other write operations on the cache unit;

allowing one or more read operations on the cache unit during the write operation; and

unlatching the slot after the write operation is complete.

16. The one or more computer-readable media of claim 15, wherein the write operation is a delete operation.

17. The one or more computer-readable media of claim 15, wherein the write operation is an update operation.

18. The one or more computer-readable media of claim 15, wherein the acts further comprise allowing the write operation to proceed when one or more read operations are ongoing at a time when the write operation begins.

19. The one or more computer-readable media of claim 15, wherein the one or more read operations that are allowed during the write operation return consistent data corresponding to the cache unit prior to the write operation.

20. The one or more computer-readable media of claim 15, wherein the write operation comprises:

inserting a new uncommitted pointer in the slot, the new pointer pointing to a new cache unit that is to replace the existing cache unit; and

marking the new pointer as being committed.