序文
前回の記事「ハッシュ・インデックスからLSMツリーへ」では、高い書き込み性能を持つキー・バリュー・データベースを、追記型ログのデータ構造で実装しました。追記型ログが高い書き込み性能を持つのは、主にディスクへのシーケンシャルな書き込みによるものです。ディスクへの書き込みは常に遅いという印象があるため、これはディスクに対する認識と反するかもしれません。正確には、書き込み中に複数のアドレス指定が行われる可能性があるため、遅くなるのはランダムに書き込まれるディスクのはずです。ディスクをシーケンシャルに書き込むだけであれば、以下のACMのレポートにあるように、性能は非常に高く、ディスクをシーケンシャルに書き込むことは、メモリをランダムに書き込むことにさえ勝っています！
例えば、Kafkaは高性能なメッセージキューで、ディスクのシーケンシャルな書き込み性能を極限まで活用しています。プロデューサとコンシューマの速度が同等であれば、オペレーティングシステムのページキャッシュレベルでメッセージを配信することさえできます。ですから、ディスクへの書き込みが遅いとはもう思わないでください！
アペンド・オンリー・ログはデータの書き込み性能を劇的に向上させますが、それに伴いデータの読み込み性能は非常に低くなります。これに対処するため、ハッシュ・インデックスを使用して最適化を行いましたが、最適化の結果は非常に大きなものでした。しかし、ハッシュ・インデックスには2つの明らかな限界があります。キーの数が多い場合、ハッシュ・インデックスを維持することはメモリに大きな負担をかけることになります。この記事で紹介する主人公、LSMツリーの登場です。
LSMツリーはデータ構造ではなく、正確にはストレージモデルであり、MemTable、Immutable MemTable、SSTable、その他のパーツで構成されています。また、追記型ログを利用することで、書き込み性能を劇的に向上させます。同時に、キーの格納が順序付けされているため読み取り性能も高く、前述のHashインデックスの2つの制限も克服しています。以下、この記事では、LSMツリーがどのようにこれを行うかをステップバイステップで分析します。
エスティーエーブル
最も単純なデータベースの例では、データが順不同に格納されているため、キーの値を読み取る際に、アルゴリズム複雑度O(n)でデータファイル全体を横断する必要があります。読み取り性能を向上させるためには、すべてのキーのハッシュインデックスをメモリに保持する必要がありました。
キー順のストレージの場合、ハッシュインデックスを使用しなくても、キーの場所をすばやく見つけるためにバイナリルックアップを使用することができますので、また、良好なクエリの効率を得ることができ、アルゴリズムの複雑さはO（logn）です。
SSTableはLSMツリーの最も基本的なストレージ構造の1つで、ディスク上に格納され、データはキーでソートされます。データをキーでソートしておくことの利点は、キー値をO(logn)時間で素早く見つけることができることです。しかし、すべてのデータが1つのSSTableに格納されている場合、データ量が多くなるとクエリの効率が低下します。そのため、LSMツリーは通常、複数のSSTableに格納されたデータを散在させ、それぞれのSSTableの最大キーと最小キーを記録します。
// SSTableデータはSSTableに読み出し専用で保存され、書き込み専用ではない。
public class SSTable {
...
// データ保存パス
private final LogFile logFile;
// このSStableに格納されるアイテムの最小数は以下の通りである。Key
private String minKey;
// このSStableに格納されるアイテムの最大数は以下の通りである。Key
private String maxKey;
// バイナリ・ルックアップを使用してキー値を取得する
public String get(String key) {
// step1まず、SSTableの範囲が
if (key.compareTo(minKey) < 0 || key.compareTo(maxKey) > 0) {
return "";
}
// step2バイナリ検索
long start = 0;
long end = logFile.size();
while (start < end) {
long mid = start + (end - start) / 2;
// まず、先頭のレコードを見つけるoffset
long startOffset = logFile.startOffsetOf(mid);
String record = logFile.read(startOffset);
String midKey = Util.keyOf(record);
if (key.compareTo(midKey) == 0) {
return Util.valueOf(record);
} else if (key.compareTo(midKey) < 0) {
end = mid;
} else {
// 開始オフセットへのRECORDの検索は、次のようになる。mid == start
if (mid == start) {
break;
}
start = mid;
}
}
return "";
}
...
}
ここでは、SSTableの比較的単純な実装では、実際には、SSTableの実装上のLSMのツリストレージエンジンの様々な異なっている、LevelDBなどのSSTableの2つの主要なブロックに分割されます、データ格納領域は、キー：値のデータを格納するために、データ管理領域は、インデックスやその他のデータを格納します。
ディスク上のデータ順序を維持する最も一般的なストレージ構造はB/B+ツリーです。 SSTableに同様のストレージ構造を使用した場合、まず問題となるのは、すべての書き込みがディスクへのランダム書き込みを伴うため、データのパフォーマンスに影響を与え、明らかにLSMツリーの本来の意図に反するということです。SSTableの順序性と書き込み性能の両方を考慮するために、LSMツリーではMemTableというコンポーネントを採用しています。
メムテーブル
MemTableは、正確にLSMは、メモリ内の順序データ構造を維持する方法を確認するために次のとおりです。次に、LSMがMemtableを使用して、SSTableの順序付き行と書き込みパフォーマンスの両方を実現する方法を説明します：
1、書き込み要求が来たら、まずMemtableにレコードを書き込みます。そうすることで、メモリ上でレコードが順番に並んでいることを確認でき、書き込み性能が高くなります。
2、Memtableのサイズがある閾値に達すると、MemTableはImmutable MemTableに変換され、書き込み要求を受け取るために新しいMemTableが作成されます。
ハッシュインデックスからLSMツリーへ」のセグメントファイルの仕組みと同様に、ある時点で書き込み要求を受け取るのは、現在のセグメントファイルだけです。
3は、バックグラウンドタスクを介して、定期的にSSTableにImmutable MemTableのデータをブラシ、Immutable MemTable自体が順序付けされているので、それはSSTableのデータが順序付けされていることを確認することができますし、データがSSTableファイルに書き込まれる完全にシーケンシャル書き込み、順序と書き込み性能のバランスを達成するためです。
4、読み取り要求が来たときに、MemTable -> Immutable MemTable -> SSTableの順序を見つける、検索してから戻り、それ以外の場合は、ステップバイステップで実行します。
Memtableは通常、基礎となるジャンプテーブルを実装するために使用され、AVLと赤黒木に比べて、データの挿入でジャンプテーブルは、ツリーノードの頻繁な調整操作を回避することができますので、書き込み効率が非常に高く、実装も少し簡単です。
// LSMSSTableはハッシュ・インデックスを必要とせず、読み出し性能に優れ、インターバル・クエリーをサポートする。MemTable
public class MemTable {
// のジャンプテーブルの実装に基づくと、以下のようになる。key-value
private final ConcurrentSkipListMap<String, String> cache;
// 保存データの現在のサイズ
private AtomicInteger size;
...
// key
public String get(String key) {
if (!cache.containsKey(key)) {
return "";
}
return cache.get(key);
}
// key:valueこれを行うには、以下の手順でMemtableの現在のサイズを更新することができる。
public void add(String key, String value) {
cache.put(key, value);
size.addAndGet(key.length() + value.length());
}
// 現在のMemtableのサイズを返す
// SSTableは閾値に達した後の判定に使用される。Immutable MemTable
public int size() {
return this.size.get();
}
// 閾値に達した後、ダンプしてSSTable
public void compact2Sst(SSTable sst) {
cache.forEach(sst::add);
}
...
}
LsmKvDb
LSMツリーをストレージエンジンとして使用するデータベースは、通常、クエリとその後のコンパクト操作を容易にするために、SSTableを階層的に管理します。本論文でも、SSTableの階層管理のアーキテクチャを用いてLsmKvDbを実装します。
まずレベルが抽象化され、それぞれが複数のSSTableで構成されます：
// SSTableとMemableで構成されるLSMのレイヤーは抽象化されている。
public class Level {
private final List<SSTable> ssts;
...
public void add(SSTable sst) {
ssts.add(sst);
}
// 在当前level总查找key对应的value, 从老到新遍历所有SSTable
public String find(String key) {
for (int i = ssts.size() - 1; i >= 0; i--) {
String value = ssts.get(i).get(key);
if (!value.equals("")) {
return value;
}
}
return "";
}
// sstカレント・レベルでのコンパクトな操作
public void compactWith(SSTable sst) {...}
// 与えられたSSTコレクションで、現在のレベルを持つコンパクト操作
public void compactWith(List<SSTable> ssts) {...}
}
LsmKvDbの実装コードは以下の通りで、MemTableにデータを書き込み、閾値に達したらImmutable MemTableにデータを書き込みます。 Immutable MemTableとMemTableは同じデータ構造ですが、唯一の違いは、前者は読み込みのみで書き込みはできませんが、後者は読み込みと書き込みの両方ができます。
/**
* LSMツリーに基づくkey-value数据库, 采用分层架构
* MemTable -> Immutable MemTable -> Level0 -> Level1 -> Level2
*/
public class LsmKvDb implements KvDb {
...
// SSTableが格納されるディレクトリ
private final String sstDir;
// 現在の書き込みMemTable
private MemTable memTable;
// MemTableへのダンプが閾値サイズに達した後、LSMツリーはディスクに保存される。immutableMts
private final List<MemTable> immutableMts;
// バックグラウンドでは、immutableMtsのMemTableをLevel0に定期的にフラッシュする。
private final Level level0;
// バックエンドは、Level0のSSTableをLevel1のSSTableに定期的にマージする。
private final Level level1;
// Level1のSSTableの数がある閾値に達すると、最も古いSSTableが選択され、Level2のSSTableとマージされる。
private final Level level2;
...
@Override
public String get(String key) {
// step1: MemTableからの読み込み
String value = memTable.get(key);
if (!value.equals("")) {
return value;
}
// step2: 从Immutable MemTable中读取，从新到老
for (int i = immutableMts.size() - 1; i >= 0; i--) {
value = immutableMts.get(i).get(key);
if (!value.equals("")) {
return value;
}
}
// step3: レベル0からの読み込み
value = level0.find(key);
if (!value.equals("")) {
return value;
}
// step4: レベル1からの読み込み
...
// step5: レベル2からの読み込み
...
return "";
}
@Override
public void set(String key, String value) {
memTable.add(key, value);
// MemTableのサイズが閾値に達し、LSMツリーに変換されると、LSMツリーは閾値に達する。Immutable MemTable
if (memTable.size() > MEMTABLE_MAX_SIZE) {
synchronized (this) {
immutableMts.add(memTable);
memTable = MemTable.create();
}
}
}
...
}
圧縮
前回の記事「ハッシュ・インデックスからLSMツリーへ」では、データ・ストレージ・ファイルの際限ない増大を避けるために、上書きまたは削除されたレコードを削除することを目的としたコンパクション・メカニズムについて説明しました。LSMツリーにおいても、このメカニズムは適用可能です。データの追加、更新、削除が継続的に行われるため、キーの重複や削除されたキーの間にいくつかのSSTableが存在する必要があります。コンパクションによって、複数のSSTableを1つに統合することができ、ディスク容量を節約することができます。
前回の記事では、セグメントファイルに対するCOMPACT操作はHashインデックスに大きく依存 していました。このインデックスはすべてのキーをカバーしているので、新しいセグメントファイルのハッシュインデックスによって、そのキーが処理済みかどうかを判断するのは簡単です。しかし、SSTableの場合は、すべてのキーをカバーするハッシュインデックスが存在しないため、どのようにCOMPACTを行えば効率的なのでしょうか？
SSTableの順序付けされた性質のおかげで、COMPACT操作を実行するためにサブサンプション・ソート・アルゴリズムを適用することができます！
マイナー・コンパクト
各Immutable MemTableのデータは直接SSTableにダンプされ、マージ処理は行われないため、Level0の各SSTable間でキーが重複する可能性があります。
メジャー・コンパクト
メジャー・コンパクトとは、レベルnのSSTableをレベルn+1にマージすることです。
1.Level0内の最も古いSSTable sst0を選択し、sst0のキーと重複するLevel0内のすべてのSSTable sst0...nを見つけます。.n.
2.Level1で、SSTable sst0...nとキーが重複しているSSTableをすべて選択します。.nで、SSTable sst'0....mとキーが重複しているものをすべて選択します。.m.
3.sst0.....n と sst'0.....mは、多重マージソートアルゴリズムを用いてマージされ、新しい sst''0.....kとなり、Level1 に格納されます。
4.sst0....を削除します。.n と sst'0.....m.
Level0と異なり、Level1とLevel2のSSTableにはキーの重複がないため、Level1→Level2のマージは若干容易になります。
1.Level1で最も古いSSTable sst0を選択します。
2.レベル2で、sst0..mとキーが重複するSSTable sst'0...mをすべて選択します。.m.
3. sst0 と sst'0.....m が多重マージソートアルゴリズムでマージされ、新しい sst''0.....kとなり、Level2に格納されます。
4.sst0とsst'0を削除.....m.
フルコンパクト
full compact は、Level0、Level1、Level2 のすべての SSTable に対する、多重化サブサンプション・ソート・アルゴリズムを使用したコンパクト操作です。
通常、フルコンパクトは時間がかかるので、トラフィックの少ない瞬間に行います。
LSMツリーの最適化
SSTable用ブロックの導入
これまでは、SSTable 内のキーを検索する場合、まず min key と max key から SSTable の範囲に属するかどうかを判断し、属する場合はバイナリ・ルックアップで SSTable を検索していました。LsmKvDb でバイナリ検索が機能する理由は、SSTable が単純な実装であるためです。この場合、バイナリ・ルックアップの実装はより複雑になり、効率が高くなりすぎ ます。
一般的な最適化手法は、レコードを一定のサイズに従ってSSTableのブロックに整理し、ブロック単位で圧縮することです。あるキーが属するブロックを素早く見つけるには、SSTable内の各ブロックの開始キーのオフセットをメモリに保持する必要があります。
1、ブロックに属するキーを見つけるためのインデックスによると。
2.ブロックをメモリにロードして展開します。
3.メモリ上のデータにはバイナリ・ルックアップを使用します。
ブロックのサイズを設計する際には、ディスクの空間的局所性の原理を利用し、システムが1回のディスクI/Oでブロック全体をメモリにロードできるようにする必要があります。
SSTable用ブルーム・フィルターの導入
実際、ターゲット・キーが特定の SSTable のキー範囲に属する場合、そのキーがその SSTable に存在するとは限りません。しかし、これまでのところ、ターゲット・キーが特定のSSTableの範囲内にある限り、LsmKvDbはルックアップ処理を実行します。システム内のSSTableの数が増えると、ルックアップの効率は低下します。
一般的な最適化アプローチは、SSTableにブルーム・フィルターを導入することです。
ブルーム・フィルターは、メモリ上に保持されたデータ構造で、「何かが存在してはならない、あるいは存在する可能性がある」ことを教えてくれるものです。これは、バイナリ・ビットの非常に長い配列と、一連のハッシュ関数で構成されています。バイナリビット配列の初期値はすべて0ですが、コレクションに要素が追加されると、その要素は一連のHash関数のマップ値、ビット配列のオフセット処分のすべての値が1になります。 要素がコレクションに存在するかどうかを判断する必要がある場合は、単純に要素の値が配列内のHash値であったかどうかを判断します。1であれば、それは存在する可能性があり、この場合は、誤った判断を持っている可能性があります。
ブルーム・フィルタを使用すると、ターゲット・キーがSSTableに存在しないかどうかを迅速に判断できるため、読み取り性能が向上します。
GoogleのGuavaライブラリはBloomFilterの実装を提供しており、必要に応じて偽陽性率を設定することができます。
概要
LSMツリーは主にMemTable、Immutable MemTable、SSTableから構成されます、SSTableから構成され、MemTableとImmutable MemTableはメモリ上に保持され、SSTableはディスクに格納されます。SSTableの順序付けされた性質により、LSMツリーはハッシュインデックスなしで良好な読み込み性能を持ち、インターバルクエリをサポートします。書き込み性能。
この一連の記事は、単純なキーバリューデータベースから始まり、ハッシュインデックス、LSMツリー、ブルームフィルタとその最適化の他の技術的な手段を介してステップバイステップで、そこから様々な技術的なポイントの実装の原理の詳細な分析。しかし、データベースのインデックス技術は、はるかにそのような最も一般的に使用されるB / B +ツリーなど、また、非常に価値のある詳細な研究であり、深くそれを分析する機会を持つことです。
