Carnegie Mellon University
Database Systems
Index Concurrency Control
ADMINISTRIVIA
Project #2 out; due Sunday March 2nd @ 11
$\rightarrow$ Don't forget to do a GitHub "pull" before starting. $\rightarrow$ Recitation on Wednesday Feb. 19 4:00- 5
pm, GHC 5117.
Homework #3 (indices and filters) due Sunday Feb 23th @11
.
Mid- term Exam on Wednesday Feb 26th
$\rightarrow$ In- class; in this room. $\rightarrow$ Study guide is available online. What to bring to the exam?
- Your CMU ID (Mandatory)- A calculator is recommended (e.g., logarithms)- A single letter-size page of handwritten notes. You may use both sides.
UPCOMING DATABASE TALK
TUM (DB Seminar) Towards Sanity in Query Languages $\rightarrow$ Monday Feb 17th @ 4
ET $\rightarrow$
https://cmu.zoom.us/j/93441451665
OBSERVATION
We (mostly) assumed all the data structures that we have discussed so far are single- threaded.
A modern DBMS needs to allow multiple threads to safely access data structures to take advantage of additional CPU cores and hide disk I/O stalls.
OBSERVATION
We (mostly) assumed all the data structures that we have discussed so far are single- threaded.
A modern DBMS needs to allow multiple threads to safely access data structures to take advantage of additional CPU cores and hide disk I/O stalls.
They Don't Do This! VOLTDB KX Redis H- Store
CONCURRENCY CONTROL
A concurrency control protocol is the method that the DBMS uses to ensure "correct" results for concurrent operations on a shared object.
A protocol's correctness criteria can vary: $\rightarrow$ Logical Correctness: Can a thread see the data that it is supposed to see? $\rightarrow$ Physical Correctness: Is the internal representation of the object sound?
CONCURRENCY CONTROL
A concurrency control protocol is the method that the DBMS uses to ensure "correct" results for concurrent operations on a shared object.
A protocol's correctness criteria can vary: $\rightarrow$ Logical Correctness: Can a thread see the data that it is supposed to see?
$\rightarrow$ Physical Correctness: Is the internal representation of the object sound?
TODAY'S AGENDA
Latches Overview Hash Table Latching B+Tree Latching Leaf Node Scans Project #2 Announcement
LOCKS VS. LATCHES
Locks (Transactions)
$\rightarrow$ Protect the database's logical contents from other transactions. $\rightarrow$ Held for transaction's duration. $\rightarrow$ Need to be able to rollback changes.
Latches (Workers)
$\rightarrow$ Protect the critical sections of the DBMS's internal data structure from other workers (e.g., threads). $\rightarrow$ Held for operation duration. $\rightarrow$ Do not need to be able to rollback changes.
LOCKS VS. LATCHES
Locks
Latches
Separate... Transactions Protect... Database Contents During... Entire Transactions Modes... Shared, Exclusive, Update, Intention Deadlock Detection & Resolution ...by... Waits- for, Timeout, Aborts Kept in... Lock Manager
Workers (threads, processes) In- Memory Data Structures Critical Sections Read, Write
Avoidance Coding Discipline Protected Data Structure
LOCKS VS. LATCHES
Lecture #15
Locks
Latches
Separate... Transactions Protect... Database Contents During... Entire Transactions Modes... Shared, Exclusive, Update, Intention Deadlock Detection & Resolution ...by... Waits- for, Timeout, Aborts Kept in... Lock Manager
Workers (threads, processes) In- Memory Data Structures Critical Sections Read, Write
Avoidance Coding Discipline Protected Data Structure
LATCH MODES
Read Mode
$\rightarrow$ Multiple threads can read the same object at the same time. $\rightarrow$ A thread can acquire the read latch if another thread has it in read mode.
Write Mode
$\rightarrow$ Only one thread can access the object. $\rightarrow$ A thread cannot acquire a write latch if another thread has it in any mode.
Compatibility Matrix
Table (html):
LATCH IMPLEMENTATION GOALS
Small memory footprint.
Fast execution path when no contention.
Decentralized management of latches.
Avoid expensive system calls.
LATCH IN
pm > I'm usually on the other side of these primitives when I write code as a consumer of them,
but it's very interesting to read about the nuances related to their implementations:
Small memory
The whole post seems to be just wrong, and is measuring something completely different than what the author thinks and claims it is measuring. First off, spinlocks can only be used if you actually know you're not being scheduled while using them. But the blog post author seems to be claimed "lock not held" timing is complete garbage. It basically reads the time before releasing the lock, and then it reads it after acquiring the lock again, and claims that the time difference is the time when no lock was held. Which is just inane and pointless and completely wrong. That's pure garbage. What happens is that (a) since you're spinning, you're using CPU time (b) at a random time, the scheduler will schedule you out (c) that random time might ne just after you read the "current time", but before you actually released the spinlock. So now you still hold the lock, but you got scheduled away from the CPU, because you had used up your time slice. The "current time" you read is basically now stale, and has nothing to do with the (future) time when you are actually going to release the lock. Somebody else comes in and wants that "spinlock", and that somebody will now spin for a long while, since nobody is releasing it - it's still held by that other thread entirely that was just scheduled out. At some point, the scheduler says "ok, now you've used your time slice", and schedules the original thread, and now the lock is actually released. Then another thread comes in, gets the lock again, and then it looks at the time and says "oh, a long time passed without the lock being held at all". And notice how the above is the good schenario. If you have more threads than CPU's (maybe because of other processes unrelated to your own test load), maybe the next thread that gets shceduled isn't the one that is going to release the lock. No, that one already got its timeslice, so the next thread scheduled might be another thread that wants that lock that is still being held by the thread that isn't even running right now! So the code in question is pure garbage. You can't do spinlocks like that. Or rather, you very much can do them like that, and when you do that you are measuring random latencies and getting nonsensical values, because what you are measuring is "I have a lot of busywork, where all the processes are CPU- bound, and I'm measuring random points of how long the scheduler kept the process in place". And then you write a blog- post blamings others, not understanding that it's your incorrect code that is garbage, and is giving random garbage
Source: Filip Pizlo CCMU- DB 15- 445/645 (Spring 2025)
LATCH IMPLEMENTATIONS
Test- and- Set Spinlock Blocking OS Mutex Reader- Writer Locks
Advanced approaches: $\rightarrow$ Adaptive Spinlock (Apple ParkingLot) $\rightarrow$ Queue- based Spinlock (MCS Locks) $\rightarrow$ Optimistic Lock Coupling (The Germans)
LATCH IM
Locking in WebKit
May 6, 2016 by Filip Pizio @filpizlo
Test- and- Set Spinlo Blocking OS Mutex Reader- Writer Loc
Back in August 2015 we replaced all spinlocks and OS- provided mutexes in WebKit with the new WTF::Lock (WTF stands for Web Template Framework). We also replaced all OS- provided condition variables with WTF::Condition. These new primitives have some cool properties:
Advanced approach $\rightarrow$ Adaptive Spinlock $\rightarrow$ Queue- based Spinlock $\rightarrow$ Optimistic Lock Co
-
WTF::Lock and WTF::Condition only require one byte of storage each. WTF::Lock only needs two bits in that byte. The small size encourages using huge numbers of very fine-grained locks. OS mutexes often require 64 bytes or more. The small size of WTF::Lock means that there's rarely an excuse for not having one, or even multiple, fine-grained locks in any object that has things that need to be synchronized.
-
WTF::Lock is super fast in the case that matters most, uncontended lock acquisition. Parallel algorithms tend to avoid contention by having many fine-grained locks. This means that a mature parallel algorithm will have many uncontended lock acquisitions - that is, calls to lock() when the lock is not held, and calls to unlock() when nobody is waiting in line. Similarly, WTF::Condition optimizes for the common case of calling notify when no threads are waiting.
-
WTF::Lock is fast under microcontention. A microcontended lock is one that is contended and the critical section is short. This means that shortly after any failing lock attempt, the lock will become available again since no thread will hold the lock for long. This is the most common kind of contention in parallel code, since it's common to go to great pains to do very little work while holding a lock.
-
WTF::Lock doesn't waste CPU cycles when a lock is held for a long time. WTF::Lock is adaptive: it changes its strategy for how to wait for the lock to become available based on how long it has been trying. If the lock doesn't become available promptly, WTF::Lock will suspend the calling thread until the lock becomes available.
LATCH IMPLEMENTATIONS
Approach #1: Test- and- Set Spin Latch (TAS) $\rightarrow$ Very efficient (single instruction to latch/unlatch) $\rightarrow$ Non- scalable, not cache friendly, not OS friendly. $\rightarrow$ Example: std::atomic
LATCH IMPLEMENTATIONS
Approach #1: Test- and- Set Spin Latch (TAS)
$\longrightarrow$ Very efficient (single instruction to latch/unlatch) $\longrightarrow$ Non- scalable, not cache friendly, not OS friendly. $\longrightarrow$ Example: std::atomic
std::atomic
std::atomic_flag latch;
while (latch.test_and_set(...)) { // Retry? Yield? Abort?}
LATCH IMPLEMENTATIONS
Approach #1: Test- and- Set Spin Latch (TAS) $\rightarrow$ Very efficient (single instruction to latch/unlatch) $\rightarrow$ Non- scalable, not cache friendly, not OS friendly. $\rightarrow$ Example: std::atomic
std::atomic
std::atomic_flag latch; while (latch.test_and_set(...)) { // Retry? Yield? Abort? }
LATCH IMPLEMENTATIONS
Approach #1: Test-and-Set Spin Latch (TAS)
$\longrightarrow$ Very efficient (single instruction to latch/unlatch) $\longrightarrow$ Non- scalable, not cache friendly, not OS friendly. $\longrightarrow$ Example: std::atomic
std::atomic
std::atomic_flag latch; while (latch.test_and_set(...)) { // Retry? Yield? Abort? }
COMPARE-AND-SWAP
Atomic instruction that compares contents of a memory location M to a given value V $\rightarrow$ If values are equal, installs new given value V’ in M $\rightarrow$ Otherwise, operation fails See C++11 Atomics
__sync_bool_compare_and_swap(&M, 20, 30)
COMPARE-AND-SWAP
Atomic instruction that compares contents of a memory location M to a given value V $\rightarrow$ If values are equal, installs new given value V' in M $\rightarrow$ Otherwise, operation fails See C++11 Atomics
COMPARE-AND-SWAP
Atomic instruction that compares contents of a memory location M to a given value V $\rightarrow$ If values are equal, installs new given value V’ in M $\rightarrow$ Otherwise, operation fails See C++11 Atomics
COMPARE-AND-SWAP
Atomic instruction that compares contents of a memory location M to a given value V $\rightarrow$ If values are equal, installs new given value V’ in M $\rightarrow$ Otherwise, operation fails See C++11 Atomics
COMPARE-AND-SWAP
Atomic instruction that compares contents of a memory location M to a given value V $\rightarrow$ If values are equal, installs new given value V’ in M $\rightarrow$ Otherwise, operation failsSee C++11 Atomics
LATCH IMPLEMENTATIONS
Approach #2: Blocking OS Mutex
$\longrightarrow$ Simple to use $\longrightarrow$ Non- scalable (about 25ns per lock/unlock invocation) $\longrightarrow$ Example: std::mutex
LATCH IMPLEMENTATIONS
Approach #2: Blocking OS Mutex
$\longrightarrow$ Simple to use $\longrightarrow$ Non- scalable (about 25ns per lock/unlock invocation) $\longrightarrow$ Example: std::mutex
std::mutex m;
m.lock();
// Do something special... m.unlock();
LATCH IMPLEMENTATIONS
Approach #2: Blocking OS Mutex
$\longrightarrow$ Simple to use $\longrightarrow$ Non- scalable (about 25ns per lock/unlock invocation) $\longrightarrow$ Example: std::mutex - > pthread_mutex_t
std::mutex m;
m.lock();
// Do something special... m.unlock();
LATCH IMPLEMENTATIONS
Approach #2: Blocking OS Mutex
$\longrightarrow$ Simple to use $\longrightarrow$ Non- scalable (about 25ns per lock/unlock invocation) $\longrightarrow$ Example: std::mutex - > pthread_mutex_t - > futex
std::mutex m;
m.lock();
// Do something special... m.unlock();
LATCH IMPLEMENTATIONS
Approach #2: Blocking OS Mutex
$\longrightarrow$ Simple to use $\longrightarrow$ Non- scalable (about 25ns per lock/unlock invocation) $\longrightarrow$ Example: std::mutex - > pthread_mutex_t - > futex
std::mutex m;
m.lock();
// Do something special... m.unlock();
OS Latch Userspace Latch
LATCH IMPLEMENTATIONS
Approach #2: Blocking OS Mutex
$\longrightarrow$ Simple to use $\longrightarrow$ Non- scalable (about 25ns per lock/unlock invocation) $\longrightarrow$ Example: std::mutex - > pthread_mutex_t - > futex
std::mutex m;
m.lock();
// Do something special... m.unlock();
LATCH IMPLEMENTATIONS
Approach #2: Blocking OS Mutex
$\longrightarrow$ Simple to use $\longrightarrow$ Non- scalable (about 25ns per lock/unlock invocation) $\longrightarrow$ Example: std::mutex - > pthread_mutex_t - > futex
std::mutex m;
m.lock();
// Do something special... m.unlock();
LATCH IMPLEMENTATIONS
Approach #2: Blocking OS Mutex
$\longrightarrow$ Simple to use $\longrightarrow$ Non- scalable (about 25ns per lock/unlock invocation) $\longrightarrow$ Example: std::mutex - > pthread_mutex_t - > futex
std::mutex m;
m.lock();
// Do something special...
m.unlock();
LATCH IMPLEMENTATIONS
Approach #2: Blocking OS Mutex
$\longrightarrow$ Simple to use $\longrightarrow$ Non- scalable (about 25ns per lock/unlock invocation) $\longrightarrow$ Example: std::mutex - > pthread_mutex_t - > futex
std::mutex m;
m.lock();
// Do something special... m.unlock();
LATCH IMPLEMENTATIONS
Approach #3: Reader-Writer Latches
$\longrightarrow$ Allows for concurrent readers. Must manage read/write queues to avoid starvation. $\longrightarrow$ Can be implemented on top of spinlocks. $\longrightarrow$ Example: std::shared_mutex
LATCH IMPLEMENTATIONS
Approach #3: Reader-Writer Latches
$\longrightarrow$ Allows for concurrent readers. Must manage read/write queues to avoid starvation. $\longrightarrow$ Can be implemented on top of spinlocks. $\longrightarrow$ Example: std::shared_mutex $\longrightarrow$ pthread_rwlock_t
LATCH IMPLEMENTATIONS
Approach #3: Reader-Writer Latches
$\longrightarrow$ Allows for concurrent readers. Must manage read/write queues to avoid starvation. $\longrightarrow$ Can be implemented on top of spinlocks. $\longrightarrow$ Example: std::shared_mutex $\longrightarrow$ pthread_rwlock_t
LATCH IMPLEMENTATIONS
Approach #3: Reader-Writer Latches
$\longrightarrow$ Allows for concurrent readers. Must manage read/write queues to avoid starvation. $\longrightarrow$ Can be implemented on top of spinlocks. $\longrightarrow$ Example: std::shared_mutex $\longrightarrow$ pthread_rwlock_t
Latch
LATCH IMPLEMENTATIONS
Approach #3: Reader-Writer Latches
$\longrightarrow$ Allows for concurrent readers. Must manage read/write queues to avoid starvation. $\longrightarrow$ Can be implemented on top of spinlocks. $\longrightarrow$ Example: std::shared_mutex $\longrightarrow$ pthread_rwlock_t
Latch
LATCH IMPLEMENTATIONS
Approach #3: Reader-Writer Latches
$\longrightarrow$ Allows for concurrent readers. Must manage read/write queues to avoid starvation. $\longrightarrow$ Can be implemented on top of spinlocks. $\longrightarrow$ Example: std::shared_mutex $\longrightarrow$ pthread_rwlock_t
LATCH IMPLEMENTATIONS
Approach #3: Reader-Writer Latches
$\longrightarrow$ Allows for concurrent readers. Must manage read/write queues to avoid starvation. $\longrightarrow$ Can be implemented on top of spinlocks. $\longrightarrow$ Example: std::shared_mutex $\longrightarrow$ pthread_rwlock_t
LATCH IMPLEMENTATIONS
Approach #3: Reader-Writer Latches
$\longrightarrow$ Allows for concurrent readers. Must manage read/write queues to avoid starvation. $\longrightarrow$ Can be implemented on top of spinlocks. $\longrightarrow$ Example: std::shared_mutex $\longrightarrow$ pthread_rwlock_t
LATCH IMPLEMENTATIONS
Approach #3: Reader-Writer Latches
$\longrightarrow$ Allows for concurrent readers. Must manage read/write queues to avoid starvation. $\longrightarrow$ Can be implemented on top of spinlocks. $\longrightarrow$ Example: std::shared_mutex $\longrightarrow$ pthread_rwlock_t
LATCH IMPLEMENTATIONS
Approach #3: Reader-Writer Latches
$\longrightarrow$ Allows for concurrent readers. Must manage read/write queues to avoid starvation. $\longrightarrow$ Can be implemented on top of spinlocks. $\longrightarrow$ Example: std::shared_mutex $\longrightarrow$ pthread_rwlock_t
LATCH IMPLEMENTATIONS
Approach #3: Reader-Writer Latches
$\longrightarrow$ Allows for concurrent readers. Must manage read/write queues to avoid starvation. $\longrightarrow$ Can be implemented on top of spinlocks. $\longrightarrow$ Example: std::shared_mutex $\longrightarrow$ pthread_rwlock_t
LATCH IMPLEMENTATIONS
Approach #3: Reader-Writer Latches
$\longrightarrow$ Allows for concurrent readers. Must manage read/write queues to avoid starvation. $\longrightarrow$ Can be implemented on top of spinlocks. $\longrightarrow$ Example: std::shared_mutex $\longrightarrow$ pthread_rwlock_t
LATCH IMPLEMENTATIONS
Approach #3: Reader-Writer Latches
$\longrightarrow$ Allows for concurrent readers. Must manage read/write queues to avoid starvation. $\longrightarrow$ Can be implemented on top of spinlocks. $\longrightarrow$ Example: std::shared_mutex $\longrightarrow$ pthread_rwlock_t
HASH TABLE LATCHING
Easy to support concurrent access due to the limited ways threads access the data structure. $\longrightarrow$ All threads move in the same direction and only access a single page/slot at a time. $\longrightarrow$ Deadlocks are not possible.
To resize the table, take a global write latch on the entire table (e.g., in the header page).
HASH TABLE LATCHING
Approach #1: Page/Block Latches
$\rightarrow$ Each page/block has its own reader- writer latch that protects its entire contents. $\rightarrow$ Threads acquire either a read or write latch before they access a page/block.
Approach #2: Slot Latches
$\rightarrow$ Each slot has its own latch. $\rightarrow$ Can use a single- mode latch to reduce meta- data and computational overhead.
HASH TABLE: PAGE/BLOCK LATCHES
HASH TABLE: PAGE/BLOCK LATCHES
HASH TABLE: PAGE/BLOCK LATCHES
T: Find D hash(D)
HASH TABLE: PAGE/BLOCK LATCHES
T: Find D hash(D)
T: Insert E hash(E)
HASH TABLE: PAGE/BLOCK LATCHES
T: Find D hash(D)
HASH TABLE: PAGE/BLOCK LATCHES
T: Find D hash(D)
HASH TABLE: PAGE/BLOCK LATCHES
T: Find D hash(D)
HASH TABLE: PAGE/BLOCK LATCHES
HASH TABLE: PAGE/BLOCK LATCHES
HASH TABLE: PAGE/BLOCK LATCHES
HASH TABLE: PAGE/BLOCK LATCHES
T: Find D hash(D)
HASH TABLE: PAGE/BLOCK LATCHES
T: Find D hash(D)
HASH TABLE: PAGE/BLOCK LATCHES
T: Find D hash(D)
T: Insert E hash(E)
HASH TABLE: PAGE/BLOCK LATCHES
T: Find D hash(D)
T: Insert E hash(E)
HASH TABLE: PAGE/BLOCK LATCHES
T: Find D hash(D)
T: Insert E hash(E)
HASH TABLE: PAGE/BLOCK LATCHES
T: Find D hash(D)
T: Insert E hash(E)
HASH TABLE: PAGE/BLOCK LATCHES
T: Find D hash(D)
T: Insert E hash(E)
HASH TABLE: PAGE/BLOCK LATCHES
T: Find D hash(D)
T: Insert E hash(E)
HASH TABLE: SLOT LATCHES
T2: Insert E hash(E)
HASH TABLE: SLOT LATCHES
T2: Insert E hash(E)
HASH TABLE: SLOT LATCHES
T: Find D hash(D)
T: Insert E hash(E)
HASH TABLE: SLOT LATCHES
T: Find D hash(D)
HASH TABLE: SLOT LATCHES
T: Find D hash(D)
T: Insert E hash(E)
HASH TABLE: SLOT LATCHES
T: Find D hash(D)
T: Insert E hash(E)
HASH TABLE: SLOT LATCHES
T2: Insert E hash(E)
HASH TABLE: SLOT LATCHES
T: Find D hash(D)
T: Insert E hash(E)
HASH TABLE: SLOT LATCHES
T: Find D hash(D)
T: Insert E hash(E)
HASH TABLE: SLOT LATCHES
T: Find D hash(D)
T: Insert E hash(E)
HASH TABLE: SLOT LATCHES
T: Find D hash(D)
T: Insert E hash(E)
HASH TABLE: SLOT LATCHES
T: Find D hash(D)
T: Insert E hash(E)
HASH TABLE: SLOT LATCHES
T: Find D hash(D)
T: Insert E hash(E)
HASH TABLE: SLOT LATCHES
T: Find D hash(D)
T: Insert E hash(E)
B+TREE CONCURRENCY CONTROL
We want to allow multiple threads to read and update a B+Tree at the same time.
We need to protect against two types of problems: $\rightarrow$ Threads trying to modify the contents of a node at the same time. $\rightarrow$ One thread traversing the tree while another thread splits/merges nodes.
B+TREE MULTI-THREADED EXAMPLE
B+TREE MULTI-THREADED EXAMPLE
B+TREE MULTI-THREADED EXAMPLE
B+TREE MULTI-THREADED EXAMPLE
B+TREE MULTI-THREADED EXAMPLE
B+TREE MULTI-THREADED EXAMPLE
B+TREE MULTI-THREADED EXAMPLE
B+TREE MULTI-THREADED EXAMPLE
B+TREE MULTI-THREADED EXAMPLE
B+TREE MULTI-THREADED EXAMPLE
B+TREE MULTI-THREADED EXAMPLE
B+TREE MULTI-THREADED EXAMPLE
B+TREE MULTI-THREADED EXAMPLE
B+TREE MULTI-THREADED EXAMPLE
B+TREE MULTI-THREADED EXAMPLE
LATCH CRABBING/COUPLING
Protocol to allow multiple threads to access/modify B+Tree at the same time.
$\longrightarrow$ Get latch for parent $\longrightarrow$ Get latch for child $\longrightarrow$ Release latch for parent if "safe"
A safe node is one that will not split or merge when updated. $\longrightarrow$ Not full (on insertion) $\longrightarrow$ More than half- full (on deletion)
LATCH CRABBING/COUPLING
Find: Start at root and traverse down the tree:
$\rightarrow$ Acquire R latch on child, $\rightarrow$ Then unlatch parent. $\rightarrow$ Repeat until we reach the leaf node.
Insert/Delete: Start at root and go down, obtaining W latches as needed. Once child is latched, check if it is safe:
$\rightarrow$ If child is safe, release all latches on ancestors. $\rightarrow$ Optimization: When at an inner node that is "safe," release all latches on ancestors.
EXAMPLE #1 - FIND 38
EXAMPLE #1 - FIND 38
EXAMPLE #1 - FIND 38
EXAMPLE #1 - FIND 38
EXAMPLE #1 - FIND 38
EXAMPLE #1 - FIND 38
EXAMPLE #1 - FIND 38
EXAMPLE #1 - FIND 38
EXAMPLE #1 - FIND 38
EXAMPLE #2 - DELETE 38
EXAMPLE #2 - DELETE 38
EXAMPLE #2 - DELETE 38
EXAMPLE #2 - DELETE 38
EXAMPLE #2 - DELETE 38
EXAMPLE #2 - DELETE 38
EXAMPLE #2 - DELETE 38
EXAMPLE #2 - DELETE 38
EXAMPLE #2 - DELETE 38
EXAMPLE #2 - DELETE 38
EXAMPLE #2 - DELETE 38
EXAMPLE #3 – INSERT 45
EXAMPLE #3 – INSERT 45
EXAMPLE #3 – INSERT 45
EXAMPLE #3 – INSERT 45
EXAMPLE #3 – INSERT 45
EXAMPLE #3 – INSERT 45
EXAMPLE #3 – INSERT 45
EXAMPLE #3 – INSERT 45
EXAMPLE #4 – INSERT 25
EXAMPLE #4 – INSERT 25
EXAMPLE #4 – INSERT 25
EXAMPLE #4 – INSERT 25
EXAMPLE #4 – INSERT 25
EXAMPLE #4 – INSERT 25
EXAMPLE #4 – INSERT 25
EXAMPLE #4 – INSERT 25
EXAMPLE #4 – INSERT 25
EXAMPLE #4 – INSERT 25
EXAMPLE #4 – INSERT 25
OBSERVATION
What was the first step that all the update examples did on the B+Tree?
OBSERVATION
What was the first step that all the update examples did on the B+Tree?
Taking a write latch on the root every time becomes a bottleneck with higher concurrency.
BETTER LATCHING ALGORITHM
Most modifications to a B+Tree will not require a split or merge.
Instead of assuming there will be a split/merge, optimistically traverse the tree using read latches.
If a worker guesses wrong, repeat traversal with pessimistic algorithm.
Acta Informatica 9, 1 - 21 (1977)
Concurrency of Operations on B-Trees
R. Bayer* and
M. Schkolch IBM Research Laboratory, San Francisco, CA 95193, USA
Summary. Concurrent operations on B- trees pose the problem of insuring that each operation can be carried out without interfering with other operations being performed simultaneously by other users. This problem can become critical if these structures are being used to support access paths like indexes, to data base structures. In this case, serializing access to one of these indexes can create an unacceptable bottleneck for the entire system. Thus, there is a need for locking protocols that can assure integrity for each access while at the same time providing a maximum possible degree of concurrency. Another feature required from these protocols is that they be deadlock free, since the cost to resolve a deadlock may be high.
Recently, there has been some questioning on whether B- tree structures can support concurrent operations in this paper, we examine the problem of concurrent access to B- trees. The present paper defines the solution which can be tuned to specific requirements. An analysis is presented which allows the selection of parameters so as to satisfy these requirements.
The solution presented here uses simple locking protocols. Thus, we conclude that B- trees can be used advantageously in a multi- user environment.
1. Introduction
In this paper, we examine the problem of concurrent access to indexes which are maintained as B- trees. This type of organization was introduced by Bayer and McCreight [2] and some variants of it appear in Knuth [10] and Wedekind [13]. Performance studies of it were restricted to the single user environment. Recently, these structures have been examined for possible use in a multi- user (concurrent) environment. Some initial studies have been made about the feasibility of their use in this type of situation [1, 6], and [11].
An accessing scheme which achieves a high degree of concurrency in using the index will be preserved. The schema allows dynamic tuning to adapt its performance to the profile of the current set of users. Another property of the
BETTER LATCHING ALGORITHM
Search: Same as before.
Insert/Delete:
$\rightarrow$ Set latches as if for search, get to leaf, and set W latch on leaf. $\rightarrow$ If leaf is not safe, release all latches, and restart thread using previous insert/delete protocol with write latches.
This approach optimistically assumes that only leaf node will be modified; if not, R latches set on the first pass to leaf are wasteful.
EXAMPLE #2 - DELETE 38
EXAMPLE #2 - DELETE 38
EXAMPLE #2 - DELETE 38
EXAMPLE #2 - DELETE 38
EXAMPLE #2 - DELETE 38
EXAMPLE #2 - DELETE 38
EXAMPLE #2 - DELETE 38
EXAMPLE #2 - DELETE 38
EXAMPLE #2 - DELETE 38
EXAMPLE #4 – INSERT 25
EXAMPLE #4 – INSERT 25
OBSERVATION
The threads in all the examples so far have acquired latches in a "top- down" manner. $\rightarrow$ A thread can only acquire a latch from a node that is below its current node. $\rightarrow$ If the desired latch is unavailable, the thread must wait until it becomes available.
But what if threads want to move from one leaf node to another leaf node?
LEAF NODE SCAN EXAMPLE #1
LEAF NODE SCAN EXAMPLE #1
T1: Find Keys < 4
LEAF NODE SCAN EXAMPLE #1
T1: Find Keys < 4
LEAF NODE SCAN EXAMPLE #1
T1: Find Keys < 4
LEAF NODE SCAN EXAMPLE #1
T1: Find Keys < 4
LEAF NODE SCAN EXAMPLE #1
T1: Find Keys < 4
LEAF NODE SCAN EXAMPLE #1
T1: Find Keys < 4
LEAF NODE SCAN EXAMPLE #2
T: Find Keys < 4 T2: Find Keys > 1
LEAF NODE SCAN EXAMPLE #2
T: Find Keys < 4 T2: Find Keys > 1
LEAF NODE SCAN EXAMPLE #2
T: Find Keys < 4 T2: Find Keys > 1
LEAF NODE SCAN EXAMPLE #2
T: Find Keys < 4 T2: Find Keys > 1
LEAF NODE SCAN EXAMPLE #2
T: Find Keys < 4 T2: Find Keys > 1
LEAF NODE SCAN EXAMPLE #2
T: Find Keys < 4 T2: Find Keys > 1
LEAF NODE SCAN EXAMPLE #2
LEAF NODE SCAN EXAMPLE #2
LEAF NODE SCAN EXAMPLE #2
LEAF NODE SCAN EXAMPLE #3
T: Delete 4 T2: Find Keys > 1
LEAF NODE SCAN EXAMPLE #3
T: Delete 4 T2: Find Keys > 1
LEAF NODE SCAN EXAMPLE #3
T: Delete 4 T2: Find Keys > 1
LEAF NODE SCAN EXAMPLE #3
T: Delete 4 T2: Find Keys > 1
LEAF NODE SCAN EXAMPLE #3
LEAF NODE SCAN EXAMPLE #3
LEAF NODE SCAN EXAMPLE #3
LEAF NODE SCAN EXAMPLE #3
LEAF NODE SCAN EXAMPLE #3
LEAF NODE SCAN EXAMPLE #3
LEAF NODE SCAN EXAMPLE #3
LEAF NODE SCANS
Latches do not support deadlock detection or avoidance. The only way we can deal with this problem is through coding discipline.
The leaf node sibling latch acquisition protocol must support a "no- wait" mode.
The DBMS's data structures must cope with failed latch acquisitions. $\rightarrow$ Usually transparent to end- user / application.
CONCLUSION
Making a data structure thread- safe is notoriously difficult in practice.
We focused on B+Trees, but the same high- level techniques are applicable to other data structures.
NEXT CLASS
We are finally going to discuss how to execute some queries...
PROJECT #2
You will build a thread- safe B+ tree backed by your buffer pool manager.
$\longrightarrow$ Page Layout $\longrightarrow$ Insert/Delete/Find Operations $\longrightarrow$ Iterator $\longrightarrow$ Latch Crabbing
We define the API for you. You need to provide the method implementations.
WARNING: This is more difficult than Project #1. Start immediately!
TASKS
Task #1: Page Layouts
$\rightarrow$ How each node will store its key/values in a page. $\rightarrow$ You only need to support unique keys.
Task #2: Operations
$\rightarrow$ Support point queries (single key). $\rightarrow$ Support inserts with node splitting. $\rightarrow$ Support removal of keys with sibling stealing + merging. $\rightarrow$ Does not need to be thread- safe.
TASKS
Task #3: Index Iterator
$\rightarrow$ Create a STL iterator for range scans on leaf nodes. $\rightarrow$ You only need to support ascending scans.
Task #4: Concurrent Index
$\rightarrow$ Introduce latch crabbing/coupling protocol to support safe concurrent operations. $\rightarrow$ Make sure you have splits / merges working correctly before proceeding with this task.
DEVELOPMENT HINTS
Follow the textbook semantics and algorithms.
Set the page size to be small (e.g., 512B) when you first start so that you can see more splits/merges.
Make sure that you protect the internal B+ Tree root_page_id member.
EXTRA CREDIT
Gradescope Leaderboard runs your code with a specialized in- memory version of BusTub.
The top 20 fastest implementations in the class will receive extra credit for this assignment.
→ #1: 50% bonus points → #2- 10: 25% bonus points → #11- 20: 10% bonus points
You must pass all the test cases to qualify!
PLAGIARISM WARNING
The homework and projects must be your own original work. They are not group assignments. You may not copy source code from other people or the web.
Plagiarism is not tolerated. You will get lit up. $\rightarrow$ Please ask me if you are unsure.
See CMU's Policy on Academic Integrity for additional information.