谈谈分布式系统中的唯一ID生成

墨蓝 2023-10-02 21:30 56阅读 0赞

### 前言 ###

我们目前主流的服务端系统都是分布式的架构。业务分布在不同的机器节点上产生数据，数据也存储在不同的机器节点。为了方便标识数据，我们使用 `唯一且有序` 的ID来标识数据。即：

*  整个分布式系统中，新生成的ID永远不会产生与之前已经生成的ID重复；
 *  生成的所有ID可以根据生成的时间进行排序（生成时间晚的排序顺序靠后）

我们来看一下市面上的几种主流的ID生成方案。

### 一、Mysql 集群 ###

由于我们的讨论前提是分布式架构的系统，所以这里的 Mysql 我们默认是集群版。

众所周知，Mysql 有自带的唯一ID机制，即自增主键，可以保证在同一个数据库中，表内生成的每一条记录都是唯一且有序的。

![format_png][]

但是如果放在分布式系统里面，我们用分库/分表的架构存储记录， **那就会导致在系统中产生重复的ID** 。

如下图，表1 2 3都是存储相同记录的不同表（可以在同一个数据库里，也可以在不同数据库里），表1 2 3都会产生id相同的数据。

![format_png 1][]

为了解决这个问题，mysql 官方支持数据库 ID 生成时设置步长，可以保证不同数据库中相同表的id唯一性。

![format_png 2][]

如上图，每个表都有 **不同的起始id和相同的步长** ，这就能保证业务记录Id的唯一性。

设置步长的方案虽然解决了id生成的唯一性，但是也有很大的缺点

*  不能保证ID的有序性和时间的强相关。（由于是分布式系统，不能保证id=4的数据一定在id=3的数据后面生成）
 *  每次新增加一个节点，要重置所有节点的起始值和步长。

第二点只是数据库管理会麻烦一些，但是第一点不能满足我们对有序性的要求。

### 二、ID数据库 ###

这里泛指一套单独维护的ID数据库，目的是为了保证业务系统内所有的ID的唯一性和有序性。

举几个例子，比如Mysql维护一条表记录，Redis 维护一个key，zookeeper 维护一个序列号。当所有业务都通过调用这些存储服务来生成+获取唯一ID的时候，就可以保证生成Id的唯一性和有序性。

缺点：

*  需要资源单独维护一个服务
 *  如果ID数据库挂掉，整个业务就会停摆。如果ID数据库出现数据错乱，可能会影响到唯一性和有序性

总结一下就是，ID数据库可以提供唯一有序的ID，但是有一定的维护成本且系统的风险很高。

### 三、雪花算法 ###

SnowFlake是Twitter公司采用的一种算法，目的是在分布式系统中产生 **全局唯一且整体递增** 的ID。

### 3.1 生成ID的结构 ###

![format_png 3][]

毫秒

### 3.2 生成原理 ###

我们先看一下雪花ID的生成过程：

1.  生成毫秒级别的时间戳，填充到 41bit 的位置
2.  序列号默认为 `000000000000` 。如果 **新生成的时间戳上次生成的相等** ，序列号就会 + 1。将序列号填充到 12bit 位置
3.  存储当前生成的时间戳到内存中，以便下次生成时判断
4.  获取到当前机器+进程的唯一标识，填充到 10bit 的位置

通过上述整个流程我们可以看到，雪花算法可以确保唯一性，单机内在同一毫秒生成的ID会有序列号的递增，多机环境在同一毫秒生成的ID会有机器+进程的唯一标识。

但是无法保证强有序性，比如多个机器在同一毫秒内生成的ID，就无法按照时间规则进行排序

### 3.3 缺点 ###

雪花算法除了无法实现严格按照时间的有序性之外，还有一个可能存在的风险点，就是 **单机时钟回拨** 。

如果一个机器之前已经生成过ID，将机器的时间改为之前的时间，那么就有一定几率会生成与之前相同的ID。

### 四、mongoDB 的唯一ID生成策略 ###

mongo唯一ID生成策略——ObjectId，和雪花算法相似度极高。区别在于雪花算法要占用64个字节，而 ObjectId 只需要占用 12个字节，但是objectId只能存储秒级别时间戳。

ObjectId如果用字符串表示则有24个字符，但实际上它是由一组十六进制的字符构成，每个字节两位的十六进制数字，总共用了12字节的存储空间。

![format_png 4][]

比如：6331500a7cac81af7136236b 这个ID

秒级时间戳
    机器码
    进程的pid
    序号

mongoDB 的 ObjectId 和雪花算法一样，无法实现严格按照时间的有序性，并且由于是秒级别的时间戳，所以 **不同机器生成的ID，不按照时间排序** 的可能性会大很多。而且如果单机时钟回拨，也会产生与之前重复的ID。

### 总结 ###

<table> 
 <thead> 
  <tr> 
   <th>特性/方案</th> 
   <th>Mysql 集群</th> 
   <th>ID数据库</th> 
   <th>雪花算法</th> 
   <th>mongoDB ObjectId</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>唯一性</td> 
   <td>:white_check_mark:</td> 
   <td>:white_check_mark:</td> 
   <td>:white_check_mark:</td> 
   <td>:white_check_mark:</td> 
  </tr> 
  <tr> 
   <td>按照生成时间的有序性</td> 
   <td>:x:</td> 
   <td>:white_check_mark:</td> 
   <td>:x:</td> 
   <td>:x:</td> 
  </tr> 
  <tr> 
   <td>维护的难易程度</td> 
   <td>难</td> 
   <td>较难</td> 
   <td>易维护</td> 
   <td>易维护</td> 
  </tr> 
 </tbody> 
</table>

在分布式系统中:

*  以上四种方案都可以保证生成ID的唯一性
 *  如果并发量很小的系统，可以考虑 雪花算法/mongoDB ObjectId 方案来保证有序性
 *  如果并发量很大，只能用ID数据库来保证有序性，但是会比 雪花算法/mongoDB ObjectId 方案增加维护成本

[format_png]: https://img-blog.csdnimg.cn/img_convert/959b76c262951d3944d3d2b0bfe31f26.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/e38faddc01f0de69090ff483bd387e6d.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/092e108bc343f22bb4817ed498fad863.webp?x-oss-process=image/format,png
[format_png 3]: https://img-blog.csdnimg.cn/img_convert/939513a856a39f58ad9499aad36f5749.webp?x-oss-process=image/format,png
[format_png 4]: https://img-blog.csdnimg.cn/img_convert/e7cecaeba3b6211427e825ad977ba281.webp?x-oss-process=image/format,png