Hash Table Resizing and Global Locks

Why and When to Resize?

First, let's define what a resize operation entails and when it should be triggered.

• The Goal: Maintain short collision chains to preserve the hash table's near-constant time performance for insert, lookup, and delete.
• The Metric: The load factor is the key metric used to decide when to resize. It's defined as:
  $\text{Load Factor}=\frac{\text{Number of elements in the table}}{\text{Number of buckets}}$
• The Trigger: A resize is typically triggered when the load factor exceeds a predefined threshold (e.g., 0.75 or 1.0). The check for this condition is most naturally placed within the HashTable_Insert function, as it's the only operation that increases the number of elements. The thread that causes the load factor to exceed the threshold would then be responsible for initiating the resize.

The fundamental process of resizing involves:

1. Allocating a new, larger array of buckets (usually double the size).
2. Iterating through every element in the old table.
3. For each element, recalculating its hash index based on the new table size.
4. Inserting the element into the correct bucket in the new table.
5. Freeing the old table's bucket array.
6. Atomically replacing the pointer to the old table with the pointer to the new one.

To understand the core mechanics, let's review the process from a sequential perspective.

The Problem with Fine-Grained Locks During a Resize

As the slides illustrate, a resize is a global operation. It doesn't just touch one bucket; it potentially touches every single element and every bucket in the table. This is where our per-bucket locking strategy breaks down.

Consider the following race condition:

1. Thread R (Resizer): The hash table is full. Thread R begins a resize. It allocates a new, larger table.
2. Thread I (Inserter): Concurrently, Thread I wants to insert a new element. It calculates the bucket index based on the old table size.
3. Thread R: Continues its work. It moves all elements from the old table to the new one and then frees the old bucket array.
4. Thread I: Now proceeds with its insertion. It calls pthread_mutex_lock on a mutex from the now-freed old bucket array, leading to undefined behavior (likely a crash). Even if it succeeded, it would be inserting its new element into a dead table that will never be accessed again, causing a silent data loss.

A similar race can happen with lookup and delete operations, which might try to read from a table that is in a nonsensical, partially-resized state. Our per-bucket locks cannot prevent this because they only guard access to a single bucket's list; they do not protect the bucket array pointer itself or coordinate activity across different buckets.

The Global Lock: A "Stop-the-World" Solution

To perform a resize safely in our current design, we need a synchronization mechanism that can halt all other operations on the table. This is the role of a global lock.

A global lock ensures that the resizing thread has exclusive access to the entire data structure. A pthread_rwlock_t (read-write lock) is a natural fit for this:

• Resize operation: Must acquire an exclusive write lock. This blocks all other threads (readers and writers) from entering any hash table function.
• All other operations (insert, lookup, delete): Must acquire a read lock. This allows multiple readers to proceed concurrently but blocks them if a writer (the resizer) is active or waiting.

With a global read-write lock, the resize algorithm becomes:

1. Acquire the global write lock. No other thread can now access the table.
2. Perform the resize: allocate new table, re-hash and move all elements.
3. Update the HashTable struct's main buckets pointer to point to the new array.
4. Release the global write lock. Other threads can now proceed, accessing the newly resized table.
5. Free the old bucket array. (This can be done after releasing the lock if the old pointer is stored in a local variable, similar to our "unlock-then-free" pattern).

This approach, often called "stop-the-world," is simple and guarantees correctness. However, it comes at a significant performance cost: all operations are stalled while the potentially lengthy resize operation completes.

Summary of Conditions

So, to summarize, a global lock is required for resizing our current hash table design because of the following conditions:

1. The Operation is Global: The resize process is not localized to one bucket. It reads from all old buckets and writes to all new buckets, fundamentally restructuring the entire data structure.
2. The Data Structure Pointer Changes: The core pointer to the array of buckets is modified. Any thread that reads this pointer must be prevented from doing so while it's in a transitional state.
3. Fine-Grained Locks are Insufficient: Per-bucket locks only protect the integrity of the linked list within that bucket. they do not protect the bucket array itself from being modified or freed from under them.

While a global lock is the most straightforward and safest solution for this design, it's important to recognize its limitation as a scalability bottleneck. Advanced, lock-free, or incremental resizing algorithms exist that are far more complex but avoid this "stop-the-world" pause. They are a fascinating topic for further study but are beyond the scope of our current implementation.

Conclusion

This lesson concludes our deep dive into implementing a concurrent hash table. We've gone from a basic design to a fully thread-safe data structure with fine-grained locking, and now we've analyzed the complexities of adding dynamic resizing.

Key Takeaways:

• Hash table resizing is triggered when the load factor exceeds a certain threshold, typically checked after an insert.
• Resizing is a global operation that rebuilds the entire table, making our fine-grained, per-bucket locking scheme insufficient on its own.
• To ensure correctness, a global lock (like a write lock from a pthread_rwlock_t) is needed to create a "stop-the-world" pause, giving the resizer exclusive access to prevent race conditions and use-after-free errors.
• This simple, correct solution introduces a scalability bottleneck, highlighting a fundamental trade-off in concurrent data structure design.

Preview of the Next Lesson:
We've spent a lot of time on the intricacies of one data structure. Now, we'll zoom out to look at a powerful and widely used concurrency pattern: the thread pool. In the next module, we will begin designing the core components of a thread pool, which will allow us to efficiently manage a set of worker threads to execute tasks from a queue.