微服务架构—Snowflake分布式ID(黑科技)

原创
2018/03/26 09:30
阅读数 1.6W

开源地址https://gitee.com/yu120/sequence

欢迎关注个人公众号查看原文(微服务基础设施QQ交流群):

1 简介

        基于Twitter的Snowflake算法(俗称雪花算法)实现64位自增ID算法。为了满足Twitter每秒上万条消息的请求,每条消息都必须分配一条唯一的ID,这些ID还需要一些大致的顺序(即时序性),并且在分布式系统中不同机器产生的ID必须不同。

 

2 标准Snowflake算法

Twitter的Snowflake算法数据划分如下:

Snowflake算法

信息说明

  • 1位:暂没有使用,二进制中最高位为1的都是负数,但是我们生成的id一般都使用整数,所以这个最高位固定是0

  • 41位:时间戳数据区,用来记录时间戳(毫秒)

    • 41位可以表示241−1个数字,

    • 如果只用来表示正整数(计算机中正数包含0),可以表示的数值范围是:0 至 241−1,减1是因为可表示的数值范围是从0开始算的,而不是1。

    • 也就是说41位可以表示241−1个毫秒的值,转化成单位年则是(241−1)/(1000∗60∗60∗24∗365)=69年

  • 10位:机器数据区,用来记录工作机器id

    • 可以部署在210=1024个节点,包括 5位datacenterId 和 5位workerId

    • 5位(bit) 可以表示的最大正整数是25−1=31,即可以用0、1、2、3、….31这32个数字,来表示不同的datecenterId或workerId

  • 12位:序列号数据区,用来记录同毫秒内产生的不同id

    • 12位(bit) 可以表示的最大正整数是212−1=4096,即可以用0、1、2、3、….4095这4096个数字,来表示同一机器同一时间截(毫秒)内产生的4096个ID序号

SnowFlake优势

  • 所有生成的ID都是按时间趋势递增

  • 整个分布式系统内不会产生重复ID

  • 每个ID中都可以解读出,该ID是在哪个数据中心的哪台工作机器上产生

  • 数值型的分布式ID(替换了UUID)

  • 高性能的ID生成器(超高400w/s的超高性能)

3 Java实现代码

        由于在Java中64bit的整数是Long类型,所以在Java中Snowflake算法生成的ID就是Long来存储的。以下是基于JAVA代码实现的标准Snowflake算法(https://gitee.com/yu120/sequence):

  1/**
  2 * 基于Twitter的Snowflake算法实现分布式高效有序ID生产黑科技(sequence)
  3 * 
  4 * <br>
  5 * SnowFlake的结构如下(每部分用-分开):<br>
  6 * <br>
  7 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
  8 * <br>
  9 * 1位标识,由于long基本类型在Java中是带符号的,最高位是符号位,正数是0,负数是1,所以id一般是正数,最高位是0<br>
 10 * <br>
 11 * 41位时间截(毫秒级),注意,41位时间截不是存储当前时间的时间截,而是存储时间截的差值(当前时间截 - 开始时间截)
 12 * 得到的值),这里的的开始时间截,一般是我们的id生成器开始使用的时间,由我们程序来指定的(如下下面程序IdWorker类的startTime属性)。41位的时间截,可以使用69年,年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>
 13 * <br>
 14 * 10位的数据机器位,可以部署在1024个节点,包括5位datacenterId和5位workerId<br>
 15 * <br>
 16 * 12位序列,毫秒内的计数,12位的计数顺序号支持每个节点每毫秒(同一机器,同一时间截)产生4096个ID序号<br>
 17 * <br>
 18 * <br>
 19 * 加起来刚好64位,为一个Long型。<br>
 20 * SnowFlake的优点是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分),并且效率较高,经测试,SnowFlake每秒能够产生26万ID左右。
 21 * 
 22 * @author lry
 23 */
 24public class Sequence {
 25
 26    /** 起始时间戳,用于用当前时间戳减去这个时间戳,算出偏移量 **/
 27    private final long startTime = 1519740777809L;
 28
 29    /** workerId占用的位数5(表示只允许workId的范围为:0-1023)**/
 30    private final long workerIdBits = 5L;
 31    /** dataCenterId占用的位数:5 **/
 32    private final long dataCenterIdBits = 5L;
 33    /** 序列号占用的位数:12(表示只允许workId的范围为:0-4095)**/
 34    private final long sequenceBits = 12L;
 35
 36    /** workerId可以使用的最大数值:31 **/
 37    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
 38    /** dataCenterId可以使用的最大数值:31 **/
 39    private final long maxDataCenterId = -1L ^ (-1L << dataCenterIdBits);
 40
 41    private final long workerIdShift = sequenceBits;
 42    private final long dataCenterIdShift = sequenceBits + workerIdBits;
 43    private final long timestampLeftShift = sequenceBits + workerIdBits + dataCenterIdBits;
 44
 45    /** 用mask防止溢出:位与运算保证计算的结果范围始终是 0-4095 **/
 46    private final long sequenceMask = -1L ^ (-1L << sequenceBits);
 47
 48    private long workerId;
 49    private long dataCenterId;
 50    private long sequence = 0L;
 51    private long lastTimestamp = -1L;
 52    private boolean isClock = false;
 53
 54    /**
 55     * 基于Snowflake创建分布式ID生成器
 56     * <p>
 57     * 注:sequence
 58     *
 59     * @param workerId     工作机器ID,数据范围为0~31
 60     * @param dataCenterId 数据中心ID,数据范围为0~31
 61     */
 62    public Sequence(long workerId, long dataCenterId) {
 63        if (workerId > maxWorkerId || workerId < 0) {
 64            throw new IllegalArgumentException(String.format("worker Id can\'t be greater than %d or less than 0", maxWorkerId));
 65        }
 66        if (dataCenterId > maxDataCenterId || dataCenterId < 0) {
 67            throw new IllegalArgumentException(String.format("dataCenter Id can\'t be greater than %d or less than 0", maxDataCenterId));
 68        }
 69
 70        this.workerId = workerId;
 71        this.dataCenterId = dataCenterId;
 72    }
 73
 74    public void setClock(boolean clock) {
 75        isClock = clock;
 76    }
 77
 78    /**
 79     * 获取ID
 80     *
 81     * @return
 82     */
 83    public synchronized Long nextId() {
 84        long timestamp = this.timeGen();
 85
 86        // 闰秒:如果当前时间小于上一次ID生成的时间戳,说明系统时钟回退过这个时候应当抛出异常
 87        if (timestamp < lastTimestamp) {
 88            long offset = lastTimestamp - timestamp;
 89            if (offset <= 5) {
 90                try {
 91                    this.wait(offset << 1);
 92                    timestamp = this.timeGen();
 93                    if (timestamp < lastTimestamp) {
 94                        throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", offset));
 95                    }
 96                } catch (Exception e) {
 97                    throw new RuntimeException(e);
 98                }
 99            } else {
100                throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", offset));
101            }
102        }
103
104        // 解决跨毫秒生成ID序列号始终为偶数的缺陷:如果是同一时间生成的,则进行毫秒内序列
105        if (lastTimestamp == timestamp) {
106            // 通过位与运算保证计算的结果范围始终是 0-4095
107            sequence = (sequence + 1) & sequenceMask;
108            if (sequence == 0) {
109                timestamp = this.tilNextMillis(lastTimestamp);
110            }
111        } else {
112            // 时间戳改变,毫秒内序列重置
113            sequence = 0L;
114        }
115
116        lastTimestamp = timestamp;
117
118        /*
119         * 1.左移运算是为了将数值移动到对应的段(41、5、5,12那段因为本来就在最右,因此不用左移)
120         * 2.然后对每个左移后的值(la、lb、lc、sequence)做位或运算,是为了把各个短的数据合并起来,合并成一个二进制数
121         * 3.最后转换成10进制,就是最终生成的id
122         */
123        return ((timestamp - startTime) << timestampLeftShift) |
124            (dataCenterId << dataCenterIdShift) |
125            (workerId << workerIdShift) |
126            sequence;
127    }
128
129    /**
130     * 保证返回的毫秒数在参数之后(阻塞到下一个毫秒,直到获得新的时间戳)
131     *
132     * @param lastTimestamp
133     * @return
134     */
135    private long tilNextMillis(long lastTimestamp) {
136        long timestamp = this.timeGen();
137        while (timestamp <= lastTimestamp) {
138            timestamp = this.timeGen();
139        }
140
141        return timestamp;
142    }
143
144    /**
145     * 获得系统当前毫秒数
146     *
147     * @return timestamp
148     */
149    private long timeGen() {
150        if (isClock) {
151            // 解决高并发下获取时间戳的性能问题
152            return SystemClock.now();
153        } else {
154            return System.currentTimeMillis();
155        }
156    }
157
158}

以下是解决大并发场景中获取时间戳的性能问题:

 1import java.sql.Timestamp;
 2import java.util.concurrent.Executors;
 3import java.util.concurrent.ScheduledExecutorService;
 4import java.util.concurrent.ThreadFactory;
 5import java.util.concurrent.TimeUnit;
 6import java.util.concurrent.atomic.AtomicLong;
 7
 8/**
 9 * 高并发场景下System.currentTimeMillis()的性能问题的优化
10 * <p><p>
11 * System.currentTimeMillis()的调用比new一个普通对象要耗时的多(具体耗时高出多少我还没测试过,有人说是100倍左右)<p>
12 * System.currentTimeMillis()之所以慢是因为去跟系统打了一次交道<p>
13 * 后台定时更新时钟,JVM退出时,线程自动回收<p>
14 * 10亿:43410,206,210.72815533980582%<p>
15 * 1亿:4699,29,162.0344827586207%<p>
16 * 1000万:480,12,40.0%<p>
17 * 100万:50,10,5.0%<p>
18 * @author lry
19 */
20public class SystemClock {
21
22    private final long period;
23    private final AtomicLong now;
24
25    private SystemClock(long period) {
26        this.period = period;
27        this.now = new AtomicLong(System.currentTimeMillis());
28        scheduleClockUpdating();
29    }
30
31    private static class InstanceHolder {
32        public static final SystemClock INSTANCE = new SystemClock(1);
33    }
34
35    private static SystemClock instance() {
36        return InstanceHolder.INSTANCE;
37    }
38
39    private void scheduleClockUpdating() {
40        ScheduledExecutorService scheduler = Executors.newSingleThreadScheduledExecutor(new ThreadFactory() {
41            public Thread newThread(Runnable runnable) {
42                Thread thread = new Thread(runnable, "System Clock");
43                thread.setDaemon(true);
44                return thread;
45            }
46        });
47        scheduler.scheduleAtFixedRate(new Runnable() {
48            public void run() {
49                now.set(System.currentTimeMillis());
50            }
51        }, period, period, TimeUnit.MILLISECONDS);
52    }
53
54    private long currentTimeMillis() {
55        return now.get();
56    }
57
58    public static long now() {
59        return instance().currentTimeMillis();
60    }
61
62    public static String nowDate() {
63        return new Timestamp(instance().currentTimeMillis()).toString();
64    }
65
66}

4 性能测试数据

性能测试数据结果发现,QPS>400w/s(Mac Pro 4C/8GB)

性能测试结果数据

5 缺点分析

  • 强依赖机器时间,如果发生回拨会导致可能生成id重复

  • 夸毫秒ID都是偶数

5.1 时间回拨

产生原因
        分布式环境,每台机器上的时钟不可能完全同步。由于机器时间不一致,需要同步各个服务器的时间而导致时间回拨的产生。

解决方案

  • 在流量最低的时间段进行时间回拨,如半夜没有流量或流量很低时

  • 每次批量获取一批ID(至少这批ID用完前,即可完成时间回拨)

  • 调整ID存储的数据结构

  • 回拨时间小于timeout时间,则通过自旋的方式进行生成

  • 回拨时间大于timeout时间,则通过更换workid来生成(精度有所降低,如可从400w降低至100w,但也完全足够了)

5.2 大量偶数

产生原因
        根据上述算法可知,在同一毫秒内是通过一个自增序列号进行区分不同ID,当时间跳至下一毫秒时,自增ID就会被重置为0。因此,如果线上的交易并发量不是很大时(即都是夸毫秒产生时),生成的所有ID的尾号基本都是0,即基本都是偶数。如果直接应用该ID来做分库分表,则极有可能出现数据不均匀的情况。

解决办法

  • 自增ID满值后再重置

  • 重置时使用范围随机

6 Snowflake扩展

        Snowflake算法并没有什么难度,其存放的数据区总长为64位,以上的数据区划分方式是Twitter给出的标准版,而算法是通用的。因此我们可以根据自己实际的需求,来制定属于我们自己的数据区(业界改造其数据存储结构的大牛也是不少的)。其次,以上算法生成的ID中存有一定是数据信息,因此我们可以解读这个ID来做更多的事,如获取出ID生成的时间、ID生成的数据中心、ID生成的机器ID等信息。

展开阅读全文
打赏
3
26 收藏
分享
加载中
还有一个疑问 ,为什么产生出来的,转换为二进制,只有60位? System.out.println(Long.toBinaryString(id));
2019/07/17 15:25
回复
举报
博主,您好,有两个疑问,第一个这个地方 this.wait(offset << 1); 如果执行了这行代码的话,应该需要有相应的notify,但是文章中貌似没有看到,第二个地方:SystemClock.now()通过这个获取系统时间,在高并发的情况下,测了下效率很低
2019/07/17 15:24
回复
举报
更多评论
打赏
2 评论
26 收藏
3
分享
返回顶部
顶部