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

相关文章
机器学习/深度学习 算法 自动驾驶
101 0
|
18天前
|
机器学习/深度学习 算法 搜索推荐
从零开始构建图注意力网络:GAT算法原理与数值实现详解
本文详细解析了图注意力网络(GAT)的算法原理和实现过程。GAT通过引入注意力机制解决了图卷积网络(GCN)中所有邻居节点贡献相等的局限性,让模型能够自动学习不同邻居的重要性权重。
85 0
从零开始构建图注意力网络:GAT算法原理与数值实现详解
|
26天前
|
机器学习/深度学习 算法 文件存储
神经架构搜索NAS详解:三种核心算法原理与Python实战代码
神经架构搜索(NAS)正被广泛应用于大模型及语言/视觉模型设计,如LangVision-LoRA-NAS、Jet-Nemotron等。本文回顾NAS核心技术,解析其自动化设计原理,探讨强化学习、进化算法与梯度方法的应用与差异,揭示NAS在大模型时代的潜力与挑战。
235 6
神经架构搜索NAS详解:三种核心算法原理与Python实战代码
|
29天前
|
传感器 算法 定位技术
KF,EKF,IEKF 算法的基本原理并构建推导出四轮前驱自主移动机器人的运动学模型和观测模型(Matlab代码实现)
KF,EKF,IEKF 算法的基本原理并构建推导出四轮前驱自主移动机器人的运动学模型和观测模型(Matlab代码实现)
|
1月前
|
算法
离散粒子群算法(DPSO)的原理与MATLAB实现
离散粒子群算法(DPSO)的原理与MATLAB实现
86 0
|
2月前
|
机器学习/深度学习 人工智能 编解码
AI视觉新突破:多角度理解3D世界的算法原理全解析
多视角条件扩散算法通过多张图片输入生成高质量3D模型,克服了单图建模背面细节缺失的问题。该技术模拟人类多角度观察方式,结合跨视图注意力机制与一致性损失优化,大幅提升几何精度与纹理保真度,成为AI 3D生成的重要突破。
167 0
|
2月前
|
算法 区块链 数据安全/隐私保护
加密算法:深度解析Ed25519原理
在 Solana 开发过程中,我一直对 Ed25519 加密算法 如何生成公钥、签名以及验证签名的机制感到困惑。为了弄清这一点,我查阅了大量相关资料,终于对其流程有了更清晰的理解。在此记录实现过程,方便日后查阅。
149 1
|
2月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
77 0
|
3月前
|
消息中间件 存储 缓存
zk基础—1.一致性原理和算法
本文详细介绍了分布式系统的特点、理论及一致性算法。首先分析了分布式系统的五大特点:分布性、对等性、并发性、缺乏全局时钟和故障随时发生。接着探讨了分布式系统理论,包括CAP理论(一致性、可用性、分区容错性)和BASE理论(基本可用、软状态、最终一致性)。文中还深入讲解了两阶段提交(2PC)与三阶段提交(3PC)协议,以及Paxos算法的推导过程和核心思想,强调了其在ZooKeeper中的应用。最后简述了ZAB算法,指出其通过改编的两阶段提交协议确保节点间数据一致性,并在Leader故障时快速恢复服务。这些内容为理解分布式系统的设计与实现提供了全面的基础。
|
3月前
|
存储 机器学习/深度学习 算法
基于 C++ 的局域网访问控制列表(ACL)实现及局域网限制上网软件算法研究
本文探讨局域网限制上网软件中访问控制列表(ACL)的应用,分析其通过规则匹配管理网络资源访问的核心机制。基于C++实现ACL算法原型,展示其灵活性与安全性。文中强调ACL在企业与教育场景下的重要作用,并提出性能优化及结合机器学习等未来研究方向。
96 4

热门文章

最新文章