• Stars
    star
    5,429
  • Rank 7,570 (Top 0.2 %)
  • Language
    Java
  • License
    Apache License 2.0
  • Created over 7 years ago
  • Updated over 1 year ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

UniqueID generator

UidGenerator

In Chinese 中文版

UidGenerator is a Java implemented, Snowflake based unique ID generator. It works as a component, and allows users to override workId bits and initialization strategy. As a result, it is much more suitable for virtualization environment, such as docker. Besides these, it overcomes concurrency limitation of Snowflake algorithm by consuming future time; parallels UID produce and consume by caching UID with RingBuffer; eliminates CacheLine pseudo sharing, which comes from RingBuffer, via padding. And finally, it can offer over 6 million QPS per single instance.

Requires:Java8+, MySQL(Default implement as WorkerID assigner; If there are other implements, MySQL is not required)

Snowflake

Snowflake
** Snowflake algorithm:** An unique id consists of worker node, timestamp and sequence within that timestamp. Usually, it is a 64 bits number(long), and the default bits of that three fields are as follows:

  • sign(1bit)
    The highest bit is always 0.

  • delta seconds (28 bits)
    The next 28 bits, represents delta seconds since a customer epoch(2016-05-20). The maximum time will be 8.7 years.

  • worker id (22 bits)
    The next 22 bits, represents the worker node id, maximum value will be 4.2 million. UidGenerator uses a build-in database based worker id assigner when startup by default, and it will dispose previous work node id after reboot. Other strategy such like 'reuse' is coming soon.

  • sequence (13 bits)
    the last 13 bits, represents sequence within the one second, maximum is 8192 per second by default.

The parameters above can be configured in spring bean

CachedUidGenerator

RingBuffer is an array,each item of that array is called 'slot', every slot keeps a uid or a flag(Double RingBuffer). The size of RingBuffer is 2^n, where n is positive integer and equal or greater than bits of sequence. Assign bigger value to boostPower if you want to enlarge RingBuffer to improve throughput.

Tail & Cursor pointer
  • Tail Pointer

    Represents the latest produced UID. If it catches up with cursor, the ring buffer will be full, at that moment, no put operation should be allowed, you can specify a policy to handle it by assigning property rejectedPutBufferHandler.

  • Cursor Pointer

    Represents the latest already consumed UID. If cursor catches up with tail, the ring buffer will be empty, and any take operation will be rejected. you can also specify a policy to handle it by assigning property rejectedTakeBufferHandler.

RingBuffer

CachedUidGenerator used double RingBuffer,one RingBuffer for UID, another for status(if valid for take or put)

Array can improve performance of reading, due to the CUP cache mechanism. At the same time, it brought the side effect of 「False Sharing」, in order to solve it, cache line padding is applied.

FalseSharing

RingBuffer filling

  • Initialization padding During RingBuffer initializing,the entire RingBuffer will be filled.

  • In-time filling Whenever the percent of available UIDs is less than threshold paddingFactor, the fill task is triggered. You can reassign that threshold in Spring bean configuration.

  • Periodic filling Filling periodically in a scheduled thread. ThescheduleInterval can be reassigned in Spring bean configuration.

Quick Start

Here we have a demo with 4 steps to introduce how to integrate UidGenerator into Spring based projects.

Step 1: Install Java8, Maven, MySQL

If you have already installed maven, jdk8+ and Mysql or other DB which supported by Mybatis, just skip to next.
Download Java8, MySQL and Maven, and install jdk, mysql. For maven, extracting and setting MAVEN_HOME is enough.

Set JAVA_HOME & MAVEN_HOME

Here is a sample script to set JAVA_HOME and MAVEN_HOME

export MAVEN_HOME=/xxx/xxx/software/maven/apache-maven-3.3.9
export PATH=$MAVEN_HOME/bin:$PATH
JAVA_HOME="/Library/Java/JavaVirtualMachines/jdk1.8.0_91.jdk/Contents/Home";
export JAVA_HOME;

Step 2: Create table WORKER_NODE

Replace xxxxx with real database name, and run following script to create table,

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;

Reset property of 'jdbc.url', 'jdbc.username' and 'jdbc.password' in mysql.properties.

Step 3: Spring configuration

DefaultUidGenerator

There are two implements of UidGenerator: DefaultUidGenerator, CachedUidGenerator.
For performance sensitive application, CachedUidGenerator is recommended.

<!-- 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" />

CachedUidGenerator

Copy beans of CachedUidGenerator to 'test/resources/uid/cached-uid-spring.xml'.

<!-- 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 -->
    <!-- Sample: bufferSize=1024, paddingFactor=50 -> threshold=1024 * 50 / 100 = 512. -->
    <!-- When the rest available UIDs < 512, RingBiffer will be padded in-time -->
    <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" />
 
<!-- Mybatis config... -->

Mybatis config

mybatis-spring.xml shows as below:

<!-- Spring annotation scan -->
<context:component-scan base-package="com.baidu.fsg.uid" />

<bean id="sqlSessionFactory" class="org.mybatis.spring.SqlSessionFactoryBean">
    <property name="dataSource" ref="dataSource" />
    <property name="mapperLocations" value="classpath:/META-INF/mybatis/mapper/M_WORKER*.xml" />
</bean>

<!-- transaction -->
<tx:annotation-driven transaction-manager="transactionManager" order="1" />

<bean id="transactionManager" class="org.springframework.jdbc.datasource.DataSourceTransactionManager">
	<property name="dataSource" ref="dataSource" />
</bean>

<!-- Mybatis Mapper scan -->
<bean class="org.mybatis.spring.mapper.MapperScannerConfigurer">
	<property name="annotationClass" value="org.springframework.stereotype.Repository" />
	<property name="basePackage" value="com.baidu.fsg.uid.worker.dao" />
	<property name="sqlSessionFactoryBeanName" value="sqlSessionFactory" />
</bean>

<!-- datasource config -->
<bean id="dataSource" parent="abstractDataSource">
	<property name="driverClassName" value="${mysql.driver}" />
	<property name="maxActive" value="${jdbc.maxActive}" />
	<property name="url" value="${jdbc.url}" />
	<property name="username" value="${jdbc.username}" />
	<property name="password" value="${jdbc.password}" />
</bean>

<bean id="abstractDataSource" class="com.alibaba.druid.pool.DruidDataSource" destroy-method="close">
	<property name="filters" value="${datasource.filters}" />
	<property name="defaultAutoCommit" value="${datasource.defaultAutoCommit}" />
	<property name="initialSize" value="${datasource.initialSize}" />
	<property name="minIdle" value="${datasource.minIdle}" />
	<property name="maxWait" value="${datasource.maxWait}" />
	<property name="testWhileIdle" value="${datasource.testWhileIdle}" />
	<property name="testOnBorrow" value="${datasource.testOnBorrow}" />
	<property name="testOnReturn" value="${datasource.testOnReturn}" />
	<property name="validationQuery" value="${datasource.validationQuery}" />
	<property name="timeBetweenEvictionRunsMillis" value="${datasource.timeBetweenEvictionRunsMillis}" />
	<property name="minEvictableIdleTimeMillis" value="${datasource.minEvictableIdleTimeMillis}" />
	<property name="logAbandoned" value="${datasource.logAbandoned}" />
	<property name="removeAbandoned" value="${datasource.removeAbandoned}" />
	<property name="removeAbandonedTimeout" value="${datasource.removeAbandonedTimeout}" />
</bean>

<bean id="batchSqlSession" class="org.mybatis.spring.SqlSessionTemplate">
	<constructor-arg index="0" ref="sqlSessionFactory" />
	<constructor-arg index="1" value="BATCH" />
</bean>

Step 4: Run UnitTest

Run CachedUidGeneratorTest, shows how to generate / parse UniqueID:

@Resource
private UidGenerator uidGenerator;

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

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

}

Tips

For low concurrency and long term application, less seqBits but more timeBits is recommended. For example, if DisposableWorkerIdAssigner is adopted and the average reboot frequency is 12 per node per day, with the configuration {"workerBits":23,"timeBits":31,"seqBits":9}, one project can run for 68 years with 28 nodes and entirely concurrency 14400 UID/s.

For frequent reboot and long term application, less seqBits but more timeBits and workerBits is recommended. For example, if DisposableWorkerIdAssigner is adopted and the average reboot frequency is 24 * 12 per node per day, with the configuration {"workerBits":27,"timeBits":30,"seqBits":6}, one project can run for 34 years with 37 nodes and entirely concurrency 2400 UID/s.

Experiment for Throughput

To figure out CachedUidGenerator's UID throughput, some experiments are carried out.
Firstly, workerBits is arbitrarily fixed to 20, and change timeBits from 25(about 1 year) to 32(about 136 years),

timeBits 25 26 27 28 29 30 31 32
throughput 6,831,465 7,007,279 6,679,625 6,499,205 6,534,971 7,617,440 6,186,930 6,364,997

throughput1

Then, timeBits is arbitrarily fixed to 31, and workerBits is changed from 20(about 1 million total reboots) to 29(about 500 million total reboots),

workerBits 20 21 22 23 24 25 26 27 28 29
throughput 6,186,930 6,642,727 6,581,661 6,462,726 6,774,609 6,414,906 6,806,266 6,223,617 6,438,055 6,435,549

throughput2

It is obvious that whatever the configuration is, CachedUidGenerator always has the ability to provide 6 million stable throughput, what sacrificed is just life expectancy, this is very cool.

Finally, both timeBits and workerBits are fixed to 31 and 23 separately, and change the number of CachedUidGenerator consumer. Since our CPU only has 4 cores, [1, 8] is chosen.

consumers 1 2 3 4 5 6 7 8
throughput 6,462,726 6,542,259 6,077,717 6,377,958 7,002,410 6,599,113 7,360,934 6,490,969

throughput3

More Repositories

1

amis

前端低代码框架,通过 JSON 配置就能生成各种页面。
TypeScript
17,235
star
2

san

A fast, portable, flexible JavaScript component framework
JavaScript
4,708
star
3

lac

百度NLP:分词,词性标注,命名实体识别,词重要性
C++
3,864
star
4

braft

An industrial-grade C++ implementation of RAFT consensus algorithm based on brpc, widely used inside Baidu to build highly-available distributed systems.
C++
3,499
star
5

dperf

dperf is a DPDK based 100Gbps network performance and load testing software.
C
3,273
star
6

bfs

The Baidu File System.
C++
2,853
star
7

openrasp

🔥Open source RASP solution
C++
2,774
star
8

Familia

A Toolkit for Industrial Topic Modeling
C++
2,638
star
9

AnyQ

FAQ-based Question Answering System
C++
2,584
star
10

sofa-pbrpc

A light-weight RPC implement of google protobuf RPC framework.
C++
2,130
star
11

Senta

Baidu's open-source Sentiment Analysis System.
Python
1,889
star
12

tera

An Internet-Scale Database.
C++
1,887
star
13

bfe-book

In-depth Understanding of BFE《深入理解BFE》(Book for BFE, a CNCF open source project. both in English and in Chinese)
1,212
star
14

BaikalDB

BaikalDB, A Distributed HTAP Database.
C++
1,169
star
15

bigflow

Baidu Bigflow is an interface that allows for writing distributed computing programs and provides lots of simple, flexible, powerful APIs. Using Bigflow, you can easily handle data of any scale. Bigflow processes 4P+ data inside Baidu and runs about 10k jobs every day.
C++
1,142
star
16

DuReader

Baseline Systems of DuReader Dataset
Python
1,133
star
17

DDParser

百度开源的依存句法分析系统
Python
973
star
18

starlight

Java implementation for Baidu RPC, multi-protocol & high performance RPC.
Java
961
star
19

CUP

CUP, common useful python-lib. (Currently, Most popular python lib in baidu). Python 开发底层库, 涵盖util、service(threadpool/generator/executor/cache等等)、logging、monitoring、增强型配置 等等库支持
Python
938
star
20

ICE-BA

C++
700
star
21

NoahV

An efficient front-end application framework based on vue.js
JavaScript
639
star
22

EasyFaaS

EasyFaaS是一个依赖轻、适配性强、资源占用少、无状态且高性能的函数计算服务引擎
Go
620
star
23

Curve

An Integrated Experimental Platform for time series data anomaly detection.
JavaScript
530
star
24

Jprotobuf-rpc-socket

Protobuf RPC是一种基于TCP协议的二进制RPC通信协议的Java实现
Java
516
star
25

bifromq

A MQTT broker implementation adopting serverless architecture
Java
514
star
26

fast_rgf

Multi-core implementation of Regularized Greedy Forest
C++
466
star
27

babylon

High-Performance C++ Fundamental Library
C++
457
star
28

Dialogue

Python
444
star
29

Elasticsearch

Baidu Elasticsearch
Java
432
star
30

brcc

BRCC(better remote config center)是一个分布式配置中心,用于统一管理应用服务的配置信息,避免各类资源散落在各个项目中,简化资源配置的维护成本。作为一种轻量级的解决方案,部署简单,同时支持多环境、多版本、多角色的资源管理,可以在不改变应用源码的情况下无缝切换和实时生效配置信息。
Java
390
star
31

Cafe

A powerful test framework for Android
Java
370
star
32

mix-img

A fast mix image javascript tool libary
JavaScript
332
star
33

puck

Puck is a high-performance ANN search engine
Jupyter Notebook
331
star
34

unit-dmkit

C++
327
star
35

galaxy

Galaxy is a cluster management system.
C++
326
star
36

information-extraction

Python
325
star
37

knowledge-driven-dialogue

baseline system of knowledge driven dialogue competition
Python
270
star
38

CarbonGraph

A Swift dependency injection / lookup framework for iOS
Swift
254
star
39

unit-uskit

unit-uskit
C++
251
star
40

BIPlatform

JavaScript
219
star
41

dlock

An effective and reliable Distributed Lock
Java
216
star
42

ins

iNexus, coordinate large scale services
C++
214
star
43

boteye

C++
212
star
44

titan-dex

Java
201
star
45

m-git

MGit 是一款基于 Git 的多仓库管理工具,可以安全的、高效的管理多个 Git 仓库; 适合于在多个仓库中进行关联开发的项目,实现批量的版本管理功能,提高 Git 操作的效率,避免逐个执行 Git 命令带来的误操作风险。
Ruby
166
star
46

Rubik

An Android platform component management tool chain, based on Kotlin language.
Kotlin
154
star
47

common

Common library
C++
132
star
48

go-lib

Go
126
star
49

titan-hotfix

Java
125
star
50

wx2

小程序互转工具
JavaScript
124
star
51

iot-sdk-c

device sdk for baidu IoT Core service, in c. Including MQTT client
C
118
star
52

Youtube-8M

PaddlePaddle models for Youtube-8M Video Understanding Challenge
Python
114
star
53

ar-sdk

DuMix AR SDK for Developer
GLSL
107
star
54

broc

Python
101
star
55

ITEST

Web service interface test framework
97
star
56

ote-stack

OTE-Stack is an edge computing platform for 5G and AI
Go
96
star
57

GPT

Java
87
star
58

redis

Baidu Ksarch Redis - a production solution of redis cluster
87
star
59

san-devtools

Browser developer tools extension for debugging San.
TypeScript
82
star
60

terminator

Service Virtualization
Java
76
star
61

QCompute

QCompute is a Python-based quantum software development kit (SDK). It provides a full-stack programming experience for advanced users via hybrid quantum programming language features and a high-performance simulator.
Python
76
star
62

spring-cloud-baidu

70
star
63

shuttle

A fast computing framework based on Galaxy
C++
64
star
64

iot-edge-sdk-for-iot-parser

C
64
star
65

baidu-iot-samples

C
61
star
66

san-store

Application States Management for San
JavaScript
59
star
67

ARK

Development framework of intelligent operation
Python
57
star
68

san-update

Object immutable update utility for san solution
JavaScript
56
star
69

logcover

轻量级异常日志测试覆盖率度量工具
Python
56
star
70

palo

A fast MPP database for all modern analytics on big data. Powered by Apache Doris(Incubating)
50
star
71

speech-samples

百度语音示例
Java
48
star
72

ntripcaster

C
43
star
73

san-router

Official Router for San
JavaScript
38
star
74

Quanlse

Jupyter Notebook
38
star
75

san-ssr

San SSR framework and utils
TypeScript
37
star
76

dm-kit-php

PHP
36
star
77

boteye_sensor

C
35
star
78

ipipe-agent

Java
33
star
79

OASP

OASP (Online App Status Protocol)
Java
32
star
80

san-composition

JavaScript
30
star
81

duedge-recipes

DuEdge百度边缘网络计算样例代码
JavaScript
27
star
82

paddle-on-k8s-operator

Kubernetes operator for managing the lifecycle of PaddlePaddle job.
Go
24
star
83

baiducloud-sdk-go

Go SDK for Baidu Cloud
Go
24
star
84

san-website

JavaScript
21
star
85

baiduads-sdk

Baidu Ads API SDK
Python
19
star
86

du1906_esp

DUHOME AIOT platform based on du1906 and esp32
C
18
star
87

highflip

HIGHFLIP: An easy way to bridge different federal learning platforms
18
star
88

smartapp-openapi-java

百度智能小程序服务端 OpenAPI SDK for java,是基于小程序服务端 OpenAPI 封装的一套让开发者方便使用的 SDK, 它可以帮开发者减少理解和使用 OpenAPI 的成本, 减少开发者直接调用服务端接口不当而引起的错误, 避免在开发中走弯路。
Java
16
star
89

san-factory

JavaScript
15
star
90

ttm

C
14
star
91

cluster-api-provider-baiducloud

Kubernetes cluster-api for Baidu Cloud
Go
13
star
92

minions

Baidu 100G Chasiss Switch hardware spec
11
star
93

signet

签章系统
JavaScript
10
star
94

sgxray

SGXRay: a bounded verifier for Intel SGX enclaves
C
10
star
95

grafana-tsdb-datasource

JavaScript
9
star
96

iotcore-sdk-java

Java SDK for baidu IoT Core service
Java
9
star
97

bce-fpga-dev-kit

VHDL
8
star
98

iot

for all code about Internet of Things
8
star
99

smartapp-openapi-go

百度智能小程序服务端 OpenAPI SDK for go,是基于小程序服务端 OpenAPI 封装的一套让开发者方便使用的 SDK, 它可以帮开发者减少理解和使用 OpenAPI 的成本, 减少开发者直接调用服务端接口不当而引起的错误, 避免在开发中走弯路。
Go
8
star
100

duedge-cli

DuEdge Command Line
Python
6
star