雪花算法
雪花算法（Snowflake Algorithm）是由Twitter开发的一种用于生成唯一ID的方法，特别适用于分布式系统。它可以在不依赖数据库的情况下生成唯一的ID，非常适合在分布式系统中作为唯一标识符使用。雪花算法的基本原理涉及以下几个关键组成部分：
- 时间戳：这是雪花算法的主要部分，通常是一个64位的长整型。算法的第一部分是一个时间戳，通常精确到毫秒级。时间戳可以保证按时间顺序生成的ID的唯一性和递增性。
- 工作机器ID：这部分用于在分布式系统中区分不同的机器。在一个大型系统中，可能有许多服务器都在生成ID，这部分确保即使多个服务器同时生成ID，生成的ID也是唯一的。这通常由两部分组成：数据中心ID和机器ID。
- 序列号：在同一毫秒内，可能会有多个ID生成请求。序列号用于区分同一毫秒内的这些不同的ID请求。每当同一毫秒内有新的ID生成请求时，序列号就会递增，并在达到最大值后重置。
- 位数分配：一个典型的64位雪花ID通常分配如下：1位符号位：通常为0，保持正数。41位时间戳：精确到毫秒，可以使用约69年。10位工作机器ID：可以分为5位数据中心ID和5位机器ID，最多支持32个数据中心，每个数据中心最多支持32台机器。12位序列号：支持同一毫秒内生成最多4096个ID。
雪花算法的优点包括：
- 高效率：ID生成过程是完全独立的，无需网络通信。
- 可扩展性：通过调整不同部分的位数，可以适应不同规模的系统。
- 唯一性和递增性：保证了ID的唯一性，并且在单个机器上生成的ID是递增的。
雪花算法的局限性：
- 依赖系统时钟：如果系统时钟回拨，可能会导致ID冲突或生成失败。
- 有使用期限：41位时间戳决定了该算法可以使用的年限（约69年）
缺点也是有的，就是强依赖机器时钟，如果机器上时钟回拨，有可能会导致主键重复的问题。
#include <iostream>
#include <mutex>
#include <chrono>
class SnowflakeIdGenerator {
private:
const int workerIdBits = 5;
const int datacenterIdBits = 5;
const int maxWorkerId = -1 ^ (-1 << workerIdBits);
const int maxDatacenterId = -1 ^ (-1 << datacenterIdBits);
const int sequenceBits = 12;
const int workerIdShift = sequenceBits;
const int datacenterIdShift = sequenceBits + workerIdBits;
const int timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
const int64_t twepoch = 1288834974657L;
int64_t lastTimestamp = -1L;
int64_t sequence = 0;
int workerId;
int datacenterId;
std::mutex mutex_;
public:
SnowflakeIdGenerator(int workerId, int datacenterId) {
if (workerId > maxWorkerId || workerId < 0) {
throw std::runtime_error("worker Id can't be greater than " + std::to_string(maxWorkerId) + " or less than 0");
}
if (datacenterId > maxDatacenterId || datacenterId < 0) {
throw std::runtime_error("datacenter Id can't be greater than " + std::to_string(maxDatacenterId) + " or less than 0");
}
this->workerId = workerId;
this->datacenterId = datacenterId;
}
int64_t nextId() {
std::lock_guard<std::mutex> lock(mutex_);
int64_t timestamp = timeGen();
if (timestamp < lastTimestamp) {
throw std::runtime_error("Clock moved backwards. Refusing to generate id for " + std::to_string(lastTimestamp - timestamp) + " milliseconds");
}
if (lastTimestamp == timestamp) {
sequence = (sequence + 1) & (-1 ^ (-1 << sequenceBits));
if (sequence == 0) {
timestamp = tilNextMillis(lastTimestamp);
}
} else {
sequence = 0;
}
lastTimestamp = timestamp;
return ((timestamp - twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | sequence;
}
protected:
int64_t tilNextMillis(int64_t lastTimestamp) {
int64_t timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
int64_t timeGen() {
auto now = std::chrono::system_clock::now();
auto duration = now.time_since_epoch();
return std::chrono::duration_cast<std::chrono::milliseconds>(duration).count();
}
};
int main() {
try {
SnowflakeIdGenerator generator(1, 1); // Replace with your workerId and datacenterId
for (int i = 0; i < 10; i++) {
std::cout << "Generated ID: " << generator.nextId() << std::endl;
}
} catch (const std::exception &e) {
std::cerr << "Error: " << e.what() << std::endl;
}
return 0;
}
调整雪花算法的时间使用限制主要分两种策略：
1.调整时间戳位数：你可以考虑增加时间戳位数，以适应更长的时间。但是，这需要从其他部分（如工作机器ID或序列号）借用一些位数，这可能会减少你能支持的数据中心或机器数量，或者减少每毫秒生成的ID数量。因此，需要根据实际系统需求来做出权衡。
2.改变参考时间：另一种方法是设定新的起始时间点，比如原始的算法定义从1970年1月1日作为起始时间，如果我们从现在这一刻（2023年12月12日）开始记时，即改变了参考时点，可以再使用约69年。只要确保新旧系统不会同时产生ID，就可以避免ID冲突。
注意以上的改动需要在系统设计阶段就确定，并且在整个系统生命周期保持一致，因为一旦雪花算法生成的ID开始使用，就不能轻易改变算法否则可能会产生ID冲突。
#c++##雪花啤酒#
查看27道真题和解析