Globally monotonic identifiers (IDs)

Xu (vol. 1), ch. 7 is dedicated to a very interesting problem: building a distributed identifier generator that is globally monotonic in its sort order. He identifies four strategies.

Twitter’s “Snowflake” method

The recommended strategy is based on a strategy called “Snowflake,” which Twitter published as a very short blog post in 2010. It has been so successful that it has its own Wikipedia page as a simple, sortable global ID. It draws on the above concept, but distills it to the components relevant to one organization running across datacenters:

1. Monotonic timestamp
2. Machine ID
3. Datacenter ID
4. Locally generated sequence number

Other strategies

Xu first gives three other strategies: multi-leader replication, UUIDs, and a centralized ID service (“ticket server”).

Multi-leader approach: Assign a number to each of leaders in a multi-leader distributed data store such that . That leader’s auto-increment starts with and then increases by , such that the -th ID for leader is given as . This breaks as soon as you add or remove a leader, and it requires a lot of communication.

UUIDs: Not monotonic, not numeric, and has to be a specific length (128 bits).

Centralized service: Single point of failure. Providing redundancy turns this into the multi-leader approach.