Multi-lock caches

• US 10,176,057 B2
• Filed: 01/29/2018
• Issued: 01/08/2019
• 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, Kanawati, Antoun Joubran
• Primary Examiner(s): Chan, Tracy C.
• Application Number:
  US15/882,982
• Publication Number:
  US 20180150364A1
• Time in Patent Office: 344 Days
• Field of Search: None
• CPC Class Codes: G06F 11/1441 Resetting or repowering
• CPC Class Codes: G06F 11/1446 Point-in-time backing up or restoration of persistent data
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• 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/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G06F 2212/281 Single cache
• CPC Class Codes: G06F 2212/284 being distributed
• CPC Class Codes: G06F 2212/313 In storage device
• CPC Class Codes: G06F 2212/314 In storage network, e.g. network attached cache
• CPC Class Codes: G06F 2212/608 Details relating to cache mapping

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 comprising:

a data store configured to store an associative array and a plurality of entries, wherein individual entries of the plurality of entries are stored in one or more storage blocks of a plurality of storage blocks, and wherein individual locks of a plurality of locks control access to at least one storage block of the plurality of storage blocks;

a first processor configured to;

obtain control of a shared first group lock and a shared first entry lock, the shared first group lock controlling access to at least a first entry and a second entry, and the shared first entry lock controlling access to the first entry;

determine that the associative array associates the first entry with a first storage block of the plurality of storage blocks;

obtain control of an exclusive first entry lock, the exclusive first entry lock controlling exclusive access to the first entry;

modify the associative array to dissociate the first storage block from the first entry; and

release control of the exclusive first entry lock; and

a second processor configured to;

while the first processor has control of the shared first group lock, obtain control of the shared first group lock and a shared second entry lock, the shared second entry lock controlling access to the second entry;

determine that the associative array associates the second entry with a second storage block of the plurality of storage blocks;

obtain control of an exclusive second entry lock, the exclusive second entry lock controlling exclusive access to the second entry;

modify the associative array to dissociate the second storage block from the second entry; and

release control of the exclusive second entry lock.

2. The system of claim 1, wherein the first processor is configured to:

while the first processor has control of the exclusive first entry lock, modify the associative array to associate a third storage block with the first entry.

3. The system of claim 1, wherein the first processor has control of the exclusive first entry lock at least partially concurrently with the second processor having control of the exclusive second entry lock.

4. The system of claim 1, wherein the first processor configured to obtain control of the exclusive first entry lock is configured to convert the shared first entry lock into the exclusive first entry lock.

5. The system of claim 1, wherein the shared first entry lock is distinct from the exclusive first entry lock, and wherein the first processor is configured to release control of the shared first entry lock subsequent to obtaining control of the exclusive first entry lock.

6. A computer-implemented method comprising:

receiving a request to access a first entry in a cache, the cache comprising a plurality of storage nodes, a plurality of locks, and a plurality of entries, wherein individual locks each of the plurality of locks control access to one or more storage nodes of the plurality of storage nodes, and wherein individual entries of the plurality of entries are stored in at least one node of the plurality of storage nodes;

receiving a request to modify the first entry in the cache;

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

determining that an associative array associates the first entry with a first storage node of the plurality of storage nodes;

accessing, by the first thread, the first storage node;

identifying, by a second thread, the first group lock and the first entry lock;

in response to a determination that the first thread is accessing the first storage node at least partially concurrently with the second thread having control of the first entry lock, modifying, by the second thread, the associative array to associate the first storage node with a temporary list, the temporary list identifying storage nodes that are in use but marked for eviction;

modifying, by the second thread, the associative array to dissociate the first entry and the first storage node;

at a subsequent time, determining, by the second thread, that the first thread is no longer accessing the first storage node; and

modifying, by the second thread, the associative array to dissociate the first storage node and the temporary list.

7. The computer-implemented method of claim 6 further comprising:

obtaining, by the second thread, control of an exclusive first entry lock prior to modifying the associative array to dissociate the first storage node and the temporary list, wherein the exclusive first entry lock controls exclusive access to the first entry; and

releasing, by the second thread, control of the exclusive first entry lock subsequent to modifying the associative array to dissociate the first storage node and the temporary list.

8. The computer-implemented method of claim 7, wherein the determination that the first thread is accessing the first storage node comprises an unsuccessful attempt to obtain control of the exclusive first entry lock.

9. The computer-implemented method of claim 7, wherein the determination that the first thread is accessing the first storage node comprises a determination that the first thread has control of the first entry lock.

10. The computer-implemented method of claim 7, wherein determining that the first thread is no longer accessing the first storage node comprises successfully obtaining control of the exclusive first entry lock.

11. The computer-implemented method of claim 7, wherein determining that the first thread is no longer accessing the first storage node comprises determining that the first thread has released control of the shared first entry lock.

12. The computer-implemented method of claim 7, wherein the request to modify the first entry includes an update to be applied to the first entry.

13. The computer-implemented method of claim 12 further comprising:

storing, by the second thread, at least a portion of the update in a second storage node; and

modifying, by the second thread, the associative array to associate the second storage node with the first entry.

14. The computer-implemented method of claim 6, wherein the request to modify the first entry comprises a request to evict the first entry.

15. The computer-implemented method of claim 6, wherein the first group lock is associated with a hash key, and wherein the hash key is associated with both the first entry and the second entry.

16. A non-transitory computer-readable medium storing computer-executable instructions that, when executed by a processor, cause the processor to perform operations comprising:

receiving a first request associated with a first entry in a cache, the cache including a plurality of storage nodes and a plurality of entries;

receiving a second request associated with a second entry in the cache;

in response to the first request;

determining that an associative array associates the first entry with a first storage node;

causing a first thread to obtain control of a first entry lock, the first entry lock controlling access to the first entry;

causing the first thread to modify the associative array to dissociate the first entry from the first storage node; and

causing the first thread to release control of the first entry lock; and

in response to the second request;

determining that the associative array associates the second entry with a second storage node;

causing a second thread to obtain control of a second entry lock, the second entry lock controlling exclusive access to the second entry;

causing the second thread to modify the associative array to dissociate the second entry from the second storage node; and

causing the second thread to release control of the second entry lock, wherein the first thread has control of the first entry lock and the second thread has control of the second entry lock at least partially concurrently.

17. The non-transitory computer-readable medium of claim 16, wherein obtaining control of the first entry lock comprising converting shared control of the first entry lock into exclusive control of the first entry lock.

18. The non-transitory computer-readable medium of claim 16, the operations further comprising causing the first thread to obtain shared control of a group lock and the first entry lock, the group lock controlling access to the first entry and the second entry.

19. The non-transitory computer-readable medium of claim 18, the operations further comprising causing the first thread to release shared control of the group lock prior to obtaining exclusive control of the first entry lock.

20. The non-transitory computer-readable medium of claim 16, wherein the first request comprises a read operation or a write operation.