SnowFlake算法推演

简介：

snowflake算法目的是为了生成分布式系统唯一ID而产生的，这种算法，可以保持69年使用，高并发情况下1MS可以生成
4096个不同的ID，那么为什么呢?如何做到的呢?

为什么是69年?

首先69年运算可以用2的41次方推算出来时间戳，然后看一下这个时间的量，也就是从1970年开始的
偏移量正好是69年,如果想要更长的时长，只需要加长时间戳的位数即可。

为什么是4096？

同理，12位的sequence，最大数为2的12次方。

MachineId和DataCenterId

作为传参，这两个来区分分布式系统中的唯一性。如果在Java中可以对节点进行唯一识别，不用传参的话，
请告诉我这个方法，我可以改进一下我的实现哦

上一张图:

我们一共需要做2件事和1个注意

事件1：首先生成这4份数据，
事件2：对数据进行移位，比如说 timestamp要左移22位！
注意：此类作为公共组建向外提供，必须要考虑到时间回拨，系统时间篡改，加锁避免并发，拿到相同ID。

CODING原版:

package snowflake;

import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.LinkedHashSet;
import java.util.Set;

/**
 * SnowFlake算法获取分布式唯一ID
 * Created by Nero on 2018-05-08.
 */
public class SnowFlake {


    private static final long START_STAMP = 1480166465631L; //开始时间戳，本算法从这个时间后退96年。。

    //
    private static final long SEQUENCE_BIT = 12;    //***占用的位数
    private static final long MACHINE_BIT = 5;  //机器标识占用bit位
    private static final long DATACENTER_BIT = 5;   //数据中心占用bit位



    //知识点预热 原码，反码，补码
    //异或 相同为0，不同为1
    //同等效果写法还有  (1 << X) - 1 位数的最大值
    private static final long SEQUENCE_BIT_MAX = -1l ^ (-1l << SEQUENCE_BIT);
    private static final long MACHINE_BIT_MAX = -1L ^ (-1L << MACHINE_BIT);
    private static final long DATACENTER_BIT_MAX = -1l ^ (-1l << DATACENTER_BIT);



    //每一部分向左的位移相加的和，现在暂时不明为啥要这样相加
    private static final long MACHINE_LEFT = SEQUENCE_BIT;
    private static final long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
    private static final long TIMESTAMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;


    private long dataCenterId;  //数据中心ID
    private long machineId;     // 机器ID
    private long sequence  = 0L;    //***
    private long lastStmp = -1L;  //上一次用到的时间戳



    public SnowFlake(long dataCenterId, long machineId) {
        if(dataCenterId > DATACENTER_BIT_MAX || dataCenterId < 0){
            throw new IllegalArgumentException("dataCenterId must range form 0 and power of 5 ");
        }
        if(machineId > MACHINE_BIT_MAX || machineId < 0){
            throw new IllegalArgumentException("machineId must range form 0 and power of 5 ");
        }
        this.dataCenterId = dataCenterId;
        this.machineId = machineId;
    }


    /****
     * 获取分布式内唯一ID
     * @return
     */
    public synchronized  long nextId(){
        long currentStmp = getNewTimeStmp();
        if(currentStmp < lastStmp){     //判断时钟回拨
            throw new RuntimeException("Clock moved backwards. Refusing to generate id");
        }

        //固定位数之后，任意数值与最大数值进行&操作都会是它本身，
        // 用下列这种方式，使得sequence的方式永远不可能超过固定位数下的最大值
        // 于是则为   TIME10000-TIME19999 的一个数量区间
        if(currentStmp == lastStmp){    //相同毫秒，采用毫秒内***自增的方式
            sequence =( sequence + 1 ) & SEQUENCE_BIT_MAX;

            //同一毫秒的序列数已经达到最大
            if (sequence == 0L) {
                currentStmp = getNextMill();
            }
        }else{  //不同毫秒内，则置为0
            sequence = 0;
        }
        lastStmp = currentStmp;

        //移位拼接64位，并且与0进行异或，得出十进制结果
        return (currentStmp - START_STAMP) << TIMESTAMP_LEFT //时间戳部分
                | dataCenterId << DATACENTER_LEFT       //数据中心部分
                | machineId << MACHINE_LEFT             //机器标识部分
                | sequence;                             //***部分
    }




    /***
     * 时钟回拨，获取下一个时钟
     * @return
     */
    private long getNextMill(){
        long currentMill = getNewTimeStmp();
        while(currentMill <= lastStmp){
            currentMill = getNewTimeStmp();
        }
        return currentMill;
    }


    /***
     * 获取最新的系统时间
     * @return
     */
    private long getNewTimeStmp(){
        return System.currentTimeMillis();
    }

    public static void main(String[] args) {
        long a = System.currentTimeMillis() - 1480166465631L;
        System.out.println(new SimpleDateFormat("YYYY-MM-dd HH:mm:ss").format(new Date(2199023255552L)));
    }
}

2个位运算：

获取SEQUENCE_BIT位的最大值：-1l ^ (-1l << SEQUENCE_BIT) == (1 << SEQUENCE_BIT) -1
通过&进行递增和重置：sequence =( sequence + 1 ) & SEQUENCE_BIT_MAX;

如果不明白，请访问连接：https://blog.csdn.net/zhang6622056/article/details/80275260

1个移位运算:

        //移位拼接64位，并且与0进行异或，得出十进制结果
        return (currentStmp - START_STAMP) << TIMESTAMP_LEFT //时间戳部分
                | dataCenterId << DATACENTER_LEFT       //数据中心部分
                | machineId << MACHINE_LEFT             //机器标识部分
                | sequence;                             //***部分

如果不明白请看本文中的图，这个移位，只是将所有的数据和0进行异或操作.

修改完的版本：

package snowflake;

import java.util.LinkedHashSet;
import java.util.Set;

/**
 * snowflake变种版本，由41位时间戳+8位地址码+14位序列码构成
 * -风险1：系统时间回拨，比如手动设置当前时间为实际时间之前的时间，可能会引发重复ID问题
 * -风险2：分布式系统或集群系统中，部署到多个节点上，如果spring配置bean输入了多个同样的IP，可能会引发重复ID问题
 * Created by Nero on 2018-05-11.
 */
public class SnowFlakeTest {


    // private static final long START_TIME_STAMP = 1480166465631L;   不设置起始时间，则从1970年开始往后推69年 可以到2039-09-07 23:47:35

    //ID码构成部分
    private static final long TOTAL_BIT_COUNT = 63;    //该序列码总占位
    private static final long TIMESTAMP_BIT_COUNT = 41;             //时间戳占位
    private static final long ADDRESS_BIT_COUNT = 8;   //地址IP信息占8位

    //序列码占位
    private static final long SEQUENCE_BIT_COUNT = TOTAL_BIT_COUNT-TIMESTAMP_BIT_COUNT-ADDRESS_BIT_COUNT;


    //时间戳移位
    private static final long TIMESTAMP_BIT_LEFT = TOTAL_BIT_COUNT - TIMESTAMP_BIT_COUNT;
    //ip移位
    private static final long ADDRESS_BIT_LEFT = TIMESTAMP_BIT_LEFT - ADDRESS_BIT_COUNT;


    //最大序列码，用做循环增长
    private static final long MAX_SEQUENCE = (-1 << SEQUENCE_BIT_COUNT) ^ -1;
    private static final long MAX_ADDRESS = (-1 << ADDRESS_BIT_COUNT) ^ -1;


    //初始化构成变量
    private long last_stamp = 0;
    private long ipsec = 0;
    private long sequence = 0;


    /****
     * 初始化
     * @param ip
     */
    public SnowFlakeTest(long ip) {
        if(ip <= 0 || ip > MAX_ADDRESS){
            throw new IllegalArgumentException("attention : the param of ip must unique in the distributed and must range form 1 to 255");
        }
        this.ipsec = ip == 0 ? 255 : ip;
    }

    /***
     * 获取ID
     * 目前占位为时间戳+序列码
     * @return
     */
    public synchronized long getNextId(){
        long currentStamp = getCurrentMilles();
        last_stamp = currentStamp;

        sequence = (sequence + 1) & MAX_SEQUENCE;
        if(sequence == 0){   //超出序列上限，获取下一毫秒
            currentStamp = getNextMilles(currentStamp);
        }

        return (currentStamp << TIMESTAMP_BIT_LEFT) |
                (ipsec << ADDRESS_BIT_LEFT) |
                sequence;
    }


    /***
     * 获取下一个时间，针对上一次ID生成
     * @param currentStamp
     * @return
     */
    private long getNextMilles(long currentStamp){
        while(currentStamp <= last_stamp){
            currentStamp = getCurrentMilles();
        }
        return currentStamp;
    }


    /***
     * 获取当前系统时间
     * @return
     */
    private long getCurrentMilles(){
        return System.currentTimeMillis();
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        Set<Long> set  = new LinkedHashSet<>();

        SnowFlakeTest snowFlake = new SnowFlakeTest(1);
        for(int i = 0 ; i < 10000000; i++){
           set.add(snowFlake.getNextId());
        }

        long end = System.currentTimeMillis();

        System.out.println("总耗时："+ (end-start));
        System.out.println(set.size());
    }
}

我的github地址：

欢迎讨论或关注:https://github.com/zhang6622056/NeroJavaEE/tree/master/algorithm