2017年的时候项目组在开发一款大区游戏，由于之前demo阶段的玩家id都是单服生成的，只能保证单进程中的唯一，而无法保证在分布式服务器端的唯一性。随着项目的开发进展，需要设计能保证在分布式的场景下，玩家id全局唯一的方案。由于当时游戏里面服务器都有一个唯一的serverId，所以自然而然想到用“serverId + 自增id”作为全局唯一的玩家id的设计方案。后来才知道，类似的这种分布式全局唯一id的方法叫“雪花算法”。这次借着重新造轮子的机会，重新思考了一下雪花算法的设计过程和实现方式。
一个long型id的二进制总共有64位，除去符号位剩余63位，全局唯一id就是将这63位的二进制划分为几个部分，其中一部分代表这个id在全局中的分段，一部分表示局部的差异。
通常雪花算法生成的id由三个部分组成：机器编码,时间戳，序列号。其中机器编码表示当前进程的唯一id;时间戳区分不同时间点生成的id;序列号用来区分相同时间戳下生成的不同的id。
机器编码就是代表这个id在全局中的分段，相当于是给当前的进程分配了一个id分段。当前进程只要在这个分段中分配id，那么就不可能和其他进程分配的id发生重复。这也有点类似于ip的分段，假如某个国家分配到了192.0.0.0这个分段的ip,那么只要在192这个分段内任意再分配ip，比如192.0.0.2，它们都不会和其他国家的ip地址冲突。因此，当整个系统中，每个服务器的机器编码确定且唯一时，各个系统可以独自以自增的形式生成id,而不必使用全局锁控制全局id的唯一性。
时间戳的作用是为了区分不同时间点生成的id。如果单单使用自增id,当第一次从0开始计数，生成N次id以后。如果服务器重启，那么自增id又将从头开始从0计数，那么id就会出现重复的情况。这时，要么依赖存储将自增id记录下来，要么在全局id中加入时间戳的部分，让id持续往自增，不再出现重启之后id回退的情况。
假如在同一个时间点上，进程需要生成多个id,那么序列号就标出这个id在同一时间点上，是第几个id了。
雪花算法的二进制位数分配
雪花算法的id中的每个部分的二进制长度都是根据自己的业务需求来进行分配的。目前我的代码中分配的二进制如下。
groupId(5) + serverId(15) + sequence(11) + timestamp(32)
其中groupId和serverId表示服务器的机器编码。由于是在我们游戏中生成全局唯一的id，游戏可能存在分区可能，而且预计每个区可能有几千个服，因此对机器编码留了一定的余量，总共分配了20位。
sequence大体上都是分配10~14位左右，这里取11位。剩下的32位空间就是时间戳，而32位一般可以表示时间戳的秒数。那么这里两个字段也就预示了在1秒的时间范围内最多只能生成2048个id。
贴上实现的代码：
public class SnowFlake {
private static final int GroupId_Bit_Num = 5;
private static final int ServerId_Bit_Num = 15;
private static final int Sequence_Bit_Num = 11;
private static final int Timestamp_Bit_Num = 63 - GroupId_Bit_Num - ServerId_Bit_Num - Sequence_Bit_Num;
private static final int GroupId_Bit_Shift = ServerId_Bit_Num + Sequence_Bit_Num + Timestamp_Bit_Num;
private static final int ServerId_Bit_Shift = Sequence_Bit_Num + Timestamp_Bit_Num;
private static final int Sequence_Bit_Shift = Timestamp_Bit_Num;
private static final long Sequence_Mark_Flag = (1L << Sequence_Bit_Num) - 1;
private static final long Timestamp_Mark_Flag = (1L << Timestamp_Bit_Num) - 1;
/** 设置一个时间起始点 */
private static long Epoch = 0;
private static long Default_Epoch_Date = 1671073633L; // 2022-12-15 10:38:50
private static long Time_Offset = 5;
private static long groupId;
private static long serverId;
private static long sequence;
private static long lastTime = System.currentTimeMillis() / 1000;
/**
* 初始化算法的字段
* @param groupId
* @param serverId
* @param epochDate 初始化时间起点（null表示默认起始日期）,后期修改会导致id重复,如果要修改，时间只能往前改，不能往后改
*/
public static void init(int groupId, int serverId, Date epochDate) {
if (groupId <= 0 || groupId >= (1 << GroupId_Bit_Num)) {
throw new IllegalArgumentException("groupId is out of range, 0 ~ " + (1 >> GroupId_Bit_Num));
}
if (serverId <= 0 || serverId >= (1 << ServerId_Bit_Num)) {
throw new IllegalArgumentException("serverId is out of range, 0 ~ " + (1 >> ServerId_Bit_Num));
}
if (epochDate != null) {
SnowFlake.Epoch = epochDate.getTime() / 1000;
} else {
SnowFlake.Epoch = Default_Epoch_Date;
}
SnowFlake.groupId = groupId;
SnowFlake.serverId = serverId;
}
public static synchronized long nextId() {
long currentTime = System.currentTimeMillis();
long timestamp = currentTime / 1000;
if (timestamp < lastTime) {
// 防止时钟回拨
if(lastTime - timestamp < 2) {
timestamp = lastTime;
} else {
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for {} s", lastTime - timestamp));
}
}
if (timestamp == lastTime) {
long newSequence = (sequence + 1) & Sequence_Mark_Flag;
if (newSequence == 0) {
timestamp = tilNextSecond(lastTime);
}
sequence = newSequence;
} else {
sequence = 0;
}
lastTime = timestamp;
return (groupId << GroupId_Bit_Shift)
| (serverId << ServerId_Bit_Shift)
| (sequence << Sequence_Bit_Shift)
| ((timestamp - Epoch) & Timestamp_Mark_Flag);
}
private static long tilNextSecond(long lastSecond) {
long timestampNow = System.currentTimeMillis() / 1000;
while (timestampNow == lastSecond) {
timestampNow = System.currentTimeMillis() / 1000;
}
if (timestampNow < lastSecond) {
throw new RuntimeException("Clock moved backwards");
}
return timestampNow;
}
}
到现在为止，有几个问题：
1.为什么将时间戳放在id的二进制的最后一部分，而不是sequence放在最后面，有什么区别？
2.代码中设置时间起始点epoch有什么用处？
3.上面的代码，如果发生了1秒的时钟回拨的情况，会发生什么？
4.在面对流量高峰的时候，频繁生成id会发生什么状况？
上面这段代码是按照一个开源的java工具包的实现来写的，来说一下我对上面这段代码的理解：
1.与原来的实现方式相比，将时间戳（而不是sequence）放在最后一部分，是因为每次进入下一秒的时候，sequence字段都会被重置为0，在流量并发没那么高的情况下，大多数生成的id的sequence部分都是1。当我们使用id去做散列的时候（比如id % 1024），这种情况下得到的结果大部分都是1，散列结果高度集中，通常容易导致一些意想不到的问题。因此把时间戳放在最末尾，生成的id往往具有更好的散列效果。
2.设置时间起始点epoch，是因为时间戳的字段的位数有限制，使得算法有效期为130年左右，从1974年开始计数的时间戳，到2106将超出32位的表示范围。在超出该时间范围之后，生成的id将有可能重复。而起始时间点的设置，可以将该算法的使用时间窗口范围从1974~2106改为2022~2158。
另外使用该算法的过程中，修改起始时间点将会导致生成的id重复。
3.时钟回拨了1s钟的时候，是代码允许的时钟回拨范围，但是tilNextSecond()方法依然会报错。
4.由于sequence长度限制的原因，在1秒的时间范围内最多只能生成2048个id。如果在1秒的时间内，快速消耗完了，那么接下来调用nextId()的线程将会进入轮询1秒的轮询中，而由于这个方法使用synchronized同步，其他调用nextId()的线程将进入阻塞状态。也就是说，在大流量、高并发的情况下，这个nextId()的方法有可能经常会导致线程集体阻塞。
针对sequence长度耗尽导致的阻塞问题,一个自然而然的解决办法就是增加sequence字段的长度。但是增加sequence长度，对应的就是需要减少时间戳的长度，而且在流量空闲的情况又会是一种浪费。
因此到这里就想设计了一种新的生成id的思路，代码如下：
private static long lastTime = System.currentTimeMillis() / 1000;
public static synchronized long nextId() {
long newSequence = (sequence + 1) & Sequence_Mark_Flag;
if (newSequence == 0) {
lastTime ++;
}
sequence = newSequence;
return (groupId << GroupId_Bit_Shift)
| (serverId << ServerId_Bit_Shift)
| (sequence << Sequence_Bit_Shift)
| ((lastTime - Epoch) & Timestamp_Mark_Flag);
}
原理很简单，使用进程启动时的时间作为时间戳，每次每个时间戳的序列耗尽的时候，才会使用下一个时间戳。这样，不需要考虑时钟回拨的问题，也不需要担心每秒钟生成的id超过限制时会阻塞线程。
但是很快就会发现问题，假如进程每秒生成的id远远超过2048个，那么lastTime字段会迅速增加而超过当前时间，如果这个时候服务器重启了，lastTime会被重新设置为当前时间，从而出现id重复的情况。
那么我们是不是可以在lastTime超过当前时间时，阻塞当前线程呢？代码如下：
private static long Time_Offset = 5;
public static synchronized long nextId() {
long newSequence = (sequence + 1) & Sequence_Mark_Flag;
if (newSequence == 0) {
lastTime ++;
long timestampSecond = System.currentTimeMillis() / 1000;
if (lastTime - timestampSecond > Time_Offset) {
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}
}
sequence = newSequence;
return (groupId << GroupId_Bit_Shift)
| (serverId << ServerId_Bit_Shift)
| (sequence << Sequence_Bit_Shift)
| ((lastTime - Epoch) & Timestamp_Mark_Flag);
}
每次sequence用完时，当检测到lastTime超过当前时间5秒的时候都会阻塞1秒。这样依然会存在sequence长度耗尽导致的阻塞的问题，但是有5 * 2048个id可以备用当作缓冲（5秒是服务器的重启时间最小值，从服务器关机到下一次服务重新启动成功之间的时间，这些时间戳的id也是可以利用的），而且在服务器流量低谷的时候，没有用到的时间戳的id，在流量高峰的时候可以尽数使用，相当于削峰填谷了。
当然，以上的设计只在频繁调用nextId()生成全局唯一id，从而很容易导致sequence用完的场景。不同的项目的实际应用场景不同，如果sequence字段长度足够长，且调用频率不是那么高，使用初版的生成方式就足够了。
总结
1.雪花算法生成id的每个字段的长度需要根据不同的业务去决定。
2.合理的设置起始时间点有助于判断有效时间是否全部耗尽。
3.使用该算法的过程中，修改起始时间点将会导致生成的id重复。
4.每秒生成的id数量与sequence字段有关, 超出时将阻塞线程直到进入下一秒
5.使用进程启动时的时间作为时间戳，每次每个时间戳的序列耗尽的时候，才使用下一个时间戳。并且每次sequence用完时，检测到lastTime超过当前时间5秒的时候都会阻塞一定时间的线程，可以一定程度上缓解阻塞频率。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
