言午月月鸟 - PHP系统解析-ID生成

# ID生成

## 是什么？

> 为系统生成一个全局唯一ID的算法。

## 应用场景

生成的ID通常应用于某一数据模型的主键ID，以便：

- 数据库按ID分表时，可以提前计算出对应分表；

- 将数据放到队列或者作为参数调用其它服务时，队列消费或下游服务可以根据此ID做请求判重，实现接口幂等。

另外，非连续性的ID生成算法，还能弥补一些直接使用数据库自增ID的问题：

- 暴露了数据量；

- 自增的数字会非常方便爬虫抓取自身数据。

## 考虑因素

- 全局唯一

ID是数据非常重要的标识：1）如果生成的ID用于数据表主键，会导致冲突写入失败。2）如果重要业务的ID出现“串门”，有可能带来业务损失，且不好定位。

- 递增性

很多时候生成的ID是用于数据表主键，期望能保留通过ID大小判断数据新旧的信息；另外递增的ID也让MySQL存储引擎在插入数据时性能更优。

- 数字ID

数字ID在系统对接时兼容性更好；另外作为数据表索引，（相比字符串）性能更优。

从技术上，ID生成是业务前置支撑，必须具备 **高性能，高可用** 。

## 常用算法

### 类uuid算法

Linux 的uuidgen命令或者PHP内置的 uniqid() 算法，或者自己参考设计的同类算法，都能生成较难重复的ID。

因为是系统/语言内置，使用时很方便；且是本地算法，消耗可以忽略。

一些业务如果对“唯一性”要求不是那么高，也不要求必须是数字ID的场景，可以考虑使用。如生成一些临时校验用的token。

### redis incr计数

直接借助redis的incr命令来生成，可以得到确保自增，唯一的数字ID。

只是生成的ID是连续自增的（参考上面“数据库自增问题”）；且有单点问题，访问量巨大时，可能成为瓶颈。

另外需要注意一个风险： 如果 Redis 的数据落地方式设置是 RDB，落地有一定的延迟。当出现宕机重启后，再次访问可能会得到少量重复ID。

### 号段分配法

在数据库维护一个全局的**ID号段** 分配。调用方每次查询时获取到的是一批（如5000个）ID，然后存在本地自行分配使用，用完再申请下一波。

相当于管理中心总控，然后按批下发给各分机构具体分发。手机号、QQ号、车牌 的发放有相通之处。

这种算法对ID生成有不少可控制的细节，如：初始ID，号段批次的量。

但涉及取批次操作，性能有损，且处理不好的话，更新时刻会出现系统性能/负载“毛刺”。

### snowflake算法

名称取自“世界上没有两片雪花是完全相同的”。（PS：美团的ID生成服务名字叫 Leaf，取自“世界上没有两片相同的树叶”）

思路很简单：

构造一个64bit 的ID：

- 1bit（占位不用。因此生成的ID始终是一个正整数，不用考虑符号问题）

- 41bit（精确到毫秒的时间戳。因为41bit只能表示约69年，因此一般会设置一个基准时间，实际值为 当前值与该基准时间的差）

- 10bit（worker_id，工作ID。可以按需进一步分为 机器ID与进程ID）

- 12bit（sequence_id，序列化。通常由worker实现在同一毫秒内自增计数）

![](https://public-pkg-1252772859.cos.ap-guangzhou.myqcloud.com/dingusxp-blog/misc/snowflake.jpeg)

snowflake算法在实现上有很多变种，各块的长度、定义、取值方式可能调整，但有两点核心一般不变：

1. 包含时间序列，以确保ID整体为增大趋势；

2. 有一个生成ID序列的worker，由它控制并确保自身生成的ID不重复；同时该worker在全局有一个唯一编号。

需要注意的是：snowflake算法依赖应用端服务器的时钟，如果出现时钟回拨，可能导致重复ID。

## 实现方案

现在主流的ID生成主要是 号段分配法 和 snowflake 算法。

### 号段分配法

分配中心。

设计一个DB表：

```SQL
CREATE TABLE IF NOT EXISTS id_generator (
  id int(11) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 'id',
  max_id bigint(20) UNSIGNED NOT NULL DEFAULT '0' COMMENT '当前最大id',
  step int(11) UNSIGNED NOT NULL DEFAULT '0' COMMENT '号段的布长',
  biz_type bigint(20) UNSIGNED NOT NULL DEFAULT '0' COMMENT '业务类型',
  version bigint(20) UNSIGNED NOT NULL DEFAULT '0' COMMENT '版本号',
  PRIMARY KEY (id),
  UNIQUE KEY biz_type (biz_type)
) ENGINE=InnoDB;
```

每个业务占用一行记录，在某个业务需要使用ID分配服务前，先在数据库插入记录初始化。参考：

```SQL
INSERT INTO `id_generator` (`id`, `max_id`, `step`, `biz_type`, `version`) VALUES (NULL, '1000000', '5000', '1001', '0');
```

具体应用申请新号段时：

```SQL
# 先查询后更新，借助version做乐观锁
select max_id, step, version from id_generator where biz_type=#{biz_type} limit 1;
update id_generator set max_id = #{max_id+step}, version = version + 1 where version = #{version} and biz_type = #{biz_type}
```

应用拿到号段后存储在本地，并控制分配策略，注意不要出现一号多发情况。

另外，一个优化点是：不要等到本地号段耗尽才去申请新号段，而应该提前储备，以防高并发时去更新碰到网络抖动，可能导致大量请求阻塞等待。

### snowflake实现

php-fpm模式下，每个请求都是相对独立的，也就是说没有确定的worker_id，同时也没有常驻内存维护 sequence_id，所以要高效实现，一般需要借助PHP扩展。

在PHP扩展里，可以定义一块共享内存做ID序列的计数器，确保在php-fpm实例内全局自增。

注意一个php-fpm实例通常有很多子进程，需要考虑进程抢占共享内存的锁问题。

开源库参考：[https://github.com/liexusong/atom](https://github.com/liexusong/atom)

当然也可以基于swoole扩展来实现。可以参考 hyperf 的[ snowflake组件](https://hyperf.wiki/2.0/#/zh-cn/snowflake)。

## 参考文章与拓展阅读

[Leaf——美团点评分布式ID生成系统](https://tech.meituan.com/2017/04/21/mt-leaf.html)

[一口气说出 9种 分布式ID生成方式，面试官有点懵了](https://mp.weixin.qq.com/s?__biz=MzAxNTM4NzAyNg==&mid=2247483785&idx=1&sn=8b828a8ae1701b810fe3969be536cb14&chksm=9b859174acf21862f0b95e0502a1a441c496a5488f5466b2e147d7bb9de072bde37c4db25d7a&token=745402269&lang=zh_CN#rd)

[唯一ID生成原理与phper的深度思考](https://www.jianshu.com/p/ea8e29a624bd)

[PHP实现Snowflake生成分布式唯一ID](https://yuanxuxu.com/2018/11/26/php-snowflake/)