详解Twitter开源分布式自增ID算法snowflake,附演算验证过程

简介: 1.snowflake简介 互联网快速发展的今天,分布式应用系统已经见怪不怪,在分布式系统中,我们需要各种各样的ID,既然是ID那么必然是要保证全局唯一,除此之外,不同当业务还需要不同的特性,比如像并发巨大的业务要求ID生成效率高,吞吐大;比如某些银行类业务,需要按每日日期制定交易流水号;又比如我们希望用户的ID是随机的,无序的,纯数字的,且位数长度是小于10位的。

1.snowflake简介

互联网快速发展的今天,分布式应用系统已经见怪不怪,在分布式系统中,我们需要各种各样的ID,既然是ID那么必然是要保证全局唯一,除此之外,不同当业务还需要不同的特性,比如像并发巨大的业务要求ID生成效率高,吞吐大;比如某些银行类业务,需要按每日日期制定交易流水号;又比如我们希望用户的ID是随机的,无序的,纯数字的,且位数长度是小于10位的。等等,不同的业务场景需要的ID特性各不一样,于是,衍生了各种ID生成器,但大多数利用数据库控制ID的生成,性能受数据库并发能力限制,那么有没有一款不需要依赖任何中间件(如数据库,分布式缓存服务等)的ID生成器呢?本着取之于开源,用之于开源的原则,今天,特此介绍Twitter开源的一款分布式自增ID算法snowflake,并附上算法原理推导和演算过程!
snowflake算法是一款本地生成的(ID生成过程不依赖任何中间件,无网络通信),保证ID全局唯一,并且ID总体有序递增,性能每秒生成300w+。

2.snowflake算法原理

snowflake生产的ID二进制结构表示如下(每部分用-分开):
0 - 00000000 00000000 00000000 00000000 00000000 0 - 00000 - 00000 - 00000000 0000

第一位未使用,接下来的41位为毫秒级时间(41位的长度可以使用69年,从1970-01-01 08:00:00),然后是5位datacenterId(最大支持2^5=32个,二进制表示从00000-11111,也即是十进制0-31),和5位workerId(最大支持2^5=32个,原理同datacenterId),所以datacenterId*workerId最多支持部署1024个节点,最后12位是毫秒内的计数(12位的计数顺序号支持每个节点每毫秒产生2^12=4096个ID序号).

所有位数加起来共64位,恰好是一个Long型(转换为字符串长度为18).

单台机器实例,通过时间戳保证前41位是唯一的,分布式系统多台机器实例下,通过对每个机器实例分配不同的datacenterId和workerId避免中间的10位碰撞。最后12位每毫秒从0递增生产ID,再提一次:每毫秒最多生成4096个ID,每秒可达4096000个。理论上,只要CPU计算能力足够,单机每秒可生产400多万个,实测300w+,效率之高由此可见。

(该节改编自:http://www.cnblogs.com/relucent/p/4955340.html

3.snowflake算法源码(java版)

@ToString  
@Slf4j  
public class SnowflakeIdFactory {  
    private final long twepoch = 1288834974657L;  
    private final long workerIdBits = 5L;  
    private final long datacenterIdBits = 5L;  
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);  
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);  
    private final long sequenceBits = 12L;  
    private final long workerIdShift = sequenceBits;  
    private final long datacenterIdShift = sequenceBits + workerIdBits;  
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;  
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);  
    private long workerId;  
    private long datacenterId;  
    private long sequence = 0L;  
    private long lastTimestamp = -1L;  
  
    public SnowflakeIdFactory(long workerId, long datacenterId) {  
        if (workerId > maxWorkerId || workerId < 0) {  
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));  
        }  
        if (datacenterId > maxDatacenterId || datacenterId < 0) {  
            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));  
        }  
        this.workerId = workerId;  
        this.datacenterId = datacenterId;  
    }  
  
    public synchronized long nextId() {  
        long timestamp = timeGen();  
        if (timestamp < lastTimestamp) {  
            //服务器时钟被调整了,ID生成器停止服务.  
            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;  
        }  
  
        lastTimestamp = timestamp;  
        return ((timestamp - twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | sequence;  
    }  
  
    protected long tilNextMillis(long lastTimestamp) {  
        long timestamp = timeGen();  
        while (timestamp <= lastTimestamp) {  
            timestamp = timeGen();  
        }  
        return timestamp;  
    }  
  
    protected long timeGen() {  
        return System.currentTimeMillis();  
    }  
  
    public static void testProductIdByMoreThread(int dataCenterId, int workerId, int n) throws InterruptedException {  
        List<Thread> tlist = new ArrayList<>();  
        Set<Long> setAll = new HashSet<>();  
        CountDownLatch cdLatch = new CountDownLatch(10);  
        long start = System.currentTimeMillis();  
        int threadNo = dataCenterId;  
        Map<String,SnowflakeIdFactory> idFactories = new HashMap<>();  
        for(int i=0;i<10;i++){  
            //用线程名称做map key.  
            idFactories.put("snowflake"+i,new SnowflakeIdFactory(workerId, threadNo++));  
        }  
        for(int i=0;i<10;i++){  
            Thread temp =new Thread(new Runnable() {  
                @Override  
                public void run() {  
                    Set<Long> setId = new HashSet<>();  
                    SnowflakeIdFactory idWorker = idFactories.get(Thread.currentThread().getName());  
                    for(int j=0;j<n;j++){  
                        setId.add(idWorker.nextId());  
                    }  
                    synchronized (setAll){  
                        setAll.addAll(setId);  
                        log.info("{}生产了{}个id,并成功加入到setAll中.",Thread.currentThread().getName(),n);  
                    }  
                    cdLatch.countDown();  
                }  
            },"snowflake"+i);  
            tlist.add(temp);  
        }  
        for(int j=0;j<10;j++){  
            tlist.get(j).start();  
        }  
        cdLatch.await();  
  
        long end1 = System.currentTimeMillis() - start;  
  
        log.info("共耗时:{}毫秒,预期应该生产{}个id, 实际合并总计生成ID个数:{}",end1,10*n,setAll.size());  
  
    }  
  
    public static void testProductId(int dataCenterId, int workerId, int n){  
        SnowflakeIdFactory idWorker = new SnowflakeIdFactory(workerId, dataCenterId);  
        SnowflakeIdFactory idWorker2 = new SnowflakeIdFactory(workerId+1, dataCenterId);  
        Set<Long> setOne = new HashSet<>();  
        Set<Long> setTow = new HashSet<>();  
        long start = System.currentTimeMillis();  
        for (int i = 0; i < n; i++) {  
            setOne.add(idWorker.nextId());//加入set  
        }  
        long end1 = System.currentTimeMillis() - start;  
        log.info("第一批ID预计生成{}个,实际生成{}个<<<<*>>>>共耗时:{}",n,setOne.size(),end1);  
  
        for (int i = 0; i < n; i++) {  
            setTow.add(idWorker2.nextId());//加入set  
        }  
        long end2 = System.currentTimeMillis() - start;  
        log.info("第二批ID预计生成{}个,实际生成{}个<<<<*>>>>共耗时:{}",n,setTow.size(),end2);  
  
        setOne.addAll(setTow);  
        log.info("合并总计生成ID个数:{}",setOne.size());  
  
    }  
  
    public static void testPerSecondProductIdNums(){  
        SnowflakeIdFactory idWorker = new SnowflakeIdFactory(1, 2);  
        long start = System.currentTimeMillis();  
        int count = 0;  
        for (int i = 0; System.currentTimeMillis()-start<1000; i++,count=i) {  
            /**  测试方法一: 此用法纯粹的生产ID,每秒生产ID个数为300w+ */  
            idWorker.nextId();  
            /**  测试方法二: 在log中打印,同时获取ID,此用法生产ID的能力受限于log.error()的吞吐能力. 
             * 每秒徘徊在10万左右. */  
            //log.error("{}",idWorker.nextId());  
        }  
        long end = System.currentTimeMillis()-start;  
        System.out.println(end);  
        System.out.println(count);  
    }  
  
    public static void main(String[] args) {  
        /** case1: 测试每秒生产id个数? 
         *   结论: 每秒生产id个数300w+ */  
        //testPerSecondProductIdNums();  
  
        /** case2: 单线程-测试多个生产者同时生产N个id,验证id是否有重复? 
         *   结论: 验证通过,没有重复. */  
        //testProductId(1,2,10000);//验证通过!  
        //testProductId(1,2,20000);//验证通过!  
  
        /** case3: 多线程-测试多个生产者同时生产N个id, 全部id在全局范围内是否会重复? 
         *   结论: 验证通过,没有重复. */  
        try {  
            testProductIdByMoreThread(1,2,100000);//单机测试此场景,性能损失至少折半!  
        } catch (InterruptedException e) {  
            e.printStackTrace();  
        }  
  
    }  
}

测试用例:

/** case1: 测试每秒生产id个数?
 *   结论: 每秒生产id个数300w+ */
//testPerSecondProductIdNums();

/** case2: 单线程-测试多个生产者同时生产N个id,验证id是否有重复?
 *   结论: 验证通过,没有重复. */
//testProductId(1,2,10000);//验证通过!
//testProductId(1,2,20000);//验证通过!

/** case3: 多线程-测试多个生产者同时生产N个id, 全部id在全局范围内是否会重复?
 *   结论: 验证通过,没有重复. */
try {
    testProductIdByMoreThread(1,2,100000);//单机测试此场景,性能损失至少折半!
} catch (InterruptedException e) {
    e.printStackTrace();
}

4.snowflake算法推导和演算过程
说明:
演算使用的对象实例:SnowflakeIdFactory idWorker = new SnowflakeIdFactory(1, 2);
运行时数据workerId=1,datacenterId=2,分别表示机器实例的生产者编号,数据中心编号;
sequence=0表示每毫秒生产ID从0开始计数递增;
以下演算基于时间戳=1482394743339时刻进行推导。

一句话描述:以下演算模拟了1482394743339这一毫秒时刻,workerId=1,datacenterId=2的id生成器,生产第一个id的过程。

我自己弄的一个

import java.text.SimpleDateFormat;
import java.util.Date;

/**
 * Created by yinx on 2017/10/27 0027.
 * Twitter_Snowflake<br>
 * SnowFlake的结构如下(每部分用-分开):<br>
 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
 * 1位标识,由于long基本类型在Java中是带符号的,最高位是符号位,正数是0,负数是1,所以id一般是正数,最高位是0<br>
 * 41位时间截(毫秒级),注意,41位时间截不是存储当前时间的时间截,而是存储时间截的差值(当前时间截 - 开始时间截)
 * 得到的值),这里的的开始时间截,一般是我们的id生成器开始使用的时间,由我们程序来指定的(如下下面程序IdWorker类的startTime属性)。41位的时间截,可以使用69年,年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>
 * 10位的数据机器位,可以部署在1024个节点,包括5位datacenterId和5位workerId<br>
 * 12位序列,毫秒内的计数,12位的计数顺序号支持每个节点每毫秒(同一机器,同一时间截)产生4096个ID序号<br>
 * 加起来刚好64位,为一个Long型。<br>
 * SnowFlake的优点是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分),并且效率较高,经测试,SnowFlake每秒能够产生26万ID左右。
 */
//@RunWith(SpringJUnit4ClassRunner.class)
public class SnowflakeIdWorker {

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

    /** 机器id所占的位数 */
    private final long workerIdBits = 5L;

    /** 数据标识id所占的位数 */
    private final long datacenterIdBits = 5L;

    /** 支持的最大机器id,结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

    /** 支持的最大数据标识id,结果是31 */
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

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

    /** 机器ID向左移12位 */
    private final long workerIdShift = sequenceBits;

    /** 数据标识id向左移17位(12+5) */
    private final long datacenterIdShift = sequenceBits + workerIdBits;

    /** 时间截向左移22位(5+5+12) */
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

    /** 生成序列的掩码,这里为4095 (0b111111111111=0xfff=4095) */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    /** 工作机器ID(0~31) */
    private long workerId;

    /** 数据中心ID(0~31) */
    private long datacenterId;

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

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

    //==============================Constructors=====================================
    /**
     * 构造函数
     * @param workerId 工作ID (0~31)
     * @param datacenterId 数据中心ID (0~31)
     */
    public SnowflakeIdWorker(long workerId, long datacenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }

    // ==============================Methods==========================================
    /**
     * 获得下一个ID (该方法是线程安全的)
     * @return SnowflakeId
     */
    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) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | 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();
    }

    //==============================Test=============================================
    /** 测试 */
    public static void main(String[] args) {
        SimpleDateFormat sdf=new SimpleDateFormat("yyyyMMddHHmmss");
        SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);
        for (int i = 0; i < 10000; i++) {
            long id = idWorker.nextId();
            String orderNo = sdf.format(new Date());
            System.out.println(Long.toBinaryString(id));
            orderNo = orderNo + "_" + id;
            System.out.println(orderNo + "=====================" + orderNo.length());
        }
    }

}

end!
参考
https://github.com/twitter/snowflake

http://www.cnblogs.com/relucent/p/4955340.html

转自:http://blog.csdn.net/li396864285/article/details/54668031

相关文章
|
2月前
|
算法 Go
[go 面试] 雪花算法与分布式ID生成
[go 面试] 雪花算法与分布式ID生成
|
2月前
|
存储 算法 NoSQL
(七)漫谈分布式之一致性算法下篇:一文从根上儿理解大名鼎鼎的Raft共识算法!
Raft通过一致性检查,能在一定程度上保证集群的一致性,但无法保证所有情况下的一致性,毕竟分布式系统各种故障层出不穷,如何在有可能发生各类故障的分布式系统保证集群一致性,这才是Raft等一致性算法要真正解决的问题。
92 11
|
2月前
|
存储 算法 索引
(六)漫谈分布式之一致性算法上篇:用二十六张图一探Raft共识算法奥妙之处!
现如今,大多数分布式存储系统都投向了Raft算法的怀抱,而本文就来聊聊大名鼎鼎的Raft算法/协议!
|
2月前
|
存储 算法 Java
(五)漫谈分布式之一致性算法篇:谁说Paxos晦涩难懂?你瞧这不一学就会!
没在时代发展的洪流中泯然于众的道理很简单,是因为它们并不仅是空中楼阁般的高大上理论,而是有着完整落地的思想,它们已然成为构建分布式系统不可或缺的底层基石,而本文则来好好聊聊分布式与一致性思想的落地者:Paxos与Raft协议(算法)。
|
2天前
|
传感器 算法 C语言
基于无线传感器网络的节点分簇算法matlab仿真
该程序对传感器网络进行分簇,考虑节点能量状态、拓扑位置及孤立节点等因素。相较于LEACH算法,本程序评估网络持续时间、节点死亡趋势及能量消耗。使用MATLAB 2022a版本运行,展示了节点能量管理优化及网络生命周期延长的效果。通过簇头管理和数据融合,实现了能量高效和网络可扩展性。
|
29天前
|
算法 BI Serverless
基于鱼群算法的散热片形状优化matlab仿真
本研究利用浴盆曲线模拟空隙外形,并通过鱼群算法(FSA)优化浴盆曲线参数,以获得最佳孔隙度值及对应的R值。FSA通过模拟鱼群的聚群、避障和觅食行为,实现高效全局搜索。具体步骤包括初始化鱼群、计算适应度值、更新位置及判断终止条件。最终确定散热片的最佳形状参数。仿真结果显示该方法能显著提高优化效率。相关代码使用MATLAB 2022a实现。
|
29天前
|
算法 数据可视化
基于SSA奇异谱分析算法的时间序列趋势线提取matlab仿真
奇异谱分析(SSA)是一种基于奇异值分解(SVD)和轨迹矩阵的非线性、非参数时间序列分析方法,适用于提取趋势、周期性和噪声成分。本项目使用MATLAB 2022a版本实现从强干扰序列中提取趋势线,并通过可视化展示了原时间序列与提取的趋势分量。代码实现了滑动窗口下的奇异值分解和分组重构,适用于非线性和非平稳时间序列分析。此方法在气候变化、金融市场和生物医学信号处理等领域有广泛应用。
|
1月前
|
资源调度 算法
基于迭代扩展卡尔曼滤波算法的倒立摆控制系统matlab仿真
本课题研究基于迭代扩展卡尔曼滤波算法的倒立摆控制系统,并对比UKF、EKF、迭代UKF和迭代EKF的控制效果。倒立摆作为典型的非线性系统,适用于评估不同滤波方法的性能。UKF采用无迹变换逼近非线性函数,避免了EKF中的截断误差;EKF则通过泰勒级数展开近似非线性函数;迭代EKF和迭代UKF通过多次迭代提高状态估计精度。系统使用MATLAB 2022a进行仿真和分析,结果显示UKF和迭代UKF在非线性强的系统中表现更佳,但计算复杂度较高;EKF和迭代EKF则更适合维数较高或计算受限的场景。
|
1月前
|
算法
基于SIR模型的疫情发展趋势预测算法matlab仿真
该程序基于SIR模型预测疫情发展趋势,通过MATLAB 2022a版实现病例增长拟合分析,比较疫情防控力度。使用SIR微分方程模型拟合疫情发展过程,优化参数并求解微分方程组以预测易感者(S)、感染者(I)和移除者(R)的数量变化。![]该模型将总人群分为S、I、R三部分,通过解析或数值求解微分方程组预测疫情趋势。
|
1月前
|
算法 数据可视化 数据安全/隐私保护
基于LK光流提取算法的图像序列晃动程度计算matlab仿真
该算法基于Lucas-Kanade光流方法,用于计算图像序列的晃动程度。通过计算相邻帧间的光流场并定义晃动程度指标(如RMS),可量化图像晃动。此版本适用于Matlab 2022a,提供详细中文注释与操作视频。完整代码无水印。
下一篇
无影云桌面