以下は、drivers/md/bcache/bcache.h の先頭のコメントの kanda.motohiro@gmail.com による訳です。原文と同じ、GPLv2 で公開します。訳したときのカーネルバージョンは v3.12 です。
bcache は、キャッシュセット、キャッシュデバイス、そして背後のデバイス(backing device)を扱うのが主な仕事です。
複数のキャッシュデバイスサポートはまだ完全には終わっていませんが、 95% くらいは完成しています。キャシュセットとそのキャッシュデバイスの関係は、 md raid アレイとそのコンポーネントデバイスの関係といえます。コードのほとんどは、個々のキャッシュデバイスは気にしません。キャッシュセットが主な抽象化を提供します。
複数のキャッシュデバイスがあれば、ダーティなキャッシュデータとメタデータをミラーすることができます。クリーンなキャッシュデータはミラーの必要はありません。
背後のデバイスは、キャッシュセットとは独立した有効期間を持つという点で特別です。新しくフォーマットした背後のデバイスを登録すると、パススルーモードで現れます。背後のデバイスは実行時にキャッシュセットからアタッチ、デタッチできます。マウントされて、使用されていても可能です。デタッチすると、その背後のデバイスのすべてのキャッシュデータは暗黙的に無効になります。
キャッシュセットは、複数の(多数の)背後のデバイスがそれにアタッチされることができます。
フラッシュオンリーボリュームというのもあります。このために、struct cached_dev と struct bcache_device の区別が必要です。フラッシュオンリーボリュームはおおむね、背後のデバイスを持つ bcache デバイスと同様に動きますが、「キャッシュ」データは常にダーティです。結局、少しコードを追加することで、シンプロビジョニングが得られたということです。
フラッシュオンリーボリュームは動きますが、移動するガーベッジコレクター(moving garbage collector)は未完成なので、本番向けではありません。これについては後で。
bcache はキャッシュのためにあります。ということは、通常処理ですべての使用可能領域は確保されているということです。このため、キャッシュからものを削除して、新しいものを書くことができるようにするための効率的な方法が必要です。
このために、キャッシュデバイスはバケツに分けられます。バケツは確保の単位です。典型的には、1 mb くらいです。128k から 2M+ ならどこでも効率的です。
バケツには16ビットの優先度と8ビットの世代番号があります。すべてのバケツの優先度と世代番号はディスク上で連続してパックされて格納されています。(バケツのリンクリストになっています。スーパーブロックを除いて、すべての bcache_メタデータはバケツに格納されています。)
優先度は LRU を実現します。バケツの優先度は、それを確保、あるいはキャッシュに使う時にリセットされます。ときどき、それぞれのバケツの優先度を減算します。誰かがやる気になったら、もっと洗練されたものにしてもよいでしょう。
世代番号は、バケツを無効にするのに使います。それぞれのポインターにも8ビットの世代番号があります。ポインターとそれが指すバケツの世代番号が同じの時に限り、ポインターは有効です。このため、バケツを再使用するためには、世代番号を加算するだけでよいです。(そして新しい世代番号をディスクに書きます。これはまとめて行われます。)
bcache は、完全に COW です。バケツへの書き込みはけっして2度は行われません。メタデータを持つバケツもです。(btree ノードもです。)
bcache は、ほぼ、B ツリーをめぐる設計だといってもよいでしょう。
高レベルから言えば、B ツリーはただの、キー => ポインターの組のインデックスです。
キーはエクステントを表します。なので、長さフィールドを持ちます。キーには、可変個のポインターがついています。(ゼロの時もあります。キャッシュが無効であるのを表すのに便利です。)
キー自身は、inode:オフセットの組です。 inode 番号は背後のデバイスあるいはフラッシュオンリーボリュームを示します。オフセットは、そのデバイス内のそのエクステントの最終オフセットです。開始オフセットではありません。これにより、参照が少し便利になります。
ポインターは、キャッシュデバイスの ID、そのデバイス内のオフセット、そして8ビットの世代番号です。世代番号については、後述します。
インデックス検索は、完全に抽象化されてはいません。特に、キャッシュ検索はいまだ、 btree コードといくぶん混在しています。しかし、分離の方向に進むはずです。
逆に、更新は完全に抽象化されています。btree を更新するには2つの異なる方法があります。挿入と置換です。
btree 挿入は、単に、キーのリストをもらって、btree に挿入します。オーバーラップするエクステントがあれば、上書き(部分的に、のときもあります。)します。これは、ライトの後にインデックスを更新するのに使います。
btree 置換は実際に cmpxchg() です。挿入するキーが上書きしようとするキーとマッチする時に限って btree にキーを挿入します。これは、キャッシュミスの後でデータをキャッシュに置くのに使います。また、バックグラウンドのライトバックや、移動するガーベジコレクターにも使います。
「削除」操作というものはありません。インデックスからものを削除するのは、ポインターを無効にする(バケツの世代番号を加算して)か、あるいは0ポインターを持つキーを挿入する(以前にインデックス
のその位置にあったものをなんでも上書きします。)ことで行われます。
ということは、btree は常に古い/無効なキーがあるということです。btree ノード内をループするコードはそれらをフィルターアウトし、btree ノードが再度書かれた時には削除されます。
確保単位はバケツです。バケツより小さい任意の単位での確保、解放はできません。このため、btree ノードはけっこう大きくなります。
(バケツがとても大きいと思えるなら、バケツの一部分(1/4以下)だけを btree ノードに使うのもよいかもしれません。でも、バケツに1つの btree ノード以外のものを入れることもできません。私は実はこれを変えたいと思っていますが、まあ、今のところはノードの再書き込みあるいはスプリットのときにバケツの世代番号によって btree ノードが削除されるのに任せましょう。)
とにかく、btree ノードは巨大です。教科書にある btree 実装では非効率です。
これを解決するために、btree ノードは内部的にログ構造をとっています。既存の btree ノードに新しいキーを追加するとき、再書き込みは不要です。つまり、書き込む複数のキーのセットのそれぞれはソートされていますが、ノードはそうでないということです。
このログ構造は、メモリーに維持されます。 1Mb のキーをソートして保持するのは高価で、書き込んだキーと書いてないキーは区別しないといけません。この結果、btree 検索は、ソートされたセットのそれぞれを見ないといけません。しかし、書き込まれたセットを一緒にマージするのは後でゆっくり行いますから、前記余分な検索のコストはとても小さいです。(通常は、ある btree ノードのほとんどのキーは1つの大きなセットに含まれ、それよりずっと小さなセットが1つか2つあるでしょう。)
このログ構造の結果、bcache の btree は従来の btree と圧縮データ構造のハイブリッド以上のものとなります。両方の長所を備えます。
どんなバケツも、ただ無効にはできません。ダーティなデータやメタデータがあるかもしれません。ダーティデータがあって、他のライトがそれを上書きした結果、インデックスにそのバケツへの有効なポインターが無いこともあります。
ですから、ガーベッジコレクションの主な目的は再使用できるバケツを見つけることです。また、それぞれのバケツが現在どれくらいの有効なデータを持っているか数えます。確保の時に、ほぼ上書きされたデータが多いバケツを再使用するのが高速にできます。
また、btree 実装の内部的な用もたします。btree ノードがあるしきい値を越える数の無効なポインターを持つ時は、btree ノードを再書き込みして、バケツの世代番号がラップするのを防ぎます。隣り合った btree ノードがほとんど空の時は、マージします。
bcache のジャーナルは、一貫性のためには不要です。メタデータ書き込みは常に厳密に順序付けられていて、btree やその他のすべてが、アンクリーンなシャットダウンがあってもディスク上で一貫するようにしています。実際、bcache 実装は、ジャーナルが実装される前から、ライトバックキャッシュ(アンクリーンなシャットダウンからの回復が可能な)をサポートしていました。
その代わり、ジャーナルは純粋に性能最適化のためです。ディスク上のインデックスを更新するまで、ライトは完了できません。そうでないと、アンクリーンなシャットダウンでキャッシュは一貫性を失います。つまり、ジャーナルがないときは、ランダムライトの負荷の時には、常に btree のすべてのリーフノードを更新し続けないといけません。さらに、これらのライトはほとんど、空です。(一度に、いくつかのキーを追加するだけです。)メタデータライトの量としてはとても非効率です。また、各種の btree の再ソート/圧縮コードにも負担をかけます。
ジャーナルは、挿入したキーの単なるログです。開始時に、オープンジャーナルエントリーのすべてのキーは、再挿入されます。つまり、btree ノードを更新するには、キーを含む 4k ブロックが一杯になって書きだされるまで待ちます。
簡単のため、リーフノードの更新だけをジャーナルします。親ノードの更新はまれですから、(リーフはとても大きいので。)面倒な割にあいません。(特に、ジャーナルリプレイ)リーフでないノードの更新は、同期で行われます。(btree_split() を参照。)
以上