LemonHX

最近 PingCAP に入社しましたが、自分の仕事について全く理解していないため、データベースとストレージに関連する知識を補完する必要がありました。しかし、私にとっては全くわからないことは悪いことではないと思います。まず第一に、成長の余地が非常に大きいことです。第二に、問題を見る視点が異なるため、新しいアイデアが生まれる可能性があります。

さて、本題に入りましょう。今日はこれまでの浅い技術的な「蓄積」を活かして、LSM🌲について簡単に話してみます。

いつからか覚えていませんが、ある会社が Big Table を作り、それに関連する論文を使用しました。この論文では、B🌲を使用せずに書き込み効率が読み取り効率よりも高いという新しいアプローチが提案されました。このデータ構造は MySQL などの伝統的なデータベースを凌駕していましたが、残念ながら Big Table はクローズドソースでした。しかし、その後すぐに、オリジナルの著者がこのアルゴリズムに基づいて作成したシングルノードのオープンソースデータベースLevelDBが公開され、エコシステムが一気に拡大しました。さまざまな分散ストレージシステムが追随しました。FaceBook がRocksDB（私が現在担当しているプロジェクトで、私の実力は本当に低いです）を作成したことで、新世代の分散データベースのストレージエンジンが確立されました。私たちの TiKV もこれをベースにしています。さて、今日はこのデータ構造が具体的に何をしているのかを見てみましょう。

では、この🌲は何をしているのか#

まず、すべての技術の誕生にはその時代の制約があります。現在の時代では、サーバーでは高スループットのランダム読み書きの SSD を使うことはできず、パフォーマンスに影響を与えずに高スループットのランダム読み書きを実現するためのストレージメディアは存在しません。したがって、この時代では大量の順次読み書きの効率がランダム読み書きの効率よりも 20 倍以上高い（実際のデータではないかもしれませんが）ことを考慮して、データの書き込み速度をストレージメディアに加速するために、順次読み書きを使用する必要があります。

そこで、LSM🌲が誕生しました！#

LSM🌲の正式名称は「Log-Structured Merge Tree」です。

要するに、データを書き込む際にログのように書き込むことで、順次書き込みが保証されるということです。
しかし、これには大きな問題があります。ログはリンクリストのようなものであり、インデックス構造がない場合、リンクリストのランダムアクセスの計算量は O (N) になります。これをどうすればいいのでしょうか？この問題は後で読み取り時に解決されます。

前述した 404 社の LevelDB では、LSM🌲は SSTable と組み合わせて使用されます。

SSTable の正式名称は「Sorted-String Table」です。

404 社は次のように説明しています。

SSTableは、キーから値への永続的で順序付けられた不変のマップを提供します。キーと値はいずれも任意のバイト文字列です。

したがって、LevelDB では LSM🌲は、永続的で順序付けられた不変のキーとデータのオフセットを格納するキーバリューストアと組み合わせて使用されます。オフセットと mmap を組み合わせることで、LSM🌲に格納された情報に瞬時にアクセスできます。すごいでしょう！

したがって、LSM🌲の書き込みプロセスは次のようになります。

1. 誰かがデータを書き込むと伝えてくれたら、まずログを記録して書き込み時に裂けるのを防ぎます。
2. このデータをメモリ内の SSTable に書き込みます（データを削除する場合もありますが、ログを記録しているので「彼は死んだ」と書き込むことになります）。同時に、メモリ内のテーブルにも書き込みます。
3. メモリ内のテーブルが一定のサイズになると、新しいテーブルを作成し、古いテーブルは書き込み不可になります。
4. 古いテーブルは適切なタイミングでディスクに書き込まれます。
5. ディスク上の小さなテーブルが増えるにつれて、適切なタイミング（深夜など）でマージが行われ、1 つの大きなテーブルに統合されます。マージの過程では、「彼は死んだ」とマークされたデータが削除されます。これらのテーブルはすべて順序付けられているため、マージのプロセスは単純なオフラインマージソートです。

では、読み取りのプロセスも簡単です。

1. メモリ内のテーブルをチェックします。- すばやい
2. 存在しない場合 - 最近の小さなテーブルをチェックします。
3. まだ存在しない場合 - 最近の大きなテーブルをチェックします。
4. それでも存在しない場合 - これを繰り返します。

では… なぜ読み取りが O (N) の最悪の場合に見えるのでしょうか？

それでは、今日の重要なポイントに入りましょう。ノートブックを取り出してくださいが、テストはありません。

読み取りの最適化#

🔴⚫🌲#

作者は 20 行の Haskell で赤黒木を書けると言っていますが、書けないということはあなたが下手だからです。なので、説明しません。

ハッシュテーブル#

// ここは再帰です
GOTO 0x00;

スキップリスト#

さて、おめでとうございます🎉。ほとんどのストレージエンジンで使用されている最適化、スキップリストに到着しました。

level 2: [11]                [21]                [41]                [70]
level 1: [11]      [14]      [21]      [31]      [41]      [58]      [70]
level 0: [11] [12] [14] [15] [21] [24] [31] [39] [41] [49] [58] [61] [70]

スキップリストは N 個のレベルを持つことができます。
LSM🌲は順序付けられたデータ構造なので、理論的には O (log N) の読み取り速度に近づくことができます。

どのように構築するか... おそらく私のブログを読んでいる子供たちはすでにほぼ書いていると思いますので、大まかに説明します。どれくらいのレベルのスキップリストを生成すると、スペースの浪費と時間の増加が相対的にバランスが取れるかを説明します。

まず、現実のデータベースでは、処理するデータ量が非常に大きいため、2 つのキーごとに 1 つのレベルを作成するなど、非常に単純な方法では構築できません。これにより、大量のスペースが無駄になります。実際には、非常に巧妙な確率戦略を使用します。

コイントス

コインの表裏はちょうど 50% の確率を持つため、厳密にスキップリストの log と一致します。

int このノードは何番目のレベルにキャッシュがあるのですか(){
    var level = 0;
    while ( true ){
        var ランダム数 = random.nextInt();
        if ( ランダム数 % 2 == 0 ) {
            level += 1;
        } else {
            break;
        }
    }
    return level;
}

これにより、公平ではないかもしれませんし、いくつかのアフリカ人ノードが多くアクセスされるがインデックスではない場合もありますが、確率に基づいて比較的安定しています。

次回予告：AgateDB の SSD 最適化と RocksDB を圧倒する方法について、Badger プロジェクトから借りた話をするかもしれません。お楽しみに〜