Redisの概要

Redis の概要#

基本データ構造#

string文字列
listリスト
set集合
hashハッシュ辞書
zsetソート済み集合

string 文字列#

Redis の文字列は変更可能な文字列で、メモリ内ではバイト配列の形式で存在し、内部構造はJavaのArrayListに似ています。
メモリの割り当てを減らすために、事前に冗長なスペースを割り当てる方法を採用していますが、文字列を作成する際には冗長なスペースは多く割り当てられません。なぜなら、ほとんどの場合、append操作を使用して文字列を変更しないため、文字列の拡張によるメモリの再割り当ては発生しません。
拡張時、1M 未満の拡張は直接倍増し、1M 以上の場合は毎回 1M のメモリが追加され、文字列の最大長は 512M です。
文字列の底層には 2 つのストレージ方式があり、特に短い場合はemb(embstr)形式で保存され、長い場合はraw形式で保存されます。

list リスト#

Redis のリストはリンクリスト構造であり、配列ではないため、挿入と削除が比較的速いですが、インデックスの位置決めは遅く、相対的に要素の検索も遅くなります。
初期バージョンでは、リスト要素が少ない場合、連続したメモリを使用して保存され、つまりziplist圧縮リストの構造が実装されます。要素が多い場合は、通常の双方向リンクリスト LinkedList の構造を使用します。しかし、リンクリストに付随するポインタが占有するスペースの消費問題のため、後にquicklist高速リンクリストの構造が代わりに使用されました。

quicklist 高速リンクリスト#

quicklistはziplistとlinkedlistの混合体であり、linkedlistをセグメントに分割し、各セグメントはziplistを使用してコンパクトに保存され、複数のziplistが双方向ポインタで接続されています。

quicklist 内部では、デフォルトで単一の ziplist の長さは 8k バイトであり、設定パラメータlist-max-ziplist-sizeによって決定され、規定の長さを超えると新しいものが作成されます。
メモリスペースをさらに節約するために、Redis は ziplist を圧縮ストレージし、LZFアルゴリズムを使用して圧縮し、圧縮の実際の深さは設定パラメータlist-compress-depthによって決定されます。

一般的な操作:
Redis のリスト構造は、非同期キューとしてよく使用されます。処理を遅らせる必要があるタスク構造体を文字列にシリアライズして Redis のリストに詰め込み、別のスレッドがこのリストからデータをポーリングして処理します。

> rpush
> lpop
> rpop

# 以下の操作はO(n)操作であり、慎重に使用してください
> lindex   # 指定したインデックス位置の値を取得
> lrange   # 指定したインデックス範囲の値を列挙
> ltrim books 1 -1  # booksリストのインデックス【1から-1】の範囲の値を保持

hash ハッシュ#

Redis の hash の実装は Java の HashMap の実装に基本的に似ており、底層も配列 + リンクリストのデータ構造に基づいています。
異なる点は:

Redis の辞書の値は文字列のみです。
拡張条件が異なります。
Java の HashMap の rehash 操作は一度にすべて rehash します。Redis は高性能のため、サービスをブロックできないので、漸進的rehash戦略を採用しています。

拡張実装#

拡張条件:
一般的に、要素の数が一次元配列の長さに達すると拡張が行われ、新しい配列は元の 2 倍になります。ただし、Redis がbgsave（バックグラウンドで非同期にスナップショット操作を実行して RDB 永続化）を行っている場合、メモリページの過剰な分離（Copy On Writeメカニズム、詳細は: COW 牛！Copy On Write メカニズムを理解する）を減らすため、Redis は拡張をできるだけ避けますが、hash テーブルが非常に満杯で、配列の長さの 5 倍に達した場合は強制的に拡張を行います。

拡張実装:
漸進的 rehash は rehash の同時に新旧 2 つの hash 構造を保持し、クエリ時には両方の hash 構造を同時にクエリし、その後の定期的なタスクや hash 操作命令の中で、徐々に旧 hash の内容を新しい hash 構造に移行し、移行が完了したら新しい hash 構造を使用します。

一般的な操作:

> hset
> hmset # バッチset
> hget
> hgetall # entries(), すべてのkey、valueを同時に取得

set 集合#

Redis の set 集合は Java のHashSetに似ており、内部実装は特別な辞書に相当し、要素はすべて key として保存され、value はすべて空値です。内部のキーと値のペアは無秩序で一意です。

一般的な操作: sadd,spop,smembers,sunionなど
set 構造は、重複排除機能があるため、アクティビティの当選者 ID を保存するのに使用できます。

zset#

Java の SortedSet と HashMap の組み合わせに似ており、一方では set で内部の value の一意性を保証し、もう一方では各 value にスコアを割り当てて、この value のソートの重みを表します。
実装方式:

ziplist：要素数が 128 未満で、各要素の長さが 64 バイト未満の 2 つの条件を満たす場合にこの構造を使用します。
skiplist：上記の 2 つの条件を満たさない場合は、スキップリストを使用し、具体的には map と skiplistmap を組み合わせて member から score へのマッピングを保存します。これにより、O (1) の時間内に member に対応するスコアを見つけることができます。skiplist は小さい順にスコアを保存し、skiplist の各要素の値は [score,value] のペアです。

一般的な操作: zadd,zrange,zrem,zcardなど

スキップリスト#

リンクリスト + 多層インデックス

考察：なぜスキップリストを使用するのか、赤黒木（平衡二分木）ではないのか？

両者の時間計算量は同じですが、スキップリストの実装はより簡単です。
同時に要素を挿入または削除する場合、平衡二分木は再バランス操作を行う必要があり、この操作は木の他の部分に影響を及ぼす可能性がありますが、スキップリストの操作はより局所的な影響を与え、性能がわずかに向上します。
ZRANGEコマンドのような範囲検索を使用する場合、スキップリスト内の双方向リンクリストを利用して便利に操作できます。また、キャッシュ局所性（cache locality）もあり、効率は平衡木に劣りません。

参考リンク:

Redis のスレッド IO モデル#

Redis は単一スレッドであり、新しいバージョンではマルチスレッドが導入されていますが、マルチスレッド部分はネットワークデータの読み書きとプロトコル解析を処理するためのものであり、ネットワーク IO の効率を向上させます。

単一スレッドの Redis がなぜそんなに速いのか#

大部分はメモリ操作であり、非常に速いです。
単一スレッドであるため、コンテキストスイッチやリソース競合の問題を回避できます。
非ブロッキング IO - 多重化を採用しています。

参考リンク#

Redis の永続化#

Redis は永続化のために 2 つの方法を提供しています:

RDB スナップショット：指定された時間間隔内でデータのスナップショットを保存し、全体のバックアップを行います。
AOF ログファイル：メモリ内のデータ変更の指令ログを記録し、連続的な増分バックアップを行います。

Redis4.0 以降は混合永続化機能を提供しています。

RDB#

関連設定:

# 時間戦略、定期的に自動トリガー
save 900 1
save 300 10
save 60 10000

# ファイル名
dbfilename dump.rdb

# ファイル保存パス
dir /home/work/app/redis/data/

# 永続化にエラーが発生した場合、主プロセスは書き込みを停止するか
stop-writes-on-bgsave-error yes

# 圧縮するか
rdbcompression yes

# インポート時にチェックするか
rdbchecksum yes

RDB 永続化のトリガーには 2 つの方法があります：手動トリガーと Redis の定期トリガー。

手動トリガー#

save: 現在の Redis サーバーをブロックし、永続化が完了するまで待機します。オンラインでは使用を禁止します。
bgsave: 子プロセスをフォークし、子プロセスが永続化プロセスを担当するため、ブロックは子プロセスをフォークする際にのみ発生します。

save コマンドはあまり使用されず、bgsave の実行フローは以下の通りです:

bgsave の原理

fork: redis は bgsave 操作を行うために子プロセスをフォークします。
cow: copy on write、子プロセスが作成された後、親子プロセスはデータセグメントを共有し、親プロセスは引き続き読み書きサービスを提供し、書き込みの汚れたページデータは徐々に子プロセスから分離されます。

自動トリガー#

自動トリガーのシナリオ:

設定ファイルに設定されたsave m nルールに基づいて自動トリガーされます。
スレーブノードが全体をコピーする際、マスターノードは rdb ファイルをスレーブノードに送信してコピー操作を完了し、マスターノードはbgsaveをトリガーします。
debug reloadを実行する際。
shutdownを実行する際、AOF が有効でない場合もトリガーされます。

AOF#

関連設定:

# AOFを有効にするか
appendonly yes

# ファイル名
appendfilename "appendonly.aof"

# 同期方式
appendfsync everysec

# AOFの再書き込み中に同期するか
no-appendfsync-on-rewrite no

# 再書き込みトリガー設定
auto-aof-rewrite-percentage 100
auto-aof-rewrite-min-size 64mb

# AOFを読み込む際にエラーが発生した場合の処理
aof-load-truncated yes

# ファイル再書き込み戦略
aof-rewrite-incremental-fsync yes

AOF の全体の流れは大まかに 2 つのステップに分けられます。1 つ目はコマンドのリアルタイム書き込み（appendfsync everysec設定の場合、1 秒の損失があります）、2 つ目は AOF ファイルの再書き込みです。

Redis はクライアントからの変更指令を受け取った後、パラメータの検証を行い、論理処理を行い、問題がなければ、その指令テキストを AOF ログに即座に保存します。これは指令を実行してからログをディスクに保存することを意味します。この点は leveldb、HBase などのストレージエンジンとは異なり、これらは先にログを保存してから論理処理を行います。

AOF 再書き込み#

Redis は長期間の運用の過程で、AOF のログが次第に長くなります。インスタンスがクラッシュして再起動すると、全体の AOF ログを再生するのは非常に時間がかかり、長時間 Redis が外部にサービスを提供できなくなります。したがって、AOF ログをスリム化する必要があります。

Redis はbgrewriteaofコマンドを提供して AOF ログをスリム化します。その原理は、子プロセスを開いてメモリを遍歴し、一連の Redis の操作指令に変換し、新しい AOF ログファイルにシリアライズします。シリアライズが完了した後、操作中に発生した増分 AOF ログをこの新しい AOF ログファイルに追加し、追加が完了したら即座に古い AOF ログファイルに置き換えます。

ログの損失#

AOF ログはファイルの形式で存在し、プログラムが AOF ログファイルに書き込み操作を行うと、実際には内容がカーネルによってファイル記述子に割り当てられたメモリキャッシュに書き込まれ、その後カーネルが非同期でデータをディスクにフラッシュします。したがって、マシンが突然クラッシュすると、ログ内容が完全にディスクに書き込まれる前にログが失われる可能性があります。

Linux のglibcはfsync(int fd)関数を提供して、指定されたファイルの内容を強制的にカーネルキャッシュからディスクにフラッシュします。生産環境のサーバーでは、Redis は通常 1 秒ごとに fsync 操作を実行します。この周期は設定可能です。これはデータの安全性と性能の間で妥協を行い、高性能を維持しつつ、できるだけデータの損失を少なくするためです。

参考リンク#

Redis の永続化原理を理解する

Redis の同期メカニズム#

Redis は主従同期と従従同期を使用できます。最初の同期時、主ノードは一度 bgsave を行い、その後の変更操作をメモリバッファに記録し、完了後に rdb ファイルを全体同期して複製ノードに送信します。複製ノードが受け取った後、rdb イメージをメモリにロードします。ロードが完了した後、主ノードに通知して、期間中の変更操作の記録を複製ノードに同期して再生することで同期プロセスが完了します。

Redis トランザクション#

Redis の単一スレッドモデルのおかげで、そのトランザクションモデルは非常にシンプルです。

各トランザクションの操作には begin、commit、rollback があります。begin はトランザクションの開始を示し、commit はトランザクションのコミットを示し、rollback はトランザクションのロールバックを示します。

Redis は形式的にはほぼ同じで、multi/exec/discardです。multiはトランザクションの開始を示し、execはトランザクションの実行を示し、discardはトランザクションの破棄を示します。

Redis のキャッシュ失効メカニズム#

キャッシュシステムとして、無効なデータを定期的にクリーンアップする必要があり、主キーの失効と淘汰戦略が必要です。

期限切れ削除戦略#

redis は期限切れ時間が設定された各 key を独立した辞書に格納し、その後定期的にこの辞書を遍歴して期限切れの key を削除します。定期的な削除に加えて、惰性戦略を使用して期限切れの key を削除します。惰性戦略とは、クライアントがこの key にアクセスする際に、redis が key の期限切れ時間をチェックし、期限切れであれば即座に削除することです。定期削除は集中処理であり、惰性削除は零散処理です。

6 つの淘汰戦略#

Redis のメモリがmaxmemory制限を超えると、メモリのデータがディスクと頻繁に交換され始め（スワップ）、これにより Redis の性能が急激に低下します。したがって、Redis はいくつかの淘汰戦略を提供しています:

noeviction: 書き込み要求を続けてサービスしません（DEL 要求は引き続きサービスされます）。読み取り要求は引き続き行えます。これによりデータの損失を防ぐことができますが、オンラインのビジネスが継続できなくなります。これはデフォルトの淘汰戦略です。
volatile-lru: 期限切れ時間が設定された key を淘汰し、最も使用されていない key が優先的に淘汰されます。期限切れ時間が設定されていない key は淘汰されず、永続化が必要なデータが突然失われることはありません。
volatile-ttl: 期限切れ時間が設定された key を淘汰し、key の残りの寿命ttlの値が小さいほど優先的に淘汰されます。
volatile-random: 期限切れ時間が設定された key を淘汰しますが、淘汰される key は期限切れ key 集合の中からランダムに選ばれます。
allkeys-lru: volatile-lru とは異なり、この戦略で淘汰される key オブジェクトは全体の key 集合であり、期限切れ key 集合だけではありません。これにより、期限切れ時間が設定されていない key も淘汰されます。
allkeys-random: 全体の key 集合からランダムに淘汰されます。

Redis のハッシュスロット#

Redis クラスターは一致性ハッシュを使用せず、ハッシュスロットの概念を導入しています。Redis クラスターには 16384 個のハッシュスロットがあり、各 key は CRC16 チェック後に 16384 で割った余りによってどのスロットに配置されるかが決まります。クラスターの各ノードは一部のハッシュスロットを担当します。

Redis のパイプライン#

複数のコマンドをサーバーに送信し、応答を待たずに、最後に一度にその応答を読み取ることで IO 効率を向上させます。

Redis のクラスター#

Redis Sentinel は高可用性に焦点を当てており、master がダウンした場合に自動的に slave を master に昇格させ、サービスを継続します。
Redis Cluster は拡張性に焦点を当てており、単一の Redis のメモリが不足した場合、Cluster を使用してシャーディングストレージを行います。

キャッシュシーンの問題#

キャッシュ貫通#

クエリするデータがキャッシュとデータベースの両方に存在しない場合、悪意のある高並列リクエスト攻撃によりバックエンド DB がクラッシュする可能性があります。

解決策:

空の値をキャッシュする：最初のクエリ後、存在しない key に対してその値を空の値として設定し、以降のこの key のリクエストは直接空を返しますが、適切な期限を設定する必要があります。
BloomFilter: ブルームフィルターを利用して要素（特定の key）が存在するかどうかを判断します。

キャッシュ雪崩#

キャッシュを設定する際に同じ期限を設定し、ある時点で大規模なキャッシュの無効化が発生し、データベースをクエリすることになり、さらにデータベースに過剰な負荷がかかる可能性があります。

解決策:

期限切れ時間の設定を分散させる：例えば、元の期限切れ時間設定にランダム値を加えることで、キャッシュの期限切れ時間の重複率を低下させます。
制限とダウングレードを行い、バックエンド DB がリクエストの過剰な負荷でクラッシュしないようにします。
ロックやキューを使用して、同時に多くのリクエストがバックエンド DB に落ちるのを避けます。
各キャッシュデータの value にキャッシュマーク時間を追加し、この時間は実際に設定されたキャッシュ時間よりも早く、キャッシュマークが失効した場合、他のスレッドにキャッシュを更新するよう通知し、実際には更新が完了するまで古いキャッシュデータを返すことができます。

キャッシュ撃破#

ある時点でこのキャッシュが期限切れになり、ちょうどその時に多くのキャッシュに対するクエリリクエストがあり、キャッシュが無効になったことを発見した後、バックエンド DB からデータをロードしてキャッシュを更新します。リクエスト量が過剰な場合、DB に過剰な負荷がかかり、クラッシュする可能性があります。

注意:
キャッシュ撃破とキャッシュ雪崩は異なり、前者は単一の key に対して、後者は多くの key に対してです。

解決策:
キャッシュ雪崩を参考にし、類似の方法を使用します。

キャッシュ予熱#

システムがオンラインになると、関連するキャッシュデータをキャッシュにロードして、最初のリクエストが DB からのロード更新キャッシュを避けます。

キャッシュ更新#

先にデータベースを更新してからキャッシュを更新#

適用しません。以下の問題があります：

スレッドが安全でなく、汚れたデータを引き起こす可能性があります。例えば、複数の書き込みリクエストが到達し、本来は最後の書き込みリクエストデータをキャッシュに更新するはずですが、ネットワークの変動により、実際にキャッシュに更新されるデータは前のいずれかの書き込みデータになる可能性があります。
書き込みが多く、読み取りが少ないシーンには適しておらず、キャッシュが頻繁に更新され、性能が無駄になります。

先にキャッシュを削除してからデータベースを更新#

問題分析:
同時にリクエスト A が更新操作を行い、別のリクエスト B がクエリ操作を行うと、次のような状況が発生します:

リクエスト A が書き込み操作を行い、キャッシュを削除します。
リクエスト B がキャッシュが存在しないことを発見します。
リクエスト B がデータベースをクエリし、旧値を取得します。
リクエスト B が旧値をキャッシュに書き込みます。
リクエスト A が新しい値をデータベースに書き込みます。

このような状況では不一致が発生します。また、キャッシュに期限を設定しない場合、そのデータは永遠に汚れたデータとなります。

解決策: 遅延二重削除戦略

先にキャッシュを削除します。
次にデータベースに書き込みます（この 2 つのステップは元のままです）。
短時間（例えば 1 秒）休眠し、再度キャッシュを削除します。

これにより、1 秒以内に発生した汚れたデータが削除されます。また、この休眠時間はビジネスの実際のシーンに基づいて評価する必要があります。

先にデータベースを更新してからキャッシュを削除（一般的な戦略）#

失効：アプリケーションはまずキャッシュからデータを取得し、得られなければデータベースからデータを取得し、成功したらキャッシュに保存します。
ヒット：アプリケーションはキャッシュからデータを取得し、取得できたら返します。
更新：まずデータをデータベースに保存し、成功したらキャッシュを失効させ、キャッシュを削除します。

問題分析：
同様に、2 つのリクエストがあると仮定します。1 つのリクエスト A がクエリ操作を行い、もう 1 つのリクエスト B が更新操作を行うと、次のような状況が発生します。

キャッシュがちょうど失効します。
リクエスト A がデータベースをクエリし、旧値を得ます。
リクエスト B が新しい値をデータベースに書き込みます。
リクエスト B がキャッシュを削除します。
リクエスト A が取得した旧値をキャッシュに書き込みます。

データの不一致が発生する前提条件は、ステップ 3 の書き込みデータベース操作がステップ 2 の読み取りデータベース操作よりも速いことですが、データベースの読み取り操作は書き込み操作よりも速いため、この確率は非常に低いです。