Go と Badger#
前回、HDD 上での優れた書き込み性能と最適化後の受け入れ可能な読み取り性能により、LSM🌲は B🌲の競争の激しいデータベース領域で一定の地位を確立しました。LSM🌲関連の技術は学習しやすく、書きやすく、並行性が高いなどの理由から、新しいタイプのデータベースは LSM🌲関連のストレージバックエンドに移行しています。
前回の記事に引き続き、HDD は回転式であるため、ランダムアクセスのパフォーマンスは順次アクセスの 100 倍遅くなります...
しかし、時代を超越した発明が登場しました！
それは、価格が上昇し続け、寿命を短くすることで価格を下げる SSD というストレージメディアです！
前回の記事で、LSM🌲の高速化の主な理由は次のとおりです：
- 新しいデータはまずメモリに入る
- ディスクに順次書き込む
- 定期的にディスクを整理する
第 3 のステップは、ディスクからの冷たいデータの読み取り速度を決定しますが、その代償としてデータをレベルごとに分割する必要があります。たとえば、10M は 1 つのレベルであり、100M は別のレベルです。小さいレベルから大きなレベルに整理するプロセスを「コンパクション」と呼びます。ほとんどの LSM は次の式を使用してレベルをアップグレードします：
sizeof( L+1 ) = 10 * sizeof( L )
1 つのレベルに収まりきれない情報を格納するために、より大きなレベルに整理する必要があります。このときに他のレベルとマージすることを「書き込みの増加」と呼びます（何度も書き込むため）。
同様に、特定のキーを検索する場合、そのキーが異なるレベルに格納されている場合、多くの回数検索することになります。これを「読み込みの増加」と呼びます（何度も読み込むため）。
したがって... 最適化の余地は、SSD の効率的なランダム読み取り性能を使用して LSM🌲を最適化し、読み込みの増加と書き込みの増加を低減することです。
ただし、書き込みの増加は SSD の寿命を大幅に短縮するため、効率的なランダム読み取り能力を利用する場合は書き込みの増加を減らす必要があります。
Badger の登場#
創設者：私は Go のユーザーです。私は DB を書きたいです。RocksDB を見てみると、できるかもしれませんが、なぜ CGo を開発しなければならないのでしょうか？CGo を開発すると、Goroutine が pthread によって遅くなり、メモリリークが発生します。クソ C（私も同意します）、私は Go で書き直します（私も同意します、なぜなら RocksDB の開発者は CMake の書き方さえ知りません）。
Badger は次の機能のみを提供しています。
Get、Set、Delete、Iterate関数。さらに、CompareAndSetおよびCompareAndDeleteのアトミック操作を追加します。
RocksDB と比較して、Badger は最初からトランザクションに対して考慮を行い、データベースの書き込みをより簡単にします。
Badger と HDD 上の LSM🌲の違い#
KV ペアを分離して保存し、Key を LSM🌲に保存し、Value を WAL（ログ）に保存することで、LSM🌲のサイズを RocksDB の半分にすることができ、書き込みの増加のパフォーマンス損失を低減します。2 番目のポイントは、SSD のランダム読み取り機能を使用して直接 WAL から値を取得することです。
実装の詳細#
KV を別々に保存#
元の LSM🌲の主なコストは「コンパクション」中にオフラインでソートを行う必要があるため、イテレーションが発生しますが、通常は Key のソートを行い、このプロセスで Value は変更されません。そのため、Badger は Key と Value の保存を分離し、無駄な Value のソートによるメモリの浪費を大幅に削減しています。
第 2 に、Badger は Value の位置を「デルタエンコーディング」と呼ばれるポインタの形式で Key の右側に保存し、SSD に Key がどの位置の Value に対応しているかを伝えることができます。また、単一のファイルのサイズを制限することでキャッシュのパフォーマンスを向上させます。たとえば、1 つのキーが 16 バイトで、1 つのポインタが 16 バイトの場合、64M のファイルに 200 万行以上の KV を保存できます。
書き込みの増加を縮小#
Value の一部が LSM🌲に保存されるサイズが小さくなるため、Value の部分は書き込みの増加を引き起こさず、Key が乱雑に移動することもありません。
Value のサイズが 1kb であり、16 バイトがキーのサイズである場合、書き込みの増加は次のようになります。
(10*16 + 1024)/(16 + 1024) ~= 1.14
つまり、わずかに増加するだけです🤏
これはパフォーマンスに反映され、書き込み速度は RocksDB の N 倍になります。N は Value がディスクに書き込まれる時間に依存します。
読み込みの増加を縮小#
Value が LSM にないため、LSM のサイズが大幅に縮小され、レベルの数が減少することを意味します。その結果、メモリに格納される部分が増えます。ベンチマークによると、RocksDB は値が 1kb であり、2200 万行のデータがある場合、LSM ツリーに 72GB のデータセットを使用しますが、Badger はキーとオフセットのみを保存するため、わずか 1.7G のデータセットで済みます。すべてがメモリに格納されています...
そのため、読み取り速度は RocksDB の 3.5 倍になります...
イテレーション速度... それは 3.5*N です。
具体的なベンチマークは次のようになります#
文字数の制限があるため#
次回予告...Agate のより先進的な機能について、老迟さんにインタビューするかもしれません。
Translation: