Day #142 - CMU Database Systems - 09 Index Concurrency Control

Concurrency Control

• Method to allow concurrent operation of the shared object 
• Ensures Logical and Physical Correctness

Physical Correctness
Latch Modes
Latch Crabbing
Leaf Scans
Delayed Parent Updates

Locks vs Latches
Locks

• Protects the index's logical contents
• Held for transaction duration
• Need to be able to rollback changes

Latches

• Protect the critical sections of index's internal data
• Held for operation duration
• Do not need to be able to rollback changes (Atomic operation)

Locks

• Separates user transactions
• Protects Database contents
• During Entire transaction
• Lock Modes are shared, exclusive, update and intent
• Deadlock by waits-for, timeout, aborts
• Kept in Lock Manager

Latches

• Separate Threads
• Protects in memory data structures
• During Critical sections
• Red / Write Modes
• Kept in the protected data structure
• Multiple threads allowed to read but only one thread to write

B+ Tree Concurrency Control

• Protect threads trying to modify node concurrently
• Latch Coupling / Latch Crabbing - Allow both threads to access / modify at the same time
• Latch is in FIFO order
• Instead of locking Root and creating contention point, Alternate option Optimistic algorithm
• Assumption leaf node will be safe
• Read / write latches compatibility decides how they manage without deadlocks
• Thread that kill itself if prolonged wait / deadlock / starving
• Retry is better than waiting without timeout / Spin for milli second then restart
• Making B+ Tree threadsafe

Highlevel techniques (Acquire latches in same order, Killing and restarting)

• Page Layout
• Data Structure
• STL Iterator
• Latch Grabbing

Happy Learning!!!