雪花算法是由 Twitter 公司开源的可在分布式系统中产生一个全局唯一 ID 的算法。最初 Twitter 把存储系统从 MySQL 迁移到 Cassandra,因为 Cassandra 没有顺序ID生成机制,所以开发了这样一套全局唯一ID生成服务。
SnowFlake 算法生成的 ID 是一个 64 位的整数,它的结构如下图所示:
SnowFlake 生成的 ID 整体上按照时间自增排序,并且整个分布式系统不会产生 ID 碰撞(由 DataCenterID 和 WorkerID 区分),并且效率较高。
在实现 SnowFlake 基本功能的基础上,增加部分拓展功能:
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};
该测试程序测试每秒生成 ID 的数量,基本上每秒可以生成 900000~1100000 左右:
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}