分布式系统中的ID生成

问题

在分布式系统中常遇到ID生成问题:

  • 场景1,在分库分表中需要保证某类ID唯一,这样使用主键自增的策略就不再合适
  • 场景2,需要某类ID需要具有同一特性来标识

诸如此类。

方案

有很多解决方案,比如

  1. 基于数据库主键自增策略(及其变种,如分片生成以提高效率、分库分表生成以解决单点问题等)
  2. UUID(简单但比较丑陋,生成的ID无规律,也有方案是基于UUID,但更简短
  3. 基于MongoDB的id策略
  4. DIY的ID(以不同用途的字符组装到一起,然后做编码转换以满足需要)

这里介绍一种方案4的实现,基本思想源于twitter的Snowflake方案,该实现可提供高性能、低延迟、高可用的ID生成。

每个ID是一个long类型的整数,结构如下:

1
2
3
4
0           41     51          64
+-----------+------+------------+

|timestamp |node |increment |
+-----------+------+------------+

前42位是timestamp,这样可以使ID生成变得有序。以中间10位标识节点,这样可以有1024个节点。最后12位为了解决并发冲突问题,并发请求时以此12位作累加,这样在同一个前42位内最多可以生成2的12次方个ID。

通过以上方案,可以快速生成时间有序的,带节点标识的ID。基于这个思想,我们可以做各种变形以满足自身需要,比如可以调整这三部分的顺序和每一部分的位数以满足具体场景;可以开启多个进程,每个进程负责某些node节点的ID生成以避免单点;可以精简位数,并做编码转换以减少ID长度等等。

【问题】 该方案严重依赖于系统时间,如果系统时钟发生错误,生成的ID就可能有问题。

代码实现

按照以上描述的策略的基本代码实现可参看:

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
/**
* 42位的时间前缀+10位的节点标识+12位的sequence避免并发的数字(12位不够用时强制得到新的时间前缀)
* <p>
* <b>对系统时间的依赖性非常强,需要关闭ntp的时间同步功能,或者当检测到ntp时间调整后,拒绝分配id。
*
* @author sumory.wu
* @date 2012-2-26 下午6:40:28
*/

public class IdWorker {
private final static Logger logger = LoggerFactory.getLogger(IdWorker.class);

private final long workerId;
private final long snsEpoch = 1330328109047L;// 起始标记点,作为基准
private long sequence = 0L;// 0,并发控制
private final long workerIdBits = 10L;// 只允许workid的范围为:0-1023
private final long maxWorkerId = -1L ^ -1L << this.workerIdBits;// 1023,1111111111,10位
private final long sequenceBits = 12L;// sequence值控制在0-4095

private final long workerIdShift = this.sequenceBits;// 12
private final long timestampLeftShift = this.sequenceBits + this.workerIdBits;// 22
private final long sequenceMask = -1L ^ -1L << this.sequenceBits;// 4095,111111111111,12位

private long lastTimestamp = -1L;

public IdWorker(long workerId) {
super();
if (workerId > this.maxWorkerId || workerId < 0) {// workid < 1024[10位:2的10次方]
throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", this.maxWorkerId));
}
this.workerId = workerId;
}

public synchronized long nextId() throws Exception {
long timestamp = this.timeGen();
if (this.lastTimestamp == timestamp) {// 如果上一个timestamp与新产生的相等,则sequence加一(0-4095循环),下次再使用时sequence是新值
//System.out.println("lastTimeStamp:" + lastTimestamp);
this.sequence = this.sequence + 1 & this.sequenceMask;
if (this.sequence == 0) {
timestamp = this.tilNextMillis(this.lastTimestamp);// 重新生成timestamp
}
}
else {
this.sequence = 0;
}
if (timestamp < this.lastTimestamp) {
logger.error(String.format("Clock moved backwards.Refusing to generate id for %d milliseconds", (this.lastTimestamp - timestamp)));
throw new Exception(String.format("Clock moved backwards.Refusing to generate id for %d milliseconds", (this.lastTimestamp - timestamp)));
}

this.lastTimestamp = timestamp;
// 生成的timestamp
return timestamp - this.snsEpoch << this.timestampLeftShift | this.workerId << this.workerIdShift | this.sequence;
}

/**
* 保证返回的毫秒数在参数之后
*
* @param lastTimestamp
* @return
*/

private long tilNextMillis(long lastTimestamp) {
long timestamp = this.timeGen();
while (timestamp <= lastTimestamp) {
timestamp = this.timeGen();
}
return timestamp;
}

/**
* 获得系统当前毫秒数
*
* @return
*/

private long timeGen() {
return System.currentTimeMillis();
}

public static void main(String[] args) throws Exception {
IdWorker iw1 = new IdWorker(1);

for (int i = 0; i < 10; i++) {
System.out.println(iw1.nextId());
}
}
}

实际应用

一个用于处理分布式系统中ID生成,唯一性字段值管理的通用模块UC