真假唯一数

在真实的业务场景中生成唯一数是很常用的功能,也是面试必考题。最近面试一个PHP开发岗位,无意中聊到这个话题,然后顺着话题一直拓展。今天说下在面试中,面试官问这个问题想得到怎样的答案。

每种编程语言都提供了唯一数生成函数,但是都有条件限制,先看看网上都有哪些生成唯一数的方法。

一. 散列+时间+随机值

1
md5(time() . mt_rand(1,1000000));

time()函数获取当前时间戳,mt_rand(1,1000000)函数获取一个1到1000000的随机值,看着好像生成的数能唯一,但这行代码的问题其实非常多。

在代码中时间是很不靠谱的参数,如果用户1秒内发送了2个请求,那么time()字段毫无意义。

在代码中随机数其实并不随机,常见的随机数都需要有随机种子,而为了保证种子不被猜到,编程语言默认会使用当前系统时间作为种子。又变成了依赖时间的一个参数,所以这种方案不可取。

二. 微秒+进程编号

1
uniqid();

uniqid()函数可以得到一个基于微秒和进程编号的唯一ID。对于php-fpm来说,每个请求都独占一个进程,一个进程会串行的处理多个请求。所以通过进程编号+微秒时间看上去能生成唯一ID。但深究之后发现并不靠谱。

1秒等于100万微秒,现在问题会变成一个进程能在百万分之一秒内处理多个请求吗?答案是可以的,用当前最普通的CPU来说,单核心1秒就可以计算20亿次,1微秒可以计算2千次。从计算机调度的角度来说,2千次同时处理到一个进程的两个请求是完全可能的。所以又变成了依赖时间的一个参数,这种方案不可取。

你还能使用纳秒,皮秒等精度更高的时间参数,但以发展的远光看问题,未来CPU的算力会越来越快,依赖时间的唯一性会越来越差。无论怎么努力,只依靠编程语言自身得到唯一ID是非常困难的,也是我不推荐的。

三. 数据库

靠编程语言自己走不通,那就通过第三方工具,这种方案是靠谱的。但实现起来也有很多种方法。

1
2
3
4
5
6
LOCK TABLES id_maker;
//拿到id
select id from id_maker;
//加1更新
update id_maker set id=id+1;
UNLOCK id_maker;

这是我曾经见过的一种id_maker用法,这样每次得到的id都是唯一并且有序的。但问题就是需要锁表,性能不高,在高并发下会发生资源抢占导致数据库崩溃。

1
2
3
//id_maker表有自增id和内容data两个字段
insert into id_maker(data) values('');
select last_insert_id();

这种方式性能就高很多,insert语句不会锁表,自增id百分百保证唯一性且有序。唯一的问题是需要定期删除历史数据,对于大部分项目我都建议使用这种方式生成唯一ID。

除了MySQL还有MongoDB,Redis等其他数据库方案,方法大同小异。但是这个方案有局限性,当我们的业务发展到成千上万台服务器时通过一个数据库的一张表去生成ID会导致性能下降拖垮其他服务,还会形成单点依赖。

四. 微秒+服务器编号+计数器

Twitter开源了他的唯一ID生成方案,名字叫SnowFlake,这种方案的原理非常简单,很容易基于SnowFlake算法做扩展。比如PHP并不会常驻内存,计数器的实现比较麻烦,但只要原理清楚了使用扩展或者数据库很容易实现。

这个方案的最大优点就是在庞大的集群中,每个服务靠自己就能算出全局的唯一ID。微秒能保证ID有序,服务器编号能确定到具体机器,计数器(可以理解为只为当前服务器提供的id_maker)能保证当前机器所有请求的唯一性,通过这些参数生成的唯一编号有序并且无懈可击。

如上四点写的其实是一种思路,处理问题都是由简单到复杂,由一到二。如果直接给面试官说终极方案,面试官会基于终极方案问更多复杂的问题,更多离业务非常贴近的问题,如果没接触过相关业务直接就pass了。所以由简单到复杂,讲清楚技术原理和思考过程,offer离你就不远了。

打赏时请留下微信号