开发者社区> 问答> 正文

Snowflake 算法如何实现?

Snowflake 算法如何实现?

展开
收起
kun坤 2020-04-24 10:49:39 782 0
1 条回答
写回答
取消 提交回答
  • 现在我们来分析一下 Github 上 beyondfengyu 大佬基于 Java 实现的 SnowFlake,完整代码如下:

    /**
     * twitter的snowflake算法 -- java实现
     * 
     * @author beyond
     * @date 2016/11/26
     */
    public class SnowFlake {
    
        /**
         * 起始的时间戳
         */
        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;//上一次时间戳
    
        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;
        }
    
        /**
         * 产生下一个ID
         *
         * @return
         */
        public synchronized long nextId() {
            long currStmp = getNewstmp();
            if (currStmp < lastStmp) {
                throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
            }
    
            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 = new SnowFlake(2, 3);
    
            for (int i = 0; i < (1 << 12); i++) {
                System.out.println(snowFlake.nextId());
            }
    
        }
    }
    

    在详细分析之前,我们先来回顾一下 Snowflake 算法的 ID 构成图:

    snowflake-64bit (1).jpg

    ID 位分配

    首位不用,默认为 0。41bit(第2-42位)时间戳,是相对时间戳,通过当前时间戳减去一个固定的历史时间戳生成。在 SnowFlake 类定义了一个 long 类型的静态变量 START_STMP,它的值为 1480166465631L:

    /**
     * 起始的时间戳:Sat Nov 26 2016 21:21:05 GMT+0800 (中国标准时间)
     */
    private final static long START_STMP = 1480166465631L;
    
    

    接着继续定义三个 long 类型的静态变量,来表示序列号和工作机器 ID 的占用位数:

    /**
     * 每一部分占用的位数
     */
    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); // 31
    private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT); // 31
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT); // 4095
    
    

    构造函数

    SnowFlake 类的构造函数,该构造函数含有 datacenterId 和 machineId 两个参数,它们分别表示数据中心 id 和机器标识:

    
    private long datacenterId;  //数据中心
    private long machineId;     //机器标识
    
    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;
    }
    
    

    生成 id

    在 SnowFlake 类的实现中,在创建完 SnowFlake 对象之后,可以通过调用 nextId 方法来获取 ID。有的小伙伴可能对位运算不太清楚,这里先简单介绍一下 nextId 方法中,所用到的位运算知识。

    按位与运算符(&)

    参加运算的两个数据,按二进制位进行 “与” 运算,它的运算规则:

    0&0=0;  0&1=0;  1&0=0;  1&1=1;
    

    即两位同时为 1,结果才为 1,否则为 0。

    • 清零:如果想将一个单元清零,只需要将它与一个各位都为零的数值相与即可。
    • 取一个数指定位的值:若需获取某个数指定位的值,只需把该数与指定位为 1,其余位为 0 所对应的数相与即可。

    按位或运算(|) 参加运算的两个对象,按二进制位进行 “或” 运算,它的运算规则:

    0|0=0; 0|1=1; 1|0=1; 1|1=1;
    

    即仅当两位都为 0 时,结果才为 0。

    左移运算符 <<

    将一个运算对象的各二进制位全部左移若干位(左边的二进制位丢弃,右边补 0)。若左移时舍弃的高位不包含1,则每左移一位,相当于该数乘以 2。

    在了解完位运算的相关知识后,我们再来看一下 nextId 方法的具体实现:

    /**
     * 产生下一个ID
     *
     * @return
     */
    public synchronized long nextId() {
      // 获取当前的毫秒数:System.currentTimeMillis(),该方法产生一个当前的毫秒,这个毫秒
      // 其实就是自1970年1月1日0时起的毫秒数。
      long currStmp = getNewstmp();
      
      // private long lastTimeStamp = -1L; 表示上一次时间戳
      // 检测是否出现时钟回拨
      if (currStmp < lastStmp) {
         throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
      }
    
      // 相同毫秒内,序列号自增
      if (currStmp == lastStmp) {
         // private long sequence = 0L; 序列号
         // MAX_SEQUENCE =      4095 111111111111
         // MAX_SEQUENCE + 1 = 4096 1000000000000
         sequence = (sequence + 1) & MAX_SEQUENCE;
         // 同一毫秒的序列数已经达到最大
           if (sequence == 0L) {
               // 阻塞到下一个毫秒,获得新的时间戳
               currStmp = getNextMill();
           }
         } else {
                //不同毫秒内,序列号置为0
                sequence = 0L;
       }
    
       lastStmp = currStmp;
       
       // MACHINE_LEFT = SEQUENCE_BIT; -> 12
       // DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT; -> 17
       // TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT; -> 22
       return (currStmp - START_STMP) << TIMESTMP_LEFT //时间戳部分
                    | datacenterId << DATACENTER_LEFT       //数据中心部分
                    | machineId << MACHINE_LEFT             //机器标识部分
                    | sequence;                             //序列号部分
    }
    

    现在我们来看一下使用方式:

    public static void main(String[] args) {
      SnowFlake snowFlake = new SnowFlake(2, 3);
      for (int i = 0; i < (1 << 12); i++) {
        System.out.println(snowFlake.nextId());
      }
    }
    

    现在我们已经可以利用 SnowFlake 对象生成唯一 ID 了,那这个唯一 ID 有什么用呢?这里举一个简单的应用场景,即基于 SnowFlake 的短网址生成器,其主要思路是使用 SnowFlake 算法生成一个整数,然后对该整数进行 62 进制编码最终生成一个短地址 URL。对短网址生成器感兴趣的小伙伴,可以参考 徐刘根 大佬在码云上分享的工具类。

    最后我们来简单总结一下,本文主要介绍了什么是 Snowflake(雪花)算法、Snowflake 算法 ID 构成图及其优缺点,最后详细分析了 Github 上 beyondfengyu 大佬基于 Java 实现的 SnowFlake。在实际项目中,建议大家选用基于 Snowflake 算法成熟的开源项目,如百度的 UidGenerator 或美团的 Leaf。

    2020-04-24 11:01:10
    赞同 展开评论 打赏
问答分类:
问答地址:
问答排行榜
最热
最新

相关电子书

更多
数据+算法定义新世界 立即下载
袋鼠云基于实时计算的反黄牛算法 立即下载
Alink:基于Apache Flink的算法平台 立即下载