`

Twitter的分布式自增ID算法snowflake (Java版)

    博客分类:
  • JAVA
 
阅读更多
概述
分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。

有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。

而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移到Cassandra,因为Cassandra没有顺序ID生成机制,所以开发了这样一套全局唯一ID生成服务。



结构
snowflake的结构如下(每部分用-分开):

0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000

第一位为未使用,接下来的41位为毫秒级时间(41位的长度可以使用69年),然后是5位datacenterId和5位workerId(10位的长度最多支持部署1024个节点) ,最后12位是毫秒内的计数(12位的计数顺序号支持每个节点每毫秒产生4096个ID序号)

一共加起来刚好64位,为一个Long型。(转换成字符串后长度最多19)

snowflake生成的ID整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由datacenter和workerId作区分),并且效率较高。经测试snowflake每秒能够产生26万个ID。


源码
(JAVA版本的源码)

/**
* 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左右。
*/


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) {
        SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);
        for (int i = 0; i < 1000; i++) {
            long id = idWorker.nextId();
            System.out.println(Long.toBinaryString(id));
            System.out.println(id);
        }
    }
}
分享到:
评论

相关推荐

    Twitter的分布式自增ID算法Snowflake的PHP实现,Snowflake PHP版本,高并发唯一id,全局唯一id,不重复id

    Twitter Snowflake算法,php版代码; 请见博客: http://blog.csdn.net/envon123/article/details/52953872

    Java实现Twitter的分布式自增ID算法snowflake

    【Java实现Twitter的分布式自增ID算法snowflake】 在分布式系统设计中,生成全局唯一ID是一个常见的需求。Twitter的Snowflake算法就是为了解决这个问题而诞生的,它提供了一种高效、有序且不会冲突的ID生成策略。...

    Twitter的分布式自增ID雪花算法snowflake

    综上所述,Twitter的雪花算法(Snowflake)提供了一种高效、简单的分布式ID生成方案,通过合理的结构设计,确保了全局唯一性和顺序性。在Java环境下,可以通过实现相应的类和方法轻松地引入这一机制,为分布式系统的...

    springboot分布式自增id_javaredis_源码

    在分布式系统中,为了生成全局唯一的自增ID,可以使用Snowflake算法、Twitter的分布式ID生成服务,或者基于Redis的序列号生成方案。Spring Boot可以轻松集成这些方案,通过配置和注解简化开发流程。 2. **Redis作为...

    snowflake-C语言实现分布式自增有序的唯一ID生成算法

    We have retired the initial release of Snowflake and working on open sourcing the next version based on Twitter-server, in a form that can run anywhere without requiring Twitter's own infrastructure ...

    SnowFlake:Twitter的分布式自增ID雪花算法snowflake(Java版)

    而twitter的snowflake解决了这种需求,最初是Twitter把存储系统从MySQL迁移到Cassandra,因为Cassandra没有顺序的ID生成机制,所以开发了这样一套唯一的ID生成服务。结构雪花的结构如下(每部分用-分开): 0 - ...

    java快速ID自增器

    3. **分布式ID生成器**:如Snowflake算法,它是由Twitter开源的一种分布式ID生成方案。通过时间戳、工作机器ID和序列号三部分组合,可以生成全局唯一的ID,而且排序性好。在Java中,可以使用诸如Snowflake或者其变种...

    分布式ID生成策略_snowflake算法

    Snowflake算法是由Twitter开源的一种高效且可扩展的分布式ID生成方案,广泛应用于Java和其他编程语言的系统中。 Snowflake算法的核心思想是将64位的整数划分为不同的部分,分别为: 1. **时间戳**(41位):自定义...

    java 获取分布式唯一ID.雪花ID

    public class SnowflakeIdGenerator { private static final SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0); public static long generateId() { return idWorker.nextId(); } } ``` 在这个例子中...

    Twitter Snowflake C#版源码

    Twitter的Snowflake是一种分布式ID生成算法,用于在大规模分布式系统中生成全局唯一的、有序的64位整数ID。这个算法由Twitter开源,解决了在分布式环境下如何生成具有时间序列属性且不重复的ID的问题。现在,我们将...

    java 分布式 代码生成器 唯一ID

    结合上述信息,"idGenerate"这个文件很可能是包含了一个Java实现的分布式代码生成器项目,可能包含了Snowflake算法或者其他分布式ID生成策略的源代码。通过学习和理解这些代码,我们可以更好地掌握在Java环境中如何...

    分布式id公开课.pptx

    - 雪花算法由Twitter提出,生成的ID由时间戳、工作节点ID和序列号三部分组成,全局唯一且有序。 - 时间戳确保ID的全局唯一性和时间顺序;工作节点ID确保不同节点生成的ID不会冲突;序列号在每个节点内部确保唯一性...

    应用级自增ID的生成

    1. **Snowflake算法**:这是一种常见的分布式ID生成策略,由Twitter开源。它通过时间戳、工作节点ID和序列号三部分组成,确保全局唯一性。然而,这里的描述并没有明确提及Snowflake,而是暗示了可能有其他自定义实现...

    雪花算法java版实现

    twitter雪花算法的java实现,分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。 有些时候我们希望能使用...

    分布式ID生成策略(1)_snowflake算法

    Snowflake算法就是一种被广泛使用的分布式ID生成方案,它由Twitter开源,具有时间戳、工作机器ID和序列号三部分组成,能够确保在分布式环境下生成的ID具有唯一性、有序性和高性能。 Snowflake算法的核心思想是将64...

    分布式数据库唯一主键设计

    为解决此问题,可以使用全局自增序列,如Twitter的Snowflake算法,它结合时间戳、工作节点ID和序列号生成全局唯一的64位ID。 2. UUID(通用唯一标识符):UUID是一种广泛使用的全局唯一ID生成方案,但其128位长度...

    snowflake-net-master_snowflake_算法_

    雪花算法是由Twitter开源的一种分布式ID生成算法,它能够为分布式系统中的每个实体生成全局唯一的、单调递增的64位整数ID。这种算法在大数据和分布式环境下广泛应用于主键生成,因为它解决了在分布式环境下的ID唯一...

    Python-分布式系统中常用的的算法python实现

    12. **分布式ID生成器**: 如Twitter的Snowflake算法,生成全局唯一且递增的ID。Python实现将关注时间戳、机器标识和序列号的组合。 项目中的实用工具类可能包括哈希函数、网络通信模块、并发控制、日志记录、配置...

    细聊分布式ID生成方法.pdf

    这是一种基于Twitter开源的ID生成算法。它通过将ID分成多个部分(如时间戳、机器ID、序列号等),从而保证了ID的全局唯一性。此算法广泛应用于高并发场景下的分布式系统中。 - **优点**:支持高并发,性能优越;...

Global site tag (gtag.js) - Google Analytics