NoSQLによく使われているインデックス方式としてLSM-treeというものがあると思います。これは一度トランザクションという考えではなく、一度データをディスク上のログ領域に書き込み、その後メモリに書き込むというものです。しかし、例えば書き込みが秒間10万リクエスト受け付ける必要があるとします。すると、ログの書き込みを毎回行なっていたら非常に遅いデータストア担ってしまうと思うのですが、これはシステム的にどのように回避しているのでしょうか？

行動規範の内容に同意します

回答1件

ベストアンサー

トランザクションという考えではなく、一度データをディスク上のログ領域に書き込み、その後メモリに書き込むというもの

この理解は正しくないです。

1

SQLでもNoSQLでも、多くの実装で、更新があるたびに更新データをディスク上のログ領域に書き出し、続いてメモリ上のキャッシュを更新する仕組みがあります。サーバがクラッシュするなどしてキャッシュが失われても、再起動時にログを順番に読み取っていけば、キャッシュの内容をクラッシュ直前の状態に復旧することができます。このように、メモリ上のキャッシュの更新に先立ってディスクに更新データを書き出しておき、クラッシュリカバリに役立てる仕組みを、先行書き込みログ (WAL) などと呼びます (呼び方は実装によって違います)。

データベース中のインデクスやテーブル (に相当するもの) へのアクセスは、可能な限りメモリ上のキャッシュにアクセスすることで行います。これにより、直近に更新されたデータの参照・更新はメモリアクセスだけで行えます。キャッシュにないデータは、ディスク上のデータベースストアからメモリに読み込まれます。

一方、キャッシュサイズは無限に大きくはできませんから、キャッシュが一定のサイズに達したら、累積された更新をディスク上のデータベースストアに書き出します。このとき、書き出された更新の分のWALは削除することができます。

以上のことは、SQLでもNoSQLでも同じようなものです。つまり、LSM-treeとWALは関係ありません。たしかに、質問者さんも懸念されている通り、更新の度にWALのためのディスクへの書き込みが発生してしまいますが、クラッシュリカバリを実現するためにはやむを得ないことです。

ただ、以上の説明でお気づきかもしれませんが、WALがなくてもデータベースは動作します。WALの保存を停止することで、クラッシュリカバリを諦める代わりにパフォーマンス向上をめざした運用をする場合はあります。また、WALに相当する機能を最初から持たない実装もあります。

2

メモリ上のキャッシュは多くの場合B木やそれに似たアルゴリズムで実現されています。メモリのようにランダムアクセスが高速に行えるデバイスの上では、データの挿入・検索が高速に行えます。

ディスク上のデータベースストアもB木や類似の形式とした場合、キャッシュをディスクに書き出すときや、キャッシュにないデータをディスクからメモリに読み込むときに、多くのランダムアクセスが発生します。伝統的なディスクデバイスでは、シーケンシャルアクセスにくらべてランダムアクセスの性能が低下します (これは、プラッタ上の互いに離れた場所へのアクセスには磁気ヘッドの移動が必要になるためです)。

LSM-treeアルゴリズムは、このようなディスクデバイスの特性に合わせて、なるべくランダムアクセスを減らすようなアルゴリズムとして考案されたもののようです。次のような特徴があります。

単一のデータベースストアに更新を書き出すのではなく、小さなストアファイルに分けて書き出す。これにより、書き込みのほとんどは単なるシーケンシャルライトになる。
データベースストアからの読み出しは、ほぼストアファイルの数だけのシーケンシャルリードで完了する。
ストアファイルが増えてきたら、小さなストアファイルをまとめてより大きなストアファイルにする操作 (コンパクション) を行う。これはマージソートと同様のアルゴリズムでB木などより高速にできる。

詳しくは、次のウィキペディア (英語版) の記事の参考文献などを参照して下さい。LSM-treeやそうでない実装のベンチマーク比較も見つかります。