唯一ID生成原理与phper的深度思考

JerryXia 发表于 2017-06-15 19:36:36 , 阅读 (24)

唯一ID引发的血案

写这篇 blog 原因是业务中遇到生成唯一ID的场景却没有按照需求生成唯一ID，由此引发了一番乱炖，业务中目前使用的方案：

// mysql 自增ID + 事务 + 时间 + 随机数public function generateTradeNumber(){    $tradeTime = date('YmdHi', time());    $lastTrade     = TradeNumber::findBySql('SELECT * FROM `Trade` ORDER BY id DESC LIMIT 1 FOR UPDATE');    $lastTradeTime = '';    if (!empty($lastTrade)) {        $lastTradeNumber = $lastTrade->getTradeNumber();        $lastTradeTime   = substr($lastTradeNumber, 0, 12);        $lastTradeSerial = substr($lastTradeNumber, 12);        if ($tradeTime == $lastTradeTime) {            return $lastTradeTime . ($lastTradeSerial >= 99999 ? $lastTradeSerial + 1 : '0' . ($lastTradeSerial + 1));        }    }    $initSerialNumber = rand(10000, 99999);    return $tradeTime . '0' . $initSerialNumber;}

简单解释一下：

唯一 TradeNumber 由 2 部分组成：当前时间 12 位 + 6 位数字
时间粒度到分：date('YmdHi', time())
当前分钟第一个进来的 Trade 会分配 rand(10000, 99999)（这样做是为了保持长度一致，以及防止被人找出规律来）
如果遇到并发场景，通过 mysql 死锁最后一条 Trade（SELECT FOR UPDATE），然后在上一个 TradeNumber 后面的数字部分加 1

todo：这一段的理解有还有问题

然而实际上并没有达到唯一ID 的目的，查询数据库发现还是有重复 TradeNumber 存在

php uniqid() 分析

php manual uniqid()

详细的分析当然是直接看源码最清楚了，不过 php manual 已经说了：based on the current time in microseconds。并且 php manual 中已经详细说明了这个问题，详细可以查看 php manual note 中的内容，note 中提供了另外一种方案：

function uniqidReal($lenght = 13) {     // uniqid gives 13 chars, but you could adjust it to your needs.     if (function_exists("random_bytes")) {         $bytes = random_bytes(ceil($lenght / 2));     } elseif (function_exists("openssl_random_pseudo_bytes")) {         $bytes = openssl_random_pseudo_bytes(ceil($lenght / 2));     } else {         throw new Exception("no cryptographically secure random function available");     }     return substr(bin2hex($bytes), 0, $lenght); }

这种方案的原理：随机数。当然这个随机数概率就比 rand(10000, 99999) 小多了，毕竟加入了英文字母。那么，回到我们的主题，随机数 === 唯一ID ？显然，无论概率怎么小，还是存在重复的可能（-_-）。

唯一ID原理

Linux多线程与同步：http://www.cnblogs.com/vamei/archive/2012/10/09/2715393.html
《高性能linux服务器编程》- 高性能 io - 进程相关部分
唯一ID生成原理与PHP实现：http://mp.weixin.qq.com/s/bagOgzdwLyZv_ITNVnYfoQ / https://github.com/liexusong/atom

其实非常的简单，只要保证从同一个地方产生，并按照不重复的规律生成。联想一下 mysql 的自增ID，就是 同一张表，依次递增。所以，自增ID真正的难点：同一个地方生成。但是，在多进程、多线程的场景下，这个地方就会成为 竞态资源。要了解race condition, mutex和condition variable的概念，请参考上面的博文 -- Linux多线程与同步。

多线程同步方式：

互斥锁(mutex)：一个线程申请了互斥锁，然后进行 原子操作，其他进程必须要等待此线程释放互斥锁，才能成功申请。
条件变量(condition variable)：配合互斥锁一起使用，在 多个线程等待某个条件发生 时的场景下使用
读写锁(reader-writer lock)：和互斥锁类似，锁有 3 种状态 -- R、W、unlock。如果资源上 R 锁，其他线程可以继续申请 R 锁；如果需要申请 W 锁，必须等待其他进程都释放 R 锁；如果资源上 W 锁，其他线程必须等待其释放

多进程的同步方式：

管道
共享内存

是不是有点峰回路转，怎么突然跑到操作系统层面了？whatever，你曾经学的操作系统原理，就是这么有用。

再来简单的剖析一下 唯一ID生成原理与PHP实现 这篇博文中提到的 snowflake算法：

唯一ID组成：64bit， 1bit（不用）+ 41bit（时间戳）+ 10bit（机器id）+ 12bit（序列号）
时间毫秒级（可以用2082年），每毫秒最多 2^12=4096 个请求，如果超过了，就分配到下一毫秒
为什么分机器ID：达到分布式计算，避免不同机器间同步带来的性能损耗

代码就不贴了，大家自己看，挺简单的。

唯一ID的php实现

韩天峰(Rango) - 从零开始编写第一个PHP扩展：http://wiki.swoole.com/wiki/page/238.html
淘宝信海龙 php 扩展开发：http://www.bo56.com/category/programming-language/php-programming-language
唯一ID生成原理与PHP实现：http://mp.weixin.qq.com/s/bagOgzdwLyZv_ITNVnYfoQ / https://github.com/liexusong/atom
韩天峰(Rango) Yii/Yaf/Swoole3个框架的压测性能对比：http://rango.swoole.com/archives/254

由于 php-fpm 是基于进程管理，每个pfm子进程都是相互独立的，想要实现 同一个地方生成，就需要依靠扩展。而php扩展开发，不少业内大牛都贴了教程，无耻引用几个。

推荐学习次序：

韩天峰(Rango) - 从零开始编写第一个PHP扩展
淘宝信海龙 php 扩展开发系列教程
查看 https://github.com/liexusong/atom 源码：github 上的文档只提到了 2 个函数，还是直接读源码吧，主要是 atom.c

[ 技术文章推荐 ]