尼恩说在前面

一个分布式 、高并发 的 ID系统，如何实现？

ID生产，如何实现600万 级别 的高并发？

最新《尼恩 架构笔记》《尼恩高并发三部曲》《尼恩Java面试宝典》的PDF，请关注本公众号【技术自由圈】获取，后台回复：领电子书

本文目录

- 尼恩说在前面

- 站上巨人肩膀上学习

- Snowflake的二进制位段 设计

- UidGenerator 的二进制位段 设计

 - UidGeneratorQuick Start

    -步骤1: 安装依赖

    -设置环境变量

    -步骤2: 创建表WORKER_NODE

    -步骤3: 修改Spring配置

    -官方给的DefaultUidGenerator配置

    -官方给的CachedUidGenerator配置

    -官方给的Mybatis配置

    -步骤4: 运行示例单测

 - DefaultUidGenerator

    -第一位段：delta seconds

    -第二位段：workerId

    -第三位段：sequence （秒内的序号）

 - CachedUidGenerator

    -CachedUidGenerator实现原理

    -CachedUidGenerator的环形队列设计

    -啰嗦一下，RingBuffer填充时机

    -CachedUidGenerator双RingBuffer设计

    -CachedUidGenerator 通过CacheLine补齐解决伪共享

- Snowflake 的时钟回拨问题

 - 什么是Snowflake 时间回拨问题

 - 如何解决

    -方法1 直接抛出异常

    -方法2 延迟等待

    -方法3 备用机

    -方法4 采用之前最大时间

    -方法5 追赶时间

 - UidGenerator  如何解决了时钟回拨问题

    -第一：workerId位段自增：

    -第二：delta seconds时间位段递增：

- 说在最后：有问题找老架构取经‍

站上巨人肩膀上学习    

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

基础知识：Snowflake的 二进制位段 设计   

1. sign(1bit) 固定1bit符号标识，即生成的UID为正数。
2. 时间戳（41位）：使用41位存储毫秒级的时间戳，表示自定义的起始时间（Epoch）到生成ID的时间之间的毫秒数。

41bit-时间可以表示（1L<<41）/(1000L*3600*24*365)=69年的时间。

3. 节点ID（10位）：用于标识不同的节点或机器。在分布式系统中，每个节点应具有唯一的节点ID。

10bit-机器可以表示1024台机器。
如果对IDC划分有需求，还可以将10-bit分5-bit给IDC，分5-bit给工作机器。
这样就可以表示32个IDC，每个IDC下可以有32台机器。

4. 序列号（12位）：在同一毫秒内生成的序列号。如果在同一毫秒内生成的ID数量超过了12位能够表示的范围，那么会等待下一毫秒再生成ID。

12个自增序列号可以表示2^12个ID，理论上snowflake方案的QPS约为409.6w/s。

UidGenerator 的二进制位段 设计

• 第1位：标志位
• 仍然占用1bit，其值始终是0：即生成的UID为 正数，不是负数
• 第2位开始的28bit：时间戳（当前时间，相对于epoch时间的增量值）
• 可表示2^28个数，不再是以毫秒为单位，而是以秒为单位，可用（1L<<28）/ (360024365) ≈ 8.51 年（最多可用8.7年，后边讲解）。
• epoch时间：指使用 UidGenerator生成分布式ID服务，第一次上线的时间，epoch可配置，默认的epoch时间是2016-09-20，不配置的话，会浪费好几年的可用时间。
• 第29位开始的22bit：中间的 workId （数据中心+工作机器，可以其他组成方式）
• 可表示 2^22 = 4194304个工作ID（最多可支持约420w次机器启动）。
• 内置实现：在启动时由数据库分配；默认分配策略：用后即弃；后续可提供复用策略。
• 最后的13-bit位：并发序列（自增）
• 表示每秒的并发数量，默认为2
• ^13 = 8192个并发（即：默认qps为8192）。

UidGeneratorQuick Start

步骤1: 安装依赖

设置环境变量

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

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;

步骤3: 修改Spring配置

官方给的DefaultUidGenerator配置

<!-- 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>
 
<!-- 用完即弃的WorkerIdAssigner，依赖DB操作 -->
<bean id="disposableWorkerIdAssigner" class="com.baidu.fsg.uid.worker.DisposableWorkerIdAssigner" />

官方给的CachedUidGenerator配置

<!-- CachedUidGenerator -->
<bean id="cachedUidGenerator" class="com.baidu.fsg.uid.impl.CachedUidGenerator">
    <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"/>
 
    <!-- RingBuffer size扩容参数, 可提高UID生成的吞吐量. -->
    <!-- 默认:3， 原bufferSize=8192, 扩容后bufferSize= 8192 << 3 = 65536 -->
    <property name="boostPower" value="3"></property>
 
    <!-- 指定何时向RingBuffer中填充UID, 取值为百分比(0, 100), 默认为50 -->
    <!-- 举例: bufferSize=1024, paddingFactor=50 -> threshold=1024 * 50 / 100 = 512. -->
    <!-- 当环上可用UID数量 < 512时, 将自动对RingBuffer进行填充补全 -->
    <property name="paddingFactor" value="50"></property>
 
    <!-- 另外一种RingBuffer填充时机, 在Schedule线程中, 周期性检查填充 -->
    <!-- 默认:不配置此项, 即不实用Schedule线程. 如需使用, 请指定Schedule线程时间间隔, 单位:秒 -->
    <property name="scheduleInterval" value="60"></property>
 
    <!-- 拒绝策略: 当环已满, 无法继续填充时 -->
    <!-- 默认无需指定, 将丢弃Put操作, 仅日志记录. 如有特殊需求, 请实现RejectedPutBufferHandler接口(支持Lambda表达式) -->
    <property name="rejectedPutBufferHandler" ref="XxxxYourPutRejectPolicy"></property>
 
    <!-- 拒绝策略: 当环已空, 无法继续获取时 -->
    <!-- 默认无需指定, 将记录日志, 并抛出UidGenerateException异常. 如有特殊需求, 请实现RejectedTakeBufferHandler接口(支持Lambda表达式) -->
    <property name="rejectedTakeBufferHandler" ref="XxxxYourTakeRejectPolicy"></property>
 
</bean>
 
<!-- 用完即弃的WorkerIdAssigner, 依赖DB操作 -->
<bean id="disposableWorkerIdAssigner" class="com.baidu.fsg.uid.worker.DisposableWorkerIdAssigner" />
 

官方给的Mybatis配置

<!-- Spring annotation扫描 -->
<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>

<!-- Mybatis Mapper扫描 -->
<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: 运行示例单测

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

}

DefaultUidGenerator 的底层原理 和核心源码 学习

第一位段：delta seconds

第二位段：workerId

DROP TABLE IF EXISTS WORKER_NODE;
CREATE TABLE WORKER_NODE(
  ID BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY ,
  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 DATETIME NOT NULL COMMENT 'modified time',
  CREATED DATEIMTE NOT NULL COMMENT 'created time'
)COMMENT='DB WorkerID Assigner for UID Generator',ENGINE = INNODB;

第三位段：sequence （秒内的序号）

• synchronized保证线程安全；
• 如果时间有任何的回拨，那么直接抛出异常；
• 如果当前时间和上一次是同一秒时间，那么sequence自增。如果同一秒内自增值超过2^13-1，那么就会自旋等待下一秒（getNextSecond）；
• 如果是新的一秒，那么sequence重新从0开始；

protected synchronized long nextId() {
    long currentSecond = getCurrentSecond();
    if (currentSecond < lastSecond) {
        long refusedSeconds = lastSecond - currentSecond;
        throw new UidGenerateException("Clock moved backwards. Refusing for %d seconds", refusedSeconds);
    }
    if (currentSecond == lastSecond) {
        sequence = (sequence + 1) & bitsAllocator.getMaxSequence();
        if (sequence == 0) {
            currentSecond = getNextSecond(lastSecond);
        }
    } else {
        sequence = 0L;
    }
    lastSecond = currentSecond;
    return bitsAllocator.allocate(currentSecond - epochSeconds, workerId, sequence);
}

CachedUidGenerator 的底层原理 和核心源码 学习 

• 使用 RingBuffer 缓存预生产 id。数组每个元素成为一个slot。
• RingBuffer容量，默认为Snowflake算法中sequence最大值（2^13 = 8192）。可通过 boostPower 配置进行扩容，以提高 RingBuffer 读写吞吐量。

CachedUidGenerator实现原理

• CachedUidGenerator 采用RingBuffer （或者环形队列）来缓存已生成的UID,
• CachedUidGenerator 把 ID的生产 和 ID消费 并行化 ,
• CachedUidGenerator 对CacheLine补齐，避免了由RingBuffer带来的硬件级「伪共享」问题.

CachedUidGenerator的环形队列设计

1. 获取id
1. Consumer 会从ringbuffer中拿一个id，
2. 支持 Consumer 并发获取
2. 填充id
1. RingBuffer填充时机 为3种：初始化预填充、即时填充、定时填充
2. 初始化预填充：程序启动时，将RingBuffer填充满，缓存着8192个id
3. 即时填充: 调用getUID()获取id时，检测到RingBuffer中的剩余id个数小于总个数的50%，将RingBuffer填充满，使其缓存8192个id
4. 定时填充: 可配置是否使用以及定时任务的周期, 通过Schedule线程，定时补全空闲slots。可通过scheduleInterval配置，以应用定时填充功能，并指定Schedule时间间隔。
3. Tail指针、Cursor指针用于环形数组上读写slot.

啰嗦一下，RingBuffer填充时机

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

CachedUidGenerator双RingBuffer 高并发设计 

• Uid-RingBuffer
• Flag-RingBuffer

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

CachedUidGenerator 通过CacheLine补齐解决伪共享

如何解决 Snowflake 的时钟回拨问题？

什么是Snowflake 时间回拨问题？

• 雪花算法通过时间来即将作为id的区分标准之一,对于同一台id生成机器,它通过时间和序号保证id不重复
• 当机器出现问题,时间可能回到之前,此时,时间就不能区分
• 又或者因为闰秒的出现,导致时间回拨

如何解决

方法1 直接抛出异常

• 不管3X7==21,直接抛出异常
• 将问题交给人工解决
• 这种方法也是原始的雪花算法,百度的uid-generator采用的
• 太过简单,显然不好

方法2 延迟等待

• 这种时间回拨(回跳)或许只出现一次,也许只是机器出现了小问题,所以产生
• 对于这种场景,没有必要抛出异常,中断业务
• 此时,将当前线程阻塞3ms,之后再获取时间,看时间是否比上一次请求的时间大
• 如果大了,说明恢复正常了,则不用管
• 如果还小,说明真出问题了,则抛出异常,呼唤程序员处理
• 实际应用项目: 美团的leaf, 用如果时间差在5ms内,则等待 时间差<<1, 然后再判断

方法3 备用机

• 当前机器出现问题,则换一台机器
• 通过高可用来解决该问题

方法4 采用之前最大时间

• 本身得出时间回拨结论就是通过当前时间和上次最后(大)的时间进行比较
• 那么此时可以采用上次最大时间的最大序号之后的序号来进行继续使用
• 从而保证了唯一性

方法5 追赶时间

• 可以采取这样的暴力思路,因为当前的时间回拨了,比之前的时间慢
• 那么我们便加速追赶时间
• 首先,不返回id
• 然后将我们的seq增加比如1024个,然后判断是否回拨,如果不是,再加1024
• 当seq超过了12位的maxSeq时,按照雪花算法的逻辑,时间便会进位,借用下个时间的seq
• 此时就实现了时间的加速
• 经过若干个加速,则可以实现时间正常

UidGenerator 如何解决了时钟回拨问题

第一：workerId位段自增：

第二：delta seconds时间位段递增：

说在最后：有问题找老架构取经‍

• 被裁太爽：每月大涨1W，10年CRUD小伙，靠转架构一个月上岸，年薪50W爽歪了！

• 绝地逢生：9年经验自考小伙伴，跟着尼恩狠卷3月硬核技术，面试机会爆表，2周后收3个offer ，满血复活

• 逆天改命：3年经验2本，卷3个月涨薪60%，进准大厂(得物、乐信、58集团等)，年薪36W

• 女35岁CRUD程序媛，12月被裁后，拿30个机会2个offer上岸，年底大裁员太不容易了

• 12年小伙转架构，1小时蜕变收年薪55万offer，秘诀：GO+Java双栖架构

• 不怕裁员，8年小伙去中年危机，秘诀：换架构师赛道，上得厅堂，下得厨房，越早越好

• 逆天啦：4年crud小伙收shein+银行两优质offer，狠卷1月收年薪43万大涨30%

• 太劲爆.... 被裁4个月，38岁Android转Java，2个月提架构offer

• 起死回生：8年小伙高中毕业+频繁跳槽，狠卷2月，提Java高级offer

• 爽翻了：指导3轮，5年小伙收5大offer，涨50%，领路模式太牛

• 降维攻击，37年大龄老伙喜提60W年薪offer，1个月顺利上岸

• 极速拿offer：阿里P6被裁后极速上岸，1个月内喜提2优质offer(含滴滴)

• 裁就裁，6年小伙60W极速上岸，白拿20W还游一圈拉萨，真香