雪花算法
雪花算法（Snowflake Algorithm）是一种生成唯一ID的算法，最初由Twitter开发。它的主要特点是生成的ID是64位的长整型数字，具有以下特性：
- 唯一性：每个生成的ID都是唯一的。
- 趋势递增：生成的ID是递增的，可以作为时间戳使用。
- 去中心化：可以在多个节点上生成ID，而不需要集中式协调。
雪花算法的基本结构
雪花算法生成的ID由以下几部分组成：
- 1位：未使用，始终为0。
- 41位：时间戳（毫秒级），表示从某个特定时间点（如2010年）开始的时间。
- 10位：机器ID，用于区分不同的机器或服务实例。
- 12位：序列号，用于同一毫秒内生成多个ID。
雪花算法的C++实现
以下是一个简化版的C++实现示例：
#include <iostream>
#include <chrono>
#include <cstdint>
#include <cstring>class Snowflake {
private:static const int64_t EPOCH = 1288834974657L; // 起始时间点，Twitter的起始时间点是2010-11-04static const int64_t WORKER_ID_BITS = 10; // 机器ID所占位数static const int64_t MAX_WORKER_ID = -1L ^ (-1L << WORKER_ID_BITS); // 机器ID最大值static const int64_t SEQUENCE_BITS = 12; // 序列号所占位数static const int64_t SEQUENCE_MASK = -1L ^ (-1L << SEQUENCE_BITS); // 序列号掩码static const int64_t WORKER_ID_SHIFT = SEQUENCE_BITS; // 机器ID左移位数static const int64_t TIMESTAMP_LEFT_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS; // 时间戳左移位数static const int64_t MAX_SEQUENCE = (1 << SEQUENCE_BITS) - 1; // 序列号最大值static const int64_t TWEPOCH = 687888001L; // 以Twitter的起始时间点为例int64_t workerId; // 机器IDint64_t sequence; // 序列号int64_t lastTimestamp; // 上次生成ID的时间戳public:Snowflake(int64_t workerId) : workerId(workerId), sequence(0), lastTimestamp(-1) {if (workerId > MAX_WORKER_ID || workerId < 0) {throw std::invalid_argument("Worker ID must be between 0 and 1023");}}int64_t nextId() {int64_t timestamp = timeGen();if (timestamp < lastTimestamp) {throw std::runtime_error("Clock moved backwards. Refusing to generate id for this time.");}if (lastTimestamp == timestamp) {sequence = (sequence + 1) & MAX_SEQUENCE;if (sequence == 0) {timestamp = tilNextMillis(lastTimestamp);}} else {sequence = 0;}lastTimestamp = timestamp;return ((timestamp - EPOCH) << TIMESTAMP_LEFT_SHIFT) |(workerId << WORKER_ID_SHIFT) |sequence;}private:int64_t tilNextMillis(int64_t lastTimestamp) {int64_t timestamp = timeGen();while (timestamp <= lastTimestamp) {timestamp = timeGen();}return timestamp;}int64_t timeGen() {return std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now().time_since_epoch()).count() + TWEPOCH;}
};int main() {Snowflake snowflake(1); // 假设机器ID为1for (int i = 0; i < 10; ++i) {std::cout << "ID: " << snowflake.nextId() << std::endl;}return 0;
}
说明
- 时间戳：使用
std::chrono库获取当前时间戳，并加上一个起始时间点（Twitter的起始时间点是2010-11-04）。 - 机器ID：在构造函数中传入，用于区分不同的机器或服务实例。
- 序列号：每次生成ID时递增，同一毫秒内最多生成4096个ID（2^12）。
- ID生成：通过按位运算组合时间戳、机器ID和序列号生成最终的ID。
这个实现是线程安全的，每次调用nextId方法会生成一个新的ID。注意，这个实现依赖于系统时钟，如果系统时钟回拨，可能会导致生成重复的ID。