1. 为什么要用分布式 ID

1.1 什么是分布式 ID

拿 MySQL 数据库举个栗子：

在我们业务数据量不大的时候，单库单表完全可以支撑现有业务，数据再大一点搞个 MySQL 主从同步读写分离也能提高数据库性能。

但随着数据日渐增长，主从同步也扛不住了，就需要对数据库进行分库分表，但分库分表后需要有一个唯一 ID 来标识一条数据，数据库的自增 ID 在分库分表设计之后显然解决不了这个问题；例如实际场景中，如订单、优惠券都是需要有唯一 ID 做标识。此时一个能够生成全局唯一 ID 的系统是非常必要的。那么这个全局唯一 ID 就叫分布式 ID。

1.2 分布式 ID 需要满足什么条件

  • 全局唯一：基本要求，必须保证 ID 是全局唯一的；
  • 高并发：ID 生成响应要快，否则会成为业务瓶颈；
  • 高可用：最好能保证 100% 可以对外提供服务；

分布式 ID 介绍 - 图1

2. 分布式 ID 常见方案

2.1 基于 UUID

当需要一个具有唯一性的 ID，我们首先想到的可能就是 UUID，它确实具有全球唯一性的特性，可以做分布式 ID，但是不推荐！

  1. public static void main(String[] args) { 
  2.        String uuid = UUID.randomUUID().toString().replaceAll("-","");
  3.        System.out.println(uuid);
  4.  }

UUID 的生成简单到只有一行代码，输出结果 c2b8c2b9e46c47e3b30dca3b0d447718，但 UUID 却并不适用于实际的业务需求。像用作订单号 UUID 这样的字符串没有丝毫的意义，看不出和订单相关的有用信息；而对于数据库来说用作业务主键 ID，它不仅是太长还是字符串，存储性能差查询也很耗时，所以不推荐用作分布式 ID。

优点：

  • 生成足够简单，本地生成无网络消耗，具有唯一性；

缺点：

  • 没有具体的业务含义
  • 字符串长度过长，36位字符串，存储及查询对 MySQL 的性能消耗较大；
    • MySQL 官方明确建议主键要尽量越短越好，UUID 作为数据库主键，它的无序性会导致数据位置频繁变动，严重影响性能
  • 无序的字符串，不具备趋势自增特性

2.2 基于数据库单点模式的主键自增

基于数据库的 auto_increment 自增 ID 完全可以充当分布式 ID，具体实现：需要一个单独的 MySQL 实例用来生成 ID，建表结构如下：

  1. CREATE DATABASE `SEQ_ID`;
  2. CREATE TABLE SEQID.SEQUENCE_ID (
  3.     id bigint(20) unsigned NOT NULL auto_increment, 
  4.     value char(10) NOT NULL default '',
  5.     PRIMARY KEY (id),
  6. ) ENGINE=MyISAM;
  1. insert into SEQUENCE_ID(value)  VALUES ('values');

当我们需要一个 ID 的时候，向表中插入一条记录返回主键 ID，但这种方式有一个比较致命的缺点，访问量激增时 MySQL 本身就是系统的瓶颈，用它来实现分布式服务风险比较大，不推荐！

优点：

  • 实现简单，ID 单调自增，数值类型查询速度快

缺点：

  • DB 单点存在宕机风险，无法抗住高并发场景

2.3 基于数据库集群模式的主键自增

针对数据库单点模式的缺点，可以做一些高可用优化，换成主从模式集群，或者做成双主模式集群，也就是两个 MySQL 实例都能单独的生产自增 ID。

那么，两个 MySQL 实例的自增ID都从1开始，会生成重复的 ID 怎么办？

解决方案：设置 起始值 和 自增步长
MySQL_1 配置：

  1. set @@auto_increment_offset = 1;     -- 起始值
  2. set @@auto_increment_increment = 2;  -- 步长

MySQL_2 配置：

  1. set @@auto_increment_offset = 2;     -- 起始值
  2. set @@auto_increment_increment = 2;  -- 步长

这样两个 MySQL 实例的自增 ID 分别就是：

  1. 1、3、5、7、9 
  2. 2、4、6、8、10

那如果集群后的性能还是扛不住高并发咋办？就要进行 MySQL 扩容增加节点，这是一个比较麻烦的事。image.png
从上图可以看出，水平扩展的数据库集群，有利于解决数据库单点压力的问题，同时为了 ID 生成特性，将自增步长按照机器数量来设置。

增加第三台 MySQL 实例需要人工修改一、二两台 MySQL 实例的起始值和步长，把第三台机器的 ID 起始生成位置设定在比现有最大自增 ID 的位置远一些，但必须在一、二两台 MySQL 实例 ID 还没有增长到第三台 MySQL 实例的起始 ID 值的时候，否则自增 ID 就要出现重复了，必要时可能还需要停机修改。

优点：

  • 解决 DB 单点问题

缺点：

  • 不利于后续扩容，而且实际上单个数据库自身压力还是大，依旧无法满足高并发场景。

2.4 基于 Redis 的 ID 自增

Redis 也同样可以实现类似数据库的主键自增，原理就是利用 Redis 的 incr 命令实现 ID 的原子性自增。

  1. 127.0.0.1:6379> set seq_id 1     // 初始化自增ID为1
  2. OK
  3. 127.0.0.1:6379> incr seq_id      // 增加1，并返回递增后的数值
  4. (integer) 2

用 Redis 实现需要注意一点，要考虑到 Redis 持久化的问题。

Redis 有两种持久化方式 RDB 和 AOF：

  • RDB 会定时打一个快照进行持久化，假如连续自增但 Redis 没及时持久化，而这会 Redis 挂掉了，重启 Redis 后会出现 ID 重复的情况。
  • AOF 会对每条写命令进行持久化，即使 Redis 挂掉了也不会出现 ID 重复的情况，但由于 incr 命令的特殊性，会导致 Redis 重启恢复的数据时间过长。

优点：

  • 不依赖于数据库，灵活方便，且性能优于数据库。
  • 数字 ID 天然排序，对分页或者需要排序的结果很有帮助。

缺点：

  • 如果系统中没有 Redis，还需要引入新的组件，增加系统复杂度。
  • 需要编码和配置的工作量比较大。

2.5 基于数据库的号段模式

号段模式是当下分布式 ID 生成器的主流实现方式之一，号段模式可以理解为从数据库批量的获取自增 ID，每次从数据库取出一个号段范围，例如 (1,1000] 代表 1000 个 ID，具体的业务服务将在本号段内，生成 1~1000 的自增 ID 并加载到内存。

表结构如下：

  • biz_type：代表不同业务类型
  • max_id：当前最大的可用 id
  • step：代表号段的长度
  • version：是一个乐观锁，每次都更新 version，保证并发时数据的正确性
    1. CREATE TABLE id_generator (
    2. id int(10) NOT NULL,
    3. max_id bigint(20) NOT NULL COMMENT '当前最大id',
    4. step int(20) NOT NULL COMMENT '号段的布长',
    5. biz_type    int(20) NOT NULL COMMENT '业务类型',
    6. version int(20) NOT NULL COMMENT '版本号',
    7. PRIMARY KEY (`id`)
    8. )
    分布式 ID 介绍 - 图3

等这批号段 ID 用完，再次向数据库申请新号段，对 max_id 字段做一次 update 操作，update max_id= max_id + step，update 成功则说明新号段获取成功，新的号段范围是(max_id ,max_id +step]。

  1. update id_generator set max_id = #{max_id+step}, version = version + 1 where version = # {version} and biz_type = XXX

由于多业务端可能同时操作，所以采用版本号 version 乐观锁方式更新，这种分布式 ID 生成方式不强依赖于数据库，不会频繁的访问数据库，对数据库的压力小很多。

优点：

  • 不会频繁访问数据库，每次取一批号段，性能提高
  • 数值自增，查询性能好

2.6 基于 Snowflake 雪花算法模式

雪花算法（Snowflake）是 twitter 公司内部分布式项目采用的 ID 生成算法，开源后广受国内大厂的好评，在该算法影响下各大公司相继开发出各具特色的分布式 ID 生成器。
image.png
Snowflake 生成的是 Long 类型的 ID，一个 Long 类型占 8 个 byte，每个字节占 8 bit，也就是说一个 Long 类型占 64 个 bit。

Snowflake ID 组成结构：正数位（占1比特）+ 时间戳（占41比特）+ 机器 ID（占5比特）+ 数据中心编号（占5比特）+ 自增值（占12比特），总共64比特组成的一个 Long 类型。

  • 第一个 bit 位（1bit）：Java中 long 的最高位是符号位代表正负，正数是0，负数是1，一般生成 ID 都为正数，所以默认为 0。
  • 时间戳部分（41bit）：毫秒级的时间，不建议存当前时间戳，而是用（当前时间戳 - 固定开始时间戳）的差值，可以使产生的 ID 从更小的值开始；41位的时间戳可以使用69年，(1L << 41) / (1000L 60 60 24 365) = 69年。
  • 工作机器 id（10bit）：也被叫做 workId，这个可以灵活配置，机房或者机器号组合都可以。整个分布式系统可以部署 2^10=1024 台节点。
  • 序列号部分（12bit），自增值支持同一毫秒内同一个节点可以生成 4096 个ID。

Snowflake 算法可以根据自身项目的需要进行一定的修改。比如估算未来的数据中心个数，每个数据中心的机器数以及统一毫秒可以能的并发数来调整在算法中所需要的 bit 数。

优点：

  • 不依赖于数据库，灵活方便，且性能优于数据库。
  • ID 按照时间在单机上是递增的。

缺点：

  • 时钟回拨问题：在单机上是递增的，但是由于涉及到分布式环境，每台机器上的时钟不可能完全同步，在算法上要解决时间回拨的问题。

3. 开源组件

3.1 百度（uid-generator）

uid-generator 是由百度技术部开发，GitHub地址；

uid-generator 是基于 Snowflake 算法实现的，与原始的 snowflake 算法不同在于，uid-generator 支持自定义时间戳、工作机器ID和 序列号 等各部分的位数，而且 uid-generator 中采用用户自定义 workId 的生成策略。

uid-generator 需要与数据库配合使用，需要新增一个 WORKER_NODE 表。当应用启动时会向数据库表中去插入一条数据，插入成功后返回的自增 ID 就是该机器的 workId 数据由 host，port 组成。

总结：只支持雪花算法，组件无人维护，需要数据库支持；

3.2 滴滴（Tinyid）

Tinyid 由滴滴开发，Github 地址；
Tinyid 是基于号段模式原理实现的与 Leaf 如出一辙，每个服务获取一个号段（1000,2000]、（2000,3000]、（3000,4000]。

总结：只支持数据库号段模式，多 DB，高可用，java-client，适合对 ID 有高可用的需求。

3.3 美团（Leaf）

Leaf 由美团开发，Github 地址；

总结：Leaf 同时支持号段模式和 Snowflake 算法模式，可以切换使用。

来源： https://zhuanlan.zhihu.com/p/107939861