当前位置:   article > 正文

分布式唯一ID-雪花算法_雪花散列

雪花散列

于今日,看到了久违的太阳,在此纪念一下。

于今日,终于看到久违的太阳

下面步入正题。

世上没有两片相同的雪花。

背景

在复杂的分布式系统中,常常需要为某条数据或消息生成一个全局唯一的标识。例如请求的 RequestId,支付流水号,订单号等。

因此分布式唯一ID的生成方案不可或缺,对于这个唯一ID有以下要求:

  • 全局唯一性,ID 之间不能重复
  • 单调递增,即下一个生成的 ID 要比上一个大,满足某些特定业务的排序要求
  • 趋势递增,ID 的总体趋势是递增的,为了保证数据库存储的性能
  • 信息安全,要求 ID 是无规则的,如果是简单的单调递增,则容易被爬虫或是被竞对推测订单量

另外作为分布式系统中一个基础的服务,对于服务的高吞吐,高可用也有严格的要求。

方案

唯一ID的生成方案主要可以概括为两类:

  • 第一类基于第三方中间件,例如数据库,Redis 等,虽然实现简单,但引入了系统复杂度,易受中间件故障影响,且存在读写的性能问题
  • 第二类基于特定算法本地生成,例如雪花算法,UUID等,特点的是性能好,且系统复杂度较低

基于数据库的实现方案可以参照美团的这篇文章,里面有相关问题的解决方案,其中双 buffer 优化的思想很有启示意义:https://tech.meituan.com/2017/04/21/mt-leaf.html

我们部门目前使用的是雪花算法,下面也主要讲雪花算法相关的实现。

雪花算法

该算法使用分段思想,通过 时间戳 + 机器ID + 自增序列 组合生成一个长度为 64 位的 Long 类型ID。

  • 1位标识,由于long基本类型在Java中是带符号的,最高位是符号位,正数是0,负数是1,所以id一般是正数,最高位是0
  • 时间戳 占用41bit,精确到毫秒,总共可以容纳约69年的时间(需要注意的是:不是指当前时间戳,而是和时间戳相关)
  • 工作节点ID 占用10bit,其中高位5bit是数据中心ID,低位5bit是工作节点ID,可以容纳1024个节点
  • 自增序列号 占用12bit,每个节点每毫秒从0开始不断累加(实际应用一般不从 0 开始累加,会随机一个起始数),最多可以累加到4095

具体实现主要涉及以下核心点:

  • 时间戳信息,工作节点ID的计算
  • 自增序列号的处理
  • 系统时针倒退问题
  • 多个节点时间不同步问题
  • 安全性
时间戳信息

下面是 id 生成的公式:

long id = ((timestamp - twepoch) << timestampLeftShift) | (workerId << workerIdShift) | sequence;
  • 1

可以看到时间戳信息 = timestamp - twepoch,其中 timestamp 为当前时间,而 twepoch 则是自定义的一个起始时间,为什么需要这个时间呢?

时间戳信息占总长的 41 bit ,如果直接用当前时间作为时间戳信息,则会浪费 41 bit 能表示的数据集中绝大部分,故让其减去 twepoch,twepoch 一般设置为系统投入生产的时间。

另外 41 bit 时间戳最多能表示 69 年,如果用完了怎么办?

互联网行业,能活 69 年的企业已经很不容易了(手动狗头),即使真活了那么久,系统可能也经历了多次重构,所以暂且不考虑这个问题。

工作节点ID

美团 Leaf-snowflake 的实现中是通过 zookeeper 为集群中每个节点生成唯一的工作节点ID。

个人觉得,如果单纯只是想生成唯一的工作节点ID,没有必要引入
zookeeper,可以根据 HostName + IP地址编码 的方式生成节点ID(我们便是如此)。

自增序列号

自增序列号的作用是防止同一毫秒,同一节点产生重复的ID,占 12 bit,最大为 4095。

如果同一毫秒同一节点存在多个生成ID的请求,则会触发自增序列自增,
如果自增序列打满了,则会阻塞到下一毫秒。

另外每当时间戳发生变更(当前时间戳与上一次生成的时间戳作比较),都会重置自增序列的值,如果想让ID分布足够散列,可以重置到一个随机值。

如何判断自增序列打满了,算法中通过与运算的方式,sequenceMask 为自增序列的掩码(低12位都为1,其余位为0),如果结果 sequence = 0,则说明自增序列被打满溢出了。

sequence = (sequence + 1) & sequenceMask;
  • 1
时钟倒退

即系统时间发生了回退,如果不做处理,则会生成重复ID。

针对这个问题,每次生成id后,记录一个最后生成时间 lastTimestamp,可以用来判断系统时钟是否发生倒退(currentTimestamp < lastTimestamp)。

如果发生了倒退,可以有如下几种处理方案:

  • 直接响应 Error
  • 如果偏差较小(如5毫秒以内),可以做一层重试,重试失败则触发报警
  • 直接摘除发生时钟倒退的节点,暂时不再对外提供服务
节点时间不同步

节点间时间不同步,可能会导致ID不满足严格的单调递增。

举个例子:存在两个节点 worker1,worker2,worker1 的时钟落后于 worker2,即使 worker1 上的 ID 后生成,也可能小于 worker2 先生成的 ID。

如果业务对于 ID 的单调递增有严格要求,则需要解决这个问题,美团 Leaf-snowflake 是通过启动时,节点间的时间协商解决这个问题的。

假设当前节点的系统时间为 currentTime,集群内节点的平均系统时间为 averageTime,如果 currentTime - averageTime > 阈值,则认为当前节点的时间发生大步长偏移,当前节点启动失败并触发报警。

具体实现可以参看原文:https://tech.meituan.com/2017/04/21/mt-leaf.html

安全性

安全性指的是生成的ID是否存在信息泄露的危险。

比如:如果订单号是简单的自增(每次+1),那么竞争对手只要前后两天同一时间,分别下一单,然后通过订单号相减就能推测你们这一天之间的订单量了,你说安不安全。

当然雪花算法满足安全性要求,它的ID主要是根据时间戳生成的,并没有和订单的增长逻辑直接关联,另外自增序列 sequence 的随机散列也可以保证信息安全。

综上所述,雪花算法满足分布式唯一ID对于唯一性,单调递增性,安全性的要求,无论在实现复杂度,还是性能方面都有很大的优势,且,能适用于大部分业务场景。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/402218
推荐阅读
相关标签
  

闽ICP备14008679号