Databases: Multi-Threaded Index Concurrency Control
So far, we have assumed that all the data structures are single-threaded. But, we need to allow multiply threads to safely access our data structures, to take advantage of additional CPU cores and hide the stalls in disk I/O.
Everything I'm going to talk about today is how most database systems actually work. Reddis is one thread, but VoltDB is that every B+ tree is only accessed by one thread, etc. The main idea, is that everybody does the same things that we are talking about.
How do so deal with this? We create a concurrency control protocol, to ensure "correct" results for concurrent operations on a shared object. A protocol's correctness criteria can vary, logical correctness is "am I seeing the data that I am expecting to see?" The physical correctness is "Is the internal representation of the object sound" which is what will be discussed inside of this article. We want to avoid segmentation faults. Logical correctness is another super interesting topic, but we want to first make sure that the data structures are thread-safe.
A lock is a logical concept protecting the high-level contents of the database from other transactions that are running at the same time. We'll hold them at the entire duration of the transaction, and we need to be able to roll back any changes as well.
The low level constructs is the latches, which is called locks in the operating system world. We only hold a latch for a short period, to do whatever operation that we need to do. They protect critical sections of DBMS's internal data structure, held for operation duration.
Here is a table discussing the differences between locks and latches:
There's only 2 modes, read and write. Mutiple threads are allowed to share a read latch, if a latch is in read mode. Write mode is an exclusive latch, where only one thread can access the object at a specific time. A thread cannot acquire a write latch if another thread holds the latch.
How do we implement the latch?
The first thing we can attempt is the blocking OS mutex, and it's pretty simple to use and non-scalable and example is std::mutex.
std::mutex m;
.
.
.
m.lock();
m.unlock();
In userspace (address space of process), there will be a memory location to compare and swap on to attempt to acquire that latch. However, if you don't acquire the latch, then you do a default mutex where it goes down back to the operating system. The idea is doing a compare and swap, run if good, otherwise fall back down to the OS. Now you got to update the scheduling table saying that the thread can't run yet. Try to avoid the operating system as much as possible.
Approach 2 is the test-and-set spin latch, which is very efficient. We compare and swap on a memory address, and we're allowed to change particular values to new values, and this indicates when I have acquired a latch, you don't need to have the correct C code ("if this then that") etc. An example is std::atomic<T> which is a Templated atomic keyword which is an alias for atomic<bool>. Acquiring the latch sets the white loop, and if I acquire the latch fine, but if I don't maybe fall into the while loop? However, this might be burning the CPU because you're constantly attempting to test-and-set.
std::atomic_flag latch;
while(latch.test_and_set(...)) {
//Retry? Yield? Abort?
}
We try to accomodate what I think the workload is going to have.
We and the database system can do a better job than the OS because we know exactly what context that we would be doing in regards to this latch. We have different modes, so we need a read/writer latch that can support these different modes, and manages queues to keep track of how many threads are looking for a latch, which you can maintain counters.
So there's holding and waiting, and that's how we can see where we can get latches. Remember that read latches are compatible, write latches aren't Write latch has to stall because the read latch is being held by other threads. We could stall and add to counter but eventually when the queue is empty, the write thread will get the latch. The policy depends heavily on the context with which the latch is being used.
To resize the table, take the global latch on the entire table in the header page.
The first thing is on each page we have a read or write latch that protects its contents, where threads acquire either a read or write latch. Slot latches is where each slot has its own latch, and that we can use. This is more of a fine-grain latching. There's a trade off, since we page-latches store less latches and less parallelism, but latch per slot means more parallelism, but now I'm storing more latches in every single slot, which is expensive as a result.
Let's say a thread goes along and they want to insert E. It wants to take write latch but it dfoesn't work so it needs to stall and wait. It's safe to release the read latch, because, well, it doesn't change any data whatsoever.
Instead of trying to acquire a write latch, try to acquire a read latch first, then try to acquire the write latch. The same technique will be applied for B+ trees. This is sort of the naive way.
The left is the read latch, while the right is the write latch. Inserting needs to acquire the write and read latch. The above diagram showcases slot latches. I do need to handle the case I take the read latch, release, and then if there's an insertion, you need to be able to utilize the latch to acknowledge that. However, it's top to bottom, and nobody else is coming to the other direction.
We need to handle cases of threads trying to modify contents of a node at the same time, or one thread traversing the tree while another tree splits/merges nodes, resulting in an invalid memory location.
Say we want to do a delete on a number, we traverse through the tree, go down the the leaf node, then delete our entry. However, if a node is less than half full, we have to rebalance. However, let's say before rebalancing, the OS swaps out thread and stalls since a thread tries to find a key, and then the OS stalls process 2, switches back to the first thread, and if tree rebalances then we might mess up the read policy. Do you see how it's ruining things now?
Best case scenario, we get a false negative, worst case scenario, the node got moved around, and the pointer pointed to nothing, and as a result getting to a segmentation fault.
Latch crabbing allows multiple things at the B+ tree at the same time and helps to protect certain latches. It's a protocol to allow multiple threads to access or modify a B+ tree at the same time. The basic idea is the first get the latch for the parent, then get the latch for the child, then release the latch for the parent if it's "safe", which is a node that will not split or merge when updated.
For finding, we start at the root and go down repeatedly. I obtain the R latch on the child, then unlatch the parent. For insert/delete, we first start at the root then obtain W latches are needed then if child is safe, release latches on all ancestors. Threads keep a stack of latches that I'm holding out when at some point I'm out of nodes, we release. We release latches when a table is 100% full as well. We can release the latch whenever something can accommodate a new insertion, we hold the latch otherwise. We release latches when they cannot overfill, for example B won't be full here:
We need to release earlier latches first, because someone up above who may need to start the corresponding process.
What was the first step I do? I latch the root in write mode!
In order to get the data structure, everyone needs to hold onto this write latch, which is an issue.
[REWATCH] - see latching algorithm.
We have to make an optimistic assumption that we get read latches and crabbing to verify that it is safe. If the leaf is not safe, then do the previous algorithm using write latches. In coding this is "optimism and pessimism" and I'm optimistically assuming that I'm not going to have to do a split. Most operations are doing are not going to split and merge.
The read latches prevent a split, the write latch prevents anyone from modifying them.
Search is the same as before for the better latching algorithm, and insert/delete is setting latches as if for search, get to leaf, set W latch on leaf. If leaf isn't safe, release the latches and restart the thread using the previous insert/delete protocol. But what if we want to move from one leaf node to another?
The original B+ tree does not have sibling pointers, but now it does. When we go horizontally, we don't release the latch the we hold until we get the latch that we want.
Now, let's say we have another thread with all keys greater than 1. We get the write latch on the entry that we want to delete. We can't have the read and write latch at the same time.
Remember, threads have NO idea what each other is doing,t here's no "global view" in a system that tells what other threads are doing. It's really unpredictable, we can wait, however thread 2 has no idea what thread 1 is doing. If we have no idea what we are doing, a solution is to "abort and kill ourselves".
If C wanted to do some modification, say the value thread gets read latch, then Key 1 starts, gets write latch on something, so things can come into other order. "terminating the process" adds additional overhead, but again, the simple thing might be the best thing.
Leafs do not support deadlock detection or avoidance, and the ONLY way we can deal with this problem is through the coding discipline. The leaf node sibling latch acquisition protocal must support a "no-wait" mode. It matters what latch the other thread is having, if one thread has a write latch, we can't get a read latch from the same thread. Otherwise, we have to interrupt a guy to steal the latch.
Merging will make you have to go back and take exclusive latches all the way down. If there are conflicting locks, then you "kill the process".
Last thing to discuss is an additional optimization for handling overflows. Every time a leaf node oveflows, we have to update the parent node, the leaf node bing split, and the new leaf node being created. In the Blink tree optimization, when a leaf node overflows, we delay updating its parent node, so I don't have to restart the traversal and do the pessimistic write-latches all the way down.
Instead we have a plan "Update C the next time".
We have to update C first in the write latch if C is the parent.
In conclusion, making a data structure thread-safe is notoriously difficult in practice. Because it's super hard, if you can do this people pay you a ton of money to do this. THere is a lot of concurrent data structure libraries (intel library, Facebook's library) off teh shell stuff is probably good at all but sometime you have to tailor towards the target operating environment of the data structure.
Threads must go in one direction in a deadlock/to avoid a deadlock. Ypu should kill yourself right away if you get a deadlock. All these techniques are reused all throughout computer science, not just B+ trees. Next class would execute queries.
Comments
Post a Comment