Contract Work

Sunday, March 30, 2014

Convergent/Divergent


This talk was crazy. It was really academically intense and while I was able to follow the basic ideas, there was a lot of important information and concepts that were ran through really quickly. Fortunately, it seemed like most of the conference participants also thought this talk was also presented really quickly, so I wasn’t alone on this. Also, every time I went to write a note, I feel like I missed the next two points and came back into the conversation on the third, so hopefully those notes don’t seem really disjointed. I will say that Chris seems like a really smart, nice dude so it’s definitely worth connecting with him for more details on this if you want to dive into it more.

There are distributed computing issues and you’re building a distributed system. Basically, if you’re pushing state to the client, it means you’re caching validations which can lead to consistent data issues and more. This is an issue regardless of the database you’re using and this fact means you’re building a distributed system.

Some of the main issues are dropped messages, rendered messages, race conditions, partial failures, and custom merges. There are TCP incast, TCP slow-start, and Nagle’s algorithm… these are cases of latency spikes… I think.

Then he went a little into distributed systems theory and consistency. Consistency is a contract and if developers follow the contract then there will be predictability. There are three kinds of consistency. Strict linearizable which is the total order of all events in a system and for single servers. Then there’s eventual consistency which means you eventually see all the events. It is a weaker form of consistency. Finally, there’s causal consistency which is basically, I observe an update immediately but another person may see the change a little later. When dealing with consistency, it comes down to safety vs. liveness.

You need consensus to deal with consistency. For consensus, you’re basically looking at termination, agreement, and validity. Termination means eventually the info will show. Agreement means it will all have the same value. Validity is that the value will be part of consensus. It comes down to a generals problem which are academic concepts. There’s two generals or the Byzantine generals. There are algorithms used to solve this. Some of those algorithms are paxos, raft, 2pc, and 3pc.

I’m not sure how this lead into vector clocks but then we discussed vector clocks whick allow us to define all possible orderings in a system. There are also dotted version vectors which are things having to do with events and actors.

We then went into CRDTs. CRDTs are conflict free replicated data types. These are data structures that store something. There are two types of CRDTs: state based and operations based. State based CRDTs have monotonicity which means functions where as inputs increase, outputs increase. We care about associativity (which is a binary operation… addition is associative), community (also a binary function, addition is also commutable), and idempotence (also a binary function). All three of those exist in programming.

If that wasn’t quite enough for you, we then spoke about bounded join semilattices… which is another math term, but this one has a decent diagram in the slides so check that out.

So, why is all of this important? Because consensus is hard. We want to avoid coordination so the system can progress and we want a weak consistency and higher availability. The conclusion is that you’re building a distributed system so you need to be thinking about this.

No comments:

Post a Comment