ID生成算法-雪花算法介绍及实现

 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};

 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}