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

2023-10-13 23:52
文章标签 算法 id 分布式 ... 面试官 雪花 只会答 傻乎乎

本文主要是介绍被面试官问到分布式ID，别再傻乎乎只会答雪花算法了...，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 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

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

6. Snowflake (雪花算法)

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

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

image-20231012223959527

41-bit的时间可以表示（1L<<41）/(1000L360024*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;@PostConstructpublic 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

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);//waittimestamp = timeGen();if (timestamp < lastTimestamp) {//还是小于，抛异常并上报throwClockBackwardsEx(timestamp);}    } catch (InterruptedException e) {  throw  e;}} else {//throwthrowClockBackwardsEx(timestamp);}}//分配ID

7.3 Leaf-snowflake Demo

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

美团Leaf：下载，

然后安装并启动Zookeeper，这里可以参考这个博客：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)
  2. 面试总被问分布式ID？ 美团（Leaf）了解一下 - 掘金 (juejin.cn)
  3. 不能错过的分布式ID生成器（Leaf ），好用的一批！ - 掘金 (juejin.cn)
  4. 分布式ID生成服务的技术原理和项目实战 - 掘金 (juejin.cn)
  5. 【分布式系统】10种分布式唯一ID生成方案总结 - 掘金 (juejin.cn)
  6. 常见分布式ID解决方案总结：数据库、算法、开源组件 - 掘金 (juejin.cn)

这篇关于被面试官问到分布式ID，别再傻乎乎只会答雪花算法了...的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/206731。

相关文章

深入理解Apache Kafka(分布式流处理平台)

深入理解Apache Kafka(分布式流处理平台)

《深入理解ApacheKafka(分布式流处理平台)》ApacheKafka作为现代分布式系统中的核心中间件,为构建高吞吐量、低延迟的数据管道提供了强大支持,本文将深入探讨Kafka的核心概念、架构... 目录引言一、Apache Kafka概述1.1 什么是Kafka？1.2 Kafka的核心概念二、Ka
阅读更多...
openCV中KNN算法的实现

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库，它提供了各
阅读更多...
springboot+dubbo实现时间轮算法

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n
阅读更多...
Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整
阅读更多...
SpringBoot实现MD5加盐算法的示例代码

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.
阅读更多...
mysql数据库重置表主键id的实现

mysql数据库重置表主键id的实现

《mysql数据库重置表主键id的实现》在我们的开发过程中,难免在做测试的时候会生成一些杂乱无章的SQL主键数据,本文主要介绍了mysql数据库重置表主键id的实现,具有一定的参考价值,感兴趣的可以了... 目录关键语法演示案例在我们的开发过程中，难免在做测试的时候会生成一些杂乱无章的SQL主键数据，当我们
阅读更多...
Java时间轮调度算法的代码实现

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组（时间轮）和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时
阅读更多...
redis+lua实现分布式限流的示例

redis+lua实现分布式限流的示例

《redis+lua实现分布式限流的示例》本文主要介绍了redis+lua实现分布式限流的示例,可以实现复杂的限流逻辑,如滑动窗口限流,并且避免了多步操作导致的并发问题,具有一定的参考价值,感兴趣的可... 目录为什么使用Redis+Lua实现分布式限流使用ZSET也可以实现限流，为什么选择lua的方式实现
阅读更多...
Seata之分布式事务问题及解决方案

Seata之分布式事务问题及解决方案

《Seata之分布式事务问题及解决方案》：本文主要介绍Seata之分布式事务问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Seata–分布式事务解决方案简介同类产品对比环境搭建1.微服务2.SQL3.seata-server4.微服务配置事务模式1
阅读更多...
如何通过Golang的container/list实现LRU缓存算法

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣：146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2