صفحه 1:
State You’re Doing it Wrong:
Alternative Concurrency
Paradigms For the JVM
Jonas Bonér
Crisp AB
blog: http://jonasboner.com
work: http://crisp.se
code: http://github.com/jboner
twitter: jboner
صفحه 2:
۱۳۱/۰۱۱۵
Agenda
>An Emergent Crisis
>State: Identity vs Value
>Shared-State Concurrency
>Software Transactional Memory (STM)
>Message-Passing Concurrency (Actors)
>Dataflow Concurrency
>Wrap up
@ Sun 2
صفحه 3:
۳۱/۰۱۵
Moore’s Law
>Coined in the 1965 paper by Gordon E. Moore
>The number of transistors is doubling every
18 months
>Processor manufacturers have solved our
problems for years
@ Sun
صفحه 4:
۱۳۱/۰۱۱۵
Not anymore
@ Sun
صفحه 5:
۳۱/۰۱۵
The free lunch is over
>The end of Moore’s Law
>We can’t squeeze more out of one CPU
@ Sun
صفحه 6:
۳۱/۰۱۵
Conclusion
>This is an emergent crisis
>Multi-processors are here to stay
>We need to learn to take advantage of that
>The world is going concurrent
@ Sun
صفحه 7:
۱۳۱/۰۱۱۵
State
@ Sun
صفحه 8:
۳۱/۰۱۵
The devil is tn
the state
@ Sun
صفحه 9:
۳۱/۰۱۵
Wrong,
let me rephrase
@ Sun
صفحه 10:
۳۱/۰۱۵
The devil is tn
the mutable state
@ Sun
صفحه 11:
۳۱/۰۱۵
Definitions
&
Philosophy
@ Sun
صفحه 12:
۳۱/۰۱۵
What is a Value?
A Value is something that
does not change
Discussion based on
htto://clojure.org/state
by Rich Hickey
@ Sun
صفحه 13:
۳۱/۰۱۵
What is an Identity?
A stable logical entity
associated with a
series of different Values
over time
@ Sun
صفحه 14:
۳۱/۰۱۵
What is State?
The Value
an entity with a
specific Identity
has at a particular
point in time
@ Sun
صفحه 15:
۱۳۱/۰۵
How do we know if
something has State?
lf a function is invoked with
the same arguments at
two different points in time and
returns different values...
...then it has state
@ Sun
صفحه 16:
۱۳۱/۰۱۱۵
The Problem
Unification of
Identity & Value
They are
not
the same
@ Sun
صفحه 17:
۱۳۱/۰۵
We need to separate Identity & Value
...add a level of indirection
software Transactional Memory
Managed References
Message-Passing Concurrency
Actors/Active Objects
Dataflow Concurrency
Dataflow (Single-Assignment) Variables
@ Sun
صفحه 18:
۱۳۱/۰۱۱۵
ohared-State
Concurrency
@ Sun
صفحه 19:
۱۳۱/۰۱۱۵
Shared-State Concurrency
>Concurrent access to shared, mutable state.
>Protect mutable state with locks
>The
e Java
°C#
°C/C++
e Ruby
e Python
- etc.
°...way
@ Sun 8
صفحه 20:
۳۱/۰۱۵
Shared-State Concurrency is
incredibly hard
>Inherently very hard to use reliably
>Even the experts get it wrong
@ Sun 7
صفحه 21:
Roadmap:
۱۳۱/۰۵
Let's look at three problem domains
1. Need for consensus and truly shared knowledge
Example: Banking
2. Coordination of independent tasks/processes
Example: Scheduling, Gaming
3. Workflow related dependent processes
Example: Business processes, MapReduce
@ Sun
صفحه 22:
۳۱/۰۱۵
...and for each of these...
1. Look at an implementation using
Shared-State Concurrency
2. Compare with implementation using an
alternative paradigm
@ Sun
صفحه 23:
تاثا در
Roadmap:
Let's look at three problem domains
1. Need for consensus and truly shared knowledge
Example: Banking
2. Coordination of independent tasks/processes
Example: Scheduling, Gaming
3. Workflow related dependent processes
Example: Business processes, MapReduce
@ Sun 25
صفحه 24:
۳۱/۰۱۵
Problem 1:
Transfer funds
between bank accounts
@ Sun
صفحه 25:
۱۳۱/۰۱۱۵
ohared-State Concurrency
Transfer funds
between bank accounts
@ Sun
صفحه 26:
۳۱/۰۱۵
Account
public class Account {
private double balance;
public void withdraw(double amount) {
balance -= amount;
}
public void deposit(double amount) {
balance += amount;
}
}
> Not thread-safe
@Sun 5
صفحه 27:
۳۱/۰۱۵
Let’s make it thread-safe
public class Account {
private double balance;
public synchronized void withdraw(double amount) {
balance -= amount;
}
public synchronized void deposit(double amount) {
balance += amount;
}
}
>Thread-safe, right?
@ Sun 03
صفحه 28:
۳۱/۰۱۵
It's still broken
Not atomic
@ Sun
صفحه 29:
۳۱/۰۱۵
Let’s write an atomic transfer method
public class Account {
public synchronized void transferTo(
Account to, double amount) {
this.withdraw(amount) ;
to.deposit(amount) ;
}
۰
> This will work right?
@Sun 5
صفحه 30:
۳۱/۰۱۵
Let’s transfer funds
Account alice =...
Account bob = ...
// in one thread
alice.transferTo(bob, 10.@D);
// in another thread
bob.transferTo(alice, 3.@D);
iicrasystems
صفحه 31:
۱۳۱/۰۱۱۵
Might lead to
DEADLOCK
Darn, this is really hard!!!
@ Sun
صفحه 32:
۳۱/۰۱۵
We need to enforce lock ordering
>How?
>Java won't help us
>Need to use code convention (names etc.)
>Requires knowledge about the internal state
and implementation of Account
>...runs counter to the principles of
encapsulation in OOP
>Opens up a Can of Worms
@ Sun ۳
صفحه 33:
۳۱/۰۱۵
The problem with locks
Locks do not compose
Taking too few locks
Taking too many locks
Taking the wrong locks
Taking locks in the wrong order
Error recovery is hard
@ Sun ۳
صفحه 34:
۱۳۱/۰۱۱۵
Java bet on the
wrong horse
But we're not completely screwed
There are alternatives
@ Sun
صفحه 35:
۱۳۱/۰۱۱۵
We need better
and more high-level
abstractions
@ Sun
صفحه 36:
۱۳۱/۰۱۱۵
Alternative Paradigms
>Software Transactional Memory (STM)
>Message-Passing Concurrency (Actors)
>Dataflow Concurrency
@ Sun
صفحه 37:
۱۳۱/۰۱۱۵
Software Transactional
Memory (STM)
lcrosystems
صفحه 38:
۱۳۱/۰۱۱۵
software Transactional Memory
>See the memory (heap and stack) as a
transactional dataset
>Similar to a database
° begin
-commit
e abort/rollback
>Transactions are retried automatically upon
collision
>Rolls back the memory on abort
@ Sun ۳
صفحه 39:
۳۱/۰۱۵
software Transactional Memory
> Transactions can nest
> Transactions compose (yipee!!)
atomic {
atomic {
lcrosystems
صفحه 40:
۳۱/۰۱۵
Restrictions
>All operations in scope of a transaction:
e Need to be idempotent
eCan’t have side-effects
lcrosystems
صفحه 41:
۳۱/۰۱۵
Case study:
Clojure
@ Sun
صفحه 42:
۱۳۱/۰۱۱۵
What is Clojure?
>Functional language
>Runs on the JVM
>Only immutable data and datastructures
>Pragmatic Lisp
>Great Java interoperability
>Dynamic, but very fast
@ Sun 58
صفحه 43:
۳۱/۰۱۵
Clojure’s concurrency story
>STM (Refs)
e Synchronous Coordinated
>Atoms
e Synchronous Uncoordinated
>Agents
e Asynchronous Uncoordinated
>Vars
e Synchronous Thread Isolated
@ Sun 8
صفحه 44:
۱۳۱/۰۱۱۵
STM (Refs)
>A Ref holds a reference to an immutable value
>A Ref can only be changed in a transaction
>Updates are atomic and isolated (ACI)
>A transaction sees its own snapshot of the world
>Transactions are retried upon collision
@ Sun “
صفحه 45:
۳۱/۰۱۵
Let’s get back to our banking problem
The STM way
Transfer funds
between bank accounts
@ Sun 4
صفحه 46:
تاثا در
Create two accounts
33; alice’s account with balance 160060 USD
(def alice (ref 1000))
33 bob’?s account with balance 10@0@ USD
(def bob (ref 1000))
@ Sun ۱
صفحه 47:
۱۳۱/۰۱۱۵
Transfer 100 bucks
33 amount to transfer
(def amount 100)
33 not valid
throws exception since و و
33 no transaction is running
(ref-set alice (- @alice amount) )
(ref-set bob (+ @bob amount) )
صفحه 48:
۳۱/۰۱۵
Wrap in a transaction
33 update both accounts inside a transaction
(dosync
(ref-set alice (- @alice amount) )
(ref-set bob (+ @bob amount)))
صفحه 49:
JavaOne
Potential problems with STM
High contention (many transaction collisions) can lead to:
Potential bad performance and too high latency
Progress can not be guaranteed (e.g. live locking)
Fairness is not maintained
Implementation details hidden in black box
@ Sun 8
صفحه 50:
۳۱/۰۱۵
My (humble) opinion on STM
>Can never work fine in a language that don’t have
compiler enforced immutability
>E.g. never in Java (as of today)
>Should not be used to “patch” Shared-State
Concurrency
> Still a research topic how to do it in imperative
languages
@ Sun 5
صفحه 51:
۳۱/۰۱۵
Discussion: Problem 1
Need for consensus and truly shared knowledge
Shared-State Concurrency
Bad fit
Software Transactional Memory
Great fit
Message-Passing Concurrency
Terrible fit
Dataflow Concurrency
Terrible fit
@ Sun 9
صفحه 52:
۱۳۱/۰۱۱۵
Message-Passing
Concurrency
lcrosystems
صفحه 53:
JavaOne
Actor Model of Concurrency
>Implements Message-Passing Concurrency
>Originates in a 1973 paper by Carl Hewitt
>Implemented in Erlang, Occam, Oz
>Encapsulates state and behavior
>Closer to the definition of OO than classes
@ Sun 5
صفحه 54:
۳۱/۰۱۵
Actor Model of Concurrency
>Share NOTHING
>|solated lightweight processes
> Can easily create millions on a single workstation
>Communicates through messages
>Asynchronous and non-blocking
@ Sun 9
صفحه 55:
۳۱/۰۱۵
Actor Model of Concurrency
>No shared state
e... hence, nothing to synchronize.
>Each actor has a mailbox (message queue)
@ Sun 5
صفحه 56:
۳۱/۰۱۵
Actor Model of Concurrency
>Non-blocking send
>Blocking receive
>Messages are immutable
>Highly performant and scalable
e Similar to Staged Event Driven Achitecture style (SEDA)
@ Sun 5
صفحه 57:
۳۱/۰۱۵
Actor Model of Concurrency
>Easier to reason about
>Raised abstraction level
>Easier to avoid
e Race conditions
e Deadlocks
e Starvation
e Live locks
@ Sun 5
صفحه 58:
۳۱/۰۱۵
Fault-tolerant systems
>Link actors
>Supervisor hierarchies
e One-for-one
e All-for-one
>Ericsson’s Erlang success story
°9 nines availability (831 ms/year downtime)
@ Sun 5
صفحه 59:
۳۱/۰۱۵
Roadmap:
Let's look at three problem domains
2. Coordination of independent tasks/processes
Example: Scheduling, Gaming
@ Sun 5
صفحه 60:
۳۱/۰۱۵
Problem 2:
A game of ping pong
@ Sun
صفحه 61:
۱۳۱/۰۱۱۵
ohared-State Concurrency
A game of ping pong
@ Sun
صفحه 62:
۱۳۱/۰۱۱۵
Ping Pong Table
public class PingPongTable {
public void hit(String hitter) {
System.out.printin(hitter) ;
}
}
@ Sun 5
صفحه 63:
۱۳۱/۰۱۱۵
Player
public class Player implements Runnable {
private PingPongTable myTable;
private String myName;
public Player(String name,
PingPongTable table) {
myName = name;
myTable = table;
}
ohun ۳
صفحه 64:
۱۳۱/۰۱۱۵
Player cont...
public void run() {
while (true) {
synchronized(myTable) {
try {
myTable. hit(myName) ;
۱۱۷ ۲ 016۰۳00110۷۵11 ) ( و
myTable.wait();
} catch (InterruptedException e) {}
}
}
}
صفحه 65:
۱۳۱/۰۱۱۵
Run it
PingPongTable table = new PingPongTable() ;
Thread ping =
new Thread(new Player("Ping", table));
Thread pong =
new Thread(new Player("Pong", table));
ping.start();
pong.start();
@ Sun os
صفحه 66:
۱۳۱/۰۱۱۵
Help: java.util.concurrent
>Great library
>Raises the abstraction level
>No more wait/notify & synchronized blocks
>Concurrent collections
>Executors, ParallelArray
>Simplifies concurrent code
>Use it, don’t roll your own
@ Sun 5
صفحه 67:
تاثا در
Actors
A game of ping pong
@ Sun
صفحه 68:
۳۱/۰۱۵
Define message
case object Ball
@ Sun
صفحه 69:
۳۱/۰۱۵
Player 1: Pong
val pong = actor {
loop {
receive { // wait on message
case Ball => // match on message Ball
println("Pong" )
reply(Ball)
lcrosystems
صفحه 70:
۱۳۱/۰۱۱۵
Player 2: Ping
val ping = actor {
pong ! Ball // start the game
loop {
receive {
case Ball =>
println("Ping" )
reply(Ball1)
@ Sun 5
صفحه 71:
۳۱/۰۱۵
Run it
...well, they are already up and running
@ Sun 7
صفحه 72:
۱۳۱/۰۱۱۵
Actor implementations for the JVM
>Killim (Java)
>Jetlang (Java)
>Actor’s Guild (Java)
>ActorFoundry (Java)
>Actorom (Java)
>FunctionalJava (Java)
>Akka Actor Kernel (Java/Scala)
>GParallelizer (Groovy)
>Fan Actors (Fan)
@ Sun 9
صفحه 73:
۳۱/۰۱۵
Discussion: Problem 2
Coordination of interrelated tasks/processes
Shared-State Concurrency
Bad fit (ok if java.util.concurrent is used)
STM
Won't help
Message-Passing Concurrency
Great fit
Dataflow Concurrency
Ok
@ Sun 8
صفحه 74:
۳۱/۰۱۵
Dataflow Concurrency
The forgotten paradigm
@ Sun
صفحه 75:
۳۱/۰۱۵
Dataflow Concurrency
>Declarative
>No observable non-determinism
>Data-driven — threads block until data is available
>On-demand, lazy
>No difference between:
>Concurrent and
>Sequential code
@ Sun 3
صفحه 76:
۳۱/۰۱۵
Dataflow Concurrency
>No race-conditions
>Deterministic
>Simple and beautiful
lcrosystems
صفحه 77:
۳۱/۰۱۵
Dataflow Concurrency
>Dataflow (Single-Assignment) Variables
>Dataflow Streams (the tail is a dataflow variable)
>Implemented in Oz and Alice
@ Sun 7
صفحه 78:
۳۱/۰۱۵
Just three operations
>Create a dataflow variable
>Wait for the variable to be bound
>Bind the variable
@ Sun
صفحه 79:
۱۳۱/۰۱۱۵
Limitations
>Can’t have side-effects
e Exceptions
° lO (printin, File, Socket etc.)
e Time
° etc.
e Not general-purpose
e Generally good for well-defined isolated modules
@ Sun 3
صفحه 80:
۳۱/۰۱۵
Oz-style dataflow concurrency for the JVM
>Created my own implementation (DSL)
> On top of Scala
lcrosystems
صفحه 81:
۱۳۱/۰۱۱۵
API: Dataflow Variable
// Create dataflow variable
val x, y, z = new DataFlowVariable|[ Int]
// Access dataflow variable (Wait to be bound)
z()
// Bind dataflow variable
x << 40
// Lightweight thread
thread { y << 2 }
@ Sun ا
صفحه 82:
۳۱/۰۱۵
API: Dataflow Stream
Deterministic streams (not |O streams)
// Create dataflow stream
val producer = new DataFlowStreamn[ Int]
// Append to stream
producer >>> 5
// Read from stream
producer()
iicrasystems
صفحه 83:
۳۱/۰۱۵
Roadmap:
Let's look at three problem domains
3. Workflow related dependent processes
Example: Business processes, MapReduce
@ Sun ۳
صفحه 84:
۳۱/۰۱۵
Problem 3:
Producer/Consumer
@ Sun
صفحه 85:
۱۳۱/۰۱۱۵
ohared-State Concurrency
Producer/Consumer
@ Sun
صفحه 86:
۳۱/۰۱۵
Use java.util.concurrent
Fork/Join framework (ParallelArray etc.)
ExecutorService
Future
BlockingQueue
@ Sun 9
صفحه 87:
۱۳۱/۰۱۱۵
Dataflow Concurrency
Producer/Consumer
lcrosystems
صفحه 88:
۳۱/۰۱۵
Example: Dataflow Variables
// sequential version
val x, y, z = new DataFlowVariable|[ Int |
x << 40
۷ >> 2
z << x() + y()
printin("z = " + z())
@ Sun 5
صفحه 89:
۳۱/۰۱۵
Example: Dataflow Variables
// concurrent version: no difference
val x, y, z = new DataFlowVariable|[ Int |
thread { x << 40 }
thread { y << 2 }
thread {
2 << x() + y()
println("z = " + z())
}
@ Sun 5
صفحه 90:
۳۱/۰۱۵
Dataflow Concurrency in Java
DataRush (commercial)
Flow-based Programming in Java (dead?)
FlowJava (academic and dead)
@ Sun
صفحه 91:
۳۱/۰۱۵
Discussion: Problem 3
Workflow related dependent processes
Shared-State Concurrency
Ok (if java.util.concurrent is used)
STM
Won't help
Message-Passing Concurrency
Ok
Dataflow Concurrency
Great fit
@ Sun 9
صفحه 92:
JavaOne
Wrap up
>Parallel programs is becoming increasingly important
>We need a simpler way of writing concurrent
programs
>“Java-style” concurrency is too hard
>There are alternatives worth exploring
e Message-Passing Concurrency
e Software Transactional Memory
e Dataflow Concurrency
e Each with their strengths and weaknesses
@ Sun «2
صفحه 93:
JavaOne
Jonas Bonér
Crisp AB
blog: http://jonasboner.com
work: http://crisp.se
code: http://github.com/jboner
twitter: jooner
