Unique IDs with Causality

Causality

In the previous lesson, we generated unique IDs to differentiate various events. Apart from the identification of events, we are also interested in finding the sequence of these events. Let’s consider an example where Peter and John are two Twitter users. John tweets on a Twitter 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 concurrent 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 Twitter 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.

The above scenario can also be handled by assigning a unique ID and encoding the dependence of events using a social graph. We might also use a separate time data structure and a simple, unique ID. However, we want a unique ID to do the double duty—unique identification and also helping with the causality of events.

The following slides provide a visualization of concurrent and non-concurrent events.

Some applications need that events to be given unique identifiers and carry any causality information. An example is giving an identifier to the concurrent writes of a key into a key-value store to implement the last-write-wins strategy.

We can either use logical or physical clocks to infer causality. Some systems have additional requirements where we want event identifiers’ causality to map wall-clock time. An example is a financial application complying with European MiFID regulations. MiFID requires clocks to be within 100 micro-seconds of UTC to detect anomalies during high-volume / high-speed market trades.

There are many subtleties associated with logical or physical clocks. See the following optional text, “Time in a Distributed System,” to refresh your concepts of time.

We use the time to determine the sequence of events in our life. For example, if Sam took a bath at 6 A.M. and ate breakfast at 7:00 A.M., we can determine that Sam took a bath before breakfast by timestamps of each event. Timestamps, therefore, can be used to maintain causality.

Using UNIX timestamps

The UNIX timestamps are granular to the milli-second, and we can use them to distinguish the events. We have an ID Generating Server that can generate one ID in a single millisecond. Any request to generate a unique ID is routed to that server, and it returns a timestamp, and we have a unique ID. Generating in milliseconds allows us to generate a thousand identifiers per second (that means we can get $24 (hour)* 60 (min/hour) * 60 (sec/min) * 1000 (ID/sec) = 86400000 IDs$ in a day). That is less than a billion per day.

Connect to the following terminal to view the UNIX timestamp in milliseconds.

So our system works well with generating IDs, but it has a crucial problem. The ID Generating Server is a single point of failure (SPOF), and we need to handle it. To cater to SPOF, we can add more servers. Each server generates a unique ID for every millisecond. To make the overall identifier unique across the system, attach the server ID with the UNIX timestamp. Add a load balancer to distribute the traffic efficiently. The design is below:

Pros

The approach is simple, scalable, and easy to implement, and multiple servers handle concurrent requests.

Cons

For two concurrent events, the same timestamp will be returned and the same ID can be assigned to them. This way the IDs are not unique anymore.

Twitter snowflake

Let’s try to use time efficiently. We can use some bits (out of our targetted 64 bits) for storing time and the remaining for other information. An overview of division is:

The explanation of the division of the bits is as follows:

• Sign bit: A single bit is assigned as a sign bit, and its value will always be 0. It makes the overall number positive. Doing so helps to ensure that any programming environment using these identifiers interprets them as positive integers.

• Timestamp: 41 bits are assigned for milliseconds. The Twitter snowflake default epoch will be used. Its value is 1288834974657 which is equivalent to Nov 04, 2010, 01:42:54 UTC. (We can initiate our own epoch when our system will be deployed, say 2022-01-20 at 12 midnight can be the start of our epoch ...