The Road to Akka Cluster and Beyond

SF Scala, Jonas Bonér: The Road to Akka Cluster, and Beyond…

Recording: SF Scala, Jonas Bonér: The Road to Akka Cluster, and Beyond…

I'm I'm really pleased to be here great location great office uh so this this talk is titled the road to AKA cluster and uh it's going to be sort of an unusual talk I guess for a scholar Meetup it's it's not really going to be that much about Scola I mean AKA is part of schola distribution right so it's in a way in indirectly related but it's not going to be really about how to use AKA either this sort of this this talk sort of assumes that you know what AKA is all about instead I'm going to try to give you sort of a walk through about so the history of of distributed systems and and uh and sort of what have inspired AKA and especially AKA cluster we really really standing on the shoulders of giants here and and we we owe a lot to the to all the all the all the great papers and all the great research and all the great products that that been done the last like 20 30 years and uh so I I'm planning sort of walking through some of the some of the highlights for me and then also sort of that's sort of the first half or some perhaps twoth thirds and then and then talk about how we apply this in AA and actually how AA cluster is actually implemented how it's working under the hood and uh if you have no clue about AUP sorry I mean I'm hope that hopefully this this can be interesting anyway and if you don't uh if you never use DOA cluster you at least know I mean how how it's how it's working under underneath and you can go go home and try it out so that's essentially the idea of of this of this talk so starting what is a distributed system and why would you need one uh the answer is I mean one of the answers is that I mean why would you need one you're already using one the distributive Computing is really The New Normal it's I mean you have a Distributive system you're using a distributed system I'm gu I guaranteed you even if you're not aware of it sometimes I mean mobile is definitely a distributed system you I mean especially since clients can go offline and and and and the clients do updates and when when they come back online you need to sync things back all the challenges of distributed computing comes back and there's a lot of things that we can learn from history that helps us deal with that problem same thing almost all SQL both SQL and nosql databases have replication that both like offline replication and like asyn and synchronous replication and so on and knowing what is what and how things actually work and how you can tune it can be really the matter I mean the difference between success and Fa and and failure and and rest I mean is also distributed system all cloud services that we use and we actually usually deploy now on Amazon all these virtualized environments actually encourages us to use distributed systems because it's it's it's it's a lot cheaper to buy to to buy just an account or at Amazon or each or if you run it yourself to run commodity Hardware really inexpensive boxes but many of them instead of buying these really beefy boxes right 48 48 course or whatever it is so scaling out is the trend scaling out is really is really is really more cost efficient and that implies a distributed system okay so what is the essence of a distributed system if we try to sort of Na nail it down yeah it's been said that it's tried to overcome two things that information travels at the speed of light mean that means that we have latency now in communication that becomes very apparent that we that we wasn't when we run just in process just regular method dispatch it's it's not that clear but but but latency becomes a big factor in how we have to design our systems today and also the second thing that what is this sound okay some some soundtrack so is that independent things can fail independently and and and and a distributed system is really I need to stand here I guess okay that's the clue uh independent things things fail in independently and in a distributed systems things are really fully independent you have you have the network in in between and this means that things can actually fail without you immediately noticing that and as we all know I mean the network is inherently unre unreliable messages can can can easily get dropped and so on this makes it a lot harder so but why would we need a distributed system we need for for SC for scalability reasons when our Sy when when we s outgrow the the resources on a single node or then we need to go as I said cross notes when we need to provide availability you can't possibly provide full resilience and availability using single machine because someone the clean lady might just unplug it right that's actually happened uh my Roland told me a story but where that where that actually happened they actually had redundancy at at this lab that he was working as a as a physicist but and but but the cleaning lady actually pulled out both plugs from both of their machines right so I mean happens right and and we better have a good way of dealing with that so availability of providing that resilience if one node fails you need to scale out you need to be able to have sort of some some sort of distributed system and Rich state for clients as I've already said also some people not don't think about it but all the all the are classic problems of State management management becomes really really apparent when you're working with with with with with stateful clients and you have the network because they can get disconnected and how do you then merge things back and how do you continue from there so what's the problem yeah the problem is that it's really really hard it's still hard and we've been trying to learn these things for 30 years and it's still very very hard one thing that that makes it so hard is that you can't really tell the difference between a slow node that just doing GC or is very under heavy load or that is dead there's down it will never come back again and since you can't tell this difference you need to have different strength Str is to work with this we're going to look at some of some of them later and as I said earlier the network is inherently unreliable uh K Kyle Kingsbury and pet pet and Peter Bailey recently wrote this great paper called the network is reliable and and I really encourage you to read that he walks I mean he gives you s about 30 different case studies 30 I just making that up 20 40 I don't remember it was a long list really sort of enlightening case studies of things can go wrong as soon as as you have a network you better be be be prepared for the worst really and and we all most I guess probably have heard about the of the eight fallacies of distributed computing by Peter Deutsch the network is reliable is the first fallacy there's no such thing latency is zero bandwidth is infinite the network is secure to poity doesn't change there's one administrator I mean human error you should not underestimate right the cleaning lady or someone that you just almost completely out of the picture when you design the system transport cost is zero the network is is hom is is homogeneous we should really like put this up on the wall and and and and and uh and and sort of internalize these things I think so it is it is very very hard and we need to to have good strategies to deal to deal to to to deal with this I have my own graveyard of of distributed system that I visit okay tionally right when I when I want to yeah well I don't really know what what I'm doing there but anyway it's it's uh it gives me peace somehow to know that I sort of I'm past this guaranteed delivery just doesn't work there's no such thing as guaranteed delivery at least not generically you can you you can provide that within a certain boundary within certain with like well- defined context but not not gener not generically synchronous RPC is another thing that I don't think just doesn't work Steve wowski wrote this great paper called convenience over correctness that I really encourage you to to read where it talks about this that emulating synchronous method dispatch on the cluster is is just doomed to fail and and distributed objects Martin fower said it said it said it well when he said they suck like an inverted hurricane It's actually an actual quote from from one of his books and I I I have I have I have to agree I mean in in general shared distributed mutable state is bad I we know that all we all know that hopefully that shared mutable state is bad if you run it on the single machine just gets worse when you try to do it on the cluster and distributed transaction XA I mean i' I bled a lot okay General strategies I think you should you that you should sort of U adopt is is divide and conquer try to decompose the problem partition for scale and replicate for for resilience in other General strategies I mean this requires you to sort of some have some solid principles and and the the these principles are are some of the ones that we try to to sort of teach and and make people understand when we talk about reactive systems systems that are are there are scalable elastic there are message driven that are that are resilient and can can really be be fully responsive even when things fail and when things when when you have like peaks in load unpredictable and so on so the essence of it is that if you if you rely on loose coupling local state keep state that belongs together local and and and have have isolation and rely on asynchronous computation right message passing across these so you have an asynchronous boundary to get this loose coupling this gives you location transparency that means that you you have the that your your that your component can actually run whenever you have these references to your components and you don't need to sort of care where they live and and you and you sort of go be well beyond these are these all the problems with with with RPC if if you if you if you fully rely on on on on asynchronous message passing instead of having this classic blocking RPC so how can we make all this happen yeah let's look at at some of the some of the research that been done the last 30 Years or or more uh let's start by by by something called the impossibility theorems there are there are a bunch but there are a couple that I think are more important than others impossibility theorems is sort of gives you a negative result you can say it pro it shows what is not possible and by showing what is not possible it gives you a glimpse of what what is possible so so it can it can point you in the right direction so to speak one one classic one is is called impossibility of of distributed consensus with one faulty process and that is sometimes called the flp paper by through like the names of of of the of the three authors Fisher Lynch That's Nancy Lynch Patterson I don't remember the first names of these other guys it was from 1985 and it it it can be sort of summarized in that the flp paper result shows that in an asynchronous setting where there's only one processor that might crash there's no distributed algorithm that solves the consensus problem and and and and uh this sounds this might shows pretty pretty harsh but in the flp paper they sort of End by saying that these these results do not show that such problems meaning consensus can be cannot be solved in practice but that they they point the need for more refined models of distributive Computing and a lot of a lot of these models have then evolved ever since and and another very interesting sort of sort negative result you can say like impossibility theorem is a cap theorem most people here probably heard about that even if you hadn't heard about the flp paper and there was a conjecture I think initially proposed at a at a keyote by Eric Brewer in 2000 uh but it was later proven by n by Nancy Lynch and and Gilbert in 2002 a couple of years later uh this is the name of the paper by the way but but essentially it proves that linearizability there's very close just to serializability you know serializability from database right whenever with there like total ordering and basically you like shoehorn everything through a single a single writer essentially at least conceptually uh that's not possible on in a distributed environment and it and it and it introduces this this idea with they have have cap stands for consistency availability and partition tolerance so and out of these three you can never have all all three you can just have two at a given point in time so and and and if you have a distributed system then you have p p means basically that there can be Network split that means that you you only have one choice and that is choosing between consistency and availability there's no other there's no way around that and and and and this have been a very highly influential paper I'm going to talk more about that everything that's sort inspired later but but but first then what is l linearizability what does it mean since it proves that it's not possible in in a distributed system at least not in in a fully Avail un like available scenario so hery Wing in 91 defined it as under linearizability linearizable consistency all operations appear to have executed atomically in order that is consistent with the global realtime ordering of operations yeah so what what does this really mean then it less formal you can say that a reed will return the last completed right regardless where is made if you have a a cluster of 1,000 nodes and the reads and writes happens all the time any read will return the last completer right regardless of where it happened this is a very strong guarantee and it's extremely costly and we can't possibly need that for all for everything we do so the question is when and and and and and and how and if we so as I said cap was sort of extremely influential but when look looking back at it a few years back now it's like 14 years it's it it it actually shows that it's it had pretty Naros scope I think Peter bis in this hat paper I'm going I'm going to come back to that later highly available transaction paper said that cap has led to confusions and misunderstanding regarding replica consistency transaction isolation and high availability and the thing is that the essence is that linearizability is very strong guarantee and it's not very often required actually sometimes it is but it's the same problem like we have or an Oracle database in our in our infrastructure we just shoehorn everything down there I mean it's convenient right and you can all use all the tools for data mining or whatever but it just won't scale period Oracle rack might help you but I mean then you like have to sleep out out on the street instead the second thing is that it ignores latency almost completely and latency is has a very practical meaning you know we started by defining distributive system as as as as as sort of a I mean a cap on the speed of light has really bad big big impact latency matters and and and and and partitions are actually pretty rare even though the P stands for partition tolerance but partitions are rare so why then do we need to sacrifice consistency or availability all the time doesn't make any sense instead I think we I mean we need more fine grained models for dealing with these things ideally adaptive models that that sort of give up on certain guarantee when when they when they just has to not all the time not just black and white and most no SQL databases that came out of this movement of eventual consistencies they were either like black and white initially and this they starting to to change that I think even Eric Brewer wrote this great paper or article more an article than a paper it was an info was written on infu I think cap 12 years later where he actually argues for for most of these things so that was impossibility theorems another very important thing I think that we in order to work with distributed systems we need a way to to work with time time needs to be first class in our programming model and you you can't just handwave that and and and thanks to lesli Lamport we we now we have pretty good ways of dealing with time now in in 78 he wrote this this this this extremely influential paper it's probably the most quot like quoted paper in in in computer science history was like was a time and ordering in distributive systems something like that I a a pretty long title where where where he talks about logical clocks and and and causal consistency they now usually named sort of Lamport clocks and and and is sort of a a virtual clock or or sort of a what do you say a sort of an abstract concept of basically just a counter so when a process does work that is important that then it in increments the counter and when a process then sends a message it he includes the counter okay so and when the when when the receiver receives that the message it it takes the counter and it merges it with its own counter this gives you caal consistency and and you can make sense out of ordering in in a distributed system this was extended by Colin fidge in 1988 and actually was he was he wrote a paper concurrently with some other guy that nobody that nobody remembers the name of at least I don't so so um they both discovered Vector clocks then and which is an extension of of lamper clocks and in in in Vector clock clocks each node a node doesn't have to be physical node it can be user it can be something something that's that's sort of yeah has has has a role of of a of a of a node that you need that need full consistency in a in a not full consistent but then need that need to be play a part in caal consistency in in the distributed system each one of these owns an increments its own Vector clock so in a way you have like a map of nodes to Lamport clocks okay and the way it works is that each one of these they always keep the full history inside the vector clock so they are fully self-contained and and and and it has sort of a monotonic merge function if you heard about crdts and we'll talk a little bit about that later they're very they're very I mean Vector clocks is actually a c a c a crdt where you have a mon monotronic merge merge function that would always I mean successfully merge and uh that that that that is an extremely useful tool we see we see out through using I mean in most s eventually consistent databases today we use them in ariv we'll talk about later so now we have a good way of working with time and and and uh a way better than than than than than I think some some databases use last right wins or so that can really lead to data loss Vector clocks has its own set of problems like like like how do you prune the history for example if if history grows forever uh you need you need you might need a way to actually prune that history because the the data that in the vector clock you need to send around just Grows Right but there are good research of that like dotted version vectors for example helps you with that and and so on so I'm optimistic failure detection is is another thing and and and as I said there's really no way of of knowing if a note is down I mean dead or if it's just doing GC if it's Java or just or if it's just the tempor every Network split somehow so failure detector is like it's more of like sort of sort of an an like an art or or like black science or whatever you you want you want you want to call it there's there's no there's no such thing as I know for sure you can only do guesses so a good failure detector is really good at guessing if so the likelihood that the node is down basically so in order to understand failure detection we we can we can first like look at a formal like a formal model to like C to categorize failure detection the the the first thing is is strong completeness strong completeness means that every crash process is eventually suspected by every correct process this is this is as As Good As It Gets okay weak completeness is that every process is event every crash process eventually suspected by some correct process this might be okay okay as long as someone like detects it and can start like telling others about it strong accuracy means that no correct process is suspected ever meaning if you if you have done nothing wrong you shouldn't be like busted for it right and have to like explain that you haven't done anything this me Bally basically means that there are no false positives weak accuracy is that some Pro some correct process is never suspected and that's basically can be translated like some false positives so in an Ideal World you have strong complet completeness and strong accuracy but you perhaps don't need that everything has a price especially in a distributed environment things are very costly so yeah it's not it's not always an easy choice to make one interesting paper is is is is a paper about acrel failer Detector by I think it's Japanese guy has yeah hayashibara sorry if you're Japanese I no offense with this is actually the one with that that we're using in AKA and we look into that and some problems with it as well later on so the acrel failure detector actually actually does what it what I guess what you can guess right it it it it sort of gathers statistics and keep statistics around from heart from heart beats and the nice another nice thing is that it decouples monitoring from the interpretation of that data and it's and what it does it calculates the likelihood that a process is down so so you don't get yes or no you get something called a five value back that that sort of shows you how likely it is that a process is down and this gives you more freedom to actually to use that I mean it might be that that that all of them are suspected but then you can sort of or like half of them are are are are suspected to some degree but then you can sort of start continue to send messages to the one with the high likelihood or the low likelihood of being of being down while ignoring the ones with with with high with high likelihood and so on as I said there's no such thing as black and white you never really know so you just have need to fill a detector that is good at making guesses out of like data basically not just flipping coins of course uh so so so when you when you plot out one of these it it usually usually have this sort of classic J curve and yeah here's the formula by the way if we're interested I can I can share the slides later it's also I have a lot of speaker notes as well with with links to all the papers and everything and there's like 10 pages of references at the end if you're really into reading up on all this which you should be actually is is your future another very interesting one is the swim failure failure detector and and and it it also has some pretty nice properties it's it's it was one of the first ones that actually separated heartbeats from cluster dissemination because which that means means that that I mean I mean a lot of a lot of the early fail detectors sort of merge like the gossip being of state with the with the heartbeat that sounds like a good idea perhaps because if you if you're communicating with the proc with with others other processes every second or whatever sending out uh State why don't why why don't like count that as as a heartbeat but but but then it gives you less freedom to to configure these independently of each other and sometimes you might you might want to like send heartbeats more often than you actually want to do state replication and and and and you don't want to send do state replication more often than you have to because they that usually has way more state that you need to send around while heartbeats can be can be extremely small and very very efficient that's why it's good to separate them I think it also introduces something like a concept of of a quarantine where where where where even if you suspect that the process is most likely down you you just don't mark it as down you actually put it in in quarantine and let some time pass and and while he he has the opportunity the possibility of getting out of quarantine if if if you were wrong which actually very often happens but if quarantine if the time passes he's doomed as faulty and he can't get back again another interesting and probably the most interesting contribution in my view from this paper was delegated heartbeat and that that's that's a very sort of cool way of sort of G getting around Network splits so the the way it works is if I would try to explain it is if you have two processes like Alice and Bob if you want to use this a classic Classics sort of names in computer science so Bob sends like sends a ping to Alice to see or up if Alice responds think's fine she's up okay if she doesn't respond within this within a certain timeout instead of marking Alys is down what Bob does is that it sends a message to like five or three or whatever random nodes in the in the cluster one of them might be Bob for example and then no bill sorry one yeah it's e ABC I guess but anyway okay so so so then so then he sends a hint to Bob and say could you go check Alice out and and and and and so so so so so so bill then goes and send a message to Alice and a whole bunch of other friends and if if if one of them is able to reach alleys then alleys is apparently healthy this was just a network split between you and alleys with between Bob and alleys right and so there's a way around the network split and things are might be fine this this this sort of network connection might heal eventually but if if all these sort of candidates that you ask to check for Alice returns with a timeout then Alice is apparently down and you can Mark her down so I I think this this is this is something that we we've talked about at we haven't done it yet it's an interesting optimization or you say it's an it's an interesting way of taking the the accuracy of the model even further I'd say strong consistency yeah that's basically about linear linearizability and that's sometimes needed but it has a very high cost I think and and but there's been some some pretty interesting sort of papers lately about that that actually you know I said in the beginning it was even part of my graveyard right the XA transaction are doomed to fail distributed transactions are actually on its way back but in in in a different form and one of the great papers there is by Peter Bailey uh is a very recent paper he talks about highly available transactions and he will talks about hat then instead of cap yeah it's sort of cute any way so and and sort of the summary of that of that paper and and what I think is interesting is that he argues that most SQL databases they do not actually provide serializability we might we might think they do right we learned in in in in sort of in when we talked about relation algebra and stuff and in in in computer science course at University that that is sort of the optimal way they actually don't do that they have weaker guarantees and that's for performance reasons and the interesting is that some of these weaker transaction guarantees are actually possible to implement in a fully highly available manner on a cluster which I think is really is is really fascinating and the question is then that they ask is what transaction semantics can be provided with with with high availability and and they from from this is from the paper here actually here actually where they where they where they list the different guarantees that gives for example an oracle it it doesn't give you serializability the best you can is read committed and the interesting thing is that when when you start looking at it read committed is actually possible to implement in a fully highly available fashion so it's so so you can actually give the same guarantees as Oracle and scale out in if and being fully highly High highly available some of the ones that are unavailable is is like serializable for example because if if cable was able was possible to be highly available then cap the cap theor will be wrong right so it's an interesting paper to read other other research papers around this is there another one by by Peter baile it's called Bolton consistency it's one called Calvin that I found intriguing as well spanner you probably heard of Google they rely on on atomic clocks I think [Music] they're yeah I won't go into details too much about this another let go on instead consensus protocols is also something important and and and and that most people know about and most people have heard about paxos for example but before we do that let's look at at at at some some properties that these consensus protocols need to have so if we have then first two events for this this little model that we have request and we have decide for for for a specific value then termination means that every process eventually decides on value V okay validity means that every process decides we then if every proc if a process decides V then V was actually proposed by some process it was just not random L made up that's a pretty interesting property integrity means that no process decide twice that would be unfair and agreement means that no no two correct process decide differently so you have then full consistency okay and and and some of the consensus algorithms that implement this is is um yeah is paxos for example that was that was probably the first one but but le le Les Lamport by the way Les Lamport is giving the closing keynote that react in San Francisco here I was really excited to to get him on board on doing that Zab is another one that's the sueper atomic broadcast Pro protocol that was another one uh and and a very s of one that came out fairly fairly recent that's been immensely popular is raft I don't know if you've heard about raft the interesting thing about raft is that they set out to to to come up with a protocol that actually was understandable paxus is extremely hard to understand I mean I mean there's for a reason that Les Lampert I think wrote seven papers trying to explain paxes right one actually named like Pax Was Made Simple and still people no one understood it h and and and and what's really what's really hard with paxus is that it's almost impossible to implement it by the spec in in the real world you always have to divert slightly from the spec and and guess what then you have a fully unproven model that you have to prove yourself raft what these guys have said they set out to create a simple model simple to understand but it actually turns out to perform very very well so I I encourage you to look at to look at raft there are implementations in most languages nowadays and and raft then or sorry and consens all these consensus protocols they they Implement CMP that means they are not highly available if one node is is gone then you can't have consistency there no way to get agreement then uh another interesting thing that's not really research but that I think is important to mention is is is is sort of the how how sort of the the popularity of of of event logging and and how and and and how to design your your system as especially event driven system and message passing system using an event driven no you're using an event log and and and uh the first thing here is that is that it favors imut IM immutability all events should be immutable and and you should really have a fully share share nothing architecture and I really think that that is the true path towards scal scalability and we should think in facts Pat Helen that the giving the second keynote that reacts I'm really happy about it he's one of my my role models I mean all his work with Jim Gray in the 80s and stuff so he said that the the database is the cache of the of of the subset of the log which is which is pretty interesting you know oracle already has event logging and transaction logging in in I mean under the hood right it's just they they don't they they they don't expose that to just expose the latest snapshot of that log to you what if you need I mean all the stuff down there right tough luck you need to do it yourself and and that's what's really starting to happen to happen now I think there's no reason to not keep State around forever it used to be when dis was really really expensive today is it's so cheap so we let's let's let's just keep it around and in place updates just need to die I think there's really no saying reason to keep on doing that so keep everything in logs never delete data knowledge just grows why delete knowledge right important things that you might need later and uh it's also very very very efficient if you have you can apply the single writer principle just writing very very fast to the log and and and minimize contention and yeah and we don't we can we don't need to go into this so another interesting thing is then eventual consistency we talked about strong consistency eventual consistency that basically means that you that you don't have consistency at the moment where when you might ask for it and but it guarantees that eventually the system will will sort of coordinate in a way that that that you get sort of stable values you get agreement and one of the sort most important papers for this was was was a Dynamo paper it was extremely influential and and it and it popularized mainly the first three things sir it popularized eventual consistency it really set set off to to create this trend of no SQL databases there are event consistent and and it also popularized epidemic gossip and and consistent hashing both of we we will look into later and that AKA has has adopted some other interesting strategies like hint like hint like hinted handoff for example send sending sending data if the node you the one that you need to replicate to is not available you can send it somewhere else with a hint whenever that guy is up send the data to him if and things like that read repair and so on you should read read up on that yourself it's interested consistent hashing is a very Nifty sort of Str strategy that gives you a very nice way to support support full elasticity meaning that nodes can come and go uh so you can like really get them and live up to the promise of cloud of cloud computing without too much of a hassle it basically gives you way if if you lay out all the nodes in a node ring then consistent hashing mean that you can you consistently hash all the buckets and and uh you have a very sort of nice way of doing like like partitioning and replication and and add notes in this ring this ring can expand and Shrink without you having to to to sort of do much work uh one one question though is how eventual is eventual consistency and how consistent is eventual consistency I said there's not there's nothing black and white you can't say in I mean in one second my system is is is is fully consistent eventually sort of sort of a bit fuzzy right so so if how can you make make sense of this and that's that's a hard answer to hard question to answer but but Peter Peter Bailey's group at at Berkeley they've also done some some pretty interesting work here that I think is worth looking into they call it probabilistic bounded staleness PBS and it gives you sort of a model they even have actually live demo on on their website where you can to start typing things in it it really gives you a model to see how itial and how and and and how consistent it is over time here here here we can see like how long it takes until this until I here's like time after commit how long it actually takes until the system is fully eventually consistent using different sort of thresholds so I I won't I won't go into that paper and just giving you a hint it's worth check checking out and give you good models for actually making sure that you are within the slas because if you start using eventual consistency might might be that you you I mean you screw you screw up and the latency is too high until you actually have full have full consistency if you use the right model and know what you're doing you you can you can avoid that lastly I want I want to talk about before we get into AKA I want to talk about another Trend that is is is starting to happen a lot that's called dis disorderly pro pro programming they also call it acid 2.0 or Nifty if you if you if you if you look at at at the at the acronym what they mean a stands for ass associative that means basically means that the system or the the the coordination is is batch insensitive meaning the grouping doesn't matter it's commutative everyone knows what Comm commutative means that means basically the ordering doesn't matter and that is em potent that's a I so a c i and d stands for I don't know distributed perhaps this is is is sort of fuzzy uh item UT means that duplication does not matter and and and and some of of these are eventually consistent by the way and some of the some of the sort of practical applications they implement this the these ideas are crdts have you heard about crdts okay yeah not not that many you should actually look into that they are an extremely useful tool I think in in in distributive systems if you can model your data as crdts you're basically fine let's say you can go home no it's not that really that that that but but but still you're you can get pretty pretty pretty far so crdts basically stands for convergent replicated data types or commutative replicated data types some also say Conflict Free replicated data types they have lots of names but the interesting thing is that it you know most a long story short most most s eventually consistent databases they basically just Implement one data structure that's that's a register key value you know Voldemort and the old old Dynamo and and and uh ROK R has have links but but most of them actually Implement some sort of sort of key Value Store crdts actually gives you a way of modeling much richer data structures than registers counters sets Maps even graphs with the same properties with that that sort of Dynamo and and Rak and and Voldemort and this gives you okay so the the question is if you can model your data as a crdt which it has some sort of properties that you need that that that need to hold one is that they need to have a monotonically increasing merge function that in math see that they need they need to be a join semilattice yeah I won't go into detail about that is it worth but but uh the paper is actually very approachable I think it's very easy to understand and and and it implements sort of availability and partition tolerance it sacrific C but the interesting thing is that these data types now you can just update and throw out there and someone else can update it and as long as as as as as they reach all replicas they will eventually consist eventually be consistent they will eventually like converge and and and this is that's sort an amazing property the thing is that the the the caveat caveat is that not all your problems can be modeled using C crdts but the ones they can simplifies things a lot and there are two types of crdts there are the state-based the CVR DTS they are convergent they are basically have the same IDE same properties and problems like vector clocks they keep all the history around they are fully like self-contained and uh that's a that's a good thing right because that means that you can send them off even to mobile devices and they can do all kinds of updates and when they and when the network comes comes back they will just automatically just converge and things will be consistent it's very it's a very very nice model but you have problems with potential problems with with sort of uh I mean that the history grows over time and and then you have also these these commutative Ops based so to speak they they requireing fully reliable broadcast channel and and there you don't send the state around then you send the behavior around and have that upd being updated on all all notes Cal the we can we can Skip it's very interesting but I I'm I'm running out of time a little bit epep epidemic gossip as I said was really popularized by Dynamo and and I say it's really popularized by cord cord it's not it was sort of initiated by so cord made it popular in the research Community I'd say Dynamo brought it to the masses so and it's this basically gives you way when you lay out all nodes in a node ring it it it it really does sort of epidemic gossiping in the same like sense that like diseas is like spread like biological it's it's fully sort of probabilistic and and it just it just happens randomly but it has a lot of nice properties so usually converges very very quickly and so on and it also implements then a everything is of course then fully eventually consistent so the benefits I think about epidemic gossip and the reason why we have fully adopted in AA is that there's no centralized coordinator all NOS are equal there's not even any any specific roles so there's no single point of failure it's extremely elastic nose can just come and go as they want and therefore very very scalable can easily round th mean have clusters of thousands of Nos and so on and um yeah some so this this brings me to AKA it was a long journey right I'm I'm exhausted are you exhausted okay but now let's let's just take a look at how how AA is using all of this or or what what we use and and and perhaps also talk some some about why why we don't use certain things so cluster membership in you know aa aa cluster has cluster membership you can just spin up notes they will automatically be sort of be be detected and join the cluster and they can they can come and go and and and so on we actually use we we're heavily influenced by Dynamo so we use a masterless or decentralized peer-to-peer model using epep using epidemic gossiping we actually do the same thing we lay out all the nodes in a node ring and we do sort of semi- random gossiping between them we we use Vector clocks that's our way of sort of keeping track of time for costal consistency it's extremely important we can't possibly make sense of anything without Vector clocks and uh it's it's actually both extremely scalable I mean we can easily run unoptimized we can run we were running 2,400 noes on on on Google comput compute engine and even even even more interestingly we were able to spin up 1,000 nodes in less than four minutes and that includes actually all the virtual instances um in inside Google comput engine and and and and so we took so this time this is the time until we reached a fully sort of connected coordinated uh cluster so yeah this is a node life cycle you can I don't know if it's really that that interesting but we have we have a bunch of stages the interesting thing I can say though though is that the the node life cycle and the data structure we use to represent this is actually a c a c a crdt but we we never thought of that until we started reading up on C on C crdts which are in a ways are naturally evolved towards a c a full crdt by by just sort of trying to make sense of of of of of of of something that could work in the distributed environment uh so we essentially so the the the gossip that we then send around when we when we do have epidemic gossiping looks like this so we have we have a set of members all the members this is basically the node ring that's why it's it's a sorted set we have something called the scene set and that's extremely important I'll talk more about that in in a second then we also have a list of of of of of of all the notes there are there are reachable or even more important unreachable there are the the these are the notes that are marked unreachable by the failure detector and then we have this whole data structure versioned I didn't say that but one very nice property of a crdt is that a crdt is is composable so a crdt can be composed out of crdts you can big big I mean data structures out of small ones so so and we make we make use of this here I mean Vector clock is a c is the crdt that is composed with this larger s data structure yeah so so a very important Concept in in in ACA cluster internally is cluster convergence and what and what that means basically that so when we when when we start gossiping around when a node has C in the state and seeing that it has it has uh sort of the the same uh Vector clock then then it puts himself in the scene in the scene set so to to to mark that I have actually seen this seen this value if if if if the if this if the sort of version that you get is is lower then then it actually replicates back the newer one if if the one you get is newer then it does emerge and and updates himself so so this is the way so the cluster very quickly can con can converge and this is how we can keep track of when we read consistency because we read consistency when all nodes are are in the SE are in the scene table or in the scene set meaning that then then we know that everyone have seen this version because it's its version are you are you are you with me as soon as someone has not seen it will it would it will it will increment as soon as a change happens a node comes and node leaves then a new a new set will be put into the into the gossip and the version will be up incremented and this means that we have full inconsistency again and everyone needs to start uh marking that they've seen this value this unreachable thing is also very very important because as soon as there's one single node in this list with unreachable nodes that means that we can't have convergence any longer because because in that node because one of the nodes is actually down we'll we'll talk more about that that later and why that is really really important one optimization that that that we do is is what we we is what we call biased gossip I haven't really seen that sort of name used anywhere but it's it's a way to to to have these the whole cluster converge more quickly basically so we have 80% bias to notes there are not in the scene table so we actually check the scene table and and with 80% chance we actually replic I mean we actually gossip to the ones that not there to have it converge faster that said we we we initially did that for like all clusters but it turned out like EMP empirical evidence show that Beyond 400 noes and it actually was not was not such a good thing because because if you have like because because um so of the the nodes there in these 20% will will easily get sort of floated with with with messages from from from from from from all these so when we start reaching 400 we actually slowly start sort of decreasing this percentage and another interesting sort of optimization we do is is push is push pull that means that if we know that we have cluster convergence there's really no reason to send all this state around then we just send the version around which is which is which is extremely little data and and in in the default case that's usually I mean the default case is usually that it is convergent that the cluster is is convergent it's not convergent just when notes leave and go or become unreachable so this means that in the default case we actually do don't send much data around at all but as soon as either no I mean one of the noes detects that that the failure detector has marked node unreachable so it's so the reachable the unreachable sort of list is not empty any longer or that or or that sort of the scene table is is is not complete sort of speak then it goes back to regular gossiping again until we reach convergence we also have a concept of a leader we do not do leader election I mean fully fully sort of uh fully consistent leader election like Allah pack sauce or or raft or so and instead the thing is that instead we we we we we rely on on the on the Node ring what we do is that we hash the node ring using S a deterministic algorithm so it's always the same order for every single node they can't end up with difference reordering brings in this and then we just pick the first guy to say this guy is the leader it really doesn't matter which one it is because it's it's a role that we use the leader has has duties but it's it's it's it's not anything that requires much load at all H um so that's a pretty nifty way of getting away with with with with having a leader in the cluster without actually doing any extra work so and the leader can of course change after cluster convergence if if the leader is is goes down and not coming back again there will naturally be another guy that's first in this in this list and he will be then be be the leader and take over the leaders d duties the leader duties is is basically to manage when NOS join and leave the cluster moving him from different stages if you remember this this this the state diagram in the I showed some slides ago actually make sure that that it moves them because it needs to just be one that that does that so as soon as he's moved one from from like from as joining to to to to actually being fully fledged member in the cluster it it it adds that in the in the in the gossip information and starts gossiping it around until we have full convergence then everyone knows that the the new node is up and healthy and they can start using him so so that's basically how how it works failure detection detection as I said is extremely important as as well and and I mean a naive one we just sort do heartbeat to to all of the noes we have we picked a configurable value of five that we we start heartbeating to five different nodes and we we do that in a sort of conversational way we actually had we had thought out a very clever algorithm where where actually can only send one heartbeat and we can still sort of understand uh uh um through some sort of some some sort some some sort of without getting into all details about the actual product but we we s figure out in a sound way uh I mean if if if it was down or not but but but but which we we we changed that to like a simple request reply basically ping a ping a are you up yes I'm up uh for because it just just it became UN unmaintainable in the long run and we use failure detect detection not just for for cluster membership but we also plug that in to do really reliable remote Death Watch and remote supervision I don't know if you used the sort of reliability or the failure sort of the failure model in AKA in in the actor model but we have something called Death Watch we can actually watch how an actor is doing and we have supervision that's like the parent child relationship where you manage the the sort of the the the the failure and the health of of of your child that used to do not work across the cluster very very very well just because we we we were lacking a reliable failure detector so once once we had that we once we have that in place that just works you can just link to a remote actor and it would it will very reliably work am I am I running out of time minut five minutes absolutely no problem so we are actually using an acral failure detector but the interesting thing is that I don't know if you probably because we run on Java with with where we have GC and so on it actually doesn't help much in practice because usually GC and like have I mean take precedence over Network hiccups so instead I mean in an ideal case we we would see something like like like this like like as as an optimal conf configuration for for our failure detector but instead usually it looks like this so we added this acceptable heartbeat pause we actually we were actually able to stretch it out just to deal with things like like like like GC that that usually is way more common and takes way longer than than than like Network hiccups unless unless it's actually down of course then it's fully flat but uh so so so so we we argued if if we should just remove this this sort of fancy like statistical Gathering all stuff because I mean you only start making use of that over here uh Network partitions is is another thing PE people ask how we deal with that and that is one of the biggest hardest problems right when when you start dropping messages on the floor and and so on and as I said the failure detector his job is to Mark nodes as as unreachable so if if if suspicion is high enough then it adds them to this unreachable list okay and as I said again if a node is in the unreachable list then the cluster is not has that doesn't have con convergence and this means that the leader cannot no can no longer per perform his his his his duties in a reli ible fashion this is what we normally call split brain and the the thing is that there is really no good automatic way out of that okay you you have you have few have a few option ideally the member will come back from unreachable and then we actually remove him and things are fine then the cluster sort of heals itself but you need to have a Timeout on that of course that's basically the sort of the the quarantine in this in this in In The Swim failure detector that that that I told aled about so if if if if that is the case if it doesn't come back then we need to Mark the node as down if the node is marked as down then it's out of the picture again it can never join back and then the cluster can continue without that node or that set of nodes if if you have a network split like in the middle and we we used to have something called out to down as the default that means that the leader can actually take the action of saying I mean I'm I'm I will Auto down you I mean you're not with me any I mean part of the cluster any longer but but that had some I mean doing too much magic can sometimes be be confusing and in in large clusters where clients running mean few hundreds nodes it was actually hard to do that I mean hard to get get the configuration done right so it did that in a predictable fashion so now they we still have Auto down but but we have it off so we usually encourage you actually to have the SS admin go in and see what what what what really happened which part the cluster should I take down and so on or which node should I sh take take down because there if if you have a network split it might be 50/50 I mean it's you might have to like if if it's a 50 node cluster like taking down 25 nodes I mean probably need to sort of have some human intervention or or understanding of the problem okay so some some potential future optimization as I said we're looking into Vector clock pruning delegating heartbeat Allah swim where we actually can can can can sort of go check check around potential Network splits real push P gossip where we actually we haven't really had a need for that and what I mean by real is that where you actually do a hash of the of the data and only send the hashes around using like Merkel trees for example that like like they do in D in Dynamo we haven't really had that need because our data set is usually is fairly small and we use Mages on it as well and it it's it's it's it's a lot of redundant information all the nodes you know in the vector clocks is the same so so so sipping things up is usually very efficient so we haven't had a need for that yet but also more out of the box our autod down patterns that's something that I love would love to see people look into I mean from the community as well can we can we do autod down in such a reliable fashion that we can bring it back mean because I mean the more automatic things we can get adaptiveness into the system is better right so so finally I just want I want to talk about we have sort of built a bunch of high level modules on top of this so and and and some of the more in oops some of the more interesting ones are or that we have cluster Singletons that's pattern we built on top to ensure there's only one single actor in the whole system doing something we have cluster routers we we we take full advantage of the cluster to do routing when when you notes come up we just we just we just make sure that we we we create roues and we put them on these notes and same thing when when the when window those leave we can we can migrate them and and and allocate them somewhere else cluster Pub sub it's a very it's a very nice Pub P like publ subscribe sort of module on top we also have like a like a model for for like a model for consistent hashing that's actually a router a clustered uh router that that has an algorithm for for consistent hashing so we can bring we can bring that in there as well so AA persistence I I'm think I'm I'm going to I'm just going to skip just just some some of the road map before I close a HTTP is also distributed computing I think rest is definitely is a great way of doing distributive Computing and we we're adding a HTTP you know that's actually through spray through spray uh merger in that comes in AKA 24 another very interesting thing that is potentially distributed is is is AA streams initially we just we will just do like M like materialization of the streams like in in process but since it's all based on actors nothing prevents us from in the future making sure the streams work across machines in a very efficient way so you can like fan out Fanning merging all kinds of stuff and uh yeah that's basically we yeah that's basically what I want to say I just finally I just want to say once again please join us at react comp if you're interested in stuff like this and not just distribut Computing but also I mean concurrency and building really resilient stuff join us at react conf he in San Francisco he's actually at the comedy club over over on U it's pretty funny yeah it's true we at the comedy club over on down what's it called uh Columbus Avenue I think uh so check out the website to look who look who's speaking there so uh I'll be around afterwards for question I don't want to take up more of your time I always spoken for an hour now so so uh I hope this was somehow useful thank you I think we have time for questions we do okay we have time for questions at least a couple yeah can you talk about the limitations of crdts the limitations of C of crdts yes uh limitations of of of of state-based crdts as I said is is that it's it's hard to get around the problem of the growing of the history that means that as as you use the crdts it will get I mean the the the the state since this is fully self-contained that means that the state you need to replicate around will get bigger and bigger and bigger and bigger and bigger and and that that that might be a problem uh as I said there are interesting strategies for doing that for Vector clocks there have sort solved it but for the more complex crdts like graphs and so I haven't seen I haven't seen anything so that is an ongoing research for the the challenge is for for this Ops based C mrdt so the other is like CV rdt so the C CM cm rdts is that it relies like it it relies on a reliable broadcast channel that means that no messages can get lost right they you must ensure that that that every single operation State change operation that you do eventually reach all replicas else else it will be inconsistent and that and as we know that that that can be pretty hard to do mean give give those guarantees so so in a way I love the beauty of the of the state based ones but uh but they have their problems as well so so I I think we're not there yet but but but there's a there very interesting ongoing research around around that in general um so so we're just getting started yeah do you see any hope of fixing the Java GC problem that seems to be coming up more and more fixing the Java GC problems yeah that's I would love uh there's a lot of things I would like to fix in Java but there can be another talk uh yeah I don't have I don't know what to say about that without being very Politically Incorrect without taking up another hour so any other questions I I can also say regarding crdts we're actually they're not in AA yet but but but I started out with a with a project called AKA crdt about a year ago that was just a prototype and and Patrick nwell on the AKA team he he he he then he took some of those ideas and implemented them for real um it's called so there's a module now called AA data replication I think that that does weigh more than crdts but it's based on C on CRTs it's a very nice module for doing eventual consistent data replication so so please look at that if you're interested in these things and and contribute it it will most likely eventually make it into AA another thing I can also mention is there is an implementation in AA of raft Conrad another guy in the AKA team did that about about a year ago um I don't know if it's production quality yet but it's it's it's it's it's pretty interesting work that that might also make it into AKA eventually if it's picked up and used and and there's a need so there's a lot of things going on on different angles yeah time for one more question one more question okay so I'm new to this thing but just I had I have a question um can we uh when you see uh a crdp system which the consistency STS uh at that point of time can weally say the system is also ciz in terms of the DAT can we can somebody prove that or my instinction I I think it's it's true but I I I'm not sure but I think it should be true at I mean at that point it is it is fully consistent but but the thing is that it's it doesn't necessarily need to be consistent at specific point in time right because in in in in a fully eventual consistent there's no like snapshot you can just do a global snapshot and say everything is consistent at this point because because while while you're just checking that things will happen so so so so it's still a causally related consistency I'd say but but but yeah we can talk more about that offline I guess okay thank [Applause] you