More info...

2009-11-04

MySQL Clusterが苦手とするJOINを如何にして克服するべきか。

シェアードナッシング型の負荷分散機能を持ち、なおかつ同期レプリケーションによるHA機能まで備えたMySQL Cluster最大の弱点といえば、JOINの遅さであろう。MySQL ClusterのJOINは偽りなく遅い。JOINを多用するアプリケーションでMySQL Clusterを利用するのはある意味マゾヒスティックな行為であると言えよう。何故MySQL ClusterはJOINが遅いのか?それはMySQL Clusterが分散データベースだからである。

ご存じの通り、MySQLにおけるJOINのアルゴリズムにはNested Loopしかない。他のストレージエンジンを利用していればそれでも十分実用に耐えうるぐらい高速なのだが、MySQL Clusterの場合はそうはいかない。JOINでは自ずとストレージエンジンからデータをフェッチする回数が増えるが、MySQL Clusterの場合レコードのフェッチはネットワークを経由しなければいけないのでここがボトルネックになってしまう。

例えば、2つのNDBストレージエンジン(MySQL Cluster)のテーブルをJOINする場合を考えよう。外部表からM行フェッチし、外部表の一行につき内部表から平均でN行フェッチする必要があるとする。その場合、外部表から1回(1回のスキャンオペレーションでデータをフェッチできる)、内部表からM回のフェッチをしなければならない。1回のフェッチにつき、ネットワーク上をパケットが往復するわけであるから、InnoDBやMyISAMのように同一ホストから(特にメモリ上のキャッシュから)データをフェッチする場合と比べてJOINは不利なのである。

ではMySQL ClusterにおいてJOINを高速化するにはどうすればいいだろうか?

単純に「ネットワーク接続を高速化すればいいじゃないか。10GbEのNICを使えば?」などと思うかも知れない。それはある意味正しいが、正しいアプローチではないと思う。確かにJOINの性能は向上するのだが、10GbEとてレイテンシは無視できないので同一ホスト上のメモリからデータをフェッチする場合より遅いのは明らかである。

少し話はそれるが、何かを処理するユニットを増強して(もしくはたくさん並べて)何とかしてしまおうというのは、いかにもBruteなやり方である。確かにハードウェアの性能向上はBruteなやり方でも良いと思うし、Bruteなやり方で成功した事例もたくさんある。例えばグラフィックスチップにたくさんの演算回路(シェーダ)を組み込んだり、ハイエンドサーバにCPUを満載したり、安価なマシンを並べてスケールアウトしたり。しかし、Bruteなアプローチではシステムの性能の限界はハードウェアの性能の限界によって頭打ちしてしまうことになる。だが一方で、ソフトウェアの性能向上を考える場合には、同じ条件のハードウェアで如何に高速化するかということを検討しなければならないと思う。つまり、もっとSmartなやり方でないといけない。ハードウェアはBruteに。ソフトウェアはSmartに。それがシステムを高速化する際のコツだろう。

そんなわけで話は戻るが、つまり単純にネットワーク接続を高速化するのは、一定の効果は上がるがすぐに限界を迎えてしまう可能性が高いのである。

現時点でも実装可能かつスマートなアプローチは、レプリケーションを利用することである。Kaj Arno氏のエントリでも紹介されているが、MySQL Clusterから通常のMySQL Serverへのレプリケーションを行い、JOINを伴う複雑なSELECTに関してはスレーブで実行することにより、複雑なSELECTを高速化するというテクニックが存在する。(詳細はKaj氏のブログエントリの図を参照して頂きたい。)スレーブへのレプリケーションは非同期なので、厳密な最新のデータに対するクエリは実行出来ないが、厳密な最新のデータが必要ない場合この方法は大抵うまくいく。システムの構築がちょっと面倒臭くなる以外弊害もない。複雑なクエリは集計データなどに利用されることが多いので、適用出来るシーンも多いだろう。

この方法で気をつけるべきポイントは、replicate[-wild]-do-tablereplicate[-wild]-ignore-tableオプションを利用して、複製するテーブルを限定することである。そうしないとndb_apply_statusテーブルへの更新が出来ないというエラーに見舞われてしまうことになる。MySQL Clusterテーブルを更新すると、バイナリログは自動的にmysql.ndb_apply_statusテーブルへの更新が含まれてしまう。このテーブルはNDBストレージエンジンで定義されているテーブルでMySQL Cluster同士のレプリケーションに利用されるのだが、MySQL Clusterから通常のMySQL Serverへレプリケーションする場合には不要などころかエラーの元凶になるだけなのできっちりとフィルタリングしておこう。例えば、worldデータベースに存在するテーブルだけを対象にしたい場合は、スレーブのmy.cnfに次のようにreplicate-wild-do-tableを使って記述するといいだろう。

[mysqld]
replicate-wild-do-table=world.%

MySQL ClusterのSQLノード上で新規にテーブルを作成する場合、つまりCREATE TABLE tbl(...) ENGINE NDB;とした場合に、スレーブ側ではデフォルトのストレージエンジンが使用されることになる点にも注意したい。(通常のMySQL ServerにはNDBストレージエンジンは含まれていないからだ。)--storage-engineオプションを好みのもの(InnoDB等)に設定しておこう。

しかし、MySQL Clusterの開発者たちは、JOINが遅いという現状をいつまでも放置しておくつもりはない。

将来的にはMySQL ClusterのJOIN性能は大幅に改善される予定である。まず、近い将来に搭載される機能として挙げられるのがBKA(Batched Key Access)というJOIN最適化手法である。この方法では、これまで1+M回必要だったデータのフェッチが、最も効率的な場合にはたったの2回にまで減少する。2つのNDBテーブルのJOINにおいて外部表からM行フェッチし、外部表の一行につき内部表から平均でN行フェッチする必要がある場合、BKAの動作は次のようになる。
  1. 外部表からM行フェッチ(一回のスキャン)
  2. JOINに利用するキーの値をリストアップする。
  3. リストアップされたキーをNDBストレージエンジンにPush-Downする。
  4. 内部表からN行フェッチ(一回のスキャン)
内部表からレコードをフェッチする際、ICT(Index Condition Pushdown)という機能が利用されるのだが、ICTではストレージエンジンに対してフェッチしたい行を含むキーを一気に送信し、レコードを一気にフェッチするのである。その結果、MySQL Clusterではネットワーク上のパケット往復の回数が劇的に減少し、JOINの性能が向上するというわけだ。従って、BKAが実装された暁には、通常のMySQL Serverへレプリケーションするといった面倒な運用は一切不要になるだろう。少なくとも他のストレージエンジンと同等程度までJOINの性能が改善するはずであるから。

BKAブラボー!!と思うかも知れない。
しかし、そんなところで終わるようなMySQL Cluster開発チームではないのである!!

実装されるのはかなり先になるだろうが、MySQL ClusterのJOINを劇的に高速化することが出来ると予想される機能が実装される見込みである。それはDbspjと呼ばれる機能であり、言うなれば「分散JOIN」とでも呼ぶべきシロモノである。かなり貪欲な性能の追求である。MySQL Clusterは分散型のRDBMSであるから、JOINの処理も分散して行えば良いじゃないかと考えるのが人情というもであるが、一方でそのような機能を実装するのは難しいということもまた事実である。(従って現時点ではそのような機能は実装されていない。)しかし難しいというのを理由にして諦めないのが真の漢。MySQL Cluster開発チームはこの難題にチャレンジしており、既に初期段階のテスト結果が開発者Jonas Oreland氏のブログで公表されている。ぶっちゃけ通常のJOINと比べると格段に速い。MySQL Clusterの正式リリースに搭載されるのはずっと先になるだろうが、楽しみな機能の一つである。

2009-11-02

GPLソフトウェアのパッチをBSDライセンスで提供することの意義

先日の投稿「GPLが適用されているソフトウェア=MySQLのパッチをBSDライセンスでリリースする。では、GPLが適用されているソフトウェアにBSDライセンスのパッチを提供することが出来るということを書いた。ただし、それが出来ることによってどのような意義があるのかということについては触れていなかった。その結果、
単独で動かないパッチに元のと違うライセンスをつける感覚がよくわからない。
という疑問が生じたらしい(ブコメ参照)ので、パッチをBSDライセンスで提供するということはどういうことなのかを説明しようと思う。

まず第一に、パッチ自身はBSDライセンスなので、BSDライセンスに従う限り他のプログラムへ流用することが出来る。
パッチといえども、それが何かの機能を追加する類のものであれば巨大なプログラムになり得るだろう。事実、Googleが提供するMySQLのパッチもかなりデカイ。パッチの規模がでかくなれば、独立して機能する有益なロジックが多々含まれることになるだろう。パッチのライセンスがBSDライセンスであれば、その機能をGPL以外のライセンスのソフトウェア、例えばBSDライセンスのPostgreSQLなどに追加するということも可能である。つまり、パッチをBSDライセンスにすることで、MySQLとPostgreSQLに同じ機能を追加するということが出来るわけだ。

第二に、
MySQLはデュアルライセンスなので、BSDライセンスで提供されたパッチであればGPL版とコマーシャルライセンス版の両方に機能を追加することが出来る。従って、BSDライセンスのパッチはMySQLにとっては都合が良いのである。(MySQLがデュアルライセンスを貫く以上、GPLで提供されたパッチは適用出来ないのである。)

ちなみに、GPLソフトウェアであるMySQL 6.0からforkしたDrizzleも、
全てのContributionはBSDライセンスのもとに行われている。(Drizzleに提供された全てのソースコードはBSDライセンスが適用されている。)従って、Drizzleに追加された全ての機能は、GPL版、コマーシャルライセンス版のいずれのMySQLにも取り込むことが出来るのである。また、DrizzleにContributeされたコードは、PostgreSQLなどの他のライセンスのRDBMSソフトウェアにも取り込むことが出来るので、PostgreSQLerの人は是非Drizzleのソースコードを覗いて見ると良いのではないだろうか。ただし、Drizzleでは積極的に外部のライブラリを取り込んで利用しようという方針があるので、外部のGPLが適用されたライブラリに依存した機能については、BSDライセンスによる利用は出来ない点には注意が必要である。(もちろん元のMySQL 6.0から残っているコードはPostgreSQLに取り込むことは出来ないので注意しよう。)

さて、ここまで書くと「GPLよりBSDライセンスの方が優れている」ということを言い出す人が居るかも知れないので、この点について少し捕捉しておく。
GPLとBSDライセンスを比較するのはハッキリ言って無意味である。確かにBSDライセンスの方が再利用出来るソフトウェアの範囲が広い。(商用、無償、プロプラエタリ、OSSを問わず利用可能である。)しかし一方で、GPLはソフトウェアの利用者に(それをカスタマイズすることを含めて)未来永劫最大限の自由を約束するライセンスであり、GPLを継承することによって再利用可能な場面が限定されることは、その自由を約束するために必要な措置なのである。つまり、GPLとBSDライセンスはそれぞれ異なる属性を持ったライセンス(かたやCopyleft、かたやPermissive)であり、それぞれのライセンスを適切に使い分けるのが重要だということである。ライセンスに対する理解とそれらの使い分けは、オープンソースに生きる人々にとっては最も重要な嗜みと言えるだろう。