我把 Snowflakes 的算法性能提升了万倍！！

缺乏、安全感 2022-12-17 08:42 227阅读 0赞

# 我把 Snowflakes 的算法性能提升了万倍 #

### 先上结论 ###

*  成果物为高性能可配置的全局递增唯一 id 生成器
 *  单节点多线程并发获取场景性能对比：
    
     *  是 twitter 雪花算法**两百万倍+**
     *  是`JDK UUID`的**120倍**！
     *  是百度开源算法的 **60 倍！**。
     *  PS：这里采用的雪花算法默认格式与其他对比，实际调整参数优化后，性能可以进一步翻倍提升！吊打一切！
 *  优雅处理时钟回拨
 *  支持突发峰值、持续高压
 *  支持格式扩展

## 网上常用代码 ##

全局 id 生成器，老生常谈的雪花算法，看了一下网上的实现，基本都是类似这种（仅举例）

class SnowFlakeIdGenerator { 
    
        /** * 起始的时间戳(a special day for me) */
        private final static long START_STAMP = 1555776000000L;
    
        /** * 每一部分占用的位数 */
        private final static long SEQUENCE_BIT = 6; //序列号占用的位数
        private final static long MACHINE_BIT = 14;   //机器标识占用的位数
        private final static long DATA_CENTER_BIT = 2;//数据中心占用的位数
    
        /** * 每一部分的最大值 */
        private final static long MAX_DATA_CENTER_NUM = ~(-1L << DATA_CENTER_BIT);
        private final static long MAX_MACHINE_NUM = ~(-1L << MACHINE_BIT);
        private final static long MAX_SEQUENCE = ~(-1L << SEQUENCE_BIT);
    
        /** * 每一部分向左的位移 */
        private final static long MACHINE_LEFT = SEQUENCE_BIT;
        private final static long DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
        private final static long TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT;
    
        private long dataCenterId;  //数据中心
        private long machineId;     //机器标识
        private long sequence = 0L; //序列号
        private long lastTimestamp = -1L;//上一次时间戳
    
        public SnowFlakeIdGenerator(long dataCenterId, long machineId) { 
            if (dataCenterId > MAX_DATA_CENTER_NUM || dataCenterId < 0) { 
                throw new IllegalArgumentException("dataCenterId can't be greater than MAX_DATA_CENTER_NUM or less than 0");
            }
            if (machineId > MAX_MACHINE_NUM || machineId < 0) { 
                throw new IllegalArgumentException("machineId can't be greater than MAX_MACHINE_NUM or less than 0");
            }
            this.dataCenterId = dataCenterId;
            this.machineId = machineId;
        }
    
        /** * 产生下一个ID */
        public synchronized long nextId() { 
            long currStamp = getNewStamp();
            if (currStamp < lastTimestamp) { 
                throw new RuntimeException("clock moved backwards, refusing to generate id");
            }
    
            if (currStamp == lastTimestamp) { 
                //相同毫秒内，序列号自增
                sequence = (sequence + 1) & MAX_SEQUENCE;
                //同一毫秒的序列数已经达到最大
                if (sequence == 0L) { 
                    currStamp = getNextMill();
                }
            } else { 
                //不同毫秒内，序列号置为0
                sequence = 0L;
            }
    
            lastTimestamp = currStamp;
    
            return (currStamp - START_STAMP) << TIMESTAMP_LEFT //时间戳部分
                    | dataCenterId << DATA_CENTER_LEFT       //数据中心部分
                    | machineId << MACHINE_LEFT             //机器标识部分
                    | sequence;                             //序列号部分
        }
    
        private long getNextMill() { 
            long mill = getNewStamp();
            while (mill <= lastTimestamp) { 
                mill = getNewStamp();
            }
            return mill;
        }
    
        private long getNewStamp() { 
            return System.currentTimeMillis();
        }
    }

虽然业务场景绝大多数情况下没什么问题，但在海量日志分布式入库、大规模事件处理、分布式爬虫数据整理、大数据处理场景，这些高并发、突发流量、甚至频繁重启、时钟回拨的场景下，问题真的不少！

有哪些问题呢？

*  时间回拨未处理，直接抛异常岂不是一旦回拨，回拨的时间不可用？
 *  突发峰值怎么办，在大数据量处理场景，超过序列上限，阻塞实现好吗？

高性能可配置的全局 id 生成器（持续高压场景为 twitter 雪花算法万倍性能），优雅处理时钟回拨，支持突发峰值、持续高压

## 性能测试 ##

无图无码谁信，[shoulder-guid 全局递增唯一标识生成器-性能测试说明][shoulder-guid _-]

## 分析 ##

> Shoulder 是如何一步一步把锁范围缩小、去掉，同时保证多个变量的原子性操作，充分利用 CPU caheLine、避免伪内存。

代码先附上，注释已经很多了，可以先看，也可以从提交记录里看出。

[代码][Link 1]

[测试代码][Link 2]

[shoulder-guid _-]: https://github.com/ChinaLym/Shoulder-Framework/tree/master/shoulder-build/shoulder-base/shoulder-core#guid%E5%85%A8%E5%B1%80%E5%94%AF%E4%B8%80%E6%A0%87%E8%AF%86%E7%AC%A6%E7%94%9F%E6%88%90%E5%99%A8
[Link 1]: https://github.com/ChinaLym/Shoulder-Framework/blob/master/shoulder-build/shoulder-base/shoulder-core/src/main/java/org/shoulder/core/uuid/ShoulderGuidGenerator.java
[Link 2]: https://github.com/ChinaLym/Shoulder-Framework/blob/master/shoulder-build/shoulder-base/shoulder-core/src/test/java/org/shoulder/core/uuid/ShoulderGuidTest.java