凡尔赛之--UidGenerator

冷不防 2022-09-10 00:07 228阅读 0赞

[uid-generator/README.zh\_cn.md at master · baidu/uid-generator · GitHub][uid-generator_README.zh_cn.md at master _ baidu_uid-generator _ GitHub]

# UidGenerator #

[In English][]

UidGenerator是Java实现的, 基于[Snowflake][]算法的唯一ID生成器。UidGenerator以组件形式工作在应用项目中, 支持自定义workerId位数和初始化策略, 从而适用于[docker][]等虚拟化环境下实例自动重启、漂移等场景。 在实现上, UidGenerator通过借用未来时间来解决sequence天然存在的并发限制; 采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费, 同时对CacheLine补齐，避免了由RingBuffer带来的硬件级「伪共享」问题. 最终单机QPS可达600万。

依赖版本：[Java8][]及以上版本, [MySQL][](内置WorkerID分配器, 启动阶段通过DB进行分配; 如自定义实现, 则DB非必选依赖）

## Snowflake算法 ##

Snowflake算法描述：指定机器 & 同一时刻 & 某一并发序列，是唯一的。据此可生成一个64 bits的唯一ID（long）。默认采用上图字节分配方式：

*  sign(1bit)  
    固定1bit符号标识，即生成的UID为正数。
 *  delta seconds (28 bits)  
    当前时间，相对于时间基点"2016-05-20"的增量值，单位：秒，最多可支持约8.7年
 *  worker id (22 bits)  
    机器id，最多可支持约420w次机器启动。内置实现为在启动时由数据库分配，默认分配策略为用后即弃，后续可提供复用策略。
 *  sequence (13 bits)  
    每秒下的并发序列，13 bits可支持每秒8192个并发。

**以上参数均可通过Spring进行自定义**

## CachedUidGenerator ##

RingBuffer环形数组，数组每个元素成为一个slot。RingBuffer容量，默认为Snowflake算法中sequence最大值，且为2^N。可通过`boostPower`配置进行扩容，以提高RingBuffer 读写吞吐量。

Tail指针、Cursor指针用于环形数组上读写slot：

*  Tail指针  
    表示Producer生产的最大序号(此序号从0开始，持续递增)。Tail不能超过Cursor，即生产者不能覆盖未消费的slot。当Tail已赶上curosr，此时可通过`rejectedPutBufferHandler`指定PutRejectPolicy
 *  Cursor指针  
    表示Consumer消费到的最小序号(序号序列与Producer序列相同)。Cursor不能超过Tail，即不能消费未生产的slot。当Cursor已赶上tail，此时可通过`rejectedTakeBufferHandler`指定TakeRejectPolicy

[![RingBuffer][]][RingBuffer 1]

CachedUidGenerator采用了双RingBuffer，Uid-RingBuffer用于存储Uid、Flag-RingBuffer用于存储Uid状态(是否可填充、是否可消费)

由于数组元素在内存中是连续分配的，可最大程度利用CPU cache以提升性能。但同时会带来「伪共享」FalseSharing问题，为此在Tail、Cursor指针、Flag-RingBuffer中采用了CacheLine 补齐方式。

[![FalseSharing][]][FalseSharing 1]

RingBuffer填充时机

*  初始化预填充  
    RingBuffer初始化时，预先填充满整个RingBuffer.
 *  即时填充  
    Take消费时，即时检查剩余可用slot量(`tail` - `cursor`)，如小于设定阈值，则补全空闲slots。阈值可通过`paddingFactor`来进行配置，请参考Quick Start中CachedUidGenerator配置
 *  周期填充  
    通过Schedule线程，定时补全空闲slots。可通过`scheduleInterval`配置，以应用定时填充功能，并指定Schedule时间间隔

## Quick Start ##

这里介绍如何在基于Spring的项目中使用UidGenerator, 具体流程如下:

### 步骤1: 安装依赖 ###

先下载[Java8][], [MySQL][]和[Maven][]

设置环境变量

maven无须安装, 设置好MAVEN\_HOME即可. 可像下述脚本这样设置JAVA\_HOME和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;

### 步骤2: 创建表WORKER\_NODE ###

运行sql脚本以导入表WORKER\_NODE, 脚本如下:

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;

修改[mysql.properties][]配置中, jdbc.url, jdbc.username和jdbc.password, 确保库地址, 名称, 端口号, 用户名和密码正确.

### 步骤3: 修改Spring配置 ###

提供了两种生成器: [DefaultUidGenerator][]、[CachedUidGenerator][]。如对UID生成性能有要求, 请使用CachedUidGenerator  
对应Spring配置分别为: [default-uid-spring.xml][]、[cached-uid-spring.xml][]

DefaultUidGenerator配置

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

CachedUidGenerator配置

<bean id="cachedUidGenerator" class="com.baidu.fsg.uid.impl.CachedUidGenerator">
        <property name="workerIdAssigner" ref="disposableWorkerIdAssigner" />
     
        
        
        <property name="timeBits" value="29"/>
        <property name="workerBits" value="21"/>
        <property name="seqBits" value="13"/>
        <property name="epochStr" value="2016-09-20"/>
     
        
        
        <property name="boostPower" value="3"></property>
     
        
        
        
        <property name="paddingFactor" value="50"></property>
     
        
        
        <property name="scheduleInterval" value="60"></property>
     
        
        
        <property name="rejectedPutBufferHandler" ref="XxxxYourPutRejectPolicy"></property>
     
        
        
        <property name="rejectedTakeBufferHandler" ref="XxxxYourTakeRejectPolicy"></property>
     
    </bean>
     
    
    <bean id="disposableWorkerIdAssigner" class="com.baidu.fsg.uid.worker.DisposableWorkerIdAssigner" />

Mybatis配置

[mybatis-spring.xml][]配置说明如下:

<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>
    
    
    <tx:annotation-driven transaction-manager="transactionManager" order="1" />
    
    <bean id="transactionManager" class="org.springframework.jdbc.datasource.DataSourceTransactionManager">
    	<property name="dataSource" ref="dataSource" />
    </bean>
    
    
    <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>
    
    
    <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>

### 步骤4: 运行示例单测 ###

运行单测[CachedUidGeneratorTest][], 展示UID生成、解析等功能

@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));
    
    }

### 关于UID比特分配的建议 ###

对于并发数要求不高、期望长期使用的应用, 可增加`timeBits`位数, 减少`seqBits`位数. 例如节点采取用完即弃的WorkerIdAssigner策略, 重启频率为12次/天, 那么配置成`{"workerBits":23,"timeBits":31,"seqBits":9}`时, 可支持28个节点以整体并发量14400 UID/s的速度持续运行68年.

对于节点重启频率频繁、期望长期使用的应用, 可增加`workerBits`和`timeBits`位数, 减少`seqBits`位数. 例如节点采取用完即弃的WorkerIdAssigner策略, 重启频率为24\*12次/天, 那么配置成`{"workerBits":27,"timeBits":30,"seqBits":6}`时, 可支持37个节点以整体并发量2400 UID/s的速度持续运行34年.

吞吐量测试

在MacBook Pro（2.7GHz Intel Core i5, 8G DDR3）上进行了CachedUidGenerator（单实例）的UID吞吐量测试.  
首先固定住workerBits为任选一个值(如20), 分别统计timeBits变化时(如从25至32, 总时长分别对应1年和136年)的吞吐量, 如下表所示:

<table> 
 <thead> 
  <tr> 
   <th>timeBits</th> 
   <th>25</th> 
   <th>26</th> 
   <th>27</th> 
   <th>28</th> 
   <th>29</th> 
   <th>30</th> 
   <th>31</th> 
   <th>32</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>throughput</td> 
   <td>6,831,465</td> 
   <td>7,007,279</td> 
   <td>6,679,625</td> 
   <td>6,499,205</td> 
   <td>6,534,971</td> 
   <td>7,617,440</td> 
   <td>6,186,930</td> 
   <td>6,364,997</td> 
  </tr> 
 </tbody> 
</table>

再固定住timeBits为任选一个值(如31), 分别统计workerBits变化时(如从20至29, 总重启次数分别对应1百万和500百万)的吞吐量, 如下表所示:

<table> 
 <thead> 
  <tr> 
   <th>workerBits</th> 
   <th>20</th> 
   <th>21</th> 
   <th>22</th> 
   <th>23</th> 
   <th>24</th> 
   <th>25</th> 
   <th>26</th> 
   <th>27</th> 
   <th>28</th> 
   <th>29</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>throughput</td> 
   <td>6,186,930</td> 
   <td>6,642,727</td> 
   <td>6,581,661</td> 
   <td>6,462,726</td> 
   <td>6,774,609</td> 
   <td>6,414,906</td> 
   <td>6,806,266</td> 
   <td>6,223,617</td> 
   <td>6,438,055</td> 
   <td>6,435,549</td> 
  </tr> 
 </tbody> 
</table>

由此可见, 不管如何配置, CachedUidGenerator总能提供**600万/s**的稳定吞吐量, 只是使用年限会有所减少. 这真的是太棒了.

最后, 固定住workerBits和timeBits位数(如23和31), 分别统计不同数目(如1至8,本机CPU核数为4)的UID使用者情况下的吞吐量,

<table> 
 <thead> 
  <tr> 
   <th>workerBits</th> 
   <th>1</th> 
   <th>2</th> 
   <th>3</th> 
   <th>4</th> 
   <th>5</th> 
   <th>6</th> 
   <th>7</th> 
   <th>8</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>throughput</td> 
   <td>6,462,726</td> 
   <td>6,542,259</td> 
   <td>6,077,717</td> 
   <td>6,377,958</td> 
   <td>7,002,410</td> 
   <td>6,599,113</td> 
   <td>7,360,934</td> 
   <td>6,490,969</td> 
  </tr> 
 </tbody> 
</table>

彩蛋：[https://download.csdn.net/download/gaowenhui2008/21847349][https_download.csdn.net_download_gaowenhui2008_21847349]

[uid-generator_README.zh_cn.md at master _ baidu_uid-generator _ GitHub]: https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md
[In English]: https://github.com/baidu/uid-generator/blob/master/README.md
[Snowflake]: https://github.com/twitter/snowflake
[docker]: https://www.docker.com/
[Java8]: http://www.oracle.com/technetwork/java/javase/downloads/jdk8-downloads-2133151.html
[MySQL]: https://dev.mysql.com/downloads/mysql/
[RingBuffer]: /images/20220829/e805bdb79406425dad99a96b2ddb8f29.png
[RingBuffer 1]: https://github.com/baidu/uid-generator/blob/master/doc/ringbuffer.png
[FalseSharing]: /images/20220829/176367abe9ad4d9b863fc216c94424f5.png
[FalseSharing 1]: https://github.com/baidu/uid-generator/blob/master/doc/cacheline_padding.png
[Maven]: https://maven.apache.org/download.cgi
[mysql.properties]: https://github.com/baidu/uid-generator/blob/master/src/test/resources/uid/mysql.properties
[DefaultUidGenerator]: https://github.com/baidu/uid-generator/blob/master/src/main/java/com/baidu/fsg/uid/impl/DefaultUidGenerator.java
[CachedUidGenerator]: https://github.com/baidu/uid-generator/blob/master/src/main/java/com/baidu/fsg/uid/impl/CachedUidGenerator.java
[default-uid-spring.xml]: https://github.com/baidu/uid-generator/blob/master/src/test/resources/uid/default-uid-spring.xml
[cached-uid-spring.xml]: https://github.com/baidu/uid-generator/blob/master/src/test/resources/uid/cached-uid-spring.xml
[mybatis-spring.xml]: https://github.com/baidu/uid-generator/blob/master/src/test/resources/uid/mybatis-spring.xml
[CachedUidGeneratorTest]: https://github.com/baidu/uid-generator/blob/master/src/test/java/com/baidu/fsg/uid/CachedUidGeneratorTest.java
[https_download.csdn.net_download_gaowenhui2008_21847349]: https://download.csdn.net/download/gaowenhui2008/21847349