特定のプロパティを満たす、スペース効率の良いキーと値のマッピング/辞書/データベースを探しています。
- 形式:キーは http(s) URI で表されます。値は可変長バイナリ データになります。
- サイズ: 10 億から 1000 億の一意のキーがあります (平均長は 60 から 70 バイト)。値は最初は数十バイトですが、最終的にはサイズが数十キロバイトになる可能性があります (複数のバージョンを保存することにした場合は、さらに大きくなる可能性があります)。データの合計サイズは、テラバイトまたはペタバイトで測定されます。
- ハードウェア:データは複数のマシンに分散する必要があります。この配布により、特定のドメインからのすべての URI が最終的に同じマシンに配置されるようになります。さらに、マシン上のデータは、アクセス頻度に応じて RAM、SSD、および HDD に分散する必要があります。クラスターにマシンが追加または削除されると、データを移動する必要があります。レプリケーションは最初は必要ありませんが、後で役立つ場合があります。
- アクセス パターン:データへのシーケンシャル アクセスと (やや) ランダム アクセスの両方が必要です。シーケンシャル アクセスは、データを継続的にスキャンする優先度の低いバッチ プロセスから行われます。この場合、スループットはレイテンシーよりもはるかに重要です。理想的には、反復は辞書順 (つまり、辞書順) に進みます。ランダム アクセスは、HTML ページ内の URI にアクセスすることで発生します。これらのほとんどは、ページと同じドメインの URI を指しているため、同じマシン上に配置されると予想されますが、他のものは別のマシン上に配置されます。1 秒あたり最大 100,000 から 1,000,000 のインメモリ ランダム アクセスが必要になると予想しています。データは静的ではありません。読み取りは、書き込みよりも 1 ～ 2 桁多く発生します。
最初は、データは 1 億から 10 億の URL で構成され、URL ごとに数十バイトのデータが含まれます。これは、10 ～ 20 GB の RAM と数 TB のハード ドライブを備えた少数の安価な汎用サーバーでホストされます。この場合、ほとんどのスペースがキーとインデックス情報の格納に使用されます。このため、また予算が限られているため、この情報をできるだけ小さなスペースに保存できるものを探しています。特に、多くの URI で共有されている共通のプレフィックスを活用したいと考えています。このようにして、キーとインデックスを URI の全長よりも少ないスペースに格納できる可能性があると考えています。
私はいくつかの伝統的なデータ構造を見てきました (例: ハッシュ マップ、自己均衡ツリー (例: 赤黒、AVL、B)、試行)。試行 (いくつかのトリックを使用) のみが、インデックスとキーのサイズを縮小する可能性があるようです (他のすべては、インデックスに加えてキーを格納します)。私が考えた最も有望なオプションは、URI をいくつかのコンポーネントに分割することです (たとえば、example.org/a/b/c?d=e&f=g は [example, org, a, b, c, d=e のようになります) 、f=g])。さまざまなコンポーネントはそれぞれ、ファイルシステムのようなツリーのような構造の後続のレベルで子にインデックスを付けます。多くの URI が同じドメインとディレクトリ プレフィックスを共有しているため、これは有益と思われます。
残念ながら、私はさまざまなデータベース製品についてあまり知りません。それらの多くが B ツリーを使用してデータのインデックスを作成していることを理解しています。私が理解しているように、インデックスとキーに必要なスペースは、URL の全長を超えています。
したがって、スペースを節約するために URI の冗長性を利用できるデータ構造またはデータベースについて、誰かが何らかのガイダンスを提供できるかどうかを知りたいです。他のものはそれほど重要ではありませんが、そこの助けもいただければ幸いです。
ありがとう、そして冗長で申し訳ありません;）