Multi-lock caches

Patent metadata

Field	Value
Publication number	US-9229869-B1
Application number	US-201213720893-A
Country	US
Kind code	B1
Filing date	Dec 19, 2012
Priority date	Dec 19, 2012
Publication date	Jan 5, 2016
Grant date	Jan 5, 2016

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.

First claim

What is claimed is:

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

Assignees

• Amazon Tech Inc

Inventors

• Parakh Vishal

Classifications

• G06F12/0871 Primary

  Allocation or management of cache space · CPC title

• G06F12/084 Primary

  with a shared cache · CPC title

• G06F11/1441

  Resetting or repowering · CPC title

• G06F2212/1044

  Space efficiency improvement · CPC title

• G06F2212/284

  being distributed · CPC title