资讯专栏INFORMATION COLUMN

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

Awbeci / 1363人阅读

摘要:原理的雪花算法,使用语言实现。生成的整体上按照时间自增排序,并且整个分布式系统内不会产生碰撞由和作区分,并且效率较高。据说每秒能够产生万个。

分布式系统中,有一些需要使用全局唯一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 Cloud(一)服务的注册与发现 Eureka

Spring Cloud(二)Consul 服务治理实现

Spring Cloud(三)服务提供者 Eureka + 服务消费者(rest + Ribbon)

Spring Cloud(四)服务提供者 Eureka + 服务消费者 Feign

Spring Cloud(五)断路器监控(Hystrix Dashboard)

Spring Cloud(六)服务网关 zuul 快速入门

Spring Cloud(七)服务网关 Zuul Filter 使用

Spring Cloud(八)高可用的分布式配置中心 Spring Cloud Config

Spring Cloud(九)高可用的分布式配置中心 Spring Cloud Config 集成 Eureka 服务

Spring Cloud(十)高可用的分布式配置中心 Spring Cloud Config 中使用 Refresh

Spring Cloud(十一)高可用的分布式配置中心 Spring Cloud Bus 消息总线集成(RabbitMQ)

Spring Boot 系列教程

源码 + 教程

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

Docker 容器

Docker Compose 1.18.0 之服务编排详解

Docker CE 安装 初窥 Dockerfile 部署 Nginx

Docker Container 容器操作

Docker Hub 仓库使用,及搭建 Docker Registry

Docker Registry Server 搭建,配置免费 HTTPS 证书,及拥有权限认证、TLS 的私有仓库

Docker Registry 企业级私有镜像仓库Harbor管理WEB UI, 可能是最详细的部署

Docker 部署 SpringBoot 项目整合 Redis 镜像做访问计数 Demo

Docker Maven Plugin 生成 Docker 镜像 push 到 DockerHub上

环境搭建

搭建 Apache RocketMQ 单机环境

手把手教你 MongoDB 的安装与详细使用(一)

手把手教你 MongoDB 的安装与详细使用(二)

搭建 MongoDB分片(sharding) / 分区 / 集群环境

搭建 SolrCloud 集群服务

搭建 Solr 单机服务

搭建 RabbitMQ 集群服务

搭建 RabbitMQ 单机服务

Mycat 读写分离 数据库分库分表 中间件 安装部署,及简单使用

离线部署 CDH 5.12.1 及使用 CDH 部署 Hadoop 大数据平台集群服务

Contact

作者:鹏磊

出处:http://www.ymq.io

版权归作者所有,转载请注明出处

Wechat:关注公众号,搜云库,专注于开发技术的研究与知识分享

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/68769.html

相关文章

  • 墙裂推荐:搜云库技术团队,面试必备技术干货

    摘要:今天整理了一下近大半年以来的一些文章,和我的预期一样,很多文章我都忘记自己曾经写过了,这个记录的过程让我也有了新的理解。希望大家,收藏,点赞,加转发。 今天整理了一下近大半年以来的一些文章,和我的预期一样,很多文章我都忘记自己曾经写过了,这个记录的过程让我也有了新的理解。希望大家,收藏,点赞,加转发。 面试必备 面试必备:深入Spring MVC DispatchServlet 源码...

    SegmentFault 评论0 收藏0
  • 墙裂推荐:搜云库技术团队,面试必备技术干货

    摘要:今天整理了一下近大半年以来的一些文章,和我的预期一样,很多文章我都忘记自己曾经写过了,这个记录的过程让我也有了新的理解。希望大家,收藏,点赞,加转发。 今天整理了一下近大半年以来的一些文章,和我的预期一样,很多文章我都忘记自己曾经写过了,这个记录的过程让我也有了新的理解。希望大家,收藏,点赞,加转发。 面试必备 面试必备:深入Spring MVC DispatchServlet 源码...

    Neilyo 评论0 收藏0
  • 关于生成订单号规则一些思考

    摘要:关于我为什么写这篇文章是因为今天在做订单模块的时候看到之前的上描述的年月日用户位企业位四位自增长数。背景对于其定订单的生成。个人的看法是主要是唯一,其他关于业务方面的不是太太重要。自增实现了用于将的值递增,并返回结果。 关于我为什么写这篇文章是因为今天在做订单模块的时候,看到之前的PRD上描述的年月日+用户id2位+企业id位+四位自增长数。然后竟被我反驳的突然改成了精确时间+4位自增...

    omgdog 评论0 收藏0
  • 雪花算法 - snowflake

    摘要:有些时候我们希望能使用一种简单一些的,并且希望能够按照时间有序生成。转换成字符串后长度最多生成的整体上按照时间自增排序,并且整个分布式系统内不会产生碰撞由和作区分,并且效率较高。经测试每秒能够产生万个。 概述 分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。 有些时候我...

    lemon 评论0 收藏0
  • 布式id生成方案概述

    摘要:序本文主要来聊聊分布式的生成方案。分布式的生成,以为代表的,系列算法采用的就是划分命名空间并行生成的思路。 序 本文主要来聊聊分布式id的生成方案。 目标 业务系统需要什么样的ID生成器中提出了几点目标: 唯一性 时间相关 粗略有序 可反解 可制造 主要思路 对于每个标识,都需要有一个命名空间(namespace),来保证其相对唯一性。分布式的ID生成,以Twitter Snowf...

    Terry_Tai 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<