分布式ID生成器

比眉伴天荒 2022-01-17 08:03 360阅读 0赞

## 0.背景 ##

公司产品线最初为了快速上线、快速迭代，所使用的ID采用把JDK原生的32位(去掉四个-)或者36位的原始UUID(Universally Unique Identifier)缩短为19位，且不丢失精度的方式。

例如：`E3MGMM6SQwsaZqHfcIs`

但是UUID太长而且人类不可读（由大写、小写、数字随机组成），且对数据库性能有一定的影响（短且数字递增的最优），所以希望开发出一种全局唯一性、高性能、纯数字、较短、趋势递增的分布式ID生成器。

## 1.需求/设计 ##

*  ID不重复、全局唯一
 *  长度简短：长度尽量保持短（最好在10位以内），方便用户转述、记录、投诉
 *  能通过ID区分业务类型，例如A开头的表示国内机票
 *  推荐使用纯数字
 *  性能要高
 *  适应分布式环境
 *  趋势递增

业界常用的ID如下所示：（作为参考）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9qaWVuaXlpbWlhby5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]  
暂定参考设计为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9qaWVuaXlpbWlhby5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]

## 2.UUID ##

#### 2.1概念 ####

UUID 含义是通用唯一识别码 (Universally Unique Identifier)，这是一个软件建构的标准。  
也是被开源软件基金会 (Open Software Foundation, OSF) 的组织应用在分布式计算环境领域的一部分。  
UUID 的目的，是让分布式系统中的所有元素，都能有唯一的辨识资讯，而不需要透过中央控制端来做辨识资讯的指定。

UUID保证对在同一时空中的所有机器都是唯一的。通常平台会提供生成的API。  
按照开放软件基金会(OSF)制定的标准计算，用到了以太网卡地址、纳秒级时间、芯片ID码和许多可能的数字

#### 2.2优缺点 ####

*  优点：  
    UUID的好处是生成和使用简单、性能好、本地生成、没有高可用风险、而且在全球范围内任意分布式系统中都不会重复，不用考虑数据库主键的冲突等。
 *  缺点：  
    缺陷在于生成的结果串会比较长；由大写、小写、数字随机组成，人类完全不可读，不可记；在进行ID转述过程中特别容易出错；查询效率低，数据库的主键若使用数字的性能要高于字符串。

#### 2.3一个生成19位UUID的算法 ####

JDK自带的UUID类中toString方法其实是把128位字节转换为16进制数值，若使用62进制，既0-9a-zA-Z，这样就能缩短UUID到19位。为此，专门编写了一个UUID字符串生成法。  
详见：[超短的19位UUID，性能几乎翻倍提升][19_UUID]

## 3.数据库自增ID ##

使用数据库的id自增策略，如 MySQL 的 auto\_increment。并且可以使用两台数据库分别设置不同步长，生成不重复ID的策略来实现高可用。  
能够保证严格有序，但是有严重的性能瓶颈。项目组最早就是使用这种方式，性能低下、吃了不少苦头。

为了解决性能低的问题，可以采用批量生成ID的方式缓解。  
主要思想为：一次按需批量生成多个ID，每次生成都需要访问数据库，将数据库修改为最大的ID值，并在内存中记录当前值及最大值。

## 4.类snowflake方案 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9qaWVuaXlpbWlhby5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]

*  1bit:一般是符号位，不做处理
 *  41bit:用来记录时间戳，这里可以记录69年，如果设置好起始时间比如今年是2018年，那么可以用到2089年，到时候怎么办？要是这个系统能用69年，我相信这个系统早都重构了好多次了。
 *  10bit:10bit用来记录机器ID，总共可以记录1024台机器，一般用前5位代表数据中心，后面5位是某个数据中心的机器ID
 *  12bit:循环位，用来对同一个毫秒之内产生不同的ID，12位可以最多记录4095个，也就是在同一个机器同一毫秒最多记录4095个，多余的需要进行等待下毫秒。

优点：  
毫秒数在高位，自增序列在低位，整个ID都是趋势递增的。  
生成ID的性能也是非常高的。  
可以根据自身业务特性分配bit位，非常灵活。

缺点：  
强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。  
上面只是方案和思路，需要落地实现

详见：[ID 生成器 雪花算法][ID _]

## 5.Leaf——美团点评分布式ID生成系统 ##

Leaf是美团开源的分布式ID生成器，能保证全局唯一性、趋势递增、单调递增、信息安全，里面也提到了几种分布式方案的对比，但也需要依赖关系数据库、Zookeeper等中间件。  
详见：[Leaf——美团点评分布式ID生成系统][Leaf_ID]

## 6.百度UidGenerator(项目中最终使用该方案) ##

UidGenerator是Java实现的, 基于Snowflake算法的唯一ID生成器。  
UidGenerator通过借用未来时间来解决sequence天然存在的并发限制; 采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费, 同时对CacheLine补齐，避免了由RingBuffer带来的硬件级「伪共享」问题. 最终单机QPS可达600万  
依赖版本：Java8及以上版本, MySQL(内置WorkerID分配器, 启动阶段通过DB进行分配; 如自定义实现, 则DB非必选依赖）  
详见：[baidu/uid-generator][baidu_uid-generator]

## 7. Redis生成ID ##

Redis的所有命令操作都是单线程的，本身提供像 incr 和 increby 这样的自增原子命令，所以能保证生成的 ID 肯定是唯一有序的  
类似数据库自增ID，性能优于数组库自增

## 8.参考文献 ##

*  [全局唯一ID设计][ID]
 *  [分布式唯一ID的几种生成方案][ID 1]
 *  [分布式ID生成器 | 架构师之路][ID_ _]
 *  [Leaf——美团点评分布式ID生成系统][Leaf_ID]
 *  [baidu/uid-generator][baidu_uid-generator]
 *  [百度开源分布式id生成器uid-generator源码剖析][id_uid-generator]
 *  [uid-generator-spring-boot-starter][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9qaWVuaXlpbWlhby5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: /images/20220117/d2aafef106264809bb49a4ddafd8ebb1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9qaWVuaXlpbWlhby5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]: /images/20220117/daa47b64360f4d249efe272066ad5eff.png
[19_UUID]: https://www.iteye.com/topic/1134781
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9qaWVuaXlpbWlhby5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]: /images/20220117/a2bd967953ed43ada1d104746bf1930b.png
[ID _]: https://blog.csdn.net/wangming520liwei/article/details/80843248
[Leaf_ID]: https://tech.meituan.com/2017/04/21/mt-leaf.html
[baidu_uid-generator]: https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md
[ID]: https://www.jianshu.com/p/61817cf48cc3
[ID 1]: https://juejin.im/post/5b3a23746fb9a024e15cad79
[ID_ _]: https://mp.weixin.qq.com/s?__biz=MjM5ODYxMDA5OQ==&mid=2651960245&idx=1&sn=5cef3d8ca6a3e6e94f61e0edaf985d11&chksm=bd2d06698a5a8f7fc89056af619b9b7e79b158bceb91bdeb776475bc686721e36fb925904a67&mpshare=1&scene=23&srcid=0627tlxFe54jtvb2Ju57eIc2#rd
[id_uid-generator]: https://www.cnblogs.com/yeyang/p/10226284.html
[uid-generator-spring-boot-starter]: https://github.com/wujun234/uid-generator-spring-boot-starter