baidu/uid-generator

repository·master·Indexed 26 days ago

A Java-based unique ID generator implementing the Snowflake algorithm. It features a RingBuffer-based caching mechanism via CachedUidGenerator to achieve over 6 million QPS, making it suitable for high-concurrency and virtualized environments like Docker. The library supports customizable bit lengths for time, worker ID, and sequence, and provides a database-based worker ID assigner using a WORKER_NODE table.

Tokens: 4.3K
Snippets: 8
Records: 11
Agent score: 41%

What's inside uid-generator

Overview of UidGenerator
master
UidGenerator is a Java-based unique ID generator implementing the Snowflake algorithm. It is designed as a component for application projects and supports custom workerId bit lengths and initialization strategies, making it suitable for virtualized environments like Docker where instances may restart or drift.
Key features:
- Uses future time to overcome the concurrency limits of the sequence.
- Employs a RingBuffer to cache generated UIDs, parallelizing production and consumption.
- Uses CacheLine padding to avoid hardware-level 'false sharing' issues.
- Achieves a single-machine throughput of approximately 6 million QPS.
https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md

Setup WORKER_NODE table for WorkerID Assignment

master

If using the DisposableWorkerIdAssigner, you must create a WORKER_NODE table in your MySQL database to manage worker IDs. Replace xxxx with your actual database name.

DROP DATABASE IF EXISTS `xxxx`;
CREATE DATABASE `xxxx` ;
use `xxxx`;
DROP TABLE IF EXISTS WORKER_NODE;
CREATE TABLE WORKER_NODE
(
ID BIGINT NOT NULL AUTO_INCREMENT COMMENT 'auto increment id',
HOST_NAME VARCHAR(64) NOT NULL COMMENT 'host name',
PORT VARCHAR(64) NOT NULL COMMENT 'port',
TYPE INT NOT NULL COMMENT 'node type: ACTUAL or CONTAINER',
LAUNCH_DATE DATE NOT NULL COMMENT 'launch date',
MODIFIED TIMESTAMP NOT NULL COMMENT 'modified time',
CREATED TIMESTAMP NOT NULL COMMENT 'created time',
PRIMARY KEY(ID)
) 
 COMMENT='DB WorkerID Assigner for UID Generator',ENGINE = INNODB;

Setup WORKER_NODE table for MySQL

master

If using the built-in DisposableWorkerIdAssigner, you must create a WORKER_NODE table in MySQL to manage worker ID allocation. Run the following SQL script:

DROP DATABASE IF EXISTS `xxxx`;
CREATE DATABASE `xxxx` ;
use `xxxx`;
DROP TABLE IF EXISTS WORKER_NODE;
CREATE TABLE WORKER_NODE
(
ID BIGINT NOT NULL AUTO_INCREMENT COMMENT 'auto increment id',
HOST_NAME VARCHAR(64) NOT NULL COMMENT 'host name',
PORT VARCHAR(64) NOT NULL COMMENT 'port',
TYPE INT NOT NULL COMMENT 'node type: ACTUAL or CONTAINER',
LAUNCH_DATE DATE NOT NULL COMMENT 'launch date',
MODIFIED TIMESTAMP NOT NULL COMMENT 'modified time',
CREATED TIMESTAMP NOT NULL COMMENT 'created time',
PRIMARY KEY(ID)
) 
 COMMENT='DB WorkerID Assigner for UID Generator',ENGINE = INNODB;

After creating the table, ensure your mysql.properties file (or Spring datasource config) has the correct jdbc.url, jdbc.username, and jdbc.password.

Configure CachedUidGenerator in Spring

master

For performance-sensitive applications, CachedUidGenerator is recommended. It uses a RingBuffer to cache UIDs, allowing for over 6 million QPS.

Key configuration properties:

boostPower: Increases RingBuffer size (size = $2^{n + boostPower}$). Default is 3.
paddingFactor: The threshold (0-100) of available UIDs in the RingBuffer that triggers an in-time fill task. Default is 50.
scheduleInterval: The interval in seconds for periodic filling. If set, periodic filling is enabled.
rejectedPutBufferHandler: Policy for handling cases where the RingBuffer is full.
rejectedTakeBufferHandler: Policy for handling cases where the RingBuffer is empty.

<!-- CachedUidGenerator -->
<bean id="cachedUidGenerator" class="com.baidu.fsg.uid.impl.CachedUidGenerator">
    <property name="workerIdAssigner" ref="disposableWorkerIdAssigner" />
 
    <!-- The config below is option -->
    <!-- Specified bits & epoch as your demand. No specified the default value will be used -->
    <property name="timeBits" value="29"/>
    <property name="workerBits" value="21"/>
    <property name="seqBits" value="13"/>
    <property name="epochStr" value="2016-09-20"/>
    <!-- RingBuffer size, to improve the throughput. -->
    <!-- Default as 3. Sample: original bufferSize=8192, after boosting the new bufferSize= 8192 << 3 = 65536 -->
    <property name="boostPower" value="3"></property> 
 
    <!-- In-time padding, available UIDs percentage(0, 100) of the RingBuffer, default as 50 -->
    <property name="paddingFactor" value="50"></property> 
 
    <!-- Periodic padding -->
    <!-- Default is disabled. Enable as below, scheduleInterval unit as Seconds. -->
    <property name="scheduleInterval" value="60"></property> 
 
    <!-- Policy for rejecting put on RingBuffer -->
    <property name="rejectedPutBufferHandler" ref="XxxxYourPutRejectPolicy"></property> 
 
    <!-- Policy for rejecting take from RingBuffer -->
    <property name="rejectedTakeBufferHandler" ref="XxxxYourTakeRejectPolicy"></property> 
 
</bean>
 
<!-- Disposable WorkerIdAssigner based on Database -->
<bean id="disposableWorkerIdAssigner" class="com.baidu.fsg.uid.worker.DisposableWorkerIdAssigner" />

Configure DefaultUidGenerator in Spring

master

The DefaultUidGenerator is a standard implementation of the Snowflake algorithm. Use this bean configuration to specify custom bit lengths and the epoch.

Note: It requires a workerIdAssigner (such as DisposableWorkerIdAssigner) to manage worker IDs.

<!-- DefaultUidGenerator -->
<bean id="defaultUidGenerator" class="com.baidu.fsg.uid.impl.DefaultUidGenerator" lazy-init="false">
    <property name="workerIdAssigner" ref="disposableWorkerIdAssigner"/>

    <!-- Specified bits & epoch as your demand. No specified the default value will be used -->
    <property name="timeBits" value="29"/>
    <property name="workerBits" value="21"/>
    <property name="seqBits" value="13"/>
    <property name="epochStr" value="2016-09-20"/>
</bean>
 
<!-- Disposable WorkerIdAssigner based on Database -->
<bean id="disposableWorkerIdAssigner" class="com.baidu.fsg.uid.worker.DisposableWorkerIdAssigner" />

Configure DefaultUidGenerator

master

Use DefaultUidGenerator for standard requirements. It is simpler than the cached version but has lower throughput.

Configuration properties:

workerIdAssigner: Reference to the worker ID assigner (e.g., disposableWorkerIdAssigner).
timeBits: Number of bits for time.
workerBits: Number of bits for worker ID.
seqBits: Number of bits for sequence.
epochStr: The epoch string (e.g., "2016-09-20").

<!-- DefaultUidGenerator configuration example -->
<bean id="defaultUidGenerator" class="com.baidu.fsg.uid.impl.DefaultUidGenerator" lazy-init="false">
    <property name="workerIdAssigner" ref="disposableWorkerIdAssigner"/>

    <!-- Custom bits and epoch -->
    <property name="timeBits" value="29"/>
    <property name="workerBits" value="21"/>
    <property name="seqBits" value="13"/>
    <property name="epochStr" value="2016-09-20"/>
</bean>
 
<bean id="disposableWorkerIdAssigner" class="com.baidu.fsg.uid.worker.DisposableWorkerIdAssigner" />

Configure CachedUidGenerator

master

For high-performance requirements, use CachedUidGenerator. It uses a dual RingBuffer (one for UIDs, one for status flags) to improve throughput.

Key configuration properties:

boostPower: Increases RingBuffer capacity (default is 3, which scales the buffer by $2^N$).
paddingFactor: Percentage (0-100) of remaining slots that triggers automatic RingBuffer replenishment (default is 50).
scheduleInterval: Interval in seconds for periodic replenishment via a scheduled thread (default is not configured).
rejectedPutBufferHandler: Strategy for when the RingBuffer is full (default: discard put and log).
rejectedTakeBufferHandler: Strategy for when the RingBuffer is empty (default: log and throw UidGenerateException).

<!-- CachedUidGenerator configuration example -->
<bean id="cachedUidGenerator" class="com.baidu.fsg.uid.impl.CachedUidGenerator">
    <property name="workerIdAssigner" ref="disposableWorkerIdAssigner" />
 
    <!-- Optional configurations -->
    <property name="timeBits" value="29"/>
    <property name="workerBits" value="21"/>
    <property name="seqBits" value="13"/>
    <property name="epochStr" value="2016-09-20"/>
 
    <!-- RingBuffer expansion parameter -->
    <property name="boostPower" value="3"></property>
 
    <!-- Threshold for automatic replenishment (percentage)
         Example: bufferSize=1024, paddingFactor=50 -> threshold=512 -->
    <property name="paddingFactor" value="50"></property>
 
    <!-- Periodic replenishment interval in seconds -->
    <property name="scheduleInterval" value="60"></property>
 
    <!-- Strategy when RingBuffer is full -->
    <property name="rejectedPutBufferHandler" ref="XxxxYourPutRejectPolicy"></property>
 
    <!-- Strategy when RingBuffer is empty -->
    <property name="rejectedTakeBufferHandler" ref="XxxxYourTakeRejectPolicy"></property>
</bean>

<bean id="disposableWorkerIdAssigner" class="com.baidu.fsg.uid.worker.DisposableWorkerIdAssigner" />

Generate and Parse UIDs with UidGenerator

master

Once the UidGenerator is injected into your Spring component, you can use getUID() to generate a unique ID and parseUID(long uid) to decompose it into its constituent parts (Timestamp, WorkerId, and Sequence).

@Resource
private UidGenerator uidGenerator;

@Test
public void testSerialGenerate() {
    // Generate UID
    long uid = uidGenerator.getUID();

    // Parse UID into [Timestamp, WorkerId, Sequence]
    // Example Output: {"UID":"180363646902239241","parsed":{ "timestamp":"2017-01-19 12:15:46", "workerId":"4", "sequence":"9" }}
    System.out.println(uidGenerator.parseUID(uid));
}

Use UidGenerator API

master

Once configured in your Spring context, you can inject the UidGenerator and use its methods to generate and parse unique IDs.

getUID(): Generates a new unique long ID.
parseUID(long uid): Parses a UID into its components: timestamp, workerId, and sequence.

@Resource
private UidGenerator uidGenerator;

@Test
public void testSerialGenerate() {
    // Generate UID
    long uid = uidGenerator.getUID();

    // Parse UID into [Timestamp, WorkerId, Sequence]
    // Example output: {"UID":"180363646902239241","parsed":{ "timestamp":"2017-01-19 12:15:46", "workerId":"4", "sequence":"9" }}
    System.out.println(uidGenerator.parseUID(uid));
}

Snowflake Algorithm Bit Allocation
master
The Snowflake algorithm generates a 64-bit unique ID (long) based on the machine, time, and a concurrency sequence. The default bit allocation is:
- sign (1 bit): Fixed bit to ensure the UID is a positive number.
- delta seconds (28 bits): Milliseconds relative to the epoch "2016-05-20". Supports approximately 8.7 years.
- worker id (22 bits): Machine ID. Supports up to ~4.2 million machine starts. The built-in implementation allocates this from a database at startup.
- sequence (13 bits): Concurrency sequence per second. Supports up to 8,192 concurrent IDs per second.
Note: All these parameters can be customized via Spring configuration.
https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md
Understand the Snowflake ID Structure
master
UidGenerator uses a Snowflake-based algorithm to generate 64-bit (long) unique IDs. The ID is composed of the following bit segments:
- sign (1 bit): The highest bit is always 0.
- delta seconds (28 bits): Represents delta seconds since the customer epoch (default: 2016-05-20). Maximum duration is approximately 8.7 years.
- worker id (22 bits): Represents the worker node ID (max value: 4.2 million). By default, it uses a database-based worker id assigner that disposes of previous IDs after a reboot.
- sequence (13 bits): Represents the sequence within one second (default max: 8192 per second).
These parameters (timeBits, workerBits, seqBits, and epochStr) can be customized in your Spring bean configuration.
https://github.com/baidu/uid-generator/blob/master/README.md