Part 5 of 7 · 3 min read
Bucket locks
Think of it this way. A mail room with a separate door and clerk for each row of pigeonholes lets many clerks work together, as long as no two want the same row. The analogy stops in one place: a clerk is tied to one row, and a thread works on whatever bucket its key chooses.
In plain words: Two operations conflict only if they work on the same bucket. So each bucket can have its own lock. This is fine-grained locking (page 3). The array of locks is called a lock stripe when each lock covers one bucket, or a group of them.
pthread_mutex_t lock[BUCKETS]; /* lock[i] guards bucket[i] only */
void insert(long k) {
struct node *n = malloc(sizeof *n); n->key = k;
pthread_mutex_t *m = &lock[k % BUCKETS]; /* the lock of this key's bucket */
pthread_mutex_lock(m);
n->next = bucket[k % BUCKETS]; bucket[k % BUCKETS] = n;
pthread_mutex_unlock(m);
}
The rule for correctness is the one of page 3: every access to a bucket holds that bucket's lock. Two threads in different buckets run in parallel. Two in the same bucket take turns.
The times, with the same total work:
| Threads | One lock | A lock for each bucket |
|---|---|---|
| 1 | 0.538 | 0.473 |
| 2 | 1.467 | 0.416 |
| 4 | 0.966 | 0.314 |
With bucket locks, the 2-thread run is faster than the 1-thread run, and 4 threads are faster again, by a factor of 1.5 (0.473 to 0.314). The gain is smaller than the two processors could give, and the reasons are instructive. The malloc calls take an internal lock of the allocator. The long chains make each operation memory-bound. Only two processors exist. A correct reading: fine-grained locking removed the contention that made the coarse version slower, and the rest is limited by other shared resources.
Costs and cautions of fine-grained locking:
- More memory. One mutex for each bucket (40 bytes for the standard mutex on this system, so 1,024 locks is about 40 kB).
- Operations that touch many buckets are harder. Counting all keys, growing the table (re-hashing into more buckets) or iterating needs a consistent view. The usual remedy is to take all the locks, in bucket order (the global order of page 7), or to use a separate lock for resizing.
- More chances for deadlock whenever an operation takes more than one lock.
Production tables, such as the ones in Java's standard library or in the Linux kernel, are variations on these ideas, often with lock-free reads.
Lock striping
Lock striping is a technique in which a shared structure is split into parts, each guarded by its own lock, so that operations on different parts run in parallel and only operations on the same part exclude each other.
Example: a hash table with one mutex for each of its 1,024 buckets.
Check yourself: 1. When do two operations on the table conflict, with bucket locks? 2. Why was the speed-up smaller than 2? 3. How would you count all keys safely?