分散環境でユニークなidを発番するGo製プロダクト「katsubushi」のご紹介

Lobiチームの長田です。 今回はkatsubushiというアプリケーションを紹介します。

https://github.com/kayac/go-katsubushi

katsubushiはid発番を行うアプリケーションです。 水平分割されたデータベースに対してユニークなidを発番するために作られました。

なお、本記事中の「データベース」はMySQLを指します。

katsubushiの特徴

Snowflakeと同様のアルゴリズムでid発番

SnowflakeはTwitter社がかつて公開していたid発番アプリケーションです。

https://github.com/twitter/snowflake/tree/master

既にメンテナンスされておらず、masterブランチにはその旨が書かれたREADMEしか残されていません。 タグが切られているので、ソースコード等はそちらで確認できます。

https://github.com/twitter/snowflake/tree/snowflake-2010

katsubushiはこのSnowflakeのアルゴリズム部分のみを取り出し、 Goに移植したアプリケーションです。

  • マシンid
  • タイムスタンプ
  • シーケンス番号

の3つの要素を使ってidを発番します。 マシンidに基づくためこれが重複しなければ複数のサーバーに分散させることができます。

アルゴリズムの詳細についてはSnowflakeのREADMEを参照して下さい。

https://github.com/twitter/snowflake/tree/snowflake-2010#solution

Goで書かれている

オリジナルのSnowflakeはScalaで書かれていましたが、katsubushiはGoで書かれています。 ビルドしてバイナリファイルを作成すればこれをサーバー上に配置するだけでデプロイすることができます。

軽量・高速

最低限の実装しか行なっていないため、軽量・高速に動作します。

以下はリポジトリに同梱のベンチマークを実行した結果です。


$ go test -bench App
BenchmarkApp-4            100000         19953 ns/op
BenchmarkAppSock-4        200000          7450 ns/op
PASS
ok      github.com/kayac/go-katsubushi  9.574s

手元のMacbook Pro (Retina, 13-inch、Early 2015)上での実行結果なので参考値ではありますが、 TCP接続の場合は秒間約50000回、unix domain socketで接続した場合は秒間約134000回のid発番が行えるという結果が得られました。 また、複数idをまとめて発番することもでき、同時に10のidをリクエストした場合は秒間200000回のid発番が行えることを確認しています。

Lobiの場合はアプリケーションサーバーごとにkatsubushiを起動し、 各アプリケーションはローカルホストのkatsubushiにid発番をリクエストしているため、 余裕で需要に耐えられる性能となっています。

通信にmemcachedのプロトコルを利用

idを必要とするアプリケーションとの通信にはmemcachedのプロトコルを利用します。

https://github.com/memcached/memcached/blob/master/doc/protocol.txt

GETコマンドを送信するとidが発番されます。 memcachedクライアントは大抵の言語で実装されているので、導入のハードルも低いと思われます。

以下はtelnetでコマンド発行してid発番を行う例です。


$ telnet localhost 11212
Trying ::1...
Connected to localhost.
Escape character is '^]'.
GET a
VALUE a 0 18
241137260152492032
END

先の項で触れたように複数のidをまとめて発番することもできます。


$ telnet localhost 11212
Trying ::1...
Connected to localhost.
Escape character is '^]'.
GET a b c
VALUE a 0 18
241137430416068608
VALUE b 0 18
241137430416068609
VALUE c 0 18
241137430416068610
END

katsubushi idの利用

水平分割されたデータベースのprimary keyとして

もともとkatsubushiはこの用途のために作られました。 サービス規模拡大に合わせてデータベースの水平分割を行う上で、 全てのデータベースについてユニークなidを発番する必要があったためです。

katsubushiはタイムスタンプとマシンidを元にidを発番するため、 連番を期待する場合は利用することができません。 Lobi内ではidの大小に一貫性があること(新しいものほどidが大きい)だけが必要とされていたため、 これを満たすid発番方法としてSnowflakeのアルゴリズムが採用されました。

タイムスタンプでパーティショニングする場合の対象カラムとして

データベースから特定期間に対応するレコードをまとめて削除する場合、 タイムスタンプを元にパーティショニングすると便利です。 パーティションごとDROPしてしまえば少ない負荷でレコードを削除することができます。

しかし、パーティショニングされたテーブルを操作する場合、 パーティションの特定ができなければ各パーティションごとにクエリ発番が行われてしまいます。 パーティションの条件になっているタイムスタンプで走査対象を特定すればこの問題は回避できますが、 タイムスタンプは複数レコード間で重複が発生する可能性があり、 たとえばページングしつつレコードを取得する場合に期待した動作をしないことが考えられます。

この問題はkatsubushiで発番したidでパーティションを区切ることで解決できます。

以下はSHOW CREATE TABLEでパーティション設定部分を抜き出したものです。


PARTITION BY RANGE COLUMNS(id)
(PARTITION p20160927 VALUES LESS THAN (229980399206400000) ENGINE = InnoDB,
 PARTITION p20160928 VALUES LESS THAN (230342787072000000) ENGINE = InnoDB,
 PARTITION p20160929 VALUES LESS THAN (230705174937600000) ENGINE = InnoDB,
 ...
 PARTITION pmax VALUES LESS THAN MAXVALUE ENGINE = InnoDB);

タイムスタンプを元に発番したidをパーティションの条件として使用しています。 以下のようなクエリを発行した場合、idによるパーティションが特定が可能なので必要最小限の処理でレコードを取得することができます。


SELECT * FROM some_table WHERE id > 240033399308288000 ORDER BY id DESC LIMITI 20;

また、idのみで日付を元にしたパーティショニングが行えるため、 idと日付を組み合わせた複合プライマリキーを設定する必要が無いというメリットもあります。

リクエストidとして

Lobiではデータベースに発番されたクエリやバックグラウンドで実行されているタスクにリクエストidを付与しています。 リクエストidはHTTPリクエストが発生した際に発番され、以降のすべての処理から参照されます。 これにより、例えばSlow logが記録された場合にそれが関連するすべての処理をリクエストidを元に辿ることができます。

nginx v1.11.0からは$request_idという同等の役割を持つidが格納された変数が利用できるようになりました。

http://nginx.org/en/docs/http/ngx_http_core_module.html#var_request_id

ただし、$request_idには複数ホスト上で動作しているnginx間でユニークであることを保証する仕組みはありません。

Tips

katsubushiのアップデート

katsubushi自体をアップデートする場合、残念ながら無停止で行うことはできません。 クライント側で別のkatsubushiをfallback先として指定し、順にアップデートする必要があります。

先に書いたようにLobiではアプリケーションサーバーごとにkatsubushiを起動しています。 アプリケーションサーバーはAWSのAuto Scalingで管理されているため、 katsubushiのアップデートが必要な場合は

  1. katsubushiをアップデートしたAMIを作成
  2. 新しいAMIからインスタンスを追加
  3. 古いインスタンスを削除

とすることで対応しています。

マシンidが重複しない限りはいくらでもkatsubushiを起動することができるので、 上記のように各サーバー上で起動するのが仕組みとしても単純で管理もしやすいと思われます。

タイムスタンプとの相互変換

katsubushiはタイムスタンプを元にidを発番しています。 また、発番されたidはそれを構成するタイムスタンプ・マシンid・シーケンス番号に分解し直すことができます。 つまり、idとタイムスタンプは相互に変換することができます。

idを期間で絞り込んだり、idがわかればそれが発番された日時を知ることができます。

Perlモジュールが用意されているので必要があればご利用下さい。

https://metacpan.org/pod/distribution/Katsubushi-Client/lib/Katsubushi/Converter.pm

※タイムスタンプとの相互変換はあくまでもid発番の特性を利用したものです。 純粋なタイムスタンプが必要な場合は別途専用のデータを用意することをおすすめします。

マシンidの決め方

Lobiではkatsubushiが動作しているマシンは同一サブネット内に存在しているため、 IPアドレスの第3・第4オクテットを元にマシンidを決定しています。


ip addr show eth0 | perl -nE '/inet (.+)?\// and do { @a=split("\\.", $1); say $a[2]*256+$a[3] }'

マシンidを管理するデータベース等を用意する方法も考えられますが、 そこに不調がある場合katsubushiが起動できなくなってしまいますし、 何より管理するものはできるだけ増やしたくないので、このようにIPアドレスを利用する方法を採用しています。

2016-10-28 15:50追記

マシンidの決定について不足があり、誤解が生じてしまったようなので補足します。 マシンidはkatsubushi起動時に -worker-id というオプションで指定します。 上記の方法はこの -worker-id オプションに渡す番号を決定するための一つの例として挙げたものです。

-worker-id には利用する環境に応じて自由な番号を設定することができますが、 重複しないidを設定する責任は起動する側にあります。

katsubushiのオプションについてはREADMEを御覧下さい。

追記ここまで

余談

名前の由来

「鰹節」です。 Lobiといえばぬこさん・・・

Snowflake・・・雪の結晶・・・細かい・・・

ぬこ・・・ねこ・・・かけら・・・細かい・・・鰹節だ!

おわり

次回はLobiチームで利用しているRe:dashとRundeckという2つのツールについて紹介します。

カヤックではGoでサービスを支えたいエンジニアも募集しています!