雪花算法：分布式ID生成的优雅解决方案

一、雪花算法的核心机制与设计思想

  雪花算法（Snowflake）是由Twitter开源的分布式ID生成算法，它通过巧妙的位运算设计，能够在分布式系统中快速生成全局唯一且趋势递增的ID。

1. 基本结构

雪花算法生成的是一个64位（long型）的整数，这个整数被划分为不同的部分，每个部分代表不同的含义：

  • 符号位（1位）：固定为0，表示正数。
  • 时间戳部分（41位）：记录的是时间戳的差值（当前时间戳 - 开始时间戳），而非当前时间戳本身。
  • 工作机器ID部分（10位）：用于标识不同的机器或节点，可进一步细分为：
    • 数据中心ID（5位）：最多支持32个数据中心
    • 机器ID（5位）：每个数据中心最多支持32台机器
  • 序列号部分（12位）：同一毫秒内的自增序列，最多支持4096个序列号

2. 设计思想

2.1 位运算的高效性

  雪花算法通过位运算来组合各个部分，形成最终的ID。位运算的效率非常高，能够满足高并发场景下的ID生成需求。基本原理是将各部分数值通过左移操作放置到对应的位置，然后通过按位或运算组合成最终的ID。

2.2 时间戳的使用

  • 选择41位时间戳：能够表示约69年的时间范围（(1L<<41)/(1000L360024*365) ≈ 69年）
  • 毫秒级精度：满足大多数应用场景的时间精度需求
  • 趋势递增特性：由于高位是时间戳，整体ID呈现递增趋势，有利于数据库索引性能

2.3 机器ID的设计

  • 分布式支持：通过10位的机器ID，最多可支持1024台机器同时生成ID，满足分布式系统需求
  • 灵活的划分方式：可根据实际需求，灵活划分数据中心ID和机器ID的位数

2.4 序列号的设计

  • 毫秒内并发：12位序列号支持同一毫秒内生成4096个不同的ID
  • 循环利用：当序列号达到最大值时，通过等待下一毫秒来重置序列号
  • 高并发支持：理论上单机每秒可生成约409.6万个ID（4096 * 1000）

3. 核心算法流程

  1. 获取当前时间戳
  2. 检查时钟回拨：如果当前时间戳小于上一次的时间戳，说明发生了时钟回拨，需要进行特殊处理
  3. 生成序列号：
    • 如果当前时间戳与上一次相同，序列号加1
    • 如果序列号超过最大值（4095），则等待下一毫秒
    • 如果当前时间戳大于上一次时间戳，序列号重置为0
  4. 更新上一次时间戳
  5. 组合ID：通过位运算将时间戳、数据中心ID、机器ID和序列号组合成最终的ID

4. 算法优势

  1. 全局唯一性：通过时间戳、机器ID和序列号的组合，确保生成的ID在分布式环境中全局唯一
  2. 趋势递增：高位是时间戳，使得生成的ID整体呈现递增趋势，有利于数据库索引性能
  3. 高性能：基于位运算的实现，性能极高，且不依赖外部系统
  4. 自治性：每台机器独立生成ID，不需要中央服务器协调，避免了单点故障
  5. 灵活性：可根据业务需求调整各部分的位数分配

5. 算法局限

  1. 强依赖机器时钟：如果发生时钟回拨，可能会导致ID重复或服务不可用
  2. 机器ID的配置：需要手动配置机器ID，确保在分布式环境中唯一

雪花算法通过简洁而巧妙的设计，提供了一种高效、可靠的分布式ID生成方案，被广泛应用于各类分布式系统中。其核心思想也启发了许多其他分布式ID生成算法的设计和优化。

6. 雪花算法的实现机制

雪花算法的实现相对简单，主要依靠位运算来组合各个部分，形成最终的ID。下面是算法的核心流程：

  • 首先，获取当前时间戳。这一步通常使用系统的毫秒级时间戳函数，如Java中的System.currentTimeMillis()。

  • 接着，检查时钟回拨问题。如果当前时间戳小于上一次生成ID时的时间戳，说明发生了时钟回拨，需要进行特殊处理。标准的雪花算法会在这种情况下抛出异常，但在实际应用中，通常会有更复杂的处理机制。

  • 然后，生成序列号。如果当前时间戳与上一次相同，序列号加1；如果序列号超过最大值（4095），则需要等待下一毫秒；如果当前时间戳大于上一次时间戳，序列号重置为0。

最后，通过位运算将时间戳、数据中心ID、机器ID和序列号组合成最终的ID。具体来说，将时间戳左移22位（10位机器ID + 12位序列号），将数据中心ID左移17位（5位机器ID + 12位序列号），将机器ID左移12位，然后将这些结果与序列号进行按位或运算，得到最终的ID。

下面是一个简化的Java实现示例：

public class SnowflakeIdGenerator {// 起始时间戳，可设定为系统上线时间private final long startTimestamp = 1420041600000L; // 2015-01-01// 各部分占用的位数private final long datacenterIdBits = 5L;private final long workerIdBits = 5L;private final long sequenceBits = 12L;// 各部分最大值private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);private final long maxWorkerId = -1L ^ (-1L << workerIdBits);private final long sequenceMask = -1L ^ (-1L << sequenceBits);// 各部分向左的位移private final long workerIdShift = sequenceBits;private final long datacenterIdShift = sequenceBits + workerIdBits;private final long timestampShift = sequenceBits + workerIdBits + datacenterIdBits;private long datacenterId;private long workerId;private long sequence = 0L;private long lastTimestamp = -1L;public SnowflakeIdGenerator(long datacenterId, long workerId) {// 参数校验if (datacenterId > maxDatacenterId || datacenterId < 0) {throw new IllegalArgumentException("Datacenter ID can't be greater than " + maxDatacenterId + " or less than 0");}if (workerId > maxWorkerId || workerId < 0) {throw new IllegalArgumentException("Worker ID can't be greater than " + maxWorkerId + " or less than 0");}this.datacenterId = datacenterId;this.workerId = workerId;}public synchronized long nextId() {long timestamp = System.currentTimeMillis();// 检查时钟回拨if (timestamp < lastTimestamp) {throw new RuntimeException("Clock moved backwards. Refusing to generate ID");}// 同一毫秒内序列号递增if (timestamp == lastTimestamp) {sequence = (sequence + 1) & sequenceMask;// 同一毫秒内序列号用尽if (sequence == 0) {// 等待下一毫秒timestamp = waitForNextMillis(lastTimestamp);}} else {// 不同毫秒，序列号重置sequence = 0L;}lastTimestamp = timestamp;// 组合IDreturn ((timestamp - startTimestamp) << timestampShift) |(datacenterId << datacenterIdShift) |(workerId << workerIdShift) |sequence;}private long waitForNextMillis(long lastTimestamp) {long timestamp = System.currentTimeMillis();while (timestamp <= lastTimestamp) {timestamp = System.currentTimeMillis();}return timestamp;}
}

二、雪花算法使用注意事项

在实际应用雪花算法（Snowflake）生成分布式ID时，需要注意以下几个关键问题和最佳实践，以确保系统的稳定性和ID的唯一性。

1. 时钟回拨问题

1.1 问题描述

时钟回拨是雪花算法面临的最大挑战。由于算法强依赖机器时钟，当服务器时间发生回调（例如NTP同步、人为调整等）时，可能导致生成重复的ID。

1.2 解决方案

  1. 拒绝服务策略：

    • 最简单的方法是检测到时钟回拨时直接抛出异常，拒绝服务
    • 适用于时钟回拨概率低且短暂不可用影响较小的场景

  2. 等待策略：

    • 当检测到时钟回拨时，算法等待直到当前时间追上之前记录的最大时间
    • 适用于回拨时间较短的情况，但如果回拨时间较长，会导致服务长时间不可用

  3. 时间回拨容忍度：

    • 设置一个可容忍的回拨时间阈值（如5毫秒）
    • 当回拨时间在阈值内，使用上一次的时间戳

  4. 备用位方案：

    • 使用序列号中的部分位作为回拨位
    • 当发生时钟回拨时，回拨位加1，序列号清零
    • 这种方法可以容忍一定次数的时钟回拨

  5. 外部时间源：

    • 使用外部时间源如数据库或专门的时间服务器
    • 减少对本地时钟的依赖

2. 机器ID分配问题

2.1 问题描述

在分布式环境中，如何确保每台机器分配到唯一的机器ID是一个挑战，特别是在动态扩缩容的云环境中。

2.2 解决方案

  1. 配置文件分配：

    • 通过配置文件为每台机器静态分配ID
    • 简单但不适合频繁变动的环境

  2. 中心化分配：

    • 使用ZooKeeper、Etcd等分布式协调服务动态分配机器ID
    • 机器启动时向中心服务申请ID，关闭时释放
    • 适合动态变化的环境

  3. 网络标识分配：

    • 基于机器的IP、MAC地址等网络标识生成机器ID
    • 需要确保生成的ID在指定位数内且唯一

  4. 数据库分配：

    • 使用数据库表记录和分配机器ID
    • 需要考虑数据库可用性问题

3. 时间位数与系统使用寿命

3.1 问题描述

标准雪花算法使用41位表示时间戳，可以使用约69年。但在某些特殊场景下，可能需要调整时间位数。

3.2 解决方案

  1. 自定义起始时间：

    • 选择接近系统上线时间的时间点作为起始时间
    • 最大化算法的可用时间范围

  2. 调整位分配：

    • 根据业务需求，调整时间戳、机器ID和序列号的位数分配
    • 例如，减少机器ID位数，增加时间戳位数

  3. 定期迁移策略：

    • 制定长期迁移计划，在算法接近使用寿命时进行系统升级

4. 性能与并发问题

4.1 问题描述

在高并发环境下，如何确保雪花算法的性能和ID生成的唯一性是一个挑战。

4.2 解决方案

  1. 序列号缓冲区：

    • 使用缓冲区预先生成一批ID
    • 减少实时生成的压力

  2. 多级缓存：

    • 实现多级缓存机制，减少锁竞争
    • 提高并发性能

  3. 异步生成：

    • 使用异步方式生成ID
    • 适用于对ID生成实时性要求不高的场景

  4. 批量生成：

    • 支持一次请求生成多个ID
    • 减少网络交互次数

5. 安全性考虑

5.1 问题描述

标准雪花算法生成的ID包含时间信息和机器信息，在某些场景下可能存在信息泄露风险。

5.2 解决方案

  1. ID混淆：

    • 对生成的ID进行加密或混淆处理
    • 防止通过ID反推系统信息

  2. 非连续ID：

    • 引入随机因子，使生成的ID不完全连续
    • 增加ID的不可预测性

  3. 业务分离：

    • 对敏感业务使用独立的ID生成策略
    • 降低信息泄露的影响范围

6. 分布式部署最佳实践

  1. 合理规划数据中心和机器ID：

    • 预留足够的扩展空间
    • 考虑未来的扩容需求

  2. 监控时钟偏移：

    • 定期检查和记录服务器时钟偏移情况
    • 设置时钟偏移告警机制

  3. 高可用部署：

    • 部署多个ID生成服务实例
    • 实现负载均衡和故障转移

  4. 定期演练：

    • 模拟时钟回拨等异常情况
    • 验证系统的容错能力

  5. 完善的监控和日志：

    • 记录ID生成的关键指标
    • 便于问题排查和性能优化

通过合理应对这些挑战并采用最佳实践，可以确保雪花算法在分布式系统中稳定、高效地生成全局唯一ID。

三、雪花算法的实际应用案例

雪花算法在实际应用中已经被广泛采用，许多知名公司和开源项目都基于雪花算法实现了自己的分布式ID生成方案。

  • Twitter作为雪花算法的发明者，自然是最早的应用者。他们使用雪花算法为Twitter平台上的每条推文、每个用户操作生成唯一ID，支撑了海量数据的处理需求。

  • 百度的UidGenerator是基于雪花算法的开源实现，它对原始算法进行了一系列优化，包括更高效的时钟回拨处理、RingBuffer缓冲区设计等，提高了ID生成的性能和可靠性。

  • 美团的Leaf系统提供了两种ID生成方案：基于号段模式的分布式ID生成和基于雪花算法的分布式ID生成。其中，雪花算法部分针对时钟回拨问题进行了特殊处理，增强了系统的稳定性。

  • 滴滴的TinyID也是一个基于雪花算法的分布式ID生成系统，它支持多种发号模式，并提供了REST API和SDK等多种接入方式，方便不同系统集成使用。

这些实际应用案例表明，雪花算法已经成为分布式ID生成领域的主流解决方案，并在实践中不断演进和完善。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.pswp.cn/news/907892.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

第1章：走进Golang

第1章：走进Golang

第1章&#xff1a;走进Golang 一、Golang简介 Go语言&#xff08;又称Golang&#xff09;是由Google的Robert Griesemer、Rob Pike及Ken Thompson开发的一种开源编程语言。它诞生于2007年&#xff0c;2009年11月正式开源。Go语言的设计初衷是为了在不损失应用程序性能的情况下…
阅读更多...
Higress项目解析（二）：Proxy-Wasm Go SDK

Higress项目解析（二）：Proxy-Wasm Go SDK

3、Proxy-Wasm Go SDK Proxy-Wasm Go SDK 依赖于 tinygo&#xff0c;同时 Proxy - Wasm Go SDK 是基于 Proxy-Wasm ABI 规范使用 Go 编程语言扩展网络代理&#xff08;例如 Envoy&#xff09;的 SDK&#xff0c;而 Proxy-Wasm ABI 定义了网络代理和在网络代理内部运行的 Wasm …
阅读更多...
NVMe IP现状扫盲

NVMe IP现状扫盲

SSD优势 与机械硬盘&#xff08;Hard Disk Driver, HDD&#xff09;相比&#xff0c;基于Flash的SSD具有更快的数据随机访问速度、更快的传输速率和更低的功耗优势&#xff0c;已经被广泛应用于各种计算领域和存储系统。SSD最初遵循为HDD设计的现有主机接口协议&#xff0c;例…
阅读更多...
`docker commit` 和 `docker save`区别

`docker commit` 和 `docker save`区别

理解 docker commit 和 docker save 之间的区别对于正确管理 Docker 镜像非常重要。让我们详细解释一下这两个命令的作用及其区别。 1. docker commit 作用&#xff1a; docker commit roop-builder roop:v1 命令的作用是基于一个正在运行的容器 roop-builder 创建一个新的镜…
阅读更多...
Linux内核体系结构简析

Linux内核体系结构简析

1.Linux内核 1.1 Linux内核的任务 从技术层面讲&#xff0c;内核是硬件和软件之间的一个中间层&#xff0c;作用是将应用层序的请求传递给硬件&#xff0c;并充当底层驱动程序&#xff0c;对系统中的各种设备和组件进行寻址。从应用程序的角度讲&#xff0c;应用程序与硬件没有…
阅读更多...
python爬虫：Ruia的详细使用（一个基于asyncio和aiohttp的异步爬虫框架）

python爬虫：Ruia的详细使用（一个基于asyncio和aiohttp的异步爬虫框架）

更多内容请见： 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Ruia概述1.1 Ruia介绍1.2 Ruia特点1.3 安装Ruia1.4 使用案例二、基本使用2.1 Request 请求2.2 Response - 响应2.3 Item - 数据提取2.4 Field 提取数据2.5 Spider - 爬虫类2.6 Middleware - 中间件三、高级功能3.1 …
阅读更多...
网络攻防技术二：密码学分析

网络攻防技术二：密码学分析

文章目录 一、传统密码分析方法1、根据明文、密文等信息的掌握情况分类 2、从密码分析途径分类二、密码旁路分析1、概念2、旁路分析方法三、现代密码系统1、对称密码&#xff08;单密钥&#xff09;2、公开密码&#xff08;成对密钥&#xff09; 四、典型对称密码&#xff08;单…
阅读更多...
Linux --TCP协议实现简单的网络通信（中英翻译）

Linux --TCP协议实现简单的网络通信（中英翻译）

一、什么是TCP协议 1.1 、TCP是传输层的协议&#xff0c;TCP需要连接&#xff0c;TCP是一种可靠性传输协议&#xff0c;TCP是面向字节流的传输协议&#xff1b; 二、TCPserver端的搭建 2.1、我们最终好实现的效果是 客户端在任何时候都能连接到服务端&#xff0c;然后向服务…
阅读更多...
pc端小卡片功能-原生JavaScript金融信息与节日日历

pc端小卡片功能-原生JavaScript金融信息与节日日历

代码如下 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>金融信息与节日日历</title><…
阅读更多...
C语言——获取变量所在地址（uint8和uint32的区别）

C语言——获取变量所在地址（uint8和uint32的区别）

前言&#xff1a; 1.使用uint8 *的原因 在C语言中&#xff0c;获取或操作一个4字节地址&#xff08;指针&#xff09;时使用uint8_t*&#xff08;即unsigned char*&#xff09;而不是uint32_t*&#xff0c;主要基于以下关键原因&#xff1a; 1.1. 避免违反严格别名规则&…
阅读更多...
Python----目标检测（《YOLOv3:AnIncrementalImprovement》和YOLO-V3的原理与网络结构）

Python----目标检测（《YOLOv3:AnIncrementalImprovement》和YOLO-V3的原理与网络结构）

一、《YOLOv3:AnIncrementalImprovement》 1.1、基本信息 标题&#xff1a;YOLOv3: An Incremental Improvement 作者&#xff1a;Joseph Redmon, Ali Farhadi 机构&#xff1a;华盛顿大学&#xff08;University of Washington&#xff09; 发表时间&#xff1a;2018年 代…
阅读更多...
50天50个小项目 (Vue3 + Tailwindcss V4) ✨ | Form Wave（表单label波动效果）

50天50个小项目 (Vue3 + Tailwindcss V4) ✨ | Form Wave（表单label波动效果）

&#x1f4c5; 我们继续 50 个小项目挑战&#xff01;—— FormWave组件 仓库地址&#xff1a;https://github.com/SunACong/50-vue-projects 项目预览地址&#xff1a;https://50-vue-projects.vercel.app/ &#x1f3af; 组件目标 构建一个美观、动态的登录表单&#xff0…
阅读更多...
【数据结构】--二叉树--堆(上)

【数据结构】--二叉树--堆(上)

一、树的概念和结构 概念&#xff1a; 树是一种非线性的数据结构&#xff0c;他是由n(n>0)个有限结点组成一个具有层次关系的集合。其叫做树&#xff0c;是因为他倒过来看就和一棵树差不多&#xff0c;其实际上是根在上&#xff0c;树枝在下的。 树的特点&#xff1a; 1…
阅读更多...
linux有效裁剪视频的方式(基于ffmpeg，不改变分辨率，帧率，视频质量，不需要三方软件)

linux有效裁剪视频的方式(基于ffmpeg，不改变分辨率，帧率，视频质量，不需要三方软件)

就是在Linux上使用OBS Studio录制一个讲座或者其他视频&#xff0c;可能总有些时候会多录制一段时间&#xff0c;但是如果使用剪映或者PR这样的工具在导出的时候总需要烦恼导出的格式和参数&#xff0c;比如剪映就不支持mkv格式的导出&#xff0c;导出成mp4格式的视频就会变得很…
阅读更多...
SystemVerilog—Interface语法（一）

SystemVerilog—Interface语法（一）

SystemVerilog中的接口&#xff08;interface&#xff09;是一种用于封装多模块间通信信号和协议的复合结构&#xff0c;可显著提升代码复用性和维护效率。其核心语法和功能如下&#xff1a; 一、接口的基本定义 1. 声明语法 接口通过interface关键字定义&#xff0c;支持信…
阅读更多...
android binder（四）binder驱动详解

android binder（四）binder驱动详解

ref&#xff1a; Android10.0 Binder通信原理(五)-Binder驱动分析_binder: 1203:1453 ioctl 40046210 77004d93f4 return-CSDN博客 https://juejin.cn/post/7214342319347712057#heading-0 第6课第1节_Binder系统_驱动情景分析_数据结构_哔哩哔哩_bilibili
阅读更多...
QT/c++航空返修数据智能分析系统

QT/c++航空返修数据智能分析系统

简介 1、区分普通用户和管理员 2、界面精美 3、功能丰富 4、使用cppjieba分词分析数据 5、支持数据导入导出 6、echarts展示图表 效果展示 演示链接 源码获取 int main(){ //非白嫖 printf("&#x1f4e1;:%S","joyfelic"); return 0; }
阅读更多...
ToolsSet之：数值提取及批处理

ToolsSet之：数值提取及批处理

ToolsSet是微软商店中的一款包含数十种实用工具数百种细分功能的工具集合应用&#xff0c;应用基本功能介绍可以查看以下文章&#xff1a; Windows应用ToolsSet介绍https://blog.csdn.net/BinField/article/details/145898264 ToolsSet中Number菜单下的Numeric Batch是一个数…
阅读更多...
Ubuntu20.04 LTS 升级Ubuntu22.04LTS 依赖错误 系统崩溃重装 Ubuntu22.04 LTS

Ubuntu20.04 LTS 升级Ubuntu22.04LTS 依赖错误 系统崩溃重装 Ubuntu22.04 LTS

服务器系统为PowerEdge R740 BIOS Version 2.10.2 DELL EMC 1、关机 开机时连续按键盘F2 2、System Setup选择第一个 System BIOS 3、System BIOS Setting 选择 Boot Setting 4、System BIOS Setting-Boot Setting 选择 BIOS Boot Settings 5、重启 开启时连续按键盘F11 …
阅读更多...
（javaSE）Java数组进阶：数组初始化 数组访问 数组中的jvm 空指针异常

（javaSE）Java数组进阶：数组初始化 数组访问 数组中的jvm 空指针异常

数组的基础 什么是数组呢? 数组指的是一种容器,可以用来存储同种数据类型的多个值 数组的初始化 初始化&#xff1a;就是在内存中,为数组容器开辟空间,并将数据存入容器中的过程。 数组初始化的两种方式&#xff1a;静态初始化&#xff0c;动态初始化 数组的静态初始化 初始化…
阅读更多...
最新文章

Copyright @ 2022~2023