Twitter雪花算法 SnowFlake算法 的java实现

摘要:
概述SnowFlake算法是Twitter设计的一种算法,可以在分布式系统中生成唯一的ID。它可以满足Twitter每秒分配数万条消息ID的请求。这些消息ID是唯一的,并且具有近似的递增顺序。也许我们不需要像上面那样使用5位作为数据中心ID和5位作为机器ID。我们可以根据业务需求灵活分配节点部分。例如,如果我们不需要数据中心,我们可以使用所有10位作为机器ID;如果数据中心不多,则只能使用3位作为数据中心,使用7位作为机器标识。
概述
SnowFlake算法是Twitter设计的一个可以在分布式系统中生成唯一的ID的算法,它可以满足Twitter每秒上万条消息ID分配的请求,这些消息ID是唯一的且有大致的递增顺序。

原理
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位作为机器标识。


源码

/**
* twitter的snowflake算法 -- java实现
*
* @author rock
* @date 2016/11/26
*/
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);
        for (int i = 0; i < (1 << 12); i++) {
            System.out.println(snowFlake.nextId());
        }
 
    }

 循环生成2^12个ID,运行结果如下:

...
2099698216995
2099698216996
2099698216997
2099698216998
2099698216999
2099698217000
2099698217001
2099698217002
2099698217003
2099698217004
2099698217005
2099698217006
2099698217007
2099698217008
2099698217009
2099698217010
2099698217011
2099698217012
2099698217013
2099698217014
2099698217015
2099698217016
2099698217017
2099698217018
2099698217019
2099698217020
2099698217021
2099698217022
2099698217023
2099698217024
2099698217025
2099698217026
2099698217027
2099698217028
2099698217029
2099698217030
2099698217031
2099702411264
2099702411265
2099702411266
2099702411267
2099702411268
2099702411269
2099702411270
2099702411271
2099702411272
2099702411273
2099702411274
2099702411275
2099702411276
2099702411277
...
可以看到生成的ID都是递增的,而且都是唯一的。

服务器的实现可以参考:基于twitter雪花算法的分布式ID —— 服务器篇
源码已经提交在GitHub:https://github.com/beyondfengyu/SnowFlake

参考
https://github.com/beyondfengyu/SnowFlake
http://www.wolfbe.com/detail/201701/386.html
https://github.com/twitter/snowflake

免责声明:文章转载自《Twitter雪花算法 SnowFlake算法 的java实现》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇SonarQube的安装、配置与使用【转】手动写一个Behavior Designer任务节点下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

行为型设计模式总结

行为型设计模式总结 Intro 行为型模式是将不同的行为代码解耦,从而解决特定场景问题的一些经典结构。 行为型设计模式主要解决的就是“类或对象之间的交互”问题。行为型设计模式比较多,有 11 个,几乎占了 23 种经典设计模式的一半。它们分别是:观察者模式、模板模式、策略模式、职责链模式、状态模式、迭代器模式、访问者模式、备忘录模式、命令模式、解释器模式、中...

树状树组(Binary Indexed Tree (BIT))的C++部分实现

一、树状数组的用处 树状树组是将一个线性数组保存为“树状”,当修改某点的值、求某个区间的和的时候能够有效的减少时间复杂度。当数组长度为N,实时对数组进行M次修改或求和,最坏的情况下复杂度是O(M*N)。 二、树状数组的建立 假设输入数组为 vector<int> nums 将其转化为树状数组的本质在于将数组的原先顺序打乱后,经过特殊的求和方...

第十三节、SURF特征提取算法

上一节我们已经介绍了SIFT算法,SIFT算法对旋转、尺度缩放、亮度变化等保持不变性,对视角变换、仿射变化、噪声也保持一定程度的稳定性,是一种非常优秀的局部特征描述算法。但是其实时性相对不高。 SURF(Speeded Up Robust Features)算法改进了特征了提取和描述方式,用一种更为高效的方式完成特征点的提取和描述。 一 使用快速Hess...

对称加密和非对称加密

对称加密(symmetrical encryption) 采用单钥密码系统的加密方法,同一个密钥可以同时用作信息的加密和解密,这种加密方法称为对称加密,也称为单密钥加密。 常用算法:在对称加密算法中常用的算法有:DES、3DES、TDEA、Blowfish、RC2、RC4、RC5、IDEA、SKIPJACK等。 算法特征 1、加密方和解密方使用同一个密钥;...

Netty构建分布式消息队列实现原理浅析

在本人的上一篇博客文章:Netty构建分布式消息队列(AvatarMQ)设计指南之架构篇中,重点向大家介绍了AvatarMQ主要构成模块以及目前存在的优缺点。最后以一个生产者、消费者传递消息的例子,具体演示了AvatarMQ所具备的基本消息路由功能。而本文的写作目的,是想从开发、设计的角度,简单的对如何使用Netty,构建分布式消息队列背后的技术细节、原理,...

Javaer 进阶必看的 RocketMQ ,就这篇了

每个时代,都不会亏待会学习的人。 大家好,我是 yes。 继上一篇 头条终面:写个消息中间件 ,我提到实现消息中间件的一些关键点,今天就和大家一起深入生产级别消息中间件 - RocketMQ 的内核实现,来看看真正落地能支撑万亿级消息容量、低延迟的消息队列到底是如何设计的。 这篇文章我会先介绍整体的架构设计,然后再深入各核心模块的详细设计、核心流程的剖析...

最新文章