江苏龙网

  1. 主页 > 生活百科 > >

雪花算法

雪花算法

雪花算法
SnowFlake 算法，是 Twitter 开源的分布式 id 生成算法 。其核心思想就是：使用一个 64 bit 的 long 型的数字作为全局唯一 id 。在分布式系统中的应用十分广泛，且ID 引入了时间戳，基本上保持自增的 。本文主要是是实现了单机版本的算法，使用多台计算机构成分布式的ID生成服务也是可以的，预留了相关的方法参数 。
应用范围
1、在jdk中自带的uuid算法可以来生成唯一性的32位字符串【拼接上‘-’之后，是36位，如：’
4211210a-ba56-41b4-b055-6262411970a4’】，uuid算法得到的id是无序的，而且是字符串，数据表记录多时，查询效率不高
2、基于数据库的sequnce【通过表也可以模拟sequence】来生成，在分布式系统中更新记录不方便，只能操作主表的更新 。
3、雪花算法在分布式系统中可以较好地使用 。
原理
把64位进行拆分，分为如下几个部份
第1部份只占1位，而且必需为0，因为最高位0表示正数 。
第2部份是时间戳，占41位【为什么是41位，后面会介绍】，最多可以表示2^41，大约是69年
第3部份是产生的机器号，占10位【也可以是其它位数，不一定非得是10位，官方约定是10位】，最多可以表示2^10，相当于1024台机器，这部分可以划成两个维度，如下：
3.1 拿5位出来做为机房号，最多可以表示 2^5个机房号，也就是最多32个机房编号
3.2 拿5位出来做为机器号，最多可以表示 2^5台电脑，也就是最多32台电脑编号
第4部份是时间戳，占12位，相当于在同一个毫秒内，可以最大支持2^12，也就是4096个序号【普通的计算机根本达不到】
代码实现
 
public class IdGenerator {
 
//定义属性 [机器码10位，如何分配成 机房码和电脑码，做为属性，这里默认都是5]
private final long dataCenterBits = 5L; //机房码的位数
private final long computerBits = 5L; //电脑码的位数
//最后的序列码，默认从0开始
private long sequence = 0L;
//记录执行的最后时间，以毫秒为单位，默认初始化为-1L
private long lastTimeStamp = -1L;
 
//因为要做二进制运算，我们需要定义如下属性来记录每个部份所在的位置的偏移量
private final long sequenceBits = 12; //序号占用12位
private final long computerIdShift = sequenceBits; //电脑码的偏移量
private final long dataCenterIdShift = computerIdShift + computerBits; //机房码的偏移量
private final long timeStampShift = dataCenterIdShift + dataCenterBits; //时间戳的偏移量
 
//根据机房码的位数，来计算出机房码最大值
private final long MAX_DATA_CENTER = -1L ^ (-1L << dataCenterBits); //相当于 11111，也就是 31
private final long MAX_COMPUTER = -1L ^ (-1L << computerBits); //同上
private final long SEQUENCE_MASK = -1L ^ (-1L << sequenceBits); // 为防止序列号溢出而准备的掩码，相当于 11111111 111
 
//定义属性
private long computerId; //电脑的id 【在分布式系统中，记录这个雪花号是由哪一台电脑生成的】
private long dataCenterId; //机房的id 【在分布式系统中，记录这个雪花号是由哪一个中心机房里的电脑生成的】
//构造
public IdGenerator(long computerId, long dataCenterId) {
//对参数的有效性进行判断，由于机房码和电脑码都是5位，所以，它们的值最大都不能超过31
if(computerId > MAX_COMPUTER || computerId < 0) {
throw new IllegalArgumentException(String.format("电脑编号不能大于 %d 或者小于 %d n",MAX_COMPUTER,0));
}
if(dataCenterId > MAX_DATA_CENTER || dataCenterId < 0) {
throw new IllegalArgumentException(String.format("机房编号不能大于 %d 或者小于 %dn",MAX_DATA_CENTER, 0));
}
//赋值
this.computerId = computerId;
this.dataCenterId = dataCenterId;
}
/***************
* 核心方法，利用雪花算法来获取一个唯一性的ID
* @return
*/
public synchronized long nextId() {
//1.获取当前的系统时间
long currTime = getCurrentTime();
//2. 判断是否在同一个时间内的请求
if(currTime == lastTimeStamp) {
//2.1 sequence 要增1, 但要预防sequence超过 最大值4095，所以要 与 SEQUENCE_MASK 按位求与
sequence = (sequence + 1) & SEQUENCE_MASK;
//2.2 进一步判断，如果在同一个毫秒内，sequence达到了4096【1 0000 0000 0000】，则lastTime时间戳必需跳入下一个时间，因为同一个毫秒内
//sequence只能产生4096个【0-4095】，当超过时，必需跳入下一个毫秒


推荐阅读


上一篇：算法系列之接雨水

下一篇：Camunda如何调用Java自定义类