分布式 ID 生成器（CosId）设计与实现

CosId 简介

CosId 旨在提供通用、灵便、高性能的分布式 ID 生成器。目前提供了俩类 ID 生成器：

• SnowflakeId : 单机 TPS 性能：409W/s JMH 基准测试 , 次要解决 时钟回拨问题 、 机器号调配问题 并且提供更加敌对、灵便的应用体验。

• SegmentId: 每次获取一段 (Step) ID，来升高号段散发器的网络 IO 申请频次晋升性能。

  • IdSegmentDistributor: 号段散发器（号段存储器）

    • RedisIdSegmentDistributor: 基于 Redis 的号段散发器。
    • JdbcIdSegmentDistributor: 基于 Jdbc 的号段散发器，反对各种关系型数据库。

  • SegmentChainId(举荐):SegmentChainId (lock-free) 是对 SegmentId 的加强。性能可达到近似 AtomicLong 的 TPS 性能:12743W+/s JMH 基准测试。

    • PrefetchWorker 保护平安间隔 (safeDistance), 并且反对基于饥饿状态的动静safeDistance 扩容 / 膨胀。

背景（为什么须要 分布式 ID）

在软件系统演进过程中，随着业务规模的增长，咱们须要进行集群化部署来摊派计算、存储压力，应用服务咱们能够很轻松做到无状态、弹性伸缩。
然而仅仅减少服务正本数就够了吗？显然不够，因为性能瓶颈往往是在数据库层面，那么这个时候咱们就须要思考如何进行数据库的扩容、伸缩、集群化，通常应用分库、分表的形式来解决。
那么我如何分片 (程度分片，当然还有垂直分片不过不是本文须要探讨的内容) 呢，分片得前提是咱们得先有一个 ID，而后能力依据分片算法来分片。（比方比较简单罕用的 ID 取模分片算法，这个跟 Hash 算法的概念相似，咱们得先有 key 能力进行 Hash 获得插入槽位。）

当然还有很多分布式场景须要 分布式 ID，这里不再一一列举。

分布式 ID 计划的外围指标

• 全局（雷同业务）唯一性 ：唯一性保障是ID 的必要条件，假如 ID 不惟一就会产生主键抵触，这点很容易能够了解。

  • 通常所说的全局唯一性并不是指所有业务服务都要惟一，而是雷同业务服务不同部署正本惟一。
    比方 Order 服务的多个部署正本在生成 t_order 这张表的 Id 时是要求全局惟一的。至于 t_order_item 生成的 ID 与t_order是否惟一，并不影响唯一性束缚，也不会产生什么副作用。
    不同业务模块间也是同理。即唯一性次要解决的是 ID 抵触问题。

• 有序性 ：有序性保障是面向查问的数据结构算法（除了 Hash 算法）所必须的，是 二分查找法 (分而治之) 的前提。

  • MySq-InnoDB B+ 树是应用最为宽泛的，假如 Id 是无序的，B+ 树 为了保护 ID 的有序性，就会频繁的在索引的两头地位插入而移动前面节点的地位，甚至导致频繁的页决裂，这对于性能的影响是极大的。那么如果咱们可能保障 ID 的有序性这种状况就齐全不同了，只须要进行追加写操作。所以 ID 的有序性是十分重要的，也是 ID 设计不可避免的个性。

• 吞吐量 / 性能(ops/time)：即单位工夫（每秒）能产生的 ID 数量。生成 ID 是十分高频的操作，也是最为根本的。假如 ID 生成的性能迟缓，那么不管怎么进行系统优化也无奈取得更好的性能。

  • 个别咱们会首先生成 ID，而后再执行写入操作，假如 ID 生成迟缓，那么整体性能下限就会受到限制，这一点应该不难理解。

• 稳定性 (time/op)：稳定性指标个别能够采纳 每个操作的工夫进行百分位采样 来剖析，比方 CosId 百分位采样 P9999=0.208 us/op，即 0% ~ 99.99% 的单位操作工夫小于等于 0.208 us/op。

  • 百分位数 WIKI：统计学术语，若将一组数据从小到大排序，并计算相应的累计百分点，则某百分点所对应数据的值，就称为这百分点的百分位数，以 Pk 示意第 k 百分位数。百分位数是用来比拟个体在群体中的绝对位置量数。
  • 为什么不必均匀 每个操作的工夫：马老师的身价跟你的身价能均匀么？均匀后的值有意义不？
  • 能够应用最小 每个操作的工夫 、最大 每个操作的工夫 作为参考吗？因为最小、最大值只阐明了零界点的状况，虽说能够作为稳定性的参考，但仍然不够全面。而且 百分位数 曾经笼罩了这俩个指标。
• 自治性（依赖）：次要是指对外部环境有无依赖，比方 号段模式 会强依赖第三方存储中间件来获取NexMaxId。自治性还会对可用性造成影响。

• 可用性 ：分布式 ID 的可用性次要会受到自治性影响，比方SnowflakeId 会受到时钟回拨影响，导致处于短暂工夫的不可用状态。而 号段模式 会受到第三方发号器（NexMaxId）的可用性影响。

  • 可用性 WIKI：在一个给定的工夫距离内，对于一个性能个体来讲，总的可用工夫所占的比例。
  • MTBF：均匀故障距离
  • MDT：均匀修复 / 复原工夫
  • Availability=MTBF/(MTBF+MDT)
  • 假如 MTBF 为 1 年，MDT 为 1 小时，即Availability=(365*24)/(365*24+1)=0.999885857778792≈99.99%，也就是咱们通常所说对可用性 4 个 9。

• 适应性：是指在面对外部环境变动的自适应能力，这里咱们次要说的是面对流量突发时动静伸缩分布式 ID 的性能，

  • SegmentChainId能够基于 饥饿状态 进行 平安间隔 的动静伸缩。
  • SnowflakeId惯例位调配计划性能恒定 409.6W，尽管能够通过调整位调配计划来取得不同的 TPS 性能，然而位调配办法的变更是破坏性的，个别依据业务场景确定位调配计划后不再变更。
• 存储空间：还是用 MySq-InnoDB B+ 树来举例，一般索引（二级索引）会存储主键值，主键越大占用的内存缓存、磁盘空间也会越大。Page 页存储的数据越少，磁盘 IO 拜访的次数会减少。总之在满足业务需要的状况下，尽可能小的存储空间占用在绝大多数场景下都是好的设计准则。

不同分布式 ID 计划外围指标比照

有序性(要想分而治之·二分查找法，必须要保护我)

刚刚咱们曾经探讨了 ID 有序性的重要性，所以咱们设计 ID 算法时应该尽可能地让 ID 是枯燥递增的，比方像表的自增主键那样。然而很遗憾，因全局时钟、性能等分布式系统问题，咱们通常只能抉择部分枯燥递增、全局趋势递增的组合（就像咱们在分布式系统中不得不的抉择最终一致性那样）以取得多方面的衡量。上面咱们来看一下什么是枯燥递增与趋势递增。

有序性之枯燥递增

枯燥递增：T 示意全局相对时点，假如有 T _n+1>T_n（相对工夫总是往后退的，这里不思考相对论、时间机器等），那么必然有 F(T_n+1)>F(T_n)，数据库自增主键就属于这一类。
另外须要特地阐明的是枯燥递增跟连续性递增是不同的概念。连续性递增：F(n+1)=(F(n)+step)即下一次获取的 ID 肯定等于以后 ID+Step，当Step=1 时相似于这样一个序列:1->2->3->4->5。

扩大小常识：数据库的自增主键也不是连续性递增的，置信你肯定遇到过这种状况，请思考一下数据库为什么这样设计？

有序性之趋势递增

趋势递增：T_n>T_n-s，那么大概率有 F(T_n)>F(T_n-s)。尽管在一段时间距离内有乱序，然而整体趋势是递增。从上图上看，是有回升趋势的（趋势线）。

• 在 SnowflakeId 中_n-s受到全局时钟同步影响。
• 在号段模式 (SegmentId) 中_n-s受到号段可用区间 (Step) 影响。

分布式 ID 调配计划

UUID/GUID

• 👍 不依赖任何第三方中间件
• 👍 性能高
• 👎 齐全无序
• 👎 空间占用大，须要占用 128 位存储空间。

UUID 最大的缺点是随机的、无序的，当用于主键时会导致数据库的主键索引效率低下（为了保护索引树，频繁的索引两头地位插入数据，而不是追加写）。这也是 UUID 不适用于数据库主键的最为重要的起因。

SnowflakeId

SnowflakeId应用 Long（64-bit）位分区来生成 ID 的一种分布式 ID 算法。
通用的位调配计划为：timestamp(41-bit)+machineId(10-bit)+sequence(12-bit)=63-bit。

• 41-bittimestamp=(1L<<41)/(1000/3600/365)，约能够存储 69 年的工夫戳，即能够应用的相对工夫为 EPOCH+69 年，个别咱们须要自定义EPOCH 为产品开发工夫，另外还能够通过压缩其余区域的调配位数，来减少工夫戳位数来缩短可用工夫。
• 10-bitmachineId=(1L<<10)=1024，即雷同业务能够部署 1024 个正本(在 Kubernetes 概念里没有主从正本之分，这里间接沿用 Kubernetes 的定义)。个别状况下没有必要应用这么多位，所以会依据部署规模须要从新定义。
• 12-bitsequence=(1L<<12)*1000=4096000，即单机每秒可生成约 409W 的 ID，全局同业务集群可产生4096000*1024=419430W=41.9 亿(TPS)。

从 SnowflakeId 设计上能够看出:

• 👍 timestamp在高位，单实例 SnowflakeId 是会保障时钟总是向前的（校验本机时钟回拨），所以是本机枯燥递增的。受全局时钟同步 / 时钟回拨影响 SnowflakeId 是全局趋势递增的。
• 👍 SnowflakeId不对任何第三方中间件有强依赖关系，并且性能也十分高。
• 👍 位调配计划能够依照业务零碎须要灵便配置，来达到最优应用成果。
• 👎 强依赖本机时钟，潜在的时钟回拨问题会导致 ID 反复、处于短暂的不可用状态。
• 👎 machineId须要手动设置，理论部署时如果采纳手动调配machineId，会十分低效。

SnowflakeId 之机器号调配问题

在 SnowflakeId 中依据业务设计的位调配计划确定了基本上就不再有变更了，也很少须要保护。然而 machineId 总是须要配置的，而且集群中是不能反复的，否则分区准则就会被毁坏而导致 ID 唯一性准则毁坏，当集群规模较大时 machineId 的保护工作是十分繁琐，低效的。

有一点须要特地阐明的，SnowflakeId的 MachineId 是逻辑上的概念，而不是物理概念。
设想一下假如 MachineId 是物理上的，那么意味着一台机器领有只能领有一个MachineId，那会产生什么问题呢？

目前 CosId 提供了以下三种 MachineId 分配器。

• ManualMachineIdDistributor: 手动配置machineId，个别只有在集群规模十分小的时候才有可能应用，不举荐。
• StatefulSetMachineIdDistributor: 应用 Kubernetes 的StatefulSet提供的稳固的标识 ID（HOSTNAME=service-01）作为机器号。
• RedisMachineIdDistributor: 应用 Redis 作为机器号的散发存储，同时还会存储 MachineId 的上一次工夫戳，用于 启动时时钟回拨 的查看。

SnowflakeId 之时钟回拨问题

时钟回拨的致命问题是会导致 ID 反复、抵触（这一点不难理解），ID 反复显然是不能被容忍的。
在 SnowflakeId 算法中，依照 MachineId 分区 ID，咱们不难理解的是不同 MachineId 是不可能产生雷同 ID 的。所以咱们解决的时钟回拨问题是指以后 MachineId 的时钟回拨问题，而不是所有集群节点的时钟回拨问题。

MachineId时钟回拨问题大体能够分为俩种状况：

• 运行时时钟回拨：即在运行时获取的以后工夫戳比上一次获取的工夫戳小。这个场景的时钟回拨是很容易解决的，个别 SnowflakeId 代码实现时都会存储 lastTimestamp 用于运行时时钟回拨的查看，并抛出时钟回拨异样。

  • 时钟回拨时间接抛出异样是不太好地实际，因为上游应用方简直没有其余解决计划（噢，我还能怎么办呢，等吧），时钟同步是惟一的抉择，当只有一种抉择时就不要再让用户抉择了。
  • ClockSyncSnowflakeId是 SnowflakeId 的包装器，当产生时钟回拨时会应用 ClockBackwardsSynchronizer 被动期待时钟同步来从新生成 ID，提供更加敌对的应用体验。

• 启动时时钟回拨：即在启动服务实例时获取的以后时钟比上次敞开服务时小。此时的 lastTimestamp 是无奈存储在过程内存中的。当获取的内部存储的 机器状态 大于以后时钟时钟时，会应用 ClockBackwardsSynchronizer 被动同步时钟。

  • LocalMachineStateStorage：应用本地文件存储 MachineState(机器号、最近一次工夫戳)。因为应用的是本地文件所以只有当实例的部署环境是稳固的，LocalMachineStateStorage 才实用。
  • RedisMachineIdDistributor：将 MachineState 存储在 Redis 分布式缓存中，这样能够保障总是能够获取到上次服务实例停机时 机器状态。

SnowflakeId 之 JavaScript 数值溢出问题

JavaScript的 Number.MAX_SAFE_INTEGER 只有 53-bit，如果间接将 63 位的 SnowflakeId 返回给前端，那么会产生值溢出的状况（所以这里咱们应该晓得后端传给前端的 long 值溢出问题，迟早 会呈现，只不过 SnowflakeId 呈现得更快而已）。
很显然溢出是不能被承受的，个别能够应用以下俩种解决计划：

• 将生成的 63-bitSnowflakeId转换为 String 类型。

  • 间接将 long 转换成String。
  • 应用 SnowflakeFriendlyId 将SnowflakeId转换成比拟敌对的字符串示意：{timestamp}-{machineId}-{sequence} -> 20210623131730192-1-0

• 自定义 SnowflakeId 位调配来缩短 SnowflakeId 的位数（53-bit）使 ID 提供给前端时不溢出

  • 应用SafeJavaScriptSnowflakeId(JavaScript 平安的 SnowflakeId)

号段模式（SegmentId）

从下面的设计图中，不难看出 号段模式 根本设计思路是通过每次获取肯定长度（Step）的可用 ID（Id 段 / 号段），来升高网络 IO 申请次数，晋升性能。

• 👎 强依赖第三方号段散发器，可用性受到第三方散发器影响。
• 👎 每次号段用完时获取 NextMaxId 须要进行网络 IO 申请，此时的性能会比拟低。

• 单实例 ID 枯燥递增，全局趋势递增。

  • 从设计图中不难看出 Instance 1 每次获取的NextMaxId，肯定比上一次大，意味着下一次的号段肯定比上一次大，所以从单实例上来看是枯燥递增的。
  • 多实例各自持有的不同的号段，意味着同一时刻不同实例生成的 ID 是乱序的，然而整体趋势的递增的，所以全局趋势递增。

• ID 乱序水平受到 Step 长度以及集群规模影响（从趋势递增图中不难看出）。

  • 假如集群中只有一个实例时 号段模式 就是枯燥递增的。

  • Step越小，乱序水平越小。当 Step=1 时，将有限靠近枯燥递增。须要留神的是这里是有限靠近而非等于枯燥递增，具体起因你能够思考一下这样一个场景：

    • 号段散发器 T ₁时刻给 Instance 1 散发了 ID=1,T₂ 时刻给 Instance 2 散发了 ID=2。因为机器性能、网络等起因，Instance 2 网络 IO 写申请先于 Instance 1 达到。那么这个时候对于数据库来说，ID 仍然是乱序的。

号段链模式（SegmentChainId）

SegmentChainId是 SegmentId 增强版，相比于 SegmentId 有以下劣势：

• 稳定性：SegmentId的稳定性问题（P9999=46.624(us/op)）次要是因为号段用完之后同步进行 NextMaxId 的获取导致的（会产生网络 IO）。

  • SegmentChainId（P9999=0.208(us/op)）引入了新的角色 PrefetchWorker 用以保护和保障 平安间隔 ，现实状况下使得获取 ID 的线程简直齐全不须要进行同步的期待NextMaxId 获取，性能可达到近似 AtomicLong 的 TPS 性能:12743W+/s JMH 基准测试。

• 适应性：从 SegmentId 介绍中咱们晓得了影响 ID 乱序 的因素有俩个：集群规模、Step大小。集群规模是咱们不能管制的，然而 Step 是能够调节的。

  • Step应该近可能小能力使得 ID 枯燥递增 的可能性增大。
  • Step太小会影响吞吐量，那么咱们如何正当设置 Step 呢？答案是咱们无奈精确预估所有时点的吞吐量需要，那么最好的方法是吞吐量需要高时，Step 主动增大，吞吐量低时 Step 主动膨胀。
  • SegmentChainId引入了 饥饿状态 的概念，PrefetchWorker会依据 饥饿状态 检测以后 平安间隔 是否须要收缩或者膨胀，以便取得吞吐量与有序性之间的衡量，这便是 SegmentChainId 的自适应性。

SegmentChainId- 吞吐量 (ops/s)

MySqlChainIdBenchmark-Throughput

SegmentChainId- 每次操作耗时的百分位数(us/op)

MySqlChainIdBenchmark-Percentile

基准测试报告运行环境阐明

• 基准测试运行环境：笔记本开发机(MacBook-Pro-(M1))
• 所有基准测试都在开发笔记本上执行。