type
status
date
slug
summary
tags
category
icon
password
Sub-item
Last edited time
Oct 29, 2023 02:55 AM
Parent item
领域
在分布式的服务系统中，例如有多个分布式服务都需要对同一个数据表进行插入操作，如何保证唯一主键ID不冲突，并能满足单向递增等要求。
此时要求每个服务要求获取到的ID具有如下特性：
- 全局唯一ID
在复杂分布式系统中，需要对大量的数据和消息进行全局唯一ID标识。
- 趋势递增
使用有序的主键能够保证写入数据库的性能。在MySQL InnoDB引擎中使用的是聚集索引，由于多数RDBMS使用B+tree的数据结构来存储索引数据，因此主键应该尽量有序递增
- 单调递增
保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求。
- 不能连续
ID不能连续，防止被恶意扒取。所以在一些应用场景下，会需要ID无规则、不规则。
- 可用性要求高
ID号生成系统的可用性要求极高，可用性5个9；如果ID生成系统瘫痪，整个美团点评支付、优惠券发券、骑手派单等关键动作都无法执行，这就会带来一场灾难。
- 生成延时低
平均延迟和TP999延迟都要尽可能低；
- 高QPS。
至少需要百万级
雪花算法
SnowFlake算法生成ID的结果是一个64bit大小的整数，结构如下图：
- 第一个部分：1个bit，无意义，固定为0。二进制中最高位是符号位，1表示负数，0表示正数。ID都是正整数，所以固定为0。
- 第二个部分：41个bit，表示时间戳，精确到毫秒，可以使用69年。时间戳带有自增属性。
- 第三个部分：10个bit，表示10位的机器标识，最多支持1024个节点。此部分也可拆分成5位
datacenterId和5位workerId，datacenterId表示机房ID，workerId表示机器ID。
- 第四部分：12个bit，表示序列化，即一些列的自增ID，可以支持同一节点同一毫秒生成最多4095个ID序号。
毫秒内初始 id 随机生成可以有效避免逆向工程导致 id 的可推测性。具体开发时通过可配置参数决定是否启用单位毫秒内随机生成起始 ID。随机生成的起始 ID 可能很大，会很快到达单位毫秒内的最大值，比如 4095（12 位序列号情况下），所以需要对 4095 处理，比如取模、或者和二进制位数&运算 循环使用单位毫秒内的可用数字，避免浪费。
存在的问题：
- 机器ID（5位）和数据中心ID（5位）配置没有解决，分布式部署的时候会使用相同的配置，任然有ID重复的风险。
- 使用的时候需要实例化对象，没有形成开箱即用的工具类。
- 强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。（这点在正常情况下是不会发生的）
雪花漂移算法
需求
💧 作为架构设计的你，想要解决数据库主键唯一的问题，特别是在分布式系统多数据库中。
💧 你希望数据表主键用最少的存储空间，索引速度更快，Select、Insert 和 Update 更迅速。
💧 你要考虑在分库分表（合库合表）时，主键值可直接使用，并能反映业务时序。
💧 如果这样的主键值太长，超过前端 js Number 类型最大值，须把 Long 型转换为 String 型，你会觉得有点沮丧。
💧 尽管 Guid 能自增，但占用空间大，索引速度慢，你不想用它。
💧 应用实例可能超过50个，每个并发请求可达10W/s。
💧 要在容器环境部署应用，支持水平复制、自动扩容。
💧 不想依赖 redis 的自增操作获得连续的主键ID，因为连续的ID存在业务数据安全风险。
💧 你希望系统运行 100 年以上。
传统雪花算法存在的问题
❌ 生成的ID太长。
❌ 瞬时并发量不够。
❌ 不能解决时间回拨问题。
❌ 不支持后补生成前序ID。
❌ 可能依赖外部存储系统。
雪花漂移算法特点
✔ 整形数字，随时间单调递增（不一定连续），长度更短，用50年都不会超过 js Number类型最大值。（默认配置）
✔ 速度更快，是传统雪花算法的2-5倍，0.1秒可生成50万个（基于8代低压i7）。
✔ 支持时间回拨处理。比如服务器时间回拨1秒，本算法能自动适应生成临界时间的唯一ID。
✔ 支持手工插入新ID。当业务需要在历史时间生成新ID时，用本算法的预留位能生成5000个每秒。
✔ 不依赖任何外部缓存和数据库。（k8s环境下自动注册 WorkerId 的动态库依赖 redis）
✔ 基础功能，开箱即用，无需配置文件、数据库连接等。
🔶 当发生系统时间回拨时，算法采用过去时序的预留序数生成新的ID。
🔶 回拨生成的ID序号，默认靠前，也可以调整为靠后。
🔶 允许时间回拨至本算法预设基数（参数可调）。
ID组成说明
- 本算法生成的ID由3部分组成（沿用雪花算法定义）：
+———————————-+—————+————+
| 1.相对基础时间的时间差 | 2.WorkerId | 3.序列数 |
+———————————+————-—+————+
- 第1部分，时间差，是生成ID时的系统时间减去
BaseTime的总时间差（毫秒单位）。
- 第2部分，
WorkerId，是区分不同机器或不同应用的唯一ID，最大值由WorkerIdBitLength（默认6）限定。
- 第3部分，序列数，是每毫秒下的序列数，由参数中的
SeqBitLength（默认6）限定。
使用示例：