redisデータ構造

列

struct sdshdr{
//buf配列の使用バイト数を記録する
//等于 SDS 保存字符串的长度
int len 
//记录 buf 数组中未使用字节的数量
int free 
//文字列を保持するバイト配列
char buf[] 
 
}

実際、redisの文字列の実装はArrayListに似ているので、文字列の長さを取得する時間の複雑さはO(1)です。事前割り当ての戦略を使用して、拡張は2倍に拡張されますが、1MBを超える場合は、1回の拡張につき1MBのみ拡張され、文字列の最大容量は512MBです。

アプリケーションのシナリオ

• ユーザー情報をキャッシュし、JSONを文字列にシリアライズしてredisに格納します。
• カウントは、値が整数である場合、セルフインクリメント操作することができ、セルフインクリメントは、符号付きロングの最大値と最小値の間の範囲です。

list

LinkedList内のJavaと同等で、彼はバイリニア連結リスト構造であり、挿入と削除操作は非常に高速ですが、インデックスの位置決めは遅くなります。

実際には、リストの基本的な構造は2つ、1つはジップリスト、1つはクイックリストであり、少ない要素でジップリストを使用すると、連続したスペースを確保し、データの集中ストレージ、データが少ないので、チェーンリストを使用する場合は、prevとnextのポインタが必要になり、スペースを占有し、データがより多く、ポインタを持つ複数のジップリストになりますquicklistに連鎖させることで、メモリの断片化を減らすことができます。

アプリケーションのシナリオ

• しばしば非同期キューとして使用され、遅延タスク構造を文字列にシリアライズしてredisのリストに詰め、別のスレッドがそのリストから処理をポーリングします。

hash

javaのhashmapに相当し、配列＋リンクリストの2次元構造を利用した順序なし辞書。ただし、辞書の値は文字列のみ。

辞書は、プログレッシブ・リハッシュ戦略を使用して、リハッシュ展開用に最適化されています。再ハッシュのプロセスでは、2つの新旧のハッシュ構造が保持され、クエリは、同時に2つのハッシュ構造を照会し、ハッシュ操作の命令と同様に、後続のタイムドタスクでゆっくりと移行され、移行が完了した後、古いハッシュ構造が削除され、メモリリカバリされます。

set

java内部のhashsetに相当し、単にペアは順序付けされておらず、一意です。内部実装は特別な辞書であり、値のすべての値は、実際には、ハッシュ値を計算することによって、それが繰り返されるかどうかを判断するために、nullです。アプリケーションのシナリオ：

• 当選したユーザーIDのシナリオを強調しないでください。
• 交差点 連結 差分

zset

sortedSetとHashMapの組み合わせに似ていますが、1つは値の一意性を保証するためのセットであること、もう1つはソートの重みの値に代わって、各値にスコアを与えることです。

zsetの内部ソート機能は、"ジャンプリスト "を介して達成され、なぜジャンプリストを使用すると、zsetのは、ランダムな挿入と削除をサポートする必要があるため、その後、配列を使用することはできません、2つの部分のルックアップは、高速ルックアップの場所に挿入することができますので、高速な挿入と削除連鎖表の特性は、2つの部分のルックアップは、配列の特性です。

struct zslnode{
 string value;
 double score;
 zslnode*[] forwards;//多層接続ポインタ
 zslnode*[] backward;//バックトラックポインタ
}
struct zsl{
 zslnode* header;//ジャンプリストヘッダーポインター
 int maxLevel;//現在最高レベルを訪問しているジャンプリスト
 map<string,zslnode*> ht;// hashmapすべての
}

ここでzslはzsetの構造体であり、まずこのヘッダーポインターはジャンプテーブルの構造を保持するために使用されます。そして最下層では、forwardとbackwardが双方向のチェーンテーブルを形成するために使用されます。最後に、マップは、すべてのノードを格納するために使用され、このマップは、行われた変更を容易にするためです。実際には、ジャンプテーブルの階層の原則は、理由の各層は、ツリーの構造と同様に構築された、いくつかを選ぶことであり、その後、クエリのO（logn）複雑さを達成することができますクエリの効率を向上させます。

アプリケーションのシナリオ

• zset を使って遅延キューを実装し、メッセージを値としてシリアライズし、処理期限をスコアとして保持します。しかし、redisメッセージキューは100%信頼できるものではないので、サービスクラッシュ後にタスクを取得するとメッセージロスにつながるため、処理失敗時の補償戦略を考慮する必要があります。

たとえば、ハッシュの有効期限はキーの1つではなくハッシュ全体であり、有効期限が設定された後はセットによって上書きされます。

redisスレッドモデル

redisは、シングルスレッドプログラムであり、すべてのデータは、メモリ上にあるので、多くの操作は、redisの遅れの原因となる、実際には、redisもNIOモデルのnettyのセット、ノンブロッキングioを行く、オペレーティングシステムのselectを呼び出す、ポーリング、epollこの物事のセットは、イベントループに基づいて対処するために、これは、実装に似ているので、直列化データベースの分離レベルです。結局のところ、すべての操作はシリアルに実行されるため、シリアライズのデータベース分離レベルと同様の実装です。シングルスレッド操作は、不要なコンテキストの切り替えや競争条件を回避し、マルチプロセスやマルチスレッドスイッチングとCPUを消費することによって引き起こされることはありません、ロックのすべての種類について考える必要はありません、ロックリリースロック操作はありません、そこにデッドロックの可能性によるパフォーマンスの消費はありません。

redis

redisのトランザクションはリレーショナルデータベースのような厳密なトランザクションではありません。

• マルチ・オープン・トランザクション
• exec トランザクションの実行
• 廃棄トランザクション
• watchは1つ以上のキーを監視するもので、multiコマンドを有効にする前に使用する必要があります。 実行中にwatchキーが変更されたことが判明した場合、エラーが報告されます。

execコマンドを受信した後、トランザクションキューに格納されているコマンドになります前に、redisトランザクションは、直接タスクのキューを実行するので、redisは、シングルスレッドでシリアライズされているため、理論的には "原子性 "を保証することができますが、コマンドエラーの実行の途中で、後続のコマンドの場合。しかし、コマンドは、エラーの途中で実行された場合、後続のコマンドはまだ実行されますので、全く原子性がない、発見コマンドは、トランザクションキュー内のすべてのコマンドを破棄するだけで実行されません。したがって、トランザクションは注意して使用する必要があります。

永続 RDB スナップショット AOF 追加書き込み

RDB

スナップショットは、実際にはデータのバイナリシリアライズのメモリは、ストレージは非常にコンパクトになり、データベースのバックアップに似て、スナップショットの過程で、redisまたはそれに応じて要求するので、メモリ内のデータを変更しながらバックアップされます。この時間は、オペレーティングシステムのマルチプロセスCOWを使用し、スナップショットの永続性を達成するために、実際には、子プロセスの関数フォークアウト内部のglibcの使用は、子プロセスは、メモリデータを変更されません、ちょうど読み取りをトラバースする場合、親プロセスは、この時点で要求に対応するために、データを変更すると、親プロセスは、現在のメモリページを変更するためにコピーされますので、子プロセスのスキャンデータはされません。変更します。

AOF：インクリメンタル・アペンド・ロギングは、実際にはデータベースのbinlogに似ており、実行中のコマンドを記録し、クラッシュがドロップされた場合、再起動時にデータを回復するためにAOFログが再生されます。AOFロギングでは、オペレーティングシステムのfsync関数が使用されます。つまり、AOFログがトリミングされないように、カーネルキャッシュが強制的にディスクにフラッシュされますが、この操作は比較的遅いため、1秒間隔で1回呼び出されるようにタイミングが設定されます。

redis4.0以降の永続化では、ハイブリッド永続化を使用することができ、これは実際にはデータベースの定期的なバックアップと同等であるため、ログの再起動と再生は処理を高速化します。

マスター・スレーブ同期

第一に、redisのマスター・スレーブ同期はCAPのAPシステムを保証するので、最終的な一貫性が保証されます。なぜならマスターノードはユーザーリクエストを処理した後に戻るからです。

マスター・スレーブ同期には、インクリメンタル同期とスナップショット同期の2種類があります。

• インクリメンタル同期：redis同期コマンドストリームの同期は、コマンドストリームは、メモリバッファにあり、バッファは固定長のリング配列は、非同期にスレーブノードに送信されますが、バッファが満杯の場合は、ドロップされたコマンドをカバーするために最初から開始され、この時間は、スナップショット同期を使用する必要があります。

• スナップショット同期：マスターは、スナップショットを生成するbgsaveコマンドを実行し、ディスクに現在のメモリ内のすべてのデータをスナップショットし、その後、スレーブノードにスナップショットファイルを送信し、スレーブノードは、それを受け入れた後、完全にロードされ、インクリメンタル同期を実行し続けます。しかし、スナップショットレプリケーションのデッドサイクルがあるかもしれません、つまり、増分同期バッファが満杯になり、スナップショット同期の出発、スナップショット同期のプロセス、増分バッファが再び満杯になり、その後スナップショット同期、スナップショットレプリケーションのデッドサイクルを避けるために、適切なバッファサイズを設定する必要があります。

• マスター・スレーブ同期クラスタ最適化：

  1. マスター・ノードは永続化処理を行わず、スレーブ・ノードを使用して永続化処理を行います。マスターとスレーブは同じLAN上にあることが望ましいです。
  2. マスター・スレーブ同期は、マスター<スレーブ1<スレーブ2<スレーブ3の連鎖構造を形成するために使用することができます。

センチネル センチネルモード

実はこれはredisが公式に提供しているマスター・スレーブ切り替えスキームで、一般的に3〜5ノードで構成されるマスター・スレーブ・ノードの健康状態を確認するスキームを提供するzookeeperクラスタとみなすことができます。クライアントがredisクラスタに接続すると、まずSentinelクラスタに接続して接続するマスターノードの接続情報を取得し、マスターノードがハングアップした場合はSentinelクラスタに再アドレス指定し、Sentinelはクライアントに最適なスレーブノードを返します。実際、このプロセスはレジストリ機構にzkを使用するDubboと似ています。

redisクラスタプログラム

• redisクラスタ：codisとは異なり、各redisノードはピアツーピアです。つまり、スロット配布情報は各redisノードに保存され、クライアントがアクセスすると、まずメモリ内のスロット情報のコピーを取得し、それから直接操作対象のノードを探します。

redisの期限切れキーの削除ポリシー

• 時間指定スキャン：redisは有効期限が設定されたキーを別のハッシュ辞書に入れ、redisはデフォルトで1秒間に10回の有効期限スキャンを行います。すべてのキーを走査する代わりに、単純な貪欲な戦略を使用しています。期限切れ辞書はランダムに20個のキーを選択し、期限切れのキーの割合が1/4以上になったら期限切れの20個のキーを削除します。同時に、時間がかかりすぎないように、redisはデフォルトで25msのタイムアウトを追加しました。

時間指定スキャンの問題点は、多数の鍵が同時に期限切れになると、リクエストが来たときに25ミリ秒待つことになるため、期限切れ時間を同時に期限切れにならないようにランダムにする必要があることです。

• 不活性削除：redisは、シングルスレッドなので、データのハッシュ構造などの要素の数千を含む大規模なキーを削除する場合は、直接削除を呼び出すと、スレッドの遅延が発生する予定です。この時、redisは、削除する参照のハッシュ構造をunlinkコマンドを実行するスレッドセーフ非同期タスクキューに入れ、サブスレッドにゆっくりと削除され、これは遅延削除戦略です。

キャッシュ侵入

redisは物理メモリの制限を超えるとメモリ消去を行い、有効期限が設定されたキーのみを消去します：

• LRU：redisが実装するLRUアルゴリズムは近似的なLRUアルゴリズムで、各キーに24ビットの小さなフィールドを追加して更新時間を記録します。そして、LRUは唯一の不活性な削除は、書き込み要求が来たときに、メモリが超過していることが判明した場合、それは、LRUを起動し、ランダムに5つのキーを検索し、最も古いキーを排除し、消去はまだ超えている場合、その後、ランダムに5つの最も古い排除を見つけるためにサンプリングを続行します。
• LFU：LRUの問題点は、キューの末尾で削除されたキーに突然アクセスがあった場合、そのキーはホットキーになりますが、アクセス頻度は1しかありません。LRUでは、キーオブジェクトの24bitに更新時刻を格納しますが、LFUでは16bitに時刻を格納し、精度を下げ、残りの8bitにアクセス回数を格納します。

redis分散ロック

redisロックをsetnxコマンドで文字列値に設定し、expireコマンドでキーの有効期限を設定することで、例外が発生した場合にプログラムがロックを解除できないという問題を回避することができます。同時に、文字列の値をランダムな値（通常はタイムスタンプ付き）に設定することもできます。この方法では、プログラムAのブロックは、ロックの有効期限以上の時間が自動的に解放され、その後、プログラムBは、ロックを解放するスレッドAであるロックを再取得し、プログラムBのロックは、この時間をリリースしました。

redis2.6以降では2.8でsetディレクティブにset supermarket timeオペレーションが追加され、値とタイムアウト時間をアトミックオペレーションに設定できるようになりました。しかし、まだタイムアウト後に2つのスレッドが同時にロックを保持する問題を解決することはできませんし、ロックの削除の問題もあります、ノードの削除はアトミック操作ではないため、同じのランダムな値を比較すると、まだタイムアウトがあるかもしれない、スレッドAのロックは、タイムアウトが終了したときに削除され、ロックのランダムな値を比較すると、削除する準備が整いましたが、その後、タイムアウトが終了し、その後、スレッドBは、ロックを取得し、この時点でスレッドAは、delを実行し、その後、スレッドAのロックが削除されます。そしてスレッドAがdelを実行すると、Bのロックが削除されます。つまり、luaスクリプトを使って、比較操作と削除操作を同じアトミック操作にすることができます。つまり、redisのロックは時間のかかる処理を実行するのには適していないのです。

Redlockアルゴリズムの考え方は、マスターとスレーブの関係を持たない複数のインスタンスのロックを取得することであり、半数のノードにsetコマンドを送信してロックを追加し、半数以上のノードのロックが成功してから成功とみなします。半数以上のノードにロックが設定されます。複数のノードが関係するため、単一ノードの場合よりもパフォーマンスは確実に低下します。

REDISメッセージキュー

• 非同期キュー

  あなたはキューとしてリストを使用することができます、あなたは、キューが空の場合、スレッドは、パフォーマンスを保存し、トレーニングのラウンドを空にする必要はありませんので、ブロッキングリードを達成するためにblpop/brpopを使用することができますが、redisクライアントは、あまりにも長い間アイドルリンクは、サーバーが切断するためのイニシアチブを取る、この時間は、クライアントが例外をキャッチする必要があり、消費を継続するために再試行します。

• ディレイドキュー

  遅延キューは、zsetを使用して実装することができ、zsetの値として文字列にシリアライズされたメッセージは、スコアとして有効期限、zetの機能は、一意であり、順序付けされ、その後、処理するタスクの有効期限を取得するzsetをポーリングするために複数のスレッドを使用し、可用性のために複数のスレッドは、ハングアップした場合には、少なくとも1つのスレッドに対処し続けるためにあります。それは複数のスレッドの呼び出しが含まれるため、この時間は、jedis zremメソッドを使用することができます、zremメソッドは、スレッドの所持によって、この要素の成功の削除は、実際には、それはポップのリストと同じである場合、zsetの1つまたは複数のメンバーを削除するために使用され、ポップすることです、この場合には、zrangebyscoreを使用することができますキューに現在に取得します！すでにタスクの時間に到着し、その後、順序が消費されることができるように、zremポップをトラバース、遅延キューの実装です。

ブルームフィルタ

これは、キャッシュヒットを防ぐために使用することができます、存在しないキーのシナリオのクエリの数が多いので、クエリが存在しないキーの数をフィルタリングする必要がある場合は、このスキームを使用することができます。guavaのメモリベースのブルームフィルタを使用することができますが、それはメモリベースであり、再起動に失敗し、分散シナリオに適用することはできません、redisのブルームフィルタは、拡張することができ、再起動失敗の問題はありませんが、ネットワークioが必要です。

原理は、実際には、複数のハッシュ関数の操作のためのキーであり、その後、内部のビットマップにマッピングされるので、内部のビットマップ内のこのキーは1の複数のビット値があるかもしれないので、彼の特性は、キーが存在しない場合は、ビットマップ、瞬間を見つけることができますが、ハッシュと他のキーの重複の結果は、その場合キーが存在するかどうかを判断することはできませんので、偽陽性率の問題があります。誤検出率は、ハッシュ関数とビットマップのサイズに関連しています。

k=0.7*f=0.6185^二つの入力があり、nは予想される要素数、もう一つはエラー率fです。

実際の要素数が期待される要素数を上回る場合、次のような計算式があります。tが大きければ大きいほど、誤差は大きくなります。

scan Bigkey Scan

コマンドのredisデフォルトのクエリのキーのリストは、キーのパターンである、つまり、正規表現に一致するように、キーは、検索のトラバーサルの原則は、キーのマッチの数千からパターンを見つけたい場合は非常に時間がかかり、redisはシングルスレッドであり、キーの操作は、他のスレッドがブロックされます。キーの欠点：

1. オフセット制限のようなページングパラメータがないため、式を満たすすべての条件を一度に検索することになります。
2. キーはO(n)の複雑さを持つ探索ロジックです。この結果、シングルスレッドになり、他のリクエストに応答できなくなります。

redis2.8ではscanコマンドが追加され、スキャン範囲、マッチングモード、開始点カーソルを設定できるようになったので、一括でクエリを実行できるようになりました。しかし、クエリ処理ではデータも挿入されるため、重複が発生する可能性があり、データの添え字が移動するため、クライアント側で重複を削除する必要があります。

通常のビジネス展開では、大きなKEYは避けるようにしましょう。

redisブロックの理由

1. キーの削除を含むような、無理なビッグキーを使用したデータ構造。
2. CPU
3. 永続的なブロッキング、rdbフォーク・サブスレッド、aofによる毎秒のディスク・フラッシュなど。

キャッシュ侵入

• 原因：システムに存在しない値へのリクエストは、キャッシュクエリをミスさせてデータベースに侵入する悪意のある攻撃である可能性が高いです。
• 解決策：あなたは、データベースを要求する必要はありませんが、無駄なデータの多くをキャッシュすることができるように、存在しないキーの値をキャッシュすることができ、値はnullです。一つは、すでに存在する値をキャッシュできるように、ブルームフィルタを使用することができますし、それが存在しない場合は、直接拒否することができ、無駄なキーを格納する必要はありません。

キャッシュヒット

• 理由：1つ以上のホットキーが無効になると、キャッシュバリアに穴を開けて直接データベースにリクエストするようなものです。
• 解決策は：キャッシュが更新されると、あなたは、以下に説明する二重の書き込み一貫性の問題が含まれ、更新する相互排除ロックを使用することができます同じデータの要求は、データベースに同時に要求されません。2番目は、ランダムな回避を使用することです、それが失敗したときに一定期間のランダムな睡眠は、それが更新するために再び更新ロックを取得するために失敗した場合、再度クエリを再試行します。3つ目は、大量のホットキーが同時に失敗した場合、大量のキー失敗を避けるためにキャッシュのタイムアウトに乱数を設定する必要があります。

キャッシュ雪崩

• 原因：実際には、キャッシュ雪崩はまた、大規模なキーの障害が原因で、実際には、ホットキーの障害が大量にまた、キャッシュハングに加えて、キャッシュ雪崩として分類することができます、また、データベースにアクセスするすべての要求につながります。解決策：高速障害直接メルトダウンを使用して、データベースの圧力を減らすために、マスタースレーブまたはサービスの高可用性を確保するためにクラスタモードを使用することができます。

キャッシュ・ダブル書き込みコヒーレンス

キャッシュ＋データベースの読み書きモード：

• キャッシュを最初に読んで、キャッシュはありませんし、データベースを読んで、キャッシュにデータを取り出し、対応する結果を返しながら。
• 更新の際は、まずデータベースを更新し、次にキャッシュされたデータを削除します。

時にはキャッシュされたデータを計算する必要があるため、データを削除する必要がある理由は、遅延ロードの考えに基づいている、更新される可能性があり、キャッシュされたデータを取得する必要がない場合は、この時間は直接キャッシュ1に計算した後、戻り時間に影響を与える、コンピューティングリソースの無駄。

二重書き込みコヒーレント読み出しの場合は、相互排他ロックを使用して、複数のスレッドが同時にキャッシュを操作するのを避けることができます。

public static String getData(String Key){
	String result = getDataByKV(Key);
 if(StringUtils.isBlank(result)){
 	if(reenLock.tryLock()){
 	result = getDataByDB(Key);
 }
 if(StringUtils.isBlank(result)){
 	setDataToKV(Key,result);
 }
 //ここでは、以下の実際のシナリオが最終的に公開される。
 reenLock.UnLock();
 }else{
 	//マルチスレッドの競合を避けるため、データを取得する前にスレッドをしばらく休止させる。
 	Thread.Sleep(1000L);
 result = getData(Key);
 }
 return result;
}

ホットキーアクセスチルト

キーがクラスタ内の1つのノードにある場合、プレッシャーは1つのredisインスタンスに偏ります。

解決策

• ローカルキャッシュに直接アクセスできるように、ローカルキャッシュポリシーであるguavaをキャッシュに使用します。
• スライシングアルゴリズムの使用は、ホットキー、または接尾辞に接頭辞を追加するには、redisインスタンス数N M回にホットキーの数は、実際には、ハッシュのスライスがキーの数にハッシュされるように、倍数で成長することです、情報の多重度は、アクセス圧力を広げるためにアクセスのランダムスライスを実行するために使用することができます。

REDISアプリケーションのシナリオ

1. セッションキャッシュ
2. リーダーボード/カウンター
3. /
4. pub/sub
5. Geohash近くの人
6. リミッター