Focusing on Causality

Some applications need that events be given identifiers that is not only unique but also 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 (There are many subtleties associated with both of them. See the following optional text “Time in a Distributed System”). Some systems have additional requirements that event identifiers’ causality maps to 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 any anomalies during high-volume / high-speed market trades.

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

Using UNIX timestamps

The UNIX timestamps are granular to the second, and we can use them to distinct the events. We have an ID Generating Server that can generate one ID in a single second. Any request to generate a unique ID is routed to that server, and it returns a timestamp, and we have a unique ID.

But we are expecting to handle billions of users, so using a single second will be inefficient. We can use nanoseconds instead.

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

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 nanosecond. 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 shown below:

Though the approach is simple, scalable, and easy to implement, and multiple servers handle concurrent requests, but this approach won’t work in our case. Firstly, IDs are generated in a dead period. The dead period is when no request for generating an ID is made to the server. These IDs will be wasted as they will eat up our identifier space, the unique range possible will deplete earlier than expected, and also create gaps in our global set of user IDs.

Moreover, the weak point of this system is its reliance on time. Network Time Protocol (NTP) can affect the working of this system. If the clock on one of the servers drifts 2 seconds in the future, other servers are 2 seconds behind. The NTP clock recognizes it and recalibrates its clock. Now all serves will be aligned. But in that drifting process, the IDs could have been generated which were of future, and now we will have two pairs of users with the same identifier. The IDs are no more unique. Lastly, the causality of our events won’t be maintained.

The Network Time Protocol (NTP) is a networking protocol for clock synchronization between computer systems over packet-switched, variable-latency data networks. NTP intends to synchronize all participating computers within a few milliseconds of Coordinated Universal Time (UTC). It mitigates the effects of variable network latency.

Having accurate time still remains an issue. We can read a machine’s time-of-day clock with microsecond or even nanosecond resolution. Even with this fine-grained measurement, the danger of NTPNTP servers can be susceptible to man-in-the-middle attacks unless packets are cryptographically signed for authentication. The computational overhead involved can make this impractical on busy servers, particularly during denial of service attacks. NTP message spoofing from a man-in-the-middle attack can be used to move clocks on client computers and allow several attacks based on bypassing cryptographic key expiration. Some of the services affected by fake NTP messages identified are TLS, DNSSEC, various caching schemes (such as DNS cache), BGP, Bitcoin, and many persistent login schemes. remains. Since we cannot rely on physical clocks, let’s put logical clocks to use.

Using logical clocks

We can utilize logical clocks (Lamport and vector clocks) that need monotonically increasing identifiers ...