Keynote: Taming Concurrency

funconf 2013, Marius Eriksen: Keynote: Taming Concurrency

Recording: funconf 2013, Marius Eriksen: Keynote: Taming Concurrency

so so this is the first silicon valley skull symposium welcome uh welcome to intel thanks to intel for hosting us uh thanks for all the sponsors who made this possible the volunteers uh who helped us here i'm just just gonna say a few words about the conference it's be it's gonna be a whole day and a few words about the history of this so uh this is a scala conference it's uh basically uh scholar meet up in the city uh i found this scholar for startups two years ago then we merged with scala and this is basically unified scholar meetup in the city there is a fellow meet up now called scala bay which used to be called base and we exchanged organizers with led with the organizer so essentially we have a unified community and we work very well with all the companies using scala with typesafe speakers so basically lily maseri she is a skull community organizer she did two scalathons in philadelphia and had moved to the area in winter and had the idea to have the same thing here and started this thing and at some point basically she did a personal search and needed to take some time off uh to explore herself and basically we had to pick it up and we decided to do this in the rest of scholar so the the option was either to cancel it or to keep going forward and the time was pretty short and the date was already set and essentially uh we decided to do this and essentially because of the meet up because of all the speakers who did their presentations in the precision years i learned on sunday that i have to put together the program and by wednesday i had 15 speakers and in a few days i had 20 speakers so basically the program came together together very quickly we arranged everything and essentially i think it testifies to the power of meetup uh and we're really thankful to all the speakers uh and meetup.com by the way is powered by scala uh so nathan the director of engineering of it is a known contributor to a lot of projects so that brings me to another theme of this conference the url is funcons.org right and the idea for funconf is something i had actually for a while uh it's a fun conference it's fun for functional in many senses because it's functional fp and it works uh and also it's fun right and if you look at a lot of speakers here i think they succeeded in an ultimate goal of i think an intellectual person they made the fun activity in the intellectual pursuit a profitable venture for them in the world right they basically found the synergy between what they like to do best uh and made it their job so what uh we have in mind for the next year is to expand this idea of fun conference uh to several more areas such as data mining uh social graph analysis and maybe some other areas and uh maybe extend uh functional programming languages coverage to some other fun languages such as closure so we're gonna think it through and but the whole idea and i think one of the themes here is this and if you look at some of the top people in nfp community i think you will notice right if you look at joshua if you look at rishiki you will clearly see that they're having fun they actually made a job for themselves doing what they love and hope that can be one of the themes here and ask everybody all the speakers who can to play with stuff and the rebels show how they do fun things uh right because essentially scala people usually cover out a little niche for themselves they start things as skunk works as side projects and then they sort of gradually move it into the mainstream and i think we're seeing this moment when scala is taking over is becoming the industrial vehicle for many companies i think the challenge for us is not to lose this spirit and really make keeps keep things fun and i think that's gonna really um keep the advantage uh keep the quality of the community um and basically that's that's a topic of the fun conference so again i want to thank our sponsors netflix and jason swartz he is one of the volunteers he's manning a desk outside or he's inside and he really was instrumental in helping with the site and getting this wonderful little veggies if you need help at any point ask one of us who holding this uh batch and the schedule is printed pick one up if you didn't i sent an email yesterday with the plan essentially we have two coffee breaks we have lunch at noon and it will be served inside so after this we will go to the training rooms which are back there and down the corridor there will be signs posted we have to basically stay on course it's a secured facility we can only be in these training rooms in the lobby or in the restrooms it will be signs for those so there are three training rooms there are three tracks and each room fits about 50 people and there is a common room for mingling and coffee and one of my main requests was that coffee is infinitely available so if it's not you have to ask me or one of the volunteers and have like we have catering folks helping out they have to replenish it right that's extremely important for us that coffee is available continuously uh so now i just want to ask lily to come up here and say a few words uh because of her that's that thing started really here all right can i speak loudly i can make up there you go i can just hold it hi can you hear me hi everyone uh yeah my name for the moment is lilly fox you probably knew me as ubi organized one and two so don't worry it's more awkward for you to me but uh you gotta put yourself in alexis shoes like two months ago when he gets his email on sunday night naturally so he wakes up this monday morning saying well you know i've decided i want to be a girl and i don't really have time to arrange this conference anymore but you know it'd be great if someone else could otherwise it's kind of handsome so we all owe like a huge debt of gratitude i only set up the venue and just a couple basic things all the food and sponsors had nothing to do with so i'll actually really put together something incredible and i just hope you all join me and thank you for that and actually it reminds me to uh mention that i think that's what it is very courageous it's also fits this idea of fun as something you do best you you know putting yourself and your personal project of yourself in front of jobs and deadlines i think it's it's a crazy thing to do it's very important and i really applaud this i think everybody should do this in the areas if you know if you find that you prefer scholar to ruby you stuck in the ruby startup actually what you should do is not to keep logging ruby but you should actually create a scala company and that's you know eventually what i have done so uh and i was you know uh stuck in a ruby place and the organized call of a startup's meetup and then eventually after a few iterations uh selected california startup and actually although scala team from versailles is here i think i get uh 10 seconds to say that we're hiring if you see any of the virtual guys we have our uniforms on uh talk to us and uh now uh our awesome keynote uh myris ericsson i think needs no introduction he is the creator of finagle uh when i talk to twitter folks they invariably say he's one of the best twitter engineers uh and uh that's a consensus from one basically everybody i talked to and uh we're very fortunate that we got marius as an advisor to reversal where we use all scala back end and we are seriously thinking of taking the whole twitter stack starting with uh finagle and then with mesas we have actually some talks in this conference which will help everybody to see how we can do this uh and everything he's done is extremely thoughtful i think he he he presents uh distributed systems uh view as a basically a new os a new computer he thinks about it structurally uh he basically systematically goes along the stack to to instrument all the pieces to provide uh profiling protocol features we need it and basically everything you can think about uh you need in a large distributed system he already thought of and actually not just that he works on it and he contributes to open source so so i think that's the ultimate achievement and we're gonna learn from mario's uh and uh uh now it's off to him well thanks again to alexi i think it's all right monica are you getting this is it are you getting the signal yeah all right because it's it's right here but it should be okay i'm also going to turn on screen recording for posterity which we've been asked to do there we go all right oh all right great so uh yeah thanks again to alexi for arranging this this conference it looks to be excellent uh i'm actually amazed that uh as many of you um as i actually ended up showing up this early um i i'm sure that we'll get more attendees as the day moves on so what i'm going to talk today talk about today is about concurrency and concurrent programming and why i i have sort of a long standing obsession with concurrent programming in particular and the central reason for that is that uh concurrency is sort of uh you know everywhere around us in what i consider sort of modern server software and uh concurrency in general has been notoriously difficult to to reason about um and to sort of reconcile with uh with programming languages and furthermore uh the kinds of tools that we consider state of the art so you know java utilizing current sort of threads and locks some of course things like that are really very primitive sort of nuts and bolts things they're very imperative in nature for one and they tend to compose very poorly and so it's very difficult to write robust good server software uh using what we considered there what the industry considers today's state-of-the-art tools and there's another sort of there's another thing which is that there's actually a really rich history of concurrent programming spanning all the way back to the 1960s which have gone somewhat ignored though not everywhere there are you know things like erlang and akka and so on that have sort of dug up different pieces of history but there's actually a lot more to it and so what i want to do is i want to effectively give you a little bit of a history lesson and then uh sort of explore how we might use the kinds of ideas that were developed in the 60s and 70s in our sort of modern practice and how in particular that fits into scala and scala historically has been very sort of fertile grounds for this there's everything from well from obviously actors from very early on which were taken from erlang and so on and so forth but a number of other sort of concurrency pools and primitives have been have have been existing in scholar for a long long time and of course part of that is because scholars sufficiently expressive language that you can create these dsls and things like that um and so you can effectively create sort of higher order languages on top of the base language so uh before i sort of get into uh into the rest of the talk i just want to make sure that we're sort of on the same page when when that when i say concurrency so briefly what i mean by concurrency is that you have a number of independently executing processes uh that communicate in some way so this can be over shared variables it could be over uh like yeah you know or a actor channel things like conditions and queues of course also count and what's really important is that these processes execute independently okay and furthermore we require non-determinism right and so what this means in particular is that every execution doesn't necessarily yield the same result for example if you have time dependence you have non-determinate non-determinism and that's a very very important property of modern server software if you have concurrency without non-determinism you're really talking about parallelism and that's not what i'm going to talk about today so so again why do we care so much about this well first of all most of sort of current practical server software uh interfaces with the world you don't decide uh when a request from a client arrives at your at your server uh you don't necessarily decide uh you know when a timeout from another system might trigger you don't necessarily decide how long a disc seek is going to take um and so our environment is sort of highly non-deterministic um and you can't really control it and this is sort of what gives rise to these tricky concurrency problems um another other interesting properties of our environment that are difficult to control are things like latency distributions uh and of course that uh that goes all the way down to things like our network fabric and our process architecture processor architecture so one way to view the sort of problem of why concurrent programming is difficult to do in the first place is that you know so our world as well as increasingly these days our hardware is highly concurrent but our languages are sort of inherently sequential we have semicolons and we say you know this happens and that happens you have a loop that's deterministic and the problem with concurrent programming is effectively trying to bridge these two worlds how do we use the sequential language to interface neatly with this concurrent world and to be able to express concurrent systems using these sequential languages and that's really what concurrent program is about and in particular if we don't understand or can't reason about uh how we go about constructing these sorts of systems we don't really stand much of a chance to have any sort of principled reasoning about our sort of modern server software so uh before i go on i want to sort of recall this quote from horror which i i think is uh at least to me as service sort of a guiding principle to the fb community in particular and he said well you can read it i'll read it for you there are two ways of constructing a software design one way is to make it so simple that there are obviously no deficiencies uh while the other way is to make it so complicated that there are no obvious deficiencies and uh in my mind this is uh this should really be like the slogan for the fb community right we try to create software that is just clearly correct right and tricky details like you know maintaining loop invariants and and dealing with uh you know instantiating and immediate data structures and so on uh we try to sort of relegate to implementation in the library language uh and try to really sort of surface the semantics of the program that we're working on and so to me uh this is sort of one of my guiding principles and so please keep those in mind as we um as we sort of explore some history and so what i'm going to do is i'm going to sort of take us through what i'll call four flavors of concurrent programming uh we'll start with just a little bit of review not not very much of the sort of imperative concurrent programming then we'll go and explore what might you consider a more sort of functional way of programming concurrent systems and after that we'll talk about uh what i'll i'll i'll call process oriented concurrent designs and so this is things like actors um and um and csp and so on which which we'll go into and then finally i'm going to talk about what i'll call channel oriented design which is a variation of the process-oriented design which gives rise to a lot of really really neat properties and i hope to spend sort of meat of the talk there and and particularly i'm going to i'm going to discuss what we call offer broker twitter which is a concurrent abstraction that services a lot of the good properties in what el what i call here channel oriented concurrent systems so first of all let's start with the imperative so uh before i uh you know before i sort of start um explaining why this is so horrible uh first of all the good things about java concurrency is that it really really brought multithreading to the mainstream and java also defined a really nice and simple shared memory model which helps in in a lot of cases and there's a lot of really good utilities and uh the problem however is that they're very sort of imperative in nature they're very nuts and bolts however they they map very very nicely onto the underlying hardware and the hardware properties and so as an implementation strategy they're great right but they're not always uh the best way to write application programs here's one of my favorite examples i'm sure a lot of you have written code like this now uh this is uh what's called a double double check blocking as sort of a pattern and in order to really understand why this works and why you have to do this at all it requires a really deep understanding of not only the java memory model but how that might interact with things like well in this case locks you have to worry here of course about well what happens if i call do something here under lock in this case um and uh you know are the deadlocks and so on and this style of programming is sort of notoriously difficult to to get right and it composes very poorly if i have a well-behaved code and you know in isolation like this i can't necessarily take that well-behaved code and integrate it with some other well-behaved code the result won't necessarily be well behaved right it gives rise to sort of unpredictable you know deadlocks um to uh and race conditions and and live locks and all these different things that are very very difficult to understand um there are some more tasteful what i'll call more more testable uses of um of the sort of standard uh java concurrency primitives uh one is for example maintaining state explicitly and so it's very very common to for example use the various atomic operations to maintain an explicit state machine and that can be a very very useful tool it's highly efficient and in many cases this is great in many cases this fits the problem very nicely and is the kind of pattern that you can use profitably now again the java concurrency model very much emphasizes effectively mapping nicely to the underlying hardware and while it does have a nice nice memory model that helps you out in a lot of cases the subtleties around the memory model and how it interacts with with the other concurrency constructs are often very subtle it it tends to be very prone to bugs and again as i mentioned it's very difficult to compose so the way i like to sort of think about these things is that these imperative tools are kind of mechanical in nature you you sort of you you have to specify well how do i go about doing a particular thing not only that but i have to say how do i do it with respect to my environment and the java memory model and the interactions between all the other agents in the system and so on and so forth whereas functional programming tends to be well called descriptive where instead of uh specifying exactly how you go about achieving a particular goal you are closer to just specifying the goal itself right not quite like to the extent of logic programming but closer to it right and so um that that's that's the kind of terminology i like to use for these are sort of things like mechanical versus descriptive so that was a short overview of the sort of current best practices java java concurrency so let's revisit what it might what it might mean to do functional concurrent programming so what i mean by functional hair is as a highlighted hair sort of emphasizing immutability composition is very very important and so is sort of being able to isolate at least somewhat various side effects and so when i say functional that's the kinds of things that i want to emphasize and highlight so there was a paper from the 80s called ice structure which give rise to what is now called data flow computing and so data flow computing is the sort of ability to take an existing program as specified sequentially and effectively just insert threads anywhere you like and the nice thing about about data flow computing is that you can insert threads anywhere and the semantics of the program remain exactly the same right and so this is what's called deterministic concurrency and i said before i wasn't really interested in deterministic concurrency uh the reason i'm showing this to you is will become clear in a second and in particular this requires you to operate in a language or with primitives that are determined in nature right like if i have like for example you can't have time dependence right because if i insert you know a thread spawn anywhere then if the scheduler decides to take longer in one run versus another you don't have time independence anymore and so you can't have uh non-determinate behavior but it's anyway an important way to think about how to sort of reconcile concurrent programming with functional programming and the basic idea is that you can sort of spawn off a subtree of your computation elsewhere and this also plays very nicely with the notion of graph reduction and so the way data flow uh languages uh the runtime is implemented it's effective to do a sort of concurrent graph reduction now there's actually a a dialect of scala which implements uh data flow programming it's called asthma this was presented at the scholar workshop this year and it works in the following way and so asthma effectively introduces just exactly one new construct which is um called thread here and anywhere you insert a thread you're telling the runtime that you may you know you may spawn off this computation in a new thread and what thread returns is just another value it's just it's not bound yet right and so this is how you would for example implement a concurrent version of mapping over a list in asthma and really the only difference between implementing it in a concurrent manner and a sequential manner is that you're inserting this thread operation for actually executing the function f right and so this to me sort of makes it obvious that yes this of course has to be determinate otherwise it wouldn't work and so on and so forth but it's also a very very nice way of sort of reasoning about or reconciling concurrent programming with functional programming you're just saying i'm just going to execute this thing asynchronously however the values themselves their types don't change it just happens that it's not yet bound and anytime i try to access that variable or value rather than binding i have to actually wait for that computation to to complete and as i mentioned this requires not only non-determination or determinancy but it also requires freedom from exceptions which can be problematic and there is there is some work in trying to sort of reconcile data flow programming with uh non-determinism and asthma which uh which uses a runtime called mozart um introduces notional ports which are effectively channels and the idea is that channels are the only source of non-determinism in your system and so what you can do to construct the system is to have these sort of independent pure parts that are sort of pure data flow programs connected by these dirty hoses that are non-deterministic and together you get a non-deterministic system but at least you can sort of easily reason about parts of it and you have a principal separation of non-deterministic parts versus the deterministic part however i posit that in modern you know server software basically any form of concurrency is non-deterministic and so this sort of quickly boils down to using ports only so this brings us to futures um and so futures are what i consider a compromise of data flow programming that allows you to embody non-determinism non-determinism and failures and so on and so forth the way to think about futures is that they're really just a container whose value is deferred right and so the operation that produces the value in this container is running asynchronously and the future itself you know is effectively a reference cell which which whose value is deferred and you can compose them in a declarative manner just like we do with collections right and so i'm not going to go uh very deeply into futures because they're kind of a sideshow in terms of this talk but here's an example of using futures which i think very neatly illustrates uh the kinds of things you can do with them and why they're very powerful for composing concurrent programs in a functional or sort of functional way emphasizing transform data transformations and so on and so in this example let's imagine that we have you know some trait page that represents a web page and it might have a method called links which gives us all the links on that webpage and i might have another method called fetch which given a url gives me a future of uh web page now if i was guaranteed that given a route i had a sort of pure dag then in fact this crawl method that i've defined here is completely accurate and it works well right and so the way to read the way to read this is the following well first you fetch a url you take the result of that and fetch all of the links you collect all of those into into one future that contains you know all all the various links so future collect is a combinator on future that turns a uh sequence of futures on uh to a future sequence of particular values uh and then your recurse right and so there's a lot of really nice um uh this sort of demonstrates a lot of really nice properties about futures first of all you can use them in a way that's very very declarative right uh in the sense that you're just saying well crawl the definition of crawl is just to well fetch and then sort of fetch recursively all of all the links of the page that you fetch that's kind of the definition of semantics of a crawl i haven't specified exactly how to go about this you know like having said well first fetch dust and allocate this intermediate array to which i'm going to stuff all the intermediate results and you know create a summer for that uh you know once it gets decremented to xero i'm going to uh you know proceed to the next step and so on and you sort of just specified what it means to crawl a page and that's very much in line with what i consider sort of good functional programming practices not only that but you've specified nothing about the runtime and so in fact the runtime itself is free to adapt to the situation at hand and this is something we use a lot in our rpc system finagle for example at twitter where finagle can for example determine well for this particular host i'm not going to have more than you know this many requests at a time for instance so i'm going to limit the concurrency of um you know of of this fetch to to get to to a given degree uh or i might decide to uh uh to uh scatter all the all the requests across a number of threads for example this is something that you can implement purely in the real in the runtime itself uh because you sort of express the meaning of the operation crawl not its mechanics right and this is very similar to having a sort of runtime that is a jet for example a jet can examine well actually this method indication is always the same and so i'm going to inline it you can do similar kinds of optimizations when you separate the runtime from how you specify these kinds of operations and that's very very powerful however futures aren't without problems and so futures present this very sort of ideal simple interface where you know the result of any operation is just some deferred reference to the result of that which which again may fail i can compose over failures however in real systems this can often be problematic in the in the given sense and so consider this example for example so i have again i'm just sort of using an http client i fetch a web page or some url rather and the result of that is represented by the future f in this case now within is a method on futures which gives me a new future which either fails within the given timeout or succeeds with the result of f right and so if f hasn't completed within one second in this case g is going to fail now the nice thing here is of course i haven't modified any of these futures i'm just expressing g as a combination of uh you know timeout and and another future um and uh it's it's sort of a pure immutable data transformation in that sense right i'm just getting a new thing that means a slightly different thing from f and uh let's say i now wait for the result of g in this case well if f takes longer than one second then g will fail with an exception and so i will you know in this case um the the print affair will throw will throw through an exception and the result is no longer needed right there's nothing in your system that has a reference to app anymore for example um and uh and because of the way i combine these two things i no longer need the result however uh the asynchronous operation that's doing the actual http fetch in this case is still going on right and so this can be problematic for example if um you have a uh a a server that becomes really slow and you're timing out most of the requests well now you might have a retry on top of that that doc piles more work onto that right and so this sort of pure this sort of pure notion of a future that is a sort of like immutable container uh over which you can do transformations kind of falls apart a little bit in real life because of things like resource management and so on and so that's kind of unfortunate uh that's that's a sort of a very concrete problem with with futures and basically what that boils down to is that the producer can the futures aren't a channel right they're just they're just a reference to uh some operation i might complete in the future and this completely divorces the notion of a producer and consumer right and in particular the producer doesn't know when a value is consumed or when a value is is no longer needed for example which can cause you know real problems in real service software and so on when you use this in the sort of pure fashion um and furthermore you can't really use futures because of their asynchronous nature to synchronize independent processes right so like for example imagine implementing a barrier you can't really implement a barrier using futures only right because you need the producer to know when you know a consumer has consumed a particular future and so on and so um while features are very very nice and present a very very simple uh interface um and and way of reasoning about these kinds of problems uh in reality it it turns out it's a slightly simplistic so this brings me to uh what i call process oriented um concurrency uh this is by the way uh tony horror of horologic fame and so on and uh concurrent concurrent programming as i mentioned before is really a quite a rich field and it started all the way back in the 60s and at the time uh people and dijkstra and so on were sort of mostly concerned about how to formalize concurrent programs and so logic sort of presented a way to reason about uh albeit in a tedious tedious way uh reasoned about sequential programs however horologic fell completely apart for concurrent programs because horlogic would then demand you to effectively examine every single possible overlapping of executions and so on and so forth and so that quickly fell apart and so um dykstra and horror in particular worked a lot on trying to figure out well how do we formalize concurrence you know how do we formalize concurrent systems that we can prove properties and variants and things like that of them and i find this a very neat way to sort of well first of all get a sense for how to sort of reduce a problem to its very essences but it also often also gives rise to um sort of actually useful constructs for implementations in particular we've done this before with functional programming lambda calculus was constructed for similar reasons so the first sort of seminal paper that that tackled concurrent programs was one from dykstra called guarded commands and guided commands were basically dijkstra's attempt to formalize and reason about non-deterministic programs and we sort of established that non-determinism is in this context uh effectively equivalent to concurrency and actually i'm going to show an example that shows very nicely why that is so what this did was basically say well i am going to define an extremely simple programming language that has two non-deterministic constructs um and the way i reason about this is i you know these these constructs maintain some sort of invariance and i you know define a sort of calculus on top of this over which i can reason about programs and so on um and again remember these are these are formalization constructs they're not meant to be sort of a service programming language but they highlight some important ideas so the first construct in dijkstra's got guarded commands was this the square bracket the square backer is called a choice operator and you can compose them the following way you can say well if x is greater than equal to y or y is rather if x is greater than equal to y then assign x to m if y is greater than or equal to x then assign y to m and so the first part here is the guard it's kind of like a predicate that determines whether or not the the second clause is eligible for execution but the composition is non-deterministic in the following sense so if there are multiple guard clauses that are that make the the following statement eligible for execution we pick one at random in this case and if there's just one we picked that if there's none we just follow through right and so basically this is uh this is like introducing a source of randomness non-determinism into your program now that's sort of interesting but things become really interesting when you put this in a loop and so the semantics of a loop are the following i'm going to execute the loop as long as there is at least one guard eligible for execution the semantics of individual choosings are the same and in this case for example i can implement a well a four slot sort in the following manner and by the time they're sorted then none of them are going to be true anymore none of the guard's going to be true they're going to fall through the interesting thing to me about this example is that this sort of describes every single you know like event loop scheduler for example this is a a sort of proto operating system scheduler where you have a number of conditions that can be true or false at any given time and you have to choose to execute one of them the semantics of the operator itself gives rise to non-deterministic interleaving right so i can't rely on one getting executed before the other and so forth so on and so forth and to me this is sort of the essence of concurrency so that extra terms is non-determinacy uh but really it's just concurrency right and uh and it's in this way that i consider the two concepts basically the same another interesting thing about uh guardia commands is that they completely separated the language from the environment and introduced the notion of a runtime like a runtime has to be there to pick you know randomly which uh which particular clause gets executed for a particular iteration for example and so that's that's another interesting theme that comes up as well so so dijkstra worked on garter commands and he sort of defined ways of formalizing about it and a few years later horror published an even more famous paper called communicating sequential processes and i think this one probably most people have heard of at least this is the famous csp paper and what csp did was to extend on guarded commands in the following way instead of just defining um a sort of a non-deterministic interleaving of loops and and and conditionals or explicitly define the notion of a process processes themselves are independent and sequential as i defined earlier on in the in the talk and in addition to processes hor defines what he called events and these events are effectively interactions between various processes so this can be you know sending a message or receiving a message it can be you know sharing some sort of condition variable and just like in the manner of functional programming horror defined a number of combinators over these processes so you can combine events and processes to give rise to other processes and so on and so forth and we're going to go through this very very briefly so first of all the kinds of events that exist in csp we're just going to treat we're just going to treat these two events for the for the purposes of this talk but basically you can send a value x to process p with the bank operator and receive a value y from the process p with a question mark operator and anybody that's done any sort of actor programming recognizes these operators immediately and in fact this is where where that syntax came from so the first way in which processes can be composed in csp is what's called prefix composition and so this is what in modern times we call a semicolon right and basically what this is is event a which is usually some sort of communication uh if that proceeds then we become process p right and so now i've defined a new process uh and so just as an aside this is how you might write this in scala right and so i might have some process p and some event a and i create a new process q by using the prefix combinator of a and p right and so i'm just creating a new process which has new semantics but it's composition in the same way right it's just doing this sort of operating over these immutable immutable data structures in this case and just creating composite processes in this case that have different behavior from the underlying ones and so i'm combining this event a with this process q and the semantics again is the following so the process q is the process which when event a happens it becomes process p it behaves behaves like process p another important composition that that um hor defined was interleaving and so if i write p uh triple uh triple whatever uh vertical line q that is now the process that behaves like both p and q at the same time right and so this is kind of like spine two threads now interesting things start to happen when you when you introduce choice composition and this is uh where core borrowed most heavily from dijkstra and so choice composition is the following the process which is defined by arop choice broq is the process that behaves either like p or q depending on which a or b is actually triggered which event actually happens right and so now i can create these composite processes which diverge in their behavior depending on what the environment is like at this at the same time and it's crucial to know these are mutually exclusive you know that exactly one of a or b happens as per the csp semantics and and this is really crucial this is a very very important point that these events are synchronous so that communication occurs only when one process names another process for sending and some other process names the same process for receiving right and so if i write p bank x that's not that's going to block effectively until somebody else executes p question mark y and just to really bring the point home uh here's how that might work uh let's assume that uh you know we're dealing with some sort of discrete time system each dot in this diagram is a tick of time and let's say i have two processes a and b and i get the uh pro i get i get the combined process which executes them both simultaneously by saying a triple line b um if process a says b question mark y a is blocked until process b says a bang one two three in this case right and so process a is saying well i want to receive some value from b and bind it to y and process b later on says well i'm going to send value one two three two um to a two a and this also works the other way right so if i try to send something and there's no receiver i also block and so when process b subsequently says a bank 333 b actually is blocked right until process a agrees to receive something from b so this is pretty simple but i really want to drive the point home because this is a very very important property which you'll see in a moment so the interesting thing is how synchronized synchrony in this case uh interacts with guards as we've seen in from dykstra and basically they um they interact in the expected way and so you can compose things that are guarded and as long as there are lots of things in your environment that want to communicate exactly one is selected and so for example this is how you might implement a summer for in csp and so a semi4 is some process which defines the value v which starts at zero if i receive a v message right from a in this case then i'm going to increment v by one and by the way this bracket construct with the um with the star just means repeat this forever right and so this is a process which just repeats that body forever and um and uh right so if i receive a v message then i increment v by one if i receive a p message and v is greater than zero so this v is greater than zero is a guard in this case then a decrement v by one and so what that means is that um process b can't grab the sum of four until process a has applied some amount of values right and so um this diagram is the same again imagine you have some sort of discrete time system each dot is a tick of time then process a might might ask s for uh islam in the summer for however it blocks at this time right because process b has not supplied at v a zero and so because of that guard b question mark p is not eligible right and some time elapses and process b supplies a v value that increments v plus one at that point in time the second class becomes eligible right and now a is unblocked right and so the the crucial thing here is that in some way um each of the classes of this non-deterministic um or this this choice operator is a sort of latent event that is waiting in your environment right it doesn't it doesn't actually trigger until uh it's eligible to ask per the guards um and then so on and so forth uh now um process b might supply another v and uh that means that the next time that process a tries to get a p uh he doesn't block anymore right and so the crucial thing here is that these events are these sort of latent things that your environment controls and their synchronous and this is a really really big idea uh and and i'm i hope to try to convince you there's nothing else you remember from this talk i'm going to remember about events um and i hope to in some subsequent examples show you why and i'm going to show you scala now not some sort of obscure outdated syntax but basically the environment is responsible for well you have a bunch of events in the environment you can think of it as a big sort of chemical soup and the environment itself is responsible for sort of matching events that are sort of eligible for rendezvous subject to the garage that they specify and this combination turns out to be extremely powerful in fact you can think of this as the environment effectively during a transaction for every time tick right on your behalf so if you remember nothing else remember dijkstra or guards and events so as a short aside actors are also structured around you know actors are familiar to to scholar programmers there also are structured around processes um and i've heard from many sources actually that um you know they share lineage with csp that's actually not true they come from carl hewitt which is actually predate csp and in particular actors are asynchronous and so they don't have you know things like guards um and uh they don't allow you you know you couldn't for example implement uh using a simple actor api things like you know barriers and and summer force which i've shown you which gives you some idea that this notion of csp is different and maybe also more powerful right that being said actors are wonderful for doing things like network communication where asynchronous is paramount right and so finally i'm going to go over now what i'll call channel oriented asynchronous programming and what i mean by that is the following and so if you remember in csp we dealt primarily with processes we had uh process we combined processes and events to create sort of composite processes uh which had sort of different behavior we had this environment that made sure that processes rendezvoused when they when they were eligible to and the thing to remember about csp is that it was constructed in order to formalize over you know in particular the number of the processes themselves were lexically bound you couldn't have more processes than you can define you know tokens in your lexical environment so that obviously is problematic for real world scenario it's not a very flexible way to to write a program and uh it on on its own it became a very very cumbersome programming model there were some people that tried to make it into a real language but it turns out to be very cumbersome so what i call channel oriented concurrent programming is basically csp but making the channels not the processes first class and so in csp if i say you know send this value to process a and receive that other value or sorry send that value to process b and b receives the value from process a i can share a channel over which i can send and receive at the same time right the semantics are actually very very similar it's more difficult to formally reason about it i think but it turns out that it's a more flexible way of doing actual programming and one one concurrent programming system that that makes use of this is something called joint calculus and again joint calculus takes the sort of core ideas of csp or some of the core ideas of csp not all of them as we'll see guardian channels and effectively defines this environment that is responsible for rendezvouing things right and so one way to think about that is that your environment is a big chemical beaker okay and each channel represents some ingredient right and so when i send something on a channel that means that that ingredient becomes available in your environment and reactions are defined as well in order to create some y i need an x and a z and a b right for example and so you can create these sort of declarative what they call joint patterns in joint calculus to effectively decide how reactions proceed in your sort of big chemical beaker environment there's a language and based off of chemical geocamel which makes use of this and this is a simple example of for example doing a concurrent stack and in this case we sort of have all the all the components that i've talked about except for synchrony and so the way to read this is the following a stack is something that defines uh three channels a state a push and a pop and there are two quote-unquote reactions defined here if i have a state s and a push so if there's both the state state events available and a push event available then that creates a new state event and replies to push and so that tells you that the push succeeded right or if there's a a non-empty state available whose head is x and a pop operation available then i produce a new states s which is the tail of of that list right so that's just us in scala you can deconstruct and construct lists in in that way uh using exactly the same operators and reply with the head of the list to the the sort of pop channel in this case and the important thing here is that these things are mutually exclusive you know that at any you know if you if you sort of think about discrete virtual time at any tick exactly one of these happens right and so now you you define here that um state can only be modified by one of these at a time and it's not exactly modified you're sort of defining it as producing a new state in your environment and these conical reactions happen only when you have both a given state and a and a push or pop operation and this example also uses guards right because the second class here is not eligible for execution if the list is zero if the list is empty so now the question is well we have now we have you know we have we have a lot of we have a primordial soup if you will now of various abstractions and ways of thinking about uh concurrent programming and the question is can we make use of this in a practical way saying scala and it turns out that there is a dialect of uh ml called concurrent ml which attempts to do just that and at twitter we created something called offer broker which borrows a lot from from cml to basically try to figure out how to employ these ideas in particular synchrony guards and channels in a practical setting one that we can actually use and we call that offer broker so an offer is again some sort of abstract value over which you can sync and so a synchronization operation uh is and its name implies that asynchronous uh allows to retrieve the value t from offer right and so when you synchronize an offer that means that you're effectively saying there's some event in the environment that that that you want to retrieve a value from and you can do the other sort of all the other kinds of things that you might do with with containers and scholar like for example you can map over it and so on now critically um now that we have this sort of abstract notion of an offering you can think of offer as an event right and so uh when you look back at csp uh an offer might be represented by you know a bang x that's an offer of sending something b question mark y is an offer receiving something right and only when you call synchronize on these offers to actually sort of actualize the fact that you do want to synchronize on it offers by themselves are just values that don't do anything right and crucially you can compose over these offers and so for example i can take a number of offers and use the offer.choose combinator to create a composite offer which does exactly what choice in csp did which is to say exactly one of those offers synchronized right select is just a shorthand for uh calling true servers set of offers and synchronizing it turns out this is just a useful pattern uh and then there's sort of sundry offers that are useful for example you can define a timeout offer which is an offer that's willing to synchronize after the given timeout and never opera is an offer that never wants to synchronize a constant offer is one that will always synchronize with the given value and so now the question is we've defined the sort of abstract notion of an offer they're just these sort of events that you can synchronize over and combine in certain ways so now the question is well i need a i need a source of these offers and that's what we call brokers and so you can think of brokers roughly as a kind of a channel right and if i have a broker of type t i can i can call send and send gives me an offer of units if i call if i have a broker b and i call send i get a get an offer over which i have to synchronize in order to actually sort of actualize that event but i'm just creating these events that i can combine and synchronize later and this is how you might want to use that let's say i have a broker of integers well if i call b sum 1 2 3 that doesn't do anything because i haven't synchronized over it however if i synchronize over it then i block until some other process has received it and this is a sort of rendezvous going on and conversely if i call b receive sync then you know that blocks until there's some sort of sender available this is just synchronous communication as we defined earlier so now you can start doing some interesting things so remember to sum it for from before this is how you might define this in offer broker so i have a p and a v broker right and if i receive a v event then i want to increment my my summer for a value and if v is greater than 0 and i receive a p event then i want to decrement my value right and so now i've i've only used what i've showed you right i'm using a broker to represent the sort of channel of sending pnv messages and i'm using offer select remember opera select is just a way of doing offer choose and then synchronizing on that right and this is now a summer form and the semantics of after select guarantees that these two classes are mutually exclusive and furthermore you have guards naturally because uh you can just use the full power to scale language to examine whatever condition you want and in this case for example if v is not greater than zero then i'm never willing to to receive a p event unless i just call it you know i just give it an offer.never instead and combine that with um with the view receive event in this case so this is what a summer 4 looks like an offer broker you might define a resource pool for example to be the following i might define a broker for getting and putting items into this resource pool the pool itself might be represented by queue and the way that the the way that works is that well if my queue is empty then i'm not willing to send anything on the on the get channel however if it's not empty then i'll send the head of my queue right and if that actually ends up synchronizing then i recursive myself with the tail of that queue i'm always willing to receive a put event and then that means i recurse uh again with that element that i just received uh and queued onto my queue right and so in this again now we're we're combining this mutually exclusive choice operator with synchronous communications with with um um with guards uh and it gives rise to some very powerful things now you might say well this is not so interesting this is just a you know pool anybody can define a pool you can have locks to do the same thing uh just you know synchronize the critical region like this is not very interesting yet however when you actually start using it is when it gets really interesting so for example let's say i want to just receive an item well that's pretty boring i can just call you know get receive sync that synchronizes on the receive event from the get broker in this case however let's say i want to wait for no more than one second to get something from my pool right and so if there's nothing available after one second i just want to time out well then i can define a timeout offer recall that's now the offer that's is willing to synchronize after one second and combine it with my receive offer and what that means is that after one second i either have none or some item right i use an option and the critical thing here is that these two are mutually exclusive right and the really interesting thing about this is now i've implemented timeouts in a semantics per serving way without modifying the pool at all right and that's only because the environment gives me this power to effectively express a mutually exclusive choice here right and so i'm guaranteed that either i received from something from the pool or the timeout happened right and the environment makes sure that's true um and that turns out to be a very very powerful thing to be able to rely on so i'm going to finish with a a just to just to try to convince you guys that this is actually really really useful and also useful way of constructing concurrent software uh i'm gonna sort of go over a recent uh example in which we used these constructions and so uh one of the things we do at twitter is that we effectively store large server lists on zookeeper however occasionally zookeeper is unstable either because the servers themselves are unstable or there's a bug in the client libraries or there's you know network issues and what ended up happening is that if we relied sort of on the the current view of the zookeeper super client of a particular cluster which again is just a number of entries in um you can think of zookeeper as basically just giving you a file system um a distributed file system and for the purpose of this um then the uh the resulting the resulting view of of zookeeper the zookeeper file tree uh was very volatile right which is not what you want in a distributed system where you want to have a stable view of your clients and all these different things and this volatility was not because the servers themselves were volatile they crashed all the time or whatever it's because of you know zookeepers would be refined or network issues and so the basic idea was well why don't we use the semantic of zookeeper to sort of qualify these removals or additions of hosts and so in particular if i receive an event from zookeepers saying host a has been removed and i wait for some amount of time that's defined by zookeeper to be the round trip time for heartbeats and zookeeper then i know that at that time plus rtt zookeeper was healthy at the time i received that remove host event right and so then i qualified and only then do i trust the fact that something was removed so for example if you have a healthy ck that basically just means well i need to i need to shift time shift effect of the the the z k events in this case however when you have flapping uh zookeepers i need to do something else and so let's say uh let's say we have a timeline like this where at first receive a remote remove host event and then before the rtt expires uh zookeeper flaps it becomes unhealthy and healthy again well what i what i need to do is to make sure that the view of zookeeper is still consistent with the fact that a is removed after another rtt has expired right and so this is the kind of this represents an interesting sort of concurrent programming problem you have all these events coming in asynchronous you don't know when they're going to happen and you have to maintain some state in terms of you know maintaining uh keeping track of of which hosts were um were removed at what time and what the shift is and so on and so let's try to figure out how to use alpha broker to solve this problem well first of all let's define two events so connections can either be added or removed and this is just a standard sort of algebraic data types pattern and then i need a way to represent the events by the way one one way of thinking about this too is that what we're implementing is basically just the filter that has the behavior on the right right so i receive the events on my on the left i apply filter that yields the behavior on the right and so i need a i need an offer for receiving all the input events right i need a broker to send the output of instances the output of the filter i need some sort of offer to receive updates of the health and so that's the other sort of concurrent uh non-deterministic asynchronous thing that happens in your system you know you get health notifications in unpredictable fashion and then the rtt is just a duration that defines effective what the qualification period is and so one common way of using off a broker is to effectively have you know loops with cases just like you would in actors for example this is how we saw in the loop example in the summer four as well and so we can do effectively case analysis and break this problem in to the various cases and the state again is the following the state is the q which is the queued removals in this case we don't care about additions we can be play fast and lose with those and the current health of the cluster so the first thing that we need to do is look at input events and so in the case it's a remove event then we recurse with recurse with a new connection with uh an expiry time of rtt from now right if if it's an addition event i just immediately pass it through but then in addition if i see an addition that was previously removed i removed that that cued remove event right and so that basically allows you to say well if i flop and the view of the zookeeper cluster is not the same when it becomes healthy again then i sort of reconcile that fact by removing the previous removes that turn out to be additions if i receive a new health event then i well first of all if it's the same then i don't need to do anything if it goes from unhealthy to healthy then i i time shift all the events and so basically i say well all of my cued removals i'm going to wait for another rtt in order to qualify and if i go from healthy to unhealthy then i just change my state so next thing i need to do is while if i'm healthy or um or my queue is empty right then i don't need to do anything uh actually i should be unhealthy that's not that should be unhealthy if i'm unhealthy or my cue is empty then don't do anything so if i'm unhealthy i want to delay all my qualifications i don't want to alter the state of the cluster also if i don't have any anything cued then i don't need to do anything otherwise look at the first element in my queue and create a timeout offer when that event expires and if that's the event that gets chosen then i send that qualified event for removal further down and this is effectively how i time shift all my removals and so all together it just looks like this this is the this is roughly all the code that's needed to implement this and we're dealing with a lot of hairy things here right we have all these different event sources i have timeouts for when the time shifted events needs to happen i can receive health notifications from the cluster and also events describing the the additional removals of various connections from that cluster and it's very very powerful to be able to reason about these things as being mutually exclusive in this case and also be able to have these guards basically saying well if i'm unhealthy in this case then i want to i want to wait until i'm healthy for example it just turns out to be a very very nice way of constructing solutions for these kinds of problems that exhibit high great amounts of concurrency so um in summary basically what i hope to sort of get through with this talk is mostly to sort of communicate that there's there's a really rich history of concurrent programming and uh threads and locks represent the sort of the very very lowest common denominator for that and unfortunately it's the sort of mainstream in mainstream programming at least that is the de facto way to go about programming concurrent systems but there are far more powerful ways of thinking about them in particular when you combine synchronicity composition events and guards in particular you get a lot of really really powerful sort of emergent properties of that and furthermore everybody should read the csp paper it's a really really insightful thing paper and that's basically all i had to say so are there any questions yep over there so the question was explaining opera broker what's the difference basically the difference is the following so so offers represent this abstract notion of an event in the system and so this is the sort of thing that there's a number of offers in your environment right and your environment is responsible for effectively matching which offers can uh you know together uh synchronize right and brokers are just a kind of a channel that allows you to produce offers from either sending something or receiving something right right and so you compose over offers uh brokers are just a mechanism for for actually producing useful or coordinating um uh these kinds of transactions