互联网面试——分布式ID生成器

如何设计一个分布式ID生成器，并保证ID大致按时间排序？

应用场景现实中，很多商家都有生成唯一ID的需求，比如：

用户ID微博ID聊天消息ID帖子ID需求(Needs)这个ID经常作为数据库的主键，所以需要全局唯一。数据库将在该字段上建立聚集索引(聚集索引)。

参考MySQL InnoDB)，即该字段会影响物理存储中每条数据的顺序。ID应该尽可能短，以节省内存并提高数据库索引的效率。基本上64位整数可以满足大部分场景。

但如果能短于64位就更好了。我们需要分析具体的业务，估算出ID的最大值，这个值通常比64位整数的上限小很多，所以我们可以用更少的位数来表示这个ID。查询时，

经常需要分页或者排序，所以需要给每一段数据添加一个时间字段，并在其上建立二级索引。但是普通索引的访问效率比聚集索引慢。如果ID可以大致按时间排序，

这个时间字段可以省略。为什么不按照时间精确有序？因为无法做到按照时间精确有序，除非使用单机算法，否则在分布式场景下精确有序的表现普遍较差。这导致ID生成的三个核心要求：

根据时间排序，全局唯一性尽可能短。下面是一些常用的生成ID的方法。

UUID任何使用过MongoDB的人都会知道，MongoDB会自动给每条数据赋予一个唯一的ObjectId，以确保它不会重复。这是如何工作的？实际上它使用了UUID算法，

生成的ObjectId占12个字节，由以下部分组成。

Unix时间戳，用4个字节表示的3，用3个字节表示的机器ID，用2个字节表示的进程ID，用3个字节表示的计数器UUID是一类算法的统称，有不同的实现。UUID的优点是每台机器可以独立生成ID。

理论上保证不重复，所以自然分布。缺点是生成的ID太长，不仅占用内存，而且索引查询效率低。

多个MySQL服务器既然MySQL可以生成自增ID，那么是否可以用多个MySQL服务器组成一个高性能的分布式horn？显然你可以。假设八台MySQL服务器协同工作，第一个MySQL的初始值为1，

每次增加8，第二个MySQL的初始值为2，每次增加8，以此类推。前端被循环负载平衡器阻塞。每次有请求时，

循环平衡器将请求随机发送到八台MySQL机器中的任何一台，然后返回一个ID。Flickr就是这么做的，只用了两台MySQL服务器。可见这种方法虽然简单无脑，

但是性能足够好。但是需要注意的是，在MySQL中，不需要保存所有的ID，每台机器只需要保存一个MAX_ID。这需要MySQL的替换功能。与单桌数据库相比，

缺点是ID不是严格递增，只是粗略递增。不过，这并不是什么大问题。我们的目标是粗糙有序的，不需要严格的增加。

比如Twitter雪花，Twitter有一个成熟的开源项目，致力于生成ID，Twitter雪花。雪花的核心算法如下：

最高位不用，永远为0，其余三组bit占位均可浮动，看具体的业务需求而定。默认情况下41bit的时间戳可以支持该算法使用到2082年，10bit的工作机器id可以支持1023台机器，

序列号支持1毫秒产生4095个自增序列id。Instagram用了类似的方案，41位表示时间戳，

13位表示shard Id(一个shard Id对应一台PostgreSQL机器),最低10位表示自增ID，怎么样，跟Snowflake的设计非常类似吧。

这个方案用一个PostgreSQL集群代替了Twitter Snowflake 集群，优点是利用了现成的PostgreSQL，容易懂，维护方便。有的面试官会问，

如何让ID可以粗略地按照时间排序？上面的这种格式的ID，含有时间戳，且在高位，恰好满足要求。如果面试官又问，如何保证ID严格有序呢？在分布式这个场景下，是做不到的，要想高性能，只能做到粗略有序，

无法保证严格有序。