源码解析之Seata项目中的分布式ID生成算法
源码解析之Seata项目中的分布式ID生成算法
一、背景
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发号的方式实现：
(来源：https://tech.meituan.com/2017/04/21/mt-leaf.html)
阿里内部使用订单号，因为涉及到LDC逻辑单元部署，涉及到大促时的弹性部署，涉及到数据版本、业务标示等等要求，其实现方案要更严格一些，但原理，也是对snowflake进行了扩展，将原来的三个组成部分扩展成了多个组成部分，比如用固定位置固定长度的bit位来标示LDC路由值，用另外N位标示弹性，最后用N位来支持并发。因此，基本是全依赖的策略。
万变不离其中，只要了解了内部实现逻辑，就可以结合自身业务做出适合的改造和优化。