Reminance's Studio.

分布式唯一id：snowflake算法[转]

java 工作 算法
字数统计: 2.6k阅读时长: 10 min
2019/07/12 Share

@TOC

分布式唯一id：snowflake算法思考

缘起

为什么会突然谈到分布式唯一id呢？原因是最近在准备使用RocketMQ，看看官网介绍：

一句话，消息可能会重复，所以消费端需要做幂等。为什么消息会重复后续RocketMQ章节进行详细介绍，本节重点不在这里。

为了达到业务的幂等，必须要有这样一个id存在，需要满足下面几个条件：

同一业务场景要全局唯一。
该id必须是在消息的发送方进行产生发送到MQ。
消费端根据该id进行判断是否重复，确保幂等。
在那里产生，和消费端进行判断等和这个id没有关系，这个id的要求就是局部唯一或者全局唯一即可，由于这个id是唯一的，可以用来当数据库的主键，既然要做主键那么之前刚刚好发过一篇文章：从开发者角度谈Mysql（1）：主键问题，文章重点提到为什么需要自增、或者趋势自增的好处。（和Mysql数据存储做法有关）。

那么该id需要有2个特性：

局部、全局唯一。

趋势递增。

如果有方法可以生成全局唯一（那么在局部也一定唯一了），生成分布式唯一id的方法有很多。大家可以看看分布式系统唯一ID生成方案汇总：http://www.cnblogs.com/haoxinyue/p/5208136.html
（由于微信不是他的地址都显示不出来，所以把地址贴出来下），这个文章里面提到了很多以及各各的优缺点。
本文关注重点是snowflake算法，该算法实现得到的id就满足上面提到的2点。

snowflake算法

snowflake是Twitter开源的分布式ID生成算法，结果是一个long型的ID。其核心思想是：使用41bit作为毫秒数，10bit作为机器的ID（5个bit是数据中心，5个bit的机器ID），12bit作为毫秒内的流水号（意味着每个节点在每毫秒可以产生 4096 个 ID），最后还有一个符号位，永远是0。

该算法实现基本就是二进制操作，如果二进制不熟悉的可以看看我之前写的相关文章：java二进制相关基础、二进制实战技巧。

这个算法单机每秒内理论上最多可以生成1000*(2^12)，也就是409.6万个ID，（吼吼，这个得了的快啊）。

java实现代码基本上就是类似这样的（都差不多，基本就是二进制位操作）：
参考：https://www.cnblogs.com/relucent/p/4955340.html

稍作修改整理, 感谢原作者

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
package com.cloud.demo.common.core.util;

import lombok.AllArgsConstructor;
import lombok.Builder;
import lombok.NoArgsConstructor;

/**
 *<p>
 *twitter的snowflake算法 -- java实现
 *</p>
 */
@Builder
@NoArgsConstructor
@AllArgsConstructor
public class SnowFlake {

    public SnowFlake(long datacenterId, long machineId) {
        if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {
            throw new IllegalArgumentException("datacenterId can't be greater than MAX_DATACENTER_NUM or less than 0");
        }
        if (machineId > MAX_MACHINE_NUM || machineId < 0) {
            throw new IllegalArgumentException("machineId can't be greater than MAX_MACHINE_NUM or less than 0");
        }
        this.datacenterId = datacenterId;
        this.machineId = machineId;
    }

    /**
     * 起始的时间戳
     */
    private final static long START_STMP = 1480166465631L;

    //每一部分占用的位数
    /**
     * 序列号占用的位数
     */
    private final static long SEQUENCE_BIT = 12;
    /**
     * 机器标识占用的位数
     */
    private final static long MACHINE_BIT = 5;
    /**
     * 数据中心占用的位数
     */
    private final static long DATACENTER_BIT = 5;

    /**
     * 每一部分的最大值
     */
    private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
    private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);

    /**
     * 每一部分向左的位移
     */
    private final static long MACHINE_LEFT = SEQUENCE_BIT;
    private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
    private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;

    /**
     * 数据中心
     */
    private long datacenterId;

    /**
     * 机器标识
     */
    private long machineId;

    /**
     * 序列号
     */
    private long sequence = 0L;

    /**
     * 上一次时间戳
     */
    private long lastStmp = -1L;

    /**
     * 产生下一个ID
     * 如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候抛出异常
     * @return
     */
    public synchronized long nextId() {
        long currStmp = getNewstmp();
        if (currStmp < lastStmp) {
            throw new RuntimeException(String.format("Refusing to generate id during clock backwards for %d milliseconds", lastStmp - currStmp));
        }

        if (currStmp == lastStmp) {
            //相同毫秒内，序列号自增
            sequence = (sequence + 1) & MAX_SEQUENCE;
            //同一毫秒的序列数已经达到最大
            if (sequence == 0L) {
                currStmp = getNextMill();
            }
        } else {
            //不同毫秒内，序列号置为0
            sequence = 0L;
        }

        lastStmp = currStmp;

        return (currStmp - START_STMP) << TIMESTMP_LEFT
                | datacenterId << DATACENTER_LEFT
                | machineId << MACHINE_LEFT
                | sequence;
    }

    private long getNextMill() {
        long mill = getNewstmp();
        while (mill <= lastStmp) {
            mill = getNewstmp();
        }
        return mill;
    }

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

    public static void main(String[] args) {

        SnowFlake snowFlake = SnowFlake.builder().datacenterId(20).machineId(5).build();
//        SnowFlake snowFlake = SnowFlake.builder().build();
//        SnowFlake snowFlake = new SnowFlake(31, 3);
//        SnowFlake snowFlake = new SnowFlake();

        for (int i = 0; i < (1 << 12); i++) {
            System.out.println(i + ":" + snowFlake.nextId());
        }

    }
}

优点：

快（哈哈，天下武功唯快不破）。
没有啥依赖，实现也特别简单。
知道原理之后可以根据实际情况调整各各位段，方便灵活。

缺点：

只能趋势递增。（有些也不叫缺点，网上有些如果绝对递增，竞争对手中午下单，第二天在下单即可大概判断该公司的订单量，危险！！！）
依赖机器时间，如果发生回拨会导致可能生成id重复。
下面重点讨论时间回拨问题。
snowflake算法时间回拨问题思考
由于存在时间回拨问题，但是他又是那么快和简单，我们思考下是否可以解决呢？ 零度在网上找了一圈没有发现具体的解决方案，但是找到了一篇美团不错的文章：Leaf——美团点评分布式ID生成系统（https://tech.meituan.com/MT_Leaf.html）
文章很不错，可惜并没有提到时间回拨如何具体解决。下面看看零度的一些思考：

分析时间回拨产生原因

第一：人物操作，在真实环境一般不会有那个傻逼干这种事情，所以基本可以排除。
第二：由于有些业务等需要，机器需要同步时间服务器（在这个过程中可能会存在时间回拨，查了下我们服务器一般在10ms以内（2小时同步一次））。

解决方法

由于是分布在各各机器自己上面，如果要几台集中的机器（并且不做时间同步），那么就基本上就不存在回拨可能性了（曲线救国也是救国，哈哈），但是也的确带来了新问题，各各结点需要访问集中机器，要保证性能，百度的uid-generator产生就是基于这种情况做的（每次取一批回来，很好的思想，性能也非常不错）https://github.com/baidu/uid-generator。
如果到这里你采纳了，基本就没有啥问题了，你就不需要看了，如果你还想看看零度自己的思考可以继续往下看看（零度的思考只是一种思考 可能也不一定好，期待你的交流。），uid-generator我还没有细看，但是看测试报告非常不错，后面有空的确要好好看看。

下面谈谈零度自己的思考，之前也大概和美团Leaf作者交流了下，的确零度的这个可以解决一部分问题，但是引入了一些其他问题和依赖。是零度的思考，期待更多的大佬给点建议。

时间问题回拨的解决方法：

当回拨时间小于15ms，就等时间追上来之后继续生成。
当时间大于15ms时间我们通过更换workid来产生之前都没有产生过的来解决回拨问题。
首先把workid的位数进行了调整（15位可以达到3万多了，一般够用了）

Snowflake算法稍微调整下位段：

sign(1bit)
固定1bit符号标识，即生成的畅途分布式唯一id为正数。
delta seconds (38 bits)
当前时间，相对于时间基点”2017-12-21”的增量值，单位：毫秒，最多可支持约8.716年
worker id (15 bits)
机器id，最多可支持约3.28万个节点。
sequence (10 bits)
每秒下的并发序列，10 bits，这个算法单机每秒内理论上最多可以生成1000*(2^10)，也就是100W的ID，完全能满足业务的需求。
由于服务无状态化关系，所以一般workid也并不配置在具体配置文件里面，看看我这篇的思考，为什么需要无状态化。高可用的一些思考和理解，这里我们选择redis来进行中央存储（zk、db）都是一样的，只要是集中式的就可以。

下面到了关键了：
现在我把3万多个workid放到一个队列中（基于redis），由于需要一个集中的地方来管理workId，每当节点启动时候，（先在本地某个地方看看是否有 借鉴弱依赖zk 本地先保存），如果有那么值就作为workid，如果不存在，就在队列中取一个当workid来使用（队列取走了就没了 ），当发现时间回拨太多的时候，我们就再去队列取一个来当新的workid使用，把刚刚那个使用回拨的情况的workid存到队列里面（队列我们每次都是从头取，从尾部进行插入，这样避免刚刚a机器使用又被b机器获取的可能性）。

有几个问题值得思考：

如果引入了redis为啥不用redis下发id？（查看分布式系统唯一ID生成方案汇总会获得答案，我们这里仅仅是用来一致性队列的，能做一致性队列的基本都可以)。

引入redis就意味着引入其他第三方的架构，做基础框架最好是不要引用（越简单越好，目前还在学习提高）。

redis一致性怎么保证？（redis挂了怎么办，怎么同步，的确值得商榷。可能会引入会引入很多新的小问题）。

总结

所以选择类似百度的那种做法比较好，集中之后批取，零度的思考虽然思考了，但是从基础组件来看并不是特别合适，但是也算一种思路吧。期待与大佬们的交流。

转自:匠心零度-分布式唯一id：snowflake算法思考

原文作者：Reminance

原文链接：https://reminance.github.io/2019/07/12/20190712-01/

发表日期：July 12th 2019, 10:30:16 pm

更新日期：March 2nd 2021, 3:40:33 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 分布式唯一id：snowflake算法思考
    1. 1.1. 缘起
      1. 1.1.1. 局部、全局唯一。
      2. 1.1.2. 趋势递增。
    2. 1.2. snowflake算法
      1. 1.2.1. 优点：
      2. 1.2.2. 缺点：
        1. 1.2.2.1. 分析时间回拨产生原因
        2. 1.2.2.2. 解决方法
        3. 1.2.2.3. 时间问题回拨的解决方法：
    3. 1.3. 有几个问题值得思考：
    4. 1.4. 总结
Total : 15
2021
2020
2019
生活 面试 总结 java 日签 工作 算法 redis SpringBoot 网络工具 内网穿透 JAVA mysql 索引 HTTPS sentinel spring cloud
工作 生活 spring-cloud