Distributed Unique ID Generator (Sequencer)

Motivation

There can be millions of events happening in a large distributed system. Commenting on a post on Facebook, sharing a tweet, posting a picture on Instagram are just a few examples of such events. We need a mechanism to distinguish these events from each other. One such mechanism is the assignment of globally unique IDs to each of these events.

Apart from identification, we are also interested in finding the sequence of these events. Let’s consider an example where Peter and John are two Facebook users. John comments on a Facebook post (event A), and Peter replies to John’s comment (event B). Event B is dependent on event A and cannot happen before it. The events are not concurrentLeslie Lamport’s landmark paper’s (Time, Clocks, and the Ordering of Events in a Distributed System) major contribution was that how we can infer potential causality between events in a distributed system without wall-clock time. In that context, two events are concurrent if they have no causal connection (i.e. neither those two events happened on the same process nor are they related in any network message as direct/in-direct sender or receiver). here.

We can also have concurrent events, i.e., two events independent of each other. For example, if Peter and John comment on two different Facebook posts, there is no happened-before relationship (causality) between them. It is essential to identify the dependence of one event over the other but not in the case of concurrent events.

A real-time scenario of unique ID usage is Facebook’s end-to-end performance tracing and analysis system, ...