源码解析之 Seata 项目中的分布式 ID 生成算法

Coder的技术之路

关注

发布于: 2021 年 05 月 12 日

公众号后台提供高并发历史文章整理版下载，欢迎关注，欢迎交流

一、背景

Saga 作为阿里开源的长事务解决方案，涉及到全局事务 id 的生成和串联，需要保证事务 id 的稳定性和全局唯一性。

二、原理

twitter 开源的 snowflake 算法。

saga 实现的全局唯一的 id 生成算法也是来源于 snowflake。作为最流行的分布式 id 生成算法之一，其实在无数的开源代码中都有看到过他的身影。比如 Sharding-jdbc，在操作分库分表时，也使用了该算法来生成分布式 id。

由上图可以看出，雪花算法是由 4 个部分组合而成的：符号位+41 位时间戳+10 位机器码+12 位序列号。

这么组合的好处是什么呢？这就要从分布式 ID 的具体使用要求来看了：

全局唯一：在分布式部署的环境下，相同机器上，不同机器之间，不能出现重复 ID。
数据安全：如果涉及到如订单号类的 ID 透出诉求，则需要考虑用非连续 ID 来隐藏生产状况。

snowflake 用时间戳+机器码保证不同机器之间的 ID 互不相同；用时间戳+序列号的方式保证同一机器上的 ID 唯一。

我们从它的组合方式也能看出来,该算法对唯一性的保障是强依赖机器时钟的，一旦时钟回拨，功能将异常。

snowflake 本身更强调的是无三方依赖，完全本地自主完成。当然，除了无依赖的策略之外，还有半依赖和纯依赖的方式。一些业务场景需要保证递增（至少是趋势递增），来做业务上的排序等判断处理。这个就需要使用额外的一些组件来配合使用了，如 mysql 批量发号缓存策略。我们在最后一部分运用里再说。

三、源码解析

首先，需要定义 ID 组合方式所需的常量，如每段占用位数等

/* 开始时间 (2020-05-03) */private final long twepoch = 1607529600000L;
/* 机器码所占的bit位数 = 10位 */private final long workerIdBits = 10L;
/* 最大支持的机器码 = 1023，该式子相当与~(-1L << 10L) */ private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
/* 序列号所占的bit位数 */private final long sequenceBits = 12L;
/* 机器码需要在序列号的左边 */private final long workerIdShift = sequenceBits;
/* 时间戳的起始位置在序列号和机器码的左边 */private final long timestampLeftShift = sequenceBits + workerIdBits;
/* 序列号的最大支持数值 */private final long sequenceMask = -1L ^ (-1L << sequenceBits);复制代码

复制代码

然后，定义三个位段的含义字段

/* 机器码 (0 ~ 1023) */private long workerId;
/* 序列号 (0 ~ 4095) */private long sequence = 0L;
/* 最后时间戳 */private long lastTimestamp = -1L;复制代码

复制代码

接下来，就是生产分布式 ID 的核心

构建机器码，机器码和服务所在机器的 ip 地址有关，初始化后一般无需改变：

InetAddress address;try {    //获取本机IP    address = InetAddress.getLocalHost();} catch (final UnknownHostException e) {    throw new IllegalStateException("Cannot get LocalHost InetAddress, please check your network!",e);}byte[] ipAddressByteArray = address.getAddress();//机器码一共需要10位，所以取段倒数第二个段取最后2位 + 倒数第一段全部8位return ((ipAddressByteArray[ipAddressByteArray.length - 2] & 0B11) << Byte.SIZE) + (ipAddressByteArray[ipAddressByteArray.length - 1] & 0xFF);复制代码

复制代码

获取下一个 ID

//当前时间戳long timestamp = System.currentTimeMillis()//如果当前时间戳 < 最后记录时间戳 ，则可能发生时钟回拨，异常中断if (timestamp < lastTimestamp) {    throw new RuntimeException(String.format(        "clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));}//如果当前时间戳 == 最后记录时间戳 if (lastTimestamp == timestamp) {    //计算下一个序列号,这里&4095的作用是循环，因为到4096会变成0    sequence = (sequence + 1) & sequenceMask;    //如果下一个序列号==0，则说明同一时间戳内序列号以用完，设置下一时间戳为最后时间戳    if (sequence == 0) {        //该方法内部while循环直到当前时间>最后时间           timestamp = tilNextMillis(lastTimestamp);    }} else {    sequence = 0L;}lastTimestamp = timestamp;//时间戳和指定时间的差 左移 12+10 | 机器码 左移12  | 序列号 return ((timestamp - twepoch) << timestampLeftShift) | (workerId << workerIdShift) | sequence;复制代码

复制代码

四、运用

因为 saga 这里生成的分布式 ID 只是来保证用来串联分布式事务的 ID 的唯一性。所以，使用无依赖的策略就完全够用。如果业务中有此类串联业务的诉求，可以直接使用该方法。

然鹅，很大一部分业务场景，是需要分布式 ID 符合特定业务要求的，比如增量消息，排序消息，涉及 B-tree 索引进行存储时 ID 递增保证效率等等。

美团的 Leaf-snowflake 方案，采用了半依赖的方式，采用依赖 zk 发号的方式实现：

(来源：tech.meituan.com/2017/04/21/…)

阿里内部使用订单号，因为涉及到 LDC 逻辑单元部署，涉及到大促时的弹性部署，涉及到数据版本、业务标示等等要求，其实现方案要更严格一些，但原理，也是对 snowflake 进行了扩展，将原来的三个组成部分扩展成了多个组成部分，比如用固定位置固定长度的 bit 位来标示 LDC 路由值，用另外 N 位标示弹性，最后用 N 位来支持并发。因此，基本是全依赖的策略。

万变不离其中，只要了解了内部实现逻辑，就可以结合自身业务做出适合的改造和优化。

发布于: 2021 年 05 月 12 日阅读数: 17

原文链接:【http://xie.infoq.cn/article/83ea5194c494282d921151465】。文章转载请联系作者。

Coder的技术之路

关注

还未添加个人签名 2018.03.14 加入

一个工作多年的技术人，浪过京东、支付宝，干过电商、搞过支付链路、玩过广告系统~ ，欢迎关注同名微信公众号，有任何想法问题，欢迎大伙交流讨论

发布

暂无评论

创作场景

源码解析之 Seata 项目中的分布式 ID 生成算法

一、背景

二、原理

三、源码解析

四、运用

Coder的技术之路

评论