Twitter-Snowflake算法产生的背景相当简单,为了满足Twitter每秒上万条消息的请求,每条消息都必须分配一条唯一的id,这些id还需要一些大致的顺序(方便客户端排序),并且在分布式系统中不同机器产生的id必须不同。
Snowflake算法核心
把时间戳,工作机器id,序列号组合在一起。
除了最高位bit标记为不可用以外,其余三组bit占位均可浮动,看具体的业务需求而定。默认情况下41bit的时间戳可以支持该算法使用到2082年,10bit的工作机器id可以支持1023台机器,序列号支持1毫秒产生4095个自增序列id。下文会具体分析。
Snowflake – 时间戳
这里时间戳的细度是毫秒级,具体代码如下,建议使用64位linux系统机器,因为有vdso,gettimeofday()在用户态就可以完成操作,减少了进入内核态的损耗。
1
2
3
4
5
6
|
uint64_t generateStamp() { timeval tv;
gettimeofday(&tv, 0);
return (uint64_t)tv.tv_sec * 1000 + (uint64_t)tv.tv_usec / 1000;
} |
默认情况下有41个bit可以供使用,那么一共有T(1llu << 41)毫秒供你使用分配,年份 = T / (3600 * 24 * 365 * 1000) = 69.7年。如果你只给时间戳分配39个bit使用,那么根据同样的算法最后年份 = 17.4年。
Snowflake – 工作机器id
严格意义上来说这个bit段的使用可以是进程级,机器级的话你可以使用MAC地址来唯一标示工作机器,工作进程级可以使用IP+Path来区分工作进程。如果工作机器比较少,可以使用配置文件来设置这个id是一个不错的选择,如果机器过多配置文件的维护是一个灾难性的事情。
这里的解决方案是需要一个工作id分配的进程,可以使用自己编写一个简单进程来记录分配id,或者利用Mysql auto_increment机制也可以达到效果。
工作进程与工作id分配器只是在工作进程启动的时候交互一次,然后工作进程可以自行将分配的id数据落文件,下一次启动直接读取文件里的id使用。
PS:这个工作机器id的bit段也可以进一步拆分,比如用前5个bit标记进程id,后5个bit标记线程id之类:D
Snowflake – 序列号
序列号就是一系列的自增id(多线程建议使用atomic),为了处理在同一毫秒内需要给多条消息分配id,若同一毫秒把序列号用完了,则“等待至下一毫秒”。
1
2
3
4
5
6
7
8
|
uint64_t waitNextMs(uint64_t lastStamp) { uint64_t cur = 0;
do {
cur = generateStamp();
} while (cur <= lastStamp);
return cur;
} |
总体来说,是一个很高效很方便的GUID产生算法,一个int64_t字段就可以胜任,不像现在主流128bit的GUID算法,即使无法保证严格的id序列性,但是对于特定的业务,比如用做游戏服务器端的GUID产生会很方便。另外,在多线程的环境下,序列号使用atomic可以在代码实现上有效减少锁的密度。
结构为:
0---0000000000 0000000000 0000000000 0000000000 0 --- 00000 ---00000 ---0000000000 00
在上面的字符串中,第一位为未使用(实际上也可作为long的符号位),接下来的41位为毫秒级时间,然后5位datacenter标识位,5位机器ID(并不算标识符,实际是为线程标识),然后12位该毫秒内的当前毫秒内的计数,加起来刚好64位,为一个Long型。
这样的好处是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由datacenter和机器ID作区分),并且效率较高,经测试,snowflake每秒能够产生26万ID左右,完全满足需要。
public class IdWorker { private final long workerId; private final static long twepoch = 1361753741828L; private long sequence = 0L; private final static long workerIdBits = 4L; private final static long maxWorkerId = -1L ^ -1L << workerIdBits; private final static long sequenceBits = 10L; private final static long workerIdShift = sequenceBits; private final static long timestampLeftShift = sequenceBits + workerIdBits; private final static long sequenceMask = -1L ^ -1L << sequenceBits; private long lastTimestamp = -1L; public IdWorker(final long workerId) { super(); if (workerId > maxWorkerId || workerId < 0) { throw new IllegalArgumentException(String.format( "worker Id can't be greater than %d or less than 0", maxWorkerId)); } this.workerId = workerId; } public synchronized long nextId() { long timestamp = this.timeGen(); if (this.lastTimestamp == timestamp) { this.sequence = (this.sequence + 1) & sequenceMask; if (this.sequence == 0) { System.out.println("###########" + sequenceMask); timestamp = this.tilNextMillis(this.lastTimestamp); } } else { this.sequence = 0; } if (timestamp < this.lastTimestamp) { try { throw new Exception(String.format( "Clock moved backwards. Refusing to generate id for %d milliseconds", this.lastTimestamp - timestamp)); } catch (Exception e) { e.printStackTrace(); } } this.lastTimestamp = timestamp; long nextId = ((timestamp - twepoch << timestampLeftShift)) | (this.workerId << workerIdShift) | (this.sequence); // System.out.println("timestamp:" + timestamp + ",timestampLeftShift:" // + timestampLeftShift + ",nextId:" + nextId + ",workerId:" // + workerId + ",sequence:" + sequence); return nextId; } private long tilNextMillis(final long lastTimestamp) { long timestamp = this.timeGen(); while (timestamp <= lastTimestamp) { timestamp = this.timeGen(); } return timestamp; } private long timeGen() { return System.currentTimeMillis(); } public static void main(String[] args) throws InterruptedException { IdWorker worker2 = new IdWorker(2); System.out.println(worker2.nextId()); Thread.sleep(1000L); System.out.println(worker2.nextId()); } }
Reference:
相关推荐
Twitter的分布式自增ID算法snowflake (Java版)
Twitter的分布式自增ID雪花算法snowflake (Java版)
主要介绍了Java实现Twitter的分布式自增ID算法snowflake,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
Twitter Snowflake算法,php版代码; 请见博客: http://blog.csdn.net/envon123/article/details/52953872
而twitter的snowflake解决了这种需求,最初是Twitter把存储系统从MySQL迁移到Cassandra,因为Cassandra没有顺序的ID生成机制,所以开发了这样一套唯一的ID生成服务。结构雪花的结构如下(每部分用-分开): 0 - ...
We have retired the initial release of Snowflake and working on open sourcing the next version based on Twitter-server, in a form that can run anywhere without requiring Twitter's own infrastructure ...
雪花算法,分布式id生成算法的有很多种,Twitter的SnowFlake就是其中经典的一种。
雪花算法分布式ID生成器 这个项目的目的是提供一个轻量级,高并发,高可用的生成唯一ID的服务,生成的ID是一个64位的长整型,彼此唯一,保持递增,相对有序。来生成ID,用于取代UUID类型无序,128位的字符串形式的ID...
nodejs-snowflake是一种快速可靠的方法,可以为分布式系统生成时间可排序的64位ID。 主要的ID生成功能是使用N-API用C ++编写的,这使得ID生成的过程非常快。 使用C ++进行id生成还可以确保生成的数字大小为64位。 ...
snowflake算法是个啥?首先我来提出个问题,怎么在分布式系统中生成唯一性id并保持该id大致自增?在twitter中这是最重要的业务场景,于是twitter推出了一种snowflake算法。
雪花算法分布式ID生成器 该项目的目的是提供一个轻量级、高并发、高可用的生成唯一ID的服务,生成的ID是一个64位的 长整型,全局唯一,保持递增,相对有序。基于twitter的雪花算法来生成ID,用于取代UUID那种无序、...
snowflake算法是Twitter开源的分布式ID生成算法,结果是一个long类型的ID 。其核心思想:使用41bit作为毫秒数,10bit作为机器的ID(5bit数据中心,5bit的机器ID),12bit作为毫秒内的流水号(意味着每个节点在每个...
Twitter 的 snowflake 在分布式生成唯一 UUID 应用还是蛮广泛的,基于 snowflake 的一些变种的算法网上也有不少。使用 snowflake 生成 UUID 很多都是在分布式场景下使用,我看了下网上有其中有几篇 PHP 实现的都没有...
提到id生成器,twitter的snowflake算法 不得不被提起,但是snowflake的算法因为使用了二进制的移位做法,导致其生成的算法过 度的对于机器友好,对于人类并不是那么的友好,也就是说snowflake生成的id对于人类来 说...
SnowFlake 算法,是 Twitter 开源的分布式 id 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 id。在分布式系统中的应用十分广泛,且ID 引入了时间戳,基本上保持自增的,后面的代码中有...
一个基于Snowflake算法PHP ID生成器(Twitter已宣布)。描述雪花算法PHP实现。 Snowflake是一项网络服务,可通过一些简单的保证大规模生成唯一的ID号。 第一位是未使用的符号位。 第二部分包括一个41位的时间戳...
twitter雪花算法的java实现,分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。 有些时候我们希望能使用...
一个实现 Twitter SnowFlake 算法 的 Go 分布式 UID 生成器
高效GUID产生算法(sequence),基于Snowflake实现64位自增ID算法。新增特性:支持自定义允许时间回拨的范围解决跨毫秒起始值每次为0开始的情况(避免末尾必定为偶数,而不便于取余使用问题)解决高并发场景中获取...
Twitter的雪花算法SnowFlake,使用Java代码实现。 分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些...