原文：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