原文：
 http://instagram-engineering.tumblr.com/post/10853187575/sharding-ids-at-instagram

以下是简单的翻译和我个人的理解。

Sharding & IDs at Instagram

在每秒大于25张照片+ 90个like的情况下，Instagram存储了大量的数据。为了确保所有的重要数据能够放到内存里以及便于用户的快速查询。我们开始着手数据分片，换句话说，就是将数据放在许多较小的buckets，每个buckets各自持有该数据的一部分。

我们应用的后端运行着Django和PostgreSQL，我们的首要问题就是决定是否使用PostgreSQL来分布式存储我们的数据，或者选用其他的方式。我们评估了几种不同的NoSQL解决方案，但最终决定最适合我们需求的解决办法是在一组的PostgreSQL服务器的分片我们的数据。

在写入数据到这些集群之前，我们必须解决如何在数据库中指定每一块数据唯一标识符的问题(例如：我们系统中发送的每张图片)。在单数据库中，典型的解决方案就是直接使用数据库原生的自增序列特性，当然，它不适用于当数据同时插入到多个数据库中的情况。本博客文章的其余部分讲解了我们如何解决这个问题。

在开始之前，首先列出哪些要求是我们的系统必须的：

  1. 生成的id必须是按照时间排序的。(比如照片列表的id，可以在没有获取照片详细信息的时候就进行照片排序)
  2. id必须尽可能的为64bit。(更小的索引，更方便的存储到系统中，比如Redis)
  3. 生成id的方式尽可能的轻量级，可替换-我们相信只用到了极少的工程师就做到了Instagram现在这个规模很大一部分原因是因为我们选择解决方案的时候尽量选择简单的，易于理解的。

现有的解决方案

许多现有的id生成解决方案都有一些问题存在，以下是我们考察过的：

在web应用中生成id

这种方式的id生成完全取决于你的应用，并没有上升到数据库层面，例如， MongoDB的ObjectId 中文版分析：MongoDB探究之ObjectId ObjectId占用了12字节的存储空间，时间戳进行编码作为第一部分。另外一种流行的方法是使用UUID。

优点：

  1. 每个应用程序线程生成独立的ID，最大限度地减少失败和资源竞争。
  2. 如果使用时间戳作为ID的第一部分，该ID可以按照时间排序。

缺点：

  1. 通常需要更多的存储空间（ 96位或更高）来保证合理的唯一性。
  2. 有些UUID类型是完全随机的，没有自然排序。

通过专门的服务生成ID

例如： Twitter开发的Snowflake，使用zookeeper协调多个节点的一个Thrift服务，生成64-bit的唯一id

优点：

  1. Snowflake生成的id占用64 bit，是UUID的一半大小。
  2. 可以使用时间作为第一部分，支持排序。
  3. 分布式服务，部分节点失效也可继续提供服务。

缺点：

  1. 将引入额外的复杂性和更多的不确定因素(ZooKeeper，Snowflake服务)到我们的架构。

数据库生成id

使用数据库自增的特性实现强一致性，Flickr使用这种方式，但是需要两个专用的id生成数据库(一个生成奇数id，一个生成偶数id)来避免单点故障。

优点：

  1. 数据库的方式我们比较容易理解，并且有很好的可控性。

缺点：

  1. 最终写入会成为一个瓶颈(虽然Flickr说即使在大规模也没有问题)。
  2. 需要额外管理两天服务器(或者EC2实例)。
  3. 如果只使用一台数据库服务器，会有单点问题，如果使用多台，随着时间的推移，不能保证他们的顺序(还是可排序性?)

上面列出的这些方法，Twitter的Snowflake可能是最合适的，但运行一个ID服务所引入的额外的复杂度对我们来说有点高(这句看不太明白..)。所以我们采取了一个思想上类似的方法，不过是基于PostgreSQL实现的。

我们的解决方案

我们的分片系统由上千个逻辑分片组成，这些逻辑分片在代码中被映射到了一些物理分片，使用这种方法，我们开始只需要启动一些少量的数据库服务器，然后可以逐渐扩容到多台.很简单的可以把一部分逻辑分片从一个数据库迁移到其他数据库，而不用重新整理我们的数据。我们使用Postgres的schemas特性来使整个过程脚本化(自动化?可编程?)，可管理。

Schemas(不要与单个表的SQL schema混淆)是Postgres的一个逻辑分组特性。每个Postgres数据库可以有多个schemas，每个schemas可以包含多个表，每个schema中的表名必须是唯一的，数据库级别可以重复。默认Postgres会把所有的东西放到一个叫"public"的schema 里面。

在我们的系统中，每个逻辑分片都是一个Postgres的schema，每张分片后的表(比如likes和photo表)都存放在一个schema里面。

我们依照每个分片中的每张表来生成ID，使用 PL/PGSQL，Postgres内建的编程语言以及Postgres已有的自增特性。

以下是我们每个id的组成： 

* 41 bits用作时间的存放，精确到毫秒(自定义一个时间周期,生成的id可以够我们使用41年)
* 13 bits用来标识逻辑分片id
* 10 bits用来标识自增序列，对1024取模，这意味着我们可以每毫秒，每个逻辑分区，生成1024个id

让我们通过一个例子来说明：首先设定当前时间为2011-09-09 下午5:00，我们的时间周期开始于2011-01-01。我们的周期开始的时候已经有1387263000毫秒，所以开始生成id，最左边的41bits设定为这个值的左移。


id = 1387263000 << (64-41)

下一步，获取尝试插入逻辑块的分片ID，比方说，我们现在使用用户id分片，共有2000个逻辑分片，如果用户ID是31341 ，那么分片ID是31341 % 2000 -> 1341 ，用这个值填充之后的13bits。


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

最后，从自增序列(这个序列是每个schema中的每个表都有一个)中获取生成的值来填充剩余的位，假设我们现在已经在一个表生成了5000个id，下一个值是5001，接着对1024取模(转换为10bits)，补全剩下的位。


id |= (5001 % 1024)

现在，我们已经生成了一个id，在我们的服务器应用中可以使用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可以更好的处理映射)。我们已经将这个方法应用到了产品中，目前看来效果不错。有兴趣帮助我们解决这些问题？我们的联系方式We’re hiring!

Comments
Write a Comment