Instagram架构的分片和ID的设计 instagram页面布局分析

前言

每秒上传超过25张图和90个“喜欢”，在Instagram我们存了很多数据，为了确保把重要的数据都扔到内存里，达到快速响应用户的请求，我们已经开始把数据进行分片-换句话说，把数据放到更多的小桶子里，每个桶了装一部分数据。

我们的应用服务器跑的是Django和后端是PostgreSQL，在决定要分片后的第一个问题是，是否还继续用PostgreSQL作为主要数据仓库，或者换成别的？我们评估了一些NoSQL的解决方案，但最终决定最好的解决方案是：把数据分片到不同的PostgreSQL数据库。

在写数据到不同服务器之前，还需要解决一个问题，如何给在数据库里的每块数据都标识上唯一的标识（如，发布到我们系统的每张图）。单库好解决，就是用自增主键-但如果数据同时写到多个库就不行了，本博客将回答如果解决这个问题。

开始前，先列出系统的主要实现目标：

1. 生成的ID可以按时间排序（如，一个图片列表的id，可以不用获取更多信息即可直接排序）
   
2. ID最好是64位的（这样索引更小，存储的也更好，像Redis）
   
3. 系统最好尽可能地只有部分是“可变因素”-很大部分原因为何在很少工程师的情况下可以扩展Instagram，就是因为我们相信简单好用！

现有的解决方案

很多类似的ID解决方案都有些问题，下面是一小部分例子：

在web应用层生成ID

这类方法把生成ID的任务都扔到应用层实现，而不是数据库层。如，MongoDB’s ObjectId，是一个12字节长的编码的时间戳作为第一部分，另外一种流行的方法是用UUIDs。

优点：

1. 每个应用服务生成的ID是独立的，生成时将失败和竞争降到最小；
   
2. 如果用时间戳作为第一部分，就可以按时间排序

劣势：

1. 需要更多存储空间（96位或更多）才能保证唯一性；
   
2. 一些UUID类型的完全是随机数，没有排序特性；
   

由单独的服务提供ID生成

如：Twitter的Snowflake，是一个Thrift服务用到Apache ZooKeeper协调各节点并生成一个唯一的64位ID。

优势：

1. Snowflake生成的ID是64位，只用UUID的一半大小；
   
2. 可以把时间排到前面，可以排序；
   
3. 分布式系统可以保证服务不会挂掉；

劣势：

1. 系统会变得更复杂和更多的“可变因素”（ZooKeeper, Snowflake 服务）加入到我们的架构。
   

数据库计数服务器

用数据库自增字段的能力来保证唯一性（Flickr用了这个方法），但用了两台计数服务器（一台是生成奇数，另外一台是偶数）才能避免单点失效。

1. 可能最终变成写入是个瓶颈（尽管Flickr报告过这一点，但在高扩展下并不是个问题）；
   
2. 新增了两台服务器要管理（或是EC2实例）；
   
3. 如果用单台数据库，会有单点失效问题，如果用多个库，不能保证他们是可按时间排序的；
   

所有以上的方法中，Twitter的Snowflake最接近，但添加生成ID服务了复杂调用又冲突了，替换的方案是，我们使用了概念类似的方法，但是从PostgreSQL内部特性实现的。

我们的解决办法

我们的分片系统由几千个逻辑分片组成，由代码指向极少的几个物理分片，用这个方法，我们可用少数几台服务器就可以实施起来，以后也可以扩展到更多，只要简单的将逻辑分片从一台物理数据器移到另外一台，不需要重新聚合各分片的数据，我们用PostgreSQL的schema特性很容易就做到实施和管理。

Schema（不要跟建单个表的SQL schema搞混了）在PostgreSQL是一个逻辑分组的功能，每台PostgreSQL有多个schema，每个schema可包含一张或多张表，表名在每个schema里是唯一的，不是每个库，PostgreSQL默认把所有东西都放到一个叫public的schema里。

我们系统里每个逻辑分片就是一个schema，每个分片的表（如，照片的“喜欢”功能）存在于每个schema中。

我们在每个分片的每张表里用PL/PGSQL（PostgreSQL内部编程语言）和自增特性来创建ID。

每个ID包含有：

41位的毫秒时间（可以用41年的ID）；

15位表示逻辑ID；

10位自增序列，与1024取模，意味着每个分片每毫秒可以生成1024 个ID；

看个例子：

假设现在是2011年9月9号下午5：00，系统的纪元开始是2011年9月1日，从纪元开始到现在已经经过了1387263000毫秒，为生成ID，用左移方法填充最左边41位值是：

id = 1387263000 << (64-41)

下一步，如果生成这个要插入数据的分片的ID呢？假设我们用用户ID（user ID）来分片，同时已经有2000个逻辑分片，如果用户ID是31341，那么分片ID是 31341 % 2000 -> 1341，用这个值也填充接下来的13位：

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

最后，来生成最后自增的序列值（这个序列对每个schema每张表是唯一的）并填充完剩下的几位，假设这张表已经生成了5000个ID，下一个值即是5001，跟1024取模（刚好10位），加进来：

id |= (5001 % 1024)

ID生成了！用RETURNING返回给应用层用来作INSERT用。

下面是完整的PL/PGSQL代码（例子中的schema是 insta5）：

<code>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;
</code>

用下面的代码创建表:

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

就这些！主键在所有应用层都是唯一的（另外的好处是，包含了分片ID这样做映射就很容易），这个方法我们已经用到生产环境了，结果到目前为止令人满意，如果您对扩展问题能帮助我们，我们正在招人！

<译者：朱淦 350050183@qq.com 2015.7.29>