乐趣区

关于分布式:一种简易但设计全面的ID生成器思考

jiezi

分布式系统中，全局惟一 ID 的生成是一个陈词滥调然而十分重要的话题。随着技术的一直成熟，大家的分布式全局惟一 ID 设计与生成计划趋向于趋势递增的 ID，这篇文章将联合咱们零碎中的 ID 针对实际业务场景以及性能存储和可读性的考量以及优缺点取舍，进行深入分析。本文并不是为了剖析出最好的 ID 生成器，而是剖析设计 ID 生成器的时候须要思考哪些，如何设计出最适宜本人业务的 ID 生成器。

我的项目地址：https://github.com/JoJoTec/id…

首先，先放出咱们的全局惟一 ID 构造：

这个惟一 ID 生成器是放在每个微服务过程外面的插件这种架构，不是有那种惟一 ID 生成核心的架构：

  • 结尾是工夫戳格式化之后的字符串，能够间接看出年月日时分秒以及毫秒。因为扩散在不同过程外面，须要思考不同微服务工夫戳不同是否会产生雷同 ID 的问题。
  • 中间业务字段，最多 4 个字符。
  • 最初是自增序列。这个自增序列通过 Redis 获取，同时做了扩散压力优化以及集群 fallback 优化，前面会详细分析。

序列号的结尾是工夫戳格式化之后的字符串，因为扩散在不同过程外面，不同过程以后工夫可能会有差别，这个差别可能是毫秒或者秒级别的。所以，要思考 ID 中剩下的局部是否会产生雷同的序列。

自增序列由两局部组成，第一局部是 Bucket，前面是从 Redis 中获取的对应 Bucket 自增序列，获取自增序列的伪代码是：

1. 获取以后线程 ThreadLocal 的 position，position 初始值为一个随机数。2. position += 1，之后对最大 Bucket 大小（即 2^8）取余，即对 2^8 - 1 取与运算，获取以后 Bucket。如果以后 Bucket 没有被断路，则执行做下一步，否则反复 2。如果所有 Bucket 都失败，则抛异样退出
3. redis 执行：incr sequence_num_key: 以后 Bucket 值，拿到返回值 sequence
4. 如果 sequence 大于最大 Sequence 值，即 2^18，对这个 Bucket 加锁（sequence_num_lock: 以后 Bucket 值），更新 sequence_num_key: 以后 Bucket 值 为 0，之后反复第 3 步。否则，返回这个 sequence
   
-- 如果 3，4 呈现 Redis 相干异样，则将以后 Bucket 退出断路器，反复步骤 2

在这种算法下，即便每个实例工夫戳可能有差别，只有在 最大差别工夫内，同一业务不生成超过 Sequence 界线数量的实体，即可保障不会产生反复 ID。

同时，咱们设计了 Bucket，这样在应用 Redis 集群的状况下，即便某些节点的 Redis 不可用，也不会影响咱们生成 ID。

以后 OLTP 业务离不开传统数据库，目前最风行的数据库是 MySQL，MySQL 中最风行的 OLTP 存储引擎是 InnoDB。思考业务扩大与分布式数据库设计，InnoDB 的主键 ID 个别不采纳自增 ID，而是通过全局 ID 生成器生成。这个 ID 对于 MySQL InnoDB 有哪些性能影响呢？咱们通过将 BigInt 类型主键和咱们这个字符串类型的主键进行比照剖析。

首先，因为 B+ 树的索引个性，主键越是严格递增，插入性能越好。越是凌乱无序，插入性能越差。这个起因，次要是 B+ 树设计中，如果值无序水平很高，数据被离散存储，造成 innodb 频繁的页决裂操作，重大升高插入性能。能够通过上面两个图的比照看出：

插入有序：

插入无序：

如果插入的主键 ID 是离散无序的，那么每次插入都有可能对于之前的 B+ 树子节点进行裂变批改，那么在任一一段时间内，整个 B+ 树的每一个子分支都有可能被读取并批改，导致内存效率低下 。 如果主键是有序的（即新插入的 id 比之前的 id 要大），那么只有最新分支的子分支以及节点会被读取批改，这样从整体上晋升了插入效率。

咱们设计的 ID，因为是以后工夫戳结尾的，从 趋势上是整体递增 的。基本上能满足将插入要批改的 B+ 树节点管制在最新的 B+ 树分支上，避免树整体扫描以及批改。

和 SnowFlake 算法生成的 long 类型数字，在数据库中即 bigint 比照：bigint，在 InnoDB 引擎行记录存储中，无论是哪种行格局，都占用 8 字节 。咱们的 ID，char 类型，字符编码采纳 latin1（ 因为只有字母和数字），占用 27 字节，大略是 bigint 的 3 倍多。

  • MySQL 的主键 B+ 树，如果主键越大，那么单行占用空间越多，即 B+ 树的分支以及叶子节点都会占用更多空间，造成的结果是：MySQL 是按页加载文件到内存的，也是按页解决的。这样一页内，能够读取与操作的数据将会变少。如果数据表字段只有一个主键，那么 MySQL 单页（不思考各种头部，例如页头，行头，表头等等）能加载解决的行数，bigint 类型是咱们这个主键的 3 倍多 。然而数据表个别不会只有主键字段，还会有很多其余字段， 其余字段占用空间越多，这个影响越小。
  • MySQL 的二级索引，叶子节点的值是主键，那么同样的，单页加载的叶子节点数量，bigint 类型是咱们这个主键的 3 倍多。然而目前个别 MySQL 的配置，都是内存资源很大的，造成其实二级索引搜寻次要的性能瓶颈并不在于此处，这个 3 倍影响对于大部分查问可能就是小于毫秒级别的优化晋升。绝对于咱们设计的这个主键带来的可读性以及便利性来说，是微不足道的。

业务上，其实有很多须要按创立工夫排序的场景。比如说查问一个用户明天的订单，并且依照创立工夫倒序，那么 SQL 个别是：

## 查问数量，为了分页
select count(1) from t_order where user_id = "userid" and create_time > date(now());
## 之后查问具体信息
select * from t_order where user_id = "userid" and create_time > date(now()) order by create_time limit 0, 10;

订单表必定会有 user_id 索引，然而随着业务增长，下单量越来越多导致这两个 SQL 越来越慢，这时咱们就能够有两种抉择：

  1. 创立 user_id 和 create_time 的联结索引来缩小扫描，然而大表额定减少索引会导致占用更多空间并且和现有索引重合有时候会导致 SQL 优化有误。

  2. 间接应用咱们的主键索引进行筛选:

    select count(1) from t_order where user_id = "userid" and id > "210821";
select * from t_order where user_id = "userid" and id > "210821" order by id desc limit 0, 10;

    然而须要留神的是，第二个 SQL 执行会比创立 user_id 和 create_time 的联结索引执行原来的 SQL 多一步 Creating sort index 行将命中的数据在内存中排序，如果命中量比拟小，即大部分用户在当天的订单量都是几十几百这个级别的，那么根本没问题，这一步不会耗费很大。否则还是须要创立 user_id 和 create_time 的联结索引来缩小扫描。

如果不波及排序，仅仅筛选的话，这样做根本是没问题的。

咱们不心愿用户通过 ID 得悉咱们的业务体量，例如我当初下一单拿到 ID，之后再过一段时间再下一单拿到 ID，比照这两个 ID 就能得出这段时间内有多少单。

咱们设计的这个 ID 齐全没有这个问题，因为最初的序列号：

  1. 所有业务共用同一套序列号，每种业务有 ID 产生的时候，就会造成 Bucket 外面的序列递增。
  2. 序列号同一时刻可能不同线程应用的不同的 Bucket，并且后果是位操作，很难看进去那局部是序列号，那局部是 Bucket。

从咱们设计的 ID 上，能够直观的看出这个业务的实体，是在什么时刻创立进去的：

  • 个别客服受理问题的时候，拿到 ID 就能看进去工夫，间接去后盾零碎对应时间段调取用户相干操作记录即可。简化操作。
  • 个别的业务有报警零碎，个别报警信息中会蕴含 ID，从咱们设计的 ID 上就能看进去创立工夫，以及属于哪个业务。
  • 日志个别会被采集到一起，所有微服务零碎的日志都会汇入例如 ELK 这样的零碎中，从搜索引擎中搜寻进去的信息，从 ID 就能直观看出业务以及创立工夫。

在给出的我的项目源码地址中的单元测试中，咱们测试了通过 embedded-redis 启动一个本地 redis 的单线程，200 线程获取 ID 的性能，并且比照了只操作 redis，只获取序列以及获取 ID 的性能，我的破电脑后果如下：

单线程
BaseLine(only redis): 200000 in: 28018ms
Sequence generate: 200000 in: 28459ms
ID generate: 200000 in: 29055ms

200 线程
BaseLine(only redis): 200000 in: 3450ms
Sequence generate: 200000 in: 3562ms
ID generate: 200000 in: 3610ms

微信搜寻“我的编程喵”关注公众号，每日一刷，轻松晋升技术，斩获各种 offer：

退出移动版