Concurrency is not Parallelism by Rob Pike

you if you looked at the programming languages of today you probably get this idea that the world is objectoriented um but it's not it's actually parallel um you've got everything from the lowest

level like multicore machines and up through networking and so on so but it gets all the way up to users who knows planets the universe there's all these things that are happening simultaneously

in the world and yet the Computing tools that we have are really not very good at expressing that kind of worldview and that seems like a failing but we can fix

that if we understand what concurrency is and how to use it now I'll assume that most of you at least heard of the go programming language is just what I've been working on at Google the last few years and go is a concurrent

language uh which means that it has some things in it to make concurrency useful like it's got the ability to execute things concurrently the ability to communicate between things that are

executing concurrently and it's got this thing called a SEL statement which is a multi-way concurrent control switch if that doesn't make any sense to you yet don't worry but when we announced go

which was about 2 years ago all these uh programmers out there said oh concurrent tools I know what to do I can run stuff in parallel yay uh but that actually isn't true concurrency and parallelism

are not the same thing it's a commonly misunderstood problem and I'm here to try to explain why and to show you that concurrency is actually better what would happen to these people who were

confused was they take a program they'd run it on more processors and it would get slower and they think this is broken it doesn't work I'm going away um but what was really broken was the worldview

and I hope I can fix that uh so what is concurrency well concurrency as I'm using it and as it's intended to be used in the computer science world is a way to build things it's the concurrent it's

a composition of independently executing things typically functions but they don't have to be and we usually Express those as the the interacting processes and by process I don't mean a Linux

process I mean the sort of General concept that embodies threads and co- routines and processes the whole thing so think in the most abstract possible sense so it's the composition of independently executing processes

parallelism on the other hand is the simultaneous execution of multiple things possibly related possibly not and if you think about it in sort of a general handwavy way concurrency is

about dealing with a lot of things at once and parallelism is about doing a lot of things at once and those are obviously related but they're actually separate ideas and there's a little confusing to try to

think about them uh if you don't have the right toolkit so one is really about structure concurrency and one is about execution Paralis and I'll show you why those are important so concurrency is a

way to structure a thing so that you can maybe use parallelism to do a better job but parallelism is not the goal of concurrency concurrency goal is is a good structure so here's an analogy you

might be familiar with if you're running an operating system it might have a mouse driver a keyboard driver display driver network drivers whatever else and those are all managed by the operating system as independent things inside the

kernel but those are concurrent things they aren't necessarily parallel if you only have one processor only one of them is ever running at a time and so there's a concurrent model for these IO devices

but it's not inherently parallel it doesn't need to be parallel whereas a parallel thing might be something like a vector dot product which you can break down into microscopic operations that you execute on some fancy computer in

parallel very different idea not the same thing at all so in order to make concurrency work though you have to add this idea of communication which I'm not going to focus on too much today but you'll see a little bit about it so

concurrency gives you way to structure a program into independent pieces but then you have to coordinate those pieces and to make that work you need some form of communication and Tony in 19 1978 wrote a paper called communicating

sequential processes which is truly one of the greatest papers in computer science and if you haven't read it if anything out of this talk SNS in is that you should go home and read that paper it's absolutely amazing but based on

that a lot of people with lesser Minds have followed and built tools to use these his ideas into concurrent languages like llang is another one that's great go has has some of these ideas in it but the key points are all

in that original paper with with a couple of minor exceptions which I'll I'll come up to but look this is all way too abstract uh we need Gophers so let's get some Gophers going

here's a real problem we want to solve okay we have a pile of ancient obsolete manuals say the C++ 98 manuals now that C++ 11 is out or maybe it's a C++ 11

books and we don't need them anymore whatever point is we got to get rid of them they're taking up space so we have a gopher whose job is to take the books from one pile and move them into the incinerator and get rid of them okay but with only one gopher it's going to take

a long time if it's a big pile and also Gophers aren't very good at moving books although we've given them a cart um so let's put another gopher in the problem except he's not going to get any better right because he needs the tools and

this this is kind of pointless we need to give him all the parts he needs in order to do this so This gopher needs not only the ability to to be a gopher but he also needs the tools to get the

job done so let's give him another cart now that's going to go faster we're definitely going to be able to move books quicker with two Gophers pushing the carts but of course there may be a little problem because we're going to have to synchronize them they can get stuck at the incinerator at the book

pile getting each other's way running back and forth so they're going to need to coordinate a little bit so you can imagine the Gopher sending s little Tony messages saying here here I am I need space to put the books in the

incinerator or whatever it is but you get the idea this is silly but I want to make it really clear these ideas are not deep they're just they're just good okay well how do we make them go faster well

we double everything we put two Gophers in and we double the the pile uh the piles and the incinerators as well as the goers and now we can move twice as many books in the same amount of time

that's parallel right but think of it instead of parallel as really the concurrent composition of two goer procedures moving books so concurrency is how we've expressed the problem these

two this this gopher guy can do this and we paralyze it by instantiating more instances of this gopher procedure and that's called the concurrent composition

of processes or in this case Gophers now um this design is not automatically parallel because sure there's two Gophers but who says they both have to

work at the same time I could say that only one gopher is allowed to move at once which would be like having a a single core computer and the design is still concurrent and correct and nice but it's not intrinsically parallel

unless I can make both those Gophers move at once that's when the parallelism comes in having two things executing simultaneously not just having two things okay that's a really important model but once we've decided that we

understand we can break the problem down into these concurrent pieces we can come up with other models so here's a different design okay now we got three Gophers on in the in the picture it's the same pile of books the same

incinerator but now we've got three Gophers right there's a gopher whose job is just to load the cart there's a job there's a gopher whose job is just to carry the cart and then presumably return the empty back again and then

there's a gopher whose job is to load the incinerator so three Gophers it's going to go faster might not go much faster though because they're going to get blocked you know the cart with the books is going to be in the wrong place and there's time to bring the Gopher

running back with the Mt where nothing useful is getting done with the cart so um let's clean that up by having another go for return the empties okay now this is obviously silly right but I want to

point something fairly profound that's going on here this this version of the problem will actually execute better than this problem this guy even though we're actually doing more work by having

another goer running back and forth in here so once we've got this concurrency idea we're able to add Gophers to the picture and actually do more work but make it run faster because the

concurrent composition of better managed pieces can actually run faster and it's pretty unlikely that things will work out just perfectly but you could imagine that if all the Gophers were time just right and the PS were just right and

they knew how many books to move at a time this thing could actually keep all four Gophers busy at once and it could in fact move four times faster than our original version unlikely but I want you to

understand that it's possible so here's an observation that's really important and it's kind of subtle we improve the performance of this program by adding a concurrent procedure to an existing

design design we actually added more things but the whole thing got faster and if you think about it that's kind of weird it's also kind of not weird because you added another gopher and Gophers do work but if you forget the

fact that he's a gopher and think of it as just adding design adding things to the design can actually make it more efficient and that parallelism can come from better concurrent expression of the

problem it's a fairly deep Insight that doesn't look like it because there are gophers involved but that's okay um so we have four concurrent procedures running here right there's a gopher that loads things into the cart there's a

gopher that takes the cart and TR trucks it across towards the incinerator there's another gopher who's unloading the carts contents into the incinerator and there's a fourth gopher who's returning the empty carts back and you

can think of these as independent procedures just running as independent things completely and we just compose those in parallel to construct the entire program solution but that's not

the only way we could do it here's a completely different design sorry not complet we we can here's a same design made more parallel by putting another pile of of books another incinerator and four more Gophers but you see the key

point is here we're taking the idea that we have how we break the problem up and once we understand it its concurrent decomposition we can actually paralyze it on different axes and get better

throughput or or not but at least we understand the problem in a much more fine grain way we have control over the pieces in this cases if we get everything just right we've got eight Gophers working hard for us burning up

those C++ manuals um or maybe there's no paralyzation at all who says that all these Gophers have to be busy at once I might only be able to run one gopher at a time in which case this design would

only run at the rate of a single gopher like the original problem and the other seven would all be idle while he's running but the design is still correct and that's a pretty big deal

because it means that we don't have to worry about parallelism when we're doing concurrency if we got the concurrency right the parallelism is actually a free variable that we can decide just how many go goers are busy or we could do a

completely different design for the whole thing let's let's forget the old pattern put in a new pattern and we'll have two Gophers in the in the in the story but instead of having one gopher carried it all the way from the pile to

the incinerator we put a staging dump in the middle so the first gopher carries the books to the to the dump drops them off runs back gets more the second guy sits there waiting for cart for books to

arrive to the pile takes them from there moves the incinerator and if you get this right you got two goer procedures running but they're kind of different procedures they're kind of the same but they're subtly different they have slightly different parameters but if you

get this system running right at least once it's started uh it can in fact in principle run twice as fast as the original even though it's a complet different design in some in some sense

to the original one but of course once we've got this composition we can go another way we can paralyze the usual way run two versions of this whole program at once and double again now we

got four golers maybe up to four times the throughput or we could take a different way again and uh put the staging Pile in the middle into the original concurrent multi-

gopher problem so now we got eight Gophers on the Fly and books getting burned at a horrific rate but that's still not good enough because we can paralyze on another dimension and Go

full on so here's 16 Gophers moving those books to the burning pile and it obviously this is is very very simplistic and silly but it's got Gophers in it so that makes it good um

but I want you to understand that conceptually this this is really how you think about running things in parallel you don't think about by running in parallel you think about how you break the problem down into independent

components that you can separate and understand and get right and then compose to solve the whole problem together so what does this all mean well first of all there are many ways you could do this I showed you just a couple

if you sit there with a Sketchbook you can probably come up with 50 more ways to have gopher move books there's lots of different designs they're not necessarily all equivalent but they can all be made to work and you can then

take those concurrent designs and refactor them rearrange them scale them in different dimensions to get different abilities to process the problem and it's nice because however you do this

the correctness of your algorithm for doing this is easy there's really it's not going to break I mean they're just Gophers but um you know the design is intrinsically safe because you've done

it that way however it's this is obviously a stupid problem this has no bearing on real work well actually it does because if you take this problem and you change the book pile into some

web content you change the Gophers into CPUs you change the cart to the networking or the marshing code or whatever it is you need to run to move the data and then the incinerator is the web proxy or browser whoever you want to

think about the consumer of the data you've just constructed the design for a web serving architecture and you don't probably don't think of your web serving architecture as looking like that but

the fact this is pretty much what it is right and you can see by substituting the pieces this is exactly the kind of designs that you think about and when you talk about things like proxies and forwarding agents and and buffers and

all that kind of stuff uh scaling up more instances they're on this drawing they you just don't think of them that way so they're not intrinsically hard things to

understand if Gophers can do it so can we right so um let me now show you how to use these ideas a little bit in building things with go now I don't I'm not going to teach you go in this talk I

hope some of you know it already I hope lots of you go and learn about more uh more about it afterwards but I'm going to try to teach you a little tiny bit of go and then hope the rest kind of gets absorbed as we as we do it so go has

these things called go routines which you can think of as being a little bit like threads but they're actually different and I rather than go into the details of how they're different let's just say what they are so let's say we

have a function that in this case takes two arguments if we call that function our in our program then we wait for the function to complete before the next statement executes that's very very familiar you all know that but if

instead you put the keyword go before you call that function then what happens is that function starts running but you get to run right away at least conceptually not necessarily remember concurrency versus parallel but

conceptually your program keeps running while f is off here doing his thing right and you don't have to wait for the F to return and if you that seems confusing just think of it as being a lot like the Amper sand in the Shell so

this is like running F Amper sand off in the background okay now what exactly is a go team well they're kind of like threads right because they run together uh they're in the the same address space

within a program they are at least but they're much much cheaper uh it's pretty easy to to make them and they're very cheap to to create and then they get multiplexed dynamically onto operating system threads as required so you don't have to worry about scheduling and

blocking and so on the system takes care of that for you and when a when a go routine does need to block like doing a read system call or something like that no other go routine needs to wait for it they're all scheduled dynamically so they feel like threads but they're a

much much lighter weight version of them and it's not an original idea other languages and systems have done things like this but we we gave them our own name to make it clear what they are so we call them go routines okay now I

mentioned we have to communicate between these things right so to do that we have these things in go called channels which are like a little bit like pipes in the Shell but they have types and they have other nice

properties which we're not going to go into here today but here's a fairly trivial example we create a timer channel uh and say it's a Channel of time.time values and then we we launch

time.time values and then we we launch this this uh function in the background that we sleeps for a certain amount of time delta T and then sends on the timer

channel the time at the at that instant timer time. now and then the other

timer time. now and then the other process because the other go routine because this one was launched with a go statement can doesn't have to wait it can do whatever it wants and when it's ready to to hear that the other guy is

completed he says I want to receive from the timer Channel whatever that value is and the that go routine will block until there's a value to be delivered and once it is completed that will be get get set

to the time at which the other go routine completed trivial example but everything you need is in that one little slide and then the last piece is a thing called select and what it does is it lets you

control your program's Behavior by listening to by looking at multiple channels at once and seeing who's ready to communicate and you can decide to rate in this case between channel one or channel two and the program will behave differently depending on whether channel

one or channel two is ready in this case if neither's ready the default clause will run which is me lets you sort of fall through if nobody's ready to communicate if the default clause is not present in the select then you'll wait until one or the other of the channels

is ready and if they're both ready the system will just pick one randomly so this this will come up a little later but it's it's pretty much like a switch statement but for communications and if you know D's guarded commands it should

seem fairly familiar now I said go supports concurrency and I mean it it really supports concurrency it is routine in a go program to create thousands of go routines and we are once

debugging actually live at a conference uh uh go thing that was running in production that created 1.3 million go routines and had something on the neighborhood of 10,000 actually active at the time we were debugging it and to

make this work of course they have to be much much cheaper than threads and that's kind of the point so they're not free there's allocation involved but not much and they grow and Shrink as needed and they they're sort of well managed

but they're very very cheap and you can think about them as being you know as cheap as Gophers uh you also need closures I showed you a closure sort of under the covers before um here's just proof that

you have them in the language because they're very handy in concurrent expressions of things to create nons procedures so you can create a a function that here in this case composes a couple more functions returns a

function it's just to show that it works and and their real closures Ino so let's use these elements to build some examples and I hope you'll learn a little bit of concurrent go programming

by osmosis which is the best way to learn uh so let's start by launching a demon um you can use a closure here to wrap some background operation you want done but not wait for it so in this case

we have two channels input and output and for whatever reason we have to deliver input to Output we but we don't want to wait until the copying is done so we say go funk for a closure and then have a for Loop that just reads the

input values and writes them to the output and the four range claws in go will drain the channels so run until the Channel's empty and then exit so this

little burst of code uh just drains the channel automatically and does it in the background so you don't have to wait for it and you has a little bit of boiler plate there but you get it's not too bad and you get used to it um Let Me Now

show you a very simple load balancer a very simple one and if there's time which is I'm not sure there will be I'll show you another one um but this is a simple one so imagine you have a bunch of jobs that need to get done and we've

abstracted them away here or maybe concretize them into a work structure with three integer values that you need to do some operation on so worker tasks what they're going to

do is compute something based on these values and then I put a sleep in there so that there's we guaranteed that we have to think about blocking because this this worker task May block an arbitrary amount of time and way we

structure it is we have the worker task read the input channel to get work to do and have an output channel to deliver the results so those are the arguments to this function and then in the loop we

range over the input values doing the calculation sleeping for some essentially arbitrary time and then delivering the output to the respon to the the output to the guy who's waiting so we have to worry about blocking so so

that's got to be pretty hard right well there's the whole solution um the reason this is so easy is that the channels and the way they work along with the other elements of the language let you express

these concurrent things and compose them really well this what this does is creates two channels an input Channel and an output Channel which are the things connected to the worker they're all reading off one input Channel and

delivering to one output Channel and then you just start up some arbitrary number of workers notice the go clause in the middle there all these guys are running concurrently maybe in parallel and then you start another job up that

says generate lots of work for these guys to do and then you hang around in this call function call receive lots of results which will read the values coming out of the output channel in the order that they complete and because of

the way this thing is structured whether you're running on One processor or a thousand the job will run correctly and completely and we use the resource as well it's all taken care of for you and

if you think about this problem it's pretty trivial but it's actually fairly hard to write concisely in most languages without concurrency concurrency makes it pretty compact to do this kind of

thing and more important it's implicitly parallel although not you don't have to think about parallelism if you don't want to but it also can scale really well there's no synchronization or nonsense in there num workers could be a

huge number and the thing would still work efficiently and the tools of concurrency therefore make it easy to build these kind of solutions to fairly big problems uh also notice there was no locking no mutexes all these things that

people think about when they think about the old concurrency models they're just not there you don't see them and yet this is a correct concurrent and parallelizable algorithm with no locking

in it that's got to be good right um but that was too easy so let's see how we doing yeah I got I got time to do the harder one this is a little trickier but it's the same basic idea but done much more realistically so imagine we have a

load balancer that we want to write that's got a bunch of requesters generating actual work okay and we want we have a bunch of worker tasks and we want to distribute all these requesters

workload onto an arbitrary number of workers and make it all sort of load balance out so the work gets assigned to the least lightly loaded worker so you can think that the workers have may have large amounts of work they're doing at

once it's not just one at a time they may be doing lots and there's lots of requests going on so it's a very busy system this could be maybe on one machine which is how I'm going to show it to you but you could also imagine that some of these these lines represent

network connections they're doing proper load balancing architecturally the design is still going to be safe the way we do it so the what a request looks like is very different now we have some

arbitrary function closure if you like that represents the calculation that we want to do and we have a channel on which we're going to return the result now notice a channel is part of the

request in go unlike a lot of the other languages like erlang the channel idea is there and it's a first class value in the language and that allows you to pass channels around and they're kind of like

file descriptors in the sense that if you have the channel you can communicate with someone but any no one with anyone who does not have the channel is not able to so it's like you know being able to pass a phone call to somebody else to

do or to pass a file descriptor over a file descriptor it's pretty a pretty powerful idea so the idea is you're going to send a request with a calculation to do and a channel on which

to return the result once it's done so what here's an artificial but somewhat illustrative version of the requester uh what we do is we we have a

Channel of requests that are coming in and we're going to generate uh stuff to do on that work channel so we make a channel which is going to go inside each request to come back to us for the

answer we do some work which I've just represented here is sleeping who knows what what it's actually doing um and then you send on the work Channel a request object with the function you

want to calculate and whatever that is I don't care and a channel on which to send the answer back and then you wait for the on that channel to get the result to come back and once you've got that you probably have to do something

with the result so this is just something generating work at some arbitrary rate it's just cranking out results but it's doing it by communicating on Channels with with inputs and

outputs uh and then the worker it's which is on the other side of this picture remember we've got requesters oops we've got requesters delivering data to the balancer which is the last thing I'm going to show you and workers on the right and what the workers have

in them is a channel of incoming requests and then a count of pending tasks and which is going to represent the load that that worker has the number of tasks he's actually got busy and then

an index which is part of the Heap architecture which'll show you in a second so then what the worker does is receive work from his request or his request Channel which is part of the

worker object uh call the function on the worker side so you pass it request I guess from your point pass the actual function from the requester through the balancer into the worker he does the

answer and then he returns the the answer back on the channnel now notice that unlike lot of other load balancing architectures the channels from the worker back to the requester do not go through the load balancer once the load

once the requester and the worker are connected the bouncers is out of the picture and the worker and the request are talking directly and that's because you can pass channels around inside the the the system as it's

running okay uh and then if you want to you could also put a go routine inside uh put a go statement inside here and just run all these requests in parallel on the worker it would work just fine if you did that but I that's enough going

on at once already okay and then the balancer is kind of magical uh you need a pool of workers and you need some balancer object you're going to put the balancers methods on and that includes a pool and then a

single done Channel which is how the workers tell the balancer that they' finished their most recent calculation so then the balancer is pretty easy what it does is it just forever does a select

statement waiting either for more work to do from a requester in which case it dispatches that request to the most likly loaded worker or a worker tells him he's done in which case you update

the data structure by saying the balancer is that worker has completed his task so it's just a simple two-way select uh and then we just have to implement these two functions and to do

that we actually what we actually do is construct a heap uh I'll skip that bit it's not very exciting you'll get the idea um dispatch all dispatch has to do is grab the least load of worker which

is a standard priority que implementation on a heap so you pull the most lightly loaded worker off the Heap you send it the task by writing the request to its request Channel now you increment the load because he's got one

more guy you know about and that's going to in influence the the loading distribution and then you push it back onto the same spot on the Heap and go and that's it you've just dispatched it you've updated the data structure and

that's what four executable lines of code and then the completion task which is when the work is finished you've got to do the sort of inverse you there's one F guy on this workers CU so you

decrement his pending count you pop him from the Heat and you put him back on the heat and that'll put him back fact where belongs in the priority que and that's a complete implementation of a semi-realistic load balancer but the key

Point here is that the data structures are using channels and go routines to construct this concurrent thing and the result is scalable it's correct it's

very simple it's got no explicit locking and yet the architecture just sort of makes it all happen and concurrency is therefore enabled parallelism intrinsic in this thing and you can actually run this program I have this is all

compilable and runable um and it works and it does low balancing per and that things all stay at exactly uniform load module quantization it's pretty good and you can of course have I never said how

many workers there are or how many requesters there are there could be one of each and 10 of the other or a thousand of each or a million of each the scaling still works and it still behaves

efficiently one more example um which is somewhat more uh surprising but it fits on a single slide so it's a nice one to finish imagine you had a a replicated database so you got a database with with

uh the same data in each of multiple uh what we call shards at Google same same instance right and what you want to do is deliver a quest to all of the

databases and a query and get back the result but they're all going to be the same you're using this to go faster by picking the first guy answer as first guy to come back with the answer is the one you want so if one of them's down or

disconnected or something you don't care because somebody else will come in so here's how to do that this is the full implementation of it um you have some array of connections and some query you

want to execute um you create a channel uh which is buffered to the number of elements the number of replicants inside this

replicas inside the the query database and then you just run over all of the connections to the databases and for each one of them you start a go routine

up to deliver the query to that channel to that database and then get the answer back by this due query call and then deliver the answer to the single channel

that that's holding the result for all of these guys and then after you've launched them all you just wait on the bottom line there and we wait for the the first guy that comes back on that channel is the answer you want you

return it and you're done and the thing is this looks like a toy and it kind of is but it's actually a complete correct implementation the one thing that's Miss is is clean tear down you want to sort of shut tell the servers that haven't

come back yet when you've got an answer that you don't need them anymore and you can do that it's it's more code but not an unreasonable amount more but then it wouldn't fit on the slide so I just want to show you this is a fairly

sophisticated problem to write in a lot of systems but here it just sort of Falls naturally out of the architecture because you've got the tools of concurrency to represent a fairly large

distributed complex problem and it works out really nicely so I 5 Seconds left that's good uh conclusion concurrency is powerl but

it's not parallelism but it enables parallelism and it makes parallelism easy and if you if you get that then I've done my job so if there if you want to read more there's a bunch of links

here uh there's a golang.org has everything about go you want to know uh there's a nice history paper that Russ put together that's linked there uh I gave a talk a few years ago that led up to us actually doing go which you might

find interesting uh Bob Harper at CMU has a really nice uh blog posting called parallelism is not concurrency which is very similar to the idea that concurrency is not parallelism but not quite uh and then there's a couple other

things the most uh surprising thing on this is the concurrent power series work that Doug math my old boss at Bell Labs did which is an amazing amazing paper but also if you want a complete different spin on it the last link on

the slide is to another language called sawal which I did at B at at Google shortly after coming there from Bell labs and it's remarkable because it is incredibly parallel language but it has

absolutely no concurrency and by now I think you might understand that that's possible so thanks very much uh for listening and thanks to herok for

inviting me and uh I guess it's time to have some drinks or something