雪花算法

雪花算法（Snowflake Algorithm）是由Twitter开发的一种用于生成唯一ID的方法，特别适用于分布式系统。它可以在不依赖数据库的情况下生成唯一的ID，非常适合在分布式系统中作为唯一标识符使用。雪花算法的基本原理涉及以下几个关键组成部分：

1. 时间戳：这是雪花算法的主要部分，通常是一个64位的长整型。算法的第一部分是一个时间戳，通常精确到毫秒级。时间戳可以保证按时间顺序生成的ID的唯一性和递增性。
2. 工作机器ID：这部分用于在分布式系统中区分不同的机器。在一个大型系统中，可能有许多服务器都在生成ID，这部分确保即使多个服务器同时生成ID，生成的ID也是唯一的。这通常由两部分组成：数据中心ID和机器ID。
3. 序列号：在同一毫秒内，可能会有多个ID生成请求。序列号用于区分同一毫秒内的这些不同的ID请求。每当同一毫秒内有新的ID生成请求时，序列号就会递增，并在达到最大值后重置。
4. 位数分配：一个典型的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冲突。