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

Easter79
• 阅读 857

概述

分布式系统中,有一些需要使用全局唯一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
2年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Stella981 Stella981
2年前
Nginx + lua +[memcached,redis]
精品案例1、Nginxluamemcached,redis实现网站灰度发布2、分库分表/基于Leaf组件实现的全球唯一ID(非UUID)3、Redis独立数据监控,实现订单超时操作/MQ死信操作SelectPollEpollReactor模型4、分布式任务调试Quartz应用
Stella981 Stella981
2年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
为什么mysql不推荐使用雪花ID作为主键
作者:毛辰飞背景在mysql中设计表的时候,mysql官方推荐不要使用uuid或者不连续不重复的雪花id(long形且唯一),而是推荐连续自增的主键id,官方的推荐是auto_increment,那么为什么不建议采用uuid,使用uuid究
京东云开发者 京东云开发者
8个月前
拆解雪花算法生成规则 | 京东物流技术团队
雪花算法(Snowflake)是一种生成分布式全局唯一ID的算法,生成的ID称为SnowflakeIDs或snowflakes。这种算法由Twitter创建,并用于推文的ID。目前仓储平台生成ID是用的雪花算法修改后的版本。
京东云开发者 京东云开发者
6个月前
分布式系统的主键生成方案对比 | 京东云技术团队
UUID​UUID(通用唯一识别码)是由32个十六进制数组成的无序字符串,通过一定的算法计算出来。为了保证其唯一性,UUID规范定义了包括网卡MAC地址、时间戳、名字空间(Namespace)、随机或伪随机数、时序等元素,以及从这些元素生成UUID的算法。
京东云开发者 京东云开发者
6个月前
Vitess全局唯一ID生成的实现方案 | 京东云技术团队
为了标识一段数据,通常我们会为其指定一个唯一id,比如利用MySQL数据库中的自增主键。但是当数据量非常大时,仅靠数据库的自增主键是远远不够的,并且对于分布式数据库只依赖MySQL的自增id无法满足全局唯一的需求。因此,产生了多种解决方案,如UUID,Sn
Easter79
Easter79
Lv1
今生可爱与温柔,每一样都不能少。
文章
2.8k
粉丝
5
获赞
1.2k