Instagram 的ID生成策略[翻译]

k668

　　项目中遇到一个ID生成策略的需求：需要在系统中为每个用户分配一个ID用作以后的用户标示。这个需求应该是非常普遍的，对于使用人数较少的系统而言不会是一个问题，不过对于向用户众多的互联网系统来讲这不是一个简单的问题。下面是翻译的最近最火爆的Instagram应用开发者的一篇文章，看看他们一个十几个人的公司是怎么解决这个问题的：

先给出原文链接：http://instagram-engineering.tumblr.com/post/10853187575/sharding-ids-at-instagram　　以下为简单翻译（不清楚的地方请参照原文）：
　　Instagram 的分片和IDs

　　每秒接收25副图片、90次"like"分享，Instagram存储了大量的数据。为了确保所有重要的数据都存入到了内存并且尽快地对于用户可用，我们将数据进行了分片---换句话说就是将数据存到很多小分片上，每个分片都持有数据的一部分。
　　我们使用Django 和PostgreSQL 作为后台的数据库系统。在决定对数据进行分片后我们遇到的第一个问题就是是否仍旧将PostgreSQL作为我们主要的数据存储系统，还是换个其他的。我们评估了一些不同的NoSQL解决方案，但最终决定：最符合我们需求的是将数据分片到由多个PostgreSQL组成的服务器组上。

　　在将数据写入到PostgreSQL服务器组之前，我们必须先解决如何为数据库中每一份数据指定相应的唯一标示（例如每一副发布在我们系统上的图片）。典型的解决方案在单个数据库中还行得通---直接使用数据库的自增来分配唯一标示；但要将数据同时插入到多个数据库时这种方案就不行了。这篇文章接下来的内容就指明了我们是如何对付这个问题的。

　　在开始之前我们列出了几个系统中必须的几个功能：

　　1.生成的ID必须可以按时间排序（这样一来，一组图片可以不用再查找其他相关信息就能排序）
　　2.ID最好是64bit的（为了索引更小且方便存储在像Redis这样的系统中）
　　3.新系统造成的不确定性(or改动)越小越好---我们之所以能用这么少的工程师搞定Instagram，很大的原因就在于选择简单、易懂、可靠的解决方案。
　　现存的解决方案：
　　对于ID生成问题现在已经有很多现存的方案，以下为几个我们可以考虑的：

　　在web应用(web application)中生成ID

　　这种方式将ID生成的问题全部交给你的应用程序，而不是数据库来解决。
　　例如：MongoDB 的ObjectID 一共有12bytes长，并且将编码后的时间戳作为首要的组件。另一个常用的就是UUID。
　　优点：
　　1.每个应用程序线程都独立地生成ID，减少了故障和不一致。
　　2.如果你使用时间戳作为ID的首要组件，ID就是可以按时间排序的。
　　缺点：
　　1.为了保证唯一性的可靠，一般需要更多的存储空间(96bit或更多)。

　　2.有些UUID完全是随机的，不能自然排序。
　　

　　使用专门的服务生成ID

　　例如：Twitter的 Snowflake---一个使用Apache ZooKeeper来整合所有节点然后生成64bit唯一ID的简洁的服务。

　　优点：

　　1.Snowflake生成的ID只有64位，只有UUID的一半大小。

　　2.可以使用时间戳作为首要组件，可排序。

　　3.分布式的系统，某个节点down掉也没事。

　　缺点：

　　1.会给整体架构引入额外的复杂性，和一些不确定内容(ZooKeeper, Snowflake servers)

　　

　　数据库"票务"服务器

　　使用数据库的自增功能来保证唯一性。Flickr 使用了这种方法---但使用了两台数据库服务器(一台生成奇数，一台生成偶数)来防止单点当机。

　　优点：
　　1.数据库非常熟悉，有很多可预见的因素。

　　缺点：

　　1.会最终成为一个写瓶颈（根据Flickr的报告，即使在大规模并发的情况下这也不会成为一个问题）

　　2.对于管理员而言额外多了一对机器。

　　3.如果使用单个数据库则容易出现单点故障，使用多个则无法保证可以按时间排序。

　　以上几种方法中Twitter的离我们想要的最为接近，但是运行一个专门的ID服务所造成的额外复杂性却是一个负面因素。
　　替代地，我们选择了一个概念上与之相似的方法，并将它整合到了PostgreSQL中。

　　我们的解决方案

　　我们的分片系统由上千个逻辑分片组成，而这些逻辑分片在代码中与非常少的物理分片进行了映射。使用这种方法我们可以从很少的数据库服务器开始，最终转到更多的服务器：只需要将一些逻辑片从一台服务器移到另一台，中间不需要重新打包任何数据。为了易于编码和管理我们使用Postgres的schema功能来实现。


Schemas(不是SQL 中的表的schema) 是逻辑上的一组功能。每个Postgres 数据库可以拥有多个schema,每个schema中可以有一到多个表；表名在schema内是唯一的，在DB中可以不唯一；默认的，数据库将所有的信息都放在一个叫"public"的schema中。　　在我们的系统中每个逻辑分片都是一个schema，每个被分片的表都存在于每个schema中。我们使用PL/PGSQL(Postgres内置的编程语言)和Postgers自身的自增函数，为每个分片中的每张表都赋予了生成ID功能。

　　每个ID由以下部分组成：
　　1.41bits 存储毫秒格式的时间。
　　2.13bits 表示逻辑分片ID。
　　3.10bits 存储自增序列值对1024取模后的结果，这意味着每个分片每秒可以产生1024个ID。

　　下面进行一个测试：假设现在是2011-09-09 下午05:00，我们的业务从2011-01-01开始运行。从开始到现在已经运行了1387263000毫秒，开始构造我们的ID，我们使用左移位的方式填充左面的41位：
　　id = 1387263000 << (64-41)

　　接着，我们获取即将插入的这份数据所在的分片ID，假设我们按用户ID来进行分片，系统中一共有2000个逻辑分片；如果我们的用户ID是31341，那么我们的分片ID就是31341 % 2000 -> 1341。我们使用这个值来填充接下来的13位：


    id |= 1341 << (64-41-13)　　最后我们使用任意生成的自增序列值(单个schema单张表内唯一)来填充其余的位数。假设我们要插入的那张表已经生成了5000个ID了，下一个值就是5001，我们对其使用1024取模（这样生成的数据就是10bits了），然后加上去：

　　id |= (5001 % 1024)

　　现在我们已经获取到了想要的ID，接下来可以使用return关键字作为insert过程的一部分返回给应用程序了。
　　下面是以上整个过程的PL/PGSQL代码实现（例如：在schema实例5中）：


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）。我们已经将这个方法应用到了产品中，目前看来效果挺令人满意。有兴趣帮助我们解决这些问题？我们的联系方式

　　Mike Krieger, co-founder