被面试官问到分布式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。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
dp算法练习题【8】

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。 示例 1： 输入：n = 3输出：5 示例 2： 输入：n = 1输出：1 class Solution {public int numTrees(int n) {int[] dp = new int
阅读更多...
Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数，每次操作将其分成2^q份，对于每一份内部的数进行翻转(逆序)，每次操作完后输出操作后新序列的逆序对数。 图一：  划分子问题。 图二： 分而治之，=>  合并 。 图三： 回溯：
阅读更多...
最大公因数：欧几里得算法

最大公因数：欧几里得算法

简述         求两个数字 m和n 的最大公因数，假设r是m%n的余数，只要n不等于0，就一直执行 m=n，n=r 举例 以18和12为例 m n r18 % 12 = 612 % 6 = 06 0所以最大公因数为：6 代码实现 #include<iostream>using namespace std;/
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2