对《分布式唯一ID生成器》的解读

本文是对廖雪峰老师[分布式唯一ID生成器](https://www.liaoxuefeng.com/article/1280526512029729)的解读，因为我第一次读这篇文章时没有读懂，后来结合很多其他文章慢慢的才搞懂所谓的“使用bit储存什么信息“，”在哪些位上储存“，这些话的意思。所以我想要用另外一些尽量简单明了的话语去解释这些东西，相当于耳边辅导一样。读本文之前建议先通读一遍廖雪峰老师的文章。

### 零、预备知识

1字节=8位

1byte = 8bit

java中int类型是4byte，也就是32bit
00000000 00000000 00000000 00000000

正数的二进制最高位必须是0，所以，若想表达正数，32个二进制只能使用后面的31个：

0000000 00000000 00000000 00000000

所以能够表达的最大正数情况就是后31位全为1：

01111111 11111111 11111111 11111111

结果是2^30+2^29+...+2^2+2^1+2^0 = 2^31-1。所以，在不考虑符号位时，31bit能表示的最大正整数是 2^31-1。

java中long类型是8byte，也就是64bit

一年约有 365\*24\*3600 = 31536000 ≈ 3154万秒（平年。[闰年](https://baike.baidu.com/item/%E9%97%B0%E5%B9%B4/27098)需再加一天）

### 一、大致思路

1、我们肯定使用long类型储存唯一id，因为int类型能使用的只有31位，太少了。

使用Long类型时，我们使用后53位，那么前面的更高位都是0，所以最后表示出的数字肯定是正数。

![](http://minio.riun.xyz/riun1/2021-12-13_1HnAxIGTn1ORrdtWJA.jpg)

接下来考虑这53位如何使用。

分布式唯一Id的组成肯定有时间戳，当前时间戳是当前时间距离1970.1.1的毫秒数。为了节约空间，我们使用秒级时间戳，也就是取当前时间到1970.1.1的秒数。如果我们的id生成器想要一直可用达到100年，那么至少要能够表示 100*31536000 = 3153600000秒，也就是要能够储存3153600000（31亿）这么大的数字。

不含符号位时，二进制1111 1111表示2^8-1=255（2^0+2^1+2^2+...+2^7 = 2^8-1）。也就是说8个二进制位所能表示的最大数是2^8-1。

则：

2^31 = 2147483648，31bit表示的最大数是2^31-1=2147483647

2^32 = 4294967296，32bit表示的最大数是2^32-1=4294967295

所以，想要储存3153600000，至少需要32个2进制位。

再来看下32bit能表示的秒数时间具体是多少：4294967295 / 31536000 =  136.19251950152 。大约能表示136年。

1970+136=2106。所以如果使用32bit储存秒级时间戳，至少能够表示到2106年，这个数字对于目前来说已经足够了。

这里还要考虑下，时间戳是放在高位好，还是低位好？

如果想要让生成的id有序，随着时间趋势递增，则放在高位好。因为放在高位的话，随着时间流逝，后面的时间数值越来越大，高位数值大的最终得到的十进制数字也就越大，所以应该放在高位。

![](http://minio.riun.xyz/riun1/2021-12-13_1Hp6pcaY7G3tsHtf9P.jpg)

2、有了秒级时间戳，不同秒生成的id一定不同，所以就只需要考虑同一秒内生成的id了。

同一秒内生成的不同id我们可以使用一个自增序列区分他们。就是一个自增数字，1，2，3，4，5...。我们把这个东西叫做序列号。

2^15= 32768

2^16= 65536

如果我们使用16个2进制位来区分同一秒内的不同请求，那么至少可以表示65536个。也就是说使用16bit储存序列号，则可以在1秒内至少能生成6.5万个不同id。

这对很多业务来说够用，也可以根据具体情况调整。

![](http://minio.riun.xyz/riun1/2021-12-13_1HroQNFeJX6jG2SaIY.jpg)

3、现在，1秒内可以生成6.5万个不同id了。那还有什么别的吗？服务器。为提升服务处理能力，我们一个服务是部署在多台机器上的，在同一秒内，多台机器上生成的id可能相同（秒数相同，又刚好拿到同样的序列号）。如何保证多台机器上生成的id不一样呢？

这就需要再引入机器标识，假如使用5bit储存机器标识，这样不同机器上的标识位不同，也就不怕他们拿到同样的序列号了；同一个机器上同一秒内序列号自增从1到6.5万，也不会相同。

5个2进制位的话，最多能表示2^5=32台不同机器。也就是说可以有32台机器同时在生成id。这个数值也可以根据业务情况调整。

![](http://minio.riun.xyz/riun1/2021-12-13_1Hroxlwnx7DSP8fJjE.jpg)

### 二、如何实现

1、使用java的System.currentTimeMillis()可获取当前时间戳，只不过得到的是毫秒为单位，我们想要得到秒级时间戳，只需/1000即可。

`long currentEpochSecond= System.currentTimeMillis() / 1000`

2、得到秒级时间戳后，使用static变量作为自增位。使用变量记录上一生成id时的秒数，如果和当前秒数不相等，则重置自增位为0；相等，则表示是同一秒内的请求，则自增位加1。

```java
static long offset = 0;

if (lastEpoch != currentEpochSecond) {
    lastEpoch = currentEpochSecond;
    //重置自增序列号
    reset();
}

//自增
offset++;

private static void reset() {
    offset = 0;
}
```

3、获取当前机器码，根据规则映射成[0,31]之间的数字。

`private static final long SHARD_ID = getServerIdAsLong();`

4、将以上三部分按照二进制拼接起来：

假设第一部分是秒级时间戳currentEpochSecond，第二部分是自增序列号next，第三部分是机器码shardId。

根据前面的分析，第二三部分共占16+5=21位，而时间戳要放在最高位，所以将时间戳向左移动21位；自增序列号次之，所以将自增序列号向左移动5位；机器码原位不动。

`return (currentEpochSecond << 21) | (next << 5) | shardId;`

位移运算是位运算，位运算之后为保留三部分信息，所以将其进行或运算|。或运算|规则是：当前位置上有一个为1则结果为1，均不是1则为0。使用或运算能够完整保留三部分中每个位置上的数字信息。

![](http://minio.riun.xyz/riun1/2021-12-13_1HrNPnMjkinPHAKVra.jpg)

#### 时间回拨问题

还有时针回拨问题，原文的首评说的很正确：保障了程序运行时间回拨，并没有解决停机时间回拨问题。

时间回拨分为程序运行时的回拨和程序非运行状态下的回拨。

1、程序运行时的时间回拨比较好解决，也有很多解决方案如多时钟（用几个2进制位标识当前使用的始终，发现回拨则换一个时钟）、采用之前最大时间等。程序在运行，内存中的记录像lastEpoch、offset这些都还在，无非就是当前时间变成了之前的某一时间。廖老师用的是“采用之前最大时间”的解决方案：

```java
		if (epochSecond < lastEpoch) {
            // warning: clock is turn back:
            //logger.warn("clock is back: " + epochSecond + " from previous:" + lastEpoch);
            epochSecond = lastEpoch;
        }
```

`if (epochSecond < lastEpoch) `就是当前时间比之前的时间还小，那就是发现时间回拨了，那么就取之前最大的时间作为当前时间，继续在之前的时间上自增。这样就不会出现重复问题。

2、程序非运行状态下的时间回拨一般是程序重启，或中断时（服务挂掉），刚好进行时间回拨，服务器时间回到了从前。这种情况由于服务挂掉，内存中的lastEpoch、offset这些数据都没有了，服务再次启动时，即使发现`if (epochSecond < lastEpoch) `，那么offset也是从0开始自增，而当前时间位又是之前用过的，那必然会出现重复问题。要解决这种情况，必须使用后本地磁盘+多时钟。本地磁盘保存时钟ID，每次启动服务时获取时钟ID，如果发现时间回拨了，则时钟ID+1：

![](https://minio.riun.xyz/riun1/2023-02-20_2VUwfm7OOJmlzj8gB2.jpg)

比如最初时钟ID是0，服务正常运行一段时间。然后突然服务重启，此时不巧服务器时间回拨，服务启动时加载磁盘时钟ID是0，然后发现时间回拨了，那么时钟ID+1，则使用的时钟ID是1，这时即使内存中的lastEpoch、offset都不存在，也不会也之前产生的ID重复。

运行一段时间后，某天服务正在运行，时间回拨了，这时使用的时钟ID就是2了。时钟ID要异步的被写入本地磁盘。

### 三、源码

为了加快生成时间，我把无用的log日志打印全部去掉了。为了尽可能独立简洁，我把不必要的方法去掉了，保证只要这一个类就能够使用。

廖雪峰老师的源码不止有上述写的那些东西。还有当1秒内生成的id超过6.5万时向后借下一秒的id来用的处理；还有最后并没有使用当前秒级时间戳，而是当前秒级时间戳减去2000.1.1到1970.1.1的秒数，以此来减小不必要的二进制位的使用，进一步减少内存占用（系统使用生成id的服务时，需要在2000.1.1之后上线）。

【全部】廖雪峰老师的源码：[IdUtil.java](https://github.com/michaelliao/itranswarp/blob/master/src/main/java/com/itranswarp/util/IdUtil.java)

【删减】我更改和加注释之后的源码：

```java
package com.example.demo.utils;

//import org.slf4j.Logger;
//import org.slf4j.LoggerFactory;

import java.net.InetAddress;
import java.net.UnknownHostException;
import java.time.LocalDate;
import java.time.ZoneId;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * 53 bits unique id:
 *
 * |--------|--------|--------|--------|--------|--------|--------|--------|
 * |00000000|00011111|11111111|11111111|11111111|11111111|11111111|11111111|
 * |--------|---xxxxx|xxxxxxxx|xxxxxxxx|xxxxxxxx|xxx-----|--------|--------|
 * |--------|--------|--------|--------|--------|---xxxxx|xxxxxxxx|xxx-----|
 * |--------|--------|--------|--------|--------|--------|--------|---xxxxx|
 *
 * Maximum ID = 11111_11111111_11111111_11111111_11111111_11111111_11111111
 *
 * Maximum TS = 11111_11111111_11111111_11111111_111
 *
 * Maximum NT = ----- -------- -------- -------- ---11111_11111111_111 = 65535
 *
 * Maximum SH = ----- -------- -------- -------- -------- -------- ---11111 = 31
 *
 * It can generate 64k unique id per IP and up to 2106-02-07T06:28:15Z.
 */
public final class IdUtil {

//private static final Logger logger = LoggerFactory.getLogger(IdUtil.class);

private static final Pattern PATTERN_HOSTNAME = Pattern.compile("^.*\\D+([0-9]+)$");

/**
	 * 1970.1.1 到 2000.1.1 的秒数
	 */
	private static final long OFFSET = LocalDate.of(2000, 1, 1).atStartOfDay(ZoneId.of("Z")).toEpochSecond();

/**
	 * 2的16次方-1  65535
	 */
	private static final long MAX_NEXT = 0b11111_11111111_111L;

/**
	 * 当前机器码，只允许返回0~31，共能标识32个数，所以占用5bit（2^5=32）
	 */
	private static final long SHARD_ID = getServerIdAsLong();

/**
	 * 自增位
	 */
	private static long offset = 0;

/**
	 * 上次生成时的秒级时间戳
	 */
	private static long lastEpoch = 0;

public static long nextId() {
		return nextId(System.currentTimeMillis() / 1000);
	}

private static synchronized long nextId(long epochSecond) {
		if (epochSecond < lastEpoch) {
			// warning: clock is turn back:
			//logger.warn("clock is back: " + epochSecond + " from previous:" + lastEpoch);
			epochSecond = lastEpoch;
		}
		//不是同一秒的请求
		if (lastEpoch != epochSecond) {
			//记录lastEpoch
			lastEpoch = epochSecond;
			//重置自增位offset
			reset();
		}
		//自增位自增
		offset++;
		//确保自增序列号在[1,65535]之间
		long next = offset & MAX_NEXT;
		if (next == 0) {
			//当在同一秒内，offset自增到65536，则 65536 & 65535 = 0，就不再在当前秒内自增，使用下一秒的自增序列号
			//（使用下一秒调用nextId()，那么秒级时间戳就是下一秒，自增序列就从下一秒的1开始） 我理解这是向后借下一个秒级时间戳的6.5万个序列号
			//logger.warn("maximum id reached in 1 second in epoch: " + epochSecond);
			return nextId(epochSecond + 1);
		}
		//每部分各自位移到自己的位置，然后做或运算
		return generateId(epochSecond, next, SHARD_ID);
	}

private static void reset() {
		offset = 0;
	}

private static long generateId(long epochSecond, long next, long shardId) {
		return ((epochSecond - OFFSET) << 21) | (next << 5) | shardId;
	}

private static long getServerIdAsLong() {
		try {
			String hostname = InetAddress.getLocalHost().getHostName();
			Matcher matcher = PATTERN_HOSTNAME.matcher(hostname);
			if (matcher.matches()) {
				long n = Long.parseLong(matcher.group(1));
				if (n >= 0 && n < 32) {
					//logger.info("detect server id from host name {}: {}.", hostname, n);
					return n;
				}
			}
		} catch (UnknownHostException e) {
			//logger.warn("unable to get host name. set server id = 0.");
		}
		return 0;
	}

}
```

测试：

```java
public static void main(String[] args) {
    //生成一百万个唯一id大概需要25ms
    System.out.println(IdUtil.nextId());
    //1452736581206048
    //Set<Long> set = new HashSet<>(1500000);
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < 1000000; i++) {
        long l = IdUtil.nextId();
        //set.add(l);
    }
    long endTime = System.currentTimeMillis();
    System.out.println(endTime - startTime);
    //System.out.println(set.size());
}
```

### 四、总结

总述：唯一id，纯数字，long型，可安全传给前端展示

组成：32bit秒级时间戳+16bit自增数字+5bit机器码

速度： 生成1000000（一百万）个平均需要25毫秒。

优点：

- 1、虽然加了锁，但是生成效率极高，速度极快（因为大多数情况下都只做了几步简单的数字运算，没有循环）。

- 2、生成的id占用空间少，利于储存和传输（且53位的long刚好够前端完全精度展示）。

- 3、由于是趋势递增的数字，更便于做索引。

缺点：

- 1、由于没有全局时钟，若每台服务器的时间不是完全一致，则生成的 id 不是绝对递增的，而是“趋势递增”（同一时刻，有的服务器时间早，有的时间晚。那么这一时刻不同服务器生成的时间戳就不一样，那么他们生成的id就会有的大有的小，但是由于时间是递增的，所以呈现趋势递增的特征。有小下降的上升折线图）

- 2、每次跨秒时，自增序列号offset都会归零，这样序列号为0的id比较多。如果我们使用这些id做分库分表时的取模依据，就会导致取模后分布不均匀。（这个没太理解，为什么序列号为0的多？“跨秒”的时刻，只是一刻，不是应该和其他“时刻”一样吗？对请求来说遇到这些时刻的机会应该是一样多的吧）

### 五、参考

- [分布式唯一ID生成器](https://www.liaoxuefeng.com/article/1280526512029729)

- [细聊分布式ID生成方法](https://mp.weixin.qq.com/s?__biz=MjM5ODYxMDA5OQ==&mid=403837240&idx=1&sn=ae9f2bf0cc5b0f68f9a2213485313127&scene=21#wechat_redirect)

- [多时钟解决雪花算法的时间回拨问题](https://www.modb.pro/db/427994)

### 篇外：

1111 1111

（不含符号位时）8个二进制位能表达的最大数值是2^8-1=255，但能表达2^8=256个不同数字。

相差的1，从数学角度来说，是因为有0的存在；又因为0也是一个数，所以才能表达比其最大数值本身多1的个数。

对《分布式唯一ID生成器》的解读

文章目录

发表评论