Multi-lock caches
First Claim
Patent Images
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.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5)
-
-
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. - View Dependent Claims (7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
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. - View Dependent Claims (17, 18, 19, 20)
-
Specification