最近我需要为运行的分布式系统某部分模块构造系统唯一的ID, 而 ID 需要是数字的形式，并应该尽量的短。不得不说，这是一个有趣的问题
1 若干实现策略#
查阅完相关的资料，发现为分布式系统生成唯一 ID 方法挺多的，例如：
- UUID
- 使用一个 ticket server, 即中央的服务器，各个节点都从中央服务器取 ID
- Twitter 的 Snowflake 算法
- Boundary 的 flake 算法
其中 UUID 生成的 ID 是字符串＋数字，不适用； ticket server 的做法略麻烦，笔者
并不想为了个 ID 还要去访问中央服务器；剩下就是 Snowflake 和 flake 算法，
flake 算法生成的是 128 位的 ID, 略长；所以最后笔者选择了 Snowflake 算法。
2 Snowflake 算法实现#
本来 Twitter 的算法是有相应实现的，不过后来删除了；笔者就只好自己卷起袖子自己 实现了:(
虽说 Twitter 没有了相应的实现，但是 Snowflake 算法原理很简单，实现起来并不难.
2.1 Snowflake 算法#
Snowflake 算法生成 64 位的 ID, ID 的格式是 41 位的时间戳 + 10 位的截断的 mac 地址 + 12 位递增序列：
1
2
3
4
| """id format =>
timestamp | machineId|sequence
41 | 10 |12
"""
|
2.2 Snowflake 实现#
2.2.1 生成时间戳#
Java 内置了生成精确到毫秒的时间戳的方法，非常便利：
1
| long timestamp = System.currentTimeMillis();
|
2.2.2 生成递增序列#
12 bits 的最大值是 2**12=4096, 所以生成递增序列也非常简单：
1
2
3
4
5
6
7
| private final long sequenceMax = 4096; //2**12
private volatile long sequence = 0L;
public void generateId(){
//do something
sequence = (sequence + 1) % sequenceMax;
//do something
}
|
2.2.3 获取 Mac 地址#
我们通过获取当前机器的 IP 地址以获取对应的物理地址：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| protected long getMachineId() throws GetHardwareIdFailedException {
try {
InetAddress ip = InetAddress.getLocalHost();
NetworkInterface network = NetworkInterface.getByInetAddress(ip);
long id;
if (network == null) {
id = 1;
} else {
byte[] mac = network.getHardwareAddress();
id =
((0x000000FF & (long) mac[mac.length - 1]) |
(0x0000FF00 & (((long) mac[mac.length - 2]) << 8))) >> 6;
}
return id;
} catch (SocketException e) {
throw new GetHardwareIdFailedException(e);
} catch (UnknownHostException e) {
throw new GetHardwareIdFailedException(e);
}
}
|
又因为 Mac 地址是6 个字节 (48 bits)，而需要的只是 10 bit, 所以需要取最低位的 2个字节 (16 bits)，然后右移 6 bits 以获取 10 个 bits 的 Mac地址
2.3 Snowflake 完整代码#
下面是 Snowflake 的 Java 实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
| public class IdGenerator {
// id format =>
// timestamp |datacenter | sequence
// 41 |10 | 12
private final long sequenceBits = 12;
private final long machineIdBits = 10L;
private final long MaxMachineId = -1L ^ (-1L << machineIdBits);
private final long machineIdShift = sequenceBits;
private final long timestampLeftShift = sequenceBits + machineIdBits;
private static final Object lock=new Object();
private final long twepoch = 1288834974657L;
private final long machineId;
private final long sequenceMax = 4096; //2**12
private volatile long lastTimestamp = -1L;
private volatile long sequence = 0L;
private static volatile IdGenerator instance;
public static IdGenerator getInstance() throws Exception {
IdGenerator generator=instance;
if (instance == null) {
synchronized(lock){
generator=instance;
if(generator==null){
generator=new IdGenerator();
instance=generator;
}
}
}
return generator;
}
private IdGenerator() throws Exception {
machineId = getMachineId();
if (machineId > MaxMachineId || machineId < 0) {
throw new Exception("machineId > MaxMachineId");
}
}
public synchronized Long generateLongId() throws Exception {
long timestamp = System.currentTimeMillis();
if (timestamp < lastTimestamp) {
throw new Exception(
"Clock moved backwards. Refusing to generate id for " + (
lastTimestamp - timestamp) + " milliseconds.");
}
if (lastTimestamp == timestamp) {
sequence = (sequence + 1) % sequenceMax;
if (sequence == 0) {
timestamp = tillNextMillis(lastTimestamp);
}
} else {
sequence = 0;
}
lastTimestamp = timestamp;
Long id = ((timestamp - twepoch) << timestampLeftShift) |
(machineId << machineIdShift) |
sequence;
return id;
}
protected long tillNextMillis(long lastTimestamp) {
long timestamp = System.currentTimeMillis();
while (timestamp <= lastTimestamp) {
timestamp = System.currentTimeMillis();
}
return timestamp;
}
protected long getMachineId() throws GetHardwareIdFailedException {
try {
InetAddress ip = InetAddress.getLocalHost();
NetworkInterface network = NetworkInterface.getByInetAddress(ip);
long id;
if (network == null) {
id = 1;
} else {
byte[] mac = network.getHardwareAddress();
id =
((0x000000FF & (long) mac[mac.length - 1]) |
(0x0000FF00 & (((long) mac[mac.length - 2]) << 8))) >> 6;
}
return id;
} catch (SocketException e) {
throw new GetHardwareIdFailedException(e);
} catch (UnknownHostException e) {
throw new GetHardwareIdFailedException(e);
}
}
}
|
正如笔者所言，算法并不难，就是分别获取时间戳， mac 地址，和递增序列号，然后移位得到 ID. 但是在具体的实现中还是有一些需要注意的细节的。
2.3.1 线程同步#
因为算法中使用到递增的序列号来生成 ID,而在实际的开发或者生产环境中很可能不止一个线程在使用 IdGenerator 这个类，如果这样就很容易出现不同线程的竞争问题，所以我使用了单例模式来生成 ID, 一方面更符合生成器的设计，另一方面因为对生成 ID的方法进行了同步，就保证了不会出现竞争问题。
2.3.2 同一毫秒生成多个 ID#
因为序列号长度是 12个 bit, 那么序列号最大值就是2**12=4096了，此外时间戳是精确到毫秒的，这就是意味着，当一毫秒内，产生超过 4096 个 ID 的时候就会出现重复的ID.
这样的情况并不是不可能发生，所以要对此进行处理；所以在 generateId() 函数中：
1
2
3
4
5
6
| if (lastTimestamp == timestamp) {
sequence = (sequence + 1) % sequenceMax;
if (sequence == 0) {
timestamp = tillNextMillis(lastTimestamp);
}
}
|
有以上的一段代码。当现在的时间戳与之前的时间戳一致，那么就意味着还是同一毫秒，如果序列号为 0, 就说明已经产生了 4096 个 ID了，继续产生 ID,就会出现重复 ID, 所以要等待一毫秒，这个就是 tillNextMills() 函数的作用了。
3 小结#
算法虽然简单，但是在找到 Snowflake 算法之前，笔者尝试了挺多的算法，但是都是因为不符合要求而被一一否决， 而 Snowflake 算法虽然简单，但是胜在实用。最后附上我写的 snowflake 算法的 Python 实现： Snowfloke