Distributed Systems Algorithms in practice

In Distributed Systems, Software Development, web application by Prabhu Missier

Let’s assume you have a few servers in a data center which serve as a proxy for some target servers located somewhere on the internet. The proxies would need to know the health status of the target servers before they load balance requests. But if each of the proxies kept sending out requests to all the target servers every few milliseconds then this would constiture a DDOS attack.

Enter the Rendezvous algorithm

h(Si, T1) = { S2, S4, S2, S3};

This is in effect means that for a given target server there’s an ordered list of servers that would do the health check. So in this case for target T1, the server that would be in charge of pinging it for a health check would be S2. If S2 is unavailable then S4 would be next in line to do the check.

Let’s now talk about failure detection.

Since all servers in the set Sn where i = 1 to 100 are now sharing the load of health checks between them, there needs to be a way to ensure communication between them. Enter the SWIM algorithm. Let’s say server S1 tries to ping server S93 which it already knows about and there’s a response. It then broadcasts this info to it’s peers. When there’s no response from S93 it then asks its peers S12 and S4 to check on S93 and they get back on S93’s status. So in effect S1 doesn’t have to do a health check on all other servers in the set. The work is shared.

This is a good time to also talk about the communication using the “Gossip” protocol where a server might push information to a random subset of its peer servers or even pull information explicitly from its peer servers. Both approaches are similar in terms of complexity but have their advantages and disadvantages.

How does the system converge?
So different servers in the system have partial information about the system. One approach to converge and collate all this information is to use version vectors and the concept of lattices. So for eg. Assuming there are 3 servers at time t1, server S1 has information about events it has seen so the version vector would be {1, 0 , 0}. At time t2, server S2 has information about events it knows but now it also has information about S1 events which occurred at t1. So the version vector becomes {1,1,0}. At t2 server S3 has information about events which concurrently occurred but it knows nothing about the S1 and S2 events. Moving forward at time t3, server S2 will now have information about events occurring at t1, t2 and t3 so the version vector becomes {1,1,1} very much like a lattice.

Let’s now talk about CRDT maps – conflict free replicated data-types or delta CRDTs. Assume 2 servers are maintaining state and server S1 now shares its world view with server S2. Server S2 also has system state information some of which might overlap with S1 but it then identifies the delta or the information that’s different from what S1 has and sends it back to S1. Now this being a lattice the delta can be merged back into S1’s world view for a complete picture of the entire system. So rather than exchange the entire system state maintained by S2, what get’s sent across to S1 is just the delta difference.
In the scenario where 2 or more servers might present state information about the system how does the merge happen? The Rendezvous algorithm comes to the rescue here and helps in conflict resolution since we now know from the priority list which server should be contacted first to read state information.

So that’s it folks. A very high level article about some of the distributed algorithms in practice. Reach out to us if you need more info.