Implementing Reader-Writer Locks for Concurrent Graph Access

The Problem with Simple Mutexes

Your first instinct might be to protect the entire graph with the pthread_mutex_t you're already familiar with. Before any search or insertion, a thread would lock the mutex, and unlock it upon completion. This would certainly guarantee correctness and prevent race conditions.

However, for a system where performance is paramount, this is a deeply unsatisfying solution. Searches are read-only operations. If ten threads want to search the graph simultaneously, there's no logical reason they shouldn't be able to. Yet, a simple mutex would force them into a queue, executing one by one, destroying any possibility of read parallelism. Given that vector databases are typically "read-mostly" (far more searches than insertions), this would create a massive performance bottleneck.

The Read-Write Lock Solution

A read-write lock is designed precisely for this scenario. It offers a more nuanced approach than a simple mutex by allowing two different kinds of locks: a "read lock" and a "write lock".

The rules are as follows:

1. Any number of threads can hold a read lock simultaneously.
2. Only one thread can hold a write lock at any given time.
3. If a thread holds a write lock, no other thread (reader or writer) can acquire a lock.
4. If any thread holds a read lock, a thread trying to acquire a write lock will block until all readers have released their locks.

This perfectly matches our requirements: we can have many concurrent searches (readers), but an insertion (a writer) gets exclusive access to modify the graph safely.

The pthread_rwlock_t API

Now that you have a conceptual and practical understanding, let's look at the formal API you'll be using. A read-write lock is a distinct type, pthread_rwlock_t, and it has its own set of functions.

As you read, the core functions to note are:

• pthread_rwlock_rdlock(): Acquires a read lock. It will block if a writer currently holds the lock.
• pthread_rwlock_wrlock(): Acquires a write lock. It will block if any thread (reader or writer) currently holds the lock.
• pthread_rwlock_unlock(): Releases either a read or write lock. The system knows which type of lock the thread holds.

Integrating the Lock into the HNSW Graph

Now, let's apply this to our project. You will add a pthread_rwlock_t directly to your main graph data structure.

typedef struct {
    // ... other graph metadata like entry_point, max_layer, etc. ...
    
    memory_arena_t node_pool; // Pool for allocating nodes
    
    // The new lock to protect the entire graph
    pthread_rwlock_t lock;
    
} hnsw_index_t;

When you initialize your graph, you will also initialize this lock:

// In your hnsw_create function
int hnsw_init(hnsw_index_t *graph, ...) {
    // ... other initializations ...
    
    if (pthread_rwlock_init(&graph->lock, NULL) != 0) {
        // Handle error
        return -1;
    }
    
    return 0;
}

Now, you can protect your search and insert functions. The search function is a "reader" because it only traverses the graph, while the insert function is a "writer" because it modifies nodes and their connections.

Following this pattern, your graph operations will be structured like this:

Search Function (Reader)

void hnsw_search(hnsw_index_t* graph, const float* query_vector, size_t k, result_t* results) {
    // Acquire a read lock. Multiple searches can enter this section concurrently.
    pthread_rwlock_rdlock(&graph->lock);
    
    // ...
    // The entire search logic, from the top layer down to layer 0,
    // happens here while the lock is held.
    // ...

    // Release the read lock.
    pthread_rwlock_unlock(&graph->lock);
}

Insertion Function (Writer)

void hnsw_insert(hnsw_index_t* graph, const float* vector) {
    // Acquire a write lock. Only one insertion can happen at a time,
    // and all searches will wait.
    pthread_rwlock_wrlock(&graph->lock);
    
    // ...
    // The entire insertion logic, including layer selection,
    // finding neighbors, and updating connections, happens here.
    // ...

    // Release the write lock, allowing waiting readers and writers to proceed.
    pthread_rwlock_unlock(&graph->lock);
}

Performance Impact

The benefit of this approach is significant, especially for read-heavy workloads. Let's look at some data.

The data is clear: for read-mostly scenarios, a read-write lock is vastly superior to a single mutex.

A final point on performance is the issue of writer starvation. The POSIX standard doesn't specify whether new readers should be blocked if a writer is waiting. In many common implementations (which are "read-preferring"), a continuous stream of incoming read-lock requests can indefinitely prevent a writer from acquiring the lock. While not something you need to solve right now, it's a critical concept in high-performance systems design, where fairness policies might be needed to guarantee writers eventual access.

Conclusion

In this lesson, you've added a crucial piece of synchronization to our concurrent vector database. By understanding the readers-writers problem, you've moved beyond simple mutexes to a more sophisticated and performant locking strategy.

Key Takeaways:

• Protecting a read-mostly data structure with a single mutex creates a severe performance bottleneck by serializing all accesses.
• A read-write lock (pthread_rwlock_t) solves this by allowing concurrent access for multiple readers but exclusive access for a single writer.
• You apply this to your HNSW graph by taking a read lock (pthread_rwlock_rdlock) for search operations and a write lock (pthread_rwlock_wrlock) for insertion/modification operations.
• Performance data confirms that for read-heavy workloads, read-write locks provide significantly better scalability than simple mutexes.

The pthread_rwlock_t we've implemented is a "coarse-grained" lock—it locks the entire graph. While effective, it can still be a point of contention. In our next lesson, we will explore an even more granular approach. We will investigate C11 atomic types (<stdatomic.h>), which allow us to perform certain simple operations (like incrementing a counter) in a thread-safe way without using any locks at all. This will open the door to further, fine-grained performance optimizations.