使用雪花算法生成分布式ID

Snowflake算法(雪花算法)是由Twitter提出的一个分布式全局唯一ID生成算法,该算法生成一个64bit大小的长整数。64bit位ID结构如下:

Snowflake-64bit

各bit位说明:

  • 1 位 不用

    生成的ID都是正整数,所以这个最高位即符号位固定是0。

  • 41 位 用来记录毫秒级别时间戳

    • 此时间戳是从某一刻算起的时间戳,单位是毫秒级
    • 41位可以表示2^41 - 1个数字(0除外), 支持约(2^41 - 1) / (1000 60 60 24 365)=69年
    • 时间戳保证了ID按时间趋势递增
  • 10 位 用来记录工作机器 ID

    • 10位包括5位DatacenterId和5位WorkId,一共可以部署2^10-1个节点, 由于DatacenterId和workId区分保证了整个分布式系统内不会产生重复
  • 12 位 用来序列号
    • 用来记录同一毫秒内产生的不同序号。最大支持2^12 - 1 = 4095个数字,来表示同一毫秒时间戳内产生的4095个ID序号

此算法关键需要记录上次生成ID的时间戳和序号,若当前时间戳和上次时间戳一至,则在当前毫秒内生成序号,否则重置序号为0:

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
<?php

class SnowflakeIdWorker
{
public function nextId()
{
$timestamp = $this->timeGen();
// 如果当前时间小于上一次ID生成的时间戳,说明系统时钟回退过这个时候应当抛出异常
if ($timestamp < $this->lastTimestamp) {
throw new RuntimeException(
sprintf("Clock moved backwards. Refusing to generate id for %d milliseconds", $this->lastTimestamp - $timestamp));
}

// 如果是同一时间生成的,则进行毫秒内序列
if ($this->lastTimestamp == $timestamp) {
$this->sequence = ($this->sequence + 1) & $this->sequenceMask;
// 毫秒内序列溢出
if ($this->sequence == 0) {
// 阻塞到下一个毫秒,获得新的时间戳
$timestamp = $this->tilNextMillis($this->lastTimestamp);
}
} else { // 时间戳改变,毫秒内序列重置
$this->sequence = 0;
}

// 记录上次生成ID的时间截
$this->lastTimestamp = $timestamp;

....
}

完整代码参考:SnowflakeIdWorker

更多