Design a system to generate a Unique ID

A database table with more than one rows needs a unique primary key for each row. Since data are partitioned across different shards therefore we need to generate a globally unique ID for the primary key.

Following are a few ideas to generate the primary key.

Random Id

We can generate a fixed length of a random number and use it as a primary key. However, due to high collision, this is not all a great fit for UUID.

Hashing

We can take input for each row and create a hash out of it. for

a. md5 hash: It generates 128 bits hash value i.e. 16 octets i.e. 32 hexadecimal digits. For example 9e107d9d372bb6826bd81d3542a419d6 .

b. Sha1 hash: It generates 160 bits hash value i.e. 20 octets i.e. 40 hexadecimal digits. For example 2fd4e1c67a2d28fced849ee1bb76e7391b93eb12 .

c. Sha2 hash: It consists of various hash functions for example Sha-224 (56 hexa digits), Sha-256 (64 hexa digits), Sha-384 (96 hexa digits), Sha-512 (128 hexa digits).

Since hash functions generate long id therefore generally not suitable for UUID. Though it reduces collision it's not 100% collision-free therefore not a recommended UUID. This is sometimes used if there is a need for deterministic UUID.

UUIDv1(Timestamp + Random number + host)

UUIDv1 uses this pattern to generate the ID.

a. Timestamp: This is a 60-bit value representing the number of 100-nanosecond intervals since a specific point in time.

b. Random number: A 14-bit random number helps ensure uniqueness even if multiple UUIDs are generated very close together in time.

c. Host identifier: This is typically a 48-bit value derived from the device’s network interface card’s Media Access Control (MAC) address. It helps differentiate UUIDs generated on different machines.

Time ordering: UUIDv1 timestamps allow for some ordering based on creation time. This can be helpful for certain applications like logging.

Cons:

a. Potential security risk of exposing MAC address.

b. A small chance of collision.

c. Time ordering creates a hotspot in a sharded database.

UUID Generation service using database auto-sequence

We can leverage the database-supported auto sequencing to generate the UUID.

A single database is not fault-tolerant therefore we can have two standalone databases as below.

1. The first database will generate the odd sequence.
2. The second will generate the even sequence.
3. The load balancer will distribute traffic to these two databases.
4. If one database is down then the load balancer will send traffic to the active database.
5. We can also use a replica set for each odd/even to improve the fault tolerance.

To increase the fault tolerance we can extend this design to use n databases.

Cons

• Write will be slow for high traffic.

UUID Generation service using pre-generated blocks

Local counter

Every app server can maintain a local counter=0 and simply keep incrementing it to generate the ID. But this has a problem as multiple App servers will generate the same ID as everyone starts with counter=0 .

Blocks of counter powered by database auto-sequencing

1. Every time the app server restarts will ask the database to give the new UUID block.
2. The app server will simply keep incrementing it to generate the UUID.
3. If the app server exhausts the ID block then it again asks the database to return the next block.

Problem with sequential UUID as Primary key

If we generate a monotonic increasing integer as the primary key then the row will always be inserted at the end of the same shard. This will create a hotspot to handle high write volume. Therefore it is not a good idea to use monotonic increasing integer as a primary key.

Approach #1: Hash the ID and use key=hash+id

A common technique to spread the load across the multiple shards is to hash the actual unique key and use primary key = hash + unique id .

Pros:

1. Helps to spread the rows across the shards to avoid hotspots on high volume.

Cons:

1. Can’t do efficient range reads of the original unique key.

Approach #2: Hash the ID and use two columns HASH and ID as composite primary key

We can write hash and ID as separate columns and use these two columns as a composite primary key order as (hash, ID).

For example, to spread writes for different users to the timestamp-ordered UserLogs the table across 100 shards, we can use a composite primary key as <ShardId, Timestamp, UserId> . Here ShardId is acting as a hash.

Note: Based on the database solution ShardId can be automatically created by the Database as per the available shards therefore it might not be known to you at the time of read.

Now we can run the query as below if you know the hash algorithm.

SELECT * 
FROM UserLogs
WHERE Timestamp > X AND ShardId = MOD(UserId, 100);

If not then you can run blindly on all the shards as below.

SELECT * 
FROM UserLogs U, (GENERATE_ARRAY(0,99) S
WHERE Timestamp > X AND ShardId = S.VALUE

Approach #3: Bit reversed sequence

The following are steps.

1. Generate monotonic increasing ID, let’s call it X (preferably odd sequence)
2. Reverse the bit and get Y (one option is to reverse the order of the bits in the 2’s complement binary representation of X).
3. Use Y as a primary key.
4. User-visible IDs (which we want to increase in value) can be generated from the same bit-reversed sequence by bit-reversing the primary key again.

Following are examples using 4 bits to show how bit reversal helps to break monotonicity which helps to shard data.

Sequence        Bitreversal
0001 (1)        1000 (8)
0010 (2)        0100 (4)
0011 (3)        1100 (12)
0100 (4)        0010 (2)
0101 (5)        1010 (10)
0110 (6)        0110 (6)
0111 (7)        1110 (14)
1000 (8)        0001 (1)

Primary Key using Commit timestamp

If the database provides the commit timestamp after a transaction is committed then we might want to use the CommitTimestamp as a primary key.

Since the timestamp is monotonic increasing the number therefore it will lead to a hotspot on high load.

We can solve this problem as similar to what we discussed above. Following is a summary.

Approach # 1: Hash the key and spread writes among N Shards

To divide the work among N servers, create N shards and maintain shard details in a separate table.

ShardId (PrimaryKey=<ShardId>)
1
2
3
.
.
N

Generate ShardId using hash(userId)%N or any other suitable data. Then create UserLogs as below.

ShardId  Timestamp UserId PrimaryKey = <ShardId, Timestamp>
1        12345     1 
2        12346     1
3        12347     1
1        12348     2
3        12349     2
4        12310     1
4        12311     2

Approach # 2: Swap the order for timestamp with leading key with high cardinality

Let’s say if we know that UserId has high cardinality then we can swap the primary key as <UserId, Timestamp> and drop the ShardId .

UserId Timestamp (Primary Key = <UserId, Timestamp>)
1      12350 
1      12351
1      12352
2      12310
2      12311
2      12312
1      12353

Now the insertion to shard is based on UserId, not the timestamp. Now writing will spread among N shards.

If the leading Primary key is low cardinality then it will lead to a hotspot on high load.

Another disadvantage of this approach over #1 is that it’s harder to read a sequence of records in order of commit timestamp. For example, find all the records that were added since the time T .

Happy learning :-)