InstagramのIDシャーディングについて

Posted bysiguniangPosted inalgorithm, databaseTags:, , , ,

約1年前の Instagram Engineering Blog で ID のシャーディングについて解説されていたのでメモ。

Sharding & IDs at Instagram
http://instagram-engineering.tumblr.com/post/10853187575/sharding-ids-at-instagram

背景

毎秒大量に行われる写真投稿やユーザーの行動をデータベースに保存するために、Instagram ではシャーディングを行なっている。
データベースにデータ格納するにあたり、シャードが別であっても、写真といったコンテンツごとにユニークなIDを振らないといけない。

Before writing data into this set of servers, we had to solve the issue of how to assign unique identifiers to each piece of data in the database (for example, each photo posted in our system).

ID 採番するにあたり、以下の要件がある

  • 時系列順に並んでいる
  • 64ビットに収まる
  • 小数精鋭のエンジニアで運用しているので単純・明快なアプローチ

Instagram のアプローチ

Instagram は以下の3つのパートからなる 64 bit の ID をDBサーバで生成するようにした。

instagram-digit

  • [Timestamp]41 bit のカスタム epoch からのミリ秒のタイムスタンプ(2^41 ≒ 70年)
  • [Shard Id]13 bit のシャードID(2^13 = 8192)
  • [Increment]10 bit のシーケンス(2^10 = 1024)

理論上、各シャードはミリ秒あたり1024のIDが採番可能。

Timestamp 部分
タイムスタンプは Unix タイムの epoch ではなく、Instagram 独自の epoch(2011-Jan-01) からのミリ秒で表す。
2 ** 41 / 1000/60/60/24/365 = 69 なので約70年分に対応。
時系列順にソートしたいため、ID の先頭部分に持ってくる。

Shard Id 部分
ユーザID mod 2000 でシャードIDを決定。
Instagram はデータベースに PostgreSQL を利用している。DBサーバの各インスタンスはスキーマを細かく切って、インスタンス:シャード=1:多にしているもよう。

Increment 部分
シーケンス mod 1024(=2^10) で決定。
modulo なので、シーケンスの採番順とID順は必ずしも一致しない。Instagram の要件としては roughly sortable であれば良いらしいので、ミリ秒内の誤差は問題ではない。

実装
各部分を求めた上で、シフト演算すればよい。
DB(PostgreSQL) サーバで採番するアプローチのため、 Instagram は PL/PGSQL で実装している。
シャードIDが5のスキーマでの ID 採番関数は以下。

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;

テーブルの ID カラムに作成した関数でIDを取得するように定義する。

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

32 bit の場合

Instagram は 64 bit のIDにしたわけだけど、仮に 32 bit だとどうなるのか?
32 bit を目一杯使っても、epoch から約50日分しか表せない。ミリ秒は諦めて秒にし、25 bit 使うと約1年もつ。
余った7 bit を Shard Id と Increment に利用できる。
たとえば、Shard Id に 2 bit、Increment に 5 bit 使用すると、約1年に渡り4つある各シャードは毎秒32のIDを払い出せる。

なかなか厳しい。

他のアプローチ

ブログのなかでは、他のアプローチも紹介されている。

  • MongoDB の ObjectID(12 byte) や UUID のようにアプリケーション採番
  • twitter の snowflake のように採番サーバをたてる
  • 採番用の DB サーバをたてる(Flickr) 

採番用データベース

最後の Flickr のアプローチの概略は以下。

Ticket Servers: Distributed Unique Primary Keys on the Cheap
http://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/

Flickr では MySQL を利用しているため、Oracle/PostgreSQL などにある SEQUENCE がない。
そのため、テーブルの auto increment を利用して、ID を強引に increment させる。
欲しいのは increment する ID だけなため、生真面目に毎回新しいデータを突っ込んで ID 生成するようなことはせず、MySQL 拡張の REPLACE INTO を利用し、REPLACE INTO TABLE_NAME …;SELECT LAST_INSERT_ID(); のコンボで ID を取得する。
SEQUENCE のある DB(Oracle や PostgreSQL)なら、シーケンスに対して nextval するだけですむハズ。

また、single point of failure (SPOF) 対策として、奇数/偶数採番の2台のサーバを用意している。
複数のサーバで採番させると、DB サーバへの問い合わせに偏りが生じるにつれて、奇数/偶数サーバはなかよくIDが増えてくれないので、IDが時系列順に並ぶという Instagram の要件を満たせなくなる。

データベースのバックエンドに Redis を使うなら INCR key や INCRBY key N(mod N の場合) とすれば、お手軽に実装できる。

References

 

Leave a comment