拆解雪花算法生成规则

拆解,雪花,算法,生成,规则 · 浏览次数 : 133

小编点评

3.3.4 生成ID见代码中注释 序号5: 此时我们拿到了时间位(timestamp - from)、机器位(instanceId )、序列号位(sequence),所以就可以计算最终的ID了。((timestamp - from) << timestampLeftShift) // (当前时间 - 起始时间) 向左移位| (instanceId << instanceIdShift) // 机器位 向左移位| sequence; // 序列位①((timestamp - from) << timestampLeftShift) 计算时间位from是固定的1422720000000, timestampLeftShift = 12 + 10.我们假设timestamp = 1422720000001。也就是from刚刚过去1毫秒。1毫秒也是我们时间位倒数第二小的值,因为0是最小值。时间位取值范围[0, 2^41 - 1],从这也可以看出上边描述时间位时为什么把时间段特意标注了,因为时间位存的不是具体时间,而是以from为起始来算的过去了多少时间。来看下 1<<22 结果图2: 时间位移位结果图2可以看出,时间位向左移位22,位置正好到第一个时间位。②(instanceId << instanceIdShift) 计算机器位为了方便计算,这里我们假设instanceId 等于1,机器位取值范围[0,-1]。那么机器位就是 1 << 12图3: 机器位移位结果图3可以看出,机器位左移12位,位置正好到第一个机器位。③按照 ① | ② | sequence 进行或运算进行生成ID现在我们有了时间位的值,机器位的值,就只差序列号位的值,序列号是上面3描述代码生成的,范围是[0, 2^12-1]。为了方便计算,我们假设sequence = 1那么 ID = ① | ② | 1.进行或运算图4: ID = ① | ② | 1下图是按照上面逻辑生成的ID图5: 程序生成结果3.3.5 注意:雪花算法需要用单例方式生成ID因为雪花算法会依赖上一次生成的ID的时间来判断是否需要对序列号进行增加的操作,如果不是单例,两个业务用两个对象同时获取ID,则可能会生成相同的ID。if (timestamp < lastTimestamp) { throw new RuntimeException(String.format(\"Clock moved backwards. Refusing to generate id for %d milliseconds\", lastTimestamp - timestamp));}如果业务的异常容忍度低,这里我们可以对其进行优化,如果时间回拨时间较短,比如配置5ms以内,那么可以直接等待一定的时间,让机器的时间追上来.也可以利用扩展位,将64-bit的机器位或者序列号位预留出2-bit的防止时钟回滚的扩展位。5 ID逆运算如果线上出现ID重复,如何进行问题定位?对ID进行逆运算拿到ID的时间位、机器位、序号位。就可以进行下一步分析了。以上述生成的4198401为例5.1 时间时间位 = ID / 2^(机器位 + 序列号位) + from时间位 = 4198401 / 2^(12 + 10) + 1422720000000 = 1422720000001与 above生成ID时用时间位相符注意:ID / 2^(机器位 + 序列号位) 是整数5.2 机器机器位 = (ID / 2^序列号位 ) % 2^(机器位)机器位 = (1025) % 1024 = 1与above生成ID时用机器位数值相符5.3 序列号ID % 2^序列号位序列号 = 4198401 % = 4198401 % 1024 = 1与above生成ID时用的序列号数值相符6 资料开源代码scala版本:https://github.com/twitter-archive/snowflake作者:京东物流 马红岩来源:京东云开发者社区 自猿其说Tech.归纳总结以上内容,生成内容时需要带简单的排版

正文

1 介绍

雪花算法(Snowflake)是一种生成分布式全局唯一ID的算法,生成的ID称为Snowflake IDs或snowflakes。这种算法由Twitter创建,并用于推文的ID。目前仓储平台生成ID是用的雪花算法修改后的版本。

雪花算法几个特性

  • 生成的ID分布式唯一和按照时间递增有序,毫秒数在高位,自增序列在低位,整个ID都是趋势递增的。

  • 不依赖数据库等三方系统,稳定性更高,性能非常高的。

  • 可以根据自身业务特性分配bit位,非常灵活。

2 其他分布式唯一ID生成方案

2.1 数据库生成

以MySQL为例,单库单表,给字段设置auto_increment来生成全局唯一ID
优点:

  • 非常简单,维护成本比较低

  • ID唯一,单调递增,可以设置固定步长

缺点:

  • 可用性难以保证,每次生成ID都需要访问数据库,瓶颈在于单台MySQL读写性能上,如果数据库挂掉会造成服务不可用,这是一个致命的问题

2.2 UUID

UUID是由一组32位数的16进制数字所构成,故UUID理论上的总数为1632=2128,约等于3.4 x 10^38。也就是说若每纳秒产生1兆个UUID,要花100亿年才会将所有UUID用完。UUID的标准型式包含32个16进制数字,以连字号分为五段,形式为8-4-4-4-12的32个字符。示例:550e8400-e29b-41d4-a716-446655440000
优点:

  • 本地生成ID,不需要进行远程调用,没有网络耗时

  • 基本没有性能上限

缺点:

  • 可读性差

  • 长度过长,16字节128位,生成的UUID通常是36位(包含-),有些场景可能不适用。如果用作数据库主键,在MySQL的InnoDB引擎下长度过长,二级索引(非主键索引)会占用很大的空间。

  • 无法保证趋势递增,在MySQL的InnoDB引擎下,新插入数据会根据主键来寻找合适位置,会导致频繁的移动、分页增加了很多开销。

3 snowflake算法实现细节

3.1拆解64bit位

snowflake生成的id通常是一个64bit数字,java中用long类型。
image.png
图1:snowflake算法中的64-bit划分方式

  • 1-bit不用于生成ID(符号位) long 范围[-2^(64-1), 2^(64-1) ] , (64-1)中的1代表的就是符号位

  • 41-bit时间戳(毫秒)可以表示1 x 2^41 / (1000 x 3600 x 24 x 365) = 69年的时间

  • 10-bit可以分别表示1 x 2^10 = 1024台机器,范围[0,1023]

  • 12-bit表示1ms内自动递增的序列号,1 x 2^12 = 4096个 范围[0,4095]。单机1ms可以生成4096个不重复的ID

通过上述方式进行生成ID,可以保证1024台机器在任意69年的时间段里不会出现重复的ID,而且单台机器支持一秒能够生成409.6万个ID。
  这种方式可以支撑大部分业务,如果不满足,可以根据自身业务特点来调整不同命名空间占用的bit数。如果我们有划分IDC的需求,可以将10-bit分5-bit给IDC,分5-bit给工作机器。这样就可以表示32个IDC,每个IDC下可以有32台机器。如果我们的机器位比较特殊,数值相对较大,但是对并发要求不高,还可以将时间位调整为秒级,时间位节省出10-bit留给机器位。

  • 1-bit符号位

  • 31-bit时间戳(秒)1 x 2^31/ (3600 x 24 x 365) = 68年

  • 22-bit机器位 运维平台给提供的数值 范围 [0,2^22-1]

  • 10-bit序列号 范围[0, 2^10 - 1]共1024个

通过上述方式进行生成ID,可以保证4194303台机器在任意68年的时间段里不会出现重复的ID,而且单台机器支持一秒能够生成1024个ID。

3.2 Java实现

public class IdGenerator {
    // 起始时间
    private final long from = 1422720000000L;
    // 机器位所占bit位数
    private final long instanceIdBits = 10L;
    // 序列号所占bit位数
    private final long sequenceBits = 12L;

    // 机器位左移长度
    private final long instanceIdShift = sequenceBits;
    // 时间位左移长度
    private final long timestampLeftShift = sequenceBits + instanceIdBits;

    // 序号1: 最大机器ID
    private final long maxInstanceId = -1L ^ (-1L << instanceIdBits);
    // 最大序列号
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    private long instanceId;
    private long sequence = 0L;
    private long lastTimestamp = -1L;

    public IdGenerator(long instanceId) {
        if (instanceId > maxInstanceId || instanceId < 0) {
            throw new IllegalArgumentException(String.format("instance Id can't be greater than %d or less than 0", maxInstanceId));
        }
        this.instanceId = instanceId;
    }
    //  序号2:
    public synchronized long nextId() {
        long timestamp = timeGen();
        //  序号3:
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }
        //  序号4:
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                timestamp = tilNextSecs(lastTimestamp);
            }
        } else {
            sequence = 0L;
        }

        lastTimestamp = timestamp;
        //  序号5:
        return ((timestamp - from) << timestampLeftShift)  // (当前时间 - 起始时间) 向左移位
                | (instanceId << instanceIdShift)  // 机器位 向左移位
                | sequence; // 序列位
    }

    private long tilNextSecs(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    private long timeGen() {
        return System.currentTimeMillis();
    }
}



3.3一些疑问

3.3.1 为什么bit位置只利用了63位?

因为long在java中占8字节,每字节8bit,一共64bit,其中有1个bit位是符号位不能用做生成ID,如果符号位也用来做ID中的1个bit为会导致ID出现负数,影响趋势递增特性。

3.3.2 计算最大机器ID

见代码中注释 序号1
maxInstanceId = -1L ^ (-1L<<instanceIdBits)
等价于 maxInstanceId = -1 ^( -1<<10)
① -1二进制

1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111

② -1左移10位 -1<<10 二进制

1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1100 0000 0000

①与②进行异或运算 异或运算:同为假,异为真,所以最终结果应该为

0000 0000 0000 0000 0000 0000 0000 00000000 0000 0000 0000 0000 0011 1111 1111

最后:maxInstanceId = 2^10 - 1 = 1023
sequenceMask 计算方法相同,结果为2^12 - 1 = 4095

3.3.3 计算序列号位

见代码中注释 序号4

if (lastTimestamp == timestamp) {
    sequence = (sequence + 1) & sequenceMask;
    if (sequence == 0) {
        timestamp = tilNextSecs(lastTimestamp);
    }
} else {
    sequence = 0L;
}



其中这段代码的是计算序列号的代码主要逻辑是,如果上个生成ID的时间位与当前ID的时间位冲突,则会生成一个序列号进行区分,如果序列号用尽,则等待下一个时间点再生成。如果上个生成ID的时间位与当前ID的时间位不冲突,则将序列号设置成0。

sequence = (sequence + 1) & sequenceMask,序列号最大值sequenceMask为4095,等价于如下这种写法。

sequence = (sequence + 1);
if(sequence == 4095){
    sequence = 0;
}



其实这两种写法的结果是一致的,就是对(sequence + 1)进行取余。
这里有个位运算知识点 k % m = k & (m - 1),m需要满足 m = 2^n,sequenceMask = 2^12 - 1。所以刚好可以用与运算进行取余操作,效率杠杠滴。

3.3.4 生成ID

见代码中注释 序号5:
 此时我们拿到了时间位(timestamp - from)、机器位(instanceId )、序列号位(sequence),所以就可以计算最终的ID了。

((timestamp - from) << timestampLeftShift)  // (当前时间 - 起始时间) 向左移位
| (instanceId << instanceIdShift)  // 机器位 向左移位
| sequence; // 序列位



①((timestamp - from) << timestampLeftShift) 计算时间位
from是固定的1422720000000, timestampLeftShift = 12 + 10.我们假设timestamp = 1422720000001。也就是from刚刚过去1毫秒。1毫秒也是我们时间位倒数第二小的值,因为0是最小值。时间位取值范围[0, 2^41 - 1],从这也可以看出上边描述时间位时为什么把时间段特意标注了,因为时间位存的不是具体时间,而是以from为起始来算的过去了多少时间。
来看下 1<<22 结果

image.png

图2: 时间位移位结果

图2可以看出,时间位向左移位22,位置正好到第一个时间位。

②(instanceId << instanceIdShift) 计算机器位
为了方便计算,这里我们假设instanceId 等于1,机器位取值范围[0,-1]。
那么机器位就是 1 << 12
image.png

图3: 机器位移位结果

图3可以看出,机器位左移12位,位置正好到第一个机器位。

③按照 ① | ② | sequence 进行或运算进行生成ID
现在我们有了时间位的值,机器位的值,就只差序列号位的值,序列号是上面3描述代码生成的,范围是[0, 2^12-1]。为了方便计算,我们假设sequence = 1
那么 ID = ① | ② | 1。进行或运算

image.png

图4: ID = ① | ② | 1

下图是按照上面逻辑生成的ID
image.png

图5: 程序生成结果

3.3.5 注意:雪花算法需要用单例方式生成ID

因为雪花算法会依赖上一次生成的ID的时间来判断是否需要对序列号进行增加的操作,如果不是单例,两个业务用两个对象同时获取ID,则可能会生成相同的ID

4 关于雪花算法的一些思考

机器位怎么取值

  • 主机唯一标识 如果运维平台有机器唯一标识,可以在运维平台取。不过需要考虑机器位能否容纳下唯一标识,可能会过长,也需要考虑运维平台的唯一标识未来变化。

  • 可根据ip进行计算 如果能保证不同机房的机器ip不重复,可以利用ip来计算机器位,IP最大 255.255.255.255。而(255+255+255+255) < 1024,因此采用IP段数值相加即可生成机器位,不受IP位限制。不过这种方式也不是绝对ok,要根据自身情况在选择,比如10.0.5.2 与 10.0.2.5 计算出来也是相同的。使用这种IP生成机器位的方法,必须保证IP段相加不能重复

  • 通过数据库/redis/zk等进行协调,在应用启动的时候给每个机器分配不会重复的机器位id。

时钟回拨问题

雪花算法强依赖时间,如果时间发生回拨,有可能会生成重复的ID,在我们上面的nextId中我们用当前时间和上一次的时间进行判断,如果当前时间小于上一次的时间那么肯定是发生了回拨,雪花算法的做法是简单的抛出了一个异常。

if (timestamp < lastTimestamp) {
   throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}



如果业务的异常容忍度低,这里我们可以对其进行优化,如果时间回拨时间较短,比如配置5ms以内,那么可以直接等待一定的时间,让机器的时间追上来。也可以利用扩展位,将64-bit的机器位或者序列号位预留出2-bit的防止时钟回滚的扩展位。

5 ID逆运算

如果线上出现ID重复,如何进行问题定位?对ID进行逆运算拿到ID的时间位、机器位、序号位。就可以进行下一步分析了。以上述生成的4198401为例

5.1 时间

时间位 = ID / 2^(机器位 + 序列号位) + from
时间位 = 4198401 / 2^(12 + 10) + 1422720000000 = 1422720000001
与上述生成ID时用时间位相符
注意:ID / 2^(机器位 + 序列号位) 是整数

5.2 机器

机器位 = (ID / 2^序列号位 ) % 2^(机器位)
机器位 = (4198401 / 2^12) % 2^10= (1025) % 1024 = 1
与上述生成ID时用机器位数值相符

5.3 序列号

ID % 2^序列号位
序列号 = 4198401 % = 4198401 % 1024 = 1
与上述生成ID时用的序列号数值相符

6 资料

开源代码scala版本:https://github.com/twitter-archive/snowflake

作者:京东物流 马红岩

来源:京东云开发者社区 自猿其说Tech

与拆解雪花算法生成规则相似的内容:

拆解雪花算法生成规则

雪花算法(Snowflake)是一种生成分布式全局唯一ID的算法,生成的ID称为Snowflake IDs或snowflakes。这种算法由Twitter创建,并用于推文的ID。目前仓储平台生成ID是用的雪花算法修改后的版本。

拆解LangChain的大模型记忆方案

之前我们聊过如何使用LangChain给LLM(大模型)装上记忆,里面提到对话链ConversationChain和MessagesPlaceholder,可以简化安装记忆的流程。下文来拆解基于LangChain的大模型记忆方案。

任务拆解,悠然自得,自动版本的ChatGPT,AutoGPT自动人工智能AI任务实践(Python3.10)

当我们使用ChatGPT完成某些工作的时候,往往需要多轮对话,比如让ChatGPT分析、翻译、总结一篇网上的文章或者文档,再将总结的结果以文本的形式存储在本地。过程中免不了要和ChatGPT“折冲樽俎”一番,事实上,这个“交涉”的过程也可以自动化,AutoGPT可以帮助我们自动拆解任务,没错,程序能

ElasticSearch性能原理拆解

逐层拆分ElasticSearch的概念 Cluster:集群,Es是一个可以横向扩展的检索引擎(部分时候当作存储数据库使用),一个Es集群由一个唯一的名字标识,默认为“elasticsearch”。在配置文件中指定相同的集群名,Es会将相同集群名的节点组成一个集群。 Node:节点,集群中的任意一

用户订阅付费如何拆解分析?看这篇就够了

会员制的订阅付费在影音娱乐行业中已相当普及,近几年,不少游戏厂商也开始尝试订阅收费模式。在分析具体的用户订阅偏好以及订阅付费模式带来的增长效果时,我们常常会有这些疑问: 如何从用户的整体付费行为中具体拆解订阅付费事件并分析? 想要了解当前应用内用户的整体订阅概况? 订阅用户和非订阅用户在留存与付费偏

PPT 动态迷幻图谱

迷幻动画的本质拆解 插件: islide + 软件: PowerPoint https://www.islide.cc/ 圆型 画一个正圆,无填充色,边框 2.25磅 左边红色、右边黄色、中间两个透明度 100% 三角型 曲线 动画 持续时间2秒 (PPT“催眠术”——如何设计一个动态的迷幻图谱)[

硬核案例分享,一文带你拆解PHP语言体系下的容器化改造

本文介绍了PHP语言体系应用现代化案例,实现了许多与业务无关的通用性应用改造方案,如PHP应用容器化架构方案、基于Prometheus的弹性伸缩方案等等,为此类型客户提供了一个可参考的案例。

[转帖]把大象装入货柜里——Java容器内存拆解

https://blog.mygraphql.com/zh/notes/java/native-mem/java-native-mem-case/ 介绍 测试环境 配置容量 POD 容量配置 JVM 容量配置 神秘的 MaxDirectMemorySize 默认值 maxThreadCount 最大

[转帖]数据库市场创变者步入商业化元年,拆解PingCAP平凯星辰成长逻辑

https://baijiahao.baidu.com/s?id=1714562859232358591&wfr=spider&for=pc PingCAP平凯星辰(以下简称PingCAP)成立于2015年,在产业和学术界受广泛认可,以独特的产品和生态价值,赋能国内外1500+企业数字化。PingC

生产制造关键业务模型拆解与平台化演进

产品生产制造是制造企业的核心业务活动,本期基于对生产制造活动的关键业务模型拆解来普及相关的基础业务知识,然后介绍传统信息化架构下生产制造活动涉及的主要应用系统,最后介绍基于统一数字平台构建业务一体化应用的企业数字化系统方案。