C++ “雪花算法“原理

简介: C++ “雪花算法“原理

C++雪花算法并不是传统的数据结构与算法而是一种崭新的分布式算法  属于深层次C++ 本篇文章就来描述一下雪花算法

什么是雪花算法:

雪花算法(Snowflake)是Twitter开源的一种分布式唯一ID生成算法。它可以在不依赖于数据库等其他存储设施的情况下,生成全局唯一的ID。雪花算法生成的ID是一个64位的长整型数,具体结构如下:

  1. 第1位:符号位,固定为0,表示生成的ID为正数。
  2. 接下来的41位:时间戳(毫秒级),记录了生成ID的时间,可以使用69年。
  3. 然后的10位:机器ID,用于标识不同的机器,可以根据自身需求配置。其中,前5位是机房号,表示最多有32个机房;后5位是机器ID,表示每个机房最多有32台机器。
  4. 最后12位:序列号,用于表示在同一毫秒内生成的多个ID的顺序,支持每台机器每毫秒产生4096个ID。

雪花算法保证了在分布式系统中生成的ID是唯一的、有序的、可排序的,并且不需要依赖于数据库等其他存储设施。同时,雪花算法的高性能、高可用和自增特性,使其在存入数据库中时,索引效率高。

需要注意的是,雪花算法在实际使用时,每台机器需要配置一个唯一的机器ID,以保证生成的ID不与其他机器生成的ID重复。此外,还需要注意时钟回拨的问题,即当本地时钟发生回拨时,可能会导致生成的ID出现重复或者乱序的情况。

snowflake-64bit 组成分析:

分别有三部分(其中第一位保留位,暂时没用):

  1. 第一部分:时间戳(毫秒级),这里为41bit
  2. 第二部分:工作机器id,一般为==5bit数据中心id(datacenterId)+5bit机器id(workerId)==组成,10位的长度最多支持部署1024个节点
  3. 第三部分:在相同毫秒内,可以产生2^12 个id,12位的计数顺序号支持每个节点每毫秒产生4096个ID序列

snowflake-32bit

大致与64bit相同,唯一区别是时间戳部分这里仅占用32bit,因为保存的时间戳为:当前时间戳-雪花算法开始的时间戳,得出来的数据仅用10bit就可以保存,位数越少,对磁盘、数据索引等数据提高越明显  

雪花代码运行过程中逻辑图:

总结:还有利用数据库来生成分布式全局唯一ID方案,不过性能与稳定性都不如snowflake,针对snowflake比较成熟的解决方案可以参考  美团点评分布式ID生成系统。

雪花算法代码实例:

#include <iostream>  
#include <chrono>  
#include <thread>  
#include <random>  
  
// 雪花算法生成的ID的位数  
const int64_t kEpoch = 1609459200000; // 起始时间戳(毫秒级),这里假设为2021-01-01 00:00:00 UTC  
const int64_t kWorkerIdBits = 5;      // 机器ID所占的位数  
const int64_t kDatacenterIdBits = 5;  // 数据中心ID所占的位数  
const int64_t kSequenceBits = 12;    // 序列号所占的位数  
  
// 机器ID和数据中心ID,这些值需要根据实际情况进行配置  
const int64_t kWorkerId = 1;  
const int64_t kDatacenterId = 1;  
  
// 用于生成序列号的随机数生成器  
std::mt19937 gen(static_cast<unsigned int>(time(0)));  
std::uniform_int_distribution<> dis(0, (1 << kSequenceBits) - 1);  
  
// 生成雪花算法ID  
int64_t generateSnowflakeId() {  
    int64_t timestamp = std::chrono::duration_cast<std::chrono::milliseconds>(  
        std::chrono::system_clock::now().time_since_epoch()).count() - kEpoch;  
  
    // 如果当前时间小于上一次生成ID的时间戳,说明系统时钟回退过,应当抛出异常  
    static int64_t lastTimestamp = -1;  
    if (timestamp < lastTimestamp) {  
        throw std::runtime_error("Clock moved backwards. Refusing to generate id for "  
                                 + std::to_string(lastTimestamp - timestamp) + " milliseconds");  
    }  
  
    // 如果是同一时间戳,则进行序列号自增  
    if (lastTimestamp == timestamp) {  
        timestamp = lastTimestamp;  
    } else {  
        // 不同时间戳,序列号置为0  
        sequence = 0;  
    }  
  
    // 上次生成ID的时间截  
    lastTimestamp = timestamp;  
  
    // 移位并通过或运算拼到一起组成64位的ID  
    return ((timestamp << (kWorkerIdBits + kDatacenterIdBits + kSequenceBits)) |  
            (kDatacenterId << (kWorkerIdBits + kSequenceBits)) |  
            (kWorkerId << kSequenceBits) |  
            sequence);  
}  
  
int main() {  
    try {  
        for (int i = 0; i < 10; ++i) {  
            int64_t id = generateSnowflakeId();  
            std::cout << "Generated ID: " << id << std::endl;  
        }  
    } catch (const std::exception& e) {  
        std::cerr << "Exception: " << e.what() << std::endl;  
    }  
  
    return 0;  
}

generateSnowflakeId函数负责生成雪花算法ID。它首先获取当前时间戳,然后检查是否发生了时钟回拨。如果没有回拨,它会根据时间戳、数据中心ID、机器ID和序列号生成一个唯一的64位ID。

好了 本篇文章就到这里结束了 在这里我向大家推荐一个质量高的课程:

https://xxetb.xetslk.com/s/2PjJ3T

相关文章
|
11天前
|
机器学习/深度学习 安全 算法
【图论】【割点】【C++算法】928. 尽量减少恶意软件的传播 II
【图论】【割点】【C++算法】928. 尽量减少恶意软件的传播 II
|
23天前
|
机器学习/深度学习 存储 算法
神经网络分类算法原理详解
神经网络分类算法原理详解
45 0
|
11天前
|
机器学习/深度学习 自然语言处理 算法
|
11天前
|
算法 测试技术 C#
【广度优先搜索】【堆】【C++算法】407. 接雨水 II
【广度优先搜索】【堆】【C++算法】407. 接雨水 II
|
11天前
|
算法 测试技术 Serverless
【二分查找】【C++算法】378. 有序矩阵中第 K 小的元素
【二分查找】【C++算法】378. 有序矩阵中第 K 小的元素
|
11天前
|
算法 测试技术 C#
【字典树】【KMP】【C++算法】3045统计前后缀下标对 II
【字典树】【KMP】【C++算法】3045统计前后缀下标对 II
|
18天前
|
存储 算法 编译器
【数据结构】栈算法(算法原理+源码)
【数据结构】栈算法(算法原理+源码)
【数据结构】栈算法(算法原理+源码)
|
23天前
|
缓存 算法 关系型数据库
深度思考:雪花算法snowflake分布式id生成原理详解
雪花算法snowflake是一种优秀的分布式ID生成方案,其优点突出:它能生成全局唯一且递增的ID,确保了数据的一致性和准确性;同时,该算法灵活性强,可自定义各部分bit位,满足不同业务场景的需求;此外,雪花算法生成ID的速度快,效率高,能有效应对高并发场景,是分布式系统中不可或缺的组件。
深度思考:雪花算法snowflake分布式id生成原理详解
|
1月前
|
机器学习/深度学习 算法 生物认证
基于深度学习的人员指纹身份识别算法matlab仿真
基于深度学习的人员指纹身份识别算法matlab仿真
|
28天前
|
传感器 算法 计算机视觉
基于肤色模型和中值滤波的手部检测算法FPGA实现,包括tb测试文件和MATLAB辅助验证
该内容是关于一个基于肤色模型和中值滤波的手部检测算法的描述,包括算法的运行效果图和所使用的软件版本(matlab2022a, vivado2019.2)。算法分为肤色分割和中值滤波两步,其中肤色模型在YCbCr色彩空间定义,中值滤波用于去除噪声。提供了一段核心程序代码,用于处理图像数据并在FPGA上实现。最终,检测结果输出到&quot;hand.txt&quot;文件。