如何设计一个分布式ID生成器保证ID按时间有序?

很多业务有生成唯一 ID 并作为数据库主键的需求。数据库会在这个字段上建立聚集索引(参考 MySQL InnoDB),即该字段会影响各条数据再物理存储上的顺序。

ID还要尽可能,节省内存,让数据库索引效率更高。基本上64位整数能够满足绝大多数的场景,但是如果能做到比64位更短那就更好了。需要根据具体业务进行分析,预估出ID的最大值,这个最大值通常比64位整数的上限小很多,于是我们可以用更少的bit表示这个ID。

查询的时候,往往有分页或者排序的需求,所以需要给每条数据添加一个时间字段,并在其上建立普通索引(Secondary Index)。但是普通索引的访问效率比聚集索引慢,如果能够让ID按照时间粗略有序,则可以省去这个时间字段。为什么不是按照时间精确有序呢?因为按照时间精确有序是做不到的,除非用一个单机算法,在分布式场景下做到精确有序性能一般很差。

More »

[译]《Grokking the System Design Interview》设计Dropbox

这是一篇双语翻译的文章,原文出自 grok_system_design_interview.pdf 的一篇文章《Designing Dropbox》设计 Dropbox。


Let’s design a file hosting service like Dropbox or Google Drive. Cloud file storage enables users to store their data on remote servers. Usually, these servers are maintained by cloud storage providers and made available to users over a network (typically through the Internet). Users pay for their cloud data storage on a monthly basis. Similar Services: OneDrive, Google Drive Difficulty Level: Medium

More »

[译]《Grokking the System Design Interview》设计Facebook Messenger

这是一篇双语翻译的文章,原文出自 grok_system_design_interview.pdf 的一篇文章《Designing Facebook Messenger》设计 Facebook Messenger。


Let’s design an instant messaging service like Facebook Messenger where users can send text messages to each other through web and mobile interfaces. 让我们设计一个像 Facebook Messenger 这样的即时消息服务,用户可以通过网络和移动界面互相发送短信。

More »