A simple and efficient implementation for small databases

chubbyの下回りのDBは、この論文https://ng.gnunet.org/sites/default/files/024-DatabasesPaper.pdfをもとにして作成したらしい。読んでみてのメモ。

オペレーティングシステムや分散システムで出てくるような小さいデータベースの実装について述べる。とても大きい仮想メモリメモリと大きな物理メモリを利用した技術である。データベースを仮想メモリ内で、強く型付けされたデータ構造とする。レコードの更新は、ディスク上のログファイルに追記され、たまに、データベース全体へのチェックポイントを作成する。強い型を持ったデータ構造の直列化は、既存のライブラリを利用している。このスキームは、分散システムに対するネームサーバを実装するときに利用されている。単純で、効果的で、信頼性が高という特徴を持っている。

OSや分散システムのデザインにおいて、構造化されて、再起動にも耐えうる永続化されたデータを管理する状況というのは多々ある。こういったシステムをデータベースとよく呼ぶけれども、銀行や保険業界でり用いられるようなデータベースとは別ものである。我々がここで考えるデータベースとは、以下のような特徴を持っている。それらは、相対的に小さく、せいぜい10MBまで。更新頻度も適度であり、高々秒間10トランザクション、１日当たりの平均は10000トランザクション。トランザクションもsigle-shotアクションである。言い換えると、複数のクライアントの要求からなるようなトランザクションはない（client actionsが分からないなあ）、トランザクションの途中状態はクライアントからは見えない。データの例としては、ユーザアカウント、名前解決サーバ、コンフィグといったものである。この論文では、そういったクラスを対象とするデータベースの実装方法について述べる。データ工学分野ではよく知られている、チェックポイントとredoログを持つようなメインメモリデータベースである。

OSの分野の人に、技術を知ってほしい。古くて新しい話である。他の実装も見てみたが、機能上抜けがある。この論文を通して、名前解決サーバを題材とし、それは分散コンピューティング環境で利用されている。特定の型を理解する実装としている。このことは、一般的なデータベースとは対照的である。

状況によって、このタイプのデータベースの実装は変わる。Unixでは、ファイル。データにアクセスしたければ、ファイルを読んでパースする。ファイル操作は、単にテキストファイルを書くだけ。そのような更新は、直列化される必要がある。管理者は、排他ロックを持った状態で更新を行う。ファイルの更新は、アトミックな操作であるrenameを利用することで、書き換え中のマシン電源障害とかには合わずにすむ。部分的にデータが読めなくなるというような障害には、フルバックアップで対応。これらの方法の良い点は、単純であること。ただまあ、やり方をみれば、スループットが出ないことは明確。大きなOSでは、特殊なスキームを取る場合がある。更新は、大抵の場合上書きされるが、そうすると一時的なエラーに弱く、バックアップからの復旧が求められる。

より洗練されたデータベースもあって、アトミックなコミットができるようなトランザクション処理を実装していて、信頼性は担保される。このようなシステムでは、undo/redoで更新トランザクションを一時的な障害から復旧する。もう少し頑張れば、ハードエラーからも復旧できる。これらの研究の中には、我々の目的とするようなオプションもある、スナップショットとログを用いたメモリデータストレージである。パフォーマンスと可用性が重要。アトミックコミットをするためには、ひとつの更新で２回の書き込みが必要。ひとつは、ログを書くこと、もうひとつは、実体の更新。信頼性はアップするけど、書き込みに対するコストが２倍。洗練されたデータベースでは、redoログを用いて、実体の更新は遅延させる。実体の更新は、他の最近の更新とまとめて行われる。でも、一般的なデータベースはトランザクションをフルスペックで提供するので、複雑すぎる。

リードは、キャッシュで早くなる。メモリ上にデータベースの実体をのっけるという思想は、このことを副産物として提供する。よいキャッシュ機構は、単純な仮想メモリに比べて、単純になるものでもない。データ構造やアクセスパターンを知っていれば、より良いキャッシュ機構を構築できるが、仮想メモリは実装済みであり、メリットに比べてコストが高い。

デザイン

どんな時でも、仮想メモリ上のデータ構造として、データベースは存在する。チェックポイントで全体を保存し、ログを用いて更新を保存する。仮想メモリ上の構造は、データベースを作りたい人が好きに作れる。リード要求は、仮想メモリへのアクセスだけ。ディスクに対するI/Oは発生しない。もちろん、リード・ライト要求に対するロック戦略は必要。更新は、以下のように行う。更新前の条件を満たすことを確認するため、仮想メモリを読む。更新に必要な情報を全て、ディスク上のログに書く。更新を仮想メモリに反映。コミットが行われたとするポイントは、ディスクへの書き込み時とする。ディスク書き込み前にクラッシュすれば、再起動時にはデータは反映されない。ディスク後であれば、反映する。並行制御のためのロック取得は行う。チェックポイント時には、仮想メモリの状態を全て保存し、それまでのログはリセットされる。書き込みに関するアトミック性は、ファイルシステムの機能を利用する。起動処理は、以下のとおり。現在のチェックポイントを決定し、読み込み仮想メモリに展開。ログの更新情報を仮想メモリに適用し、最新の状態に戻す。新しいチェックポイントをいつ作るかについて考えないといけない。期間が空き過ぎるとログが肥大化、やり過ぎるとパフォーマンスに影響。

ネームサーバの例では、shared/update/exclusiveのロックを用意して、グラフ構造の並列処理に一貫性を持たせる。sharedとupdateは、コンフリクトしないことが特徴的。更新要求では、updateロックを取得し、事前条件を満たしていれば、ログに書き込む。その後、updateロックをexclusiveに昇格し、仮想メモリを更新する。チェックポイント書き込み時においても、updateロックを取得する。思想としては、ログ書き込みの時には排他せず、仮想メモリの変更時にのみ排他する。チェックポイント書き込みを以下に記すが、これが最適と言うつもりはない。利用するディレクトリはひとつ。チェックポイントファイルには、インクリメンタルなidを付ける。新しいチェックポイントファイルを作成し、書きこむ。この時、からのlogfileも作成する。で、newVersionと呼ばれるファイルにidを書きこむ。fsyncを行った後が、コミット完了。古いファイルを削除して、newVersionをversionにrename。newVersionファイルが残っているなら、ファイルを読み込んで、idが記述されていれば、採用。なければ、versionファイルを読み込む。

RELIABILITY

信頼性を二つの観点で考える。ひとつは、一時的な障害であり、システムが突然停止した場合。ひとつは、ハードディスク障害。全車に関しては、リカバリは単純。基本は、ログから復旧すれば良い。部分的に書きこまれたログレコードは無視する。途中までの書き込みかどうかは、エントリの最初に書き込んだレコード長に基づく。チェックポイントの書き込み中に停止の場合は、一つ前のチェックポイントファイルとログファイルから復旧。ネームサーバの例では、ハードディスク障害については、他の正常なレプリカからの復旧を行う。もし、ハードエラーに対して、ログから復旧する場合、おかしなログエントリを無視するという方法もある。また、最新のファイルが壊れたなら、一つ前のチェックポイントファイルとログファイルを利用するという手もある。

PERFORMANCE

パフォーマンスは、仮想メモリへのアクセスなので、良い。仮想メモリへの読み込み時に、page faultが起きなければなお良い。だから、独自のページングシステムとキャッシュシステムを持てばよりよい。が、実装コストが高い。ログ書き込みの際に、複数レコードをまとめて書く方式も考えられるが、同様に実装コスト高い。リスタートや可用性とチェックポイントの期間はトレードオフの関係。ネームサーバの例ではチェックポイント中には、更新ができなくなるので、チェックポイントは重たい処理。チェックポイントの間隔が長いと、ログが長くなるので、起動時間が遅くなる。

とまあ、とりあえず、ここまで。重要なのはシンプルさ。ここで記述されていることは、とてもわかりやすいし、あらゆるところで採用されている気がする。checkpoint+redoログという組み合わせは、単純であるにもかかわらず、障害に強い。ただ、信頼性や永続性を高めようと思うと、このスキームの場合レプリカを作成という方向に向かうので、そうなるとそれほど簡単ではない。bigtableでは、その部分がGFSにお願いしているので、色々と捗る。