Instagram 的分布式数据库生成时序 ID 策略

Jul 02, 2017 分布式, 数据库 https://git.io/vATZM

https://engineering.instagram.com/sharding-ids-at-instagram-1cf5a71e5a5c

这是一篇 2012 年的文章,那时候 Instagram 每秒钟有 25 张新照片和 90 个赞,服务器是用的 Django,数据库是 PostgreSQL。为了提高性能,他们开始做一些数据库的分区(shard),第一个问题就是多节点如何生成 ID。传统单节点数据库直接一个自增的主键就可以了,多节点就不能这么处理了。而且需要满足:1. ID 本身是有时序的;2. ID 需要是 64 位(bit);3. 要足够简单和容易在现有系统上升级。

现有方案 1:在应用程序端生成 ID,比如 UUID。优点是,完全独立几乎不可能重复,而且可以有时序。缺点是,ID 的位数太多了( >= 96 bit),而且有一些 UUID 类型是完全随机不能排序。

现有方案 2:服务器端生成 ID,比如 Twitter 的 Snowflake 或者依赖 ZooKeeper 生成的节点 ID。优点是,位数少、加上时间就有时序、有节点挂掉也是可以容忍的。缺点是,给系统架构引入了额外的部分,迁移成本较高。

现有方案 3:数据库来存 ID,比如当时 Flickr 就是这么做的。优点是足够简单。确定也很明显,数据库的写操作很容易成为系统瓶颈,而且需要额外的计算节点来操作数据库,另外如果是单节点没有冗余,多节点又不能保证时序。

Instagram 的策略是:利用 Postgre 自带的特性把数据库划分几千个逻辑分区,这些逻辑分区分布在少得多的物理节点上。ID 的策略就是,前 41 位是从某个指定时间开始的毫秒数(可以使用 41 年),中间 13 位是逻辑分区的 ID,最后 10 位是这个逻辑分区自己的一个自增序列对 1024 取余的值,也就是说每个逻辑分区每毫秒可以生成 1024 个 ID。