Multi-lock caches

• US 9,229,869 B1
• Filed: 12/19/2012
• Issued: 01/05/2016
• Est. Priority Date: 12/19/2012
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Parakh, Vishal
• Primary Examiner(s): Li, Aimee
• Assistant Examiner(s): Chan, Tracy
• Application Number:
  US13/720,893
• Time in Patent Office: 1,112 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1441 Resetting or repowering
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/152 Virtualized environment, e.g. logically partitioned system
• CPC Class Codes: G06F 2212/225 Hybrid cache memory, e.g. having both volatile and non-volatile portions
• CPC Class Codes: G06F 2212/284 being distributed
• CPC Class Codes: G06F 2212/314 In storage network, e.g. network attached cache
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Processes are disclosed for decreasing contention in caches in order to increase the efficiency of multi-threaded or multi-processor systems. By using multiple locks in a cache, smaller portions of the cache can be locked during cache updates (e.g., during a data update or a storage block eviction). As only small portions of the cache are locked at any given time, contention between threads, particularly in multi-processor implementations, will likely be reduced. For example, if different threads are trying to update different entries in the cache, the threads can proceed with updating the cache concurrently.

Claims

1. A system for updating cached data, the system comprising:

computer memory for storing a caching structure, the caching structure including multiple locks and a plurality of entries, each entry stored in one or more storage blocks;

a first processor configured to;

obtain a first group lock and a first entry lock, the first group lock controlling access to at least a first entry and a second entry, the first entry lock controlling access to the first entry, wherein the first group lock and the first entry lock are obtained as shared locks;

identify first storage nodes associated with the first entry using first associative array value that associates the first storage nodes with the first entry;

subsequent to identifying the first storage nodes, release the first group lock while retaining the first entry lock for the first entry;

convert the first entry lock into an exclusive lock;

disassociate the first storage nodes from the first entry by deleting the first associative array value;

update the first storage nodes; and

subsequent to updating the first storage nodes, release the first entry lock; and

a second processor configured to;

obtain the first group lock and a second entry lock, the first group lock controlling access to at least the first entry and the second entry after the first processor obtains the first group lock and prior to the first processor releasing the first group lock, the second entry lock controlling access to the second entry, wherein the first group lock and the second entry lock are obtained as shared locks;

identify second storage nodes associated with the second entry using a second associative array value that associates the second storage nodes with the second entry;

subsequent to identifying the second storage nodes, release the first group lock while retaining the second entry lock for the second entry;

convert the second entry lock into an exclusive lock;

disassociate the second storage nodes from the second entry by deleting the second associative array value;

update the second storage nodes; and

subsequent to updating the second storage nodes, release the second entry lock;

wherein the first processor updates the first storage nodes at least partially concurrently with the second processor updating the second storage nodes.

2. The system of claim 1, wherein the first group lock, the first entry lock and the second entry lock are spinlocks.

3. The system of claim 1, wherein the caching structure includes an entry lock for each entry in the caching structure.

4. The system of claim 1, wherein the computer memory comprises processor cache memory.

5. The system of claim 1, wherein the computer memory comprises random access memory.

6. The system of claim 1, wherein the multiple locks are applied during a write operation and not during a read operation.

7. A method for updating cached data, the method comprising:

receiving updated data for a first entry in a cache, the cache including multiple locks and a plurality of entries stored in the cache;

receiving updated data for a second entry in the cache;

obtaining, by a first thread, a first group lock and a first entry lock, the first entry lock controlling access to the first entry in the cache, the first group lock controlling access to at least the first entry and the second entry;

identifying first storage nodes associated with the first ent using a first associative array value that associates the first storage nodes with the first entry;

subsequent to identifying the first storage nodes, releasing, by the first thread, the first group lock while retaining the first entry lock;

disassociating the first storage nodes from the first entry by deleting the first associative array value;

obtaining, by a second thread, the first group lock and a second entry lock, the first group lock controlling access to at least the first entry and the second entry, the first group lock obtained after obtaining the first group lock and prior to releasing the first group lock, the second entry lock controlling access to the second entry in the cache; and

updating, by the first thread, the first entry and updating, by the second thread, the second entry, wherein the updating by the first thread and the second thread occur at least partially concurrently.

8. The method of claim 7, wherein obtaining, by the first thread, the first group lock and the first entry lock comprises obtaining the first group lock and the first entry lock as shared locks.

9. The method of claim 8, wherein obtaining, by the second thread, the first group lock and the second entry lock comprises obtaining the first group lock and the second entry lock as shared locks.

10. The method of claim 7 further comprising:

obtaining, by the first thread, a first exclusive lock for the first entry prior to updating the first entry; and

obtaining, by the second thread, a second exclusive lock for the second entry prior to updating the second entry.

11. The method of claim 10, wherein obtaining the first exclusive lock comprises converting the first entry lock from a shared lock to an exclusive lock.

12. The method of claim 10, wherein the first exclusive lock for the first entry is distinct from the first entry lock.

13. The method of claim 7 further comprising:

releasing, by the first thread, the first entry lock subsequent to updating the first entry; and

releasing, by the second thread, the second entry lock subsequent to updating the second entry.

14. The method of claim 7 further comprising, obtaining, by the first thread, a lock on a data structure for maintaining priority order and updating the data structure to reflect the update to the first entry.

15. The method of claim 7, wherein the first entry lock and second entry lock are spinlocks.

16. The method of claim 7, wherein the first entry lock and second entry lock are semaphores.

17. The method of claim 7, wherein the first entry lock is configurable to function as an exclusive lock or a shared lock.

18. The method of claim 7, wherein the first entry lock functions as a write lock or a read lock.

19. The method of claim 7, wherein the caching structure includes an entry lock for each entry in the caching structure.

20. The method of claim 7, wherein the cache comprises:

a hash table configured to map key/value pairs, each key/value pair comprising a key portion and a value portion;

the first data structure comprising a doubly-linked list that reflects the access order of data in the cache; and

one or more linked lists of storage blocks for storing data, wherein each value portion references a linked-list of one or more storage blocks.

21. The method of claim 20, wherein the caching structure includes a bucket lock for each bucket of the hash table.

22. The method of claim 7, wherein the first thread is operating on a first processor and the second thread is operating on a second processor.

23. Non-transitory computer storage having stored thereon instructions that, when executed by a computer system, cause the computer system to perform operations comprising:

receiving updated data for a first entry and a second entry in a cache, the cache including multiple locks and a plurality of entries;

obtaining, by a first thread, a first group lock and a first entry, the first entry lock controlling access to the first entry in the cache, the first group lock controlling access to at least the first entry and the second entry;

identifying first storage nodes associated with the first ent using a first associative array value that associates the first storage nodes with the first entry;

subsequent to the identifying the first storage nodes, releasing, by the first thread, the first group lock while retaining the first entry lock;

disassociating the first storage nodes from the first entry by deleting the first associative array value;

obtaining, by a second thread, the first group lock and a second entry lock, the first group lock controlling access to at least the first entry and the second entry, the first group lock obtained after obtaining the first group lock and prior to releasing the first group lock, the second entry lock controlling access to the second entry in the cache; and

updating, by the first thread, the first entry and updating, by the second thread, the second entry, wherein the updating by the first thread and the second thread occur at least partially concurrently.

24. The non-transitory computer storage of claim 23, wherein obtaining, by the first thread, the first group lock and the first entry lock comprises obtaining the first group lock and the first entry lock as shared locks.

25. The non-transitory computer storage of claim 24, wherein obtaining, by the second thread, the first group lock and the second entry lock comprises obtaining the first group lock and the second entry lock as shared locks.

26. The non-transitory computer storage of claim 23 further comprising:

obtaining, by the first thread, a first exclusive lock for the first entry prior to updating the first entry; and

obtaining, by the second thread, a second exclusive lock for the second entry prior to updating the second entry.

27. The non-transitory computer storage of claim 23, the operations further comprising:

releasing, by the first thread, the first entry lock subsequent to updating the first entry; and

releasing, by the second thread, the second entry lock subsequent to updating the second entry.

28. The non-transitory computer storage of claim 23, wherein the caching structure includes a lock for a group of entries in the caching structure.

29. The non-transitory computer storage of claim 23, wherein the caching structure further comprises:

a first data structure configured to track the access order of data in the caching structure;

a second data structure configured to map key/value pairs, each key/value pair comprising a key portion and a value portion; and

one or more of a third data structure configured to track storage blocks for storing data.

30. The non-transitory computer storage of claim 23, wherein the caching structure includes a lock for each entry of the first data structure.