分布式唯一 ID 生成方式调研与迁移方案

背景

公司项目使用 5.6.40 版本 MySQL 数据库存储数据,多个业务进行了分库分表操作,且做了读写分离。

MySQL InnoDB 引擎主键为 B+ Tree 索引,具有 unique 特性,日后数据可能做迁移,而项目为分布式部署,故 id 生成策略需要满足唯一性;又由于互联网项目的高并发,id 生成策略还需满足高性能。

痛点

id 生成场景主要是新数据的持久化过程,UUID 的方式会影响插入速度, 并且造成硬盘使用率低。UUID 通过 MAC、时间戳、随机数等因子进行运算,可以满足“唯一性”这一要求,但是性能上,无论是生成速度,亦或是插入 MySQL 的速度,都不理想。

关于 UUID 的插入性能的说明

B+ Tree 结构如下:

B+Tree

插入顺序数据时,如果磁盘块已满,则会使用新磁盘块,但如果 id 不是按一定顺序递增的,则可能需要数据迁移,比如图中磁盘块 5 已满,但是此时新插入的数据 id=14,则 id=15 的数据需要迁移到磁盘块 6 中,当数据量很大时,迁移动作可能非常频繁,而这个动作是很耗时间的(磁盘 IO),在互联网项目中是无法接受的,轻则导致超时、TPS 低等问题,重则导致服务不可用。

解决方案

从架构上,分两种:

  • 客户端自给自足型,直接在业务 JVM 中生成;
  • 中心化思想,搭建专门的发号服务,消耗方通过 RPC 等方式进行调用。

两种方式各有优缺点,前者无网络调用的消耗,后者方便统一维护,解耦彻底,可以弹性扩容、提供高可用。

客户端自给自足

业务表配置自增主键

直接做业务表的 DDL,使用 AUTO_INCREMENT 的主键,一般是在需求量不是很高的场景下使用。

优点
  • 严格连续递增;
  • 节省存储空间;
  • 性能好。
问题
  • 数据做了分片,今后如果在多个 Shards 之间迁移,会受限制;
  • 由于配置了主从复制,binlog 格式也有要求;
  • ID 号码不够随机,能够泄露发号数量的信息,不太安全。容易被爬虫,一旦获取权限,泄露数据更加容易。

MySQL 支持三种二进制日志格式:

  • ROW:基于行
  • STATEMENT:基于语句
  • MIXED:混合模式

关于 binlog 格式,详见 官方文档

使用 InnoDB 引擎基于 STATEMENT 配置主从复制的情形下,有以下几个问题:

  1. 在 MySQL 5.6.10 之前,STATEMENT 模式需要主、从的自增列定义得一模一样。
  2. 触发器或方法更新自增列的复制会失效。
  3. ALTER TABLE 中添加 AUTO_INCREMENT 列可能导致主、从的行数据顺序不一样。

来自官网,更多信息,可查看 官方文档

SnowFlake

结构如下:
0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000

  • 1 位标识,Java 中 long 带符号,id 一般是正数,最高位固定为 0;
  • 41 位时间戳,毫秒级。存的是 (当前时间 - 开始时间),这里的开始时间一般是该 id 生成器开始使用的时间,由程序指定。41 位可以使用 69 年:(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69
  • 10 位机器序号(原生其实是 5 位数据中心标识+ 5 位机器标识),理论上支持 1024 个节点上,只要确保单个 JVM 用的是唯一序号。可以使用 IP+port 等方式获取,或者依赖 zk;
  • 12 位序列,毫秒内的计数,支持同一机器同一毫秒窗口内产生 4096 个 id
优点
  • 支持客户端自生成,也支持单独部署;
  • 一共 64 位,正好是 Java long 型的长度,利用率 max;
  • 客户端自生成方案中没有网络调用;
  • 整体上按照时间趋势递增;
  • 效率较高。
问题
  • 机器时钟回拨问题:由于强依赖时间戳,故服务器 NTP 不能有问题;
  • 中心部署的方式中,client 每次只能取一个 id,网络延时是个问题;
  • 只能用 69 年(可以适当调整,比如减少机器位)。

发号机

中心化的思想,一般会依赖某个组件的特性,如 Redis 的原子 incr。为性能考虑,通常获取方式为批量获取一批 id,然后在内部慢慢消费。缺点是会增加架构的复杂度,依赖架构的高可用、分区容错。性能瓶颈就是服务本身瓶颈和网络消耗。

SnowFlake

SnowFlake 其实是一种紧凑地拼接 id 的算法,部署与算法无关,也可以支持中心化。

Leaf

Leaf 是发号机模式的一种实现,由美团点评技术团队开源,托管在 github 上,分为两种模式:号段模式(Leaf-segment)和 snowflake 模式(Leaf-snowflake),目前已经做了整合,可以通过配置选择。

Leaf-segment

号段模式下,服务不直接从 DB 取,而是通过代理层服务批量预取,提高性能,且 Leaf 有个优化,就是不等到号段用尽去更新号段,而是未雨绸缪地提前取,做到无阻塞,很大程度上降低系统的 TP999 指标,美团管它叫“双 buffer 优化”,就是 agent buffer 和提前取号 buffer。

Leaf-segment

biz_tag 用来区分业务,max_id 表示该 biz_tag 目前所被分配的 ID 号段的最大值,step 表示每次分配的号段长度。

Leaf-snowflake

这种方案和普通的 SnowFlake 没太多区别,leaf-snowflake 使用了 Zookeeper 实现对机器 id 的配置(本地节点也会有一个备用的机器 id),可以一定程度的提高系统的伸缩性和容错性:

Leaf-snowflake

优点
  • 方便扩展,性能能满足大多数业务场景;
  • 由于是批量取,异步消费,容灾性很高(发号机模式的优点)。
问题
  • 单独部署,增加结构复杂度;
  • 依赖 zk 或者数据库;
  • 自增 ID 固有问题:号码不够随机,能够泄露发号数量的信息,不太安全;
  • 号段使用完之后还是会 hang 在更新数据库的 I/O 上。

迁移方案

整体迁移

步骤如下:

  1. 新增方法,上线后的新增数据的 id 使用新策略生成;
  2. 新增逻辑,执行原有主键的更新,可添加入口手动触发或者通过定时任务;
  3. 执行 DDL 更改 id 的数据类型为 bigint。

优点

  • 磁盘使用率变高;
  • 如果当前数据已生成满数据页,则更改后能避免一部分插入时的页数据迁移。

问题与解决方案

# 问题 方案
1 现有方法在其它非生成主键的业务中也有调用(UUID 使用广泛) 需要统计所有生成 ID 的方法调用点,新增方法,然后修改调用点代码
2 强依赖服务器时钟 1. 方法中将上次生成的时间戳与当前作比对,若发现回拨,则等待直到满足要求,期间工具类无法提供服务(如果只是秒级回拨,可以承受),可配置报警逻辑;2. 配置服务器 NTP 为不能回拨的模式(需要运维支持),或者干脆关闭 NTP 同步
3 上线后需要校验老数据是否迁移完,然后执行 DDL 才能成功 新增校验逻辑,扫描表,甄别新老数据
4 有的表有其它表的主键列 工作量,存在遗漏风险
5 需要扫描所有表 数据量不大时还好
6 DDL 需要获取 metadata 锁,锁为表级,故执行时不能有大事务在进行,否则有挂库风险 项目目前很少使用事务的业务,且事务粒度不大,风险很小,关于会阻塞 DELETE、UPDATE,建议使用 pt-online 等工具进行修改

回滚方案

回滚代码、DDL。

方法切换

仅新增工具类方法。

问题与解决方案

# 问题 方案
1 现有方法在其它非生成主键的业务中也有调用(UUID 使用广泛) 需要统计所有生成 ID 的方法调用点,新增方法,然后修改调用点代码
2 强依赖服务器时钟 1. 方法中将上次生成的时间戳与当前作比对,若发现回拨,则等待直到满足要求,期间工具类无法提供服务(如果只是秒级回拨,可以承受);2. 配置服务器 NTP 为不能回拨的模式(需要运维支持)

回滚方案

回滚代码。

参考: