MemC3-並列処理が強化されたコンパクトなMemcache-より愚かなキャッシュとよりスマートなハッシュ

これは、記事「MemC3：Dumber Caching and Smarter Hashingを使用したコンパクトで同時のMemCache」のレビューの翻訳です。 ネットワーク化されたシステムの設計と実装に関する第10回USENIXシンポジウム（NSDI'13）の議事録、 pdfはこちら

Dudes（元Google、Carnegie Mellon Universityの男、Intel Labsの別の男）は、Memcached互換のキャッシュを改良し（実際、memekeshを追加したばかりです）、パフォーマンスの結果が優れています。 ブログ「The morning paper」でのこの記事のレビュー-アルゴリズムの説明などが本当に気に入りました。

斜体-翻訳者としての私のコメント。

MemC3は、通常のmemcashとは異なるハッシュアルゴリズム-楽観的な「カッコウ」ハッシュ（カッコウ）と、これに加えて特別な「CLOCK」プリエンプションアルゴリズムに基づいています。 一緒に接続すると、通常のMemcachedと比較して、メモリの効率的な使用が最大30％向上し、1秒あたりのクエリパフォーマンスが最大3倍になります（Facebookのmemekesに典型的な小さなオブジェクトの読み取りが多い負荷の下で）。

元の記事の最後に、適用された最適化の寄与に関して得られた結果の優れた分析があります。 次のようになります。



スレッドの数に応じた完全な帯域幅（ネットワーク経由）

この分析では、単純にアルゴリズムと、memcacheへの埋め込みの詳細とパフォーマンステスト手法を確認します。元の記事をお読みください。

カッコウハッシュ

最初に、通常のカッコウハッシュを理解しましょう。 通常のハッシュテーブルはどのように機能しますか？ キーを取得し、このハッシュによって、挿入するキーまたはキーに対応する値を見つけることができるテーブルセル（バケットまたはバケット:)を選択します。 クッキングハッシュは2つのハッシュ関数を使用します;値を挿入または検索する可能性のあるセルは2つあります。

次の表を検討してください。各行はセルを表し、各セルには4つのデータスロットがあります。 スロットは、データ自体、オブジェクト、キーと値のペアへのポインターです。



検索するキーがあるため、2つのハッシュをカウントし、2つの可能なセルを取得します。 つまり、2つのセル×4スロット= 8スロットをチェックして、目的のキーを見つけるかどうかを確認する必要があります。

つまり、このようなハッシュテーブルを検索する場合、「通常の」ハッシュテーブルと比較して多くの操作が必要です。

カッコウハッシュは、貼り付け操作の処理方法のためにその名前を得ました。 最初に、両方のハッシュ関数を使用して挿入するキーXをハッシュし、2つの可能なセルを取得します。 これらのセルのいずれかに空のスロットがある場合、 Xをそこに保存します。 すべてのスロットがビジーの場合は、いくつかのキーが移動する時間です。 これらの2つのセルのいずれかで1つのスロットをランダムに選択し、そこからキーを移動（または「再配置」）して（ Xを呼び出して）、 Xを書き込むためのスペースを解放します。 2つのハッシュ関数で既にYをハッシュし、2番目のセルを見つけて、そこにYを挿入しようとします。 このセルのすべてのスロットもいっぱいになっている場合は、これらのスロットから既にキーを移動してYのスペースを空け、空のスロットが見つかるまで（または、特定の最大移動数、たとえば500に達するまで）移動し続けます。

ここでは、アルゴリズムはカッコウのように動作します-すでに使用されている場所から外部キーを引き出し、独自のキーをその中に入れます。

それでも空きスロットが見つからない場合は、このハッシュテーブルを拡張し、割り当てられたメモリを増やします。

このような挿入アルゴリズムでは、シーケンス全体、一連の動作の実行が必要になりそうですが、ハッシュをキャッシュするための挿入操作の時間の複雑さの推定値はO（1）です。

オリジナル作品からの引用

タグを使用して検索操作を改善する

上記から、多くの重要なサンプルと多くの比較があり、これらすべてがデータの局所性の観点からあまり良くないことは明らかです。 （どうやら、著者は、キーもキーのハッシュもテーブルセルのスロットに直接格納されず、別々に割り当てられたキー値構造に格納されるため、メモリからのランダムアクセスとキーの完全な比較が多数あることを意味しますプロセッサキャッシュを適切に機能させることができます） Cookieハッシュを最適化するために最初にしたことは、タグを導入することでした。 タグはキーの1バイトのハッシュ値であり、キーへのポインターの隣のハッシュテーブルスロットに直接格納します。 このようなタグを使用すると、ポインターで取得して完全に比較することなく、保存されたキーが検索キーと一致するかどうかを非常にすばやく（1バイトを比較するだけで）理解できます。

同じタグを持つ2つの異なるキーに対して余分な抽出が発生する可能性があるため、キーを完全に抽出して比較し、探しているキーと一致することを確認する必要があります。 シングルバイトタグの場合、衝突頻度は1/2 ^ 8 = 0.39％になります。 8つのスロット候補すべてをチェックする場合（たとえば、見つからないキーを検索する場合-ミス）、平均8×0.39％= 0.03ポインターの逆参照が発生します。 各セルはプロセッサのプロセッサキャッシュの1つのブロック（通常64バイト）に配置されるため、各検索では2つのブロックを読み取って2つのセルをチェックするだけでなく、キー検索が見つからない場合のポインターの逆参照-miss'eまたは1.03検索が成功した場合-ヒット。

オリジナル作品からの引用

タグを使用して貼り付け操作を改善する

キーに2つの可能なセルを定義する場合、2つのハッシュ関数を使用する代わりに、1つのハッシュと追加のタグのみを使用します：let cell_1 = hash（X）、そしてtag（X）、次にcell_2 = cell_1⊕tag（ X）。 この構造には次の便利なプロパティがあります。タグとcell_2を知っているcell_1を定義できます。 つまり、キーの移動操作中、キーがどのセルにあったかは関係ありません。完全なキーにアクセスせずに代替セルを計算できます。

アクセスの同時実行性サポート

私たちの知る限り、ハッシュスキームは並列アクセス（マルチリーダー、シングルライター）をサポートする最初の実装であり、高いメモリ効率を備えています（テーブルが90％を超える場合でも）。

オリジナル作品からの引用

このようなアルゴリズムに並列性を追加するには、2つの問題を解決する必要があります。

1. どのセルが操作の影響を受けるかを事前に知ることができないため、記録のためにセルをロックする際に祖父のロックを避ける
2. 誤ったキャッシュミスを避けるため、移動中にキーが1つのセルから既に削除されているが、新しいセルにまだ挿入されておらず、その時点で読み取りが行われた場合。

もちろん、厳密に言えば、著者は最初の問題を解決せず、一度に記録操作を1つしか実行できないため、単純に採点しました。 実際の条件下では、読み込みが負荷プロファイルを支配することが多いため、これは妥当な妥協案です。

キャッシュミス（偽陰性の応答）は、最初にCookieの移動の完全なチェーンを定義し、何も移動せずに、最後の空のスロットから目的の元の挿入まで逆の順序でこれらの移動を実行することで回避できます。 書き込み操作が1つのストリームで行われるという事実と組み合わせて、個々の交換は追加の動きを引き起こさないことが保証され、チェーン全体を事前にブロックすることなく実行できることがわかります。

最も簡単な実装は、交換に関係する2つのセルのそれぞれをロックし（順序を慎重に）、交換後にロックを解除することです。 ここでは、交換ごとに2つのロック/リリースが必要です。

最も一般的な用途に合わせてパフォーマンスを最適化することを試み、すべての挿入とルックアップを小さなオーバーヘッドで順次操作の1つのストリームに構築するために、1つの記録スレッドのみの存在を利用しました。 セルをロックする代わりに、各キーでバージョンカウンターを開始します。 挿入中にキーを移動するときにカウンターを増やし、同時移動の検出のためにルックアップ中にバージョンの変更を監視します。

オリジナル作品からの引用

しかし、これらのカウンターはどこに保存しますか？ それらを各キー値オブジェクトに追加すると、何億ものキーで多くのメモリが使用されます。 これらのキーと値のオブジェクトはハッシュテーブル自体の外部に格納され、ロックによって保護されないため、競合状態が発生する可能性もあります。

解決策は、固定サイズのカウンターの配列を使用することです-キーの数よりはるかに小さいです。 8192個のカウンターの配列が32KBキャッシュに分割され、各カウンターは古い友人であるハッシュの使用により、いくつかのキーに使用されます。 そのような妥協、このような共有カウンターの使用は、「余分な再試行」の可能性を維持しながら、ある程度のアクセス並列化を依然として提供します（バージョンカウンターテーブルでハッシュの衝突がある他のキーに対してバージョンカウンターが1増加しました）。約0.01％。

これらのカウンターは、次のように一般的なアルゴリズムに刻まれています。

• キーを移動する必要がある場合、挿入プロセスはこのキーのカウンターバージョンを1つ増やして、移動のプロセスを示します。 キーを移動した後、カウンターは再び1増加します。 カウントはゼロから開始するため、カウンターの奇数値はロックされたキーに対応し、偶数-ロック解除されます。
• カウンターで奇数の値を検出する検索プロセスは、待機してから再試行します。 カウンターが偶数の場合、この値を覚えて、両方のセルをカウントしてから、カウンター値を保存されている値と比較する必要があります。 カウンター値が変更された場合は、操作を再度繰り返す必要があります。

キャッシングハッシュを最適化するための追加のトリックは、いくつかの可能な挿入パスを並行して検索することです。 これにより、空のスロットをすばやく見つける可能性が高くなります。 テストによると、2つの可能なパスを並行してチェックすることが最適であることが判明しました。

時計の交換

これまで、挿入と検索について説明してきました。 最適化されたCookieハッシュもメモリを非常に効率的に使用しますが、キャッシュが限界まで（またはほぼ限界まで）満杯になることが予想されるため、混雑を心配する必要があります。

通常のMemcachedでは、最もよく使用されるキー（LRU）をクラウドアウトするポリシーが使用されますが、LRU順で厳密に安全にクラウドアウトするには、キーごとに18バイト（2つのポインターと2バイトの参照カウンター）が必要です。 また、かなりの同期オーバーヘッドが発生します。

対照的に、MemC3はキーごとに1ビットのみを使用し、操作を並列化する機能を備えています。 これは、厳密なLRUを放棄して、おおよそのCLRUベースのLRUアルゴリズムを採用することで実現されます。

ターゲットケースでは小さなオブジェクトが優勢であるため、LRUに近い押し出しを使用すると、メモリ使用量が削減され、キャッシュにより多くのレコードを保存できるようになり、全体的なヒット率が向上します。 セクション5に示すように、このような押し出し制御により、従来のMemcachedに比べてスループットが3倍から10倍に増加し、すべてが最高のヒットとなります。

オリジナル作品からの引用

周期的なビットバッファと、バッファ内の特定の場所を指す仮想の時針を想像してください。

各ビットは、キーと値のペアのオブジェクトの「年齢」（使用年齢）を表します。 対応するキーが最近使用された場合、ビットは「1」、それ以外の場合は「0」です。 キー操作は、単に対応する処方ビットを「1」に設定するだけです。 混み合うときは、時計の針が指すビットを確認する必要があります。 「0」の場合、対応するキーをキャッシュからプッシュできます。 「1」の場合、そこに「0」を書き込み、時計の針を次のビットに進めます。 このプロセスは、ゼロビットが見つかるまで繰り返されます。

ディスプレイスメントプロセスは、次のように楽観的ブロッキングスキームと統合されています。

プリエンプションプロセスがCLOCKアルゴリズムを使用して被害者キーXを選択すると、最初にキーXのカウンターバージョンをインクリメントし、現在Xを読み取っている他のスレッドに後で再試行する必要があることを伝えます。 次に、 Xを削除し、他のスレッドからの再試行を含め、後続の読み取りにアクセスできないようにします。 最後に、キーXのカウンターバージョンを再度インクリメントして、変更サイクルを完了します。 すべてのプリエンプションと挿入はロックを使用してシリアル化されるため、カウンターを更新するときに互いに影響を与えないことに注意してください。

オリジナル作品からの引用

それだけです 私と同じように楽しんでいただけたでしょうか。

okmeter.ioのオタクブログを購読する