KK's blog

每天积累多一些

0%

Design Distributed ID Generator

题目大意:

生成唯一ID如用户ID,订单ID。

解题思路:

基本思路是将所有网站映射到一个整数。
三大核心需求:

  1. 全局唯一(unique)
  2. 按照时间粗略有序(sortable by time)。按时间查询是普遍的请求,如得到最新的1000个用户。
  3. 尽可能短。省空间,查询要更有效率。

UUID:

UUID是一类算法的统称,具体有不同的实现。UUID的有点是每台机器可以独立产生ID,理论上保证
不会重复,所以天然是分布式的,缺点是生成的ID太长,不仅占用内存,而且索引查询效率低。
4个字节表示的Unix timestamp,
3个字节表示的机器的ID
2个字节表示的进程ID
3个字节表示的计数器

多机器分别自增:

假设用8台MySQL服务器协同工作,第一台MySQL初始值是1,每次自增8,第二台MySQL初始值是2,
每次自增8,依次类推。前面用一个 round-robin load balancer 挡着,每来一个请求,由
round-robin balancer 随机地将请求发给8台MySQL中的任意一个,然后返回一个ID。
load balance可以确保请求平均分配到不同的机器,所以粗略有序,缺点是加机器要re-hash这些Id
且顺序不够稳定。

Twitter Snowflake:

原理与UUID基本一样。也是时间戳+机器id+自增序号。时间戳保证有序。

Free mock interview