This is the 7th day of my participation in the August Text Challenge.More challenges in August

The data structures discussed above are all in single-threaded situations. But in the actual scene, concurrent and multi-threaded operation is certain to exist, so we must ensure that DBMS in the case of multi-threaded operation can still access data safely, as far as possible to use now more and more CPU core, reduce disk IO.

Concurrency control ensures correct access to shared resources during concurrent operations.

  • Logical: The thread can read the data it should be allowed to read
  • Physically correct: Ensure that there are no cluttered Pointers in the data structure causing threads to access invalid memory addresses while looking for data

1.Latch

The difference between lock and latch has already been mentioned.

  • Lock is a transaction-level concept that lasts for the entire transaction cycle, locking specific data in the data table. For example, read/write locks (mutexes, shared locks); Lock Manager does the maintenance;
  • Latch is a thread-level concept that manages the concurrency security of in-memory data structures. Including read and write two modes, similar to the reader problem, read is compatible, read and write, write and write is mutually exclusive.

2.Implementation

blocking OS MUTEX

Use an operating system mutex, such as STD ::mutex, and then call lock and unlock methods;

Each lock/unlock call takes about 25ns, so it can’t scale.

TAS (Test and Set spin latch)

The spin lock. Busy waiting. Spin, as the name suggests, is always spinning in place. Keep waiting. Mutex. Processes that do not apply for resources will sleep and wait.

High efficiency; Not extensible, not cache friendly.

For example, STD: : atomic

reader-writer latch

Allow concurrent reads;

R/W queues need to be managed to avoid starvation;

This can be done on spin locks.

3.Hash table latch

Lock the hash table. There are whole bucket granularity (locking one bucket at a time) and slot granularity (locking one cell at a time).

When resize the entire table, place a global latch on the entire table.

  • Page latches
  • Slot latches

Page latch

Each page has its own read/write latch to protect its entire page; A thread requests a read or write latch before accessing a page.

For example, if find (key0) hits PAGe1, the latch for Page1 is requested. If another thread is expected to insert into PAGe1 at this time, it needs to wait for page1’s read LATCH to be released before applying for page1’s write LATCH. If a conflict occurs and key0 is not found in page1 and you need to look back linearly to Page2, you can safely release the read latch for Page1.

Slot latch

Each slot has its own latch.

For example, if find (key0) hits PAGe1, the slot in page1 is iterated, and only the read latch of the current slot is applied each time a slot is viewed. When jumping to the next slot, apply for the next latch and release the previous latch. If another thread is writing to another slot in page1 at this point, it is obviously unaffected.

4. Concurrency control for B + Tree

Expect to allow multiple threads to read and update b+ trees simultaneously. In this way, two aspects of security issues need to be considered:

  • What if multiple threads modify the contents of a Node at the same time?
  • What if a thread traverses a tree while another thread splits or merges?

Latch crabbing/coupling

Basic idea:

  • Obtain the latch of the parent of the target node

  • Obtain the latch of the target node’s child

  • If the parent is a safe node, the latch of the parent can be released

    • Safe node: a node that is not later split or merged (in insert operations, a non-full node; In the delete operation, is a non-half-full node. See the B + tree for the rebalance operation.

Find operation: start from root, repeat:

  • Gets the Read Latch for the child node of the current node
  • Unlatch parent

Insert /delete operation: Start the search from root and obtain the write latch for each node on the path while finding the target node. When a node is latched, check that it is safe to release latches on all ancestor nodes.

For example, in the following example, write latch is added for node A and node B in sequence during the search for node D where node 38 resides. At D, we confirm that it is safe (does not merge C), so we can release all of D’s ancestors (A, B). Then go to 38, lock node H and delete it.

There are several examples of this on the original Slide that you can view directly.

Better latching alg

Note that the first step in all update operations is to add a write latch to the root node. This means that all other UPDATE operations are blocked before being released. So this is going to be a bottleneck.

The essence of the bottleneck is that write latches are mutually exclusive.

Can we change it to read latch?

In the previous approach, after writing Latch confirms that a node is secure, it releases all ancestors of that node (including root, of course) until the target leaf node location is found. We can assume that the target leaf node is secure and then access the target leaf node in the same way as the previous lookup operation (with read latch in sequence). If the node is truly secure, there is no problem; Otherwise, execute the latch again.

That is:

  • Search: same as before.
  • Insert /delete: perform the search operation first; If the Leaf node is secure, only the Writh latch is added to the node.

Leaf node scan

The process mentioned above is a top-down LATCH application. Sometimes, when the predicate is looking for a range of data (for example, key < 10), you will need to do a peer scan at the level of the leaf node after finding the leaf node key=10 (the leaf nodes of the B + tree have Pointers to each other). At this point, the latch of the next node is obtained first, and the latch of the current node is released.

The problem is that if the next node has already been latched by another thread, the current thread cannot apply for a Read latch and does not know when the other thread will release the latch.

Latch has no mechanism for deadlock detection or avoidance. Deadlocks can only be avoided at the code level.

  • A solution is required when a sibling latch is unavailable
  • A no-wait mode needs to be supported

Delayed parent updates

When a leaf node overflows, at least three nodes need to be updated:

  • Current node split
  • Add a node
  • Father node

The optimal solution is to split the current node and the new node when an insert operation causes overflow, and then record what the parent node needs to change, but leave it unchanged (for example, in a log). Wait until the next time a thread holds a write Latch on the parent node.

5. To summarize

This section covers some issues related to concurrency control.

The first is the two types of concurrent locking, lock and latch. Lock refers to various locks that are added to a table while the database performs transactions, etc. Latch refers to a direct lock on hardware resources (such as a node in a B + tree, a slot in a hash table, etc.).

Then we’ll look at how to implement latch. Basically, you can borrow some operating system logic, such as direct use of mutex mutex, use spin locks, and since database access is mostly read and write operations, you can use read and write lock logic for some optimization.

In application scenarios, the hash table can lock the entire page or a specific slot. Access to each node in a B + tree is also classified according to read and write locks to improve efficiency. Because write locks are mutually exclusive, and the B + tree is a tree structure where access starts from the same root node, this can easily cause bottlenecks. Therefore, an improved solution is to add read locks to update operations (INSERT and DELETE) first, and then modify them accordingly.

We are finally going to discuss how to execute some queries.