文档章节

Twitter的分布式雪花算法 SnowFlake 每秒自增生成26个万个可排序的ID (Java版)

搜云库
 搜云库
发布于 03/13 16:51
字数 1623
阅读 604
收藏 56
点赞 1
评论 0

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

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

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

关注公众号,搜云库,专注于开发技术的研究与知识分享,获取最新文章

搜云库

原理

Twitter的雪花算法SnowFlake,使用Java语言实现。

SnowFlake算法产生的ID是一个64位的整型,结构如下(每一部分用“-”符号分隔):

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

1位标识部分,在java中由于long的最高位是符号位,正数是0,负数是1,一般生成的ID为正数,所以为0;

41位时间戳部分,这个是毫秒级的时间,一般实现上不会存储当前的时间戳,而是时间戳的差值(当前时间-固定的开始时间),这样可以使产生的ID从更小值开始;41位的时间戳可以使用69年,(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年;

10位节点部分,Twitter实现中使用前5位作为数据中心标识,后5位作为机器标识,可以部署1024个节点;

12位序列号部分,支持同一毫秒内同一个节点可以生成4096个ID;

SnowFlake算法生成的ID大致上是按照时间递增的,用在分布式系统中时,需要注意数据中心标识和机器标识必须唯一,这样就能保证每个节点生成的ID都是唯一的。或许我们不一定都需要像上面那样使用5位作为数据中心标识,5位作为机器标识,可以根据我们业务的需要,灵活分配节点部分,如:若不需要数据中心,完全可以使用全部10位作为机器标识;若数据中心不多,也可以只使用3位作为数据中心,7位作为机器标识。

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

源码

本机实测:100万个ID 耗时5秒

/**
 * 描述: Twitter的分布式自增ID雪花算法snowflake (Java版)
 * https://github.com/souyunku/SnowFlake
 *
 * @author yanpenglei
 * @create 2018-03-13 12:37
 **/
public class SnowFlake {

    /**
     * 起始的时间戳
     */
    private final static long START_STMP = 1480166465631L;

    /**
     * 每一部分占用的位数
     */
    private final static long SEQUENCE_BIT = 12; //序列号占用的位数
    private final static long MACHINE_BIT = 5;   //机器标识占用的位数
    private final static long DATACENTER_BIT = 5;//数据中心占用的位数

    /**
     * 每一部分的最大值
     */
    private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
    private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);

    /**
     * 每一部分向左的位移
     */
    private final static long MACHINE_LEFT = SEQUENCE_BIT;
    private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
    private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;

    private long datacenterId;  //数据中心
    private long machineId;     //机器标识
    private long sequence = 0L; //序列号
    private long lastStmp = -1L;//上一次时间戳

    public SnowFlake(long datacenterId, long machineId) {
        if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {
            throw new IllegalArgumentException("datacenterId can't be greater than MAX_DATACENTER_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
     *
     * @return
     */
    public synchronized long nextId() {
        long currStmp = getNewstmp();
        if (currStmp < lastStmp) {
            throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
        }

        if (currStmp == lastStmp) {
            //相同毫秒内,序列号自增
            sequence = (sequence + 1) & MAX_SEQUENCE;
            //同一毫秒的序列数已经达到最大
            if (sequence == 0L) {
                currStmp = getNextMill();
            }
        } else {
            //不同毫秒内,序列号置为0
            sequence = 0L;
        }

        lastStmp = currStmp;

        return (currStmp - START_STMP) << TIMESTMP_LEFT //时间戳部分
                | datacenterId << DATACENTER_LEFT       //数据中心部分
                | machineId << MACHINE_LEFT             //机器标识部分
                | sequence;                             //序列号部分
    }

    private long getNextMill() {
        long mill = getNewstmp();
        while (mill <= lastStmp) {
            mill = getNewstmp();
        }
        return mill;
    }

    private long getNewstmp() {
        return System.currentTimeMillis();
    }

    public static void main(String[] args) {
        SnowFlake snowFlake = new SnowFlake(2, 3);

        long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            System.out.println(snowFlake.nextId());
        }

        System.out.println(System.currentTimeMillis() - start);


    }
}

循环生成的ID,运行结果如下:

170916032679263329
170916032679263330
170916032679263331
170916032679263332
170916032679263333
170916032679263334
170916032679263335
170916032679263336
170916032679263337
170916032679263338
170916032679263339
170916032679263340
170916032679263341
170916032679263342

开源地址

Github:https://github.com/souyunku/SnowFlake

推荐阅读

Spring Cloud 系列教程

Spring Boot 系列教程

源码 + 教程

Github:https://github.com/souyunku/spring-boot-examples

Spring Cloud 系列教程

Docker 容器

环境搭建

关注微信公众号

  • 作者:鹏磊
  • 出处:http://www.ymq.io
  • 版权归作者所有,转载请注明出处
  • Wechat:关注公众号,搜云库,专注于开发技术的研究与知识分享

关注公众号-搜云库

© 著作权归作者所有

共有 人打赏支持
搜云库
粉丝 97
博文 63
码字总数 215581
作品 1
朝阳
后端工程师
【死磕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

Twitter的分布式自增ID算法Snowflake实现分析及其Java、Php和Python版

在分布式系统中,需要生成全局UID的场合还是比较多的,twitter的snowflake解决了这种需求,实现也还是很简单的,除去配置信息,核心代码就是毫秒级时间41位+机器ID 10位+毫秒内序列12位。 该...

真爱2015 ⋅ 2016/05/18 ⋅ 0

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

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

异步社区 ⋅ 05/09 ⋅ 0

扯扯ID

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

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

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

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

woshixin ⋅ 01/18 ⋅ 0

ID生成器--idCreator

idCreator是我们设计并且开发一个分布式的id生成器。它主要为业务系统提供唯一、索引友好、 可排序的id。它解决了互联网行业中,使用int自增id或者是string类型的自定义id而导致的 无法方便的...

xuhf ⋅ 2016/04/26 ⋅ 0

分布式高效有序 ID 生产--dsequence

高性能(理论QPS > 400w/s)GUID产生算法(sequence),基于Snowflake实现64位自增ID算法。 Twitter-Snowflake算法产生的背景相当简单,为了满足Twitter每秒上万条消息的请求,每条消息都必须分...

李景枫 ⋅ 2017/04/27 ⋅ 0

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

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

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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

vim基础-编辑模式-命令模式

编辑模式:可以编辑修改文件。编辑模式下 按“esc”键返回一般模式。 按一次“Insert”键 (一般在键盘回格键右边)作用和“i”一样表示“插入”。按两次“Insert”键表示“替换”,作用为:...

ZHENG-JY ⋅ 15分钟前 ⋅ 0

MaxCompute读取分析OSS非结构化数据的实践经验总结

摘要: 本文背景 很多行业的信息系统中,例如金融行业的信息系统,相当多的数据交互工作是通过传统的文本文件进行交互的。此外,很多系统的业务日志和系统日志由于各种原因并没有进入ELK之类...

阿里云云栖社区 ⋅ 20分钟前 ⋅ 0

Linux操作系统有何优势?Linux学习

  当今世界流行的操作系统有3大类,Linux、Mac OS和Windows操作系统,Linux操作系统因其开源、免费、跨平台、良好的界面等特性,深受广大程序员们的青睐!   Linux操作系统被广泛的应用于...

老男孩Linux培训 ⋅ 21分钟前 ⋅ 0

Spring Cloud Spring Boot mybatis分布式微服务云架构 开发Web应用

静态资源访问 在我们开发Web应用的时候,需要引用大量的js、css、图片等静态资源。 默认配置 Spring Boot默认提供静态资源目录位置需置于classpath下,目录名需符合如下规则: /static /pub...

itcloud ⋅ 25分钟前 ⋅ 0

6月19日任务 设置更改root密码、连接mysql、mysql常用命令

13.1 设置更改root密码 1. /usr/local/mysql/bin/mysql -uroot 设置环境变量 : export PATH=$PATH:/usr/local/mysql/bin/ 永久生效: vim /etc/profile 加入 export PATH=$PATH:/usr/local/m......

吕湘颖 ⋅ 27分钟前 ⋅ 0

MaxCompute读取分析OSS非结构化数据的实践经验总结

摘要: 本文背景 很多行业的信息系统中,例如金融行业的信息系统,相当多的数据交互工作是通过传统的文本文件进行交互的。此外,很多系统的业务日志和系统日志由于各种原因并没有进入ELK之类...

猫耳m ⋅ 28分钟前 ⋅ 0

Spring MVC controller,return重定向redirect:

@RequestMapping(value="/save",method=RequestMethod.POST)public String doSave(Course course) {log.debug("Info of Course");log.debug(ReflectionToStringBuilder.toStr......

颖伙虫 ⋅ 36分钟前 ⋅ 0

JavaSE——线程介绍

声明:本栏目所使用的素材都是凯哥学堂VIP学员所写,学员有权匿名,对文章有最终解释权;凯哥学堂旨在促进VIP学员互相学习的基础上公开笔记。 线程: 介绍:管线程叫多任务处理,首先你得知道...

凯哥学堂 ⋅ 39分钟前 ⋅ 0

ORM——使用spring jpa data实现逻辑删除

前言 在业务中是忌讳物理删除数据的,数据的这个对于一个IT公司可以说是最核心的资产,如果删除直接就物理删除,无疑是对核心资产的不重视,可能扯的比较远,本文最主要是想通过spring jpa ...

alexzhu592 ⋅ 46分钟前 ⋅ 0

CDN caching

Incapsula应用感知CDN使用智能分析和频率分析来动态缓存内容,并最大限度地提高效率。确保可直接从RAM获取最常访问的资源,而不依赖于较慢的访问机制。 1、 静态内容缓存 Incapsula缓存静态内...

上树的熊 ⋅ 49分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部