Twitter的雪花算法SnowFlake原版及改进版全解析

Twitter的雪花算法SnowFlake原版

packagecom.wheel.eden.common.util.core;/**
 * Twitter 的 Snowflake 算法
 * 分布式系统中, 有一些需要使用全局唯一ID的场景, 有些时候我们希望能使用一种简单一些的ID，并且希望ID能够按照时间有序生成。
 * <p>
 * snowflake 的结构如下(每部分用-分开):
 * 符号位（1bit）- 时间戳相对值（41bit）- 数据中心标志（5bit）- 机器标志（5bit）- 递增序号（12bit）
 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000
 * <p>
 * 1位标识, 由于long基本类型在Java中是带符号的, 最高位是符号位, 正数是0, 负数是1，id一般是正数，所以最高位是0
 * 41位毫秒级时间截, 存储时间截的差值（当前时间截 - 开始时间截) ,可以使用69年 (年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69)
 * 10位数据机器位, 可以部署在1024个节点, 包括5位dataCenterId和5位workerId
 * 12位序列, 毫秒内的计数, 支持每个节点每毫秒产生4096个ID序号
 * <p>
 * SnowFlake 共计64位分布式ID, 正好是一个Long型, 且可根据ID反推出 createTime , dataCenterId , workerId 等信息
 * SnowFlake 整体上按照时间自增排序, 分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分), 每秒能够产生26万ID左右
 * <p>
 * 雪花算法改进版, 参考：
 * https://blog.csdn.net/u010541670/article/details/119775492
 * 自动生成数据中心ID和机器ID算法, 参考：
 * https://blog.csdn.net/u010541670/article/details/119774545
 * 
 * @author 白纸涂鸦
 * @date 2021/7/28
 * @since 1.0.0
 */publicclassTwitterSnowflake{// ================================ Default ============================================/** 基准开始时间截 (2021-01-01) 一旦确定不能变动 */privatefinalstaticlong EPOCH=1609430400000L;/** 0L **/privatefinalstaticlong MIN_POSITIVE_LONG=0L;/**
     * 每一部分占用的位数
     */privatefinalstaticlong CENTER_ID_BITS=5L;privatefinalstaticlong WORKER_ID_BITS=5L;privatefinalstaticlong SEQUENCE_BITS=12L;/**
     * 每一部分的最大值
     */privatefinalstaticlong MAX_WORKER_ID=~(-1L<< WORKER_ID_BITS);privatefinalstaticlong MAX_CENTER_ID=~(-1L<< CENTER_ID_BITS);privatefinalstaticlong MAX_SEQUENCE=~(-1L<< SEQUENCE_BITS);/** 序列ID的掩码, 2^12 -1 = 4095 */privatefinalstaticlong SEQUENCE_MASK=~(-1L<< SEQUENCE_BITS);/** 机器ID向左移12位 **/privatefinalstaticlong WORKER_ID_SHIFT= SEQUENCE_BITS;/** 数据中心ID向左移17位(12+5) **/privatefinalstaticlong CENTER_ID_SHIFT= SEQUENCE_BITS+ WORKER_ID_BITS;/** 时间截向左移22位(5+5+12) **/privatefinalstaticlong TIMESTAMP_LEFT_SHIFT= SEQUENCE_BITS+ WORKER_ID_BITS+ CENTER_ID_BITS;// ================================ Fields ==============================================/** 数据中心ID (0~31) **/privatefinallong centerId;/** 机器ID (0~31) **/privatefinallong workerId;/** 序列ID (0~4095) **/privatelong sequence=0L;/** 上次生成ID的时间截 **/privatelong lastTimestamp=-1L;// ================================ Constructors ========================================publicTwitterSnowflake(long workerId,long centerId){if(workerId<= MAX_WORKER_ID&& workerId>= MIN_POSITIVE_LONG){if(centerId<= MAX_CENTER_ID&& centerId>= MIN_POSITIVE_LONG){this.workerId= workerId;this.centerId= centerId;}else{thrownewIllegalArgumentException(StrUtil.format("dataCenter Id can't be greater than {} or less than 0", MAX_CENTER_ID));}}else{thrownewIllegalArgumentException(StrUtil.format("worker Id can't be greater than {} or less than 0", MAX_WORKER_ID));}}// ================================ Methods ============================================/**
     * 获得下一个分布式ID (该方法是线程安全的)
     *
     * @return snowflakeId
     */publicsynchronizedlongnextId(){// 当前时间戳long timestamp=genTime();// 如果当前时间戳小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常if(timestamp< lastTimestamp){thrownewIllegalStateException(StrUtil.format("Clock moved backwards. Refusing to generate id for {}ms",this.lastTimestamp- timestamp));}// 同一毫秒内进行序列自增if(timestamp== lastTimestamp){
            sequence=(sequence+1L)& SEQUENCE_MASK;// 同一毫秒的序列数已经达到最大if(sequence==0L){
                timestamp=tilNextMillis(lastTimestamp);}}else{// 不同毫秒内，序列号置为0
            sequence=0L;}// 重置最后生成ID的时间戳
        lastTimestamp= timestamp;// 时间戳部分 | 数据中心部分 | 机器标识部分 | 序列号部分return(timestamp- EPOCH)<< TIMESTAMP_LEFT_SHIFT| centerId<< CENTER_ID_SHIFT| workerId<< WORKER_ID_SHIFT|this.sequence;}/**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     *
     * @param lastTimestamp 上次生成ID的时间截
     * @return 当前时间戳
     */privatelongtilNextMillis(long lastTimestamp){long timestamp=genTime();while(timestamp<= lastTimestamp){
            timestamp=genTime();}return timestamp;}/**
     * 返回当前毫秒时间戳
     *
     * @return 当前毫秒时间戳
     */privatelonggenTime(){returnSystem.currentTimeMillis();}}

Twitter的雪花算法SnowFlake改进版

1、闰秒兼容改进
https://blog.csdn.net/u010541670/article/details/119774545

2、时钟回拨兼容改进
https://blog.csdn.net/wengengeng/article/details/106007879

3、位数改进
https://blog.csdn.net/ciap37959/article/details/100619920

4、自动获取 datacenterId 和 workerId 改进
https://blog.csdn.net/u010541670/article/details/119774545