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

2022-12-02 18:29:26

缘起

为什么会突然谈到分布式唯一id呢？原因是最近在准备使用全局唯一ID，项目要搞微服务化，看看官网介绍：

同一业务场景要全局唯一，这个id的要求就是局部唯一或者全局唯一即可，由于这个id是唯一的，可以用来当数据库的主键。
那么该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实现代码基本上就是类似这样的，不过我改了，是适应我司业务场景的要求，我将在里面重点提出更改内容（都差不多，基本就是二进制位操作）：

package com.ztesoft.res.gid.worker;

import org.springframework.stereotype.Component;

@Component
public class SnowflakeIdWorker {

    // ==============================Fields===========================================
    /** 开始时间截 (2015-01-01) */
    private final long twepoch = 1420041600000L;
            //(2010-01-01)
//    private final long twepoch = 1262275200000L;

    /** 资源类型id所占的位数 */
    private final long resTypeIdits = 14L;

    /** 本地网id所占的位数 */
    private final long regionIdBits = 6L;

    /** 机器设备id所占的位数 */
    private final long machineIdBits = 2L;

    /** 支持的最大资源类型id，结果是 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
    private final long maxResTypeId = -1L ^ (-1L << resTypeIdits);

    /** 支持的最大数据本地网id，结果是31 */
    private final long maxRegionId = -1L ^ (-1L << regionIdBits);

    /** 支持的最大数据机器设备ID，结果是31 */
    private final long maxMachineId = -1L ^ (-1L << machineIdBits);

    /** 序列在id中占的位数 */
    private final long sequenceBits = 3L;

    /** 机器ID向左移3位 */
    private final long machineIdShift = sequenceBits;

    /** 资源规格ID向左移5位(3+2) */
    private final long resTypeIdShift = sequenceBits + machineIdBits;

    /** 本地网ID向左移19位(3+2+14) */
    private final long regionIdShift = sequenceBits + machineIdBits + resTypeIdits;

    /** 时间截向左移25位(3+2+14+6) */
    private final long timestampLeftShift = sequenceBits + machineIdBits + resTypeIdits + regionIdBits;

    /** 生成序列的掩码，这里为7 */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    /** 本地网ID(0~63)*/
    private long regionId;

    /** 资源类型ID(0~16383) */
    private long resTypeId;

    /** 机器设备ID(0~3) */
    private long machineId;

    /** 毫秒内序列(0~7) */
    private long sequence = 0L;

    /** 上次生成ID的时间截 */
    private long lastTimestamp = -1L;

    //==============================Constructors=====================================
    public SnowflakeIdWorker(){}
    /**
     * 构造函数
     * @param resTypeId 资源类型ID
     * @param machineId 机器ID
     * @param regionId 本地网
     */
    public SnowflakeIdWorker(long resTypeId, long machineId, long regionId) {
        if (regionId > maxRegionId || regionId < 0) {
            throw new IllegalArgumentException(String.format("region Id can't be greater than %d or less than 0", maxRegionId));
        }
        if (resTypeId > maxResTypeId || resTypeId < 0) {
            throw new IllegalArgumentException(String.format("resTypeId can't be greater than %d or less than 0", maxResTypeId));
        }
        if (machineId > maxMachineId || machineId < 0) {
            throw new IllegalArgumentException(String.format("machine Id can't be greater than %d or less than 0", maxMachineId));
        }
        this.regionId = regionId;
        this.resTypeId = resTypeId;
        this.machineId = machineId;
    }

    // ==============================Methods==========================================

    /**
     * 获得下一个ID (该方法是线程安全的)
     * @return
     */
   public synchronized long nextId() {
        long timestamp = timeGen();
        //如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(
                    String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }
        //如果是同一时间生成的，则进行毫秒内序列
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            //毫秒内序列溢出
            if (sequence == 0) {
                //阻塞到下一个毫秒,获得新的时间戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        //时间戳改变，毫秒内序列重置
        else {
            sequence = 0L;
        }
        //上次生成ID的时间截
        lastTimestamp = timestamp;
        //移位并通过或运算拼到一起组成64位的ID
        return ((timestamp - twepoch) << timestampLeftShift)
                | (regionId << regionIdShift)
                | (resTypeId << resTypeIdShift)
                | (machineId << machineIdShift)
                | sequence;
    }

    /**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     * @param lastTimestamp 上次生成ID的时间截
     * @return 当前时间戳
     */
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    /**
     * 返回以毫秒为单位的当前时间
     * @return 当前时间(毫秒)
     */
    protected long timeGen() {
        return System.currentTimeMillis();
    }
    private String lpad(String value, int maxLength){
        StringBuffer sb = new StringBuffer(value);
        for(int i = 0; i < (maxLength - value.length());i++){
            sb.insert(0, "0");
        }
        return sb.toString();
    }

    //==============================Test=============================================
    /** 测试 */
    public static void main(String[] args) {
        SnowflakeIdWorker idWorker = new SnowflakeIdWorker(200, 1, 22);
        for (int i = 0; i < 100000; i++) {
            Long id = idWorker.nextId();
            System.out.println(Long.toBinaryString(id)+"   W:"+ Long.toBinaryString(id).length()+"  ID:"+id);
        }
    }
}

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

缺点：
只能趋势递增。（有些也不叫缺点，网上有些如果绝对递增，竞争对手中午下单，第二天在下单即可大概判断该公司的订单量，危险！！！）
依赖机器时间，如果发生回拨会导致可能生成id重复。
下面重点讨论时间回拨问题。

分析时间回拨产生原因
第一：人物操作，在真实环境一般不会有那个傻逼干这种事情，所以基本可以排除。
第二：由于有些业务等需要，机器需要同步时间服务器（在这个过程中可能会存在时间回拨，查了下我们服务器一般在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挂了怎么办，怎么同步，的确值得商榷。可能会引入会引入很多新的小问题）。

码农公寓

相关文章