文档章节

【转】Twitter的分布式自增ID算法snowflake

talen
 talen
发布于 07/20 17:49
字数 1221
阅读 5
收藏 0

结构

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型。(转换成字符串长度为18)

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

 

源码

 
  1. /**

  2. * Twitter_Snowflake<br>

  3. * SnowFlake的结构如下(每部分用-分开):<br>

  4. * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>

  5. * 1位标识,由于long基本类型在Java中是带符号的,最高位是符号位,正数是0,负数是1,所以id一般是正数,最高位是0<br>

  6. * 41位时间截(毫秒级),注意,41位时间截不是存储当前时间的时间截,而是存储时间截的差值(当前时间截 - 开始时间截)

  7. * 得到的值),这里的的开始时间截,一般是我们的id生成器开始使用的时间,由我们程序来指定的(如下下面程序IdWorker类的startTime属性)。41位的时间截,可以使用69年,年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>

  8. * 10位的数据机器位,可以部署在1024个节点,包括5位datacenterId和5位workerId<br>

  9. * 12位序列,毫秒内的计数,12位的计数顺序号支持每个节点每毫秒(同一机器,同一时间截)产生4096个ID序号<br>

  10. * 加起来刚好64位,为一个Long型。<br>

  11. * SnowFlake的优点是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分),并且效率较高,经测试,SnowFlake每秒能够产生26万ID左右。

  12. */

  13. public class SnowflakeIdWorker {

  14.  
  15. // ==============================Fields===========================================

  16. /** 开始时间截 (2015-01-01) */

  17. private final long twepoch = 1420041600000L;

  18.  
  19. /** 机器id所占的位数 */

  20. private final long workerIdBits = 5L;

  21.  
  22. /** 数据标识id所占的位数 */

  23. private final long datacenterIdBits = 5L;

  24.  
  25. /** 支持的最大机器id,结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */

  26. private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

  27.  
  28. /** 支持的最大数据标识id,结果是31 */

  29. private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

  30.  
  31. /** 序列在id中占的位数 */

  32. private final long sequenceBits = 12L;

  33.  
  34. /** 机器ID向左移12位 */

  35. private final long workerIdShift = sequenceBits;

  36.  
  37. /** 数据标识id向左移17位(12+5) */

  38. private final long datacenterIdShift = sequenceBits + workerIdBits;

  39.  
  40. /** 时间截向左移22位(5+5+12) */

  41. private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

  42.  
  43. /** 生成序列的掩码,这里为4095 (0b111111111111=0xfff=4095) */

  44. private final long sequenceMask = -1L ^ (-1L << sequenceBits);

  45.  
  46. /** 工作机器ID(0~31) */

  47. private long workerId;

  48.  
  49. /** 数据中心ID(0~31) */

  50. private long datacenterId;

  51.  
  52. /** 毫秒内序列(0~4095) */

  53. private long sequence = 0L;

  54.  
  55. /** 上次生成ID的时间截 */

  56. private long lastTimestamp = -1L;

  57.  
  58. //==============================Constructors=====================================

  59. /**

  60. * 构造函数

  61. * @param workerId 工作ID (0~31)

  62. * @param datacenterId 数据中心ID (0~31)

  63. */

  64. public SnowflakeIdWorker(long workerId, long datacenterId) {

  65. if (workerId > maxWorkerId || workerId < 0) {

  66. throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));

  67. }

  68. if (datacenterId > maxDatacenterId || datacenterId < 0) {

  69. throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));

  70. }

  71. this.workerId = workerId;

  72. this.datacenterId = datacenterId;

  73. }

  74.  
  75. // ==============================Methods==========================================

  76. /**

  77. * 获得下一个ID (该方法是线程安全的)

  78. * @return SnowflakeId

  79. */

  80. public synchronized long nextId() {

  81. long timestamp = timeGen();

  82.  
  83. //如果当前时间小于上一次ID生成的时间戳,说明系统时钟回退过这个时候应当抛出异常

  84. if (timestamp < lastTimestamp) {

  85. throw new RuntimeException(

  86. String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));

  87. }

  88.  
  89. //如果是同一时间生成的,则进行毫秒内序列

  90. if (lastTimestamp == timestamp) {

  91. sequence = (sequence + 1) & sequenceMask;

  92. //毫秒内序列溢出

  93. if (sequence == 0) {

  94. //阻塞到下一个毫秒,获得新的时间戳

  95. timestamp = tilNextMillis(lastTimestamp);

  96. }

  97. }

  98. //时间戳改变,毫秒内序列重置

  99. else {

  100. sequence = 0L;

  101. }

  102.  
  103. //上次生成ID的时间截

  104. lastTimestamp = timestamp;

  105.  
  106. //移位并通过或运算拼到一起组成64位的ID

  107. return ((timestamp - twepoch) << timestampLeftShift) //

  108. | (datacenterId << datacenterIdShift) //

  109. | (workerId << workerIdShift) //

  110. | sequence;

  111. }

  112.  
  113. /**

  114. * 阻塞到下一个毫秒,直到获得新的时间戳

  115. * @param lastTimestamp 上次生成ID的时间截

  116. * @return 当前时间戳

  117. */

  118. protected long tilNextMillis(long lastTimestamp) {

  119. long timestamp = timeGen();

  120. while (timestamp <= lastTimestamp) {

  121. timestamp = timeGen();

  122. }

  123. return timestamp;

  124. }

  125.  
  126. /**

  127. * 返回以毫秒为单位的当前时间

  128. * @return 当前时间(毫秒)

  129. */

  130. protected long timeGen() {

  131. return System.currentTimeMillis();

  132. }

  133.  
  134. //==============================Test=============================================

  135. /** 测试 */

  136. public static void main(String[] args) {

  137. SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);

  138. for (int i = 0; i < 1000; i++) {

  139. long id = idWorker.nextId();

  140. System.out.println(Long.toBinaryString(id));

  141. System.out.println(id);

  142. }

  143. }

  144. }

本文转载自:https://blog.csdn.net/gongzi2311/article/details/58144091

共有 人打赏支持
talen
粉丝 0
博文 31
码字总数 8624
作品 0
深圳
扯扯ID

🙂🙂🙂关注微信公众号:【芋艿的后端小屋】有福利: RocketMQ / MyCAT / Sharding-JDBC 所有源码分析文章列表 RocketMQ / MyCAT / Sharding-JDBC 中文注释源码 GitHub 地址 您对于源码...

芋道源码掘金Java群217878901
2017/06/11
0
0
分布式高效有序 ID 生产--dsequence

高性能(理论QPS > 400w/s)GUID产生算法(sequence),基于Snowflake实现64位自增ID算法。 Twitter-Snowflake算法产生的背景相当简单,为了满足Twitter每秒上万条消息的请求,每条消息都必须分...

李景枫
2017/04/27
287
0
李景枫/sequence

分布式高效ID生产黑科技(sequence) 开源产品介绍(微服务基础设施QQ交流群:191958521) 配置中心(mconf) GITHUB:https://github.com/yu120/mconf 码云:https://git.oschina.net/yu120/mco...

李景枫
2016/07/08
0
0
【迁移2018-05-08 14:14:27】全局唯一ID生成

唯一ID生成 全局唯一ID 《高并发分布式系统中生成全局唯一Id汇总》 Twitter 方案(Snowflake 算法):41位时间戳+10位机器标识(比如IP,服务器名称等)+12位序列号(本地计数器) Flicker 方案...

twentwo
08/10
0
0
ID生成器--idCreator

idCreator是我们设计并且开发一个分布式的id生成器。它主要为业务系统提供唯一、索引友好、 可排序的id。它解决了互联网行业中,使用int自增id或者是string类型的自定义id而导致的 无法方便的...

xuhf
2016/04/26
1K
0

没有更多内容

加载失败,请刷新页面

加载更多

MySQL 到底支不支持事务嵌套?

最近开发中遇到了使用MySQL,多次开启事务,出现了数据错乱问题,伪代码如下: begin; # 操作1 begin; # 操作2 rollback; 执行完后出现了操作1的数据真正写入,只有操作2的数据回滚...

宇润
20分钟前
1
0
fastDfs应用(安装过程待写)

1.效果 2.安装 2.1 导入已经安装好fastDFS的镜像 2.1.1 导入镜像 2.1.2 更改系统兼容性 2.1.3 开机 2.1.4 修改 一下内容 2.1.4.1 修改系统的ip 原来系统ip...

Lucky_Me
24分钟前
2
0
5. Python3源码—字符串(str)对象

5.1. 字符串对象 字符串对象是“变长对象”。 5.1.1. Python中的创建 Python中字符串(strs)对象最重要的创建方法为PyUnicode_DecodeUTF8Stateful,如下Python语句最终会调用到PyUnicode_D...

Mr_zebra
43分钟前
3
0
第十章:路由网关(Zuul)进阶:过滤器、异常处理

第十章:路由网关(Zuul)进阶:过滤器、异常处理 简单介绍了关于Zuul的一些简单使用以及一些路由规则的简单说明。而对于一个统一网关而言,需要处理各种各类的请求,对不同的url进行拦截,或者...

DemonsI
45分钟前
2
0
nginx屏蔽指定接口(URL)

Step1:需求 web平台上线后,需要屏蔽某个服务接口,但又不想重新上线,可以采用nginx屏蔽指定平台接口的办法 Step2:具体操作 location /dist/views/landing/UNIQUE_BEACON_URL { re...

Linux_Anna
54分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部