LMAX Disruptorを調べたり触ったり
これはCyberAgent Advent Calender 16日目の記事です
CyberAgent エンジニア Advent Calendar 2015 - Adventar
昨日は@choheyさんの「ボードゲーム部（仮）の紹介をするよ。」でした。
ボードゲーム部（仮）の紹介をするよ。 | 今日も元気にがんばるぞぞい
さてみなさん、
どすこい！
もう説明不要ですね！どすこいエンジニアの@sitotkfmです
何度も会社のブログで書くのもなんなので今回はブログを作ってみました。
おそらく今日が最初で最後の更新です。
この会は輪読会メンバーの多数決で票が集まった論文を担当の人が資料を作って発表するという極めて一般的な輪読会です。
例えば僕が担当の時にはFaceBookのGorillaという時系列データベース(と書いているけど読んだ感じはキャッシュのようなデータストア)について発表しました。
そして今週の月曜日にこの輪読会が行われたのですが、今回の発表はMicrosoftのFaRMというRDMAを使って論文の発表でした。
内容としてはデータストアと行ってもかなり低レイヤな話だったのでWeb企業ではあまり意識しないような領域の話で大変興味深かったのですが、その中でも私の興味を特に引いたのがCircular bufferというデータ構造でした。日本語のwikipediaだとリングバッファという記事になってます。
リングバッファ - Wikipedia
さてCircular buffer、このデータ構造の話題になると必ず出てくるのが「LMAX Disruptor」というLibraryがあるそうです。
あるそうですと結んでいますが、恥ずかしながら私このLibraryについてその時まで全く知りませんでした。
なので今回は勉強がてらこのLMAX Distruptorでちょっと遊んでみたいと思います。
LMAX Disruptorとはなんぞや
複数のスレッド間でのデータのやり取りを行うためのです。データを渡す方(Producer, Publisher)からデータを使う方(Comsumer, EventProcessor)に渡す橋渡し的な存在です。
機能はキューなんですが、単純なスレッドセーフなキューではなくComsumerに依存関係をもたせたりすることもできるそうです。
Log4j 2にも採用されたLMAX Disruptorはなぜ狂ったように速いのか？ | JUMPERZ.NET Blogという上の記事の通りlog4j2にも使われているそうですが、かの有名な活火山NoSQLであるHBaseでもWALに書き込むときに使用しています。
// At the core is a ring buffer. Our ring buffer is the LMAX Disruptor. It tries to // minimize synchronizations and volatile writes when multiple contending threads as is the case
// here appending and syncing on a single WAL.
ちょっとした内部構造の解説
全体を説明すると長くなりそうなのでここでは速さを実現するための工夫を少しだけ紹介します。
Memory Allocation
DisruptorはCircular Buffer(Disruptorの流儀ではRing bufferですが)にエントリを保持します。このデータ構造はサイズがあらかじめ決まっいるので先にメモリを確保してしまいます。
エントリを使い回すことでGCによる性能への影響を回避しています。
False sharing
コンピュータのストレージ構造というのはCPUを頂点として考えた時にCPUに近いほどアクセス速度が高くてサイズが小さく、CPUから離れていくに連れ速度は遅くなりますがその分サイズが大きくなります。
ですので一般的にデータアクセス速度を向上させるためにはいかに頻繁に使われるデータをCPUの近くに配置するかが鍵になるわけです。
まあCSの基本中の基本なんで今更という話なんですが、これが並列処理だと問題になる場合があります。
メモリ上のキャッシュというのはCache lineという単位でデータを保存しています。このCache lineは一般的に64byteです。例えば変数がlongの場合longは8byteなので一つのCache lineに8つのlongの変数が同居する可能性があります。
複数のスレッドでCache line上の異なる変数の更新した場合、競合してキャッシュが全く乗らなくなることが起こりえます。これがFalse Sharingという状態です。
LMAX DisruptorではFlase sharingを防ぐためにlong値のCache lineにpaddingとしてlongを呼ぶことで回避しています。
使ってみよう
じゃあ早速使ってみましょう。
versionは最新の3.3.0を使っています。
gistb5bd4e02e2f85d6eb2d5 gist34ce826c0b0ecaa3ff60 へーって感じですね。
そりゃほぼGetting Started · LMAX-Exchange/disruptor Wiki · GitHubのコピペなのでそうですよね。
ではここでhandleEventsWithの部分をちょっと変更してみましょう。
Publish ---------> Handler1-1 ----- 1s -----> Handler1-2 このときdisruptor.handleEventsWithを二回呼び出すことでEventを二股に流しています。
\ ---> Handler2-2 - 0.5s -> Handler2-2
その結果がこちらになります。
この様にHandlerに依存関係をもたせたりHandlerのチェインを作ることができます。
(といってもEventを変更して次のHandlerに渡せるわけではないです。)
これ以外にもhandleEventsWithに複数のEventHandlerを登録することで並列に実行することも可能です。
あとConsumerのWait Strategyを変えることで高速化を試みることもできます。
- BlockingWaitStrategy : デフォルト。LockとConditionを使って同期をとる
- SleepingWaitStrategy : いわゆるビジーウェイト
- YieldingWaitStrategy : Thread.yieldを呼び出しまくる
- BusySpinWaitStrategy : ほとんど何もしない
基本的に下に行くほど早くなるそうですが楽しそう
まとめ
あんまり掘り下げられなかったですが、スレッド間の通信は解析系のアプリを作るときには必要になることも少なくないと思うので色々検討しようと思います。枯れてそうな雰囲気なのも好印象です。
本当は速度検証をした方がよかったかもしれませんがそれは本家でやっているのを参考にしてください。
Performance Results · LMAX-Exchange/disruptor Wiki · GitHub
おまけ
ちなみになんでdisruptorという名前にしたかというと
Why is it called the Disruptor?
Well there are two reasons. Primarily we wanted to disrupt the common assumptions in this space because we think that they are wrong. But, to be honest, we also couldn’t resist the temptation; There was some talk about Phasers in Java at the time when we named it and, for those of you too young to care, Phasers were the Federation weapon and Disruptors the Klingon equivalent in Star Trek.
へーって感じですね。
参考ブログ
golang - 750,000MPSを達成したsurgemqの秘密に迫る - Qiita
Log4j 2にも採用されたLMAX Disruptorはなぜ狂ったように速いのか？ | JUMPERZ.NET Blog
記事中で取り上げた記事
明日は@principia_caなんで社内でもすごい人が記事を書いてくれるはずです。
ではごっつあんでした！
