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

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

我的个人网站：http://riun.xyz

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

零、预备知识

1字节=8位

1byte = 8bit

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

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

0000000 00000000 00000000 00000000

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

1111111 11111111 11111111 11111111

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

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

一年约有 365*24*3600 = 31536000 ≈ 3154万秒（平年。闰年需再加一天）

一、大致思路

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

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

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

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

不含符号位时，二进制1111 1111表示28-1=255（20+21+22+…+2^7 = 28-1）。也就是说8个二进制位所能表示的最大数是28-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有序，随着时间趋势递增，则放在高位好。因为放在高位的话，随着时间流逝，后面的时间数值越来越大，高位数值大的最终得到的十进制数字也就越大，所以应该放在高位。

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

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

2^15= 32768

2^16= 65536

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

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

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

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

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

二、如何实现

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

long currentEpochSecond= System.currentTimeMillis() / 1000

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

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。使用或运算能够完整保留三部分中每个位置上的数字信息。

三、源码

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

廖雪峰老师的源码不止有上述写的那些东西。还有当1秒内生成的id超过6.5万时向后借下一秒的id来用的处理；还有最后并没有使用当前秒级时间戳，而是当前秒级时间戳减去2000.1.1到1970.1.1的秒数，以此来减小不必要的二进制位的使用，进一步减少内存占用（系统使用生成id的服务时，需要在2000.1.1之后上线）；还有时针回拨问题，原文的首评说的很正确：保障了程序运行时间回拨，并没有解决停机时间回拨问题。停机时服务已经停止，内存中记录的lastEpoch 也就丢失，所以停机时针回拨后仍有可能出现重复id（回拨时间>重启服务时间时）。由于不是主线，我就没有在上文中介绍，可以看下面源码结合注释思考一下。

【全部】廖雪峰老师的源码：IdUtil.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;


public final class IdUtil {

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

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

	
	private static final long OFFSET = LocalDate.of(2000, 1, 1).atStartOfDay(ZoneId.of("Z")).toEpochSecond();

	
	private static final long MAX_NEXT = 0b11111_11111111_111L;

	
	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;
	}

}

测试：

public static void main(String[] args) {
    //生成一百万个唯一id大概需要25ms
    System.out.println(IdUtil.nextId());
    //1452736581206048
    //Set 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生成器
细聊分布式ID生成方法

篇外：

1111 1111

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

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

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5672382.html

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

发表评论

评论列表（0条）