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

阿义

2019-10-28

前言

众所周知, 在分布式全局唯一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默认结构如下:

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

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

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

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

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

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

缩短算法后空间划分
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 ......

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

具体代码则体现如下: 节点标识为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生成方式最终选中了雪花算法, 通过此次改造总算是深入了解了雪花算法的原理了, 同时也复习了一遍简单加减乘处的位运算, 总的来说收获还是颇丰的, 出来工作的时间也不算长, 在程序员大军中还算是年轻的一股经验有所不足, 如有错误请多指教, 借此慢慢培养自己写博客的习惯, 为了钱钱, 冲鸭!

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

分布式算法 js代码分布式部署时间戳算法 js twitter

安科网

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

阿义

前言

对SnowFlake进行改造

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

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

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

代码实现

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

后记

阿义

相关推荐

一致性HASH算法在分布式应用场景使用

Twitter的分布式自增ID算法Snowflake

php hash算法实现memcached分布式

分布式负载均衡算法

分布式选举

分布式系统卫星时钟服务器（NTP服务器）架设与设计

分布式基础

梯度下降的分布式训练简介

分布式系统之Quorum （NRW）算法

分布式系统的核心问题一致性与共识

分布式算法（转）

分布式配置服务etcd VS 分布式协调服务zookeeper

《区块链底层设计Java实战》之第五章分布式一致性与共识算法

分布式ID生成之雪花算法

分布式系统下的哈希一致性算法设计

分布式系统的一致性算法简介

《区块链底层设计Java实战》之第五章分布式一致性与共识算法

分布式搜索算法

从 Memcached 分布式应用看一致性哈希散列函数的选择

zookeeper 分布式任务

阿义