Fine-Grained Locking for Hash Tables

The Problem: Race Conditions in the Hash Table

Imagine two threads trying to insert new keys that both hash to the same bucket. Let's say bucket k is initially empty (buckets[k] == NULL).

1. Thread A executes insert(key_A). It calculates the index k. It sees that buckets[k] is NULL.
2. Before Thread A can allocate and link a new node, the OS scheduler preempts it and runs Thread B.
3. Thread B executes insert(key_B). It also calculates the index k and sees that buckets[k] is NULL.
4. Thread B allocates a new node for key_B, sets its next pointer to NULL, and updates buckets[k] to point to this new node.
5. Now, the scheduler switches back to Thread A. It resumes where it left off. It still believes buckets[k] was NULL, so it allocates a new node for key_A, sets its next pointer to NULL, and updates buckets[k] to point to its new node.

The result? The node created by Thread B is lost forever—a memory leak and a lost insertion. The buckets[k] pointer has been overwritten by Thread A. This is a classic race condition. To prevent this, we must ensure that operations on a bucket are atomic.

Approach 1: Coarse-Grained Locking

The simplest solution is to use a single mutex to protect the entire hash table.

• Design: Add one pthread_mutex_t to the HashTable struct.
• Protocol: Before any thread can perform any operation (insert, lookup, or delete), it must lock this single mutex. It unlocks it upon completion.

This approach is easy to implement and guarantees thread safety. However, it comes at a huge performance cost. If Thread A is inserting into bucket 5, and Thread B wants to look up a key in bucket 99, Thread B must wait for Thread A to finish. The lock becomes a bottleneck, serializing all access and eliminating any potential for concurrent operations. We can do much better.

Approach 2: Fine-Grained Locking (Per-Bucket Locking)

A much more scalable approach is to use fine-grained locking. Instead of one lock for the entire table, we use one lock for each bucket.

• Design: Maintain an array of mutexes, with a one-to-one mapping to the array of buckets.
• Protocol: A thread wishing to operate on a bucket first identifies the bucket index. It then locks only the mutex corresponding to that specific bucket.

This design allows two threads to access the hash table concurrently, as long as they are operating on different buckets. This dramatically increases the potential for parallelism, especially for large hash tables with well-distributed keys.

The following reading from the OSTEP book discusses this exact strategy and its impressive performance benefits.

As the text highlights, this design "scales magnificently." Let's look at what this design means for our C code.

Designing the Data Structure and Initialization

To implement per-bucket locking, we must modify our HashTable structure to include an array of mutexes alongside the array of buckets.

The following resource provides a concrete C implementation of this design. We will focus on the structure definition and the initialization function.

Let's break down the key changes required for our design.

1. Modifying the HashTable Struct

Based on the resource, our new HashTable struct should look like this. We are assuming a fixed TABLE_SIZE for simplicity, just as in the example.

#define TABLE_SIZE 101

// Node for the linked list (separate chaining)
typedef struct Node {
    char *key;
    int value; // Or a generic void*
    struct Node *next;
} Node;

// The hash table structure
typedef struct HashTable {
    Node *buckets[TABLE_SIZE];
    pthread_mutex_t locks[TABLE_SIZE]; // One mutex per bucket
} HashTable;

The crucial addition is pthread_mutex_t locks[TABLE_SIZE];. This array holds the locks that will protect each bucket's linked list.

2. Updating Initialization and Destruction Logic

An array of mutexes must be properly initialized before use and destroyed upon cleanup.

• Initialization: The init_table function must loop from i = 0 to TABLE_SIZE - 1 and call pthread_mutex_init(&table->locks[i], NULL) for each element in the locks array. This prepares each mutex for use.

• Destruction: Similarly, a free_table function must not only free the nodes and keys but also loop through the locks array and call pthread_mutex_destroy(&table->locks[i]) on each one to release system resources.

The Locking Protocol for Hash Table Operations

With the structure defined and the mutexes initialized, the final piece of the design is the protocol for using them. The rule is simple and must be followed by insert, lookup, and delete:

1. Given a key, compute the bucket index = hash(key) % TABLE_SIZE.
2. Acquire the specific lock for that bucket: pthread_mutex_lock(&table->locks[index]);
3. Perform the required linked list operation (traverse, add node, remove node) within the now-protected critical section.
4. Release the lock for that bucket: pthread_mutex_unlock(&table->locks[index]);

The insert and get functions in the LINK resource you just reviewed demonstrate this protocol perfectly. For example, the get function looks like this:

int get(HashTable* table, const char* key) {
    unsigned int index = hash(key);

    // Lock the specific bucket
    pthread_mutex_lock(&table->locks[index]);

    // Critical Section: Safe to access the linked list
    Node* current = table->buckets[index];
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            int val = current->value;
            // Unlock before returning
            pthread_mutex_unlock(&table->locks[index]);
            return val;
        }
        current = current->next;
    }

    // Unlock if key not found
    pthread_mutex_unlock(&table->locks[index]);
    return -1; // Not found
}

Notice how the lock is acquired at the beginning and released on all possible exit paths from the function.

Conclusion

In this lesson, we have designed an efficient, fine-grained locking strategy for our hash table. By moving from a single, coarse-grained lock to a per-bucket locking model, we unlock significant potential for concurrency and performance.

Key Takeaways:

• A coarse-grained lock (one for the whole table) is simple to implement but creates a major performance bottleneck, serializing all operations.
• A fine-grained locking strategy uses one mutex per hash bucket, allowing multiple threads to operate on different buckets concurrently.
• The design requires adding an array of pthread_mutex_t to the HashTable struct.
• The table initialization and destruction functions must be updated to call pthread_mutex_init and pthread_mutex_destroy for every mutex in the array.
• The core locking protocol is: identify the target bucket, lock the corresponding mutex, perform the operation, and then unlock the mutex.

Preview of the Next Lesson:
We have our blueprint. In the next lesson, we will put this design into action by implementing the thread-safe insert operation for the hash table. You will modify your existing insert function to correctly acquire and release the per-bucket lock, making it safe for concurrent execution.