分布式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 的加强。性能可达到近似 AtomicLongTPS 性能:12743W+/s JMH 基准测试 。

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

背景(为什么须要分布式ID

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

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

分布式ID计划的外围指标

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

    • 通常所说的全局唯一性并不是指所有业务服务都要惟一,而是雷同业务服务不同部署正本惟一。
      比方 Order 服务的多个部署正本在生成t_order这张表的Id时是要求全局惟一的。至于t_order_item生成的IDt_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全局唯一性有序性吞吐量稳定性(1s=1000,000us)自治性可用性适应性存储空间
UUID/GUID齐全无序3078638(ops/s)P9999=0.325(us/op)齐全自治100%128-bit
SnowflakeId本地枯燥递增,全局趋势递增(受全局时钟影响)4096000(ops/s)P9999=0.244(us/op)依赖时钟时钟回拨会导致短暂不可用64-bit
SegmentId本地枯燥递增,全局趋势递增(受Step影响)29506073(ops/s)P9999=46.624(us/op)依赖第三方号段散发器受号段散发器可用性影响64-bit
SegmentChainId本地枯燥递增,全局趋势递增(受Step、平安间隔影响)127439148(ops/s)P9999=0.208(us/op)依赖第三方号段散发器受号段散发器可用性影响,但因平安间隔存在,预留ID段,所以高于SegmentId64-bit

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

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

有序性之枯燥递增

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

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

有序性之趋势递增

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

  • SnowflakeIdn-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的保护工作是十分繁琐,低效的。

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

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

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

SnowflakeId之时钟回拨问题

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

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

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

    • 时钟回拨时间接抛出异样是不太好地实际,因为上游应用方简直没有其余解决计划(噢,我还能怎么办呢,等吧),时钟同步是惟一的抉择,当只有一种抉择时就不要再让用户抉择了。
    • ClockSyncSnowflakeIdSnowflakeId的包装器,当产生时钟回拨时会应用ClockBackwardsSynchronizer被动期待时钟同步来从新生成ID,提供更加敌对的应用体验。
  • 启动时时钟回拨:即在启动服务实例时获取的以后时钟比上次敞开服务时小。此时的lastTimestamp是无奈存储在过程内存中的。当获取的内部存储的机器状态大于以后时钟时钟时,会应用ClockBackwardsSynchronizer被动同步时钟。

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

SnowflakeId之JavaScript数值溢出问题

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

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

    • 间接将long转换成String
    • 应用SnowflakeFriendlyIdSnowflakeId转换成比拟敌对的字符串示意:{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时,将有限靠近枯燥递增。须要留神的是这里是有限靠近而非等于枯燥递增,具体起因你能够思考一下这样一个场景:

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

号段链模式(SegmentChainId)

SegmentChainIdSegmentId增强版,相比于SegmentId有以下劣势:

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

    • SegmentChainId (P9999=0.208(us/op))引入了新的角色PrefetchWorker用以保护和保障平安间隔,现实状况下使得获取ID的线程简直齐全不须要进行同步的期待NextMaxId获取,性能可达到近似 AtomicLongTPS 性能: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))
  • 所有基准测试都在开发笔记本上执行。