分布式id生成算法(SnowFlake算法)
分布式id生成算法的有很多种,Twitter的SnowFlake就是其中经典的一种。
概述
SnowFlake算法生成id的结果是一个64bit大小的整数,它的结构如下图:
- 1位,不用。二进制中最高位为1的都是负数,但是我们生成的id一般都使用整数,所以这个最高位固定是0。
- 41位,用来记录时间戳(毫秒)。
- 41位可以表示241−1个数字,如果只用来表示正整数(计算机中正数包含0),可以表示的数值范围是:0至241−1,减1是因为可表示的数值范围是从0开始算的,而不是1。也就是说41位可以表示241−1个毫秒的值,转化成单位年则是(2^41−1)/(1000∗60∗60∗24∗365)=69年。
- 10位,用来记录工作机器id。(此处可根据需要调整datacenterId和workerIdde位数,位数和为10即可)。
- 可以部署在210=1024个节点,包括5位datacenterId(机房id)5位workerId(机器id)。
- 5位(bit)可以表示的最大正整数是25−1=31,即可以用0、1、2、3、…31这32个数字,来表示不同的datecenterId或workerId。
- 12位,序列号,用来记录同毫秒内产生的不同id。
- 12位(bit)可以表示的最大正整数是212−1=4095,即可以用0、1、2、3、…4094这4095个数字,来表示同一机器同一时间截(毫秒)内产生的4095个ID序号。
由于在Java中64bit的整数是long类型,所以在Java中SnowFlake算法生成的id就是long来存储的。
SnowFlake可以保证:
- 所有生成的id按时间趋势递增。
- 整个分布式系统内不会产生重复id(因为有datacenterId和workerId来做区分)。
Java代码实现
package com.fyj.util;
import java.text.SimpleDateFormat;
import java.util.Date;
/**
* @author fanyongju
* @Title: IdWorker
* @Description: TODO
* @date 2018/10/1219:35
*/
public class IdWorker {
private long workerId;
private long datacenterId;
private long sequence;
public IdWorker(long workerId, long datacenterId, long sequence) {
// sanity check for workerId
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;
this.sequence = sequence;
}
private long twepoch = 1539920215000L;//初始毫秒时间戳2018-10-19 11:36:55
private long workerIdBits = 7L;//机器选择2^7=128(每个机房最多128台机器)机器id为0~127
private long datacenterIdBits = 3L;//机房选择2^3=8(最多8个机房)机房id为0~7
private long maxWorkerId = -1L ^ (-1L << workerIdBits);//^异或:两个比较的位不同时其结果是1,相同结果为0
private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
private long sequenceBits = 12L;
private long workerIdShift = sequenceBits;
private long datacenterIdShift = sequenceBits + workerIdBits;
private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
private long sequenceMask = -1L ^ (-1L << sequenceBits);
private long lastTimestamp = -1L;
public long getWorkerId() {
return workerId;
}
public long getDatacenterId() {
return datacenterId;
}
public long getTimestamp() {
return System.currentTimeMillis();
}
//用同步锁保证线程安全
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;
//sequence等于0说明毫秒内序列已经增长到最大值
if (sequence == 0) {
//阻塞到下一个毫秒,获得新的时间戳
timestamp = tilNextMillis(lastTimestamp);
}
} else {//时间戳改变,毫秒内序列重置
sequence = 0;//这种重置可能会导致id分布不均,后期如果需要的话,建议改为0-4095之间的随机数
}
//记录上次生成ID的时间截
lastTimestamp = timestamp;
/*
移位并通过或运算拼到一起组成64位的ID,将timestamp减去指定的初始时间戳twepoch结果左移timestampLeftShift(22)位
,然后与上左移datacenterIdShift(19)的datacenterId,再与上左移workerIdShift(12)位的workerId,再与上sequence。
注意:此处转换成二进制进行操作
*/
return ((timestamp - twepoch) << timestampLeftShift) |
(datacenterId << datacenterIdShift) |
(workerId << workerIdShift) |
sequence;
}
private long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
private long timeGen() {
return System.currentTimeMillis();
}
public static void main(String[] args) {//通过生成的id反解出dataCenId和workId
IdWorker idWorker = new IdWorker(39, 7, 0);
while (true) {//请手动终止
Long id = idWorker.nextId();
System.out.println("generate id is:" + id);
StringBuilder dw = new StringBuilder(Long.toBinaryString(id / 4096 % 1024));
StringBuilder time = new StringBuilder(Long.toBinaryString(id / (4096 * 1024)));
if (dw.length() < 10) {
int l = 10 - dw.length();
for (int i = 0; i < l; i++) {
dw.insert(0, "0");
}
}
String dataCenterId = dw.substring(0, 3);
String workId = dw.substring(3);
Date date = new Date((Long.parseLong(time.toString(), 2) + 1288834974657L));
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
System.out.println("time:" + sdf.format(date)
+ ", dataCenterId:" + Long.parseLong(dataCenterId, 2)
+ ", workId:" + Long.parseLong(workId, 2)
+ ", sequence:" + Long.parseLong(Long.toBinaryString(id % 4096), 2));
}
}
}
代码解释
- 获得单一机器的下一个序列号,使用Synchronized控制并发,而非CAS的方式,是因为CAS不适合并发量非常高的场景。
- 如果当前毫秒在一台机器的序列号已经增长到最大值4095,则使用while循环等待直到下一毫秒。
- 如果当前时间小于记录的上一个毫秒值,则说明这台机器的时间回拨了,抛出异常。但如果这台机器的系统时间在启动之前回拨过,那么有可能出现ID重复的危险。
SnowFlake算法的优点:
- 生成ID时不依赖于DB,完全在内存生成,高性能高可用。
- ID呈趋势递增,后续插入索引树的时候性能较好。
SnowFlake算法的缺点:
- 依赖于系统时钟的一致性。如果某台机器的系统时钟回拨,有可能造成ID冲突,或者ID乱序。