专栏首页Coder的技术之路源码解析之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位来支持并发。因此,基本是全依赖的策略。

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

本文分享自微信公众号 - Coder的技术之路(gh_1b3189982966),作者:Coder的技术之路

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-02-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 我参与阿里巴巴 ASoC-Seata 的一些感悟

    我先来说说 Seata 这个项目的 idea 是怎么来的。一直就有参与开源项目的打算,一个事物的兴起必定或大或小引发一定的问题,微服务就是这样,分布式事务概念泛...

    用户5397975
  • 全局事务服务 GTS 与 Seata 融合的开始

    Seata(Simple Extensible Autonomous Transaction Architecture)是一款开源的分布式事务解决方案,致力于提...

    用户5397975
  • 看了 5 种分布式事务方案,我司最终选择了 Seata,真香!

    好长时间没发文了,最近着实是有点忙,当爹的第 43 天,身心疲惫。这又赶上年底,公司冲 KPI 强制技术部加班到十点,晚上孩子隔两三个小时一醒,基本没睡囫囵觉的...

    程序员内点事
  • 对比 5 种分布式事务方案,还是宠幸了阿里的 Seata(原理 + 实战)

    好长时间没发文了,最近着实是有点忙,当爹的第 43 天,身心疲惫。这又赶上年底,公司冲 KPI 强制技术部加班到十点,晚上孩子隔两三个小时一醒,基本没睡囫囵觉的...

    程序员内点事
  • Spring Boot 集成 Seata 解决分布式事务问题

    Seata 是 阿里巴巴2019年开源的分布式事务解决方案,致力于在微服务架构下提供高性能和简单易用的分布式事务服务。在 Seata 开源之前,Seata 对应...

    程序员果果
  • 业务无侵入框架Seata, 解决分布式事务问题

    事务的原子性和持久性可以确保在一个事务内,更新多条数据,要么都成功,要么都失败。在一个系统内部,我们可以使用数据库事务来保证数据一致性。那如果一笔交易,涉及到跨...

    用户7676729
  • 对比 5 种分布式事务方案,还是宠幸了阿里的 Seata(原理 + 实战)

    我们先看看百度上对于分布式事务的定义:分布式事务是指事务的参与者、支持事务的服务器、资源服务器以及事务管理器分别位于不同的分布式系统的不同节点之上。

    Bug开发工程师
  • SpringCloud Alibaba 实战教程10-seata1.3整合nacos实现分布式事务

    Seata 是一款开源的分布式事务解决方案,致力于提供高性能和简单易用的分布式事务服务。Seata 将为用户提供了 AT、TCC、SAGA 和 XA 事务模式,...

    gang_luo
  • 分布式事务选型及对比

    如果您也对Java感兴趣,我的文章能帮助到您,加入【Go Big】一起进步。群号:243108249

    envoke
  • 微服务痛点-基于Dubbo + Seata的分布式事务(AT)模式

    Seata 是一款开源的分布式事务解决方案,致力于提供高性能和简单易用的分布式事务服务。Seata 将为用户提供了 AT、TCC、SAGA 和 XA 事务模式,...

    sanshengshui
  • Spring Cloud 中的分布式事务,附源码《一》

    在开发我的开源项目 prex 时,加入工作流,解决工作流用户与当前系统用户同步问题时,涉及到远程调用操作两个数据库所产生的事务问题,比如系统用户在增加用户同步工...

    搜云库技术团队
  • ​深入了解分布式事务组件 Seata (一)

    分布式事务的问题,在微服务架构中一直是难题。单体应用实现本地事务即可,到了分布式环境,情况就变得复杂。一个请求可能涉及多个服务,上下游存在依赖关系,其中的一环失...

    aoho求索
  • [图文] Seata AT 模式分布式事务源码分析

    AT 模式是 Seata 主推的分布式事务解决方案,最早来源于阿里中间件团队发布的 TXC服务,后来成功上云改名 GTS。相较于TCC而言,Seata的AT模式...

    田守枝
  • 深度剖析一站式分布式事务方案Seata(Fescar)-Server

    再前不久,我写了一篇关于分布式事务中间件Fescar的解析,没过几天Fescar团队对其进行了品牌升级,取名为Seata(Simpe Extensible Au...

    用户5397975
  • 分布式事务之解决方案(XA和2PC)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    海仔
  • 分布式事务:SpringBoot+Dubbo+Seata+Nacos 实现案例

    案例源码使用SpringBoot 2.3.2 + Dubbo 2.7.6 + Mybatis 1.3.2 + Nacos 1.3.2 + Seata 1.3.0...

    朝雨忆轻尘
  • 使用Seata彻底解决Spring Cloud中的分布式事务问题!

    随着业务需求的变化,单体应用被拆分成微服务应用,原来的三个模块被拆分成三个独立的应用,分别使用独立的数据源,业务操作需要调用三个服务来完成。此时每个服务内部的数...

    JAVA葵花宝典
  • 使用Seata彻底解决Spring Cloud中的分布式事务问题!

    随着业务需求的变化,单体应用被拆分成微服务应用,原来的三个模块被拆分成三个独立的应用,分别使用独立的数据源,业务操作需要调用三个服务来完成。此时每个服务内部的数...

    macrozheng
  • 分布式事务框架 seata-golang 接入指南

    seata-golang 是一个分布式事务框架,实现了 AT 模式和 TCC 模式,AT 模式相较 TCC 模式对代码的入侵性更小、需要开发的接口更少;但 AT...

    CNCF

扫码关注云+社区

领取腾讯云代金券