Synchronisation and ordering in distributed systems

Question

I have been wondering, what are some ways to handle synchronisation and/or sequencing issues in distributed systems. For example, assume multiple homogeneous nodes listening on a stream of messages and updating a data store based on those messages. Let's say 2 updates for a particular record enter the queue, one at t1 and the other at t2 (t2 > t1). Further, the t1 packet is consumed by a node n1 and the other one by n2. Now, what would happen if due to computational or network latencies, n2 processes the packet earlier than n1 and updates the data store. Since n1 has an older update, it should not update the data store.

One way I can think of, is to maintain a per attribute versioning of the record and generate a sequence number for each message based on which updates should be made. We could also use timestamps but we would run into issues if the clocks across the nodes drift.

Is there a standard universal way of tackling these sequencing issues? Is this what ZooKeeper does? Are there any interesting reading materials on this topic?

Answer 1

At a high level, you are considering consistency models (@wiki) in distributed systems, like a distributed replicated data store in your example. Consistency models specify what values may be returned by a read given that memory operations may only be partially ordered. Note that this has imposed restrictions on the order in which all the operations are performed.

There are lots of different consistency models, as indicated in the wiki article. Informally each of them defines a partial order over the operations. One of the common implementation methods is to utilize broadcast service. Not surprisingly, there are various broadcast service with different ordering (what you are probably interested in) and reliability (concerning fault tolerance) requirements. The following description is quoted from Chapter 8 "Broadcast and Multicast" of the book "Distributed Computing: Fundamentals, Simulations, and Advanced Topics (2nd Edition) By Hagit Attiya and Jennifer Welch. 2004.":

Ordering: Do processes see all messages in the same order or just see the messages from a single process in the order they were sent? Does the order in which messages are received by the broadcast service preserve the happens-before relation?

Reliability: Do all processes see the same set of messages even if failures occur in the underlying system? Do all processes see all the messages broadcast by a nonfaulty process?

---

This Technical Report: A Modular Approach to Fault-Tolerant Broadcasts and Related Problems; 1994 gives a more comprehensive formal framework of broadcast service. It has also related the consensus problem with atomic broadcast. Consensus is also popular in distributed data storage systems, by implementing a replicated state machine.

---

As for your comment:

I would also be interested in any implementations of these which are in production or used by large scale companies?

Most distributed storage systems have considered such consistency models issues and their implementations. Again, different storage systems are targeted for different application scenarios, and thus adopt different consistency models and implement different ordering strategies.

I will name a few keywords and it is not difficult for you to find papers or articles about them: Amazon's Dynamo, Yahoo!'s PNUTS, Google's Bigtable, ZooKeeper, COPS@SOSP'11, Cassandra, HBase, ...