文档章节

【转】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
博文 19
码字总数 2218
作品 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
Twitter-Snowflake,64位自增ID算法详解

Twitter-Snowflake算法产生的背景相当简单,为了满足Twitter每秒上万条消息的请求,每条消息都必须分配一条唯一的id,这些id还需要一些大致的顺序(方便客户端排序),并且在分布式系统中不同...

毛爷爷夸我帅
2016/05/10
448
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

HTTPS is easy

HTTPS is easy https://www.troyhunt.com/https-is-easy/ HTTPS is easy! In fact, it's so easy I decided to create 4 short videos around 5 minutes each to show people how to enable ......

openthings
20分钟前
0
0
bugList 2

用户端: 1. 上传文件时,当选择:彩色-A3-双面时,第二个图片有bug 应改为 和第一个图片的类型相同 2. 确认打印时,三个下拉选目前有bug 应改为:根据后台配置的商家,group by计算出不同城...

勇恒
23分钟前
2
0
keras cnn 网咯 mnist 分类

搭建貌似比tf是简单很多。。。。。 from keras.datasets import mnistfrom keras.utils import np_utilsfrom keras.models import Sequentialfrom keras.layers import Dense, Activat......

阿豪boy
25分钟前
0
0
解决 /var/run/nginx.pid failed

nginx: [error] open() "/var/run/nginx.pid" failed (2: No such file or directory) sudo nginx -c /etc/nginx/nginx.conf nginx -s reload...

驛路梨花醉美
27分钟前
0
0
nginx负载均衡-ssl原理-生成ssl密钥对-nginx配置ssl

nginx负载均衡: 1.创建配置文件 vim /usr/local/nginx/conf/vhost/load.conf #添加以下内容: upstream qq_com #名字自定义,借助此模块定义多个IP,后面...

ZHENG-JY
27分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部