Unique Serial Number Generation

This document introduces the unique serial number generation scheme to help developers who generate their own unique IDs.

Auto-increment column

AUTO_INCREMENT is a column attribute of many RDBMSs that are compatible with the MySQL protocol. With the AUTO_INCREMENT attribute, a database can automatically assign values to this column without user intervention. As the number of records in the table increases, the value of this column automatically increments and are guaranteed to be unique. In most scenarios, AUTO_INCREMENT columns are used as proxy primary keys with no actual meaning.

The limitation of AUTO_INCREMENT columns is that the column must be of the integer type and the values assigned to them must be integer. If the serial numbers required by the application are sliced by letters, numbers, and other characters, it is difficult for the user to get the auto-increment numbers required in the serial number through the AUTO_INCREMENT column.

Sequence

A Sequence is a database object that an application can invoke to produce incremental sequence values. Applications can flexibly use the sequence values to assign values to one or more tables. Applications can also use the sequence values for more complex processing to produce a combination of text and numbers. This approach gives some tracking and classification meaning to proxy keys.

Sequence is available starting with TiDB v4.0. For details, refer to sequence documentation.

Snowflake-like solutions

Snowflake is a distributed ID generation solution proposed by Twitter. There are several implementations, the more popular ones are Baidu’s uid-generator and Meituan’s leaf. This section uses uid-generator as an example.

The 64-bit ID structure generated by uid-generator is as follows:

| sign | delta seconds | worker node id | sequencs |
|------|---------------|----------------|----------|
| 1bit |     28bits    | 22bits         | 13bits   |

• sign: Fixed length of 1 bit. Fixed to 0 to indicate that the generated ID is always a positive number.
• delta seconds: 28 bits by default. The current time, presented as an incremental value in seconds relative to a preset time base (defaults to 2016-05-20). 28 bits can support up to about 8.7 years.
• worker node id: 22 bits by default. Represents the machine ID, usually obtained from a centralized ID generator when the application process is started. Common centralized ID generators include auto-increment columns and ZooKeeper. The default allocation policy is discard-as-you-go, and the process re-acquires a new worker node ID on restart. 22 bits can support up to about 4.2 million starts.
• sequence: 13 bits by default. The sequence of concurrency per second. 13 bits can support 8192 concurrent sequences per second.

Number allocation solution

The number allocation solution can be understood as bulk acquisition of auto-increment IDs from the database. This scheme requires a sequence number generation table, with each row representing a sequence object. An example of table definition is as follows:

Every time, the application gets a segment of sequence numbers at the configured step. It updates the database at the same time to persist the maximum value of the current sequence that has been allocated. The processing and allocation of sequence numbers are completed in the application’s memory. After a segment of sequence numbers is used up, the application gets a new segment of sequence numbers, which effectively alleviates the pressure on the database write. In practice, you can also adjust the step to control the frequency of database updates.

Finally, note that the IDs generated by the above two solutions are not random enough to be directly used as primary keys for TiDB tables. In practice, you can perform bit-reverse on the generated IDs to get more random new IDs. For example, after performing bit-reverse, the ID 00000010100101000001111010011100 becomes 00111001011110000010100101000000, and 11111111111111111111111111111101 becomes 10111111111111111111111111111111.