Java キャッシュにおけるアバランシェとブレークダウンの問題とその解決策

キャッシュ雪崩

キャッシュ雪崩とは、Redis 内の多数のキャッシュがすべて同時に失敗することを意味します。この期間中に大量のリクエストが開始された場合、リクエストはデータベースに直接アクセスします。 . 、データベースに負荷がかかる可能性があります。

キャッシュなだれとは、一般に、キャッシュには存在しないがデータベース内に存在するデータを指し、期限切れによりリクエストがデータベースに直接送信されます。

解決策

キャッシュ雪崩を解決するには多くの方法があります:

• 1. キャッシュへの単一スレッド アクセスを保証するためにロックします。こうすることで、同時にデータベースにアクセスするリクエストが多くなくなります。

• 2. 有効期限を同じに設定しないでください。典型的な例は、ウォームアップ データを初期化するときで、データをキャッシュに保存するときに、ランダムな時間を使用して、多数のキャッシュが同時に期限切れにならないようにすることができます。

• 3. メモリが許せば、キャッシュを期限切れにしないように設定できます。

キャッシュ ブレークダウン

キャッシュ ブレークダウンはキャッシュ アバランチと非常によく似ていますが、異なる点は、キャッシュ ブレークダウンは一般に 1 つのキャッシュ障害を指し、同時にキャッシュ アバランチが発生することです。多くの同時リクエストがこのキーにアクセスする必要があるため、データベースに負荷がかかります。

解決策

キャッシュ ブレークダウンを解決する方法は、キャッシュ アバランシェを解決する方法と非常によく似ています:

• 1. シングル スレッドを確保するためのロックキャッシュにアクセスします。この方法では、最初のリクエストがデータベースに到達した後にキャッシュが書き換えられ、後続のリクエストでキャッシュを直接読み取ることができます。

• 2. メモリが許せば、キャッシュを期限切れにしないように設定できます。

キャッシュペネトレーション

キャッシュペネトレーションと上記の 2 つの現象の本質的な違いは、この時点でアクセスされるデータがデータベースに存在しないことです。存在しないため、キャッシュにも存在しません。同時実行性が大きすぎると、データが継続的にデータベースに到着し、データベースに大きな負荷がかかります。

解決策

キャッシュペネトレーションの問題では、キー自体が存在しないためロックが効かず、スレッドアクセス数を制御してもリクエストはデータベースに継続的に到着します。

キャッシュ侵入の問題を解決するには、通常、次のソリューションを一緒に使用できます:

• 1. インターフェイス層は検証を実行し、不正なキーがあれば直接返します。見つかった。たとえば、データベースが自動インクリメント ID を使用している場合、非整数 ID または負の ID が返された場合は、それを直接返すことができます。または、32 ビット UUID が使用されている場合、ID の長さが 32 に等しくない場合は、それを直接返すことができます。ビットの場合は、直接返すことができます。

• 2. 存在しないデータもキャッシュする 空の値、またはその他の合意された無効な値を直接キャッシュできます。このソリューションでは、キーの有効期限を短く設定することが最善です。そうしないと、多数の存在しないキーが Redis に保存され、大量のメモリを占有することになります。

ブルーム フィルター

上記のキャッシュ侵入ソリューションについて考えてみましょう。キーが最初のメソッドである検証をバイパスでき、この時点で多数の存在しないキー (1 億または 10 億など) がアクセスされると、それらはすべてキャッシュに保存されます。これにより、非常に大きなスペースが占有され、大量のサーバー メモリが浪費され、メモリ不足が発生します。

では、もっと良い解決策はあるのでしょうか?次に紹介するブルームフィルターは、キー値が多すぎる問題を最大限に解決することができます。

ブルーム フィルターとは

おそらくほとんどの人は、面接で次のような質問があることを知っているでしょう。「10 億個の大量の不規則なデータに要素が存在するかどうかを迅速に判断するにはどうすればよいですか?」

この問題を解決するには、ブルーム フィルターを使用する必要があります。そうしないと、ほとんどのサーバーのメモリにこれほど大量のデータを保存できません。

ブルーム フィルターは、1970 年にブルームによって提案されました。実際には、長いバイナリ ベクトル (ビットマップ) と一連のランダム マッピング関数 (ハッシュ関数) です。

ブルーム フィルターを使用すると、要素がコレクション内にあるかどうかを取得できます。利点は、スペース効率とクエリ時間が通常のアルゴリズムよりも優れていることですが、欠点は、一定の誤認識率があり、削除が難しいことです。

ビットマップ

Redis のデータ構造の 1 つはビットマップです。ブルーム フィルターの重要な実装は、ビット配列であるビットマップの実装であり、この配列内の各位置in には 0 と 1 の 2 つの状態しかなく、各位置は 1 バイトのみを占めます。0 は要素が存在しないことを示し、1 は要素が存在することを示します。次の図は、ブルーム フィルターの簡単な例です (キー値は、ハッシュとビット演算によってどこに該当するかを決定できます)。

ハッシュ衝突

上で孤独と狼が同じ位置にあることがわかりましたが、異なるキー値がハッシュ化後に同じ値になるこの現象はハッシュ衝突と呼ばれます。ハッシュの衝突が発生してからビット操作が実行されると、必ず同じ位置になります。

ハッシュの衝突が多発すると判定の精度に影響を与えるため、ハッシュの衝突を減らすためには一般に次の 2 つの要素を考慮します。 #1. ビットマップ配列のサイズを増やします (ビットマップ配列が大きくなると、占有されるメモリも大きくなります)。

• 2. ハッシュ関数の数を増やします (1 つの関数の後では同じキー値が等しくなります。その後、2 つ以上のハッシュ関数を計算すると、同じ結果が得られます)。自然と減っていきます）。

• 上記の 2 つの方法を総合的に考慮する必要があります: たとえば、ビット配列を増やすとより多くのスペースが消費され、より多くのハッシュ計算も CPU を消費して影響が生じます。したがって、ビット配列の大きさと、ハッシュ関数を何回計算する必要があるかについては、特定の状況を具体的に分析する必要があります。

ブルーム フィルターの 2 つの主な特徴

次は 2 つのハッシュ関数によって得られるブルーム フィルターです。下の図によると、Redis がまったく存在しないことが簡単にわかります。 、しかし、2 つのハッシュ関数の後に Redis によって取得された 2 つの位置はすでに 1 です (1 つは f2 を介して wolf によって取得され、もう 1 つは f1 を介して Nosql によって取得されます)。

#したがって、上記の現象を通じて、ブルーム フィルターの観点から、ブルーム フィルターには主に 2 つの大きな特徴があると結論付けることができます。

1. ブルーム フィルターが要素が存在すると判断した場合、その要素は存在する可能性があります。

• 2. ブルーム フィルターによって要素が存在しないと判断された場合、この要素は存在してはなりません。

• 要素の観点から、次の 2 つの主要な特性も引き出す​​ことができます:

1. 要素が実際に存在する場合、ブルーム フィルター存在を判断しなければなりません。

• 2. 要素が存在しない場合、ブルーム フィルターは要素が存在すると判断する場合があります。

• PS: ハッシュ関数が N 回渡される場合、存在を判断するには N 個の位置が 1 である必要があることに注意してください。1 つが 0 である限り、それは可能です。要素がブルーム フィルターに存在しません。
  fpp

ハッシュの衝突を 100% 回避することはできないため、ブルーム フィルターには常に誤検知率が存在します。ブルーム フィルターは、この偽陽性確率を、False Positive Probability (略して fpp) と呼びます。

実際にブルーム フィルタを使用する場合は、自分で fpp を定義し、ブルーム フィルタの理論に基づいて必要なハッシュ関数の数とビット配列スペースの大きさを計算できます。ハッシュ衝突が発生しないという 100% の保証はないため、この fpp を 100% として定義することはできないことに注意してください。

以上がJava キャッシュにおけるアバランシェとブレークダウンの問題とその解決策の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。