CS764

Intro storage-disaggregation log-once API allows multiple participants to read and update the same log file and ensures that only the first log append for a transaction can update this transaction’s state eliminates decision logging by the coordinator LogOnce(txn, type) It atomically checks if a log record already exists for txn, and if not assigns the value in type to the record, namely VOTE-YES, COMMIT, or ABORT. It returns the state of txn after performing the atomic operation, which is either type or the existing state, depending on whether the operation updated the state

Aria Non deterministic database 2PC Paxos/Raft Deterministic Concurrency Control Use a sequencing layer to determine total order & replace nondeterministic operations Dependency graph / ordered lock Require read/write set of the transaction Single thread locking Aria Pass through a seq layer to get TID Commit order by default But might get reordered Runs batch in execution phase and commit phase A transaction commits if it has no WAW-dependencies or RAW-dependencies on any earlier transact Aborted transaction goes to the next batch Re-ording A transaction commits if two conditions are met: (1) it has no WAW-dependencies on any earlier transaction, and (2) it does not have both WAR-dependencies and RAW dependencies on earlier transactions with smaller TID def of batch?...

Adaptive Radix Tree (Trie) Radix Tree The height depends on the length of the keys Inner node array of $2^{s}$ pointers use s bit chunk of the key to index into array s: span Adaptive Radix Tree Adaptively use different node sizes use span of 8 bits Inner node Node4, Node16 (Linear search) Node48, Node 256 (direct index) Optimization Path compression Lazy expansion Binary–Comparable Keys String: naturally sorted in radix tree How about int, float … (negative two-complement signed integers are lexicographically greater than positive integers)

Storage model fixed memory per process no sharing Able to lock/unlock a disk page Concurrent Issue Process A insert 9 Process B search 15 Process B goes to old y node => 404 not found B-Link-Tree two nodes, since they are joined by a link pointer, are functionally essentially the same as a single node until the proper pointer from their father can be added Add link pointer first when creating new node Search Normal search, if greater than current node max => follow link Insert (Splitting node) Splitting node a into a' and b' Delete Allow leaf nodes with less than k entries (Don’t even need to modify non-leaf nodes) Lock whole tree to reorganize if too many deletions

Occ issues Tracking “anti-dependencies” global transaction IDha Silo epoch-based group commit only know order across epoch boundaries return results at epoch boundaries Design Global Epochs A designated thread periodically advances global epoch number $E$ Each worker $w$ maintains a local epoch number TID |epoch|id distinguish same epoach transaction |lock bit|lastest-version bit|abset bit| (a) larger than the TID of any record read or written by the transaction (b) larger than the worker’s most recently chosen TID (c) in the current global epoch....