Instagram 的分片与 ID 设计

听听那冷雨

笔记

发布于：2020年6月3日

次浏览

Instagram上有大量的数据，每分钟就有超过25张的图片和90个点赞。为了确保所有重要的数据都能被合理存储并且及时得被提取应用，我们对数据进行了分片（sharding）——也就是说，我们把数据放到多个桶（bucket）中，每个桶里都有一部分数据。

我们的应用服务器上运行的是Django， 后端数据库是PostgreSQL。对数据分片首先要决定是否要保留PostgreSQL作为主要的数据存储库，是否要采用其他的数据库。经过评估一些不同的数据库解决方案，我们最终确定最适合的方案是在PostgreSQL数据库集群上实现数据分片。

然而在把数据写到数据库之前，我们还要解决如何给数据（例如Instagram上发布的没一张图片）加上唯一标识符的问题。在单一数据库上的典型解法——使用数据库自带的自增主键功能——在当数据需要被同时插入到多个数据库时就不适用了。文章的下面就来讲讲我们是如何解决这个问题的

开始前，我们先列出系统所需要的所有重要的功能。

1. 产生的数据ID需是可以按时间排序的。（比如对一列图片数据的ID进行排序，可以不需要提取太多图片本身的信息）
2. 理想的ID是64位的。（这样索引更小，存储也更优，像Redis）
3. 系统要尽量少的引用“可变动因素”——在很少工程师的情况下还可以扩张Instagram的很大一部分原因就是，我们相信简单易懂的方案。

现有的解决方案

由Web应用层生成ID

这种方案将ID的生成完全交到应用层，而不是数据库。例如，MongoDB的ObjectId，就是12字节长并且在最前面加上时间戳进行编码。另一个流行的方案是使用UUIDs。

优点：

1. 每个应用线程独立生成ID，最小的降低ID生成的失败和竞争。
2. 如果用时间戳作为ID的起始部分，那么ID可以按时间排序。

缺点：

1. 通常需要更多的存储空间（96位或者更多）来确保ID的合理唯一性。
2. 一些UUID类型完全是随机的，无法排序。

通过单独的服务产生ID

例如：Twitter的Snowflake，是一个Thrift服务，使用了Apache Zookeeper来协调各个结点并且产生64为的唯一ID。

优点：

1. Snowflake的ID只有64位，是UUID的一半。
2. 可以放时间戳到ID头，从而可以按时间排序。
3. 分布式系统保证了系统结点不会挂掉。

缺点：

增加了复杂性，而且引入了更多的“可变动因素”（如ZooKeeper, Snowflake服务器）到系统构架中。

数据库票据（DB Ticket）服务器

利用数据库自带的自增特性来确保唯一性。Flicker采用这一方法，不过还用了两台ticket数据库（一个生成偶数，一个生成奇数）来避免单点失败。

优点：

数据库好理解，带有易预测的可扩张功能。

缺点：

1. 最终会出现数据写入的瓶颈（尽管Flicker称在高扩展下没有问题）。
2. 需要管理多的两台服务器（或者EC2实例）。
3. 如果单独使用数据库，会出现单点失效。如果使用多个数据库，则不能保证ID可以按时间排序。

在所有这些方案中，Twitter的snowflake是最接近的，但是生成ID所需的添加复杂性又和我们的目标冲突。我们的替换方案是采用概念上相近的方法，但是带到PostgreSQL内部实现。

Instagram 的方案

我们的分片系统是由上千个“逻辑”分片组成的，由代码映射到少量的物理分片。

通过这个方法，我们一开始用少数数据库实现，慢慢扩展到更多个数据库，只需要把部分逻辑分片从一台数据库转移到另一台数据库里，不需要重新把数据重新聚合。我们用到的PostgreSQL的schema的特性可以轻松的实现计划和管理。

Schema（不要和SQL单个表的schema搞混了）是PostgreSQL里的一个逻辑分组功能。每一个PostgreSQL数据库都有好几个schema，每一个schema都有一到多个表。表名在没个schema中都是唯一的，而不是每个数据库，默认情况下，PostgreSQL会把所有数据都放在一个叫“public”的schema中。

在我们的系统中每个“逻辑”分片都是一个PostgreSQL schema， 每个分片的表（比如照片的“点赞”功能）都存在每个schema中。

我们通过使用PL/PGSQL, PostgreSQL内部的编程语言，和PostgreSQL现有的自增功能来生成ID。

每个ID都由下面几个部分组成：

1
2
3

41位的毫秒级时间（用于产生41年的ID）
13位用来表示逻辑分片的ID
10位的自增序列，模上1024， 意味着每个分片每毫秒可以产生1024个ID

下面通过一个例子说明：比如说现在是2011年的九月九日，我们的纪元是从2011年的一月一号开始。从新纪元开始到此有1387263000毫秒，那么我们把这个数字左移41位来填满ID的头。

id = 1387263000 <<(64 – 41)

接下来， 我们拿来我们准备把这个数据插入的分片ID；如果我们用户ID是31341， 这个分片的ID是 31341%2000 → 1341。 我们接下来把下面13为填满：

id |= 1341 << (64-41-13)

最后， 我们用所剩的自增序列（每个schema中每个表中这个序列都是唯一的）来填满的后面的位数。 假设这张表中已经有了5000个ID； 我们下一个数据就是5001，我们把它模上1024得到：

id |= （5001%1024）

我们就得到了我们的ID， 我们把这个id作为insert中的RETURNING返回给应用层。

下面是是实现以上过程的PL/PGSQL代码（这里用的schema是insta5）

1
2
3
4
5
6
7
8
9
10
11
12
13
14

CREATE OR REPLACE FUNCTION insta5.next_id(OUT result bigint) AS $$
DECLARE
    our_epoch bigint := 1314220021721;
    seq_id bigint;
    now_millis bigint;
    shard_id int := 5;
BEGIN
    SELECT nextval('insta5.table_id_seq') %% 1024 INTO seq_id;
    SELECT FLOOR(EXTRACT(EPOCH FROM clock_timestamp()) * 1000) INTO now_millis;
    result := (now_millis - our_epoch) << 23;
    result := result | (shard_id << 10);
    result := result | (seq_id);
END;
$$ LANGUAGE PLPGSQL;

要生成表示执行下面的部分：

1
2
3
4

CREATE TABLE insta5.our_table(
    "id" bigint NOT NULL DEFAULT insta5.next_id(),
    ... rest of table schema ...
)

成了！我们得到了应用中唯一的主键（还有一个好处是，ID中包含了分片ID可以用来轻松映射）。我们已经把这个方法用在产品中，并且对结果感到非常满意。

本文来自：Instagram 的分片与 ID 设计

更新于：2020年6月12日

Algorithm