System design basic - Unique ID generator

Common way to generate Unique ID in distributed system

In distributed system, it is not enough to rely on auto_increment provided by a transactional database.

multi-master replication:

Suppose we have k databases, each database increase by k, there will be no conflicts amoung IDs.

Pros:
    1. easy to implement
    2. solve some scalability issues
Cons:
    1. not scale well when new db added or removed.
    2. not time sensitive

UUID:

UUID is a 128-bit number unique ID. Can be used to generate ID independently without coordination between servers

Pros:
    1. easy to use
    2. easy to scale because do not need to synchronizae ID with other servers
Cons:
    1. fixed 128-bits long
    2. not time sensitive
    3. could be non-numeric

Ticket server:

Ticket server basiclly is a single Ticket server responsible for the ID generation, before insert into database, call Ticket server to get the unique id then store it.

pros:
    1. ID type can be customized.
    2. easy to implement and works fine with medium-scale applications.
Cons:
    1. single point of failure. If using multiple ticket server will introduce synchronization problems

snowflake:

Twitter's ID generation system called snowflake. It divide 64 bits into below:

| sign (1 bit) | timestamp (41 bit) | datacenter ID (5 bit) | worker ID (5 bit) | sequence ID (12 bit) |

sign is always 0 to represent positive number.
machine ID inclue datacenter ID + worker ID
sequence ID: For every ID generated on that machine/process, the sequence number is incremented by 1. The number is reset to 0 every millisecond.
In theory, a machine can support a maximum of 4096 new IDs per millisecond.