SnowflakeIdWorker c++11
Twitter Snowflake c++11實(shí)現(xiàn)版本
SnowFlake 算法生成的 id 是一個(gè)64位大小的整數(shù), 它的結(jié)構(gòu)如下圖:
id結(jié)構(gòu)
1位: 不用, 二進(jìn)制中最高位為1的都是負(fù)數(shù), 但是我們生成的id一般都使用整數(shù), 所以這個(gè)最高位固定是0.
41位: 用來記錄時(shí)間戳(毫秒級(jí)), 注意, 這里存儲(chǔ)的不是當(dāng)前的時(shí)間戳，而是存儲(chǔ)時(shí)間戳的差值(當(dāng)前時(shí)間截 - 開始時(shí)間截), 可以表示69年的時(shí)間.
10位: 用來記錄工作機(jī)器id, 可以部署在1024個(gè)節(jié)點(diǎn), 包括5位datacenterId和5位workerId.
12位: 序列號(hào)，用來記錄同毫秒內(nèi)產(chǎn)生的不同id, 同一機(jī)器同一時(shí)間截（毫秒)內(nèi)可以產(chǎn)生4096個(gè)序列號(hào), 也就是1毫秒內(nèi)可以產(chǎn)生4096個(gè)id.
Snowflake可以保證：
- 所有生成的id按時(shí)間趨勢遞增.
- 整個(gè)分布式系統(tǒng)內(nèi)不會(huì)產(chǎn)生重復(fù)id（因?yàn)橛衐atacenterId和workerId來做區(qū)分）.
代碼實(shí)現(xiàn):
#ifndef _JW_CORE_ID_WORKER_H_
#define _JW_CORE_ID_WORKER_H_
#include <mutex>
#include <atomic>
#include <chrono>
#include <exception>
#include <sstream>
#include "Noncopyable.h"
#include "Singleton.h"
// 如果不使用 mutex, 則開啟下面這個(gè)定義, 但是我發(fā)現(xiàn), 還是開啟 mutex 功能, 速度比較快
// #define SNOWFLAKE_ID_WORKER_NO_LOCK
namespace Jiawa {
/**
* @brief 核心
* 核心功能
*/
namespace Core {
/**
* @brief 分布式id生成類
* https://segmentfault.com/a/1190000011282426
* https://github.com/twitter/snowflake/blob/snowflake-2010/src/main/scala/com/twitter/service/snowflake/IdWorker.scala
*
* 64bit id: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
* || || || | | |
* |└---------------------------時(shí)間戳--------------------------┘└中心-┘└機(jī)器-┘ └----序列號(hào)----┘
* |
* 不用
* SnowFlake的優(yōu)點(diǎn): 整體上按照時(shí)間自增排序, 并且整個(gè)分布式系統(tǒng)內(nèi)不會(huì)產(chǎn)生ID碰撞(由數(shù)據(jù)中心ID和機(jī)器ID作區(qū)分), 并且效率較高, 經(jīng)測試, SnowFlake每秒能夠產(chǎn)生26萬ID左右.
*/
class SnowflakeIdWorker : private Noncopyable {
// 實(shí)現(xiàn)單例
friend class Singleton<SnowflakeIdWorker>;
public:
typedef unsigned int UInt;
typedef unsigned long long int UInt64;
#ifdef SNOWFLAKE_ID_WORKER_NO_LOCK
typedef std::atomic<UInt> AtomicUInt;
typedef std::atomic<UInt64> AtomicUInt64;
#else
typedef UInt AtomicUInt;
typedef UInt64 AtomicUInt64;
#endif
void setWorkerId(UInt workerId) {
this->workerId = workerId;
}
void setDatacenterId(UInt datacenterId) {
this->datacenterId = datacenterId;
}
UInt64 getId() {
return nextId();
}
/**
* 獲得下一個(gè)ID (該方法是線程安全的)
*
* @return SnowflakeId
*/
UInt64 nextId() {
#ifndef SNOWFLAKE_ID_WORKER_NO_LOCK
std::unique_lock<std::mutex> lock{ mutex };
AtomicUInt64 timestamp{ 0 };
#else
static AtomicUInt64 timestamp{ 0 };
#endif
timestamp = timeGen();
// 如果當(dāng)前時(shí)間小于上一次ID生成的時(shí)間戳，說明系統(tǒng)時(shí)鐘回退過這個(gè)時(shí)候應(yīng)當(dāng)拋出異常
if (timestamp < lastTimestamp) {
std::ostringstream s;
s << "clock moved backwards. Refusing to generate id for " << lastTimestamp - timestamp << " milliseconds";
throw std::exception(std::runtime_error(s.str()));
}
if (lastTimestamp == timestamp) {
// 如果是同一時(shí)間生成的，則進(jìn)行毫秒內(nèi)序列
sequence = (sequence + 1) & sequenceMask;
if (0 == sequence) {
// 毫秒內(nèi)序列溢出, 阻塞到下一個(gè)毫秒,獲得新的時(shí)間戳
timestamp = tilNextMillis(lastTimestamp);
}
} else {
sequence = 0;
}
#ifndef SNOWFLAKE_ID_WORKER_NO_LOCK
lastTimestamp = timestamp;
#else
lastTimestamp = timestamp.load();
#endif
// 移位并通過或運(yùn)算拼到一起組成64位的ID
return ((timestamp - twepoch) << timestampLeftShift)
| (datacenterId << datacenterIdShift)
| (workerId << workerIdShift)
| sequence;
}
protected:
SnowflakeIdWorker() : workerId(0), datacenterId(0), sequence(0), lastTimestamp(0) { }
/**
* 返回以毫秒為單位的當(dāng)前時(shí)間
*
* @return 當(dāng)前時(shí)間(毫秒)
*/
UInt64 timeGen() const {
auto t = std::chrono::time_point_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now());
return t.time_since_epoch().count();
}
/**
* 阻塞到下一個(gè)毫秒，直到獲得新的時(shí)間戳
*
* @param lastTimestamp 上次生成ID的時(shí)間截
* @return 當(dāng)前時(shí)間戳
*/
UInt64 tilNextMillis(UInt64 lastTimestamp) const {
UInt64 timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
private:
#ifndef SNOWFLAKE_ID_WORKER_NO_LOCK
std::mutex mutex;
#endif
/**
* 開始時(shí)間截 (2018-01-01 00:00:00.000)
*/
const UInt64 twepoch = 1514736000000;
/**
* 機(jī)器id所占的位數(shù)
*/
const UInt workerIdBits = 5;
/**
* 數(shù)據(jù)中心id所占的位數(shù)
*/
const UInt datacenterIdBits = 5;
/**
* 序列所占的位數(shù)
*/
const UInt sequenceBits = 12;
/**
* 機(jī)器ID向左移12位
*/
const UInt workerIdShift = sequenceBits;
/**
* 數(shù)據(jù)標(biāo)識(shí)id向左移17位
*/
const UInt datacenterIdShift = workerIdShift + workerIdBits;
/**
* 時(shí)間截向左移22位
*/
const UInt timestampLeftShift = datacenterIdShift + datacenterIdBits;
/**
* 支持的最大機(jī)器id，結(jié)果是31
*/
const UInt maxWorkerId = -1 ^ (-1 << workerIdBits);
/**
* 支持的最大數(shù)據(jù)中心id，結(jié)果是31
*/
const UInt maxDatacenterId = -1 ^ (-1 << datacenterIdBits);
/**
* 生成序列的掩碼，這里為4095
*/
const UInt sequenceMask = -1 ^ (-1 << sequenceBits);
/**
* 工作機(jī)器id(0~31)
*/
UInt workerId;
/**
* 數(shù)據(jù)中心id(0~31)
*/
UInt datacenterId;
/**
* 毫秒內(nèi)序列(0~4095)
*/
AtomicUInt sequence{ 0 };
/**
* 上次生成ID的時(shí)間截
*/
AtomicUInt64 lastTimestamp{ 0 };
};
typedef SnowflakeIdWorker IdWorker;
}
}
#endif // _JW_CORE_ID_WORKER_H_
測試代碼:
#include <iostream>
#include "./Core/Timer.h"
#include "./Core/IdWorker.h"
using namespace Jiawa::Core;
int main(int argc, char **argv) {
std::cout << "start generate id" << std::endl;
auto &idWorker = Singleton<IdWorker>::instance();
idWorker.setDatacenterId(12);
idWorker.setWorkerId(5);
const size_t count = 20000000;
Timer<> timer;
for (size_t i = 0; i < count; i++)
{
idWorker.nextId();
}
// 我的電腦生成 20000000 id 的耗時(shí)為 4.887s
std::cout << "generate " << count << " id elapsed: " << timer.elapsed() << "ms" << std::endl;
return 0;
}
