被面试官问到分布式ID，别再傻乎乎只会答雪花算法了...

亦凉 2024-02-22 09:35 31阅读 0赞

#### 文章目录 ####

*  1. 分布式ID
 *  2. 数据库主键自增
 *  3. 数据库号段模式
 *  4. Redis自增
 *  5. UUID
 *  6. Snowflake (雪花算法)
 *  7. Leaf (美团分布式ID生成系统)
 *   *  7.1 Leaf-segment 号段方案
     *   *  7.1.2 双buffer优化
     *  7.2 Leaf-snowflake方案
     *  7.3 Leaf-snowflake Demo

## 1. 分布式ID ##

在分布式系统中，通常都需要对大量数据和消息进行唯一标识，这个表示通常被称为分布式ID。

分布式ID是用于识别不同实体或数据对象的，这就要求**分布式ID必须具有全局唯一性，不能出现重复的ID**。

并且，由于在复杂的分布式系统下，分布式ID使用的场景很多，这就要求**分布式ID的生成速度应该足够快，并且对本地资源消耗小**。除此之外，生成分布式ID必须是高可用的，因为分布式ID关联着众多系统，必须要求**分布式ID的生成的服务可用性无限趋向于100%**。

> **在业务方面，ID通常有以下两个需求，但是这两个需求是互斥的：**
> 
> 1.  **单调递增**：在某些业务场景，ID必须是单调递增的，也就是上一个ID要比下一个ID要小。例如MySQL事务的版本号。
> 2.  **无规则**：上述的这种ID生成策略，如果遇到恶意的人就能从ID号得到信息。比如存储图片进MySQL的时候，图片的重名是ID自增的，那么别人就可以恶意猜测到下一张图片的URL是啥；再比如，我们所熟悉的订单号，如果订单号是递增的，那么别人就可以知道一天的单量。

现如今，分布式ID的生成方案有很多

1.  数据库主键自增
2.  Redis自增
3.  UUID
4.  Snowflake (雪花算法)
5.  Leaf (美团分布式ID生成系统)
6.  uid-generator (百度分布式ID生成系统)
7.  Tinyid (滴滴分布式ID生成系统)

**本文重点介绍前五种，后两种以后有机会再做介绍~**

--------------------

## 2. 数据库主键自增 ##

在MySQL数据库，我们可以通过创建一个具有主键ID自增字段的表。

每次向数据库中插入一条数据，那么数据库插入的记录的ID就会自增ID。

接着，将这个操作抽象成一个服务，那么这就是一个简单的分布式ID生成服务了。

这样的方式实现的分布式ID系统，**显而易见的简单，优点也是简单方便。**

**但是，这样的实现方式会存在以下缺点**：

1.  **并发性能并不好，受限于MySQL的性能**
2.  **当数据量上来的时候，需要进行分库分表，操作起来复杂**

![img][]

--------------------

## 3. 数据库号段模式 ##

在前面这种通过数据库自增的方式生成ID，每次都需要访问一次数据库，很容易受到数据库上限导致并发低。

因此可以改造为批量获取然后存进内存里，需要用到的时候直接在内存拿即可。

这就是数据库的号段模式，每次请求分配一个号段，号段模式相比主键自增，性能有一定提升。

--------------------

## 4. Redis自增 ##

Redis可以通过自增命令`INCR`将某一个Key进行自增。

并且这一过程是线程安全的，利用这些特性，我们就可以实现一个分布式ID生成系统，也可以在分布式系统中使用。

这样的分布式ID生成系统，**可用性依赖于Redis**。

虽然Redis有AOF与RDB持久化，但是依然会存在数据丢失问题。**一旦数据发送丢失，那么就可以出现ID重复问题**，但是系统出现异常。

![img][img 1]

--------------------

## 5. UUID ##

UUID是通用唯一标识符（Universally Unique Identifier）的缩写。它是由数字和字母组成的32位字符串，用于在计算机系统中唯一地标识实体或资源。UUID的生成算法能够保证在正常情况下几乎不会生成重复的标识符。

UUID中包含了网卡MAC地址、时间戳、名字空间（Namespace）、随机或伪随机数、时序等元素，其就是利用这些元素生成UUID的。

UUID的优点在于**UUID的生成性能非常高，因为UUID是本地生成的，没有任何网络消耗。**

**不过，UUID也存在以下缺点：**

1.  **不易存储**：UUID包含了32个16进制的数字，形成8-4-4-4-12的36个字符，生成的ID太长在很多场景不适用
2.  **信息不安全**：UUID看似无规则，实际其是基于MAC地址生成的，因此有可能泄漏MAC地址，MAC地址是可以被用到定位位置的
3.  **不适用于MySQL主键**：在MySQL官方文档中提到，主键的长度应该越短越好

![img][img 2]

--------------------

## 6. Snowflake (雪花算法) ##

Snowflake，也称雪花算法，是一种用于生成分布式系统中唯一ID的算法。它是Twitter公司开发的，**目的是为了解决分布式系统中高并发场景下生成ID的问题**。

Snowflake算法生成的ID是一个64位整数，其中包含41位的时间戳、10位的机器ID和12位的序列号。

![image-20231012223959527][]

41-bit的时间可以表示（1L<<41）/(1000L*3600*24\*365)=69年的时间，10-bit机器可以分别表示1024台机器。如果我们对IDC划分有需求，还可以将10-bit分5-bit给IDC，分5-bit给工作机器。这样就可以表示32个IDC，每个IDC下可以有32台机器，可以根据自身需求定义。12个自增序列号可以表示2^12个ID，理论上snowflake方案的QPS约为409.6w/s，这种分配方式可以保证在任何一个IDC的任何一台机器在任意毫秒内生成的ID都是不同的。

由于前41为是时间戳，也就是毫秒数，因此**雪花算法生成的ID是趋势自增的**。

雪花算法不依赖与第三方系统，**以服务的方式部署，稳定性更高，生成ID的性能也是非常高的**。

另外，**可以根据业务特性分配bit位，非常灵活**。

当然，雪花算法也存在缺点，那就是**雪花算法强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。**

这是一个雪花算法生成的工具类，是基于`hutool`工具类生成的

@Component
    public class SnowFlake{
        
    
        private Snowflake snowflake;
    
        @PostConstruct
        public void init() {
        
            // 0 ~ 31 位，可以采用配置的方式使用
            long workerId;
            try {
        
                workerId = NetUtil.ipv4ToLong(NetUtil.getLocalhostStr());
            } catch (Exception e) {
        
                workerId = NetUtil.getLocalhostStr().hashCode();
            }
    
            workerId = workerId >> 16 & 31;
    
            long dataCenterId = 1L;
            snowflake = IdUtil.createSnowflake(workerId, dataCenterId);
        }
    
        public synchronized long nextId() {
        
            return snowflake.nextId();
        }
    
    }

--------------------

## 7. Leaf (美团分布式ID生成系统) ##

![img][img 3]

`Leaf` 是美团开源的一个分布式 ID 解决方案。提供了号段模式 和 Snowflake这两种模式来生成分布式 ID。

`Leaf` 具有高可靠、低延迟、全局唯一的特点。

--------------------

### 7.1 Leaf-segment 号段方案 ###

Leaf-segment 号段方案是基于数据库自增方案做的改进。

在数据库自增方案中，每次获取新的ID都需要请求一次数据库，会造成数据库压力很大。

而在Leaf-segment 号段方案中，**改为利用`proxy server`批量获取，每次获取一个`segment(step决定大小)`号段的值。用完之后再去数据库获取新的号段，可以大大的减轻数据库的压力。**

在使用 Leaf-segment 号段方案需要建立DB表

CREATE DATABASE leaf
    CREATE TABLE `leaf_alloc` (
      `biz_tag` varchar(128)  NOT NULL DEFAULT '',
      `max_id` bigint(20) NOT NULL DEFAULT '1',
      `step` int(11) NOT NULL,
      `description` varchar(256)  DEFAULT NULL,
      `update_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
      PRIMARY KEY (`biz_tag`)
    ) ENGINE=InnoDB;
    
    insert into leaf_alloc(biz_tag, max_id, step, description) values('leaf-segment-test', 1, 2000, 'Test leaf Segment Mode Get Id')

> `biz_tag`是用于区分业务的
> 
> `max_id`表示该`biz_tag`目前所被分配的ID号段的最大值
> 
> `step`表示每次分配的号段长度
> 
> 原来获取ID每次都需要写数据库，现在只需要把`step`设置得足够大，比如1000。那么只有当1000个号被消耗完了之后才会去重新读写一次数据库。读写数据库的频率从1减小到了`1/step`
> 
> ![image-20231012230626604][]
> 
> `test_tag`在第一台Leaf机器上是11000的号段，当这个号段用完时，会去加载另一个长度为\`step\`=1000的号段，假设另外两台号段都没有更新，这个时候第一台机器新加载的号段就应该是30014000。同时数据库对应的biz\_tag这条数据的max\_id会从3000被更新成4000，更新号段的SQL语句如下：
> 
>     Begin
>     UPDATE table SET max_id=max_id+step WHERE biz_tag=xxx
>     SELECT tag, max_id, step FROM table WHERE biz_tag=xxx
>     Commit

并配置`leaf.jdbc.url`, `leaf.jdbc.username`,`leaf.jdbc.password`

如果不想使用该模式配置`leaf.segment.enable=false`即可。

![image-20231012230417166][]

Leaf-segment 号段方案有以下优缺点

**优点：**

*  Leaf服务可以**很方便的线性扩展**，性能完全能够支撑大多数业务场景。
 *  ID号码是趋势递增的8byte的64位数字，**满足上述数据库存储的主键要求**。
 *  **容灾性高**：Leaf服务内部有号段缓存，**即使DB宕机，短时间内Leaf仍能正常对外提供服务**。
 *  **可以自定义max\_id的大小**，非常方便业务从原有的ID方式上迁移过来。

缺点：

*  ID号码不够随机，能够泄露发号数量的信息，**不太安全**。
 *  TP999数据波动大，当号段使用完之后还是会hang在更新数据库的I/O上，tg999数据会出现偶尔的尖刺。
 *  DB宕机会造成整个系统不可用。

--------------------

#### 7.1.2 双buffer优化 ####

针对第二个缺点`TP999数据波动大，当号段使用完之后还是会hang在更新数据库的I/O上，tg999数据会出现偶尔的尖刺。`

这其中的耗时主要体现在Leaf取号时机是在号段消耗完进行的，也就意味着**号段临界点的ID下发时间取决于下一次从DB取回号段的时间，也就是这段时间内会导致线程阻塞，倘若请求DB的网络和性能不稳定，会导致整体响应时间变慢**。

**优化思路也很简单，就是希望DB取号段的过程做到无阻塞，也就是在号段消费到某个程度的时候就异步将下一个号段加载进内存中，而不是等待号段消耗完成才去更新号段。**

> ***什么是TP999？***
> 
> TP90就是满足百分之九十的网络请求所需要的最低耗时。
> 
> TP99就是满足百分之九十九的网络请求所需要的最低耗时。
> 
> 同理TP999就是满足千分之九百九十九的网络请求所需要的最低耗时。

![image-20231013201119082][]

美团Leaf对此的优化是采用双Buffer的方式，**Leaf服务内部有两个号段缓存区segment。当前号段已下发10%时，如果下一个号段未更新，则另启一个更新线程去更新下一个号段。当前号段全部下发完后，如果下个号段准备好了则切换到下个号段为当前segment接着下发，循环往复。**

1.  每个biz-tag都有消费速度监控，**通常推荐segment长度设置为服务高峰期发号QPS的600倍（10分钟）**，这样即使DB宕机，Leaf仍能持续发号10-20分钟不受影响。
2.  每次请求来临时都会判断下个号段的状态，从而更新此号段，所以偶尔的网络抖动不会影响下个号段的更新。

--------------------

### 7.2 Leaf-snowflake方案 ###

`Leaf-segment 号段方案`生成的ID是递增的，并不适用与订单场景。

于是`Leaf`还提供了`Leaf-snowflake`方案。

`Leaf-snowflake`方案沿用了`Snowflake`的设计思想，也就1+41+10+12的方式装订ID。

![image-20231013201625617][]

对于`workerID`的分配，当服务集群数量较小的情况下，完全可以手动配置。Leaf服务规模较大，动手配置成本太高。所以使用`Zookeeper`持久顺序节点的特性自动对`snowflake`节点配置`wokerID`。`Leaf-snowflake`是按照下面几个步骤启动的：

1.  启动`Leaf-snowflake`服务，连接`Zookeeper`，在`leaf_forever`父节点下检查自己是否已经注册过（是否有该顺序子节点）。
2.  如果有注册过直接取回自己的`workerID`（zk顺序节点生成的int类型ID号），启动服务。
3.  如果没有注册过，就在该父节点下面创建一个持久顺序节点，创建成功后取回顺序号当做自己的`workerID`号，启动服务。

![image-20231013201734419][]

**该方式除了每次会去ZK拿数据以外，也会在本机文件系统上缓存一个`workerID`文件。这样的好处在于`ZK`出现问题的时候，能确保服务能够正常启动，这样使得`Leaf-snowflake`弱依赖于第三方组件。**

> ***那么`Leaf-snowflake`是如何解决时钟问题呢？***
> 
> `snowflake`算法当时钟回拨的时候，有可能出现重复ID的情况，在`Leaf-snowflake`是这也解决时钟问题的。
> 
> 1.  服务会先检查自己是否写过`ZooKeeper leaf_forever`节点
> 2.  如果写过，则用**自身系统时间与leaf\_forever/$\{self\}节点记录时间做比较**，如果小于则认为机器时间发生回拨，服务启动失败并报警
> 3.  如果没写过，证明是新服务节点，**直接创建持久节点leaf\_forever/$\{self\}并写入自身系统时间**，接下来综合对比其余Leaf节点的系统时间来判断自身系统时间是否准确，具体做法是取leaf\_temporary下的所有临时节点(所有运行中的Leaf-snowflake节点)的服务IP：Port，然后通过RPC请求得到所有节点的系统时间，计算sum(time)/nodeSize。
> 4.  若**abs( 系统时间-sum(time)/nodeSize ) < 阈值**，认为当前系统时间准确，正常启动服务，同时写临时节点leaf\_temporary/$\{self\} 维持租约。
> 5.  否则认为本机系统时间发生大步长偏移，启动失败并报警。
> 6.  每隔一段时间(3s)上报自身系统时间写入leaf\_forever/$\{self\}。
> 
> 由于强依赖时钟，对时间的要求比较敏感，在机器工作时NTP同步也会造成秒级别的回退，建议可以直接关闭NTP同步。要么在时钟回拨的时候直接不提供服务直接返回ERROR\_CODE，等时钟追上即可。**或者做一层重试，然后上报报警系统，更或者是发现有时钟回拨之后自动摘除本身节点并报警**，如下：
> 
>     //发生了回拨，此刻时间小于上次发号时间
>      if (timestamp < lastTimestamp) {
>          
>       			  
>                 long offset = lastTimestamp - timestamp;
>                 if (offset <= 5) {
>          
>                     try {
>          
>                     	//时间偏差大小小于5ms，则等待两倍时间
>                         wait(offset << 1);//wait
>                         timestamp = timeGen();
>                         if (timestamp < lastTimestamp) {
>          
>                            //还是小于，抛异常并上报
>                             throwClockBackwardsEx(timestamp);
>                           }    
>                     } catch (InterruptedException e) {
>            
>                        throw  e;
>                     }
>                 } else {
>          
>                     //throw
>                     throwClockBackwardsEx(timestamp);
>                 }
>             }
>      //分配ID

--------------------

### 7.3 Leaf-snowflake Demo ###

想要使用`Leaf-snowflake`方案，首先需要上GitHub将项目clone下来

美团Leaf：[下载][Link 1]，

然后安装并启动`Zookeeper`，这里可以参考这个博客：[Zookeeper 安装(Windows)\_zookeeper windows安装\_coder i++的博客-CSDN博客][Zookeeper _Windows_zookeeper windows_coder i_-CSDN]

![image-20231013205035860][]

完成后，配置`leaf.properties`，因为这里使用的`snowflake`方案，所以`leaf.segment.enable`设置为`false`，`leaf.snowflake.enable`设置为`true`，并配置`Zookeeper`的地址和端口

leaf.name=com.sankuai.leaf.opensource.test
    leaf.segment.enable=false
    #leaf.jdbc.url=
    #leaf.jdbc.username=
    #leaf.jdbc.password=
    
    leaf.snowflake.enable=true
    leaf.snowflake.zk.address=127.0.0.1
    leaf.snowflake.port=2181

启动`leaf-server`服务，默认端口为8080。但是由于这里我冲突了，所以我将端口设置为8081。

![image-20231013205752630][]

浏览器访问`(http://127.0.0.1:8081/api/snowflake/get/leaf-test)`，就会得到一个ID

![image-20231013205913861][]

对应的调用就是`LeafController`的`getSnowflakeId`方法，这里需要传入一个Key，这个Key可以是用到这个分布式ID生成的服务表示，这样可以做到不同模块之间的分布式ID隔离。

![image-20231013210006358][]

Leaf的简单使用就到这里了，在项目中可以将该项目单独为一个服务，使用`OpenFeign`或是`Dubbo`等RPC框架远程调用获取接口。

--------------------

> **参考：**
> 
> 1.  [Leaf——美团点评分布式ID生成系统 - 美团技术团队 (meituan.com)][Leaf_ID_ - _ _meituan.com]
> 2.  [面试总被问分布式ID？ 美团（Leaf）了解一下 - 掘金 (juejin.cn)][ID_ _Leaf_ - _ _juejin.cn]
> 3.  [不能错过的分布式ID生成器（Leaf ），好用的一批！ - 掘金 (juejin.cn)][ID_Leaf _ - _ _juejin.cn]
> 4.  [分布式ID生成服务的技术原理和项目实战 - 掘金 (juejin.cn)][ID_ - _ _juejin.cn]
> 5.  [【分布式系统】10种分布式唯一ID生成方案总结 - 掘金 (juejin.cn)][10_ID_ - _ _juejin.cn]
> 6.  [常见分布式ID解决方案总结：数据库、算法、开源组件 - 掘金 (juejin.cn)][ID_ - _ _juejin.cn 1]

[img]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/ab3e59980c9645d9a3d569b56d429c59.png
[img 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/df66947242404dd9a472adc494dc86fb.png
[img 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/8be8fd8e151442e68d0a36d3be198075.png
[image-20231012223959527]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/f0ed571359f0496fbbd04baa8d33eb15.png
[img 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/58210c504e314488a5d298a74a098616.png
[image-20231012230626604]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/db6b85a9dec54b258fbaeb56b35eda78.png
[image-20231012230417166]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/dc123939477b4c5aa1849089bce27910.png
[image-20231013201119082]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/a42bc358c7e14a5e8fdf45b56a9efa45.png
[image-20231013201625617]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/a805e84acc5542008731565e4db8aa48.png
[image-20231013201734419]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/42b5658a75514aaa994935f33951325e.png
[Link 1]: https://github.com/Meituan-Dianping/Leaf
[Zookeeper _Windows_zookeeper windows_coder i_-CSDN]: https://blog.csdn.net/weixin_53370274/article/details/126389546
[image-20231013205035860]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/282176d34d574750845bd62e60af708b.png
[image-20231013205752630]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/fb2cc689816044e89e3c90fa136f00aa.png
[image-20231013205913861]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/465d9bf044c84dbe98b630c0502b75fa.png
[image-20231013210006358]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/7e2b88adacad4dac8eda5e9e8047c48a.png
[Leaf_ID_ - _ _meituan.com]: https://tech.meituan.com/2017/04/21/mt-leaf.html
[ID_ _Leaf_ - _ _juejin.cn]: https://juejin.cn/post/6844904082772082696
[ID_Leaf _ - _ _juejin.cn]: https://juejin.cn/post/6858063069000499208
[ID_ - _ _juejin.cn]: https://juejin.cn/post/7156425205391294494
[10_ID_ - _ _juejin.cn]: https://juejin.cn/post/7245891823159590969
[ID_ - _ _juejin.cn 1]: https://juejin.cn/post/7264920202865328187