MySQL Cluster進化の歴史

MySQL Cluster開発者の一人であるFrazer Clement氏がその歴史についてとても興味深いエントリを自身のブログで綴っているのだが、いかんせん英語の長文で日本人には辛いかも知れないので今日はその日本語訳を皆さんにも紹介しようと思う。進化の歴史とその結果生じた構造を知ることにより、MySQL Clusterの仕組みに興味を持って頂けると幸いである。（わかり辛いところにはところどころ訳者による注釈を入れてある。ただし翻訳は結構大ざっぱなので、英語が達者であれば細かいニュアンスなどはオリジナルのエントリを参照して頂きたい。なお、日本語訳をすることに関してはFrazer氏の了解を得ているのであしからず。）

NDB（MySQL Clusterの略称。元々はNetwork DBという名称であった。）の開発の正確な歴史について、きっと他の誰かのほうが上手く解説できると思うのだが、限られて曖昧かも知れないが私の見解を以下に述べようと思う。

• NDBは元々、EricssonのPLEXというプログラム言語が使われている環境で（EricssonのAXE交換機用に）開発された。PLEXはマルチプルステートマシン（ブロックと呼ばれる）がメッセージ（シグナルと呼ばれる）を互いに交換し合うことによって、いくつかのシステムレベルの起動、再起動、およびメッセージクラスなどのタスクを実行する構造になっている。各ブロックは内部に状態を持っており、シグナルごとにそれを処理するルーチンが定義されているという具合である。ただしブロックがサブルーチンに対してサポートしている抽象化（訳者注：定義出来る機能の実装）はごく限られたものであった。（私＝FrazerはPLEXについて、それがどのように進化したかをもっと詳しく聞きたいと思っている。）このことは、AXEのプロセッサのデザインにそのまま反映されている。AXEは常識とは異なり、シグナルバッファがソフトウェアではなくハードウェアとしてシリコン上に実装されているのである。このような「ハードコーディング」がされているため、当初NDBは最長で25 x 32ビット長のシグナルしかサポート出来なかった。
• PLEXの仮想実行環境（VM）がUNIX上のプロセスとして実行された。ブロック上で実行されるPLEXのコードはVM用のコードに逐次解釈（interpret）され、シグナルはVMによってブロックへ転送された。これにより、PLEXベースのシステムのUNIX上での開発が始まったのである。その結果、PLEXベースのシステムが容易にUNIXソフトウェアと通信することが可能になった。それぞれのVMのインスタンスはシングルスレッドのプロセスで、送られて来たシグナルをブロック内に定義されている処理シグナル処理ルーチンへ振り分けるという仕組みになっていた。 
• PLEXからC++への変換システムが設計された。ブロックが巨大なC++のクラスに変換され、シグナル処理用のメンバ関数とブロックごとのグローバルな状態がメンバ変数が定義された。PLEX環境における限られた命名規則と抽象化された機能が、C++クラス内にC言語スタイルの機能として実装された。
• VM環境は元々のPLEX/AXE環境から分岐し、NDBのベースとして独自の進化路線をとった。その結果、NDBはOSの各種サービス（通信、ディスクI/Oなど）へアクセスすることが可能となった。PLEXコードの逐次解釈（インタプリタ）機能は取り除かれ、PLEXのコードはすべてC++のコードに書き直された。VMインスタンスは各種通信経路を用いて相互に通信出来るようになり、分散システムを形成するようになった。
• このぐらいの時期にNDBとその開発チームがEricssonを去ることになった。（訳者注：Ericossonはベンチャー企業であるAlzato社を作ってNDBを独立した製品にし、さらにその後Alzato社がMySQL ABに買収されることになる。）
• ブロックの共通した機能がベースまたはユーティリティクラスへと抽象化された。これにより、ハードウェアやシステムに起因した制限が緩和され、抽象化の度合いが上昇することになる。現在では、ブロックはPLEXの（負の）遺産に悩まされることなく、C++の抽象化機能を活用して実装されている。元々存在していたブロックは全て作り直された。
• マルチスレッドのNDBデーモン（ndbmtd）が開発された。ブロックの各インスタンスが異なるスレッドで実行されるようになった。といってもこれは急激な変更ではなく、PLEX実行環境で元々採用されていた「1つのブロックを1つのプロセッサとして実装する」という設計への回帰である。（訳者注：ndbmtd内にはおよそ20種のブロックが存在し、それらが予め定められた数のスレッドで実行されている。）

というわけで、現在NDBはシグナルモデルを利用してブロックがお互いに通信するような仕組みになっているのである。シグナルはもはや25ワード長に制限されていない。シングルスレッド版のNDBデーモン（ndbd）もあり、それは全てのブロックが一つのスレッドを共有しているが、VM同士の通信やディスクI/Oなどのための専用のスレッドが実装されている。（訳者注：I/Oなどのスレッドが別途あるという意味では厳密にシングルスレッドプロセスであるわけではない。）いずれの場合にしても、ひとつひとつのブロックはシングルスレッドのままであり、スレッドは複数のブロックによって共有されている。（訳者注：スレッド対ブロックは1対Nの関係である。）

このようなブロック-シグナルモデルは、ErlangやHoareのCSPを思い起こさせる。つまり、同時実行性がシーケンシャルなプロセスがお互いに明示的なメッセージを交換し合うことによってモデル化されているようなシステムである。これは共有メモリモデル、つまりメモリへのアクセス整合性をロックやメモリ保護機能、アトミック命令などで保証するというモデルとは対照的である。もしくは、ブロック-シグナルモデルはMPIやActiveオブジェクト/Actorモデルに似ているとも言える。

明確なメッセージ交換によって同期または通信を行うのはコストが掛かる。つまり、実行時により多くのメモリコピーが発生するということである。プログラム設計時には、潜在的な同時実行制御はメッセージ交換および状態遷移というモデルで明示的に表現されていなければならず、マルチスレッドセーフな共有メモリとロックを用いたモデルよりも多くのソースコードを改変または記述する必要が生じてしまう。

しかしながら、これらのデメリットはコードの見通しがよくなるという利点によって十分に報われると思う。ステートマシン間の同期はとても見通しが良く、同期のためのコストを容易に理解することができる。明確なメッセージ交換をスレッドまたはプロセスの通信手段として利用すれば、ごく僅かな部分だけをマルチスレッドの（スレッドセーフな）カーネルとして実装するだけで済み、そのカーネルは正しく最適化されているということが保証されるであろう。そして多くのコードがシングルスレッドのスタイルで（マルチスレッドを意識する必要なく）記述することが出来る。マルチスレッドのためにライブラリを作り直す必要もない。（訳者注：ブロックがシグナルに応答する各種ロジックは全てシングルスレッドで実行されるからである。）その結果、プロセッサとシステムアーキテクチャに依存したコードおよびトレードオフが最小化されるのである。

内部的には、NDBのVMはブロック同士の通信は非同期のものだけをサポートしているが、そのような非同期のメッセージ交換を用いることは多くのメリットがある。第一に、メッセージを送信したスレッドは、そのメッセージの処理が送信先のブロックにおいて完了するのを待たなくても良いので、他に多くの作業ができる。同じスレッドを共有している他のブロックにメッセージを送った場合は自らが送信したメッセージを即座に処理するということもあるだろう。これにより、CPU内のデータおよび命令キャッシュが最大限に活用され、コンテキストスイッチが減少し、デッドロックの可能性が低減することになる。ブロッキングI/O（ネットワークおよびディスク）は専用のスレッドプールへ処理が割り振られるため、シグナルを処理するスレッドがブロックすることは絶対にない。（ただし保留中のシグナルがなくなった場合にはスレッドが停止する）システムの応答性は、優先付けされたジョブキューを使い、どのジョブを先に処理するべきかということを決定して各種ジョブに掛かる時間を最小化することによって実現している。形式的な見方をすれば、スレッド同士が相互作用する必要のある状況は、スレッドが同時に実行されている状態とほぼ同等まで減少することが可能となる。つまり、スレッド同士の同期はシグナル処理の境界だけで必要なのである。このように、前述のような制限は、（シングルスレッド処理に起因する）システムの正しさやタイミング特性（応答性の向上）を容易にするのである。

しかしながら、このような非同期で、イベントドリブンなスタイルの開発はとても難しいというのもまた事実である。全てのブロッキング操作（ディスクアクセス、ブロックされる通信、他のスレッドやプロセスへの要求など）をリクエストとレスポンスのペアとして実装しなければならないからである。また、広く一般的に使われる数多くのデータ構造やアルゴリズムは単一の（その処理を開始したスレッドの）スタックを（データを格納したり関数の引数を渡したりするために）利用するという前提に立っているが、このようなメッセージ交換によりシステムを実装するとそれらのデータ構造やアルゴリズムを活用することが出来ない。また、非同期のスタイルで開発されたソフトウェアはこまごまとした詳細が分からず、つかみ所がないため新しい機能を設計するのは時として難しい場合がある。その上、抽象化の深いレイヤーでのコードであっても、並列化が可能なものであれば常に最もレベルの浅い呼び出し元（コールポイント）までリターンしなければならないため、非同期のシステムは構造が平坦になってしまいがちである。（訳者注：つまりスタックが深くなることはない。）このような構造をとることによる副作用は、エラー処理のコードがエラーの発生源になっているブロックに固有のものではないという点である。しかし、まあそれもこのような非同期（の並列）システムをいじる楽しみの一つだと言える。C++環境はそのような抽象化された要素を設計するために、非常に幅広いツールを提供してくれる。そして、個々の改善が将来の作業を易しくしてくれるのである。

以上が翻訳である。このように、MySQL Clusterはシグナル（メッセージ）交換を基礎として実装されており、通常の共有メモリ方式の並列ソフトウェアとは大きく構造が異なっている。その結果として、MySQL Clusterは高い同時実行性と素早い応答性を実現しているのである。排他ロックを使わずに同時実行制御をする構造はロックがボトルネックにならないためCPU数に応じてスケールし易く、CPUコア数が増加すると予想されるこれからの時代にはとても有利に働く可能性があり、これからMySQL Clusterがどこまで性能を向上させられるかとても楽しみである。

しかし、はっきり言ってMySQL Clusterの構造を理解するのは少し敷居が高い。動作不良を起こした場合に原因を特定するためには、各ブロックのソースコードを行ったり来たりしなければならないので必然的に解析には時間が掛かってしまうし、各ブロックの状態は刻々と変化するので問題の発生条件の特定も難しい。なので慣れるまでは結構大変かも知れない。その内部構造を詳しく知るようになればFrazer氏が言うようにそれもまた魅力になるかも知れないが、構造が分からないうちは単なる苦痛である可能性が高い。というわけで、次回はNDBデーモンの各カーネルブロックについて紹介しようと思う。