Fastest Indiana：Trieに基づくキー/値コンテナ

「私は何もしていないように見えるかもしれません。 しかし、実際には、携帯電話のレベルでは、私は非常に忙しいです。」

不明な著者

21世紀には、建築プログラムはますますレゴコンストラクターに似てきました。 このアプローチは、多くの「キューブ」が私たちの前に発明されたことを意味します。 実際、それらの基本的な性質は、長年にわたる改善のリソースが実質的に使い果たされており、私たちが使用できるものだけを使用していることを偽って示唆しています。 しかし、奇妙なことに、生物学との類推により、基本的な「セル」は、最も複雑で熟考されたアルゴリズムを隠すことがあり、ここですべての最も興味深いバトルが終了します。 この意味で、プログラマーは、業界の汎用性の点で医師を連想させます。 医師、獣医、外科医がおり、数行のコードに数か月の作業を費やすことができる人がいます。

「Googleでは、私が言うにはサーバーパークでは、すべてのCPUの1％がハッシュテーブル内の計算に関与しています。 私が話すように、ハッシュテーブルはすべてのサーバーRAMの8％以上を占めます。 これはC ++に当てはまることです。Javaの状況はわかりません」

Matt Kulukundis、CppCon 2017

かつて、ジャンプによってコンテナ内のキー値自体をエンコードする方法に沿って、1つのメモリに2つのスパースページを配置する方法について興味深いアイデアが思いつきました。 このアイデアは非常に興味深く、新鮮で、その検証には数十行のコードしかかからなかったので、次の夜、好奇心を克服して、この方法で圧縮できるメモリページの量を見つけました。 これはほんの始まりであり、時間が経つにつれて、すべてが膨大な数の仮説、測定、バージョンのテストに変わったと言わなければなりません。 現在のバージョンでは、元の「理想的な」モデルの概要を見分けることは非常に困難です。 このようなタスクでは、通常のエンジニアリングタスクと同様に、バランスを見つけることが非常に重要です。 自動機械のシャッターのように、汚れ、水、熱の中で簡単に普遍的なメカニズムを見つけることは困難です。

「シンプルにすることは、難しいことよりも何倍も難しいことがあります。」

ミハイル・カラシニコフ

Hestablitzよりも速く実行されるTrieを作成するというアイデアは新しいものではありません。 2001年、ダグラスバスキンスはJudy Arrayの動作原理を説明しました。 このアイデアは非常に興味深いものであるため、Hewlett Packardはこのプロジェクトにエンジニアグループ全体を割り当てました。 最適化されたTrieは、小さなオペレーティングシステムに似ています。 メモリマネージャの独自の実装、ノードの圧縮およびバランシングアルゴリズムの全リスト、コンテナ内のマイクロワールドを管理するための独自の小さなエコシステムがあります。 実装が複雑であるため、パブリックドメインにはそのようなプロジェクトはほとんどありません。 オープンリポジトリでは、 Treeの実装のほとんどのほとんどに数百行のコードしかありません（HPのJudyArrayは約20K、 HArrayは約8K LOCです）。 本質的に学術的である可能性が高い、またはテキストを操作するための特定の問題を解決するために作成された実装。 インタビュー中にTrieについて尋ねられることはほとんどありません;そのようなキー/値コンテナは、一般的なプログラミング言語の標準ライブラリには含まれていません。 そして、私は完全に無駄であると言わなければなりません。 すでに最初の調査で、最適化されたTrieはハッシュテーブルよりも高速に動作し、バイナリツリーよりも機能が豊富であることを理解しています。



情報検索は、コンピューター技術の基本的なタスクの1つです。 実際、コンピューターが情報を読み取って保存する方法を教えた直後に、効果的な検索が必要でした。 常に、クイック検索を構成するための3つの基本概念のみが提案されました。 バイナリツリー-検索のキーを厳密に並べ替える必要があるコンテナを整理する方法。 ハッシュテーブル-ハッシュ関数でキーを処理することでアドレス値を取得します。 そしてトライ-キー自体が値へのパスをエンコードします。 文献では、これらのアルゴリズムがどのように機能するかを詳細に見つけることができます。 たとえば、これらのアプローチが互いにどのように異なるかについてのグラフィカルな説明があります。

しかし、ユニバーサルキー/バリューコンテナの構築という観点から、Trieがより興味深い理由についてはほとんど語られていません。



ハッシュテーブルこの構造は、非常に高速なキー検索用に設計されており、実際には、他のすべてを犠牲にします。 最前線にはハッシュ関数があり、その品質にはほとんどすべてが依存しています。 ただし、優れたハッシュ関数を選択できます。これにより、テストデータではほぼ均一な分布が得られますが、状況を100％で制御することはできません。 おそらく実際の作業では、新しいデータに対して、最悪のケースに近いケースでハッシュ関数が劣化します。 この場合、超高速検索は、フルスキャンとO（1）ではなくO（N）のようなものに変わります。 もう1つの問題は、データが多いほど衝突が増えることです。 大量のデータでは、衝突は雪だるま式に成長し、ある時点で、ハッシュテーブル全体を全体として再構築する必要があります。 このイベントはStop Worldイベントと呼ばれ、呼び出し元コードの遅延が近いことを保証できないことを意味します。 また、大量のデータは非線形の過剰なメモリ消費を伴い、ハッシュテーブル内の多くのセルは空になり、キー自体は非圧縮形式でバケットに格納されます。 コンテナ内の範囲またはキーパターンで検索する効果的な方法はありません。 キーが最後の1ビットだけ異なる場合でも、同じバケット内の構造内でキーが近くなる確率はゼロになる傾向があります。 プロセッサの場合、キー自体が互いに類似している何らかの種類の自然なデータセット（URL、FilePath、Wordsなど）を使用する場合、これは多くの場合、キャッシュミスを意味し、パフォーマンスも向上しません。 ただし、理想的なハッシュ関数を使用している場合でも、コンテナ内のキーはわずかであり、衝突はまったくありません。キー自体を挿入および検索すると、少なくとも2回スキャンされます。 1回目はハッシュ関数を通過し、2回目はアドレスに到達したときに、見つかったキーが実際に必要なものであることを再確認します。 トライはこれらの欠点のほとんどすべてを奪われていますが、それについては以下で詳しく説明します。



バイナリツリー特定のゴールドスタンダード、特にデータベースに関しては、バイナリ検索のさまざまなバリエーションがあります。 ほとんどの場合、2つの変更があります。 Red Black Tree-ディスクで追加の作業が必要な場合、効率的なツリーバランシングとB +変更によるバイナリ検索。 バイナリ検索には、ハッシュテーブルの多くの欠点がありません。 ハッシュ関数は必要ありません。メモリ消費はほぼ線形で、予測可能な時間、通常O（log（n））で挿入および検索します。 キーの範囲で検索し、データの並べ替えの種類を設定する機能。 しかし、検索速度自体は非常に遅いです。 約100万のキーを持つコンテナでは、キーは約20回のシーク時間で見つかります。 同時に、衝突のない理想的なハッシュテーブルでキーを2回スキャンすることについて話した場合、ここでキーを互いに不均等に比較する必要がある各段階で何十回もキーをスキャンできます。 一般に、バイナリツリーは本当にうまく機能しますが、残念ながら、フラットメモリモデルでは機能しません。 新しいキーを挿入する必要があるたびに、ソート順序を保持するために中央のどこかに挿入します。 このため、バランスアルゴリズムは非常に複雑です。これは、挿入ごとに古いデータが移動するのを避けるために、スペースが拡張されたままになるためです。



ここでは、「ダークホース」に戻ります。最初に言うと、Trieは常にキーを1回スキャンします。 本質的に、これは、少なくとも理論的には、Treeがハッシュテーブルよりも高速に動作し、さらにバイナリツリーよりも高速に動作できることを意味します。 ここからもう1つの興味深い特性が得られます。キーが長いほど、ハッシュテーブルとTrieの速度の差が大きくなり、後者が優先されます。 さらに、この構造はプロセッサキャッシュと非常に友好的です。これは、第一に、同様のキーがメモリの近くに配置されているためですL1 / L2プロセッサキャッシュ内。 キーがURLなどの類似した性質のものである場合、構造はプレフィックス圧縮により多くのメモリを節約します。 このようなキーは、範囲全体でより効率的にスキャンされます。 バイナリツリーは各キーを最初から最後まで読み取りますが、Trieはキーの「テール」のみをスキャンします。 Trieは、バイナリツリーとは異なり、一定のバランスを必要とせず、ハッシュテーブルとは異なり、大量のデータでツリーを完全に再構築する必要がないため、フラットメモリモデルで明らかに動作します。 Stop Worldイベントはありません。



欠点は何ですか？ 第一-パトリシアのようなノード圧縮のさまざまな方法にもかかわらず、この構造は長いジャンプが非常に好きです。 シーク時間が非常に高価な操作であるHDDにデータを保存する場合、ハッシュテーブルははるかに高速に動作します。 確かに、キーを2回以上スキャンするという事実にもかかわらず、シークは1回しかありません-目的のバケットに自分自身を配置しますが、Trieは、バイナリではなく平均して、クラシック）ツリー。 また、サブツリーをスキャンするときに多くのジャンプがあるので、バイナリツリーの範囲でランダムな性質のキーをスキャンする方がはるかに効果的です。 別の欠点は、このような構造の実装の複雑さとカスタムキーの並べ替えを指定できないことです。ただし、これはすべての実装に当てはまるわけではありません。たとえば、 HArrayでは、カスタムキーの並べ替えを指定できます。



JSON前の例では、速度、メモリ、キーの範囲ごとのスキャン機能などのパラメーターによって、さまざまなコンテナーの作業の機能を比較しました。 ほとんどのアプリケーションでは、あるコンテナ実装を別のコンテナ実装に置き換えることは、「ビット最適化」を意味します。 負荷の高いプロジェクトでは、もちろん大幅に向上します。 さらに、負荷が高いということは、多くのクライアント要求がある大企業のサーバーだけではありません。 たとえば、データアーカイブ、グラフィックレンダリング、コンテンツインデックス-これらはすべて、通常のキー/値コンテナーが1秒あたり数百万の要求の負荷の下で「エンジン」内で動作できる同じタスクです。 そのようなシナリオでは、速度は決して不必要ではなく、条件付きで最適化を行うと、16 GBのコンテンツが4時間ではなく2時間だけインデックスに登録されるという2倍の意味があります。 キー/値コンテナの既存の実装を使用できますが、その作業の詳細についてはあまり考えません。 ただし、Trie以外の何かを使用することが完全に非実用的なタスクのクラスがあります。 たとえば、サフィックスツリーがどのように機能するかなど、多くのテキスト処理タスクについて話します。 また、例として、Radix TreeはLinuxカーネル内で成功したアプリケーションを発見し、他のものに置き換えることはほとんどできませんでした。 これらの例はすべて、さまざまな文献で詳しく説明されているため、詳細については説明しません。 代わりに、別の興味深い例を示します。 一般に、アプリケーションアーキテクチャの均一性を実現することは非常に重要です。 「パターン」のように、正しく選択された抽象化、テンプレートが他のすべてに適していることがよくあります。 したがって、JSONは、Trie内で同じ自然で直感的な方法で保存できる、自然で直感的な形式です。 どうやってやるの？ 簡単なことですが、JSONをキーにスライスするだけです。Keyは属性とその値へのパスで、Valueはドキュメント番号です。 したがって、JSONドキュメントの途中で属性を挿入、更新、または削除しても、完全に書き換えられるわけではなく、コンテナ内のキーを挿入、更新、または削除するだけです。 属性の検索または属性値の範囲の検索は、キー全体の検索またはTrie内のサブツリーのスキャンのみを意味し、ドキュメント全体をデシリアライズしません。 これらの操作はすべて非常に高速です。 Key \ Valueコンテナからキーを取得するには、通常100ナノ秒未満かかります。 さらに、Trieは逆インデックスを使用してJSONを自然に圧縮します。 実際、そのようなドキュメントが別々のファイルとして保存されている場合、それらの属性は複製されます。 ただし、Trieに追加された場合、Trieでは、コンテナに追加されたドキュメントの数に関係なく、すべての属性が一度表示されます。 このアプローチは、列データウェアハウスで使用されているアプローチに似ていますが、今回はドキュメント指向のデータベースで使用されています。 一般に、このトピックは別の記事に値します。

「実践のない理論は死んで不毛であり、理論のない実践は役に立たず悲惨です」

P.L.チェビシェフ

最近、 HArrayプロジェクトがオープンアクセスでネットワークに実装されました。これは、多くの最適化を備えたTrieアルゴリズムを実装しています。 実装は非常に複雑であることが判明しましたが、私の意見では、非常に効果的であり、 ベンチマークで確認されています 。 このオプションは最終的なものではなく、改善のためのアイデアがたくさんあります。 さらに、古いバージョンは1.5倍速く動作しましたが、新しい機能を追加すると大幅に遅くなり、これも整理する価値があります。



基本的な機能に加えて、公正な削除が実装されています。 正直なところ、これはキーが「無効化」されず、段階的に正直に解体され、徐々にメモリが解放されるときです。 キーの大規模な追加および削除のシナリオでは、構造は「非廃棄物生成」モードで動作し、古い「デッド」キーの一部が新しいキーの構築に使用されます。 削除の数が新しいキーの追加の数を超える場合、ある時点で、構造はオペレーティングシステムに「余分な」メモリページを提供し、使用中のページを最適化します。 あらゆる種類のツリーウォーク、キーパターンによる検索、ディスクへの保存、コンテナ内のキーのソートをオーバーライドする機能、およびその他の機能も実装されています。