Catapult's Disruptor

はじめに

NIS2,mijin共通のコアプログラムとなるCatapult、使いようによっては高スループットが出せるという前評判も有り、NEMが高スループットになるのではないかなどという 誤解 が生まれてしまいました。

実際には リッチで最低要求スペックの高いノード -> ノードを立てられる人が減る -> 分散から遠ざかる になるので、高スループットが性能として出せるからと言って、すぐにパブリックチェーンに採用できるものでもありません。慎重になるべき理由があるのです。

それはさておき、Catapultのソースコードを眺めていると、Disruptorというものを発見しました（発見と言っても普通にある）。どうやらこれが高スループットの秘訣の一つであるようだぞと思ったのと（実際にはわからない）、仕組みが面白かったので、ここで共有したいと思います。

Disruptor概要

ディスラプタは、マルチスレッドプログラムのデザインパターンの中の一つ、プロデューサ・コンシューマパターンにおいて、コンシューマにメッセージを渡すための仕組みの一つ。特徴は 高速である ということ。

元々は LMAX という英国に本部を持つFXプラットホームを運営するチームが開発したjavaライブラリが発端で、高スループットを目標に開発された。そのコンセプトは プロデューサ及びコンシューマがデータの書き込み、読み込み時を行う時にオブジェクトの状態を確保するためのロックを極力減らすこと です。

では実際にそれをどうやって実現しているのかと言うと、英語だが分かりやすいブログの記事があるのでそちらを見てください。

[参考URL]

http://mechanitis.blogspot.com/2011/07/dissecting-disruptor-writing-to-ring.html

http://mechanitis.blogspot.com/2011/06/dissecting-disruptor-how-do-i-read-from.html

ただ、LMXAの実装は見てないが、カタパルトのディスラプタとLMXAの実装は違う部分がある可能性があるので、あくまで参考URLのプログはコンセプトの理解のために紹介する。ここではカタパルトのディスラプタについて書きます。（そのため、登場するディスラプタを構成する部品が、上記ブログの記事と違ったりする）

結局何なのか

上記概要をみてもいまいちピンと来ないと思います。

ディスラプタを調べると、「ディスラプタとは循環バッファである」「ディスラプタとはロックフリーでプロデューサ・コンシューマパターンを回す仕組みである」など、いろんな言い方がされているのが分かる。こういう一つの言葉に抽象・具体、広義・狭義それぞれの捉え方があるような言葉は理解するのがとても大変。

私は

• プロデューサからの要求を複数のコンシューマが競合することなく処理するための仕組み
• ディスラプタという仕組みの中心にディスラプタと名付けられた循環バッファがある

と理解している。

駄目押しのために図でも説明をしておきます。

そのための仕組み。

リソースの奪い合いが全体の足を引っ張るって人間みたいですね

で、図ではリソースと書きましたが、Catapultでは トランザクション と ブロック をバリデータ等がロックを取り合わないように処理していくための仕組みになります。

Parts

ディスラプタの仕組みの理解は、いかにしてプロデューサが渡してくるエレメントを複数の並行したコンシューマが競合せずに処理するか という仕組みを理解することであり、つまりは エレメントの渡し方 と エレメントの読み込み方 を理解することになるので、最初に各部品を紹介しても仕方ないのですが、流れ上登場人物を紹介しておく必要があるので紹介します。

Disruptorを構成する部品は以下の通り。

1. Disruptor (CircularBuffer)
2. DisruptorElement
3. Consumer
4. Barrier
5. Dispatcher

1のDisruptorは仕組みとしてのDisruptorの中心に置かれる部品だと思ってください。

1.Disruptor (CircularBuffer)

ディスラプタオブジェクトはいわばただの「倉庫」であり、この中にプロデューサはコンシューマに与えたい命令を入れていきます。

で、上でエレメントと書きましたが、その前にも書いたとおり、ディスラプタには

• トランザクションディスラプタにはトランザクションの連なり
• ブロックディスラプタにはブロックの連なり

が入れられていきます。

なぜディスラプタが循環バッファを採用したのかと言うと、エレメントIDを無限に利用できるというのと、 最初に必要な容量を確保してそこを使い回せば、コンシューマに消費され終わったエレメントを破棄したり、新しいエレメントの為にメモリを確保する作業を省略できる からです。

2.DisruptorElement

ディスラプタに入れられる要素。実際には トランザクションの連なり か、ブロックの連なり がこれになります。

3.Consumer

コンシューマ（厳密にはDisruptorConsumer）はディスラプタにあるエレメントを消費します。

実際のところこれが何になるのかというと、新しく取得したトランザクションを検証するバリデータなどがコンシューマになります。

図を見ると分かるとおり、各コンシューマはそれぞれの階層を持ち、階層はディスラプタのエレメントを消費する順番になります。コンシューマはlevel-0から順番に、ディスラプタからエレメントを取得して消費していきます。このとき、必要であればコンシューマはエレメントの内容を書き換えます。

4.Barrier

バリア（厳密にはDisruptorBarrier）は、ディスラプタとコンシューマの間に立ち、コンシューマが取得できるエレメントの(ディスラプタ上の)ポジション(position)を保持します。各コンシューマはバリアのポジションと自身のポジションを比較して、次のエレメントが取得可能かどうかを判断します。

例えば、コンシューマのポジションが8で、バリアのポジションが12の場合、コンシューマは9,10,11,12の4つのエレメントを取得可能であるということになります。

また、各バリアはコンシューマ同様に階層(level)をもち、 コンシューマの数＋１個 のバリアが生成され、各コンシューマに一対一で対応するように階層が割り当てられる。（ただし、最後の一つは対応するコンシューマが無いが、これは後々分かる）

5.Dispatcher

全てのディスラプタ、コンシューマ、バリアは、このディスパッチャ(厳密にはConsumerDispatcher)によって生成されます。実装の上で、ディスラプタを中心となって動かしているのはディスパッチャです。このディスパッチャには BlockDispatcher と TransactionDispatcher　の2種類があります。

また、ディスラプタにエレメントを登録するのもディスパッチャの役割で、各ディスパッチャはエレメント登録用の関数をサーバにフックし、操作はサーバフック経由で行われます。

これで登場人物の紹介はおわり。

Consumerのエレメント読み取り

ディスラプタの挙動を把握するには、コンシューマがディスラプタからエレメントを読み取る仕組みと、ディスパッチャがディスラプタにエレメントを登録する仕組みを把握すれば良い。ここではコンシューマの読み取りを説明します。

全てのエレメントは、全てのコンシューマに階層順に渡され、最後の(一番階層番号の高い)コンシューマがエレメントを受け取って処理が終わると、そのエレメントは全てのコンシューマに渡されたということになり、そのエレメントが占領しているバッファが開放されます。

開放されると言っても、メモリは確保したままにするので、「ここに上書きしても良いですよ」と判断されることを意味します。

ではどのようにして階層順にエレメントが渡っていくのか。

コンシューマのエレメントの読み取りはディスパッチャにあるtryNext関数から始まる。tryNext関数が呼ばれると、まず最初にコンシューマとバリアのポジションの比較が行われる。もし、コンシューマとバリアが同じポジションを示しているとき、そのコンシューマが取得できる最新のエレメントが存在しないことを意味するので、エレメントの読み込みは行われず、コンシューマは最新のエレメントが取得するまでスピンして待機・監視を行う。

コンシューマがエレメントを処理し終わると、ディスパッチャのadvance関数を呼び出して 自身のポジションと、自身の階層の一つ上の階層のバリアのポジションを 一つ進める。なぜこのようなことをするのかと言うと、割り当てられた階層順にエレメントを消費させるためである。これにより、 最後の階層のコンシューマがエレメントを消費したとき、そのエレメントは全てのコンシューマに渡ったことを確信できる のと、 全てのエレメントは各コンシューマに順に処理されることになるので、コンシューマがエレメントの内容を書き換える時にロックを取得する必要がなくなる。

ここで、コンシューマの階層に対して一つバリアが多い理由が分かる。一番最後のコンシューマが処理を終えた後に呼び出すadvance関数も、他と同様に、一番最後のコンシューマとその一つ上の階層のバリアのポジションを一つ進める処理を行おうとする。そのため、一つ増やしている。

一番最初(level 0)のバリアのポジションは、ディスラプタにエレメントが追加されることで進む。

これがコンシューマの読み取りです。前にも言いましたが、この中でディスラプタの内容の読み書き中に状態が変化しないようにロックをかけるような仕組みは登場しません。なぜなら各エレメントは順番にコンシューマに消費されることが決まっているので、複数スレッドが一つのリソースを取り合う時に行うようなロックが必要がないのです。

Disruptorへのエレメントの登録

ディスラプタへのエレメントの登録は、ディスパッチャのprocessElement関数が操作されることによっておこわなれる。

processElement関数が実行されると引数を検査した後、最初に行われるのがロックの取得である。ディスラプタ上の同じポジションに同時に書き込まないようにするためには必要になる。

ロックを獲得すると、まず最初にディスラプタに新たにエレメントを挿入可能かどうかを検査する。

新たなエレメントが挿入できない場合、processElement関数は例外を投げるか戻り値として0を返して終了する。

新たなエレメントが挿入できる場合、ディスラプタ内の最後尾未処理エレメントのすぐ後ろにエレメントを挿し込み、一番下の階層のバリアのポジションを一つ進める。

ディスラプタが満杯のとき

ディスラプタが満杯の時にprocessElementで新たにエレメントを登録しようとした時に、processElementの結果は下記の２つ
- ランタイムエラーを投げる
- 戻り値として0を返す

これらを決めるのはconfig-node.properties内のshouldAbortWhenDispatcherIsFullフィールドであり、trueなら例外を投げ、falseなら0を返す。それに対してノードがどういう挙動をするかは実際には関数の呼び出し元に依存する。キャッチしなければ実行時エラーになる。デフォルトはtrue

これがディスラプタへのエレメント登録の流れになります。

さいごに

読み書きを理解できればディスラプタってどんなものか何となく分かると思います。また、ノードの設定にあるdisruptorという文字がどんなものを指しているのかも分かると思います。

私はどうやらこれが高スループットの秘訣の一つのようだぞ、と思いましたが、実際には色々なノウハウが詰まっているのだろうなと思います。

こういう仕組みを学んでみるのも面白いですね。