文档章节

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

满风
 满风
发布于 2017/09/05 11:14
字数 1023
阅读 88
收藏 1
点赞 0
评论 0
/**
 * Twitter的分布式自增ID算法snowflake (Java版)
 * (分布式唯一ID生成器)
 *
 * @author dy
 *         JDK-version:  JDK1.7
 *         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 {

    /**
     * 开始时间截 (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;


    /**
     * 构造函数
     *
     * @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;
    }


    /**
     * 获得下一个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();
    }

    /**
     * 测试
     */
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int count = 100000;
        SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);
        for (int i = 0; i < count; i++) {
            long id = idWorker.nextId();
//            System.out.println(Long.toBinaryString(id));
            System.out.println("ID = "+id);
        }
        System.out.println("it takes :"+(System.currentTimeMillis()-start) +" ms");
    }
}

© 著作权归作者所有

共有 人打赏支持
满风

满风

粉丝 81
博文 155
码字总数 167321
作品 0
杭州
技术主管
【死磕Sharding-jdbc】—–分布式ID

原文作者:阿飞Javaer 原文链接:https://www.jianshu.com/p/7f0661ddd6dd 实现动机 传统数据库软件开发中,主键自动生成技术是基本需求。而各大数据库对于该需求也提供了相应的支持,比如M...

飞哥-Javaer ⋅ 05/05 ⋅ 0

MySQL多数据源笔记5-ShardingJDBC实战

Sharding-JDBC集分库分表、读写分离、分布式主键、柔性事务和数据治理与一身,提供一站式的解决分布式关系型数据库的解决方案。 从2.x版本开始,Sharding-JDBC正式将包名、Maven坐标、码云仓...

狂小白 ⋅ 03/19 ⋅ 0

分布式 ID 生成器 - UidGenerator

UidGenerator 是 Java 实现的,基于 Snowflake 算法的唯一 ID 生成器。 UidGenerator 以组件形式工作在应用项目中,支持自定义 WorkerID 位数和初始化策略,从而适用于 Docker 等虚拟化环境下...

匿名 ⋅ 2017/04/07 ⋅ 1

Java程序员必读书单,家族又添新成员

点击关注异步图书,置顶公众号 每天与你分享IT好书 技术干货 职场知识 参与文末话题讨论,每日赠送异步图书。 ——异步小编 有些革命出其不意地吸引了全世界的眼球。Twitter、Linux操作系统和...

异步社区 ⋅ 05/09 ⋅ 0

看到sequence这个开源中国给排39

看开源中国出了这个top 50,看看大神们都出了什么样神奇的作品,看到第39个项目小编的标题是,“分布式高效 ID 生产黑科技”,这个就吸引我的眼球了,因为我的工作经验最多的就是交易流程,这...

woshixin ⋅ 01/18 ⋅ 0

扯扯ID

🙂🙂🙂关注微信公众号:【芋艿的后端小屋】有福利: RocketMQ / MyCAT / Sharding-JDBC 所有源码分析文章列表 RocketMQ / MyCAT / Sharding-JDBC 中文注释源码 GitHub 地址 您对于源码...

芋道源码掘金Java群217878901 ⋅ 2017/06/11 ⋅ 0

Java开发学习之三版本简介 java编程

  Java编程语言,在更迭迅速的互联网领域多年屹立不倒,足以得见Java这门语言旺盛的生命力,因此,会有很多想要进入互联网领域的朋友,想要学Java来转行开发。但是,所谓“隔行如隔山”,j...

老男孩Linux培训 ⋅ 06/05 ⋅ 0

ZooKeeper学习笔记八 ZooKeeper典型应用场景——命名服务

《从Paxos到ZooKeeper分布式一致性原理与实践》 电子工业出版社 命名服务是分布式系统中比较常见的一类场景。命名服务是分布式系统最基本的公共服务之一。在分布式系统中,被命名的实体通常可...

xundh ⋅ 05/02 ⋅ 0

少走弯路,给Java 1~5 年程序员的建议

今天LZ是打算来点干货,因此咱们就不说一些学习方法和技巧了,直接来谈每个阶段要学习的内容甚至是一些书籍。这一部分的内容,同样适用于一些希望转行到Java的同学。 在大家看之前,LZ要先声...

重走Java ⋅ 05/29 ⋅ 0

加强Docker容器与Java 10集成

很多运行在Java虚拟机(JVM)中的应用,包括数据服务如Apache Spark和Kafka以及传统企业应用,都运行在容器中。最近,运行在容器里的JVM出现了由于内存和CPU资源限制和使用率导致性能损失问题...

java高级架构牛人 ⋅ 06/04 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

JDK1.6和JDK1.7中,Collections.sort的区别,

背景 最近,项目正在集成测试阶段,项目在服务器上运行了一段时间,点击表格的列进行排序的时候,有的列排序正常,有的列在排序的时候,在后台会抛出如下异常,查询到不到数据,而且在另外一...

tsmyk0715 ⋅ 30分钟前 ⋅ 0

spring RESTful

spring RESTful官方文档:http://spring.io/guides/gs/rest-service/ 1. 可以这么去理解RESTful:其实就是web对外提供的一种基于URL、URI的资源供给服务。不是一个原理性知识点。是一个方法论...

BobwithB ⋅ 32分钟前 ⋅ 0

C++ 中命名空间的 5 个常见用法

相信小伙伴们对C++已经非常熟悉,但是对命名空间经常使用到的地方还不是很明白,这篇文章就针对命名空间这一块做了一个叙述。 命名空间在1995年被引入到 c++ 标准中,通常是这样定义的: 命名...

柳猫 ⋅ 34分钟前 ⋅ 0

@Conditional派生注解

@Conditional派生注解(Spring注解版原生的@Conditional作用) 作用:必须是@Conditional指定的条件成立,才给容器中添加组件,配置配里面的所有内容才生效; @Conditional扩展注解 作用(判...

小致dad ⋅ 35分钟前 ⋅ 0

适配器模式

适配器模式 对象适配器 通过私有属性来实现的类适配器 通过继承来实现的接口适配器 通过继承一个默认实现的类实现的

Cobbage ⋅ 39分钟前 ⋅ 0

Java 限流策略

概要 在大数据量高并发访问时,经常会出现服务或接口面对暴涨的请求而不可用的情况,甚至引发连锁反映导致整个系统崩溃。此时你需要使用的技术手段之一就是限流,当请求达到一定的并发数或速...

轨迹_ ⋅ 43分钟前 ⋅ 0

GridView和子View之间的间隙

默认的情况下GridView和子View之间会有一个间隙,原因是GridView为了在子View被选中时在子View周围显示一个框。去掉的办法如下: android:listSelector="#0000" 或 setSelector(new ColorDra...

国仔饼 ⋅ 46分钟前 ⋅ 0

idea插件开发

1 刷新页面要使用多线程 2 调试要使用restart bug 不要去关闭调试的idea 否则再次启动会卡住

林伟琨 ⋅ 46分钟前 ⋅ 0

Java 内存模型

物理机并发处理方案 绝大多数计算任务,并不是单纯依赖 cpu 的计算完成,不可避免需要与内存交互,获取数据。内存要拿到数据,需要和硬盘发生 I/O 操作。计算机存储设备与 cpu 之间的处理速度...

长安一梦 ⋅ 53分钟前 ⋅ 0

思路分析 如何通过反射 给 bean entity 对象 的List 集合属性赋值?

其实 这块 大家 去 看 springmvc 源码 肯定可以找到实现办法。 因为 spirngmvc 的方法 是可以 为 对象 参数里面的 list 属性赋值的。 我也没有看 具体的 mvc 源码实现,我这里只是 写一个 简...

之渊 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部