Slides

S1: Csci 8701 - Week 7

Administrative
- Mid-Sem. Exam. coming Tuesday
- Sample question available (closed book exam.)
Goals:
- Review of Concurrency Control
Recommended Readings:
- Lehman, Efficient Locking for Concurrent Operations on B-Trees
- Agrawal, Concurrency Control Performance Modeling

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

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)

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)

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);

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.

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;
}

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
- Update survey - ARIES: ARIES/KVL & ARIES/IM
- Don't require right-links
- adds more constraint on ordering of operations.
- consistency degrees, logging/recovery, savepoints.

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

S11: Extensions for R-trees & GiSTs