`
郑云飞
  • 浏览: 812548 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Twitter的分布式自增ID算法snowflake

 
阅读更多

各种主键优缺点对比

1.数据库自增主键

优点:简单;唯一;递增;增幅固定

缺点:写性能决定每秒生成数量上限,扩展差;分布式数据库,主节点挂掉,备节点上时可能有问题(主节点写入成功,日志未同步到备节点,导致id重复)

备注:可有一个写库变成多个库同时写,如1、2、3三个库同时写,初始id分别为1、2、3,自增幅度都为3。这种方式可保证id不重复。但导致id不是绝对递增,而是整体趋势上递增;其次是写入的压力仍然很大,mysql容易成为性能瓶颈。

 

2.数据库批量生成id

优点:效率高;降低数据库压力

缺点:需考虑安全性问题,防止取到重复id;如果业务需求是每次只生成一个id,性能有问题

备注:利用数据库,初始化一行数据,初始值为1,取10个id,就给该值加10,调用端取返回id值的前10个数值。以上即为批量生成id思路。

 

3.UUID

优点:本地生成;效率高

缺点:UUID字符串过长,且无实际意义;无法保证递增趋势;建立的索引查询效率低

 

4.当前时间毫秒与微秒

优点:本地生成;延时低;索引性能高

缺点:1秒内请求过1000后id肯定重复,微秒同理

 

5.zookeeper生成id

利用zookeeper增加版本号的方式是其中一种。建立节点,每次使节点版本加1。

优点:利用zk集群解决单点问题

缺点:性能不高;id有上限,提供32位id;需要zk服务

备注:具体代码见 http://blog.csdn.net/gongzi2311/article/details/58144091

 

6.snowflake算法

twitter开源分布式生成id算法。

优点:基本解决了所有问题

缺点:每个节点时间可能不同,生成id是整体趋势递增的

 

所以我采用snowflake算法生成主键,代码如下

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型。(转换成字符串长度为18)

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

/**
 * 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

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

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

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

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

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

    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 ...

    springboot分布式自增id_javaredis_源码

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

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

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

    分布式ID生成策略_snowflake算法

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

    java快速ID自增器

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

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

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

    分布式id公开课.pptx

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

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

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

    应用级自增ID的生成

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

    Twitter Snowflake C#版源码

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

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

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

    snowflake-net-master_snowflake_算法_

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

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

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

    Go-GolangMysql实现的分布式ID生成服务

    Twitter开源的Snowflake算法是一种常用的分布式ID生成策略,它将ID分为三部分:时间戳(41位)、工作机器ID(10位)和序列号(12位)。通过这种方式,可以保证ID的全局唯一性,并且有序。 #### 3.2 UUID UUID...

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

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

    cpp-idgen是一个可以生成全局唯一自增id的分布式的高可用服务

    cpp-idgen可能采用了一种类似于Twitter的Snowflake算法或者百度的WID(Worker ID)算法,这些算法将ID分为多个部分,如时间戳、工作节点ID和序列号,确保了ID的唯一性和顺序性。具体实现可能会包括以下几个步骤: - ...

Global site tag (gtag.js) - Google Analytics