Concurrency ControlCS262, Fall 2011.Joe HellersteinI. Concurrency & controlling order.Order in a traditional programming abstraction.Why is concurrency hard?Why does order matter? What orders matter? These are deep questions.Step back: ignore shared state, side-channels, etc. Assume no sharing, explicit communication,II. Inter-Agent Communication: Rendezvous/JoinThe Ancient Communication Scenario: 1 sender, 1 receiver.1. SpatioTemporal Rendezvous: Timed Smoke Signals on 2 mountaintops. Agent 1 has instructions togenerate a puff at certain time (and place). Agent 2 has instructions to watch at same time (and place).2. Receiver Persist: Smoke Signal and Watchtower. Agent 2 waits in watchtower for smoke-signal in theagreed-upon place. Agent 1 puffs at will. (What if too early?)3. Sender Persist: WatchFires. Agent 1 can light a watchfire. Agent 2 checks for the watchfire whenconvenient. (What if too early?)4. Both Persist: Watchfire and Watchtower. Both persist.Upshot: (1) one-sided persistence allows asynchrony on the other side. (2) BUT persistent party must span thetime of the transient party. (3) Without any temporal coordination, persistence of both sides is the way toguarantee rendezvous: second arrival necessarily overlaps first.This is very much like a choice of join algorithm in a database engine!Next Question: Multiple communications. Can we guarantee order? With temporal rendezvous, the agentscoordinate (“share a clock”). With receiver persist, receiver can observe/maintain sender order. Sender persistmuch more common, but doesn’t (organically) preserve order!Beware: In most computing settings, this reasoning is flipped. Storage is a given, and ends up being animplicit comm channel. Must control operations on it across agents.III. On State and PersistenceWhat is state?all values of memory, registers, stack, PC, etc.What is persistent state?persistent state: state that is communicated across time. E.g. across PC settings. Write is a Send into thefuture, Read is Receive.how does DRAM persist state? sender-persist! And recall: Sender-Persist doesn’t guarantee order!!(aside: how does OS do disk persistence?)IV. How to control communication?Prevention: Change the space or the time of rendezvous!writer uses private space (shadow copies, copy-on-write, multiversion, functionalprogramming, etc.)and/or a protocol arranges appropriate “time” for rendezvous (e.g. agree on timing scheme vialocks, or on a publication location scheme).these protocols typically rely recursively on controlled communication! (e.g. callback orcontinuation on lock release, e.g. publication of a fwding pointer in a well-knownlocation followed by polling, etc.)Detection: Identify an undesirable communication (one that violates ordering constraints), andsomehow undo an agent.Ensure that all communication it performed was invisible, or recursively undo.V. Acceptable orders of communication1. What are the basic operations on state? Communication — i.e. data dependencies.2. What orders matter for these operations? It depends!3. A client’s view of the acceptable orderings: serial schedules, serializability.4. Conflicts. Assume two clients, one server. What interleavings do not preserve client views? R-W andW-W conflicts. Conflict Serializability is a conservative test for Serializability.VI. Locking as the “antijoin antechamber”Idea: Since communication is rendezvous, let’s prevent inappropriate rendezvous — no conflicts!Result: equiv. to a serial schedule based on time-of-commit. (Dynamic!)consider a rendezvous in space: e.g. two spies passing a message in a locked room.before you can “enter” the rendezvous point:check that no conflicting action is currently granted access to the rendezvous point (not-in =“antijoin”).if yes conflict with the granted actions (join), wait in the antechamberif no conflict, mark yourself (persistently until EOT) as having been granted access. Enterthe rendezvous point to do your businesswhen granted transactions depart, choose a mutually compatible group of transactions to letinto the granted group.some games we can play with spacecould “move” the rendezvous point in space (locking proxy? lock caching?)could further delay rendezvous in time based on other considerationsYou should know the multi-granularity locks from Gray’s paper! (Took the MySQL guys years to learnthis.)VII. Timestamp ordering (T/O)Streaming symmetric join of reads and writes, outputting data and aborts.T/O. Predeclare the schedule via timestamp (wall-clock? sequence? out-of-sequence?) at transaction birth. Noantijoin = no waiting! But restart when reordering detected…Keep track of r-ts and w-ts for each object: r-ts: max counter rather than persistence.reject (abort) stale reads.reject (abort) delayed writes to objects that have later r-ts (write was already missed). Can allow(ignore) delayed writes to objects that have a later w-ts tho. (Thomas Write Rule.)Multiversion T/O: Even fewer restart scenariosKeep sets of r-ts, and . This is kind of like symmetric persistence.Reads never rejected! (more liberal than plain T/O)Write rule on x: interval(W(x)) = [ts(W), mw-ts] where mw-ts is the next write after W(x) — i.e. Min_xw-ts(x) > ts(W). If any R-ts(x) exists in that interval, must reject write. I.e. that read shoulda read thiswrite. Note more liberal than plain T/O since subsequent writes may “mask” this one for even laterreads.GC of persistent state: anything older than Min TS of live transactions.Note: no waiting (blocking, antijoin) in Multiversion T/O.VIII. Optimistic concurrency: antijoin with historySchedule predeclared by acquiring timestamp before validation.go through basic OCCidea: persist read history, copy on write, and try to antijoin over time window on commit to ensure“conflicts in a particular order”OCC antijoin predicates are complicated — transaction numbers, timestamps for read/write phases,read/write sets:Valdating Tj. Suppose TN(Ti) < TN(Tj). Serializable if for all uncommitted Ti one of the followingholds (“for all” is like anti join — i.e. notin(set-of-uncommited-Ti, NONE of the following hold))Ti completes writes before Tj starts reads (prevents rw and ww conflicts out of order).WS(Ti) \cap RS(Tj) = empty, Ti completes writes before Tj starts writes (no rw conflicts in order,prevent ww conflicts out of order)WS(Ti) \cap RS(Tj) = empty, WS(Ti) \cap WS(Tj) = empty, Ti finishes read before Tj starts read(no ww conflicts, prevent