System Design - ID
Global Lock and Single Master
We can enforce a single global master that take care of unique ID generation. This can be a traditional SQL database that atomically increments primary key columns. But it needs locking during incrementing, so soon we will have scalability issues.
For auto-increment IDs, the latest value need to be persisted, otherwise the state will be lost upon restart.
If not auto-increment, the IDs need to be stored so no same ID will be used again in the future.
Unique ID
E.g. UUID:
- 128bit
- completely stateless, no coordination needed, multiple nodes can generate IDs at the same time
- no guarantee of uniqueness
- type 4: random
- type 1: MAC address + time component
- nothing to store on disk so we can go as fast as our CPU can go
http://engineering.intenthq.com/2015/03/icicle-distributed-id-generation-with-redis-lua/
https://segment.com/blog/a-brief-history-of-the-uuid/
Improvements to UUID
- GTID: Global Transaction Identifier
- Twitter Snowflake
- Cassandra TimeUUID
- KSUID: K-Sortable Globally Unique IDs
- K-ordering is a more precise way of saying roughly sorted.
- Github: https://github.com/segmentio/ksuid
Timestamp Does Not Work In Distributed System
Timestamp is not reliable in distributed environment. Computer clock is constantly skewing forwards or backwards away from the actual time(called "clock drift"), and every computer skews at a different rate.
Cannot use timestamp as id, or for ordering. Unless servers are perfectly synchronized.
Generate Unique ID: http://antirez.com/news/99
A centralized clock system would be a single point of failure. The dedicated servers(called "time oracle") normally equipped with an atomic clock or GPS to keep time as precise as possible. Often used in trading platforms where super accurate time is important.
So it is not impossible, but could be very expensive. Google has its own highly available, distributed clock called TrueTime, it guarantees to generate monotonically increasing timestamps. It serves all Google's internal services and Cloud Spanner in GCP.
https://cloud.google.com/spanner/docs/true-time-external-consistency
id / sequence generator
A sequence generator that’s safe across a distributed system: have a table in Cloud Spanner contain a row for each required sequence that contains the next value in the sequence, e.g.:
CREATE TABLE Sequences (
Sequence_ID STRING(MAX) NOT NULL, -- The name of the sequence
Next_Value INT64 NOT NULL
) PRIMARY KEY (Sequence_ID)
When a new ID value is required, the next value of the sequence is read, incremented and updated in the same transaction as the insert for the new row.
This will limit performance when many rows are inserted, as each insert will block all other inserts due to the update of the Sequences table that we created above.
This performance issue can be reduced — though at the cost of possible gaps in the sequence — if each application instance reserves a block of, for example, 100 sequence values at once by incrementing Next_Value by 100, and then manages issuing individual IDs from that block internally.