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

Easter79
• 阅读 348

概述

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

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

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

结构

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型。(转换成字符串后长度最多19)

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

源码

(JAVA版本的源码)

/** * Twitter_Snowflake
* SnowFlake的结构如下(每部分用-分开):
* 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000
* 1位标识,由于long基本类型在Java中是带符号的,最高位是符号位,正数是0,负数是1,所以id一般是正数,最高位是0
* 41位时间截(毫秒级),注意,41位时间截不是存储当前时间的时间截,而是存储时间截的差值(当前时间截 - 开始时间截) * 得到的值),这里的的开始时间截,一般是我们的id生成器开始使用的时间,由我们程序来指定的(如下下面程序IdWorker类的startTime属性)。41位的时间截,可以使用69年,年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69
* 10位的数据机器位,可以部署在1024个节点,包括5位datacenterId和5位workerId
* 12位序列,毫秒内的计数,12位的计数顺序号支持每个节点每毫秒(同一机器,同一时间截)产生4096个ID序号
* 加起来刚好64位,为一个Long型。
* 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);
    }
}

}

点赞
收藏
评论区
推荐文章
Jacquelyn38 Jacquelyn38
1年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
一种简易但设计全面的ID生成器思考
分布式系统中,全局唯一ID的生成是一个老生常谈但是非常重要的话题。随着技术的不断成熟,大家的分布式全局唯一ID设计与生成方案趋向于趋势递增的ID,这篇文章将结合我们系统中的ID针对实际业务场景以及性能存储和可读性的考量以及优缺点取舍,进行深入分析。本文并不是为了分析出最好的ID生成器,而是分析设计ID生成器的时候需要考虑哪些,如何设计出
blmius blmius
1年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
艾木酱 艾木酱
1个月前
快速入门|使用MemFire Cloud构建React Native应用程序
MemFireCloud是一款提供云数据库,用户可以创建云数据库,并对数据库进行管理,还可以对数据库进行备份操作。它还提供后端即服务,用户可以在1分钟内新建一个应用,使用自动生成的API和SDK,访问云数据库、对象存储、用户认证与授权等功能,可专
Stella981 Stella981
1年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Wesley13 Wesley13
1年前
(绝对有用)iOS获取UUID,并使用keychain存储
UDID被弃用,使用UUID来作为设备的唯一标识。获取到UUID后,如果用NSUserDefaults存储,当程序被卸载后重装时,再获得的UUID和之前就不同了。使用keychain存储可以保证程序卸载重装时,UUID不变。但当刷机或者升级系统后,UUID还是会改变的。但这仍是目前为止最佳的解决办法了,如果有更好的解决办法,欢迎留言。(我整理的解决办法的参
Wesley13 Wesley13
1年前
MySQL查询按照指定规则排序
1.按照指定(单个)字段排序selectfromtable_nameorderiddesc;2.按照指定(多个)字段排序selectfromtable_nameorderiddesc,statusdesc;3.按照指定字段和规则排序selec
helloworld_34035044 helloworld_34035044
5个月前
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
helloworld_28799839 helloworld_28799839
2个月前
常用知识整理
Javascript判断对象是否为空jsObject.keys(myObject).length0经常使用的三元运算我们经常遇到处理表格列状态字段如status的时候可以用到vue
京东云开发者 京东云开发者
1星期前
为什么mysql不推荐使用雪花ID作为主键
作者:毛辰飞背景在mysql中设计表的时候,mysql官方推荐不要使用uuid或者不连续不重复的雪花id(long形且唯一),而是推荐连续自增的主键id,官方的推荐是auto_increment,那么为什么不建议采用uuid,使用uuid究