manifesto pldi

The Transactional Manifesto: 

The Transactional Manifesto Maurice Herlihy Microsoft Research and Brown University

From the New York Times …: 

From the New York Times … SAN FRANCISCO, May 7. 2004 - Intel said on Friday that it was scrapping its development of two microprocessors, a move that is a shift in the company's business strategy….

Moore’s Law: 

Moore’s Law (hat tip: Simon Peyton-Jones) Clock speed flattening sharply Transistor count still rising

Multicore Architetures: 

Multicore Architetures 'Intel's first dual-core processor will be available April 18 from PC vendors ….' 'AMD will launch a dual-core version of its Opteron server processor at an event in New York on April 21.' [PC World] 'Sun’s UltraSparc IV processor combines 2 UltraSparc III cores on one slice of silicon ….' [xbitlabs]

Why do we care? : 

Why do we care? Time no longer cures software bloat When you double your path length You can’t just wait 6 months Your software must somehow exploit twice as much concurrency

The Problem: 

The Problem Cannot exploit cheap threads Today’s Software Non-scalable methodologies Today’s Hardware Poor support for scalable synchronization

Locking: 

Locking

Coarse-Grained Locking: 

Coarse-Grained Locking Easily made correct … But not scalable.

Fine-Grained Locking: 

Fine-Grained Locking Here comes trouble …

Why Locking Doesn’t Scale: 

Why Locking Doesn’t Scale Not Robust Relies on conventions Hard to Use Conservative Deadlocks Lost wake-ups Not Composable

Locks are not Robust: 

Locks are not Robust If a thread holding a lock is delayed … No one else can make progress

Why Locking Doesn’t Scale: 

Why Locking Doesn’t Scale Not Robust Relies on conventions Hard to Use Conservative Deadlocks Lost wake-ups Not Composable

Locking Relies on Conventions: 

Locking Relies on Conventions Relation between Lock bit and object bits Exists only in programmer’s mind /* * When a locked buffer is visible to the I/O layer * BH_Launder is set. This means before unlocking * we must clear BH_Launder,mb() on alpha and then * clear BH_Lock, so no reader can see BH_Launder set * on an unlocked buffer and then risk to deadlock. */ Actual comment from Linux Kernel (hat tip: Bradley Kuszmaul)

Why Locking Doesn’t Scale: 

Why Locking Doesn’t Scale Not Robust Relies on conventions Hard to Use Conservative Deadlocks Lost wake-ups Not Composable

Sadistic Homework: 

Sadistic Homework enq(x) enq(y) Double-ended queue No interference if ends 'far enough' apart

Sadistic Homework: 

Sadistic Homework enq(x) enq(y) Double-ended queue Interference OK if ends 'close enough' together

Sadistic Homework: 

Sadistic Homework deq() deq() Double-ended queue Make sure suspended dequeuers awake as needed 

You Try It …: 

You Try It … One lock? Too Conservative Locks at each end? Deadlock, too complicated, etc Waking blocked dequeuers? Harder that it looks

Actual Solution: 

Actual Solution Clean solution would be a publishable result [Michael andamp; Scott, PODC 96] What good is a methodology where solutions to such elementary problems are hard enough to be publishable?

In Search of the Lost Wake-Up: 

In Search of the Lost Wake-Up Waiting thread doesn’t realize when to wake up It’s a real problem in big systems 'Calling pthread_cond_signal() or pthread_cond_broadcast() when the thread does not hold the mutex lock associated with the condition can lead to lost wake-up bugs.' from Google™ search for 'lost wake-up'

Why Locking Doesn’t Scale: 

Why Locking Doesn’t Scale Not Robust Relies on conventions Hard to Use Conservative Deadlocks Lost wake-ups Not Composable

Locks do not compose: 

Locks do not compose add(T1, item) delete(T1, item) add(T2, item) item item Move from T1 to T2 Must lock T2 before deleting from T1 Exposing lock internals breaks abstraction Hash Table Must lock T1 before adding item

Monitor Wait and Signal: 

Monitor Wait and Signal zzz If buffer is empty, wait for item to show up Empty buffer Yes!

Wait and Signal do not Compose: 

Wait and Signal do not Compose empty empty zzz… Wait for either?

The Transactional Manifesto: 

The Transactional Manifesto What we do now is inadequate to meet the multicore challenge Research Agenda Replace locking with a transactional API Design languages to support this model Implement the run-time to be fast enough

Related Work: Software: 

Related Work: Software DSTM [PODC 03] Sun Microsystems, Java library FSTM, OSTM [OOPSLA 03] Cambridge University, Java extension STM Haskell [PPoPP 05 that’s tomorrow!] Microsoft Research SXM [TBA] Microsoft Research, C# library

Related Work: Hardware: 

Related Work: Hardware First wave Herlihyandamp;Moss 93, Stone et al. 93 Second wave Rajwarandamp;Goodman 02, Martinezandamp;Torellas 02, Oplingerandamp;Lam 02, Hammond et al. 04, Rajwar et al. 05

Sadistic Homework Revisited: 

Public void LeftEnq(item x) { Qnode q = new Qnode(x); q.left = this.left; this.left.right = q; this.left = q; } Sadistic Homework Revisited (1) Write sequential Code

Transactions in SXM: 

Transactions in SXM myDelegate = new XAction.Delegate(LeftEnq); XAction.Run(myDelegate, item); Create a delegate (function ptr) to your method

Transactions: 

Transactions Run it as a transaction myDelegate = new XAction.Delegate(LeftEnq); XAction.Run(myDelegate, item);

Transactions in SXM: 

Transactions in SXM No need to figure out: which locks protect which objects order of lock acquisition andamp; release myDelegate = new XAction.Delegate(LeftEnq); XAction.Run(myDelegate, item);

Composition: 

Public void Transfer(Queue q1, q2) { Item x = q1.deq(); q2.enq(x); } Composition (1) Trivial or what?

Wake-ups: lost and found: 

Public item LeftDeq() { if (this.left == null) XAction.Retry(); … } Wake-ups: lost and found (1) Roll back transaction and restart when something changes (See PPoPP paper for details)

OrElse Composition: 

OrElse Composition myDelegate1 = new XAction.Delegate(q1.Deq); myDelegate2 = new XAction.Delegate(q2.Deq) XAction.OrElse(myDelegate1, myDelegate2); Run 1st method. If it retries … Run 2nd method. If it retries … Entire statement retries See PPoPP paper

Optimistic Synchronization: 

Optimistic Synchronization 'Easier to apologize than to ask permission' Detects conflicts dynamically If a conflict occurs One transaction may abort another If no conflict occurs They run in parallel Deadlock (practically) impossible

Old Wine in New Bottles?: 

Old Wine in New Bottles? Just another failed Utopian 20th Century ideology? Effective when conflicts are rare Low overhead, no waiting Ineffective otherwise Roll back, wasted work

Solution: Division of Labor: 

Solution: Division of Labor System Detects conflicts Rolls back andamp; retries failed transactions Contention Manager (user-provided) Mediates conflict Toolkit: backoff, queuing, aging, etc. Performance issue, not correctness!

Ease of Use: Bottom Line: 

Ease of Use: Bottom Line Used summer interns at Sun to design and implement complex, fine-grained concurrent data structures Red-black trees, skew heaps, etc…. None were harmed We defy you to try this with locks

Open Research Questions: 

Open Research Questions Some are subject of 'serious dispute in high style' Some are mysterious All are fair game for PLDI community Language Design Implementation

What is a Transaction?: 

What is a Transaction? Replacement for critical section? Are transactions 1st-class objects? Is everything a transaction? Can transactions Be long-lived? Do remote method invocation? Et cetera …

Nested Transactions?: 

Nested Transactions? Some form of nesting is essential Because method calls are nested 'Flat' nesting Outermost only matters Easy to implement First-Class nesting Needed for OrElse composition

Types & Classes: 

Types andamp; Classes Can any object be transactional? Probably not Is it an attribute of the class? DSTM: no, use 'wrapper' object SXM: yes, andamp; must follow conventions STM Haskell: hell, yes.

What about Libraries?: 

What about Libraries? Do we need two copies of every library routine One transaction-safe, one not Is it like being thread-safe? What about system calls?

What about I/O?: 

What about I/O? Some I/O makes sense Provide transaction-safe libraries Undoable file system/DB calls Some doesn’t Opening cash drawer Firing missile

Interaction with non-transactional threads: 

Interaction with non-transactional threads Same questions raised by Java memory group Hans-J Boehm’s talk Important Transactional integrity preserved Normal-case performance unaffected

Wild & Crazy Models: 

Wild andamp; Crazy Models Long-lived transactions Distributed transactions Compensating actions Automatic apology after firing missile Concurrency within transactions, Integration with old-school (persistent) transactional systems

Contention Managers: 

Contention Managers What works and why? Scherer and Scott [CSJP 04] tested Backoff, randomized, various priority, … None dominates on all benchmarks Guerraoui, Herlihy, and Pochon [PODC 05] CMs that guarantee a competitive ratio against optimal off-line scheduler Ideal combination of theory andamp; practice

Consistency: 

Consistency Do transactions always see a consistent state? Sometimes cheaper if 'doomed' transactions don’t OK if you can squash side-effects Dubious otherwise

Implementation Issues: 

Implementation Issues Granularity of synchronization Word or object? Conflict detection At run-time or commit-time? Commit/Abort Undo on abort? Redo on commit?

Performance: 

Performance Costs CAS calls Copying Improvements possible Compiler/postprocessor optimizations Better data structures, algorithms, etc.

Hardware Support: 

Hardware Support Will software TMs be fast enough? We don’t know yet Will we need hardware support? Number of proposals exist HW/SW division of responsibilities?

Automatic Parallelization?: 

Automatic Parallelization? Effective parallelization must be aggressive, not afraid to make mistakes But that requires synchronization Locks can’t cut it Maybe optimistic, non-blocking transactions can …

My Penultimate Slide: 

My Penultimate Slide A workshop on transactional issues in programming languages (broadly defined) is being planned to precede the next PLDI. Stay tuned … Oh, and did I mention there is a PPoPP paper tomorrow on STM Haskell?

I, for one, Welcome our new Multicore Overlords …: 

I, for one, Welcome our new Multicore Overlords … Multicore architectures force us to rethink how we do synchronization Standard locking model won’t work Transactional model might Software Hardware A PLDI full-employment act!