雪花算法简介
SnowFlake 中文意思为雪花,故称为雪花算法。最早是 Twitter 公司在其内部用于分布式环境下生成仅有 ID。
雪花算法有以下几个长处:
- 高并发分布式环境下生成不重复 id,每秒可生成百万个不重复 id。
- 基于时刻戳,以及同一时刻戳下序列号自增,根本保证 id 有序递加。
- 不依靠第三方库或许中间件。
- 算法简略,在内存中进行,效率高。
雪花算法有如下缺点:
- 依靠服务器时刻,服务器时钟回拨时或许会生成重复 id。算法中可经过记录最终一个生成 id 时的时刻戳来处理,每次生成 id 之前比较当时服务器时钟是否被回拨,避免生成重复 id。
- 需求装备机器ID和服务器ID
[参考来源](SnowFlake 雪花算法详解与实现 – ())
容器化布置雪花算法遇到的问题
-
容器化无状况布置机器ID不行获取
以前项目运用物理机器布置时,我们可以根据机器的IP分配对就的机器id,可是现在都是运用容器化布置,一般都是布置成无状况形式,无法获取workId;
-
一个容器一般只布置一个服务,所有服务id可以不需求了。
处理思路
- 将机器id和服务id兼并
- 项目启用时经过redis获取一个workId
RID的诞生
根本思路
- 为每个微服务装备一个rid.redisKey,当作该服务在redis中的仅有标识服务
- 在项目启用时,将rid.redisKey自增,获取到一个workId
- 将wordId与maxWorkerId取余运算,得到单个服务的仅有workId
核心代码
/**
* 根本Redis生成ID
*/
@Component
public class ID {
@Resource
private StringRedisTemplate stringRedisTemplate;
private static Long REDIS_ID;
/**
* redis KEY 不同项目需求修改
*/
@Value("${rid.redisKey}")
private String ID_REDIS_KEY = "RID";
/**
* 起始时刻戳
*/
@Value("${rid.startStamp}")
private Long startStamp = 1577808000000L;
/**
* 机器id所占的位数 最多机器节点2^5=32个
*/
@Value("${rid.workerIdBits}")
private final long workerIdBits = 5L;
/**
* 序列号所占的位数 决议单个容器每毫秒生成速度,默认每毫秒生成 2^7=128
*/
@Value("${rid.sequenceBits}")
private final long sequenceBits = 7L;
/**
* 时刻戳位数 从startStamp开始可以 2^41/(1000606024365)=69,大概可以运用69年。
*/
private final long timeStampBits = 41L;
private Long workerId;
@PostConstruct
void init() {
REDIS_ID = stringRedisTemplate.opsForValue().increment(ID_REDIS_KEY) % maxWorkerId;
}
/**
* 时刻戳最大值
*/
private final long maxTimeStamp = ~(-1L << timeStampBits);
/**
* 机器id的最大值
*/
private final long maxWorkerId = ~(-1L << workerIdBits);
/**
* 序列号的最大值
*/
private final long maxSequence = ~(-1L << sequenceBits);
private long sequence = 0L;
private long lastTimeStamp = -1L;
public synchronized long id() {
long currentTimeStamp = timeGen();
if (currentTimeStamp < lastTimeStamp) {
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimeStamp - currentTimeStamp));
}
if (lastTimeStamp == currentTimeStamp) {
sequence = (sequence + 1) & maxSequence;
if (sequence == 0) {
currentTimeStamp = tilNextMillis(lastTimeStamp);
}
} else {
sequence = 0L;
}
lastTimeStamp = currentTimeStamp;
return ((currentTimeStamp - startStamp) & maxTimeStamp) << (sequenceBits + workerIdBits) | (workerId << sequenceBits) | sequence;
}
private long tilNextMillis(long lastTimeStamp) {
long timeStamp = timeGen();
while (timeStamp <= lastTimeStamp) {
timeStamp = timeGen();
}
return timeStamp;
}
private long timeGen() {
return System.currentTimeMillis();
}
private static class SingletonHolder {
private static ID ID;
static {
ID = new ID(REDIS_ID);
}
}
public static ID getInstance() {
return SingletonHolder.ID;
}
private ID() {
}
private ID(long workerId) {
this.workerId = workerId;
}
}
@Component
public class RID {
public static Long generateId() {
return ID.getInstance().id();
}
}
测验代码
@RunWith(SpringRunner.class)
@SpringBootTest(classes = {Application.class})
public class SpringBootApplicationTests {
@Test
public void testId() {
Set<Long> ids = new HashSet<>();
int size = 1000000;
long startTime=System.currentTimeMillis();
for (int i = 0; i < size; i++) {
ids.add(RID.generateId());
}
System.out.println(String.format("generate %d ids spend %s ms",size,System.currentTimeMillis()-startTime));
Assert.assertEquals(size, ids.size());
}
}
长处
- 无需装备机器ID,服务ID,可以用微服务的applicationId当作rid.redisKey,可无状况化布置
- 单个微服务容器最大节点数量及生成速度可装备
- ID大部分情况是自增了
存在问题
- ID只能做到单个容器仅有,不行做到大局仅有
- 2^workerIdBits> 2倍容器数据,容器节点重启会生成新的容器,然后替换本来老容器
- 集群中如果有容器一直不重启,后面重启容器或许会分配到相当的workId导致ID重复
- 生成的ID位数不固定 当时时刻-startStamp 位数会跟着时刻添加,数据库不要用varchar类型
- 服务器时刻回拨,或许导致ID重复
- ID不是严厉大局自增,同一毫秒内rid.redisKey到达maxWorkerId后从0开始,或许导致生成ID比其它服务生成的小