The "Mutex Key Pool" Data Structure

back to index

The Problem

How do you efficiently lock access to one row in a large database table?

What Doesn't Work

Mutex Key Pool

A Mutex Key Pool is a data structure that supports two operations, locking a key and unlocking a key.

A MKP consists of a table of (Key key, Mutex mutex, int pending) and a global lock.

A table row is "free" if pending == 0.

Lock a key

Unlock a key


It is easy to see that the number of allocated mutexes scales with the number of simultaneous locked, rather than total keys.

Furthermore, there is almost never a reallocation after warmup.

Also, it is straightforward to turn the table into a hashmap, gaining O(1) lock/unlock performance.