私は検索エンジン（仮想プロジェクト）を書いています。 データ保存

ストレージは、おそらくそのようなプロジェクトにとって最も薄い場所です。 解決するタスクに応じて、以下を提供する必要があります。

-データへの迅速なアクセス。

-高速データ更新;

-拡張オプションで十分な機能。

リクエストのフローが大きいキューシステムでは、個々のリクエストの処理時間が短いことがシステムのパフォーマンスの鍵となります。

アクセス中の新しいデータ（ニュースシステム）の出現速度が重要な場合、データベースの更新速度が重要になります。

データ量の増加に伴い、高速アクセスと更新を組み合わせることはほとんど不可能になります。



この状況でユニバーサルDBMSを使用することはほとんど不可能です（この論文に同意しない人は、YandexまたはGoogleにこれを説得することを提案します）。 私が処理したデータの量ははるかに少ない（別のサーバーに展開されたデータは約200ギガバイト）が、他のソリューションを探すことを余儀なくされた。

よく知られているKeyValue NoSQLリポジトリを使用することも常に役立つとは限りません。 Berkelley DBで数億件のレコードを更新しようとしました-特にこの操作を毎日実行する必要があることを考えると、結果は私には不適当でした。

その結果、私は自分で次のカクテルを選びました（以下で説明する作業方法は実際の問題で使用され、その有効性が証明されています）。

-ハッシュキーを使用した順序付き線形リスト。

-バイナリツリー形式のインデックス付きの順序付き線形リスト。

-MemcacheDBのアドインを使用したBerkeley DB。

最初の2つのオプションはメインインデックスを保存するために使用され、最後は-毎日の更新/追加を必要とするレコードの数が数百万を超えず、複数のレコードをすばやく追加、削除、冬にする必要がある場合です。

インデックスは非常に大きいため、すべてのデータをRAMに保存することはできません。

もちろん、最速のオプションはハッシュキーです。 値によって、すぐに結果が得られます。 これらのキーの唯一の欠点は、ストレージに過剰なリソースが必要なことです。 インデックス内のボイドは合計の20％を超えません。 これは、ハッシュが目的の値によって計算されないという事実により実現されますが、実際にはこのレコードに割り当てられたIDです。 時間の経過とともに廃止されるレコードのIDは再利用されます。

残念ながら、そのようなスキームは常に可能とは限りません。 たとえば、場合によっては反対の操作を実行する必要があります-値によって、IDを取得します。 この状況では、ハッシュの使用はリソースを集中的に使用する場合があります。 このような場合、バイナリツリーキーを使用します。 ハッシュの前の主な欠点は、単一のレコードを検索するには、1つではなくlog2ディスクアクセスが必要なことです。 インデックスに5億を超えるレコードが含まれる場合、少なくとも28の読み取り操作。 これはかなり高価です。 もちろん、システムは最も頻繁に要求されるブロックをキャッシュすることで私を助けようとします。 その結果、結果は非常に受け入れられます。 しかし、システムの容赦に頼らないために、私は次のストレージオプションを組み合わせることにしました。 キーの前半はハッシュ形式でメモリに保存されます。 したがって、RAMの消費量が少ない場合、ディスクアクセスの回数が減少します。 また、ディスク上のデータが順序付けられていることを考慮すると、ハッシュによってキーブロックを1回読み取り、メモリ内でそれを操作します。 このオプションはまだ実装されていませんが、バイナリツリーよりも機敏になると思います。



したがって、私は高速データアクセスを提供しようとします。 次に、更新の問題を解決する必要があります。

データの更新プロセスでは、毎日5つのレコードから5億から10億のレコードの4つのテーブルが関係しています。 さらに、約150万件の新しいレコードが入力されます。これらのレコードは、処理中にこれらのテーブルを通過し、ふるいを通過します。

たとえば、操作の1つ。 与えられた：

-辞書[キー、ID]、約7億エントリ。

-ソースデータ[キー、データ]、約7000万件のレコード。

キーはテキスト文字列です。 2番目のテーブルのキーをIDで置き換え、最初のキーを2番目のテーブルから新しいキーに追加する必要があります。 2番目のテーブルの穴は一意ではありません。 リレーショナルDBMSの場合、1つのクエリでは十分ではなく、2番目のテーブルをインポートしてインデックスを作成するためのオーバーヘッドが追加されます（データはテキストファイルで提供されます）。 このプロセス全体がどのくらい実行されるかは想像しにくいです。 小さいボリュームでの作業では、満足のいく結果が得られませんでした。

KeyValueシステムも状況を保存しません。 MemcacheDBには非常においしいベンチマークが配置されていますが、実験で使用されたデータの量から判断すると、このような結果はRAMの制限を超えることなく達成されました。

この問題を解決するには、2つのストリームのマージを使用して、結果を分離します（置換結果を保存しながら、2番目のテーブルを最初のテーブルに流し込みます）。 アルゴリズムは非常に単純で、D。クヌートと彼だけでなく、非常に効果的であると長い間説明されてきました。 さまざまなバリエーションで、私はこのスキームを他の多くの治療で使用しています。

上記の操作（2x2.6GHz Opteron-2218サーバー、16 Gig OP、ディスク-4x73G scsi）を完了するには約50分かかります。

したがって、毎日更新するタスクは許容可能な時間で解決されます。 それが私に完全に合っているとは言えませんが、効率を上げるには、より複雑な開発が必要になるかもしれません。 いくつかの紙のスケッチがありますが、それらは「金属で」予備チェックを必要とするので、それは私が話していることです。