1. SnowFlake 算法介绍
雪花算法是由 Twitter 公司开源的可在分布式系统中产生一个全局唯一 ID 的算法。最初 Twitter 把存储系统从 MySQL 迁移到 Cassandra，因为 Cassandra 没有顺序ID生成机制，所以开发了这样一套全局唯一ID生成服务。
SnowFlake 算法生成的 ID 是一个 64 位的整数，它的结构如下图所示：
- 第一部分：1bit 符号位，由于都是生成 ID 都是正数，所以第一位统一为0；
- 第二部分：41 bit 时间戳，单位是毫秒，41 位可以表示的数字多达 2^41 - 1，换算成年就是 69 年；
- 第三部分：5 bit 机房 ID，代表最多支持 32 个机房；
- 第四部分：5 bit 机器 ID，代表每个机房最多支持 32 台机器；
- 第五部分：12 bit，记录同一时间（毫秒）内产生的不同 id，也就是说同一毫秒内可以产生4096个不同 id。
SnowFlake 生成的 ID 整体上按照时间自增排序，并且整个分布式系统不会产生 ID 碰撞（由 DataCenterID 和 WorkerID 区分），并且效率较高。
2. 实现
在实现 SnowFlake 基本功能的基础上，增加部分拓展功能：
- 定义开始时间戳，默认为 2020/01/01 08:00:00，如果使用默认的时间戳位数，那么该程序生成 ID 大概可以使用到 2089 年；
- 机房 ID 、机器 ID 和 序列 ID 三个数据段长度可以自定义，通过构造函数传入。
2.1 方法介绍
- timeGen
- 描述：生成当前毫秒时间戳，相对于 2020年1月1日 8:00:00
- 属性：private
- 返回值：当前毫秒时间戳
- tilNextMillis
- 描述：阻塞直到下一毫秒
- 属性：private
- 返回值：下一毫秒时间戳
- nextId
- 描述：生成一个新的 ID
- 返回值：新 ID
2.2流程图
2.3 代码实现
代码语言：javascript复制 1// SnowFlake.h
2
3#pragma once
4
5#include <mutex>
6#include <chrono>
7#include <stdint.h>
8
9extern const uint64_t INVALID_ID = 0;
10
11class SnowFlake
12{
13public:
14 SnowFlake(uint64_t datacenterId, uint64_t machineId,
15 uint64_t datacenterIdBit = 5, uint64_t machineIdBit = 5, uint64_t sequenceBit = 12)
16 : datacenterIdBit_(datacenterIdBit),
17 machineIdBit_(machineIdBit),
18 sequenceBit_(sequenceBit),
19 maxDataCenterCount_(-1 ^ (uint64_t(-1) << datacenterIdBit_)),
20 maxMachineCount_(-1 ^ (uint64_t(-1) << machineIdBit)),
21 maxSequenceCount_(-1 ^ (uint64_t(-1) << sequenceBit_)),
22 machineShift_(sequenceBit_),
23 dataCenterShift_(machineShift_ machineIdBit_),
24 timestampShift_(dataCenterShift_ datacenterIdBit_),
25 datacenterId_(datacenterId),
26 machineId_(machineId)
27 {
28 if (datacenterIdBit machineIdBit sequenceBit != 64 - 1 - 41)
29 {
30 std::cout << "datacenterIdBit machineIdBit sequenceBit != 22, please check." << std::endl;
31 exit(0);
32 }
33 }
34 ~SnowFlake() {}
35
36 uint64_t nextId() {
37 std::unique_lock<std::mutex> lock(mutex_);
38 uint64_t currTimestsmp = timeGen();
39 if (currTimestsmp < lastTimestamp_) {
40 std::cout << "Clock has been moved backwards. Generate id failed." << std::endl;
41 return INVALID_ID;
42 }
43
44 if (currTimestsmp == lastTimestamp_) {
45 sequence_ = (sequence_ 1) & maxSequenceCount_;
46 if (0 == sequence_) {
47 currTimestsmp = tilNextMillis();
48 }
49 }
50 else {
51 sequence_ = 0;
52 }
53
54 lastTimestamp_ = currTimestsmp;
55 return lastTimestamp_ << timestampShift_
56 | datacenterId_ << dataCenterShift_
57 | machineShift_ << machineShift_
58 | sequence_;
59 }
60
61protected:
62 uint64_t timeGen() const {
63 return std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now().time_since_epoch()).count() - startTimestamp_;
64 }
65
66 uint64_t tilNextMillis() const {
67 uint64_t mill = timeGen();
68 while (mill <= lastTimestamp_) {
69 mill = timeGen();
70 }
71 return mill;
72 }
73
74private:
75 const uint64_t startTimestamp_ = 1577836800000; // 2020/01/01 08:00:00
76 const uint64_t datacenterIdBit_;
77 const uint64_t machineIdBit_;
78 const uint64_t sequenceBit_;
79
80 const uint64_t maxMachineCount_;
81 const uint64_t maxDataCenterCount_;
82 const uint64_t maxSequenceCount_;
83
84 const uint64_t machineShift_;
85 const uint64_t dataCenterShift_;
86 const uint64_t timestampShift_;
87
88 uint64_t lastTimestamp_ = 0;
89 uint64_t datacenterId_ = 0;
90 uint64_t machineId_ = 0;
91 uint64_t sequence_ = 0;
92
93 std::mutex mutex_;
94};2.4 测试程序
该测试程序测试每秒生成 ID 的数量，基本上每秒可以生成 900000~1100000 左右：
代码语言：javascript复制 1#include <iostream>
2
3#include "SnowFlake.h"
4
5int main()
6{
7 std::chrono::steady_clock::time_point start_;
8 std::chrono::steady_clock::time_point end_;
9
10 SnowFlake uuid(5 , 10);
11 start_ = std::chrono::steady_clock::now();
12 uint64_t cnt = 0;
13
14 while (std::chrono::duration<double, std::milli>(std::chrono::steady_clock::now() - start_).count() < 1000)
15 {
16 cnt ;
17 uuid.nextId();
18 }
19
20 std::cout << "SnowFlake generates " << cnt << " ids one second." << std::endl;
21}
