引言
最近发现项目里主键id生成算法很短小精悍，遂深入看了下，还蛮有意思，在此分享一下，源码如下。
private static SpinLock mLock = new SpinLock();
private static volatile int rotateId = 0;
private static volatile long timeId = 0;
private static int nodeId = 0;
private static int rotateIdWidth = 15;
private static int rotateIdMask = 0x7FFF;
private static int nodeIdWidth = 6;
private static int nodeIdMask = 0x3F;
private static final long T201801010000 = 1514736000000L;
public static void setNodeId(int nodeId) {
MessageShardingUtil.nodeId = nodeId;
}
public static long generateId() throws Exception {
mLock.lock();
rotateId = (rotateId + 1)&rotateIdMask;
long id = System.currentTimeMillis() - T201801010000;
if (id > timeId) {
timeId = id;
rotateId = 1;
} else if(id == timeId) {
if (rotateId == (rotateIdMask - 1)) { //当前空间已经用完，等待下一个空间打开
while (id <= timeId) {
id = System.currentTimeMillis() - T201801010000;
}
mLock.unLock();
return generateId();
}
} else { //id < timeId;
if (rotateId > (rotateIdMask -1)*9/10) { //空间已经接近用完
if (timeId - id < 3000) { //时间回拨小于3秒，等待时间赶上回拨之前记录
while (id < timeId) {
id = System.currentTimeMillis() - T201801010000;
}
mLock.unLock();
return generateId();
} else { //时间回拨大于3秒，抛出异常，这段时间消息将不可用。
mLock.unLock();
throw new Exception("Time turn back " + (timeId - id) + " ms, it too long!!!");
}
} else {
id = timeId;
}
}
id <<= nodeIdWidth;
id += (nodeId & nodeIdMask);
id <<= rotateIdWidth;
id += rotateId;
mLock.unLock();
return id;
}
介绍
这个 ID 生成算法是一种基于 雪花算法 (Snowflake) 和 自定义时序生成策略 的设计方法，可以用于分布式系统中生成全局唯一且递增的 ID。算法结合了时间戳、机器节点 ID 和序列号，保证了生成的 ID 在分布式环境下的唯一性，并且能够高效地生成 ID（最大支持每毫秒32678个ID的生成）。
这个 ID 生成算法是一个 时序型（时间序列）算法，并在其基础上加入了自定义的 轮换序列（rotateId） 来处理同一毫秒内生成多个 ID 的问题。我们可以将其分为几个核心组成部分：
1. 时间戳（Timestamp）部分
- 时间戳部分（
timeId）是 ID 的前缀，表示 自 2018年1月1日以来的毫秒数。 - 时间戳能够保证生成的 ID 是递增的，且在大多数情况下会根据系统当前的时间进行自增。时间戳的设计基于一个固定的基准时间
T201801010000，减去该时间戳后，可以得到自 2018年1月1日以来的时间毫秒数。
2. 节点 ID（NodeId）部分
- 节点 ID 部分（
nodeId）是一个 6 位 的字段，最多支持 64 个节点。这个字段用于标识不同的服务器或实例。 - 节点 ID 的设计保证了在多节点环境下生成的 ID 不会冲突，每个节点生成的 ID 是唯一的。
3. 序列号（rotateId）部分
- 序列号部分（
rotateId）是一个 15 位 的字段，用于处理同一毫秒内生成多个 ID 的情况。每当一个节点在同一毫秒内生成多个 ID 时，rotateId会递增，以保证每个生成的 ID 唯一。 - 如果 同一毫秒内的 ID 已经生成完（即
rotateId达到最大值 32767），生成新的 ID 时会进行 等待下一毫秒 的操作，直到新的毫秒到来。
4. 锁机制
- 自旋锁（SpinLock）：为了确保在高并发环境下生成的 ID 是唯一的，并且避免多个线程同时生成 ID 时产生冲突，使用了自旋锁
SpinLock来保证同一时刻只有一个线程可以生成 ID。
5. ID 结构
生成的 ID 结构通常是这样的：
| 时间戳 (43 bits) | 节点 ID (6 bits) | 序列号 (15 bits) |
- 时间戳部分（43 位）：存储自 2018年1月1日以来的毫秒数，通常为高位。
- 节点 ID 部分（6 位）：标识生成 ID 的节点，最多支持 64 个节点。
- 序列号部分（15 位）：在同一毫秒内生成多个 ID 时，保证唯一性的递增序列。
6. 具体步骤分析
generateId() 方法的流程基本上遵循了以下步骤：
-
获取当前时间戳：通过
System.currentTimeMillis()获取当前的时间戳，然后减去T201801010000，得到自 2018年1月1日以来的毫秒数。 -
旋转 ID（rotateId）递增：每次调用
generateId()方法时，都会对rotateId进行递增，递增的过程是通过按位与（&）操作来实现的，确保它不会超过最大值（32767）。如果rotateId达到最大值，则进入等待下一毫秒的状态。 -
生成 ID：ID 的生成是将时间戳、节点 ID 和序列号组合起来，按顺序拼接成一个长整型数字。时间戳左移节点 ID 和序列号的位置，保证各部分不重叠。
-
处理时间回拨：如果时间回拨（即系统时间发生了倒退），会进行特殊处理。若时间差超过 3 秒，则抛出异常；若小于 3 秒，则会等待系统时间恢复。
7. 算法总结
这个 ID 生成算法的核心思想是：
- 使用时间戳来保证 ID 的递增性。
- 使用节点 ID 来保证分布式系统中不同节点生成的 ID 不会冲突。
- 使用旋转序列（
rotateId）来保证同一毫秒内生成多个 ID 时的唯一性。 - 利用自旋锁保证并发环境下 ID 生成的正确性。
这种算法设计类似于 雪花算法（Snowflake），但是它在实现上做了若干调整，主要体现在时间的基准点、节点 ID 的位宽、序列号的位宽等方面。因此，可以认为它是一种基于时间的 定制版雪花算法。
代码详解
generateId() 方法的每个 if 分支情况
1. 时间戳 id 大于 timeId
if (id > timeId) {
timeId = id;
rotateId = 1;
}
- 发生条件：当前生成的时间戳（
id）大于上次生成的时间戳（timeId）。 - 解释：这表示我们进入了一个新的毫秒时间段。每毫秒最多可以生成 32768 条消息，所以在每一毫秒内，
rotateId从 1 开始递增，直到达到最大值rotateIdMask。当时间变化到新的毫秒时，rotateId会被重置为 1，timeId更新为当前的时间戳。 - 例子：假设当前时间是 2025 年 1 月 1 日 12:00:01.123，而上次生成的 ID 是 2025 年 1 月 1 日 12:00:01.122，那么
id > timeId会成立，timeId会更新为当前时间。
2. 时间戳 id 等于 timeId，但 rotateId 达到最大值
else if (id == timeId) {
if (rotateId == (rotateIdMask - 1)) { // 当前空间已经用完，等待下一个空间打开
while (id <= timeId) {
id = System.currentTimeMillis() - T201801010000;
}
mLock.unLock();
return generateId();
}
}
- 发生条件：当前生成的时间戳
id和timeId相等，且当前rotateId已经到达最大值，即该毫秒内的消息 ID 已经用完。 - 解释：此时没有更多的 ID 可以生成，因此需要等待直到系统时间继续前进，产生下一个毫秒的时间戳。
rotateId到达最大值后，会重新从 1 开始。这个while循环会阻塞直到时间戳id大于timeId，即当前时间推移到下一个毫秒。这种情况意味着在某一毫秒内，已生成了 32768 条消息，需要等待下一个毫秒。 - 例子：假设
rotateId达到了最大值rotateIdMask - 1，并且id == timeId。这时候，就会进入阻塞，直到系统时间发生变化。
3. 时间戳 id 小于 timeId
else { // id < timeId
if (rotateId > (rotateIdMask - 1) * 9 / 10) { // 空间已经接近用完
if (timeId - id < 3000) { // 时间回拨小于3秒，等待时间赶上回拨之前记录
while (id < timeId) {
id = System.currentTimeMillis() - T201801010000;
}
mLock.unLock();
return generateId();
} else { // 时间回拨大于3秒，抛出异常，这段时间消息将不可用。
mLock.unLock();
throw new Exception("Time turn back " + (timeId - id) + " ms, it too long!!!");
}
} else {
id = timeId;
}
}
- 发生条件：当前生成的时间戳
id小于timeId，即时间回拨了。 - 解释：
- 如果
rotateId已接近最大值的 90%（即空间接近用尽），并且时间回拨小于 3 秒，那么系统会进入等待，直到当前时间大于或等于上次生成的时间戳timeId。这时 ID 会重新生成。 - 如果时间回拨超过 3 秒，则抛出异常，表示这段时间内生成的消息 ID 不再有效，因为时间回拨过长。
- 如果
- 例子：
- 假设
timeId是 1000 毫秒前的时间戳，而id当前时间戳小于timeId。如果回拨小于 3 秒，就会等待；如果超过 3 秒，则抛出异常。
- 假设
解释 ID 的组装
在 generateId() 方法中，ID 是由以下几个部分拼接而成的：时间戳、节点 ID 和轮换 ID。每个部分通过位移和按位与操作与其他部分合并。具体来说：
id <<= nodeIdWidth;
id += (nodeId & nodeIdMask);
id <<= rotateIdWidth;
id += rotateId;
1. id <<= nodeIdWidth;
id <<= nodeIdWidth;
- 含义：将当前的
id向左移动nodeIdWidth位。nodeIdWidth代表节点 ID 部分占用的位数。 - 作用：这个操作会将时间戳部分腾出足够的空间，以便存储节点 ID。左移之后，
id的低nodeIdWidth位被空出来，用来存储后续的节点 ID。
2. id += (nodeId & nodeIdMask);
id += (nodeId & nodeIdMask);
- 含义：将
nodeId（节点 ID）与nodeIdMask（节点 ID 的掩码）进行按位与操作，确保nodeId在允许的范围内。然后将该节点 ID 加到id中。 - 作用：此时节点 ID 被加入到
id中的低nodeIdWidth位。通过按位与操作，确保节点 ID 的范围不超过nodeIdMask设定的值。
3. id <<= rotateIdWidth;
id <<= rotateIdWidth;
- 含义：将当前的
id向左移动rotateIdWidth位。rotateIdWidth代表轮换 ID 部分占用的位数。 - 作用：这个操作将腾出空间以存储轮换 ID。
4. id += rotateId;
id += rotateId;
- 含义：将
rotateId加到id的低rotateIdWidth位。 - 作用：将轮换 ID 加入到最终的 ID 中。
总结
- ID 的组成：通过左移位操作，首先将时间戳、节点 ID 和轮换 ID 按照一定的顺序拼接成一个长整型 ID。
- 时间戳部分提供顺序性；
- 节点 ID 确保不同机器生成的 ID 不重复；
- 轮换 ID 确保同一毫秒内生成多个 ID 时不冲突。
通过位运算（左移和按位与）实现高效的 ID 组装。每一部分都有其特定的宽度（由 nodeIdWidth、rotateIdWidth 等变量控制），这使得 ID 的生成和解析非常高效且灵活。
最后
欢迎follow同名gzh:加瓦点灯， 每天推送干货知识，一起进步！
本文由mdnice多平台发布
标签：完必,算法,id,毫秒,timeId,解析,生成,ID,rotateId From： https://www.cnblogs.com/javadd/p/18678984