Thread-Safe Hash Table Lookups

The Need for Locking in a Read Operation

Let's start with a standard non-thread-safe lookup function. Its logic is straightforward: hash the key to find the bucket, then traverse the bucket's linked list to find a matching key.

// Non-thread-safe lookup
int HashTable_Lookup(HashTable* table, const char* key) {
    unsigned int index = hash(key) % TABLE_SIZE;

    // Traverse the linked list for the given bucket
    Node* current = table->buckets[index];
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            return current->value; // Found
        }
        current = current->next;
    }

    return -1; // Not found
}

In a single-threaded world, this is perfect. But what happens if another thread calls HashTable_Insert or HashTable_Delete on the same bucket at the same time?

1. Race with insert: An insert operation adds a new node at the head of the list. If a lookup is traversing the list just as an insert modifies the head pointer and the new node's next pointer, the lookup thread could read inconsistent pointers, potentially missing the new node or even crashing.
2. Race with delete (more dangerous): Imagine your lookup thread is currently examining a node (current). At that exact moment, another thread deletes this same node and calls free(current). When your lookup thread proceeds to current = current->next;, it is accessing freed memory. This is a classic use-after-free bug, leading to undefined behavior and likely a crash.

The entire list traversal is a critical section. We must ensure that the linked list's structure does not change while we are reading it. Therefore, even read-only operations need protection.

Implementing a Thread-Safe lookup

The solution is to apply the same per-bucket locking protocol we used for insert:

1. Calculate the bucket index.
2. Acquire the lock for that specific bucket.
3. Traverse the linked list to find the key.
4. Release the lock.
5. Return the result.

The following resource provides a professionally written example of this exact pattern.

Inspired by that clean implementation, we can write our thread-safe HashTable_Lookup function. Note the use of a return variable (found_value) to ensure we can unlock the mutex before the final return statement. This pattern prevents us from needing unlock calls in multiple places inside the function body.

int HashTable_Lookup(HashTable* table, const char* key) {
    int found_value = -1; // Default to "not found"
    unsigned int index = hash(key) % TABLE_SIZE;

    // 1. Acquire the lock for the bucket
    pthread_mutex_lock(&table->locks[index]);

    // 2. Traverse the list within the critical section
    Node* current = table->buckets[index];
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            found_value = current->value;
            break; // Found it, exit the loop
        }
        current = current->next;
    }

    // 3. Release the lock
    pthread_mutex_unlock(&table->locks[index]);

    // 4. Return the result
    return found_value;
}

This implementation correctly protects the traversal from concurrent modifications, preventing race conditions and use-after-free errors.

// Proposed incorrect optimization
while (current != NULL) {
    if (strcmp(current->key, key) == 0) {
        found_value = current->value;
        pthread_mutex_unlock(&table->locks[index]); // <-- Release lock early
        return found_value;
    }
    current = current->next;
}
pthread_mutex_unlock(&table->locks[index]);

An Avenue for Optimization: Read-Write Locks

Our mutex-based solution is correct, but it has a performance limitation: it serializes all operations on a given bucket. If ten threads all want to lookup keys in the same bucket, they will have to wait for the mutex one by one, even though they are only reading and not interfering with each other.

This is a classic scenario where a more specialized lock can improve concurrency: the read-write lock (pthread_rwlock_t).

A read-write lock allows for two types of locking:

• Read Lock (rdlock): Multiple threads can acquire a read lock simultaneously.
• Write Lock (wrlock): Only one thread can acquire a write lock, and it excludes all readers and other writers.

For a read-heavy workload, changing our per-bucket pthread_mutex_t to a pthread_rwlock_t could significantly boost performance. lookup would use pthread_rwlock_rdlock(), while insert and delete would use pthread_rwlock_wrlock().

We will dive deep into implementing read-write locks in Module 3, but it's valuable to recognize this pattern now. Your experience with physics may bring to mind principles of superposition, where multiple non-interfering states (readers) can coexist, but an interaction that changes the system (a writer) requires a unique, exclusive state.

Implementation Challenge

Now, let's put this into practice. Using the same ph.c structure from the previous lesson, your task is to implement the thread-safe get function (their version of lookup).

// The non-thread-safe get function from ph.c
static struct entry* 
get(struct ph *t, char *key)
{
  int i;
  struct entry *e;

  i = hash(key) % NBUCKET;
  e = t->buckets[i];
  while(e != NULL){
    if(strcmp(e->key, key) == 0)
      return e;
    e = e->next;
  }
  return NULL;
}

Rewrite this get function to make it thread-safe using the per-bucket pthread_mutex_t locks available in the struct ph.

static struct entry* 
get(struct ph *t, char *key)
{
  int i;
  struct entry *e = NULL; // Initialize to NULL

  i = hash(key) % NBUCKET;

  // Acquire lock
  pthread_mutex_lock(&t->locks[i]);

  // Traverse list
  struct entry* current = t->buckets[i];
  while(current != NULL){
    if(strcmp(current->key, key) == 0) {
      e = current; // Save the result
      break;
    }
    current = current->next;
  }
  
  // Release lock
  pthread_mutex_unlock(&t->locks[i]);

  return e; // Return the saved result
}

Conclusion

Excellent work. You have now implemented a thread-safe lookup operation, completing the read-side counterpart to our insert function.

Key Takeaways:

• Read-only operations like lookup require locking to protect against data races with concurrent write operations (insert, delete).
• The critical section for a lookup spans the entire traversal of the shared linked list.
• The lock must be held until the traversal is complete to prevent use-after-free bugs and ensure data consistency.
• Using a simple mutex is a correct and robust way to ensure safety, but specialized locks like pthread_rwlock_t can offer better concurrency for read-heavy workloads, a topic we'll explore soon.

Preview of the Next Lesson:
We have handled adding and finding elements. The final core operation is delete. Implementing a thread-safe delete operation for a linked list is the most complex of the three. It requires careful pointer manipulation inside the critical section to safely unlink a node without breaking the list for other concurrent threads. We will tackle this challenge next.