Instagram 小而美的分片和 ID 生成解决方案
Instagram 是一款以图片和短视频分享为主的社交媒体平台，于 2010 年由 Kevin Systrom 和 Mike Krieger 创建。用户可以通过 Instagram 应用发布和编辑照片和视频，添加滤镜和标签，以及与朋友互动。
上期「人均身价超 5 亿的 Instagram，如何用 3 个工程师支撑 1400 万用户」介绍了 Instagram 早期的快速增长阶段遵循的原则和技术栈，本文展开讲解了他们是如何在工程师团队较小的情况下扩展业务的。
Instagram 每秒要处理 25+ 张照片和 90+ 点赞，数据量巨大。为了确保这些重要的数据能迅速载入内存并快速供用户访问，我们开始将数据分片 (shard) 储存：把数据分布在多个小的存储单元中，每个单元负责一部分数据。
我们的应用服务器是 Django，以 PostgreSQL 作为后端数据库。决定对数据进行分片后，我们面临的首要问题是是否继续使用 PostgreSQL 作为主数据库，还是使用其他系统。我们评估了若干种 NoSQL 数据库解决方案，最终认为最符合我们需求的是将数据分片存储在多台 PostgreSQL 服务器上。
然而，在向这些服务器写入数据之前，我们得解决一个关键问题：如何为数据库中的每一项数据（比如每一张上传的照片）分配一个唯一的标识符。当数据需要同时写入多个数据库时，在单个数据库中使用的自增主键就不再适用了。本文将详细介绍我们是如何解决这个问题的。
首先，我们确定了几个系统必须具备的关键功能：
- 生成的 ID 要能按时间顺序排列（这样一来，我们可以直接对照片 ID 进行排序，而无需额外查询照片的详细信息）。
- 理想情况下，ID 应为 64 位（这样可以缩小索引的大小，并在 Redis 这类系统中实现更有效的存储）。
- 尽量减少系统中新增的复杂组件 — 我们之所以能够在工程师团队相对较小的情况下扩展 Instagram 的业务，很大程度上归功于我们选择了那些简单、易懂且可靠的解决方案。
现有解决方案
针对 ID 生成的问题，市面上有多种解决方案，我们考虑了其中几种：
在 Web 应用程序中生成 ID
这种方法完全依赖应用程序来生成 ID，而不是数据库。比如 MongoDB 的 ObjectId 就是一个例子，它包含 12 字节，其中时间戳占据首位。另外一种常见的做法是使用 UUID。
优点
- 每个应用程序线程都能独立生成 ID，这样可以大幅减少因 ID 生成而引起的系统故障和冲突。
- 如果 ID 的开头是时间戳，那么这些 ID 就能按时间顺序进行排序。
缺点
- 为了确保 ID 的唯一性，通常需要更多的存储空间（96 位或更多）。
- 有些类型的 UUID 是完全随机生成的，无法进行自然排序。
通过特定服务生成 ID
例如，Twitter 开源的雪花算法 (Snowflake) 是一个利用 Apache ZooKeeper 协调各节点并生成 64 位唯一 ID 的解决方案。
优点
- 生成的 ID 长度为 64 位，只有 UUID 的一半。
- ID 的开头可以是时间，这使得 ID 可以按时间顺序排列。
- 它是一个分布式系统，能够处理节点失效的情况。
缺点 引入这种系统会增加我们架构的复杂性，包括需要加入 ZooKeeper 和 Snowflake 服务器等多个新组件。
数据库凭据服务器
这种方法利用数据库自带的自增功能确保数据的唯一性。Flickr 就用这种方式，并设置两台机器对应的参数，一个处理奇数，另一个处理偶数，这样做可以避免系统出现单一故障点。
优点 数据库很好理解，其扩展性相对可预测。
缺点
- 随着时间的推移，写入操作可能成为系统的瓶颈（虽然根据 Flickr 的报告，即使是在非常大的规模下，这也不构成问题）。
- 需要额外管理几台机器（或 EC2 实例）。
- 如果只使用一个数据库，它可能成为系统的脆弱点。使用多个数据库时，则不能保证数据随时间保持可排序性。
在所有这些方法中，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，以便于更好的数据映射。我们已经将这种方法应用到生产中了，迄今为止相当满意！
💡 更多资讯，请关注 Bytebase 公号：Bytebase
