Lazy Replication in a Distributed System.

I am inspired to write about replication in the back-end servers after robustly implementing Lazy replication in my Distributed micro-blogging service. I.e, Data Servers/ Replica Managers synchronize themselves by Lazy replication, also called as Gossip replication.

The other two types of replication strategies(active and passive) provide fault tolerance and strong consistency(immediately synchronizing before responding to a client request) but I preferred to trade latency for strong consistency. Hence I implemented Lazy replication to get a highly available service (immediately return responses and synchronize later) which will be eventually consistent.
Note: I used JSON for communication everywhere in the system.

DATA SERVERS/REPLICAS SYNCHRONIZATION.
* Replicas synchronize with each other through gossip mechanism/messages.
* A gossip message contains a log of past updates and a vector timestamp, which is the vector clock. I differentiated delete updates from others with the help of a flag.
* When a Gossip message is received, the receiver applies all stable updates.
* After four rounds of Gossiping the Data Server removes entries from the log table(and frees up the memory) that are known to have been applied everywhere, which is determined by the help of vector clocks received from all the servers.

DATA SERVER & HTTP SERVER COMMUNICATION.
The Http server associates a vector timestamp with each query when communicating with a Data server. The Data server also returns its vector timestamp to the front end Http server. Note that each update/log will also have a unique identifier.
* If the http server:timestamp <> data server:timestamp, the data server queues the query until it has received enough gossip messages to sufficiently update its state.
* The http server sends heartbeat messages once in a while to keep track of newly added replica managers.

I balanced the load by randomly selecting a data server to communicate from the http server. When that data server fails, the http server adds it in its dead list and selects an other available data server. In a system with N data storage servers, the system will tolerate the failure of up to N-1 nodes. As long as one data storage server is available, a client request will succeed. In the data returned by the back-end the events will be causally ordered with the help of vector clock timestamps, which means that updates that were initially handled by the same back-end will be in chronological order. Feel free to ask if you have any questions!