关键词:
什么是雪花算法?
雪花算法(Snowflake
)是一种经典的分布式ID生成算法。
在分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。
有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。
而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移到Cassandra,因为Cassandra没有顺序ID生成机制,所以开发了这样一套全局唯一ID生成服务。
其他ID生成算法的优缺点
UUID
缺点:太长,无法排序,使数据库性能降低。
自增ID
缺点:对于数据敏感的场景不宜使用,且不适用于分布式场景。
GUID
缺点:采用无意义字符串数据,数据量增大时造成访问过慢,且不宜排序。
Snowflake算法介绍
原理
snowflake算法产生的ID是一个64位的long整型,结构如下(每部分用-分开):
1位标志位 - 41位时间戳部分 - 10位节点部分 - 12位序列号部分
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。
实现
本机实测:100万个ID 耗时5秒
/**
* Twitter_Snowflake<br>
* SnowFlake的结构如下(每部分用-分开):<br>
* 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
* 1位标识,由于long基本类型在Java中是带符号的,最高位是符号位,正数是0,负数是1,所以id一般是正数,最高位是0<br>
* 41位时间截(毫秒级),注意,41位时间截不是存储当前时间的时间截,而是存储时间截的差值(当前时间截 - 开始时间截)
* 得到的值),这里的的开始时间截,一般是我们的id生成器开始使用的时间,由我们程序来指定的(如下下面程序IdWorker类的startTime属性)。41位的时间截,可以使用69年,年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>
* 10位的数据机器位,可以部署在1024个节点,包括5位datacenterId和5位workerId<br>
* 12位序列,毫秒内的计数,12位的计数顺序号支持每个节点每毫秒(同一机器,同一时间截)产生4096个ID序号<br>
* 加起来刚好64位,为一个Long型。<br>
* 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);
long start = System.currentTimeMillis();
for (int i = 0; i < 1000; i++) {
long id = idWorker.nextId();
System.out.println(Long.toBinaryString(id));
System.out.println(id);
}
System.out.println(System.currentTimeMillis() - start);
}
}
参考:https://github.com/twitter/snowflake
twitter的分布式自增id算法snowflake(java版)(代码片段)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够... 查看详情
转:snowflake分布式自增id算法
原文地址:http://www.cnblogs.com/relucent/p/4955340.html概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们... 查看详情
数据库分库分表(二)twitter-snowflake(64位分布式id算法)分析与java实现
...些id还需要一些大致的顺序(方便客户端排序),并且在分布式系统中不同机器产生的id必须不同。各种主键ID生成策略对比,见常见分布式主键ID生成策略把41位的时间前缀,10位的节点标识,12位的sequence组合在一起。 除了... 查看详情
推特(twitter)的snowflake算法——用于生成唯一id
...是极不友好的。 推特的工程师snowflake也提出了一个在分布式系统中生成唯一序列的方法。SnowFlake的优点是,效率高,整体上按照时间自增排序 查看详情
snowflake算法(代码片段)
1、snowflake算法ID生成器介绍snowflake是twitter开源的一个分布式ID生成器 2、为什么使用snowflake(1)主键自增弊端:不是全局id,当多表合并、构建数据仓库、进行数据分析、会导致主键冲突(2)uuid或guid弊端:数据量过大(3)全局redis... 查看详情
分布式自增id算法snowflake(代码片段)
分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的,作为索引非常不好,严重影响性能。snowflake的结构如下(每部分用-... 查看详情
go工具库分析——go-snowflake(代码片段)
...的唯一id,自增id在数据库中有利于排序和索引,但是在分布式系统中如果还是利用数据库的自增id会引起冲突,自增id非常容易被爬虫爬取数据。在分布式系统中有使用uuid作为数据唯一id的,但是uuid是一串随机字符串,所以它无... 查看详情
雪花算法原理解析(代码片段)
分布式ID常见生成策略: 分布式ID生成策略常见的有如下几种:数据库自增ID。UUID生成。Redis的原子自增方式。数据库水平拆分,设置初始值和相同的自增步长。批量申请自增ID。雪花算法。百度UidGenerator算法(基于雪花算法实... 查看详情
twitter-snowflake:自增id算法(代码片段)
...相近,这样才能方便各种客户端对记录进行排序。Twitter-Snowflake算法就是在这样的背景下产生的。核心Twitter解决这两个问题的方案非常简单高效:每一个ID都是64位数字,由时间戳、工作机器节点和序列号组成,ID是由当前所在的... 查看详情
雪花算法(snowflake)
简介现在的服务基本是分布式、微服务形式的,而且大数据量也导致分库分表的产生,对于水平分表就需要保证表中id的全局唯一性。对于MySQL而言,一个表中的主键id一般使用自增的方式,但是如果进行水平分表... 查看详情
分布式id生成方案:雪花算法(源自twitter)
参考技术A雪花(snowflake)在自然界中,是极具独特美丽,又变幻莫测的东西:雪花算法的原始版本是scala版,用于生成分布式ID(纯数字,时间顺序),订单编号等。算法描述:snowflake.gomain.go测试结果:结论: 查看详情
理解分布式id生成算法snowflake(代码片段)
理解分布式id生成算法SnowFlakehttps://segmentfault.com/a/1190000011282426#articleHeader2分布式id生成算法的有很多种,Twitter的SnowFlake就是其中经典的一种。概述SnowFlake算法生成id的结果是一个64bit大小的整数,它的结构如下图:图片描述1位,... 查看详情
分布式id生成器(代码片段)
...文将对snowflake算法进行讲解: 1.snowflake是Twitter开源的分布式ID生成算法,结果是一个long型的ID。 2.其核心思想是:使用41bit作为毫秒数,10bit作为机器的ID(5个bit是数据中心,5个bit的机器ID),12bit作为毫秒内的流水号,... 查看详情
分布式id理解snowflake算法的实现原理(代码片段)
...owflake算法的实现原理我上次也看了一个视频讲解:【分布式ID】键高并发分布式全局唯一ID雪花算法snowflake2.前提#Snowflake(雪花)是Twitter开源的高性能ID生成算法(服务)。上图是Snowflake的Github仓库,mas 查看详情
分布式id生成方案-snowflake算法(代码片段)
...各种各样的ID,这些ID需要保证全局唯一。我们称之为分布式ID,分布式ID需要满足唯一性、趋势递增性、高可用性、高性能等特点。snowflake算法,也叫雪花算法,是其中的一种分布式ID生成方案。是twitter公司内部... 查看详情
图解分布式id生成算法snowflake(代码片段)
分布式id生成算法的有很多种,Twitter的SnowFlake就是其中经典的一种。概述SnowFlake算法生成id的结果是一个64bit大小的整数,它的结构如下图: 1位,不用。二进制中最高位为1的都是负数,但是我们生成的id一般都使用整数,所... 查看详情
snowflake算法实现(代码片段)
一 背景在分布式系统中,如何在各个不同的服务器产生 ID 值?例如,有一个订单系统部署在A、B 两个节点上,那么如何在这两个节点上产生各自的订单 ID,并且保证 ID 值不会冲突。通常有三种解决方案... 查看详情
分布式id生成方案-snowflake算法(代码片段)
...各种各样的ID,这些ID需要保证全局唯一。我们称之为分布式ID,分布式ID需要满足唯一性、趋势递增性、高可用性、高性能等特点。snowflake算法,也叫雪花算法,是其中的一种分布式ID生成方案。是twitter公司内部... 查看详情