学习笔记9：雪花算法

雪花算法

雪花算法（Snowflake Algorithm）是一种生成唯一ID的算法，最初由Twitter开发。它的主要特点是生成的ID是64位的长整型数字，具有以下特性：

1. 唯一性：每个生成的ID都是唯一的。
2. 趋势递增：生成的ID是递增的，可以作为时间戳使用。
3. 去中心化：可以在多个节点上生成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-04
    static 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; // 机器ID
    int64_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为1
    for (int i = 0; i < 10; ++i) {
        std::cout << "ID: " << snowflake.nextId() << std::endl;
    }
    return 0;
}

说明

1. 时间戳：使用std::chrono库获取当前时间戳，并加上一个起始时间点（Twitter的起始时间点是2010-11-04）。
2. 机器ID：在构造函数中传入，用于区分不同的机器或服务实例。
3. 序列号：每次生成ID时递增，同一毫秒内最多生成4096个ID（2^12）。
4. ID生成：通过按位运算组合时间戳、机器ID和序列号生成最终的ID。

这个实现是线程安全的，每次调用nextId方法会生成一个新的ID。注意，这个实现依赖于系统时钟，如果系统时钟回拨，可能会导致生成重复的ID。

原文地址：https://blog.csdn.net/qq_29111047/article/details/140673915

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！