原文 https://instagram-engineering.com/sharding-ids-at-instagram-1cf5a71e5a5cInstagram 是一款以图片和短视频分享为主的社交媒体平台，于 2010 年由 Kevin Systrom 和 Mike Krieger 创建。用户可以通过 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 就用这种方式 (https://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/)，并设置两台机器对应的参数，一个处理奇数，另一个处理偶数，这样做可以避免系统出现单一故障点。
随着时间的推移，写入操作可能成为系统的瓶颈（虽然根据 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 现有的自动递增功能来处理。一个具体的例子：设想现在是 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 位中。最后，我们获取每个 schema 中每个表特有的自增序列的下一个值，并用这个值填充剩余的位数。假设这个表已经生成了 5000 个 ID，那么下一个 ID 就是 5001。我们将这个数字对 1024 取模（以确保它能够适配 10 位空间），并将结果包含在内。现在我们生成了 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 签约 Xendit，助力东南亚 Stripe 数据库变更自动化
管理者如何在团队里讨论那些不便讨论的话题
召唤新版「数据库 GitOps 」体验官，赢取新款 Bytebase 限量周边！
从 MySQL 到 DynamoDB，Canva 如何应对每天新增的 5000 万素材