Building a Lock Manager for Concurrency Control

The Problem, Revisited

Let's quickly refresh our memory on why we need this. A simple, real-world example makes the problem crystal clear.

This "lost update" problem happens because the read and write operations from different transactions are interleaved without any control. The solution is to introduce locks to protect data while a transaction is working on it.

The Lock Manager: A Centralized Gatekeeper

To manage locks, a database system uses a centralized component called the Lock Manager. Think of it as a traffic controller for data access. Whenever a transaction wants to read or write an object, it must first request permission (a lock) from the lock manager.

The lock manager's job is to:

1. Receive lock requests from transactions.
2. Grant the lock if it's compatible with existing locks.
3. Block the transaction if the request is not compatible.
4. Keep track of which transactions hold which locks.
5. Manage the release of locks when a transaction is done.

The following video segment from CMU's database course introduces this concept.

As the video highlights, it's vital to distinguish between locks and latches. Given your background in C++, you can think of it this way:

• Locks: A high-level, logical concept managed by the database to ensure transaction serializability. They protect database objects (like tuples or tables) for the duration of a transaction.
• Latches: A low-level, physical synchronization primitive, like a std::mutex. They provide short-term protection for the internal data structures of the database itself, such as the lock manager's internal hash table or the buffer pool. They are held for microseconds, not the entire length of a transaction.

Today, we are building a manager for transactional locks, but we will need to use latches inside our implementation to protect its own data structures from concurrent access by different worker threads.

Lock Modes: Shared and Exclusive

To allow for more concurrency, we don't just have one type of lock. We have different lock modes. The two most basic and important modes are:

1. Shared Lock (S-lock): A transaction requests a shared lock before it reads an object.
2. Exclusive Lock (X-lock): A transaction requests an exclusive lock before it writes to an object.

These locks follow a simple compatibility rule: multiple transactions can hold a shared lock on the same object simultaneously, but an exclusive lock cannot be shared with any other lock (not even a shared one). This is summarized in the lock compatibility matrix:

This logic is intuitive: it's fine for many people to read a document at once, but if someone is editing it, nobody else should be able to read or edit it until they are finished.

Designing the Lock Manager's Internals

Now for the core of the lesson: how would we implement this? This is a great systems design problem that maps well to your experience with data structures and C++.

Let's start with a high-level visual. The lock manager needs a central data structure to track the state of all locked objects. A hash table is a perfect fit, mapping an object identifier (e.g., a RecordID or RID for a tuple) to its lock information.

Based on this diagram and the requirements of our system, for each RID that has a lock on it, we need to store:

• A queue of lock requests. This is crucial for transactions that must wait. Each request in the queue should contain at least the transaction ID (txn_id) and the desired lock mode (S or X).
• The current state of the lock, such as the lock mode (e.g., SHARED, EXCLUSIVE) and which transactions are currently holding the lock.

This waiting queue is fundamental. When a transaction requests a lock that cannot be granted, we create a LockRequest object, add it to the queue, and put the transaction's thread to sleep. When another transaction unlocks the object, the lock manager re-examines the queue and wakes up any waiting threads whose requests can now be granted.

Implementing the Wait/Notify Logic in C++

In C++, this blocking and waking mechanism is implemented using std::mutex (a latch) and std::condition_variable.

• A std::mutex protects the lock manager's internal hash table, ensuring only one thread can modify it at a time.
• A std::condition_variable is used to block a thread until it is notified by another. Each LockRequest in our waiting queue can contain a condition variable for its transaction to wait on.

This is a classic readers-writer lock problem. Let's look at a technical resource that discusses a common pitfall and provides a C++ solution.

The Implementation Task

Now let's formalize our implementation plan. We can use the project specification from CMU's course as a guide. It provides a clear API for a lock manager that you would build in C++.

As outlined in the spec, your lock manager class would need to implement these core methods:

• LockShared(Transaction* txn, const RID& rid)
• LockExclusive(Transaction* txn, const RID& rid)
• LockUpgrade(Transaction* txn, const RID& rid)
• Unlock(Transaction* txn, const RID& rid)

Let's walk through the high-level logic for LockExclusive, which is the most restrictive case.

Logic for LockExclusive(txn, rid):

1. Acquire the lock manager's global latch (std::unique_lock<std::mutex>).
2. Look up the LockRequestQueue for the given rid in your hash map.
3. Check if any other transaction holds any lock (S or X) on this rid.
4. If a conflict exists:
   a. Create a LockRequest for this transaction and add it to the wait queue.
   b. Block the current thread by calling wait() on a std::condition_variable. The thread will sleep here until another thread calls notify.
   c. When woken up, re-check for conflicts (this handles spurious wakeups). If a conflict still exists, go back to sleep.
5. If no conflict exists:
   a. Grant the lock. Update the LockRequestQueue to show that this txn now holds an exclusive lock.
6. Release the lock manager's latch.

The logic for Unlock(txn, rid) is the reverse process:

1. Acquire the global latch.
2. Remove txn from the list of lock holders for rid.
3. Check the wait queue for rid. Iterate through the waiting requests and see which ones are now compatible (e.g., multiple S-locks can be granted, or one X-lock).
4. For each transaction you decide to unblock, call notify_one() or notify_all() on its std::condition_variable.
5. Release the global latch.

Conclusion

Today, we designed the machinery for one of the most fundamental concurrency control methods. We moved from the what (serializability) to the how (a lock manager).

Key Takeaways:

• A lock manager is a centralized database component that arbitrates access to data by granting, denying, and tracking locks.
• The two primary lock modes are Shared (read) and Exclusive (write), governed by a compatibility matrix.
• A practical implementation uses a hash map to store a request queue for each locked object.
• The logic for blocking and waking up transactions is implemented using low-level latches (std::mutex) and condition variables (std::condition_variable).

Preview of the Next Lesson

Having a lock manager is like having a throttle and a brake in a car—they are the mechanisms of control. But you still need rules of the road to drive safely. How should transactions use the lock manager to guarantee serializability?

In our next lesson, we will implement Strict Two-Phase Locking (S2PL), a protocol that dictates when transactions can acquire and release locks. By integrating S2PL with our lock manager, we will have a complete, working concurrency control system that guarantees correctness.