mixi engineer blog

＊＊＊ 引っ越しました。最新の情報はこちら → https://medium.com/mixi-developers ＊＊＊ ミクシィ・グループで、実際に開発に携わっているエンジニア達が執筆している公式ブログです。様々なサービスの開発や運用を行っていく際に得た技術情報から採用情報まで、有益な情報を幅広く取り扱っています。

Inside Tokyo Cabinet その四

algorithm

涼しさに夏の終わりを感じてなんだか寂しくなるも、新しいオフィスから見えるパノラマの空の高さに癒されているmikioです。秋は気が変わりやすいこともあり、今回は唐突にDBMの並列性についての考察を記してみます。

sky.jpg

並列性って何?

最近はマルチコアのプロセッサが当り前になってきて、そのパワーを100%引き出すために、並列性をできるだけ高めることが求められるようになってきました。それについて考える前に、まずは用語の整理をしておきましょうか。
  • 並行性 : 二つ以上のタスクを一緒に進めること。必ずしも同時に処理を行うとは限らず、Aを少しやってからBを少しやって、それからまたAを少しやって、またBをやって...といった、いわゆるタイムシェアリングで実現してもよい雰囲気。
  • 並列性 : 二つ以上のタスクを同時に進めること。タスクを複数のマシンに割り当てたり、複数のCPUに割り当てたり、CPU内の複数のコアに割り当てたりして、とにかくマジで同時に処理をやっていく感じ。
  • マルチプロセス : OSがメモリ保護や実行権限を割り当てる単位であるプロセスを複数使ってタスクを進める趣向。
  • マルチスレッド : 単一のプロセス内で作業メモリを共有した複数のスレッドを使ってタスクを進めるニュアンス。
  • スレッドセーフ: マルチスレッドのプログラムから呼び出す場合にそれほど気をつかわなくていいような関数やライブラリの売り文句。
  • リエントラント : スレッドセーフを名乗る前提として、グローバル変数やstaticな内部変数やそれらに依存する関数を使わないようにした関数の気取った言い方。
  • アトミック : あるスレッド（またはプロセス。以下同）が変更中のデータを他のスレッドが参照してしまうと不完全な状態に基づいて処理を進めてしまうおそれがあるので、そういう不完全な参照がないように一連の変更を不可分にやること。つまり変更中の状態があたかも存在しないように見せる努力。
これ以上詳しく説明すると識者の方々から厳しめのツッコミが来そうなのでほどほどにしますが、とにかく、ユーザが定義する様々なタスクの中でのDBMに対する操作である「格納」「削除」「取得」などの並列性を上げたいのです。

マルチプロセスでの並列性向上策としては、ファイルロックを使っています。データベースファイルを開く際に読み込み専用の「リーダ」と読み書き両用の「ライタ」を指定できるようにして、リーダ同士は複数のプロセスが同時にデータベースファイルを開けるが、ライタとしてデータベースファイルを開いたプロセスが一つでもある場合はそのプロセスがデータベースファイルを閉じるまで他のプロセスは同時に接続できないようにします。接続できないといっても、エラーになるわけではなく、接続できるようになるまで待たされる（ブロックする）というのがポイントです。各プロセスがDBMに対する一連の操作が終わった時に行儀よくファイルを閉じるようにすれば、少なくとも読み込みは並列に処理できますし、書き込みと読み込みは並行に処理できます。

ただし、細かい操作の都度データベースファイルを開いたり閉じたりするのはオーバーヘッドが大きいので、個人のユースケースではそれでも十分なことが多いかもしれませんが、mixiのような大規模なサイトではその戦略は現実的ではありません。そこで、マルチスレッドを重視することになります。データベースに接続したままのひとつのプロセスがいわゆるサーバの役割を果たし、アプリケーションから渡されるクエリを並列に処理するのです。今、サーバの役割といいましたが、実際にクライアント/サーバ方式でDBMサーバをバックエンドに持つシステムを設計することもできますし、アプリケーションのプロセス自体にDBMを組み込んだ場合でも、DBMオブジェクトにあたかも並列処理能力のあるサーバのように振る舞わせるというのが理想でしょう。

マルチスレッドで使うライブラリは、もちろんスレッドセーフでないといけません。一言にスレッドセーフといっても解釈が曖昧ではありますが、ここでは、APIの関数がリエントラントである上に、それらに渡すパラメータであるDBMオブジェクトの状態変更がアトミックであり、すなわちAPIの関数をアプリケーション側で排他制御することなしに呼び出せるということをゴールに設定します。前回述べたように、グローバル変数に依存しないAPIを設計し実装したことでリエントラントを達成するのは比較的容易だったTCですが、DBMオブジェクトのアトミック性をいかに確保するかについてこれから考えていくことにしましょう。

クリティカルセクション

DBMオブジェクトはもちろん状態を持つものですから、スレッドセーフにするには、オブジェクトの更新はアトミックに行わねばなりません。更新をアトミックにするには、他のスレッドが同時に更新処理をできないように、更新する前にロックを獲得し、更新した後にそのロックを解放するという排他制御を行うことになります。このように排他制御した区間をクリティカルセクションと呼びます。UNIX上では、ロックはmutexというオブジェクトを使うことで実現できます。 最も簡単にアトミック性を確保するには、全てのAPI関数をクリティカルセクションに入れるというのが考えられます。つまり、関数の最初と最後でオブジェクトに対してロックをかけるのです。それはこんな風な実装になります。 
static bool tchdblockobj(TCHDB *hdb){ 
  return pthread_mutex_lock(&hdb->mutex) == 0; 
}  

static bool tchdbunlockobj(TCHDB *hdb){ 
  return pthread_mutex_unlock(&hdb->mutex) == 0; 
}  

bool tchdbput(TCHDB *hdb, const char *kbuf, int ksiz, 
    const char *vbuf, int vsiz){ 
  if(!tchdblockobj(hdb)) return false;   // ロックをかける 
  ... // ここで関数の処理を行う 
  if(!tchdbunlockobj(hdb)) return false; // ロックを解放する 
}  

char *tchdbget(TCHDB *hdb, const char *kbuf, int ksiz, int *sp){ 
  if(!tchdblockobj(hdb)) return NULL;    // ロックをかける 
  ... // ここで関数の処理を行う 
  if(!tchdbunlockobj(hdb)) return NULL;  // ロックを解放する 
}
putは更新処理を伴うのでクリティカルセクションを張るのはもちろんですが、getも更新中の状態にアクセスしてはならないので、putなどが同時に動いていないことを保証するためにgetにもクリティカルセクションを張るのがポイントです。なお、ロックが取得できないとか解放できないとかいう事態は稀で、ほとんどバグによるものですが、いちおうエラーチェックも忘れてはいけません。

上記のようにlockとunlockを書きまくればスレッドセーフは実現できるわけで、QDBMはそうして「スレッドセーフです」と言い張っているわけですが、これは並列性という意味ではダメダメなアプローチと言わざるを得ません。同時に1スレッドしかDBMの具体的な処理をできないようにしているわけで、複数のスレッドを並列実行できる最近のプロセッサのパワーを使いきることができないからです。

ああ、面倒くさい。しかし、せっかく64ビット対応してディスクの大容量化というトレンドについていけるようになったのだから、マルチコアのトレンドにもついていかないといけません。そのためには、複数のスレッドが真の意味で同時にputやgetを実行できるようにしないといけないのです。うぉー。やっぱ面倒くさい。

粒度を見極める

同時に読み書きするといけない状態のことをレースコンディションと呼びますが、実際にはDBMオブジェクト全体がレースコンディションを持つわけではありません。DBMオブジェクトの内部状態の要素をもっと細かく分類した上で、関係あるグループ毎に、それを参照するコードにクリティカルセクションを張っていくことにします。

内部状態の代表選手はバケット配列ですね。バケット配列の個々の要素はlong int型（またはlong long int型）の変数なので、プロセッサの単一の命令でアトミックに読み書きできそうです。また、個々の要素は相互に依存しないので、同時に読み書きしても問題なさそうです。したがって、バケット配列はレースコンディションの心配はないと判断し、その操作にはクリティカルセクションは設けないこととします。

次に、put/out/getがバケット配列の後に参照することになるセパレートチェーンはどうでしょうか。これはレースコンディションありまくりです。二分探索木の親子関係を操作するにあたって、「子供を移動させる」「親からのチェーンをつなぎ変える」という大きな処理が行われますが、それらは全てアトミックでないといけません。となると更新も探索も並列にはできないじゃないかと思うかもしれませんが、そうではありません。幸いなことにチェーンの依存関係は同じバケット要素から連なるレコード間でしか生じないので、バケット要素単位でロックをかければレースコンディションは回避できそうです。同じバケットのレコードを同時に操作する確率は低いでしょうから、バケット要素単位のロックなら並列性は十分と言えるでしょう。ただし、mutexオブジェクトを作るオーバーヘッドも馬鹿にならない（私の環境では各24バイト）ので、バケット数の分だけmutexオブジェクトを作るわけにはいきません。そこで、バケットのインデックスを256くらいで割った数でグループ化してmutexオブジェクトを割り当ててロックをかけることにしましょう。

バケットとチェーンの操作が並列に行えることで、put/out/getは同時に実行できるようになったでしょうか。いやいや、まだ他にもレースコンディションは潜んでいます。DBMオブジェクトが持つメタデータとしてレコード数やファイルサイズなどがありますが、それらに依存する処理はオブジェクト単位のロックをかける必要があります。フリーブロックプールも同様にオブジェクト単位のロックが必要です。ただ、それらの操作はディスクI/Oと関係なく一瞬で終わるので、遠慮なくロックかけてもそれほど問題ではないでしょう。

さらに忘れてならないのは、データベースファイルそれ自体がレースコンディションを持つということです。なぜなら、ファイルの読み書きを行う際の位置（オフセット）はファイルディスクリプタに関連づけられた内部状態としてOSが管理しているからです。すなわち、lseek/readおよびlseek/writeの組み合せはアトミックにしないといけません。

最も上層に操作単位の排他制御も必要となります。open/closeなどのデータベースそれ自体への操作は、put/get/outなどの終了を待ってから行わねばならないからです。

最後の課題は「エラーコード」です。エラーコードはDBMオブジェクトに問い合わせる形になっていますが、それだと他のスレッドのエラーを拾ってしまう可能性があるのでよろしくないです。これはTSD（thread specific data）にすることで回避するしかありません。つまりスレッド毎に変数のコピーを用意して、単一の変数にアクセスしているつもりで別々の領域を参照させるのです。

以上をまとめると、以下の種類のロックを用意して、多重にクリティカルセクションを張ることになります。
  • メソッドロック : データベース操作に対するロック
  • レコードロック : バケット要素をいくつかにグループ分けした単位のロック
  • オブジェクトロック : オブジェクトそれ自体にかけるロック
  • I/Oロック : ファイルのI/Oに伴うロック

デッドロック対策

妻は自分の髪を売った金で夫へのプレゼントとして時計のチェーンを買い、夫は自分の時計を売った金で妻へのプレゼントの櫛を買うという話がO.Henryの短篇にありますが、スレッドプログラミングで同様の行き違いが起きた場合は本当の悲劇になってしまいます。すなわち、スレッドAはスレッドBの持つロックの解放を待ち、スレッドBはスレッドAの持つロックの解放を待つことで、処理が永遠に停止してしまうという、いわゆるデッドロックの問題です。 デッドロックを防ぐには、クリティカルセクションを多重化したとしても再帰しないようにすることが重要です。ということで、putを題材にして、ロックの構造をXML的に疑似コードに入れるとこんな感じになります。 
put(){ 
    <method_lock> 
        check_db_is_open; 
        <record_lock> 
            scan_chains(){ 
                <io_lock> 
                    lseek_read; 
                </io_lock> 
            } 
            write_records(){ 
                <object_lock> 
                    check_meta_data; 
                        <io_lock> 
                            lseek_write; 
                        </io_lock> 
                    update_meta_data; 
                </object_lock> 
            } 
        </record_lock> 
    </method_lock> 
}
ここでとってもとっても重要なのは、「メソッドロック＞レコードロック＞オブジェクトロック＞I/Oロック」という関係を常に成立させ、それを逆転させないことです。ただし、scan_chainsの中でレコードロックの直下でI/Oロックをかけていますが、これはI/Oロックのクリティカルセクションは最下位なので自明にアトミックとみなせるからOKなのです。さらに、I/Oロックのクリティカルセクションがアトミックならばその直上位であるオブジェクトロックのクリティカルセクションもアトミックとみなせ、そうするとその直上位であるレコードロックのクリティカルセクションもアトミックとみなせ、最終的に最上位であるメソッドロックのクリティカルセクションもアトミックとみなせるというわけです。長げー。

リードライトロック

get/put/outの間でレコードロックをしないといけないのはわかりましたが、get同士であれば更新がないので排他制御をしなくてもいいような気がします。そのような場合には、リードライトロックが役に立ちます。これはmutexとほぼ同じ挙動をするのですが、ロックの際にリードロック（共有ロック）モードとライトロック（排他ロック）モードが選べるのが特徴です。そして、リードロックは他のスレッドのライトロックのみをブロックし、ライトロックはリードロックもライトロックもブロックします。マルチプロセスのところで説明したファイルロック機構と同じカラクリですね。ということで、レコードロックに層にて、getはリードロックをかけて、outとputはライトロックをかけるようにするとよいでしょう。 メソッドロックでもリードライトロックが活用されます。open/closeはライトロックで、put/out/getはリードロックです。メソッドロックが普通のmutexだったら全く並列性がないですもんね。

まとめ

DBMの並列性を「読み込みや書き込みを同時に行える能力」と定義して、特にマルチスレッド環境での並列性を引き出すための設計について述べました。レースコンディションをクリティカルセクションで包むためにロックを配置していくという考え方で設計を進めたものです。

ちなみにこの設計はまだ実装していません。ぶっちゃけ、TCは十分に高速なんで、メソッドロックをリードライトロックで運用するだけでも十分だと思うし、ロックをたくさん入れることによる性能劣化を考えるとメソッドロックのみにする誘惑にかられます。ロック絡みのバグって本当につぶしにくいから、複雑なロック機構を入れると保守性も下がるんですよね。うー。悩みます。皆さんどう思います？

次回はたぶん最終回で、TCのその他の工夫について言い残したことを消化します。