name: inverse layout: true class: center, middle, inverse --- # Such blocking very concurrency, wow ??? thinking of calling it "such writers block, very concurrency" --- class: center layout: false # Follow along http://shairosenfeld.com/such_blocking_very_concurrency/ # http://shairosenfeld.com/sbvc/ Slides are going to be dense... --- name: whoami layout: false .left-column[ # Who Am I ] .right-column[ - Work at [Engine Yard](http://engineyard.com) - I code on [github / shaiguitar](http://github.com/shaiguitar) - Tweet at me [@shaiguitar](http://twitter.com/shaiguitar) - Other boring info on my [personal website](http://shairosenfeld.com) ] --- template: inverse .headernote[ ## Such blocking very concurrency, wow ] Cats. --- template: inverse .headernote[ ## Such blocking very concurrency, wow ] Cats. Tech talks must have cats in them. --- class: center .left-column[ ## Cats ] ![cat1](images/cat1.gif) --- class: center .left-column[ ## Cats ] ![cat2](images/cat2.gif) --- class: center .left-column[ ## Cats ] ![cat3](images/cat3.gif) --- template: inverse .headernote[ ## Such blocking very concurrency, wow ] How do you scale? ??? since this is a talk about scaling, I was thinking I should give a talk about concurrency! that's how you scale, right? --- class: center, middle ![sb](images/super_bowl.gif) --- class: center, middle ![sb](images/super_bowl1.gif) --- template: inverse .headernote[ ## Such blocking very concurrency, wow ] How do you scale? Do more things at once! --- .left-column[ ## Agenda ] .right-column[ .center-height[ - Talk about all the ways you can do more things at once! ] ] --- .left-column[ ## Agenda ] .right-column[ All of the ways! ![all](images/all.jpg) ] --- .left-column[ ## Agenda ] .right-column[ - Concurrency and Parallelism. ] --- .left-column[ ## Agenda ] .right-column[ All of the ways! ![all](images/all.jpg) ] --- .left-column[ ## Agenda ] .right-column[ - Concurrency and Parallelism. Models... - Actors. - Shared memory (mutexes, STM). - Communicating sequential processes aka CSP. - Futures/Promises/Dataflow variables. - Coroutines/Continuations. - Evented IO/multiplexing. - ...... ] --- .left-column[ ## Agenda ] .right-column[ All of the ways! ![all](images/all.jpg) ] --- .left-column[ ## Agenda ] .right-column[ - Petri nets - Process Calculi - Ambient calculus - Calculus of Communicating Systems - π-calculus - Join-calculus - ...... ] --- .left-column[ ## Agenda ] .right-column[ ![thenIwaslike](images/theniwaslike.jpg) ] --- But I wanna... ![do_work](images/do_work.png) --- name:agenda .left-column[ ## Agenda So...for realsies! ] .right-column[ - A concurrency patterns Tour - General concepts - Models - Pros/Cons ] --- name:agenda .left-column[ ## Agenda So...for realsies! ] .right-column[ - A concurrency patterns Tour - General concepts - Models - Pros/Cons ] --- template: inverse # General Concepts ## common ingredients --- template: inverse # Models ## some famous ones --- template: inverse # Advantages/Disadvantages ## pros and cons --- template: inverse # Let you sit with it ## people spend lifetimes on this stuff --- template: inverse # Let you sit with it ## people spend lifetimes on this stuff ## "exercise for the reader" --- name: tour_general template: inverse .headernote[ ## General Concepts / Terminology ] --- template: inverse .headernote[ ## General Concepts / Terminology ] ## Concurrency vs Parallelism What is the difference? --- name:concurrency_vs_parallel_conclusion .left-column[ ## Concurrency tour - General concepts / Terminology - Concurrency vs Parallelism ] .right-column[ http://www.haskell.org/haskellwiki/Parallelism_vs._Concurrency - Warning: Not all programmers agree on the meaning of the terms 'parallelism' and 'concurrency'. They may define them in different ways or do not distinguish them at all. ] --- .left-column[ ## Concurrency tour - General concepts / Terminology - Concurrency vs Parallelism ] .right-column[ ![concurrency_vs_parallel](images/concurrency_vs_parallel.png) ] --- .left-column[ ## Concurrency tour - General concepts / Terminology - Concurrency vs Parallelism ] .right-column[ http://blog.golang.org/concurrency-is-not-parallelism - Concurrency is about dealing with lots of things at once. - Parallelism is about doing lots of things at once. ] --- .left-column[ ## Concurrency tour - General concepts / Terminology - Concurrency vs Parallelism ] .right-column[ ![joe](images/joe.jpg)

Monty Python

] --- .left-column[ ## Concurrency tour - General concepts / Terminology - Concurrency vs Parallelism ] .right-column[ ![joe](images/joe.jpg)

Monty Python

] --- .left-column[ ## Concurrency tour - General concepts / Terminology - Concurrency vs Parallelism ] .right-column[ ![joe](images/joe.jpg)

Joe Armstrong, Erlang

http://joearms.github.io/2013/04/05/concurrent-and-parallel-programming.html http://www.youtube.com/watch?v=uKfKtXYLG78 ] ??? guy in the middle means serious biz. --- .left-column[ ## Concurrency tour - General concepts / Terminology - Concurrency vs Parallelism ] .right-column[ ![concurrency_vs_parallel](images/concurrent_parallel_joe.png) ] --- name:concurrency_vs_parallel_conclusion .left-column[ ## Concurrency tour - General concepts / Terminology - Concurrency vs Parallelism ] .right-column[ http://stackoverflow.com/questions/1050222/concurrency-vs-parallelism-what-is-the-difference - Parallelism: A condition that arises when at least two threads are executing simultaneously. - Concurrency: A more generalized form of parallelism that can include time-slicing as a form of virtual parallelism. ] ??? A simplified conclusion: - Concurrency ⊇ Parallelism * * not actually true ([Flynn's taxonomy](http://en.wikipedia.org/wiki/Flynn%27s_taxonomy)) my unprofessional simplified conclusion is kinda incorrect ( although: http://programmers.stackexchange.com/questions/155109/parallelism-implies-concurrency-but-not-the-other-way-round-right ). But it's simplified. it's not really a subset. See: http://en.wikipedia.org/wiki/Flynn%27s_taxonomy --- template: inverse .headernote[ ## General Concepts / Terminology ] ## OS mechanisms How are things executed? ??? Process is NOT a Concurrent Process in the generic term. --- .left-column[ ## Concurrency tour - General concepts / Terminology - OS mechanisms ] .right-column[ ![multithread](images/multithreaded_process.svg) - Threads and processes ] --- .left-column[ ## Concurrency tour - General concepts / Terminology - OS mechanisms - Processes ] .right-column[ - OS Processes ![resized](images/hello_world.png) ### ps aux | grep a_process ] --- .left-column[ ## Concurrency tour - General concepts / Terminology - OS mechanisms - Threads ] .right-column[ - Native Threads ![resized](images/threads.jpg) http://www.yolinux.com/TUTORIALS/LinuxTutorialPosixThreads.html#BASICS All threads within a process share the same address space. ] --- .left-column[ ## Concurrency tour - General concepts / Terminology - OS mechanisms - Threads ] .right-column[ - "Green" Threads ![resized](images/green_threads.jpg) http://en.wikipedia.org/wiki/Green_threads Scheduled by a virtual machine (VM) without relying on any native OS capabilities. ] ??? maybe expand a bit about fibers, talk more about it later: http://en.wikipedia.org/wiki/Fiber_(computer_science)#Operating_system_support not strictly related to OS, more like a thread that's cooperative template: inverse --- .left-column[ ## Concurrency tour - General concepts / Terminology - OS mechanisms - Processes ] .right-column[ - VM Processes (eg, erlang processes) ![resized](images/inception.png) Similar to green threads but don't share memory. ] ??? It's inception because it's a process within a process. expand on goroutines, erlang processes, the generic term of a "process" in regards to concurrency inception because: process within a process...so that's like a green thread, but it can be different, because no shared state like threads http://stackoverflow.com/questions/2708033/technically-why-are-processes-in-erlang-more-efficient-than-os-threads "Erlang processes correspond (approximately) to green threads in other languages; there's no OS-enforced separation between the processes. (There may well be language-enforced separation, but that's a lesser protection despite Erlang doing a better job than most.) Because they're so much lighter-weight, they can be used far more extensively. OS threads on the other hand are able to be simply scheduled on different CPU cores, and are (mostly) able to support independent CPU-bound processing. OS processes are like OS threads, but with much stronger OS-enforced separation. The price of these capabilities is that OS threads and (even more so) processes are more expensive." --- template:inverse .headernote[ ## General Concepts / Terminology ] ## Scheduling How do you switch around between the executing things? --- .left-column[ ## Concurrency tour - General concepts / Terminology - Scheduling ] .right-column[ ![resized](images/preemtive_cooperative.png) - Preemtive - Cooperative ] ??? exapand on differences of blocking semantics within those? @CT Scheduling: coperative multitasking vs premtive scheduling cooperative multitasking "Because a cooperatively multitasked system relies on each process regularly giving up time to other processes on the system, one poorly designed program can consume all of the CPU time for itself or cause the whole system to hang. in ruby - fibers, continuations, etc. premtive scheduling "Preemptive multitasking allows the computer system to more reliably guarantee each process a regular "slice" of operating time." --- .left-column[ ## Concurrency tour - General concepts / Terminology - Scheduling - Preemtive ] .right-column[ - Preemtive ![resized](images/preemtive.jpg) ] ??? Interrupts It's like Bush, attacks can happen at any time, and for no good reason --- .left-column[ ## Concurrency tour - General concepts / Terminology - Scheduling - Preemtive ] .right-column[ Anything can happen at any time... http://en.wikipedia.org/wiki/Preemption_%28computing%29 "In computing, preemption is the act of temporarily interrupting a task being carried out by a computer system, without requiring its cooperation." ] ??? Interrupts http://en.wikipedia.org/wiki/Interrupt are preemptive. --- .left-column[ ## Concurrency tour - General concepts / Terminology - Scheduling - Cooperative ] .right-column[ - Cooperative ![resized](images/cooperative.gif) ] ??? Essentially, a fiber/coroutine --- .left-column[ ## Concurrency tour - General concepts / Terminology - Scheduling - Cooperative ] .right-column[ http://en.wikipedia.org/wiki/Scheduling_%28computing%29 "It relied on the program to end or tell the OS that it didn't need the processor so that it could move on to another process. This is usually called cooperative multitasking." http://en.wikipedia.org/wiki/Computer_multitasking#Cooperative_multitasking "Each user wanted to see their program running as if it were the only program in the computer. The use of time sharing made this possible, with the qualification that the computer might not seem as fast to any one user as it really would be if it were running only that user's program." ] --- template: inverse .headernote[ ## General Concepts / Terminology ] ## Communication How do the executing things not trip over each other? --- .left-column[ ## Concurrency tour - General Concepts - Atomicity ] .right-column[ Problems happen (in some environments) because operations are not atomic: ```ruby foo =+ 1 actually translates to 1) read foo into TMP 2) increment TMP (whatever calculation is needed) 3) write back foo to curr TMP value ``` http://en.wikipedia.org/wiki/Atomicity_%28programming%29 ```ruby - Thread1: - read variable / eq 0 - increment variable / eq 1 - Thread2: - read variable / eq 0 - Thread1: - write variable / eq 1 - Thread2: - increment variable / eq 1 - write variable / eq 1 ``` ] --- .left-column[ ## Concurrency tour - General concepts / Terminology - Communicate ] .right-column[ ![resized](images/communication.jpeg) ] --- .left-column[ ## Concurrency tour - General concepts / Terminology - Communicate - Shared Memory ] .right-column[ - Shared Memory ![resized](images/shared_mem.jpeg) ] ??? Atomicity is commonly enforced by mutual exclusion, whether at the hardware level building on a cache coherency protocol, or the software level using semaphores or locks. - http://en.wikipedia.org/wiki/Atomic_operation (MyMutex?, hardware support) @CT Communication Shared Mem: synchronization over shared memory: http://en.wikipedia.org/wiki/Dekker%27s_algorithm http://en.wikipedia.org/wiki/Peterson's_algorithm http://en.wikipedia.org/wiki/Test-and-set http://en.wikipedia.org/wiki/Atomic_operation --- .left-column[ ## Concurrency tour - General concepts / Terminology - Communicate - Shared Memory ] .right-column[ http://en.wikipedia.org/wiki/Shared_memory "In computing, shared memory is memory that may be simultaneously accessed by multiple programs with an intent to provide communication among them or avoid redundant copies. Shared memory is an efficient means of passing data between programs." ] --- .left-column[ ## Concurrency tour - General concepts / Terminology - Communicate - Channels / Message Passing ] .right-column[ - Message Passing/Channels ![resized](images/message_passing.gif) ] ??? @CT Communication Channels: !! http://en.wikipedia.org/wiki/Back_pressure !! It's like what you use ever day! unix pipes... the internet! sockets... Hidden from programmer Message passsing/Channels a channel is really a synchronous message passing (passing messages over a stream, in a sync manner: rendezvous). message passing is _kind of_ a async way to communicate over channels (if no stream is necessary, so it's not really a channel). types of message passing: blocking/non blocking, order matters?? can expand on message passing being a kind of subtype of channel (async buffered). or, it can be seen as channels being a type of message passing...related, but not the same (similar to parallel vs concurrent?) just expand on types of channels: block/non or sync/non sync (same in this context?) buffered/non buffered bounded/unbounded "A key characteristic of channels is that they are blocking. In the most primitive form, an unbuffered channel acts as a rendezvous, any reader will await a writer and vice-versa. Buffering can be introduced, but unbounded buffering is discouraged, as bounded buffering with blocking can be an important tool coordinating pacing and back pressure, ensuring a system doesn't take on more work than it can achieve." - http://clojure.com/blog/2013/06/28/clojure-core-async-channels.html expand on the differences of message passing: http://en.wikipedia.org/wiki/Message_passing#Synchronous_versus_asynchronous_message_passing you CAN have a buffered channel, which is kinda async, but IMO that's kinda message passing? cons:Another problem related to asynchronous message passing has to do with buffering. --- .left-column[ ## Concurrency tour - General concepts / Terminology - Communicate - Message Passing ] .right-column[ http://en.wikipedia.org/wiki/Message_passing "Message passing is a way of invoking behavior through some intermediary service or infrastructure. Rather than directly invoke a process, subroutine, or function by name as in conventional programming, message passing sends a message to a process (which may be an actor or object) and relies on the process and the supporting infrastructure to select and invoke the actual code to run." ] --- .left-column[ ## Concurrency tour - General concepts / Terminology - Communicate - Channels ] .right-column[ http://en.wikipedia.org/wiki/Channel_%28programming%29 "In computing, a channel is a model for interprocess communication and synchronization via message passing. A message may be sent over a channel, and another process or thread is able to synchronously receive messages sent over a channel it has a reference to, as a stream." ] --- name: tour_models template: inverse class:middle,center # Models ??? ( http://en.wikipedia.org/wiki/Database-as-IPC and https://blog.engineyard.com/2011/5-subtle-ways-youre-using-mysql-as-a-queue-and-why-itll-bite-you/ ) --- class: center # Follow along http://shairosenfeld.com/such_blocking_very_concurrency/ # http://shairosenfeld.com/sbvc/ --- name: table Let's classify the Concurrency models
Model OS Mechanism Scheduling Communication Concurrent/Parallel Example
Threads & Mutexes Threads Preemptive Shared Memory (locks) C / P Mutex
Threads & Transactional Memory Threads Preemptive Shared Memory (commit/abort) C / P STM
Threads & Message Passing Threads Preemptive Message Passing C / P ~Anonymous Actors
Processes (OS) & IPC Processes Preemptive Shared memory / Message Passing (IPC) C / P Resque / Forking Webservers
CSP (commincating sequential processes) Threads / Processes Preemptive Message Passing (Channels) C / P Occam / Go channels
Actors Threads Preemptive Message Passing (Mailbox) C / P Erlang / Celluloid
Futures / Promises Threads Cooperative Message Passing (itself) C / P Oz / Dataflow variables
Coroutines One process/thread Cooperative ? Message Passing C (not parallel) Fibers
Evented One process/thread Cooperative ? shared memory ? C (not parallel) Eventmachine
??? - This is a rudimentary attempt to simplify a pretty convoluted and complicated subject, take it as such :) - was thinking of adding another column that was "Sucks" ? - TODO put table on github or something, allow some collab editing of it? (since I aint the authority) --- .left-column[ ## Concurrency tour - Models - Threads & Mutexes ] .right-column[
Threads & Mutexes Threads Preemptive Shared Memory (locks) C / P Mutex
![threads_mutex](images/mutex.png) ] --- .left-column[ ## Concurrency tour - Models - Threads & Mutexes ] .right-column[
Threads & Mutexes Threads Preemptive Shared Memory (locks) C / P Mutex
Atomicity problems? http://en.wikipedia.org/wiki/Atomicity_%28programming%29 ![atomicity](images/atomicity.jpg) Just use a mutex! ] ??? important to understand, boiled down, atomicity is the underlying problem of most synchronization issues re concurrency and that's what communicating (or ensuring immutability, which ensures atomicity isn't needed beacuse we'll never run into that scenario) aims to solve --- .left-column[ ## Concurrency tour - Models - Threads & Mutexes ] .right-column[
Threads & Mutexes Threads Preemptive Shared Memory (locks) C / P Mutex
```ruby mutex = Mutex.new shared_counter = 0 t1 = Thread.new do mutex.synchronize do shared_counter += 1 end end t2 = Thread.new do mutex.synchronize do shared_counter += 1 end end t1.join t2.join # shared_counter will always be 2 # (w/out mutex we could get 1 as a result) ``` ] --- .left-column[ ## Concurrency tour - Models - Threads & Mutexes ] .right-column[
Threads & Mutexes Threads Preemptive Shared Memory (locks) C / P Mutex
## Pros - Don't have to worry about scheduling (preemtive) - Common paradigm - Wide support. ## Cons - Scheduling overhead (context switching) - Synchronization/locking issues - livelock, deadlock, blalock ] --- .left-column[ ## Concurrency tour - Models - Threads & Transactions ] .right-column[
Threads & Transactional Memory Threads Preemptive Shared Memory (commit/abort) C / P STM
![stm](images/transactions.jpg) ] --- .left-column[ ## Concurrency tour - Models - Threads & Transactions ] .right-column[
Threads & Transactional Memory Threads Preemptive Shared Memory (commit/abort) C / P STM
Similar conceptually to http://en.wikipedia.org/wiki/Database_transaction "Transactions provide an "all-or-nothing" proposition, stating that each work-unit performed in a database must either complete in its entirety or have no effect whatsoever. Further, the system must isolate each transaction from other transactions, results must conform to existing constraints in the database, and transactions that complete successfully must get written to durable storage." ] --- .left-column[ ## Concurrency tour - Models - Threads & Transactions ] .right-column[
Threads & Transactional Memory Threads Preemptive Shared Memory (commit/abort) C / P STM
http://en.wikipedia.org/wiki/Software_transactional_memory "After completing an entire transaction verifies that other threads have not made changes to memory that it accessed in the past...If validation is successful, made permanent, is called a commit." "May also abort at any time." ] --- .left-column[ ## Concurrency tour - Models - Threads & Transactions ] .right-column[
Threads & Transactional Memory Threads Preemptive Shared Memory (commit/abort) C / P STM
http://stackoverflow.com/questions/1627600/how-do-you-implement-software-transactional-memory Don't wait on a lock, just check when we're ready to _commit_: ```ruby Thread1: atomic { - read variable - increment variable - write variable } Thread2: atomic { - read variable - increment variable # going to write, but Thread1 has written variable... # notices Thread1 changed data, so ROLLS BACK - write variable } ``` Give concurrency the benefit of the doubt it'll probably be fine, most of the time. "Unlike the locking techniques...STM is very optimistic" ] --- .left-column[ ## Concurrency tour - Models - Threads & Transactions ] .right-column[
Threads & Transactional Memory Threads Preemptive Shared Memory (commit/abort) C / P STM
## Pros - Increased concurrency - No thread needs to wait for access to a resource - Smaller scope that needs synchronizing - modifying disjoint parts of a data structure - Locks don't compose; STM's benefits are composability and modularity - http://www.haskell.org/haskellwiki/Software_transactional_memory ## Cons - Aborting transactions - Places limitations on the behavior of transactions - they cannot perform any operation that cannot be undone, including most I/O. ] ??? Such limitations are typically overcome in practice by creating buffers that queue up the irreversible operations and perform them at a later time outside of any transaction --- .left-column[ ## Concurrency tour - Models - Futures / Promises ] .right-column[
Futures / Promises Threads Cooperative Message Passing (itself) C / P Oz / Dataflow variables
![resized](images/future_promise.jpg) ] ??? @CT Futures/Promises http://en.wikipedia.org/wiki/Futures_and_promises "They describe an object that acts as a proxy for a result that is initially unknown" compute a value, either start retrieiving the value before it's asked for or not (explicit vs implicit/eager vs lazy) if you ask for it and it's not ready, do you block or not (raise for example) blocking vs non blocking "The access could block the current thread or process until the future is resolved (possibly with a timeout). This is the semantics of dataflow variables in the language Oz." - dataflow # http://doc.akka.io/docs/akka/current/scala/dataflow.html from what I can tell, uses promises and futures and differs on blocking semantics it's a larger model/arch that is about chaining and changing dependent data (calculating Y if X changes automatically) but it probably has heavy use of futures and promisies. https://blog.jcoglan.com/2013/03/30/callbacks-are-imperative-promises-are-functional-nodes-biggest-missed-opportunity/ con: http://lambda-the-ultimate.org/node/3221 con: http://doc.akka.io/docs/akka/current/scala/dataflow.html ( The limitation is that the code needs to be side-effect free, i.e. deterministic. You can't use exceptions, time, random etc., but need to treat the part of your program that uses dataflow concurrency as a pure function with input and output. ) --- .left-column[ ## Concurrency tour - Models - Futures / Promises ] .right-column[
Futures / Promises Threads Cooperative Message Passing (itself) C / P Oz / Dataflow variables
```ruby require 'celluloid/future' future_pinger = pinger.future.do_ping # returned a reference to an async thing # we can do other calcs here Bignum.calculate_primes future_pinger.value # block when called explicitly # we get a "ping" ponger.do_pong # now we get a "pong" ``` Communication is done via ... itself. When we ask for the value we're telling the ponger to wait for a ping and only then do it. ] --- .left-column[ ## Concurrency tour - Models - Futures / Promises ] .right-column[
Futures / Promises Threads Cooperative Message Passing (itself) C / P Oz / Dataflow variables
## Pros - Abstracts locks away ## Cons - Readiness efficiency (wait if it's not ready yet, similar to locks) http://en.wikipedia.org/wiki/Futures_and_promises#Blocking_vs_non-blocking_semantics ] --- .left-column[ ## Concurrency tour - Models - Processes & IPC ] .right-column[
Processes (OS) & IPC Processes Preemptive Shared memory / Message Passing (IPC) C / P Resque / Forking Webservers
![resized](images/ipc.png) ] --- class:center .left-column[ ## Concurrency tour - Models - Processes & IPC ] .right-column[
Processes (OS) & IPC Processes Preemptive Message Passing (IPC) C / P Resque / Forking Webservers
How do we handle atomicty? Don't share memory. ![noshare](images/nosharing.jpg) How do you communicate? ] ??? You coulse use Shared memory but you'll still need locks (shmget) --- .left-column[ ## Concurrency tour - Models - Processes & IPC ] .right-column[
Processes (OS) & IPC Processes Preemptive Shared memory / Message Passing (IPC) C / P Resque / Forking Webservers
## Message Passing (channels) http://stackoverflow.com/questions/7969557/how-are-message-passing-concurrent-languages-better-than-shared-memory-concurren "Passing data through a channel to a receiver, implies transfer of ownership of the data." ] --- .left-column[ ## Concurrency tour - Models - Processes & IPC ] .right-column[
Processes (OS) & IPC Processes Preemptive Shared memory / Message Passing (IPC) C / P Resque / Forking Webservers
Yeah Pipes: ``` date | xargs echo "The date is:" ``` Mundane communication: ```ruby # process 1 increment_shared_data pipe.write("process 2, I'm done") # process 2 pipe.read # blocks until process 1 allows to go increment_shared_data ## no locks! you could argue a blocking read ## is kind of a "lock", but it's just way to sync ## ## in this case, atomicty isn't guaranteed ## but we are explicity communicating so no need ``` Sockets, and more... ] --- .left-column[ ## Concurrency tour - Models - Processes & IPC ] .right-column[
Processes (OS) & IPC Processes Preemptive Shared memory / Message Passing (IPC) C / P Resque / Forking Webservers
## Pros - Can't corrupt data when data is not shared. - No locking. - Easier to scale horizontally (adding nodes). ## Cons - Can't communicate over shared memory - Slower to spawn a new process vs a new thread - More memory overhead. - Scaling horizontally is $$$ expensive. ] --- .left-column[ ## Concurrency tour - Models - CSP ] .right-column[
CSP (commincating sequential processes) Threads / Processes Preemptive Message Passing (Channels) C / P Occam / Go channels
![hoare](images/hoare.jpg) ![csp](images/csp.jpg) ] ??? closely related to actors CSP was first described in a 1978 (everything has already been invented), historic interest Go highly influenced by it --- .left-column[ ## Concurrency tour - Models - CSP ] .right-column[
CSP (commincating sequential processes) Threads / Processes Preemptive Message Passing (Channels) C / P Occam / Go channels
https://gobyexample.com/channels http://golangtutorials.blogspot.com/2011/06/channels-in-go.html ```go // Go channels! Similar to pipes in IPC func makeCakeAndSend(cs chan string) { i = i + 1 cakeName := "Strawberry Cake " + strconv.Itoa(i) fmt.Println("Making a cake and sending ...", cakeName) cs <- cakeName //send a strawberry cake } func receiveCakeAndPack(cs chan string) { s := <-cs //get whatever cake is on the channel fmt.Println("Packing received cake: ", s) } ``` Same as IPC, dont need locking because we are waiting for our turn, whenever it is our turn. ] --- .left-column[ ## Concurrency tour - Models - CSP ] .right-column[
CSP (commincating sequential processes) Threads / Processes Preemptive Message Passing (Channels) C / P Occam / Go channels
## Pros - Uses message passing and channels heavily, alternative to locks ## Cons - Shared data can be simpler to implement for simple use cases - Handling very big messages, or a lot of messages, unbounded buffers (backpressure helps this) - Messaging is essentially a copy of shared data (usually non-issue. Embedded systems?) ] --- .left-column[ ## Concurrency tour - Models - Actors ] .right-column[
Actors Threads Preemptive Message Passing (Mailbox) C / P Erlang / Celluloid
![resized](images/actors.jpg) ] --- .left-column[ ## Concurrency tour - Models - Actors ] .right-column[
Actors Threads Preemptive Message Passing (Mailbox) C / P Erlang / Celluloid
```ruby class PingActor include Celluloid def ping sleep rand(2) puts "ping" Celluloid::Actor[:ponger].async.pong end end class PongActor include Celluloid def pong puts "pong" Celluloid::Actor[:pinger].async.ping end end Celluloid::Actor[:pinger] = PingActor.new Celluloid::Actor[:ponger] = PingActor.new # start ping ponging Celluloid::Actor[:pinger].async.ping puts "this should print first though" ``` ] --- .left-column[ ## Concurrency tour - Models - Actors ] .right-column[
Actors Threads Preemptive Message Passing (Mailbox) C / P Erlang / Celluloid
Atomicity? Conflict? Every actor has it's own address space. Don't share memory. Communicate via mailboxes. ![actorgraffle](images/actorgraffle.gif) "Don’t communicate by sharing state; share state by communicating" ] --- .left-column[ ## Concurrency tour - Models - Actors ] .right-column[
Actors Threads Preemptive Message Passing (Mailbox) C / P Erlang / Celluloid
```ruby class PingActor include Celluloid def ping sleep rand(2) puts "ping" Celluloid::Actor[:ponger].async.pong end end class PongActor include Celluloid def pong puts "pong" Celluloid::Actor[:pinger].async.ping end end Celluloid::Actor[:pinger] = PingActor.new Celluloid::Actor[:ponger] = PingActor.new # start ping ponging Celluloid::Actor[:pinger].async.ping puts "this should print first though" ``` ] ??? object oriented threads --- .left-column[ ## Concurrency tour - Models - Actors ] .right-column[
Actors Threads Preemptive Message Passing (Mailbox) C / P Erlang / Celluloid
## Comparison with CSP http://en.wikipedia.org/wiki/Communicating_sequential_processes#Comparison_with_the_Actor_Model - CSP processes are anonymous, while actors have identities. - Message-passing in actor systems is fundamentally asynchronous (CSP traditionally uses synchronous messaging: "rendezvous") - CSP uses explicit channels for message passing, whereas actor systems transmit messages to named destination actors. ] --- .left-column[ ## Concurrency tour - Models - Actors ] .right-column[
Actors Threads Preemptive Message Passing (Mailbox) C / P Erlang / Celluloid
## Pros - Uses message passing and channels heavily, alternative to locks - No shared state (avoid locks, easier to scale) - Easier to reason about the code (maintenance) ## Cons - When shared state is required doesn't fit as well - Implementing shared data can be simpler to implement for mundane use cases - Handling very big messages, or a lot of messages, unbounded buffers (backpressure helps this) - Messaging is essentially a copy of shared data (usually non-issue. Embedded systems?) ] --- .left-column[ ## Concurrency tour - Models - Coroutines ] .right-column[
Coroutines One process/thread Cooperative ? Message Passing C (not parallel) Fibers
![resized](images/coroutine.jpg) ] ??? @CT Coroutines / Continuations http://en.wikipedia.org/wiki/Coroutine --- .left-column[ ## Concurrency tour - Models - Coroutines ] .right-column[
Coroutines One process/thread Cooperative ? Message Passing C (not parallel) Fibers
Fibers are coroutines: ```ruby require 'fiber' f1 = nil # for scope f2 = Fiber.new do loop do puts "pong" f1.transfer end end f1 = Fiber.new do i = 0 loop do i += 1 sleep rand(2) puts "ping" f2.transfer Fiber.yield if i == 10 end end f1.resume ``` Cooperative! Handing execution rights between one another, saving local state. ] --- .left-column[ ## Concurrency tour - Models - Coroutines ] .right-column[
Coroutines One process/thread Cooperative ? Message Passing C (not parallel) Fibers
A Curious Course on Coroutines and Concurrency:
David Beazley (https://twitter.com/dabeaz) writing an operating system (!) with only coroutines. http://dabeaz.com/coroutines/ No Threads, Evented style, just cooperative scheduling of coroutines... Possible use cases: http://stackoverflow.com/questions/303760/what-are-use-cases-for-a-coroutine ] --- .left-column[ ## Concurrency tour - Models - Coroutines ] .right-column[
Coroutines One process/thread Cooperative ? Message Passing C (not parallel) Fibers
## Pros - Expressive state: state based computations much easier to understand and implement - No need for locks (cooperative scheduling) - Scales vertically (add more cpu) ## Cons - Single thread: Harder to parallelize/scale horizontally (use more cores, add more nodes) - Constrained to have all the components work together symbiotically ] --- .left-column[ ## Concurrency tour - Models - Evented Programming ] .right-column[
Evented One process/thread Cooperative ? shared memory ? C (not parallel) Eventmachine
![resized](images/evented_prog.gif) ] ??? @CT Evented style: eventmachine, nodejs (coroutines/continuations?) more etc etc CAVEAT: evented programming isn't "the best", use the best tool for the job. I just want to understand it --- name: evented .left-column[ ## Concurrency tour - Models - Evented Programming ] .right-column[
Evented One process/thread Cooperative ? shared memory ? C (not parallel) Eventmachine
## Examples - C10k problem - Eventmachine in ruby - Twisted in python - Redis's event loop - Apache vs Nginx - Node.js vs the world - AJAX - signals? rescuing exceptions? ] --- name: buildingblocks .left-column[ ## What is evented programming? - Common building blocks ] .right-column[
Evented One process/thread Cooperative ? shared memory ? C (not parallel) Eventmachine
## Common building blocks - Event Handlers / Callbacks - Dispatcher: Connecting callbacks, watchers, the loop (event queue/registry) - Timers - Event loop - Reactor / Proactor pattern: handling blocking operations ] ??? CPS style (XXX sidenote: "A continuation is just that, it's a saved state." - http://c2.com/cgi/wiki?StacklessPython ) CPS:"No procedure is allowed to return to its caller--ever." http://matt.might.net/articles/by-example-continuation-passing-style/ "inversion of control" ] --- .left-column[ ## What is evented programming? - Common building blocks - Event Handlers / Callbacks ] .right-column[
Evented One process/thread Cooperative ? shared memory ? C (not parallel) Eventmachine
http://en.wikipedia.org/wiki/Event_(computing)#Event_handler ```ruby # Taken from github @tmm1/http_parser.rb # uses ry http parser require "http/parser" parser = Http::Parser.new parser.on_headers_complete = proc do p parser.headers end ``` ```ruby h[:on_headers_complete] = proc { puts "inspect all the headers" } ``` Create "watchers" which store callbacks, of what to do when an event is recognized. ] --- .left-column[ ## What is evented programming? - Common building blocks - Dispatcher ] .right-column[
Evented One process/thread Cooperative ? shared memory ? C (not parallel) Eventmachine
When something happens that we have a watcher for, that watcher queues an event to act upon, to be executed. An abstraction of the Queue/Registry of pending events to take action upon is the Dispatcher. - Event type (timer, io, whatever) - Event handler (callback) - Data (IO handles/other)
name (event type/incoming event) what to do (callback) IO handle or event specific data (data)
headers parsed inspect the headers Socket fd 4
body chuck received add it to the buffer Socket fd 4
a timer fired execute the timer callback/event handler in 666 seconds
handle user interrupt write logs SIGUSR1
justin bieber is playing on the radio change station Baby Baby Baby
] --- .left-column[ ## What is evented programming? - Common building blocks - Timers ] .right-column[
Evented One process/thread Cooperative ? shared memory ? C (not parallel) Eventmachine
[Javascript](http://nodejs.org/api/timers.html) example: ```javascript // setTimeout() or setInterval // timer + callback (event handler) // var myVar=setInterval(function(){myTimer()},1000); function myTimer() { alert("boo"); } ``` [EventMachine](http://eventmachine.rubyforge.org/EventMachine/Timer.html): ```ruby EM.set_timer(1) { do_thing } ``` [Python Twisted](https://twistedmatrix.com/documents/12.3.0/core/howto/time.html): ```python def runEverySecond(): print "a second has passed" l = task.LoopingCall(runEverySecond) l.start(1.0) # call every second ``` ] --- .left-column[ ## What is evented programming? - Common building blocks - Event loop ] .right-column[
Evented One process/thread Cooperative ? shared memory ? C (not parallel) Eventmachine
http://en.wikipedia.org/wiki/Event_loop AKA the main loop Redis's event loop: ```c // redis.c main() calls aeMain(server.el); void aeMain(aeEventLoop *eventLoop) { eventLoop->stop = 0; while (!eventLoop->stop) { if (eventLoop->beforesleep != NULL) eventLoop->beforesleep(eventLoop); aeProcessEvents(eventLoop, AE_ALL_EVENTS); } } ``` Twisted's main loop (twisted/internet/base.py) ```python def mainLoop(self): while self._started: try: while self._started: # Advance simulation time in delayed # event processors. self.runUntilCurrent() t2 = self.timeout() t = self.running and t2 self.doIteration(t) ``` ] --- .left-column[ ## What is evented programming? - Common building blocks - Reactor Pattern ] .right-column[
Evented One process/thread Cooperative ? shared memory ? C (not parallel) Eventmachine
http://en.wikipedia.org/wiki/Reactor_pattern ```ruby loop do IO.select([socket]) # socket is ready! # this will ALWAYS be instantaneous handle_socket end ``` when something is _ready_ to do work, call the dispatcher and do the work! ] ??? http://stackoverflow.com/questions/9138294/what-is-the-difference-between-event-driven-model-and-reactor-pattern --- .left-column[ ## What is evented programming? - Common building blocks - Proactor Pattern ] .right-column[
Evented One process/thread Cooperative ? shared memory ? C (not parallel) Eventmachine
http://en.wikipedia.org/wiki/Proactor_pattern Do the work _immediately_, pass a callback to it to be executed when it's done. ```ruby # more at github @methodmissing/eio def test_open_close_with_proc_cb closed = false ccb = Proc.new{ closed = true } cb = Proc.new do |fd| EIO.close(fd, &ccb) end EIO.open(__FILE__, &cb) EIO.wait assert closed end ``` Another example: Windows Completion Ports http://stackoverflow.com/questions/9138294/what-is-the-difference-between-event-driven-model-and-reactor-pattern ] ??? http://methodmissing.github.io/eio/ --- name:libev .left-column[ ## What is evented programming? - Common building blocks - Putting it together: Typical evented program ] .right-column[
Evented One process/thread Cooperative ? shared memory ? C (not parallel) Eventmachine
Gory details of what the libev loop (http://doc.dvgu.ru/devel/ev.html#synopsis) does:
] --- .left-column[ ## What is evented programming? - Common building blocks - Putting it together: Typical evented program ] .right-column[
Evented One process/thread Cooperative ? shared memory ? C (not parallel) Eventmachine
A simplified version of most event loops: ```ruby loop do process_events_on_the_queue # process_timers, handle_io, handle_signals, etc wait_for_events_and_enqueue end ``` queue == dispatcher concept ] --- name: proscons .left-column[ ## Evented Programming ] .right-column[
Evented One process/thread Cooperative ? shared memory ? C (not parallel) Eventmachine
## Pros - Avoid polling - CPU bound vs IO bound - Don't do what you don't need to do - Expanding your horizons (very different paradigms) - Scales well vs spawning many threads (caveat) ## Cons - You block the event loop, all goes bad - Program flow is "spaghetti"-ish - Callback Hell - Hard to debug, you loose "the stack" - Closures/First class functions - Rely heavily on state ] --- .left-column[ ## Beyond C10k ] .right-column[
Evented One process/thread Cooperative ? shared memory ? C (not parallel) Eventmachine
## Sidenote: C10M http://highscalability.com/blog/2013/5/13/the-secret-to-10-million-concurrent-connections-the-kernel-i.html http://c10m.robertgraham.com/p/manifesto.html http://c10m.robertgraham.com/2013/02/wimpy-cores-and-scale.html http://www.youtube.com/watch?v=D09jdbS6oSI ] --- template:inverse # Conclusions --- class:center,middle .left-column[ ## Conclusion ] .right-column[ ## All the things aren't black and white ![wrongright](images/black_white.jpg) ] --- class:center,middle .left-column[ ## Conclusion ] .right-column[ ## All the things aren't black and white ![wrongright](images/black_white.jpg) ] --- .left-column[ ## Use the best tool ### Some examples ] .right-column[ ### Threads/Locks: - Implement other models - Simple programs ### Actor model: - Facebook chat application, Ericson AXD 301 switch, - telephone, RabbitMQ: messaging system, - EJabberd XMPP chat, - SMS systems (WhatsApp uses Erlang) ### CSP (golang): - https://gist.github.com/ungerik/3731476 ### Evented Model: - Your Browser ] ??? Actors: Lots of entities sending messages to each other Evented: Lots of idle waiting for external event to happen (keyboard) http://www.slideshare.net/drorbr/the-actor-model-towards-better-concurrency --- .left-column[ ## Conclusion ] .right-column[ ## USE THE BEST TOOL FOR THE JOB ![tool](images/tool.jpg) ] --- .left-column[ ## Conclusion ] .right-column[ ## Keep on learning ![expand](images/expand.png) ] --- name: last-page template: inverse ## That's all, folks. ![thanks](images/thanks.png) Slideshow created using [remark](http://github.com/gnab/remark). --- name: questions template: inverse ## Questions? (Is there time?!) Slideshow created using [remark](http://github.com/gnab/remark). --- name: resources .left-column[ ## resources: ] .right-column[ - OS mechanisms http://stackoverflow.com/questions/3324643/processes-threads-green-threads-protothreads-fibers-coroutines-whats-the - Concurrency vs Parallelism http://blog.golang.org/concurrency-is-not-parallelism http://en.wikipedia.org/wiki/Flynn%27s_taxonomy - Cooperative http://www.igvita.com/2009/05/13/fibers-cooperative-scheduling-in-ruby/ http://masanjin.net/blog/fibers - Message passing/Channels http://en.wikipedia.org/wiki/Message_passing#Synchronous_versus_asynchronous_message_passing http://www.dalnefre.com/wp/2010/07/message-passing-part-1-synchronous-rendezvous/ http://clojure.com/blog/2013/06/28/clojure-core-async-channels.html (async channels) ] --- - Seven concurrency models in seven weeks (book) http://pragprog.com/book/pb7con/seven-concurrency-models-in-seven-weeks - Producer Consumer http://en.wikipedia.org/wiki/Producer%E2%80%93consumer_problem - Evented https://gist.githubusercontent.com/sandal/3612925/raw/315e7bfc5de7a029606b3885d71953acb84f112e/ChatServer.rb broken link taken from https://practicingruby.com/articles/event-loops-demystified http://doc.dvgu.ru/devel/ev.html#synopsis (libev) http://www.slideshare.net/simon/evented-io-based-web-servers-explained-using-bunnies - IO types http://www.ibm.com/developerworks/library/l-async/ - Async vs Sync https://gist.github.com/jamesob/9548827 - Good select/epoll explanation (nelson elhage) http://www.quora.com/Network-Programming/How-is-epoll-implemented http://www.quora.com/Network-Programming/How-is-select-implemented --- - CSP http://www.igvita.com/2010/12/02/concurrency-with-actors-goroutines-ruby/ http://www.usingcsp.com/cspbook.pdf http://assets.cs.ncl.ac.uk/seminars/224.pdf http://www.cs.pomona.edu/~kim/cs334/s00/Lectures/Lec23/sld031.htm http://en.wikipedia.org/wiki/Communicating_sequential_processes#Comparison_with_the_Actor_Model - Go https://www.youtube.com/watch?v=f6kdp27TYZs http://tour.golang.org/#1 http://joneisen.tumblr.com/post/38188396218/concurrency-models-go-vs-erlang - Actors http://www.slideshare.net/mperham/actors-and-threads http://learnyousomeerlang.com/content - STM http://stackoverflow.com/questions/209751/any-real-world-experience-using-software-transactional-memory http://www.youtube.com/watch?v=tYRIg4M5xNM http://book.realworldhaskell.org/read/software-transactional-memory.html --- - Video "Erlang the movie" http://www.youtube.com/watch?v=uKfKtXYLG78 - C10k? C10M: http://c10m.robertgraham.com/p/blog-page.html http://highscalability.com/blog/2013/5/13/the-secret-to-10-million-concurrent-connections-the-kernel-i.html https://news.ycombinator.com/item?id=7180672
A talk about concurrency patterns boiled down. An online slideshow of 'Such blocking very concurrency, wow' given at ScaleConf.