Twitter雪花算法SnowFlake改造-兼容JS截短位数的53bit分布式ID生成器

前言

---

  众所周知, 在分布式全局唯一 ID 生成器方案中, 由 Twitter 开源的 SnowFlake 算法对比 美团 Leaf为代表的需要部署的发号器算法, 因其有性能高, 代码简单, 不依赖第三方服务, 无需独立部署服务等优点, 在一般情况下已经能满足绝大多数系统的需求, 原生 SnowFlake, 百度 UidGenerator 这类基于划分命名空间原理的算法已经积累了大量用户;

  使用原生的雪花算法其 默认生成的是 64bit 长整型, 如果以 ID 和前端的 JS 进行交互时会出现精度丢失(最后两位数字变成 00) 而导致最终系统报错: 找不到 ID; 废话, 最后两位都变成 00 了那肯定找不到啊! 究其原因是因为JS 的 Number 类型精度最高只有 53bit, 导致 JS 其最大安全值只有 2^53 = ‭9007199254740992 算法生成的 18 位数字妥妥的超标了啊;

  解决方法有: 避免使用 ID 进行交互, 后端将 long 类型的 ID 映射为 String, 使 JS 兼容 64bit 长整型, 改造 SnowFlake 缩短位数;

  既然是因为位数太长了, 那我们缩短位数不就好了吗? JS 的 53bit 精度, 也有最大值是亿亿, 也没有谁会有亿亿个数据吧, 那我们仔细研究一下这个雪花算法, 把他缩短一下, 程序员如何向公司证明自己的价值不就在于反复造轮子吗? 管他方的轮子好不好用呢;

对 SnowFlake 进行改造

---

• 命名空间划分(减少位长, 改为 Unix 的秒级时间戳)

原生 SnowFlake 默认结构如下:

原生 SnowFlake 中的空间划分:
1, 高位 1bit 固定 0 表示正数
2, 41bit 毫秒时间戳
3, 10bit 机器编号, 最高可支持 1024 个节点
4, 12bit 自增序列, 单节点最高可支持 4096 个 ID/ms

由上面原生算法结构可以看到, 影响最终生成 ID 长度最大的是毫秒时间戳, 它占了整整 41bit 换成 10 进制就是占了 13 位数, 不减少这个最终位数肯定就下不去; 考虑到绝大部分公司并不存在这么高的数据库并发也没有 1024 台这么多的机器集群;

时间戳由毫秒改为 32bit 的秒级时间戳, 机器编码缩短为 5bit, 剩下 16bit 做自增序列;

机器编号也可以减少, 最终结果如下图 ↓↓↓:

缩短算法后空间划分
1, 高位 32bit 作为秒级时间戳, 时间戳减去固定值(2019 年时间戳), 最高可支持到 2106 年(1970 + 2^32 / 3600 / 24 / 365 ≈ 2106)
2, 5bit 作为机器标识, 最高可部署 32 台机器
3, 最后 16bit 作为自增序列, 单节点最高每秒 2^16 = 65536 个 ID
PS: 如果需要部署更多节点, 可以适当调整机器位和自增序列的位长, 如机器位 7bit, 自增序列 14bit, 这样一来就变成了支持 2^7=128 个节点, 单节点每秒 2^14=16384 个自增序列

• 时钟回拨问题(可用节点减半, 设置备份节点)

趋势自增依赖于高位的时间戳, 如果服务器因同步时间等操作导致了时钟回拨, 那么将会有可能产生重复 ID, 对此我的解决方法是 将 32 个节点 ID 再次拆分 , 0~15 作为主节点 ID, 16~31 作为备份节点 ID, 当主节点检测到时钟回拨时, 启用对应的备份节点继续提供服务, 如果不巧极端情况并发极高, 使用备份节点时一秒内耗尽 65536 个序列, 则借调下一秒的未使用序列, 直到主节点时钟追回;
备份节点可在主节点秒内序列耗尽时接管继续提供服务, 或者在时钟回拨时接管服务, 这样一来最大支持的机器就只剩下 16 台了, 虽然少了点, 但是也已经足够满足一般小型企业的需求了, 同时也提高了服务的可靠性;

主节点与备份节点关系: 主节点为 0 时对应备份节点为 0 + 16 = 16, 主节点为 1 时则对应 1 + 16 = 17, 主节点为 2 时则对应 2 + 16 = 18 ……

具体代码则体现如下: 节点标识为 5bit 时, BACK_WORKER_ID_BEGIN 是备份节点 ID 的最小值 = 16, 主节点 + 16 得到备份节点

((WORKER_ID ^ BACK_WORKER_ID_BEGIN) << WORKER_SHIFT_BITS)

• 秒内自增序列用尽问题(向后借下一秒未分配的序列)

当遇到极端情况每秒并发超过 65536 时则会遇到该秒内再无可分配 ID 的问题, 为了解决这个问题, 可在秒内序列用尽时启用备份节点, 这个一个节点 ID 则每秒可以获得翻倍的 ID, 当备份节点也不足时, 最后可以考虑由备份节点直接启用下一秒的未分配序列继续提供服务, 这样 理论上就获得了无限容量的秒内可分配 ID(只要机器性能跟得上可以无限借调下一秒, 直到 1 秒后主节点追回时间差由主节点继续提供服务, 以此循环往复生生不息~)

if (0L == (++sequence & SEQUENCE_MAX)) {
    // 上面自增序列已自增 1, 回滚这个自增操作确保下次进入时依旧触发条件
    sequence--;
    // 秒内序列用尽, 使用备份节点继续提供服务
    return nextIdBackup(timestamp);
}

代码实现

---

为了代码逻辑清晰简单, 主节点和备份节点生成直接复制为结构相似的两个方法

/**
 * 雪花算法分布式唯一 ID 生成器 <br>
 * 每个机器号最高支持每秒‭65535 个序列, 当秒序列不足时启用备份机器号, 若备份机器也不足时借用备份机器下一秒可用序列 <br>
 * 53 bits 趋势自增 ID 结构如下:
 *
 * |00000000|00011111|11111111|11111111|11111111|11111111|11111111|11111111|
 * |-----------|##########32bit 秒级时间戳 ##########|-----|-----------------|
 * |--------------------------------------5bit 机器位 |xxxxx|-----------------|
 * |-----------------------------------------16bit 自增序列 |xxxxxxxx|xxxxxxxx|
 *
 * @author: yangzc
 * @date: 2019-10-19
 **/
@Slf4j
public class SequenceUtils {

    /** 初始偏移时间戳 */
    private static final long OFFSET = 1546300800L;

    /** 机器 id (0~15 保留 16~31 作为备份机器) */
    private static final long WORKER_ID;
    /** 机器 id 所占位数 (5bit, 支持最大机器数 2^5 = 32)*/
    private static final long WORKER_ID_BITS = 5L;
    /** 自增序列所占位数 (16bit, 支持最大每秒生成 2^16 = ‭65536‬) */
    private static final long SEQUENCE_ID_BITS = 16L;
    /** 机器 id 偏移位数 */
    private static final long WORKER_SHIFT_BITS = SEQUENCE_ID_BITS;
    /** 自增序列偏移位数 */
    private static final long OFFSET_SHIFT_BITS = SEQUENCE_ID_BITS + WORKER_ID_BITS;
    /** 机器标识最大值 (2^5 / 2 - 1 = 15) */
    private static final long WORKER_ID_MAX = ((1 << WORKER_ID_BITS) - 1) >> 1;
    /** 备份机器 ID 开始位置 (2^5 / 2 = 16) */
    private static final long BACK_WORKER_ID_BEGIN = (1 << WORKER_ID_BITS) >> 1;
    /** 自增序列最大值 (2^16 - 1 = ‭65535) */
    private static final long SEQUENCE_MAX = (1 << SEQUENCE_ID_BITS) - 1;
    /** 发生时间回拨时容忍的最大回拨时间 (秒) */
    private static final long BACK_TIME_MAX = 1L;

    /** 上次生成 ID 的时间戳 (秒) */
    private static long lastTimestamp = 0L;
    /** 当前秒内序列 (2^16)*/
    private static long sequence = 0L;
    /** 备份机器上次生成 ID 的时间戳 (秒) */
    private static long lastTimestampBak = 0L;
    /** 备份机器当前秒内序列 (2^16)*/
    private static long sequenceBak = 0L;

    static {
        // 初始化机器 ID
        // 伪代码: 由你的配置文件获取节点 ID
        long workerId = your configured worker id;
        if (workerId < 0 || workerId > WORKER_ID_MAX) {throw new IllegalArgumentException(String.format("cmallshop.workerId 范围: 0 ~ %d 目前: %d", WORKER_ID_MAX, workerId));
        }
        WORKER_ID = workerId;
    }

    /** 私有构造函数禁止外部访问 */
    private SequenceUtils() {}

    /**
     * 获取自增序列
     * @return long
     */
    public static long nextId() {return nextId(SystemClock.now() / 1000);
    }

    /**
     * 主机器自增序列
     * @param timestamp 当前 Unix 时间戳
     * @return long
     */
    private static synchronized long nextId(long timestamp) {
        // 时钟回拨检查
        if (timestamp < lastTimestamp) {
            // 发生时钟回拨
            log.warn("时钟回拨, 启用备份机器 ID: now: [{}] last: [{}]", timestamp, lastTimestamp);
            return nextIdBackup(timestamp);
        }

        // 开始下一秒
        if (timestamp != lastTimestamp) {
            lastTimestamp = timestamp;
            sequence = 0L;
        }
        if (0L == (++sequence & SEQUENCE_MAX)) {
            // 秒内序列用尽
//            log.warn("秒内 [{}] 序列用尽, 启用备份机器 ID 序列", timestamp);
            sequence--;
            return nextIdBackup(timestamp);
        }

        return ((timestamp - OFFSET) << OFFSET_SHIFT_BITS) | (WORKER_ID << WORKER_SHIFT_BITS) | sequence;
    }

    /**
     * 备份机器自增序列
     * @param timestamp timestamp 当前 Unix 时间戳
     * @return long
     */
    private static long nextIdBackup(long timestamp) {if (timestamp < lastTimestampBak) {if (lastTimestampBak - SystemClock.now() / 1000 <= BACK_TIME_MAX) {timestamp = lastTimestampBak;} else {throw new RuntimeException(String.format("时钟回拨: now: [%d] last: [%d]", timestamp, lastTimestampBak));
            }
        }

        if (timestamp != lastTimestampBak) {
            lastTimestampBak = timestamp;
            sequenceBak = 0L;
        }

        if (0L == (++sequenceBak & SEQUENCE_MAX)) {
            // 秒内序列用尽
//            logger.warn("秒内 [{}] 序列用尽, 备份机器 ID 借取下一秒序列", timestamp);
            return nextIdBackup(timestamp + 1);
        }

        return ((timestamp - OFFSET) << OFFSET_SHIFT_BITS) | ((WORKER_ID ^ BACK_WORKER_ID_BEGIN) << WORKER_SHIFT_BITS) | sequenceBak;
    }

}

Linux 下 System.currentTimeMillis()的性能问题

---

copy 上面的 ID 生成算法你会发现有个报错找不到 SystemClock.now(), 因为它并不是 JDK 自带的类, 使用这个工具类生成时间戳的原因是经过实测发现 Linux 环境中高并发下 System.currentTimeMillis()这个 API 对比 Windows 环境有近百倍的性能差距;

此问题的原因分析博文: 缓慢的 System.currentTimeMillis();

百度简单搜索发现已有很多解决方案, 最简单直接的是起一个线程定时维护一个毫秒时间戳以覆盖 JDK 的 System.currentTimeMillis(), 虽然这样固然会造成一定的时间精度问题, 但我们的 ID 生成算法是秒级的 Unix 时间戳, 也不在乎这几十微秒的误差, 换来的却是百倍的性能提升, 这是完全值得的支出;

代码如下:

import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicLong;

/**
 * 缓存时间戳解决 System.currentTimeMillis()高并发下性能问题 <br>
 *     问题根源分析: http://pzemtsov.github.io/2017/07/23/the-slow-currenttimemillis.html
 *
 * @author: yangzc
 * @date: 2019-10-19
 **/
public class SystemClock {

    private final long period;
    private final AtomicLong now;

    private SystemClock(long period) {
        this.period = period;
        this.now = new AtomicLong(System.currentTimeMillis());
        scheduleClockUpdating();}

    /**
     * 尝试下枚举单例法
     */
    private enum SystemClockEnum {
        SYSTEM_CLOCK;
        private SystemClock systemClock;
        SystemClockEnum() {systemClock = new SystemClock(1);
        }
        public SystemClock getInstance() {return systemClock;}
    }

    /**
     * 获取单例对象
     * @return com.cmallshop.module.core.commons.util.sequence.SystemClock
     */
    private static SystemClock getInstance() {return SystemClockEnum.SYSTEM_CLOCK.getInstance();
    }

    /**
     * 获取当前毫秒时间戳
     * @return long
     */
    public static long now() {return getInstance().now.get();}

    /**
     * 起一个线程定时刷新时间戳
     */
    private void scheduleClockUpdating() {
        ScheduledExecutorService scheduler = Executors.newSingleThreadScheduledExecutor(runnable -> {Thread thread = new Thread(runnable, "System Clock");
            thread.setDaemon(true);
            return thread;
        });
        scheduler.scheduleAtFixedRate(() -> now.set(System.currentTimeMillis()), period, period, TimeUnit.MILLISECONDS);
    }

}

后记

---

  了解了主流的各大公司开源的分布式 ID 生成方式最终选中了雪花算法, 通过此次改造总算是深入了解了雪花算法的原理了, 同时也复习了一遍简单加减乘处的位运算, 总的来说收获还是颇丰的, 出来工作的时间也不算长, 在程序员大军中还算是年轻的一股经验有所不足, 如有错误请多指教, 借此慢慢培养自己写博客的习惯, 为了钱钱, 冲鸭!