Lehman, Efficient Locking for Concurrent Operations on B-Trees
Agrawal, Concurrency Control Performance Modeling
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S2: ... Concurrent Operations on B-Trees
Problem Statement: Tree Locking Protocols
Given: B-tree; a set of operations (search, insert, delete)
Find: A locking protocol, a variant of B-tree
Objectives: Highly concurrent access to index
Constraints: Preserve correctness of B-tree
Comparison with generic Locking Protocols (e.g. 2PL)
Pages chosen by an opertion are not random
Ex. insert touching H pages (due to splits)
... needs to possibly lock the entire tree
... Reduces concurrent access in locking
... Has lots of rollback in optimistic CC
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S3: ... Concurrent Operations on B-Trees
Major Contributions
B-link tree - a variant of B+ tree
Tree locking protocol - no locking for reads
... latches (binary locks) for writes
Simpler than previous approaches
Definition and Proof of correctness
Proofs related to efficiency
Admits problems - e.g. livelock /starvation,
... Need for simulation to validate efficiency (TPS)
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S4: ... Concurrent Operations on B-Trees
Key Concepts : B-Link Trees
Take a B+ tree and add the following to each page:
... high keys (Sec. 3.1.2, pp. 225)
... right-links (threads at each level) (Sec. 3.3, pp. 227)
Ensure the following on algorithms for operations:
... search top-down, left-to-right
... insert bottom-up
Key Concepts: Tree locking protocol (pp. 224 end)
NO locking for search (i.e. read !!)
Binary Lock for writes (insert, delete, update)
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S5: B-Link Trees (Lehman/Yao)
Key Concepts: Modification to Search Algorithm
Use high-keys and right-links in scannode().
scannode(v,A): examine memory page A and find
... the appropriate pointer for value v.
... may return a right-link pointer or a child pointer
current = root;
A = get(current);
while (current is not a leaf) {
current = scannode1(v, A);
A = get(current);
}
while ((t = scannode(v,A)) == link pointer of A) {
current = t;
A = get(current);
}
if (v is in A)
return(success);
else return(failure);
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S6: B-Link Trees (Lehman/Yao)
Key Concepts: Insert Algorithm
Psuedocode in (Sec. 5, pp. 229-230)
Assume the key being inserted is not in tree.
A. Search for proper leaf node (Stack rightmost node per level)
B. At leaf level, may need to search right
... move_right() with lock coupling
... first lock right neighbor, then release lock on current.
C. insert & possibly split:
D. Worst case - 3 locks with the process
... Improvement later proposed by Sagiv, and by Lanin & Shasha
... Could unlock current after put(A, current)).
Delete
Remove from the leaf
Did not address immediate underflow management
Periodic reorganize offline.
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S7: Insert into B-Link Trees (Lehman/Yao)
initialize stack; /* Comment A. */
current = root;
A = get(current);
while (current is not a leaf) {
t = current;
current = scannode(v,A);
if (current not link pointer in A) push t;
A = get(current);
}
lock(current); /* Comment B */
A = get(current);
move_right();
Doinsertion:
if A is safe {
insert new key/ptr pair on A;
put(A, current);
unlock(current);
}
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S8: Insert into B-Link Trees (Lehman/Yao)
Key Concepts: Modification to Insert Algorithm
else { // gonna have to split
u = allocate(1 new page for B);
redistribute A over A and B;
y = max value on A now;
make high key of B equal old high key of A;
make right-link of B equal old right-link of A;
make high key of A equal y;
make right-link of A point to B;
put (B, u);
put (A, current);
oldnode = current;
new key/ptr pair = (y, u); // high key of new page, new page
current = pop(stack);
lock(current);
A = get(current);
move_right(); // at this point we may have 3 locks: oldnode,
// and two at the parent level while moving right
unlock(oldnode);
goto Doinsertion;
}
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S9: B-Link Trees (Lehman/Yao)
Validation Methodology
Definition and Proof of correctness
... no deadlock, consistent tree seen by all processes
... preserves critical properties of tree
Proofs related to efficiency: update locks < = 3 pages
... search: no wait for lock, but read few more pages
Admits problems - e.g. livelock /starvation,
... Need for simulation to validate efficiency (TPS)
Assumptions
Primary index B-tree
Search slowdowns from additional work is acceptable
Rewrite today
Use serializability as definition of correctness
... concurrent execution eqv. to a serial execution
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S10: B-link Tree
Proof Sketches - Deadlock-free
a total order on tree nodes (bottom-up, left-to-right)
... followed by locking protocol
Proof Sketch - Correctness of Tree Modifications:
Node splitting atomic at each level.
... put(B, u) before put(A, current) in insert,
At any time tree appears consistent (despite big nodes)
Proof Sketch - Correct Interaction:
Tricky to show that reader/writer and writer/writer pairs
don't step on each other.
Consider a reader reads node N, which is subsequently
... updated by a writer.
Reader will later detect relevant inserts by seeing
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)S11: Extensions for R-trees & GiSTs
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. ,,.(home)
The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.