Instagram小而美的分片和ID生成解决方案

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

Instagram 是一款以图片和短视频分享为主的社交媒体平台，于 2010 年由 Kevin Systrom 和 Mike Krieger 创建。用户可以通过 Instagram 应用发布和编辑照片和视频，添加滤镜和标签，以及与朋友互动。

上期「人均身价超 5 亿的 Instagram，如何用 3 个工程师支撑 1400 万用户」介绍了 Instagram 早期的快速增长阶段遵循的原则和技术栈，本文展开讲解了他们是如何在工程师团队较小的情况下扩展业务的。

---

Instagram 每秒要处理 25+ 张照片和 90+ 点赞，数据量巨大。为了确保这些重要的数据能迅速载入内存并快速供用户访问，我们开始将数据分片 (shard) 储存：把数据分布在多个小的存储单元中，每个单元负责一部分数据。

我们的应用服务器是 Django，以 PostgreSQL 作为后端数据库。决定对数据进行分片后，我们面临的首要问题是是否继续使用 PostgreSQL 作为主数据库，还是使用其他系统。我们评估了若干种 NoSQL 数据库解决方案，最终认为最符合我们需求的是将数据分片存储在多台 PostgreSQL 服务器上。

然而，在向这些服务器写入数据之前，我们得解决一个关键问题：如何为数据库中的每一项数据（比如每一张上传的照片）分配一个唯一的标识符。当数据需要同时写入多个数据库时，在单个数据库中使用的自增主键就不再适用了。本文将详细介绍我们是如何解决这个问题的。

首先，我们确定了几个系统必须具备的关键功能：

1. 生成的 ID 要能按时间顺序排列（这样一来，我们可以直接对照片 ID 进行排序，而无需额外查询照片的详细信息）。

2. 理想情况下，ID 应为 64 位（这样可以缩小索引的大小，并在 Redis 这类系统中实现更有效的存储）。

3. 尽量减少系统中新增的复杂组件 — 我们之所以能够在工程师团队相对较小的情况下扩展 Instagram 的业务，很大程度上归功于我们选择了那些简单、易懂且可靠的解决方案。

现有解决方案

针对 ID 生成的问题，市面上有多种解决方案，我们考虑了其中几种：

在 Web 应用程序中生成 ID

这种方法完全依赖应用程序来生成 ID，而不是数据库。比如 MongoDB 的 ObjectId 就是一个例子，它包含 12 字节，其中时间戳占据首位。另外一种常见的做法是使用 UUID。

优点

1. 每个应用程序线程都能独立生成 ID，这样可以大幅减少因 ID 生成而引起的系统故障和冲突。

2. 如果 ID 的开头是时间戳，那么这些 ID 就能按时间顺序进行排序。

缺点

1. 为了确保 ID 的唯一性，通常需要更多的存储空间（96 位或更多）。

2. 有些类型的 UUID 是完全随机生成的，无法进行自然排序。

通过特定服务生成 ID

例如，Twitter 开源的雪花算法 (Snowflake) 是一个利用 Apache ZooKeeper 协调各节点并生成 64 位唯一 ID 的解决方案。

优点

1. 生成的 ID 长度为 64 位，只有 UUID 的一半。

2. ID 的开头可以是时间，这使得 ID 可以按时间顺序排列。

3. 它是一个分布式系统，能够处理节点失效的情况。

缺点

1. 引入这种系统会增加我们架构的复杂性，包括需要加入 ZooKeeper 和 Snowflake 服务器等多个新组件。

数据库凭据服务器

这种方法利用数据库自带的自增功能确保数据的唯一性。Flickr 就用这种方式 (https://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/)，并设置两台机器对应的参数，一个处理奇数，另一个处理偶数，这样做可以避免系统出现单一故障点。

优点

1. 数据库很好理解，其扩展性相对可预测。

缺点

1. 随着时间的推移，写入操作可能成为系统的瓶颈（虽然根据 Flickr 的报告，即使是在非常大的规模下，这也不构成问题）。

2. 需要额外管理几台机器（或 EC2 实例）。

3. 如果只使用一个数据库，它可能成为系统的脆弱点。使用多个数据库时，则不能保证数据随时间保持可排序性。

在所有这些方法中，Twitter 的雪花算法方法最接近我们的需求，但是运行一个专门的 ID 服务的复杂性让我们望而却步。因此，我们选择了一个在概念上相似但更简化的方法，即将此系统集成到 PostgreSQL 中。

我们的方案

我们建立了一个包含数千个「逻辑」分片的系统，这些逻辑分片在编程中映射到较少的物理分片上。利用这种策略，我们最初只需几台数据库服务器即可运行，随后可以通过将一组逻辑分片从一个数据库迁移到另一个，逐步扩大到更多服务器，而无需重新整理数据。我们用了 Postgres 的 schemas 功能来方便脚本编写和系统管理。

Schema（不要与单表的 SQL schema 混淆）是 Postgres 中用于逻辑分组的功能。每个 Postgres 数据库可以包含多个 schema，每个 schema 内可包含一个或多个表。在每个 schema 中，表名必须是唯一的，而默认情况下，Postgres 会将所有内容放置在名为 public 的 schema 中。

在我们的系统中，每个逻辑分片就是一个 Postgres 的 schema，每个分片的表（比如图片的点赞）都设在每个 schema 内。

我们将每个分片内的表的 ID 创建任务委托给了 PL/PGSQL（Postgres 的内部编程语言）和 Postgres 现有的自动递增功能来处理。

我们的每个 ID 结构如下：

• 41 位用于记录时间（以毫秒计），这样可以保证 41 年内的每个毫秒都有唯一的 ID。

• 13 位用于标识逻辑分片的 ID。

• 10 位用于一个自动递增的序列，以 1024 为模。也就是说每个分片在每毫秒内可以生成多达 1024 个 ID。

一个具体的例子：设想现在是 2011 年 9 月 9 日下午 5:00，而我们的「纪元 (epoch)」起始于 2011 年 1 月 1 日。从纪元开始到现在已经过去了 1387263000 毫秒，因此在构造 ID 的时候，我们将这个时间值填充到 ID 的最左边的 41 位，并将其向左移位

id = 1387263000 <<(64-41)

接下来，我们将获取我们试图插入数据的特定分片 ID。假设我们根据用户 ID 来分片，而总共有 2000 个逻辑分片；如果用户 ID 是 31341，那么计算得到的分片 ID 是 31341 % 2000 -> 1341。我们将这个值填入接下来的 13 位中。

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

最后，我们获取每个 schema 中每个表特有的自增序列的下一个值，并用这个值填充剩余的位数。假设这个表已经生成了 5000 个 ID，那么下一个 ID 就是 5001。我们将这个数字对 1024 取模（以确保它能够适配 10 位空间），并将结果包含在内。

id |= (5001 % 1024)

现在我们生成了 ID，可以通过在 INSERT 语句中使用 RETURNING 关键字，将其返回给应用服务器。

以下是用于实现这一切的 PL/PGSQL 示例 (针对示例 schema insta5):

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;

创建表格时，只需这样操作：

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

就是这样！我们应用中的主键是唯一的，并且（更方便的是）它们包含了分片 ID，以便于更好的数据映射。我们已经将这种方法应用到生产中了，迄今为止相当满意！