keep coding
0%

snowflake-雪花算法

发表于 更新于 分类于 Disqus：
本文字数： 4.5k 阅读时长 ≈ 4 分钟

Snowflake 算法介绍
Snowflake 是由 Twitter 提出的一个分布式全局唯一 ID 生成算法，算法生成 ID 的结果是一个 64bit 大小的长整，标准算法下它的结构如下图：

1 位，不用。
二进制中最高位为符号位，我们生成的 ID 一般都是正整数，所以这个最高位固定是 0。
41 位，用来记录时间戳（毫秒）。
41 位 可以表示 2^41 - 1 个数字。
也就是说 41 位 可以表示 2^41 - 1 个毫秒的值，转化成单位年则是 (2^41 - 1) / (1000 * 60 * 60 * 24 * 365) 约为 69 年。
10 位，用来记录工作机器 ID。
可以部署在 2^10 共 1024 个节点，包括 5 位 DatacenterId 和 5 位 WorkerId。
12 位，序列号，用来记录同毫秒内产生的不同 id。
12 位 可以表示的最大正整数是 2^12 - 1 共 4095 个数字，来表示同一机器同一时间截（毫秒)内产生的 4095 个 ID 序号。
Snowflake 可以保证：
所有生成的 ID 按时间趋势递增。
整个分布式系统内不会产生重复 ID（因为有 DatacenterId (5 bits) 和 WorkerId (5 bits) 来做区分）。

算法的PHP实现：

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
<?php

/**
 * Class IdWorker snowflake算法生成unique id
 * @package Snowflake
 */
class Snowflake
{
    //开始时间
    const EPOCH_OFFSET = 1293811200000;
    //首位
    const SIGN_BITS = 1;
    //时间戳相减占用的位数
    const TIMESTAMP_BITS = 41;
    //数据中心位数
    const DATA_CENTER_BITS = 5;
    //机器位数
    const MACHINE_ID_BITS = 5;
    //同一毫秒内自增的位数
    const SEQUENCE_BITS = 12;

    /**
     * @var mixed
     */
    protected $dataCenterId;

    /**
     * @var mixed
     */
    protected $machineId;

    /**
     * @var null|int
     */
    protected $lastTimestamp = null;


    /**
     * @var int
     */
    protected $sequence = 1;

    //标志位需要位移的长度
    protected $signLeftShift = self::TIMESTAMP_BITS + self::DATA_CENTER_BITS + self::MACHINE_ID_BITS + self::SEQUENCE_BITS;
    //时间差值需要位移的长度
    protected $timestampLeftShift = self::DATA_CENTER_BITS + self::MACHINE_ID_BITS + self::SEQUENCE_BITS;
    //数据中心需要位移的长度
    protected $dataCenterLeftShift = self::MACHINE_ID_BITS + self::SEQUENCE_BITS;
    //机器需要位移的长度
    protected $machineLeftShift = self::SEQUENCE_BITS;
    //最大自增数
    //下边语法执行效果 等于 (1 << 12) - 1;
    //-1 << self::SEQUENCE_BITS = 1111111111111111111111111111111111111111111111111111000000000000
    protected $maxSequenceId   = ~ (-1 << self::SEQUENCE_BITS);
    //最大机器数
    protected $maxMachineId    = ~ (-1 << self::MACHINE_ID_BITS);
    //最大数据中心机器数
    protected $maxDataCenterId = ~ (-1 << self::DATA_CENTER_BITS);

    /**
     * IdWorker constructor.
     * @param $dataCenter_id
     * @param $machine_id
     * @throws Exception
     */
    public function __construct($dataCenter_id, $machine_id)
    {
        if ($dataCenter_id > $this->maxDataCenterId) {
            throw new \Exception('data center id should between 0 and ' . $this->maxDataCenterId);
        }
        if ($machine_id > $this->maxMachineId) {
            throw new \Exception('machine id should between 0 and ' . $this->maxMachineId);
        }
        $this->dataCenterId = $dataCenter_id;
        $this->machineId = $machine_id;
    }

    /**
     * @return string
     * @throws Exception
     */
    public function id()
    {
        $sign = 0;
        $timestamp = $this->getUnixTimestamp();
        if ($timestamp < $this->lastTimestamp) {
            throw new \Exception('Clock moved backwards!');
        }
        if ($this->lastTimestamp == $timestamp) {
            $this->sequence++;
            if ($this->sequence > $this->maxSequenceId) {
               return $this->id();
            }
        } else {
            $this->sequence = 1;
        }
        $this->lastTimestamp = $timestamp;
        //算出时间差值
        $time = (int)($timestamp - self::EPOCH_OFFSET);

        //($sign << $this->signLeftShift) =》  1 左移 63 位 : 1000000000000000000000000000000000000000000000000000000000000000
        //($time << $this->timestampLeftShift) 时间左移 22 位
        // ($this->dataCenterId << $this->dataCenterLeftShift) 数据中心 左移 17位
        // ($this->machineId << $this->machineLeftShift) 机器中心左移 12 位
        $id = ($sign << $this->signLeftShift) | ($time << $this->timestampLeftShift) | ($this->dataCenterId << $this->dataCenterLeftShift) | ($this->machineId << $this->machineLeftShift) | $this->sequence;
        return (string)$id;
    }

    /**
     * 解析自增ID
     * @param $id
     * @return array
     */
    public function parse($id)
    {
        //转化为二进制字符串
        $binUuid = decbin($id);
        $len = strlen($binUuid);
        $sequenceStart = $len - self::SEQUENCE_BITS;
        //截取自增的二进制字符串
        $sequence = substr($binUuid, $sequenceStart, self::SEQUENCE_BITS);

        $machineIdStart = $len - self::MACHINE_ID_BITS - self::SEQUENCE_BITS;
        $machineId = substr($binUuid, $machineIdStart, self::MACHINE_ID_BITS);

        $dataCenterIdStart = $len - self::DATA_CENTER_BITS - self::MACHINE_ID_BITS - self::SEQUENCE_BITS;
        $dataCenterId = substr($binUuid, $dataCenterIdStart, self::DATA_CENTER_BITS);

        $timestamp = substr($binUuid, 0, $dataCenterIdStart);
        $realTimestamp = bindec($timestamp) + self::EPOCH_OFFSET;
        $timestamp = substr($realTimestamp, 0, -3);
        $microSecond = substr($realTimestamp, -3);
        return [
            'timestamp' => date('Y-m-d H:i:s', $timestamp) . '.' . $microSecond,
            'dataCenterId' => bindec($dataCenterId),
            'machineId' => bindec($machineId),
            'sequence' => bindec($sequence),
        ];
    }

    private function getUnixTimestamp()
    {
        return floor(microtime(true) * 1000);
    }
}