Sharding & IDs at Instagram

andyyuduo

　　原文：http://instagram-engineering.tumblr.com/post/10853187575/sharding-ids-at-instagram
　　Instagram的存储量非常大，差不多每秒25-90张照片。为了保证我们的重要的数据能够合理的存储以便快速的提取应用，我们对数据进行了分片 -- 换句话说，将数据放到很多小的桶（buckets）中，每个桶存储一部分的数据。
　　我们的应用服务器跑的是Django ，后端数据库采用PostgreSQL 。我们决定采用分片后，第一个问题是我们是否还保留我们的主数据库，是否应该转换到其他的存储方案。我们评估了一些不同的NOSQL的解决方案，但是最后觉得最适合我们的需求的还是通过PostgreSQL server集群实现分片。
　　在将数据写入数据库集群前，我们必须解决如何分配数据唯一标识的问题（例如，上传上来的每一张照片）。在一个单数据的情况下，典型的解决方案是使用数据库原有的自增主键特性即可，但是这种方法在同时插入多个数据库的情况下不可行。这篇博客其他的部分将讲述我们如何解决这个问题的。
　　开始之前，我们列出了我们系统的基本特性：
　　生成的ID应该按时间排序（这样一个照片ID 的列表就足够了，并不需要照片的其他信息）
　　ID应该是64位的（为了更小的索引以及更好的存储在像Redis这样的系统中）
　　该系统应引入尽可能少的考虑新的“移动部件”（这里指额外的技术部件） --- 我们如何能够一直用很少的工程师扩展Instagram是因为选择简单、易于理解的解决方案。（The system should introduce as few new ‘moving parts’ as possible—a large part of how we’ve been able to scale Instagram with very few engineers is by choosing simple, easy-to-understand solutions that we trust. ）
　　现成的解决方案
　　关于ID生成有很多现成的解决方案，这些是我们曾经考虑过的：
　　在web程序中生成ID
　　这个方案是将整个ID生成逻辑放到应用程序层而非数据库层。例如：MongoDB的ObjectId，采用12个字节的长度，并且将时间戳进行编码。另外一种流行的方案是使用UUIDs。
　　赞成者:
　　每个应用程序线程独立生成ID，这样最大限度减小了生成ID冲突的概率
　　如果你采用时间戳编码，得到的ID将保持按时间排序、
　　
反对者:
　　通常需要更多的存储空间（96位或更高）以保证唯一性约束
　　一些UUID类型是完全随机的，没有自然顺序
　　通过专门的服务生成ID；
　　例如：Twitter的 Snowflake，一个Thrift 服务使用Apache ZooKeeper 去协调节点并生成64位的唯一标识ID
　　赞成者:
　　Snowflake ID是64位的，只有UUID的一般大小；   
可以使用时间编码，保持有序性
　　适用于分布式系统（Distributed system that can survive nodes dying ）   
   
反对者：
　　将引入额外的复杂性和更多的“移动部件”（ZooKeeper, Snowflake servers）
　　
DB Ticket Servers
　　使用数据库的自增长技术保证唯一性。Flickr 采用这种方案，但是使用了两个ticket DBs（一个生成奇数，一个生成偶数），用于避免单点的失败情况；
　　赞成者：
　　数据库比较好理解，也有很好的可扩展性   
反对者:
　　最后可能会变成写的瓶颈（虽然据Flickr，已经有很大的规模，也没有发现问题 ）   
需要管理一对额外的机器（或EC2实例）
　　如果使用单个数据库，将无法避免单点冲突。如果使用多个数据库，将不再能保证按时间排序。
　　
上面这些方法，Twitter的 Snowflake 是最接近的，但是额外的复杂性是需要跑一个ID服务。取而代之，我们采用了一种概念类似，但是内建于PostgreSQL中的方案。
　　我们的方案
　　我们的分片系统由数千个通过代码映射到少量物理分片的逻辑分片组成。使用这种方案，我们可以刚开始使用少量是的数据库服务器，最后逐渐增加，也很容易实现将一些逻辑分片从一个数据库转移到另一个数据库，而不需要re-bucket 数据。我们通过Postgres的schemas特性使脚本化和管理工作变得很简单。
　　Schemas（不要与单个表的SQL schema 概念混淆）在Postgres中是一个逻辑组。每个Postgres数据库可以有几个schemas，每个schema包含一个或多个表。表名在每个schema中必须唯一。而不是在每个数据库中。默认Postgres 会将创建的东西放到一个叫‘public’的schema 中。
　　在我们的系统中，每个“逻辑分片”就是一个Postgres 的schema ，每个分片的表（例如，像我们的照片表）存在于每个schema中；
　　我们通过PL/PGSQL（Postgres’ 的内部编程语言）和Postgres的自增长功能完成每个分片内每个表的ID创建工作。
　　我们每个ID有以下几部分组成：
　　1、41位时间的毫秒部分（gives us 41 years of IDs with a custom epoch / 使我们拥有41年的自定义纪元？）
　　2、13位表示逻辑分片的ID
　　3、10位表示自增长序列，最大1024.这意味着每个分片，每毫秒我们可以生成1024个ID。
　　让我们来看一个例子：假设现在是2011年9月9日，上午5：00，我们的纪元从2011年1月，那么从纪元开始到现在就有1387263000毫秒。所以我们生成ID 的时候，通过左移符号将这个值填入最左面的41位：

　　id = 1387263000 << (64-41)

　　接下来，我们将要为需要插入的数据进行ID 切片，我们使用user ID，假设有2000个逻辑分片，而我们的user ID是31341，这样分片ID是31341% 2000 -> 1341，将1341填入到接下来的13位中；

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

　　Finally, we take whatever the next value of our auto-increment sequence (this sequence is unique to each table in each schema) and fill out the remaining bits. Let’s say we’d generated 5,000 IDs for this table already; our next value is 5,001, which we take and mod by 1024 (so it fits in 10 bits) and include it too:
　　id |= (5001 % 1024)
　　最后，我们将通过自增长序列（这个序列的唯一性针对在每一个schema的每一个表，即每个schema的每个表有自己的序列）获取下一个值，并填入到余下的位中。假设我们已经为这个表生成了5000个序列ID，我们下一个序列ID应该是5001，我们用5001模1024，即为余下的ID值：

　　id |= (5001 % 1024)

　　我们现在已经有了我们的ID，我们可以通过INSERT语句的RETURNING 关键字，将ID返回给应用程序；
　　这里是the 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;      
And when creating the table, we do:
　　CREATE TABLE insta5.our_table (      
    "id" bigint NOT NULL DEFAULT insta5.next_id(),      
    ...rest of table schema...      
)

　　就这样!主键在我们的应用程序中是唯一的(额外的好处,包含在其中切分ID为更易于映射)。我们已经将这一方案应用到我们的产品中了，到目前为止效果良好。有兴趣帮助我们找出问题吗?我们正在招聘!   
Mike Krieger, co-founder