CosId 1.3.9 发布,通用、灵活、高性能的分布式 ID 生成器

栏目: 软件资讯 · 发布时间: 2年前

内容简介:CosId 通用、灵活、高性能的分布式ID生成器 更新内容(1.3.9) :tada: :tada: :tada: 增强: 新增 CosIdAnnotationSupport ,支持基于@CosId注解的ID自动注入。 @Target({ElementType.FIELD}) @Documented @...

CosId 通用、灵活、高性能的分布式ID生成器

更新内容(1.3.9) ???? ???? ????

  • 增强: 新增 CosIdAnnotationSupport ,支持基于@CosId注解的ID自动注入。
    • @Target({ElementType.FIELD})
      @Documented
      @Retention(RetentionPolicy.RUNTIME)
      public @interface CosId {
          String value() default IdGeneratorProvider.SHARE;
      
          boolean friendlyId() default false;
      }
      
      public class Entity {
      
          @CosId
          private long id;
      
          @CosId
          private String stringId;
      
          @CosId(friendlyId = true)
          private String friendlyId;
      
          @CosId(value = "bizC")
          private long bizId;
      
          /**
           * ...
           * getter or setter
           */
      }
      
    • cosIdAnnotationSupport.ensureId(entity);
  • 增强: 新增 CosIdPlugin (cosid-mybatis) ,支持通过注解的方式自动注入分布式ID。
    • @Mapper
      public interface EntityRepository {
          @Insert("insert into t_entity (id,string_id,friendly_id,biz_id) value (#{id},#{stringId},#{friendlyId},#{bizId});")
          void insert(Entity entity);
      
          @Insert({
                  "<script>",
                  "insert into t_entity (id,string_id,friendly_id,biz_id)",
                  "VALUES" +
                          "<foreach item='item' collection='list' open='' separator=',' close=''>" +
                          "(#{item.id},#{item.stringId},#{item.friendlyId},#{item.bizId})" +
                          "</foreach>",
                  "</script>"})
          void insertList(List<Entity> entityList);
      }
      
              Entity entity=new Entity();
              entityRepository.insert(entity);
              /**
               * {
               *   "id": 213044050087903230,
               *   "stringId": "213044050087903233",
               *   "friendlyId": "20210803212059708-0-2",
               *   "bizId": 28801
               * }
               */
              return entity;

简介

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生成的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段,所以高于SegmentId 64-bit

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

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

有序性之单调递增

CosId 1.3.9 发布,通用、灵活、高性能的分布式 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

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

有序性之趋势递增

CosId 1.3.9 发布,通用、灵活、高性能的分布式 ID 生成器

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

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

分布式ID分配方案

UUID/GUID

  • CosId 1.3.9 发布,通用、灵活、高性能的分布式 ID 生成器不依赖任何第三方中间件
  • CosId 1.3.9 发布,通用、灵活、高性能的分布式 ID 生成器性能高
  • CosId 1.3.9 发布,通用、灵活、高性能的分布式 ID 生成器完全无序
  • CosId 1.3.9 发布,通用、灵活、高性能的分布式 ID 生成器空间占用大,需要占用128位存储空间。

UUID最大的缺陷是随机的、无序的,当用于主键时会导致数据库的主键索引效率低下(为了维护索引树,频繁的索引中间位置插入数据,而不是追加写)。这也是UUID不适用于数据库主键的最为重要的原因。

SnowflakeId

CosId 1.3.9 发布,通用、灵活、高性能的分布式 ID 生成器

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 设计上可以看出:

  • CosId 1.3.9 发布,通用、灵活、高性能的分布式 ID 生成器timestamp在高位,单实例SnowflakeId是会保证时钟总是向前的(校验本机时钟回拨),所以是本机单调递增的。受全局时钟同步/时钟回拨影响SnowflakeId是全局趋势递增的。
  • CosId 1.3.9 发布,通用、灵活、高性能的分布式 ID 生成器SnowflakeId不对任何第三方中间件有强依赖关系,并且性能也非常高。
  • CosId 1.3.9 发布,通用、灵活、高性能的分布式 ID 生成器位分配方案可以按照业务系统需要灵活配置,来达到最优使用效果。
  • CosId 1.3.9 发布,通用、灵活、高性能的分布式 ID 生成器强依赖本机时钟,潜在的时钟回拨问题会导致ID重复、处于短暂的不可用状态。
  • CosId 1.3.9 发布,通用、灵活、高性能的分布式 ID 生成器machineId需要手动设置,实际部署时如果采用手动分配machineId,会非常低效。

SnowflakeId之机器号分配问题

SnowflakeId中根据业务设计的位分配方案确定了基本上就不再有变更了,也很少需要维护。但是machineId总是需要配置的,而且集群中是不能重复的,否则分区原则就会被破坏而导致ID唯一性原则破坏,当集群规模较大时machineId的维护工作是非常繁琐,低效的。

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

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

  • ManualMachineIdDistributor: 手动配置machineId,一般只有在集群规模非常小的时候才有可能使用,不推荐。
  • StatefulSetMachineIdDistributor: 使用KubernetesStatefulSet提供的稳定的标识ID(HOSTNAME=service-01)作为机器号。
  • RedisMachineIdDistributor: 使用Redis作为机器号的分发存储,同时还会存储MachineId的上一次时间戳,用于启动时时钟回拨的检查。

CosId 1.3.9 发布,通用、灵活、高性能的分布式 ID 生成器

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)

CosId 1.3.9 发布,通用、灵活、高性能的分布式 ID 生成器

从上面的设计图中,不难看出号段模式基本设计思路是通过每次获取一定长度(Step)的可用ID(Id段/号段),来降低网络IO请求次数,提升性能。

  • CosId 1.3.9 发布,通用、灵活、高性能的分布式 ID 生成器强依赖第三方号段分发器,可用性受到第三方分发器影响。
  • CosId 1.3.9 发布,通用、灵活、高性能的分布式 ID 生成器每次号段用完时获取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)

CosId 1.3.9 发布,通用、灵活、高性能的分布式 ID 生成器

SegmentChainIdSegmentId增强版,相比于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)

RedisChainIdBenchmark-Throughput

CosId 1.3.9 发布,通用、灵活、高性能的分布式 ID 生成器

MySqlChainIdBenchmark-Throughput

CosId 1.3.9 发布,通用、灵活、高性能的分布式 ID 生成器

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

RedisChainIdBenchmark-Percentile

CosId 1.3.9 发布,通用、灵活、高性能的分布式 ID 生成器

MySqlChainIdBenchmark-Percentile

CosId 1.3.9 发布,通用、灵活、高性能的分布式 ID 生成器

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

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

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Ajax Design Patterns

Ajax Design Patterns

Michael Mahemoff / O'Reilly Media / 2006-06-29 / USD 44.99

Ajax, or Asynchronous JavaScript and XML, exploded onto the scene in the spring of 2005 and remains the hottest story among web developers. With its rich combination of technologies, Ajax provides a s......一起来看看 《Ajax Design Patterns》 这本书的介绍吧!

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具