Non-blocking caching technique

• US 9,223,780 B2
• Filed: 12/19/2012
• Issued: 12/29/2015
• Est. Priority Date: 12/19/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Aue, Anthony, Menezes, Arul A.
• Primary Examiner(s): Bertram, Ryan
• Application Number:
  US13/719,252
• Publication Number:
  US 20140173200A1
• Time in Patent Office: 1,105 Days
• Field of Search: 711/118, 711/130, 711141-146, 711/150
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 12/0844 Multiple simultaneous or quasi-simultaneous cache accessing
• CPC Class Codes: G06F 12/0857 by multiple requestors
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files

Abstract

The described implementations relate to processing of electronic data. One implementation is manifested as a system that can include a cache module and at least one processing device configured to execute the cache module. The cache module can be configured to store data items in slots of a cache structure, receive a request for an individual data item that maps to an individual slot of the cache structure, and, when the individual slot of the cache structure is not available, return without further processing the request. For example, the request can be received from a calling application or thread that can proceed without blocking irrespective of whether the request is fulfilled by the cache module.

Claims

1. A method performed by executing software instructions with a processor, the method comprising:

receiving lookup requests from calling threads to obtain requested data items from a software cache data structure having a plurality of slots;

mapping the requested data items to individual slots of the software cache data structure based on characteristics of the requested data items;

performing access checks to determine whether the individual slots of the software cache data structure are being used by other threads; and

after performing the access checks, selectively checking whether the requested data items are stored in the individual slots of the software cache data structure based on whether the individual slots are being used by the other threads, the selectively checking comprising;

for first lookup requests from first calling threads where the individual slots are being used by the other threads, returning to the first calling threads without checking whether corresponding requested first data items are stored in the software cache data structure, and

for second lookup requests from second calling threads where the individual slots are not being used by the other threads, checking whether corresponding requested second data items are stored in the software cache data structure.

2. The method of claim 1, wherein at least some of the requested first data items are stored in the software cache data structure when returning to the first lookup requests.

3. The method of claim 1, further comprising:

maintaining a plurality of access control bits in association with the plurality of slots of the software cache data structure.

4. The method of claim 3, wherein performing the access checks comprises performing compare-and-swap operations on access control bits that are associated with the individual slots.

5. The method of claim 3, wherein the software cache data structure comprises a single array or multiple arrays.

6. The method of claim 1, further comprising:

when the requested second data items are stored in the software cache data structure, providing the requested second data items in response to the second lookup requests.

7. The method of claim 1, wherein the requested data items have variable sizes.

8. A computing device comprising:

a processor; and

a memory or storage device storing software instructions which, when executed by the processor, cause the processor to;

receive an insertion request from a calling thread to insert a data item into a software cache data structure having a plurality of slots;

map the data item to an individual slot of the software cache data structure by applying a hashing function to an identifier of the data item to obtain a hash value, the individual slot being identified by bits of the hash value;

perform an access check to determine whether the individual slot of the software cache data structure is available; and

in an instance when the individual slot is not available, return to the calling thread without inserting the data item into the software cache data structure,

wherein the software cache data structure has a number of slots that is based on a number of the bits of the hash value that are used to identify the individual slot.

9. The computinq device of claim 8, wherein the returning to the calling thread does not indicate whether the data item was inserted into the software cache data structure.

10. The computinq device of claim 8, wherein the software instructions, when executed by the processor, cause the processor to:

receive another request to insert another data item into the software cache data structure;

map the another data item to another slot of the software cache data structure; and

in an instance when the another slot is available, store the another data item in the another slot.

11. The computing device of claim 8, wherein the bits of the hash value that are used to identify the individual slot are low order bits of the hash value.

12. The computinq device of claim 8, wherein the bits of the hash value that identify the individual slot are a subset of bits of the hash value.

13. The computing device of claim 12, wherein the software instructions, when executed by the processor, cause the processor to:

obtain a fingerprint for the data item from a different subset of bits of the hash value; and

store the fingerprint in the individual slot with the data item.

14. The computinq device of claim 12, wherein the software cache data structure has a fixed number of slots.

15. A system comprising:

a cache module comprising software instructions;

a processor configured to execute the software instructions of the cache module; and

a memory or storage,

wherein the software instructions of the cache module cause the processor to;

store a plurality of data items in a plurality of slots of a cache data structure, the cache data structure being stored in the memory or storage;

receive, from a calling thread, a lookup request to retrieve a requested data item that maps to an individual slot of the cache data structure;

perform an access check to determine whether the individual slot is in use;

when the access check indicates the individual slot is not in use, check whether the requested data item is present in the cache data structure; and

when the access check indicates the individual slot is in use, return to the calling thread without checking whether the requested data item is present in the cache data structure.

16. The system according to claim 15, wherein the software instructions of the cache module further cause the processor to:

return the requested data item when the requested data item is present in the cache data structure.

17. The system according to claim 15, wherein software instructions of the cache module further cause the processor to:

perform an operation on an identifier of the requested data item to identify the individual slot to which the requested data item is mapped.

18. The system according to claim 15, wherein the requested data item is present in the cache data structure when returning to the calling thread without checking whether the requested data item is present in the cache data structure.

19. The system according to claim 15, further comprising an application configured to execute in the calling thread and provide the lookup request to the cache module.

20. The system according to claim 15, embodied as a mobile device or as a server.