雪花算法
雪花算法(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++##雪花啤酒#