• 欢迎访问web前端中文站,JavaScript,CSS3,HTML5,web前端demo
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏web前端中文站吧

java实现分布式下Twitter全局唯一ID生成器Snowflake(64位自增ID算法)

JAVA web前端中文站 2年前 (2017-11-02) 1333次浏览 已收录 0个评论

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

更多精彩内容请看 web 前端中文站
http://www.lisa33xiaoq.net 可按 Ctrl + D 进行收藏

关于的算法,网上有很多的介绍。大家可以搜索相关内容进行查看,本文主要用 java 实现它在分布式下的生成方法。

java 实现分布式下 Twitter 全局唯一 ID 生成器 Snowflake(64 位自增 ID 算法)

把时间戳,工作机器 id,序列号组合在一起。

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 左右。

下面是 java 对该算法的实现:

 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======web 前端中文站 www.lisa33xiaoq.net========== 
 /**   * 构造函数   ** @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;  }   
 /**   * 阻塞到下一个毫秒,直到获得新的时间戳   *:www.lisa33xiaoq.net   * @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();   
 return SystemClock.now();  }   
 //==============================Test=============================================   
 /**   * 测试:www.lisa33xiaoq.net   */  
 public static void main(String[] args) {   
 long start = System.currentTimeMillis();   
 SnowflakeIdWorker idWorker0 = new SnowflakeIdWorker(0, 0);   
 for (int i = 0; i < 10000000; i++) {    
 long id = idWorker0.nextId();    
 //System.out.println(id);   }   
 System.out.println("耗时:" + (System.currentTimeMillis() - start));  } }

本实例 1 亿个 id 耗时:37124 毫秒。

【注:本文源自网络文章资源,由站长整理发布】


web 前端中文站 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:java 实现分布式下 Twitter 全局唯一 ID 生成器 Snowflake(64 位自增 ID 算法)
喜欢 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址