晖序列号在线⽣成器_开源分布式ID⽣成器UidGenerator的
技术实现
1、引⾔
很多⼈⼀想到IM应⽤开发，第⼀印象就是“长连接”、“socket”、“保活”、“协议”这些关键词，没错，这些确实是IM开发中肯定会涉及的技术范畴。
但，当你真正开始编写第⼀⾏代码时，最现实的问题实际上是“聊天消息ID该怎么⽣成？”这个看似微不⾜道的⼩事情。说它看似微不⾜道，是因为在IM⾥它太平常了，处处可见它的⾝影。不过，虽然看似微不⾜道，但实际却很重要，因为它的⽣成算法和⽣成策略的优劣在某种意义上来说，决定了你的IM应⽤层某些功能实现的难易度。
有签于此，即时通讯⽹专门整理了“IM消息ID技术专题”系列⽂章，希望能带给你对这个看似微⼩但却很重要的技术点有更深刻的理解和最佳实践思路。
本⽂是专题系列⽂章的第5篇，专门介绍百度开源的分布式消息ID⽣成器UidGenerator的算法逻辑、实现思路、重点源码解读等，或许能带给你更多的启发。
学习交流：
- 即时通讯/推送技术开发交流5：215477170 [推荐]
- 移动端IM开发⼊门⽂章：《新⼿⼊门⼀篇就够：从零开发移动端IM》
2、专题⽬录
本⽂是“IM消息ID技术专题”系列⽂章的第5篇，专题总⽬录如下：
《IM消息ID技术专题(⼀)：的海量IM聊天消息序列号⽣成实践(算法原理篇)》
《IM消息ID技术专题(⼆)：的海量IM聊天消息序列号⽣成实践(容灾⽅案篇)》
《IM消息ID技术专题(三)：解密融云IM产品的聊天消息ID⽣成策略》
《IM消息ID技术专题(四)：深度解密美团的分布式ID⽣成算法》
《IM消息ID技术专题(五)：百度开源分布式ID⽣成器UidGenerator介绍》(* 本⽂)
3、基本介绍
全局ID(常见的⽐如：IM聊天系统中的消息ID、电商系统中的订单号、外卖应⽤中的订单号等)服务是
分布式服务中的基础服务，需要保持全局唯⼀、⾼效、⾼可靠性。有些时候还可能要求保持单调，但也并⾮⼀定要严格递增或者递减。
全局ID也可以通过数据库的⾃增主键来获取，但是如果要求QPS很⾼显然是不现实的。
UidGenerator(备⽤地址)⼯程是百度开源的基于Snowflake算法的唯⼀ID⽣成器(百度对Snowflake算法进⾏了改进)，引⼊了⾼性能队列⾼性能队列disruptor中RingBuffer思想，进⼀步提升了效率。
UidGenerator是Java语⾔实现的，它以组件形式⼯作在应⽤项⽬中，⽀持⾃定义workerId位数和初始化策略,，从⽽适⽤于docker等虚拟化环境下实例⾃动重启、漂移等场景。
在技术实现上，UidGenerator有以下关键特性：
1)UidGenerator通过借⽤未来时间来解决sequence天然存在的并发限制；
2)采⽤RingBuffer来缓存已⽣成的UID, 并⾏化UID的⽣产和消费；
3)同时对CacheLine补齐，避免了由RingBuffer带来的硬件级「伪共享」问题。
基于以上技术特性，UidGenerator的单机压⼒测试数据显⽰，其QPS可⾼达600万。
依赖的环境：
1)Java8及以上版本(代码中使⽤了函数式编程语句等新特性，请见：uid-generator源码在线版)；
2)MySQL(内置WorkerID分配器, 启动阶段通过DB进⾏分配; 如⾃定义实现, 则DB⾮必选依赖)。
以下是UidGenerator⼯程的相关资源：
4、什么是Snowflake算法？
4.1 SnowFlake算法原理
友情提⽰：本节⽂字内容摘选⾃《IM消息ID技术专题(四)：深度解密美团的分布式ID⽣成算法》⼀⽂，如果您想了解美团对于SnowFlake算法的理解和应⽤情况，可详细阅读之。
SnowFlake 算法，是 Twitter 开源的分布式 ID ⽣成算法。其核⼼思想就是：使⽤⼀个 64 bit 的 long 型的数字作为全局唯⼀ ID。
这 64 个 bit 中，其中 1 个 bit 是不⽤的，然后⽤其中的 41 bit 作为毫秒数，⽤ 10 bit 作为⼯作机器 ID，12 bit 作为序列号。
SnowFlake的ID构成：
(本图引⽤⾃《IM消息ID技术专题(四)：深度解密美团的分布式ID⽣成算法》)
SnowFlake的ID样本：
(本图引⽤⾃《IM消息ID技术专题(四)：深度解密美团的分布式ID⽣成算法》)
给⼤家举个例⼦吧，如上图所⽰，⽐如下⾯那个 64 bit 的 long 型数字：
1)第⼀个部分，是 1 个 bit：0，这个是⽆意义的；
2)第⼆个部分，是 41 个 bit：表⽰的是时间戳；
3)第三个部分，是 5 个 bit：表⽰的是机房 ID，10001；
4)第四个部分，是 5 个 bit：表⽰的是机器 ID，1 1001；
5)第五个部分，是 12 个 bit：表⽰的序号，就是某个机房某台机器上这⼀毫秒内同时⽣成的 ID 的序号，0000 00000000。
① 1 bit：是不⽤的，为啥呢？
因为⼆进制⾥第⼀个 bit 为如果是 1，那么都是负数，但是我们⽣成的 ID 都是正数，所以第⼀个 bit 统⼀都是 0。
② 41 bit：表⽰的是时间戳，单位是毫秒。
41 bit 可以表⽰的数字多达 2^41 - 1，也就是可以标识 2 ^ 41 - 1 个毫秒值，换算成年就是表⽰ 69 年的时间。
③ 10 bit：记录⼯作机器 ID，代表的是这个服务最多可以部署在 2^10 台机器上，也就是 1024 台机器。
但是 10 bit ⾥ 5 个 bit 代表机房 id，5 个 bit 代表机器 ID。意思就是最多代表 2 ^ 5 个机房(32 个机房)，每个机房⾥可以代表 2 ^ 5 个机器(32 台机器)。
④12 bit：这个是⽤来记录同⼀个毫秒内产⽣的不同 ID。
12 bit 可以代表的最⼤正整数是 2 ^ 12 - 1 = 4096，也就是说可以⽤这个 12 bit 代表的数字来区分同⼀个毫秒内的 4096 个不同的ID。理论上snowflake⽅案的QPS约为409.6w/s，这种分配⽅式可以保证在任何⼀个IDC的任何⼀台机器在任意毫秒内⽣成的ID都是不同的。
简单来说，你的某个服务假设要⽣成⼀个全局唯⼀ ID，那么就可以发送⼀个请求给部署了 SnowFlake 算法的系统，由这个 SnowFlake 算法系统来⽣成唯⼀ ID。
1)这个 SnowFlake 算法系统⾸先肯定是知道⾃⼰所在的机房和机器的，⽐如机房 ID = 17，机器 ID = 12；
2)接着 SnowFlake 算法系统接收到这个请求之后，⾸先就会⽤⼆进制位运算的⽅式⽣成⼀个 64 bit 的 long 型 ID，64 个 bit 中的第
⼀个 bit 是⽆意义的；
3)接着 41 个 bit，就可以⽤当前时间戳(单位到毫秒)，然后接着 5 个 bit 设置上这个机房 id，还有 5 个 bit 设置上机器 ID；
4)最后再判断⼀下，当前这台机房的这台机器上这⼀毫秒内，这是第⼏个请求，给这次⽣成 ID 的请求累加⼀个序号，作为最后的 12
个 bit。
最终⼀个 64 个 bit 的 ID 就出来了，类似于：
(本图引⽤⾃《IM消息ID技术专题(四)：深度解密美团的分布式ID⽣成算法》)
这个算法可以保证说，⼀个机房的⼀台机器上，在同⼀毫秒内，⽣成了⼀个唯⼀的 ID。可能⼀个毫秒内会⽣成多个 ID，但是有最后 12 个bit 的序号来区分开来。
下⾯我们简单看看这个 SnowFlake 算法的⼀个代码实现，这就是个⽰例，⼤家如果理解了这个意思之后，以后可以⾃⼰尝试改造这个算法。
总之就是⽤⼀个 64 bit 的数字中各个 bit 位来设置不同的标志位，区分每⼀个 ID。
4.2 SnowFlake算法的代码实现
SnowFlake 算法的⼀个典型Java实现代码，可以参见⽂章中的第“6.5 ⽅案四：SnowFlake 算法的思想分析”节：《通俗易懂：如何设计能⽀撑百万并发的数据库架构？》，是Jack Jiang曾在某项⽬中实际使⽤过的代码。
4.3 SnowFlake算法的优缺点
广东民俗对于份布式的业务系统来说，SnowFlake算法的优缺点如下。
► 优点：
1)毫秒数在⾼位，⾃增序列在低位，整个ID都是趋势递增的；
2)不依赖数据库等第三⽅系统，以服务的⽅式部署，稳定性更⾼，⽣成ID的性能也是⾮常⾼的；
3)可以根据⾃⾝业务特性分配bit位，⾮常灵活。
► 缺点：
强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可⽤状态。
5、UidGenerator改进后的SnowFlake算法
通过上节，我们知道了原版SnowFlake算法的基本构成。
具体是，原版SnowFlake算法核⼼组成：
原版SnowFlake算法各字段的具体意义是：
1)1位sign标识位；
2)41位时间戳；
泊妃3)10位workId(即5位数据中⼼id+5位⼯作机器id)；
4)12位⾃增序列。
⽽UidGenerator改进后的SnowFlake算法核⼼组成如下图：
简单来说，UidGenerator能保证“指定机器 & 同⼀时刻 & 某⼀并发序列”，是唯⼀，并据此⽣成⼀个64 bits的唯⼀ID(long)，且默认采⽤上图字节分配⽅式。
与原版的snowflake算法不同，UidGenerator还⽀持⾃定义时间戳、⼯作机器id和序列号等各部分的位数，以应⽤于不同场景(详见源码实现)。
如上图所⽰，UidGenerator默认ID中各数据位的含义如下：
1)sign(1bit)：固定1bit符号标识，即⽣成的UID为正数。
2)delta seconds (28 bits)：当前时间，相对于时间基点"2016-05-20"的增量值，单位：秒，最多可⽀持约8.7年(注意：(a)这⾥的
单位是秒，⽽不是毫秒！ (b)注意这⾥的⽤词，是“最多”可⽀持8.7年，为什么是“最多”，后⾯会讲)。
3)worker id (22 bits)：机器id，最多可⽀持约420w次机器启动。内置实现为在启动时由数据库分配，默认分配策略为⽤后即弃，后
续可提供复⽤策略。
虎皮鹦鹉怎么分公母4)sequence (13 bits)：每秒下的并发序列，13 bits可⽀持每秒8192个并发(注意下这个地⽅，默认⽀持qps最⼤为8192个)。6、UidGenerator的具体代码实现分析
通过阅读UidGenerator的源码可知，UidGenerator的具体实现有两种选择，即 DefaultUidGenerator 和 CachedUidGenerator。我们分别来看看这两个具体代码实现的精妙之处。
6.1 DefaultUidGenerator
DefaultUidGenerator 的源码很清楚的说明了⼏个⽣成ID的关键位的实现逻辑。
1)delta seconds(28 bits)：
这个值是指当前时间与epoch时间的时间差，且单位为秒。epoch时间就是指集成DefaultUidGenerator⽣成分布式ID服务第⼀次上线的时间，可配置，也⼀定要根据你的上线时间进⾏配置，因为默认的epoch时间可是2016-09-20，不配置的话，会浪费好⼏年的可⽤时间。
2)worker id(22bits)：
接下来说⼀下DefaultUidGenerator是如何给worker id赋值的，搭建DefaultUidGenerator的话，需要创建⼀个表：
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',
2寸证件照片尺寸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;
DefaultUidGenerator会在集成⽤它⽣成分布式ID的实例启动的时候，往这个表中插⼊⼀⾏数据，得到的id值就是准备赋给workerId的值。由于workerId默认22位，那么，集成DefaultUidGenerator⽣成分布式ID的所有实例重启次数是不允许超过4194303次(即2^22-1)，否则会抛出异常。
3)sequence(13bits)：
核⼼代码如下，⼏个实现的关键点：
a. synchronized保证线程安全；
b. 如果时间有任何的回拨，那么直接抛出异常；
c. 如果当前时间和上⼀次是同⼀秒时间，那么sequence⾃增。如果同⼀秒内⾃增值超过2^13-1，那么就会⾃旋等待下⼀秒
(getNextSecond)；
d. 如果是新的⼀秒，那么sequence重新从0开始。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论