leveldb - LevelDB が 2 つ以上のレベルを必要とするのはなぜですか?

Question

2 つのレベル (レベル 0 とレベル 1) だけで問題ないと思いますが、なぜ LevelDB はレベル 2、レベル 3 などを必要とするのですか?

Answer 1

LevelDB に関するいくつかの記事の方向性と、その基礎となるストレージ構造を紹介します。

そのため、LevelDB のドキュメントで は、レベル間のマージについて説明しています。

これらのマージには、大量の読み取りと書き込みのみを使用して新しい更新を若いレベルから最大のレベルに徐々に移行する効果があります (つまり、高価なシークを最小限に抑えます)。

LevelDB の構造はLog Structured Merge Treesに似ています。この論文では、分析に興味がある場合は、さまざまなレベルについて説明しています。数学を理解できれば、データ構造を理解するための最善の策と思われます。

levelDB の分析を読みやすくすると、データストアと LSM ツリーとの関係について説明されますが、レベルに関する質問に関しては、次のようになります。

最後に、何百ものオンディスク SSTable を持つことも良い考えではありません。そのため、定期的にオンディスク SSTable をマージするプロセスを実行します。

おそらく、LevelDB のドキュメントが最良の答えを提供します: (LevelDB はディスク上の (シークが遅い) データ ストレージであるため、書き込みと読み取りのサイズを最大化します)。

幸運を！

Answer 2

レベルを簡単かつ迅速にマージすることが主な理由だと思います。

Leveldb では、level-(i+1) はおよそ レベル i と比較して 10 倍のデータ。これは、データベースにキー x1 から x2 の間に 1000 レコードがある場合、その範囲内で最も頻繁にアクセスされる 10 個がレベル 1 にあり、同じ範囲内の 100 個がレベル 2 で残りはレベル 3 です (これは正確ではありませんが、レベルの直感的なアイデアを提供するためのものです)。この設定では、レベル i のファイルをマージするには、レベル (i+1) で最大 10 個のファイルを調べる必要があり、すべてをメモリに取り込み、迅速なマージを実行して書き戻すことができます。これらの結果、圧縮/マージ操作ごとに比較的小さなデータのチャンクが読み取られます。

一方、レベルが 2 つしかない場合、1 つのレベル 0 ファイルのキー範囲がレベル 1 の数千のファイルと一致する可能性があり、それらすべてをマージ用に開く必要があり、かなり遅くなります。ここでの重要な前提は、固定サイズのファイル (たとえば 2MB) があることです。レベル 1 の可変長ファイルを使用しても、あなたのアイデアは機能する可能性があり、HBase や Cassandra などのシステムでその変形が使用されていると思います。

ここで、多くのレベルでのルックアップの遅延が懸念される場合、これもマルチレベルのキャッシュ構造のようなもので、最近書き込まれたデータは、典型的な参照の局所性を助けるために、より高いレベルにあります。

Answer 3

レベル 0 はメモリ内のデータで、他のレベルはディスク データです。重要な部分は、レベル内のデータがソートされていることです。level1 が 3 つの 2Mb ファイルで構成されている場合、file1 のキーは 0..50 (ソート済み) で、file2 は 150..200、file3 は 300..400 (例として) です。そのため、メモリ レベルがいっぱいになると、そのデータを最も効率的な方法でディスクに挿入する必要があります。これはシーケンシャル書き込みです (できるだけ少ないディスク シークを使用します)。メモリに 60 ～ 120 のキーがあると想像してみてください。クールです。それらをファイルとして順次書き込み、レベル 1 のファイル 2 にします。非常に効率的です！しかし、ここで、level1 が level0 よりもはるかに大きいと想像してください (level0 はメモリであるため、これは妥当です)。この場合、レベル 1 に多くのファイルがあります。そして今、メモリ内のキー (60 ～ 120) は、level1 のキー範囲が非常に細かいため、多くのファイルに属しています。level0 を level1 とマージするには、多くのファイルを読み取り、多くのランダム シークを行い、メモリ内に新しいファイルを作成して書き込む必要があります。したがって、ここで多くのレベルのアイデアが始まります。多くのレイヤーがあり、それぞれが前のレイヤー (x10) よりも多少大きくなりますが、それほど大きくはないため、i-1 から i 番目のレイヤーにデータを移行する必要がある場合は、最小量のファイルを読み取る必要がある可能性が高くなります。

現在、データは変更される可能性があるため、それを上位のより高価なレイヤーに伝播する必要がない可能性があるため (変更または削除される可能性があります)、コストのかかるマージを完全に回避します。最後のレベルに到達するデータは、統計的に変更される可能性が最も低いため、最後のレイヤーとのマージに最も費用がかかるデータに最適です。