Lecture

• 3 techniques for CC
  • locking, 2PL
  • timestamp ordering
  • optimistic control
• Why hard?
  • lack of global info
  • replication of data: need to update both
    • you want stored items to emulate logical items
• model paper uses: TMs with private workspace, DM which handles stored items
• dm-read(x): read from DM, dm-prewrite(x): "private writes", dm-write(x): pubic writes
• distributed locking
  • replication handling
    • primary site/DM
    • primary copy: similar, but partitioned (still need read lock)
    • decentralized: ready any copy, write locks on all copies (mostly used in industry)
    •  voting: read at k, write at n-k+1 | n-k+1 > n/2, TODO: makes reads more expensive, writes cheaper
      • need to make sure you read the "newest" timestamp
  • distributed deadlock
    • prevention: xacts timestamps with localtime : site ID
      • wound-wait: Ti->Tj conflicts, TS(Ti) < TS(Tj) ? wound Tj : wait on Tj
      • wait-die: TS(Ti) < TS(Tj) ? wait on Tj : Ti dies | "conservative"
    • detection:
      • centralized "snoop" site
      • improved snoop: send wait graphs; check deadlocks; appooint next snoop
      • hierachical: check each level
      • edge chasing: R* ; complicated
      • timeout: not discussed in paper, but commonly used now

• "conservative timestamping": ignore
• T/O you get new timestamp each restart
• READ(T,X)
  • TS(T) < TS-W(X) : restart
  • set TS-R(X) =  max(old, TS(T))

• WRITE(T,X)
  • if TS(T) < TS-R(X) || TS(T) < TS-W(X) ? restart T :
  •  Thomas write rule TODO
• commit(T): unbuffer, make all writes
• multiversion timestamp ordering: keep linked list of all values: read from the right timestamp
• 2PL: use waiting
• certifying transactions: SIGMOD '85: Singha TODO
  • use similar to BT/O, but picks TSs at the end
  • info: TS-R, TS-W updated at commit time. remember these figures to ensure world hasn't changed before commit
  • General execution plan:
  • 1. TM initiates T at all sites needed
  • 2. when sub xacts done, report back to coordinator: DONE
  • 3. master chooses timestamp of T, sends validate(T) to sub-xact
  • 4. sub-xact do local certification, report back: READY or ABORT
  • 5, master commmits or aborts

• local certification is  in a critical section
• pending Ts are treated as if they'll commit
•