在不少的技术文章，或者技术书籍中，关于唯一ID的生成，总结起来，可以有多种方法。比如：
在程序中使用全局计数器
使用数据库自增ID
相助操作系统底层或者编程语言本身提供的机制生成
使用现实世界中唯一的信息，例如个人身份证号
随机生成
根据特定的算法生成唯一序列
……
如果发散一下思维，我们还可以想到很多其他的技术实现方案。
回归到我们企业级网站系统开发，回归到业务的需求层面，到处都可以找到ID生成的业务场景，如：优惠券ID、订单流水号、新用户的UUID、工单号。那这些看似简单的ID生成，有什么要求，可以怎样实现，又有哪些隐藏的风险点呢？我们又该如何优化改进？由此带来的思考和启发是什么？
下面将一起来探讨。
1 流水号ID的约束、实现和风险点
为实际业务生成提供的流水号ID，通常需要满足两个约束：
唯一性：即生成的ID不能重复
随机性：提供的ID具备一定随机性，使得外界不能轻量穷举或遍历
这类流水号ID，会有周期性循环，例如每天都会有新的生成周期。
假设我们需要为二手商场的每次交易生成一个唯一的交易号，下面是简单的实现过程。
生成交易ID第一版
在生成ID时，有两个常用的因子，分别是：当前时间和随机数。结合当前时间和随机数，我们就能轻易构建一个随机不重复的ID。生成ID的实现函数create_trade_id()实现代码如下：
/**
* 生成交易ID - 第一版
*
* 简单的ID生成
*/
function create_trade_id() {
return date('y')
. str_pad(date('z') % 100, 2, '0', STR_PAD_LEFT)
. str_pad(time() % 1000, 3, '0', STR_PAD_LEFT)
. mt_rand(100, 999);
}
根据此函数生成的交易ID，由四部分组成，从左往右依次是：
第一部分：当前年份，2 位数字表示的年份
第二部分：年份中的第几天，并对100求余数，固定2位，不足左边用0填充
第三部分：当前时间戳，并对1000求余数，固定3位，不足左边用0填充
第四部分：100到999之间的随机数，即固定3位
累加起来就可以产生一个固定长度为10位数字的交易ID。以下是几个示例：
1873295365 1873295459 1873295565
这是常见的ID生成实现方式，其中利用了时间和随机数，看起来也是能正常工作的。但实际情况真的是这样吗？它真的能由始至终提供唯一的ID吗？
生成交易ID第二版
稍加分析，就可以发现上面的create_trade_id()函数是有漏洞的，因为最后三位随机数，并不能100%保证生成的ID不会重复，只是概率相对较低。但概率低，并不表示不会发生。在完成上面业务功能需求开发并上线发布投入使用后，过了一段时间，有不少用户投诉说交易信息会错乱。经排查，正是这里生成的交易号不重复，产生了串号的情况。
针对这一故障，技术人员快速响应，立即进行了缺陷修复工作。这一次，技术人员使用了缓存，对最近已经使用的ID进行缓存并判断是否已被使用，从而修复交易串号的问题。修复后的第二版代码如下：
/**
* 生成交易ID - 第二版
*
* 利用缓存，修复重复使用的缺陷
*/
function create_trade_id_v2() {
// 缓存实例
$cache = new Cache();
$newId = 0;
do {
$newId = date('y')
. str_pad(date('z') % 100, 2, '0', STR_PAD_LEFT)
. str_pad(time() % 1000, 3, '0', STR_PAD_LEFT)
. mt_rand(100, 999);
// 检测是否已经被使用
if (!$cache->get('trade_id_' . $newId)) {
break;
}
} while(true);
// 标记为已使用，缓存3秒
$cache->set('trade_id_' . $newId, 1, 3);
return $newId;
}
这一次的实现代码，稍微有点复杂，但也还是比较容易理解的。但这样就已经是足够了吗？
生成交易ID第三版
事实上，不久后，重复交易号的问题又重现了。这是为什么呢？因为在第二版修复时，只考虑了现在，而没有考虑到过去，也没想到有未来。注意到，在交易号的第三部分，是由当前时间戳对1000求余数。这意味着什么呢？每一天，都有24小时，1440分钟，86400秒。时间戳的单位是秒，86400 / 1000的商是86，这意味着同一天内至少会有86次重复的余数。以余数为0为全例，可以算出，在同一天内余数重复的次数和时间点。
表2 同一天内余数重复的情况
|
序号
|
具体时间
|
同一天内的第几秒
|
对1000求余数
|
最终余数
|
|---|---|---|---|---|
|
第1次
|
00:00:00
|
0
|
0 % 1000
|
0
|
|
第2次
|
00:16:40
|
1000
|
1000 % 1000
|
0
|
|
第3次
|
00:33:20
|
2000
|
2000 % 1000
|
0
|
|
……
|
……
|
……
|
……
|
……
|
|
第84次
|
23:20:00
|
84000
|
84000 % 1000
|
0
|
|
第85次
|
23:36:40
|
85000
|
85000 % 1000
|
0
|
|
第86次
|
23:53:20
|
86000
|
86000 % 1000
|
0
|
所以，仅仅缓存3秒是远远不够的，除了要与当前同一秒做重复判断外，还要和过去16多分钟、半小时前做重复检测。基于这份发现，我们使用了数据库，进行了更长时间的重复检测。优化后的第三版实现代码如下：
/**
* 生成交易ID - 第三版
*
* 利用数据库，更长时间的重复检测
*/
function create_trade_id_v3() {
// 数据库模型实例
$model = new TraceModel();
$newId = 0;
do {
$newId = date('y')
. str_pad(date('z') % 100, 2, '0', STR_PAD_LEFT)
. str_pad(time() % 1000, 3, '0', STR_PAD_LEFT)
. mt_rand(100, 999);
// 检测是否已经被使用
if (!$model->isTradeIdUsed($newId)) {
break;
}
} while(true);
// 标记为已使用
$model->tradeIeHasBeenUsed($newId);
return $newId;
}
随着业务的发展，二手交易平台因为其环保的理念和便捷的操作，受到了越来越多的青年人群的喜欢，网站流量不断增加，带来了更多的交易。在这背后，比以往都需要更多的交易号。就在这一切都趋向美好的时刻，突然某天晚上正值交易高峰期，客服接收到大量的投诉和反馈，说交易无法正常进行，系统一直处于超时、无法响应状态中！
网站用户的不满，来自高层的压力，以及客服不断的催促，在那一刻，我们能做什么，我们又应该做些什么呢？首先，当故障发生时，要及时止损，快速修复问题。但要解决问题，就要先知道问题出在哪里。而在这一起故障中，问题的根源就在于交易ID的生成函数里，你能想到为什么吗？
流水号ID生成的风险点
不考虑上下文的代码，都是在耍流氓。而考虑欠缺的数据模型，又是引诱别人耍流氓的根本原因。让我们回过头来看下前面交易ID生成的算法，以及其中深藏的危机。
回到第一版实现的create_trade_id()函数，让我们来模拟一下，通过此函数生成的ID，到底重复冲突的情况有多严重。
编写一个实验性的脚本test_create_trade_id.php，并在里面使用create_trade_id()函数不断模拟生成交易ID，不管重复与否，都把每次生成的ID纪录到文件中。当前生成算法，同一天内，最多可以生成非重复的ID有：999 (999 – 100) = 898101个，约90万。让我们尝试生成这90万个交易ID的部分ID，看下会发生什么。因此模拟的场景是，模拟每秒钟生成2个ID，则每分钟生成120个ID，同一天内生成共 24小时
60分钟 60秒
2个 = 172800个ID，约占全部交易ID的20%。也就是说，本次实验性脚本需要的交易ID数量为172800个，小于整体数量，理论上是可以满足的，并且应该产生的ID都是非重复的。
其中，实验性脚本test_create_trade_id.php的代码如下：
<?php
// 每一分钟
for ($j = 0; $j <= 59; $j ++) {
// 每一秒钟
for ($i = 0; $i <= 1; $i ++) {
// 模拟并发
usleep(rand(3, 50));
$id = create_trade_id();
$file = dirname(__FILE__) . sprintf('/create_trade_id_%s.log', date('Ymd'));
file_put_contents($file,
$id . PHP_EOL,
FILE_APPEND
);
}
}
使用Linux系统上的crontab命令，为上面脚本配置一个计划任务，让它每一分钟执行一次。
*/1 * * * * /usr/bin/php /path/to/test_create_trade_id.php
完整执行一天一夜后，对生成的全部交易ID纪录进行分析。首先，生成的交易ID，类似如下：
$ less ./create_trade_id_20180624.log | head -n 5 1874401578 1874401585 1874401608 1874401846 1874401467
然后，统计一下每个ID重复了多少次。可以发现，在本次模拟中，最多会重复14次、然后是重复13次、重复12次……最坏的情况下，重复了14次！
$ less ./create_trade_id_20180624.log | sort | uniq -c | sort -k1nr | head
14 1874301699
14 1874681250
13 1874741218
13 1874761868
13 1874961571
12 1874061102
12 1874081293
12 1874161672
12 1874321743
12 1874341495
我们还可以统计，分别重复1次、2次、3次、……、12次的频次有多少。继续使用sort、uniq、awk命令，可以得到以下数据：
$ less ./create_trade_id_20180624.log| sort | uniq -c | sort -k1nr | awk '{print $1}' | uniq -c | sort -k2n
12891 1
9216 2
9750 3
8620 4
6079 5
3714 6
1919 7
831 8
329 9
126 10
45 11
17 12
3 13
2 14
把这些数据，做成可视化图表，将能更容易发现端倪。频次最高的是重复1次的情况，共有12891次， 其次最多的是重复了3次， 共有9750次。
图1 重复次数的统计
这是在未干预重复出现情况下的统计，即即便重复了也不会重新生成分配，进行重试机制。在这里，我们整体的交易ID总量是898101个，需要的交易ID是172800个，约占整体20%，最后去掉重要的ID后，有效的唯一ID只有53542个，约占整体的6%。由此，按照中学所学的物理公式，这里的有用功只有： 6% / 20% = 30%。这意味着，我们生成了10个交易ID，只有3个是合格的，有效的，唯一的。反过来说，假设我们需要3个有效的交易ID，就需要生成10个候选ID才能满足。而这个30%的有用功，会随意需要的基数变化而变化。具体的变化系数不好评估，但能够明确的是，需要的基数越大，无用功就会越大。
这和硬盘的使用情况是类似的，一开始整个硬盘都是空闲的，随便找一处空间都是有效的。但越往后，随着硬盘的空间使用率越来越高，越到后面，随机寻址找到的空间又是空闲状态的则越来越少，越找越难，耗时也就越来越高。同样地，对于我们的交易ID生成也是一样的道理，一开始随机生成任意一个交易ID都是从未使用过的，越往后，特别是生成的交易ID越来越多时，例如整体的ID使用过半时，能一次性找到有效的ID的概念就会降低，尤其当使用率达到80%或者90%以上时，这时就越发困难了。更不用说，到最后只剩下0.01%的可用ID时，这时几乎是等于小概念事件了。这时随机找到一个可用的iD，简直比上青天还难。
通过交易ID生成这一场景，我们见证了ID生成的简单实现方案，优化改进的方案，以及它隐藏在深处的风险点。
2 生成全局唯一ID标识
与流水号ID类似的是，全局唯一ID也是要求不可重复、有一定的随机性。但不同的是，全局唯一ID标识不会随着时间的推移而有周期性的变化，例如全局用户唯一ID。如果说流水号ID是一个开区间，那么全局唯一ID标识则是一个闭区间，是一个有限集合，生成全局唯一ID只不过是从中产生一个子集合而已。
从双色球到优惠券
中国福利彩票中有一个项目是双色球，我对双色球了解不多，但简单知道它的开奖结果由6个数字结成，这些数字从1到36。
为了模拟实现双色球的开奖结果，曾经在业余时间我们讨论过不同语言下的实现方案。例如Ruby元编程的实现版本：
# double_ball.rb
puts (1..36).to_a.shuffle().take(6).sort.join(',')
运行Ruby代码的方式和结果是：
$ ruby ./double_ball.rb
3,10,19,22,33,35
又如Scala函数式编程的实现版本：
// double_ball.scala
import scala.util.Random
object double_ball extends App {
println(Random.shuffle(1 to 36).take(6).sorted.mkString(","))
}
Scala代码需要先编译，然后运行方式和结果是：
$ scalac ./double_ball.scala $ scala double_ball 9,10,19,29,33,35
而由双色球模拟开奖结果的程序，我们可以联想到优惠券ID生成的独特方式，再延伸到全局唯一ID标识生成的算法。
正如前面所说，在业务上，很多时候都需要提供一个全局唯一标识，以区分企业系统中不同的实体。这些实体，可以不同的用户、银行账号、优惠券、手机唯一标识码等。流水号ID是偏向于映射虚拟世界的概念，而全局唯一标识则是倾向于绑定现实生活世界中的实体。这些唯一ID，也要求不可重复、随机性，并要有一定的防伪能力。
下面以生成一批优惠券ID为例，探索全局唯一ID生成的方式。
第一种生成方式：从未知确定已知
先来看第一种生成方式。受到双色球的启发，我们也可以使用双色球模拟的开奖结果，作为组成优惠券的基本元素。然后对这6个数字进行排序，进行统一的格式化操作，固定每个数字为2位，最后将这些格式化的数字串起来，就可以得到一个优惠券ID。它的实现函数如下：
<?php
/**
* 生成一个优惠券ID
*/
function create_coupons_id() {
// 随机打乱36个数字
$arr = range(1, 36);
shuffle($arr);
// 选取6个数字，并排序
$balls = array_slice($arr, 0, 6);
sort($balls);
// 格式化
foreach ($balls as &$itRef) {
$itRef = sprintf('%02d', $itRef);
}
// 字符串反转
return strrev(implode($balls));
}
当需要生成一批优惠券ID时，我们可以再编写一个辅助函数，它的职责主要是保证最后生成的优惠券ID不会有重复的情况。思索一翻，结合PHP数组的使用，很快就可以得出以下实现代码：
<?php
/**
* 生成一批优惠券ID
*/
function create_more_coupons_id($num) {
$ids = array();
do {
$id = create_coupons_id();
$ids[$id] = true;
} while (count($ids) < $num);
return array_keys($ids);
}
在实现上面两个函数后，就可以对其进行调用，从而生成一批优惠券ID了。
<?php // 生成100个优惠券ID，并预览前面10个 $rs = create_more_coupons_id(100); print_r(array_slice($rs, 0, 10));
将以上三份代码，全部保存到同一个文件double_ball.php ，最后执行此脚本，就可以得到结果了。类似如下：
$ php ./double_ball.php
Array
(
[0] => 630361410190
[1] => 337232719080
[2] => 234232113020
[3] => 033291310150
[4] => 231322516040
[5] => 633382526170
[6] => 624222714111
[7] => 037252913111
[8] => 435281510160
[9] => 237161219060
)
这种方式，我称之为从未知确定已知的方式。因为每次生成的ID都是不确定的，都是随机生成的。但怎么确定这些新的候选ID是可用的呢？那就需要根据已经提供过的ID进行重复判断，而这部分则是可以从缓存、数据库中查找的。最终，得到一个有效的新ID。这就是从未知到已知。一开始，先生成一个，不知道行不行，是未知的。最后检测都合格、未被使用、符合条件后，那就是已知的了。
但这种方式，有一个严重的缺陷，就是当生成的ID越来越多，生成的子集占据整体集合越多时，性能就会明显下降。这和前面的交易ID生成的案例，情况是类似的。针对刚才的double_ball.php脚本，我们依次生成了1个、10个、100个、……、100万个，其脚本执行需要的时间分布如下：
表3 优惠券ID生成的脚本执行时间分布
|
占比
|
生成优惠券的ID数量
|
脚本执行时间
|
|---|---|---|
|
极少
|
1
|
0.014s
|
|
极少
|
10
|
0.014s
|
|
少量
|
100
|
0.015s
|
|
约占0.05%
|
1000
|
0.023s
|
|
约占0.5%
|
10000
|
0.106s
|
|
约占5%
|
100000
|
0.962s
|
|
约占50%
|
1000000
|
13.051s
|
上面脚本执行的时间，根据不同的系统配置，以及每次随机性的差异，都会有所不同。受双色球灵感而设计生成优惠券ID的算法，结合排列结合的计算公式，最终最多可生成的优惠券ID数量是：(36 35
34 33
32 31) / (6
5 4
3 2
1) = 1947792，约200万个。但从这份数据不难发现，生成的优惠券ID越多，需要的时间就越长。
第二生成方式：从已知确定未知
第二种方式，是从已知确定未知。因为整体集合元素是可以确定的，也是可以穷举的（虽然也有可能整体集合元素较多，超出服务器系统的最大内存）。我们可以基于现有的整体集合元素，进行随机打乱，最后截取其中一批提供返回即可。这也是一种方案，而且有时是更为有效的解决方案。让我们一起来看下它的具体实现过程和思路。
当需要穷举时，就可以使用程序三大结构中的循环结构。
<?php
/**
* 生成全部有序的优惠券ID
*/
function create_all_coupons_id() {
// 最大数字是36
$max = 36;
$ids = array();
for ($i = 1; $i <= $max; $i ++) { // 第一个球
for ($j = ($i + 1); $j <= $max; $j ++) { // 第二个球
for ($k = ($j + 1); $k <= $max; $k ++) { // 第三个球
for ($x = ($k + 1); $x <= $max; $x ++) { // 第四个球
for ($y = ($x + 1); $y <= $max; $y ++) { // 第五个球
for ($z = ($y + 1); $z <= $max; $z ++) { // 第六个球
// 排序
$id = array($i, $j, $k, $x, $y, $z);
sort($id);
// 格式化
foreach ($id as &$itRef) {
$itRef = sprintf('%02d', $itRef);
}
// 字符串反转
$id = implode('', $id);
$id = strrev($id);
// 纪录之
$ids[$id] = true;
}
}
}
}
}
}
return array_keys($ids);
}
在这基础上，我们就可以继续完成后面的辅助函数，和调用了。
<?php
/**
* 生成部分优惠券ID
*/
function create_some_ids($num) {
$ids = create_all_coupons_id();
shuffle($ids);
return array_slice($ids, 0, $num);
}
// 生成100个优惠券ID，并预览前面10个
$rs = create_some_ids(100);
print_r(array_slice($rs, 0, 10));
最后也可以得到类似的结果，但要注意内存的使用情况。
3 ID生成的两种策略
关于ID的生成，我们讲解了两个实际的应用场景，一个是交易流水号ID的生成，一个是全局唯一标记优惠券ID的生成。这是两类有微妙区别的ID，但它们的生成方式都有着共同的特点，归根到底，也可以分为两大策略。
这两大策略，可以有很多不同命名方式，最经典的莫过于：以空间换时间，以时间换空间。
策略一：以时间换空间
由于事先不知道需要提供多少个ID，只能需要时才在线实时生成。但随着生成的ID越来越多，这种方式的弊端会越来越明显，因为后期想找到一个有效ID所消耗的时间会更大。但它有个好处就是，如果“生意惨淡”，它可以不用消耗任何资源，因为本来就是延迟生成，直到用到时才会运转。这也是做加法的体现，一开始，什么也没有，然后生成一个ID，接着生成第二个ID……后面的候选ID必须符合前面从未使用的约束，以达到非重复的要求。所以这种策略的特点概括起来有：
实时生成
数量不确定
延迟生成
懒汉式做法
从未知确定已知
做加法
在实现这种策略时，要注意对ID的重复性判断上，考虑到可能跨越的时间周期会很长，因此判断重复性时要对持久化的数据进行检测，避免以偏概全。
策略二：以空间换时间
与第一种策略相对，则是以空间换时间。
这种策略，会提前把全部的ID都穷举罗列出来，然后随机打乱，再批量发货。如果整体的集合过大，则可以采取分批作业，先人为划分几个不等子的集合，再分而治之。因此，它的特点有：
离线运行
整体数量确定
提前生成
饿汉式做法
从已知确定未知
做减法
在实现这种策略时，可以人为手工进行一次性处理。如果整体集合过大需要分批作业时，则可以通过计划任务来定时执行。并且这种策略的实现关键点在于，它把对重复性的判断这一复杂性，通过空间换时间的策略，转换成对临界ID数据的并发获取处理这一问题上。也就是说，提前生成的一批ID，可以放入到队列里面去，当需要用到时，就从中取出一个，但要保证不能重复获取。关于数据的并发读取，已经有成熟方案，可以说这种策略也是把复杂的问题，转化成了我们已经熟悉的问题来处理，也不失为一种启发式的做法。
4 小结
我一直在思考，ID生成的本质是什么，如何才能做到生成的ID既唯一又随机，既简单又快速呢？
本质上，我们都是在有限的集合内找到一个特定的子集，很明显这个子集中的元素都是非重复的。这意味着，如果整体的集合足够大时，而我们所需要的子集又比较小时，那么在圈定子集时发生重复冲突的概率就会大大降低。简单来说，我们可以增长ID的长度，增加可用ID的范围，来快速解决前面的问题。但这只是权宜之计，只能减缓疼痛，但不能根治问题。
最理想的状态是，我们可以构建成完全随机生成ID的算法，这个完美的算法，既能完全生成特定格式的ID，又能保证唯一性，还能体现随机性。但这个确实比较难达到，并且可以提供的ID数量，最终还是会限于所选取的整体集合大小。比如说，我们只允许出现骰子的6个数字，那么不管多精湛的算法，都不会生成7个数字，因为骰子只有1、2、3、4、5、6这六个数字。
比较贴近实际情况的是，ID生成这一过程，是有状态的，而不是无状态的。不管是以空间换时间，还是以时间换空间，都需要有记忆性，以存储已有提供了哪些ID。它不是一个纯函数就能实现的过程，除非不用考虑唯一性。
ID的生成，再往上抽象一个层级，那就是唯一ID的设计。在现实生活中的例子有，手机号码、IP地址、身份证号码等。在设计ID生成器时，我们要先考虑到它的格式要求，它可以由什么组成，不能由什么组成。要考虑它可用的最大数量，以及实际业务场景的使用情况，并且要确保可用数量应远大于实际使用数量，方能保障业务的正常运转。其次才是考虑选择何种策略来实现，最后落实到代码实现细节之上。
以上，就是我关于ID生成的一些思考和感悟。