キャッシュの操作中の問題とその解決方法

こんにちは、Habr！



私の名前はVictor Pryazhnikovです。私はBadoo SRVチームで働いています。 私たちのチームは、サーバー側のクライアント向けに内部APIを開発およびサポートしています。データキャッシングは、私たちが毎日遭遇することです。



プログラミングには、名前の作成とキャッシュの無効化という、本当に複雑なタスクが2つしかないという意見があります。 障害は難しいとは言いませんが、キャッシングは障害がなくてもかなり厄介なことのように思えます。 キャッシュの使用を開始する前に、考えるべきことがたくさんあります。 この記事では、大規模システムでキャッシュを操作するときに発生する可能性のあるいくつかの問題を定式化しようとします。







サーバー間でキャッシュされたデータを共有する問題、並列データ更新、「コールドスタート」、システムの誤動作について説明します。 また、これらの問題の可能な解決策を説明し、これらのトピックがより詳細にカバーされている資料へのリンクを提供します。 原則としてキャッシュとは何か、特定のシステムの実装の詳細については説明しません。



作業するとき、問題のシステムはアプリケーション、データベース、およびデータのキャッシュで構成されていると思います。 データベースの代わりに、他のソースを使用できます（たとえば、ある種のマイクロサービスや外部API）。

キャッシュサーバー間でデータを共有する

十分に大きなシステムでキャッシュを使用する場合は、使用可能なサーバー間でキャッシュされたデータを共有できることを確認する必要があります。 これはいくつかの理由で必要です。

• 大量のデータが存在する可能性があり、それらは1つのサーバーのメモリに物理的に収まりません。
• データは非常に頻繁に要求される可能性があり、1つのサーバーがこれらすべての要求を処理することはできません。
• キャッシュの信頼性を高める必要があります。 キャッシュサーバーが1つしかない場合、クラッシュした場合、システム全体がキャッシュなしのままになり、データベースの負荷が大幅に増加する可能性があります。

データを分割する最も明白な方法は、キャッシュキーに応じて擬似乱数的にサーバー番号を計算することです。



これを実装するためのさまざまなアルゴリズムがあります。 最も簡単な方法は、数値キー表現（CRC32など）の整数除算の余りとして、サーバー番号をキャッシュサーバーの数で計算することです。

$cache_server_index = crc32($cache_key) % count($cache_servers_list);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このようなアルゴリズムは、モジュラーハッシュと呼ばれます。 ここではCRC32を例として使用しています。 代わりに、他のハッシュ関数を使用できます。その結果から、サーバー数以上の数を取得でき、結果はほぼ均等に分散されます。



この方法は理解と実装が簡単で、サーバー間でデータをかなり均等に分散しますが、重大な欠点があります：サーバーの数を変更すると（技術的な問題や新しいサーバーの追加により）、キーの残りの部分が変更されるため、キャッシュの大部分が失われます。



この問題を実証する小さなスクリプトを作成しました。



モジュラーハッシュとCRC32を使用して、5つのサーバーに分散された100万の一意のキーを生成します。 1台のサーバーの障害と残りの4台のデータの再配布をエミュレートします。



この「失敗」の結果、キーの約80％が位置を変更します。つまり、以降の読み取りにはアクセスできなくなります。



合計キー数：1,000,000

破片カウント範囲：4、5





ここで最も不愉快なことは、80％が制限からかけ離れていることです。 サーバーの数が増えると、キャッシュ損失の割合は増え続けます。 唯一の例外は複数の変更（2から4、9から3など）であり、損失は通常より少なくなりますが、いずれの場合も既存のキャッシュの少なくとも半分：





GitHubにデータを収集するスクリプトと、このテーブルを描画するipynbファイル、およびデータファイルを投稿しました。



この問題を解決するために、別のブレークダウンアルゴリズム- 一貫性のあるハッシュがあります。 このメカニズムの基本的な考え方は非常に単純です。ここでは、キーのスロットへの追加マッピングが追加され、その数はサーバーの数を大幅に超えます（数千またはそれ以上になる場合があります）。 スロット自体は、サーバー全体に分散されています。



サーバーの数を変更しても、スロットの数は変わりませんが、これらのサーバー間のスロットの分布は変わります。

• サーバーの1つに障害が発生すると、そのサーバーに属していたすべてのスロットが残りのスロットに分配されます。
• 新しいサーバーが追加されると、既存のサーバーのスロットの一部がサーバーに転送されます。

通常、一貫性のあるハッシュの考え方は、リングを使用して視覚化されます。リングの円上の点は、スロットまたはスロットの範囲の境界を示します（これらのスロットが多数ある場合）。 以下は、最初は4つのサーバーに分散されている少数のスロット（60）がある状況の単純な再分散の例です。







最初のパーティションの図では、1つのサーバーのすべてのスロットが一列に並んでいますが、実際にはこれは前提条件ではありません。好きなように配置できます。



前の方法に対するこの方法の主な利点は、ここでは各サーバーに1つの値ではなく全範囲があり、サーバーの数が変わると、キーの非常に小さい部分がそれらの間で再配布されることです（ k / N



、ここでk



はキーの総数、 N



はサーバーの数）。



ハッシュモジュロの欠如を実証するために使用したシナリオに戻ると、同じ状況で5つのサーバーのうちの1つが（同じウェイトで）落ち、残りの損失の間でキーが再分配されるという状況では、キャッシュの80％はありませんが、20％しかありません。 最初にすべてのデータがキャッシュにあり、それらすべてが要求されると仮定すると、この違いは、調整されたハッシュを使用すると、データベースへの要求が4倍少なくなることを意味します。



このアルゴリズムを実装するコードは前のコードよりも複雑になるため、この記事では説明しません。 必要に応じて、簡単に見つけることができます-GitHubには、さまざまな言語の実装が多数あります。



一貫性のあるハッシュに加えて、この問題を解決する方法は他にもあります（たとえば、 ランデブーハッシュ ）が、あまり一般的ではありません。



選択したアルゴリズムに関係なく、キーハッシュに基づいてサーバーを選択するとうまく機能しない場合があります。 通常、キャッシュには同じタイプのデータのセットは含まれませんが、大量の異種データ：キャッシュされた値はメモリ内の異なる場所を占め、異なる頻度で要求され、異なる生成時間、異なる更新レート、異なるライフタイムを持ちます。 ハッシュを使用する場合、キーの行き先を正確に制御することはできません。また、結果として、保存されたデータの量とその要求の数の両方で「スキュー」が発生する可能性があります。これにより、異なるキャッシュサーバーの動作が大きく異なります。



この問題を解決するには、異種データがサーバー間でほぼ均一に分散されるように、キーを「汚す」必要があります。 これを行うには、サーバーを選択するために、キーではなく、説明されているアプローチのいずれかを適用する必要がある他のパラメーターを使用する必要があります。 これは、データモデルに依存するため、どのようなパラメーターになるかを示すものではありません。



この場合、キャッシュされたデータのほとんどすべてが同じユーザーを参照しているため、キャッシュ内のデータをシャーディングするためのパラメーターとしてユーザーIDを使用します。 これにより、データをほぼ均等に分散できます。 さらに、ボーナスを受け取りますmulti_get



を使用して、複数の異なるキーをユーザー情報とともに一度にロードする機能（現在のユーザーの頻繁に使用されるデータのプリロードで使用します）。 各キーの位置が動的に決定された場合、要求されたすべてのキーが同じサーバーに属しているという保証がないため、このシナリオでmulti_get



を使用することはできません。



こちらもご覧ください：

• ウィキペディアの記事「分散ハッシュテーブル」
• ウィキペディアの記事「一貫したハッシュ」
• 一貫性のあるハッシュのガイド
• 一貫したハッシュとランダムツリー：World Wide Webのホットスポットを緩和するための分散キャッシングプロトコル
• 一貫性のあるハッシュリングの構築

並列データ更新リクエスト

次の簡単なコードをご覧ください。

 public function getContactsCountCached(int $user_id) : ?int { $contacts_count = \Contacts\Cache::getContactsCount($user_id); if ($contacts_count !== false) { return $contacts_count; } $contacts_count = $this->getContactsCount($user_id); if (is_null($contacts_count)) { return null; } \Contacts\Cache::setContactsCount($user_id, $contacts_count); return $contacts_count; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

キャッシュにリクエストされたデータがない場合はどうなりますか？ コードから判断すると、このデータを取得するメカニズムを開始する必要があります。 コードが1つのスレッドでのみ実行される場合、すべてが正常に実行されます。データはダウンロードされ、キャッシュされ、次の要求でそこから取得されます。 しかし、複数の並列フローで作業する場合、すべてが異なります。データは一度ではなく複数ロードされます。



次のようになります。











プロセスNo. 2でリクエストの処理を開始した時点では、キャッシュにはまだデータはありませんが、プロセスNo. 1でデータベースからすでに読み取られています。 この例では、リクエストは2つしかないため、問題はそれほど深刻ではありませんが、さらに多くのリクエストが存在する可能性があります。



並列ダウンロードの数は、並列ユーザーの数と必要なデータのダウンロードにかかる時間によって異なります。



1秒あたり200リクエストの負荷でキャッシュを使用する何らかの機能があるとします。 データのダウンロードに50ミリ秒が必要な場合、この時間内に50 / (1000 / 200) = 10



リクエストを受け取ります。



つまり、キャッシュが存在しない場合、1つのプロセスがデータのロードを開始し、ダウンロード中に、キャッシュ内のデータを参照せずにロードする9つのリクエストがさらに送信されます。



この問題はキャッシュスタンプと呼ばれます（この用語のロシア語の類似語は見つかりませんでした。文字通り「スタンプキャッシュ」と翻訳できます。記事の冒頭の写真はこのアクションの例を示しています）、 ヒットストーム （「キャッシュミスストーム」）または犬パイル効果 。 解決するにはいくつかの方法があります。

再カウント/ロード操作を開始する前にロックする

このメソッドの本質は、キャッシュにデータがない場合、それをロードするプロセスは、他の並列プロセスが同じことをできないようにするロックをキャプチャする必要があるということです。 memcachedの場合、ブロックする最も簡単な方法は、キャッシュされたデータ自体が保存される同じキャッシュサーバーにキーを追加することです。



このオプションを使用すると、データは1つのプロセスでのみ更新されますが、キャッシュが欠落しているがロックを取得できなかった状況に陥ったプロセスをどう処理するかを決定する必要があります。 エラーまたはデフォルト値を与え、しばらく待ってから、データの取得を再試行します。



さらに、ロック自体の時間を慎重に選択する必要があります。ソースからデータをロードし、キャッシュに入れることが保証されている必要があります。 十分でない場合、別の並列プロセスがデータのリロードを開始する場合があります。 一方、この時間が長すぎて、ロックを受信したプロセスがキャッシュにデータを書き込んでロックを解除せずに停止した場合、他のプロセスもロック時間が切れる前にこのデータを取得できません。

バックグラウンドの更新を削除する

このメソッドの主なアイデアは、キャッシュからデータを読み取り、キャッシュに書き込むプロセスを分離することです。 オンラインプロセスはキャッシュからデータを読み取るだけで、ロードはしません。これは別のバックグラウンドプロセスでのみ発生します。 このオプションは、並列データ更新を不可能にします。



この方法では、データをキャッシュに書き込む別のスクリプトを作成および監視し、記録されたキャッシュの有効期間とそれを更新するスクリプトが次に開始する時間を同期するために、追加の「費用」が必要です。



Badooでこのオプションを使用するのは、たとえば、ユーザーの総数のカウンターです。これについてはさらに説明します。

確率的更新方法

これらのメソッドの本質は、キャッシュ内のデータが存在しない場合だけでなく、存在する場合はある程度の確率で更新されることです。 これにより、キャッシュされたデータが「腐敗」する前に更新され、すべてのプロセスで一度に必要になります。



このようなメカニズムを正しく動作させるには、キャッシュされたデータの有効期間の開始時に、再計算の確率は小さいが、徐々に増加することが必要です。 これは、指数分布を使用するXFetchアルゴリズムを使用して実現できます。 その実装は次のようになります。

 function xFetch($key, $ttl, $beta = 1) { [$value, $delta, $expiry] = cacheRead($key); if (!$value || (time() − $delta * $beta * log(rand())) > $expiry) { $start = time(); $value = recomputeValue($key); $delta = time() – $start; $expiry = time() + $ttl; cacheWrite(key, [$value, $delta, $expiry], $ttl); } return $value; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この例では、 $ttl



はキャッシュ内の値のライフタイム、 $delta



はキャッシュされた値を生成するのにかかった時間、 $expiry



はキャッシュ内の値が$expiry



になるまでの時間、 $beta



はアルゴリズム設定パラメーターで、変更可能なもの再カウントの確率（値が大きいほど、リクエストごとに再カウントされる可能性が高くなります）。 このアルゴリズムの詳細な説明は、このセクションの終わりにあるリンクであるホワイトペーパー「Optimal Probabilistic Cache Stampede Prevention」にあります。



このような確率的メカニズムを使用する場合、並列更新を除外せず、その可能性を減らすだけであることを理解する必要があります。 それらを除外するには、複数のメソッドを一度に「クロス」できます（たとえば、更新する前にロックを追加します）。



こちらもご覧ください：

• ウィキペディアのCacheスタンプ記事
• 最適な確率的キャッシュスタンピード防止
• さまざまな方法の説明とテストを含むGitHubリポジトリ
• 記事「キャッシュ」「ダミー」

コールドスタートとキャッシュウォームアップ

キャッシュに存在しないことによる大量データ更新の問題は、同じキーの多数の更新だけでなく、異なるキーの多数の同時更新によっても発生する可能性があることに注意する必要があります。 たとえば、これは、キャッシュと固定キャッシュライフタイムを使用して新しい「人気のある」機能を展開するときに発生する可能性があります。



この場合、ロールアウト直後にデータのロードが開始され（問題の最初の兆候）、その後キャッシュに移動し、しばらくの間すべてが正常になります。キャッシュが期限切れになると、すべてのデータが再びロードを開始し、データベースの負荷が増加します。



このような問題を完全に排除することはできませんが、データのロードを時間内に「スミア」することは可能です。これにより、データベースに対する急激な数の並列クエリを排除できます。 これを実現するには、いくつかの方法があります。

• 新機能のスムーズな組み込み。 そのためには、これを実行できるメカニズムが必要です。 最も簡単な実装オプションは、ごく一部のユーザーに含まれる新しい機能を展開し、徐々に増やしていくことです。 このシナリオでは、一度に大量の更新が行われることはありません。最初は一部のユーザーのみが機能を利用できるようになり、増加するにつれてキャッシュが既に「ウォームアップ」されているためです。
• データセットの異なる要素の異なる寿命。 このメカニズムは、すべての機能を展開するときに発生するピークにシステムが耐えられる場合にのみ使用できます。 その特徴は、キャッシュにデータを書き込むとき、各要素に独自の有効期間があるという事実にあり、これにより、更新シャフトは、その後の更新が時間内に配信されるため、はるかに速くスムーズになります。 このようなメカニズムを実装する最も簡単な方法は、キャッシュの有効期間にランダム係数を掛けることです。

 public function getNewSnapshotTTL() { $random_factor = rand(950, 1050) / 1000; return intval($this->getSnapshotTTL() * $random_factor); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

何らかの理由で乱数を使用したくない場合は、いくつかのデータ（ユーザーIDなど）に基づいてハッシュ関数を使用して取得した擬似乱数値に置き換えることができます。

例

「冷たい」キャッシュ状況をエミュレートする小さなスクリプトを書きました。

その中で、要求されたときにユーザーが自分のデータをダウンロードする状況を再現します（キャッシュにない場合）。 もちろん、この例は合成ですが、それでもシステムの動作の違いを見ることができます。



これは、固定（fixed_cache_misses_count）と異なる（random_cache_misses_count）キャッシュライフタイムがある状況でのヒットミスの数のグラフです。







どちらの場合も、作業の開始時に負荷のピークは非常に顕著ですが、疑似ランダムの有効期間を使用すると、はるかに高速に平滑化されることがわかります。

ホットキー

キャッシュ内のデータは異種であり、その一部は非常に頻繁に要求できます。 この場合、並行して更新することさえできませんが、読み取り値の数自体が問題を引き起こす可能性があります。 このようなキーの例は、ユーザーの総数のカウンターです：







このカウンターは最も一般的なキーの1つであり、通常のアプローチを使用すると、それに対するすべての要求は1つのサーバーに送信されます（これは1つのキーであり、同じタイプではないため）。 。







この問題を解決するには、1つのキャッシュサーバーではなく、一度に複数のキャッシュサーバーにデータを書き込む必要があります。 この場合、このキーの読み取り回数を数倍減らしますが、更新とサーバー選択コードが複雑になります。結局、別のメカニズムを使用する必要があります。



Badooでは、すべてのキャッシュサーバーにデータを一度に書き込むことでこの問題を解決しています。 このため、読み取り時には、一般的なサーバー選択メカニズムを使用できます。コードでは、通常のユーザーIDシャーディングメカニズムを使用できます。読み取り時には、このホットキーの詳細について知る必要はありません。 私たちの場合、サーバーが比較的少ないため（サイトあたり約10台）、これは機能します。



キャッシングサーバーがさらに多い場合、この方法は最も便利ではない可能性があります。同じデータを何百回も複製するのは意味がありません。 この場合、すべてのサーバーではなく、サーバー側でのみキーを複製することが可能ですが、このオプションにはもう少し手間がかかります。



キャッシュキーによるサーバー定義を使用する場合、限られた数の擬似ランダム値を追加できます（ total_users_count_2



t otal_users_count_1



、 total_users_count_2



などを作成することにより）。 同様のアプローチが、たとえばEtsyで使用されています。



シャーディングパラメーターに明示的な指示を使用する場合は、異なる擬似乱数値を渡すだけです。



両方の方法の主な問題は、異なる値が実際に異なるキャッシュサーバーに送られることを確認することです。



こちらもご覧ください：

• Etsyのキャッシュ方法：ハッシュ、ケタマ、キャッシュスミアリング

機能不全

システムは100％信頼できるものではないため、障害が発生した場合の動作を考慮する必要があります。 障害は、キャッシュ自体とデータベースの両方で発生する可能性があります。



前のセクションでキャッシュの障害について既に説明しました。 追加できる唯一のことは、稼働中のシステムで機能の一部を無効にする可能性を予見することです。 これは、システムがピーク負荷に対処できない場合に役立ちます。



データベースに障害が発生し、キャッシュがない場合、キャッシュスタンプの状況に陥ることがあります。これについては、前に説明しました。 すでに説明した方法で終了するか、意図しない誤った値を短い寿命でキャッシュに書き込むことができます。 この場合、システムはソースが使用不可であると判断でき、しばらくの間、データを要求しようとするのを停止します。

おわりに

この記事では、キャッシュを操作する際の主な問題について触れましたが、それ以外にも多くの問題があり、この会話を非常に長く続けることができると確信しています。 私の記事を読んだ後、キャッシュがより効率的になることを願っています。