9 hours ago
- The algorithm generates monotonically increasing IDs using a majority of nodes with a 'current' key.
- It requires a data store supporting set_if_less_than and fsync on writes.
- Safety: It's impossible for two clients to generate the same ID or for a new ID to be less than a past ID.
- Liveness issue: concurrent accesses cause retries and 'holes' in the sequence.
- Performance is slow due to retries, but can be improved by a mediating ID server.
- Fsync is necessary to prevent ID regression after node restarts.
- The IDs provide total ordering useful for merging events across distributed processes.
- The algorithm resembles Paxos first phase and Raft leader election.