• If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!

View
 

BernsteinConcurrencyControl

Page history last edited by PBworks 17 years, 3 months ago

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
  •  

Comments (0)

You don't have permission to comment on this page.