# 思维导图

分布式ID系统设计-思维导图

源文件地址

# 业务场景

业务系统对于ID的要求有哪些?

  • 全局唯一性:不能出现重复的ID号,既然是唯一标识,这是最基本的要求。
  • 趋势递增:在MySQL InnoDB引擎中使用的是 聚集索引,由于多数RDBMS使用B-tree的数据结构来存储索引数据,在主键的选择上面我们应该尽量使用有序的主键保证写入性能。
  • 单调递增:保证下一个ID一定大于上一个ID,例如事务版本号、IM增量消息、排序等特殊需求。
  • 信息安全:如果ID是连续的,恶意用户的扒取工作就非常容易做了,直接按照顺序下载指定URL即可;如果是订单号就更危险了,竞对可以直接知道我们一天的单量。所以在一些应用场景下,会需要ID无规则、不规则。

# 性能要求

如果ID生成系统瘫痪,整个系统的无法获取新生成ID号,业务系统会面临崩溃

因此ID系统在保证 ID号码满足自身的要求 同时,还需要满足以下性能要求

  1. 平均延迟和TP999延迟都要尽可能低
  2. 可用性5个9
  3. 高QPS

# 业内方案

9种分布式ID解决方案:

  1. 数据库自增ID
    • 读写瓶颈
    • 单点故障风险大
  2. UUID随机数
    • 长度过长
    • 无序性
  3. 雪花算法(SnowFlake)
    • 时钟回拨问题
    • workId相同造成id冲突
  4. 数据库多主模式
    • 集群的扩展问题
    • 未从根本上解决高并发的性能问题
  5. 号段模式
    • 通过预分配号段的方式,减小了DB的压力,解决了并发场景的性能问题
    • 采用版本号乐观锁的方式更新,保证了并发场景下数据的准确性
  6. Redis
    • 通过incr命令实现ID的原子性自增
    • redis持久化问题
      • RDB:持久化不及时,重启后出现ID重复
      • AOF:重启恢复数据时间过长
  7. 滴滴出品(TinyID)
    • 基于号段模式
  8. 百度 (Uidgenerator)
    • 支持自定义时间戳、工作机器ID和序列号等各部分的位数
    • 支持用户自定义workId的生成策略,应用每次启动消费一个workId
  9. 美团(Leaf)
    • 同时支持号段模式和snowflake算法模式
    • snowflake模式依赖ZooKeeper解决了时钟回拨问题

我们主要讲下前三种,以及外研基于号段模式实现的分布式ID系统

# 数据库自增ID

以MySQL举例,利用给字段设置auto_increment_incrementauto_increment_offset来保证ID自增。

# 优点

  • 非常简单,利用现有数据库系统的功能实现,成本小,有DBA专业维护。
  • ID号单调自增,可以实现一些对ID有特殊要求的业务。

# 缺点

  • 强依赖DB,当DB异常时整个系统不可用,属于致命问题。
    • 配置主从复制可以尽可能的增加可用性,但是数据一致性在特殊情况下难以保证。
    • 主从切换时的不一致可能会导致重复发号。
  • ID发号性能瓶颈限制在单台MySQL的读写性能。

对于MySQL性能问题,可用如下方案解决:

在分布式系统中我们可以多部署几台机器,每台机器设置不同的初始值,且步长和机器数相等。 比如有两台机器,设置步长step为2,TicketServer1的初始值为1(1,3,5,7,9,11…)、TicketServer2的初始值为2(2,4,6,8,10…)

# UUID

UUID(Universally Unique Identifier)的标准型式包含32个16进制数字,以连字号分为五段,形式为8-4-4-4-12的36个字符

示例:550e8400-e29b-41d4-a716-446655440000

优点:

  • 性能非常高:本地生成,没有网络消耗。

缺点:

  • 不易于存储:UUID太长,16字节128位,通常以36长度的字符串表示,很多场景不适用。
  • 信息不安全:基于MAC地址生成UUID的算法可能会造成MAC地址泄露,这个漏洞曾被用于寻找梅丽莎病毒的制作者位置。
  • ID作为主键时在特定的环境会存在一些问题,比如做DB主键的场景下,UUID就非常不适用:

MySQL官方有明确的建议主键要尽量越短越好,36个字符长度的UUID不符合要求。

# 优点

  • 性能非常高:本地生成,没有网络消耗。

# 缺点

  • 不易于存储:UUID太长,16字节128位,通常以36长度的字符串表示,很多场景不适用。
  • 信息不安全:基于MAC地址生成UUID的算法可能会造成MAC地址泄露,这个漏洞曾被用于寻找梅丽莎病毒的制作者位置。
  • ID作为主键时在特定的环境会存在一些问题,比如做DB主键的场景下,UUID就非常不适用:

# 雪花算法

自然界中并不存在两片完全一样的雪花

自然界中并不存在两片完全一样的雪花

雪花算法正如其名字,表示生成的ID如雪花般独一无二

# 工作原理

是一种以划分命名空间(UUID也算,由于比较常见,所以单独分析)来生成ID的一种算法

Twitter Snowflake为例,生成的数据为64bit的long型数据,在数据库中应该用大于等于64bit的数字类型的字段来保存该值,比如在MySQL中应该使用BIGINT。

# Snowflake-ID结构

Twitter Snowflake64-bit结构

  • E1-bit reserved,1bit,置为0;
  • E41-bit timestamp,41bit,表示从系统初始时间到现在的毫秒数, 可以用大概69年;2 ^ 41 / 365 / 24 / 3600 / 1000 = 69.73
  • E10-bit machine id,10bit,这个机器id每个业务要唯一; 机器id获取的策略后面会详述;
  • E12-bit sequence,12bit,每台机器每毫秒最多产生4096个id,超过这个数的话会等到下一毫秒

雪花算法

# 优势

  • 毫秒数在高位,自增序列在低位,整个ID都是趋势递增的。
  • 不依赖数据库等第三方系统,以服务的方式部署,稳定性更高,生成ID的性能也是非常高的。
  • 可以根据自身业务特性分配bit位,非常灵活。

# 弊端

  • 依赖机器时钟,如果机器 时钟回拨 ,会导致发号重复或者服务会处于不可用状态。(严重缺陷)
  • 不能在一台服务器上部署多个分布式ID服务;(算不上缺陷,可以避免)

# 应用举例

# 实际业务场景案例

雪花算法二次改造案例,引自58沈剑《架构师之路》系列

假设某公司ID生成器服务的需求如下:

  1. 单机高峰并发量小于1W,预计未来5年单机高峰并发量小于10W
  2. 有两个机房,预计未来5年机房数量小于4个
  3. 每个机房机器数小于100台
  4. 目前有5个业务线有ID生成需求,预计未来业务线数量小于10个
  5. 。。。

分析过程如下:

  • 高位取从系统ID生成器服务上线到现在的毫秒数,假设系统至少运行10年,那至少需要10年365天24小时3600秒1000毫秒=320*10^9,差不多预留39bit给毫秒数
  • 每秒的单机高峰并发量小于10W,即平均每毫秒的单机高峰并发量小于100,差不多预留7bit给每毫秒内序列号
  • 5年内机房数小于4个,预留2bit给机房标识
  • 每个机房小于100台机器,预留7bit给每个机房内的服务器标识
  • 业务线小于10个,预留4bit给业务线标识

这样设计的64bit标识,可以保证:

  • 每个业务线、每个机房、每个机器生成的ID都是不同的
  • 同一个机器,每个毫秒内生成的ID都是不同的
  • 同一个机器,同一个毫秒内,以序列号区区分保证生成的ID是不同的
  • 将毫秒数放在最高位,保证生成的ID是趋势递增的

# 外研分布式ID服务

# 思维导图

外研分布式ID服务-思维导图

# 场景

对外提供全局独立唯一ID

  • 支持单个、批量不同数量的ID获取
  • 支持单调递增、趋势递增不同特性的ID获取

# 业务流程

业务流程图

# 核心服务

  1. id发号器
  2. id池定时轮询器

# 存储设计

应用配置存储(支持高性能查询)+ 缓存id池(支持高性能读取、写入)

# 应用配置存储设计

mysql存储 + redis缓存优化读取性能,注意 数据一致性

# 缓存id池设计

id池要实现高性能读取和写入,我们选择了redis作为底层数据存储

对于数据结构选择,redis常用容器类型有hash、list、set、zset,选择哪一个更为合适呢

考虑到要支持单调递增模式,严格要求顺序性,list和zset都能实现顺序性,究竟该选择哪一个?

我们知道zset可以根据权值实现顺序性,但是其底层实现为跳表,其查询、插入、删除的时间复杂度为O(logn),不满足我们对高性能的要求,故选择list

# 发号策略

list中维护了从小到大的预生成ID队列,遵循FIFO规则,不管是单个还是批量,直接从队头获取

# 更新策略

我们使用号段模式作为id的生成方式,每次从 currentOffset 算法生成 满足 单调递增or趋势递增的ID序列,执行入队操作

  • 单调递增:不定增率,有序入队
  • 趋势递增:增率为1,shuffle后入队

入队操作完成后,同步更新缓存配置,再异步更新db配置

# 问题思考

分布式场景下,缓存id池的写入操作,会不会造成重复发号、id池溢出等问题?

必须配置分布式锁机制,保证全局串行化,即某一时刻,只允许一个ID生成器的worker在工作

批量获取数量大于缓存池大小(缓存池被过度消费),如何处理?

  1. 理论上不会出现这种情况
    1. 系统预留1分钟的最大秒并发数(目前默认5000),
    2. 定时任务每隔100ms扫描,低于最大池的80%,进行补充
  2. 如果异常发生,返回空;同时应触发报警机制

# web层

接口文档

# 数据层

表结构设计

# 应用表示

  • appKey:应用的唯一key
  • appSecret:应用秘钥
  • appName:应用名称

# ID的增长方式

  • 趋势递增 trend
  • 严格递增(单调递增) monotony

# ID的分配范围配置

  • startOffset 初始化的id起始位置
  • step 每次向id池子增加的数量
  • currentOffset id的当前位置

# 缓存ID池配置

  • maxSizePerTimes 一次最大获取id量(默认1000)
  • maxSizePerSecond 1s最大获取量(秒级并发QPS,默认5000)
  • minSizePercent 触发添加的百分比上限(默认80%)
  • interval 循环添加间隔时间10ms(不可修改)
  • maxPoolSize id池的最大id存量(系统默认是maxSizePerSecond60倍,为了保证1分钟不断供)

# 我们做到了

  • 一致性,服务端保证不会获取到重复的ID
  • 两种递增方式支持,趋势递增+严格递增
  • 高可用,短ID服务允许部署多套完全独立的环境,每个环境产生的ID都不一样,client可以failover到任何环境
  • 高性能,每秒钟可以获取百万级的ID,并且不会出现阻塞
  • 基于时间的大致有序,基本上获取到的ID会越来越大,无法保证严格有序,比如一小时前获取的ID应该会比一小时后的小

# 我们不支持

  • 没有实现严格自增长ID
  • 无法保证每个ID都不浪费

# 参考文档