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 ビット未満の条件を満たす場合にこの構造を使用します。
skiplist：上記の 2 つの条件を満たさない場合は、スキップリストを使用します。具体的には、map と skiplistmap を組み合わせて member から score へのマッピングを保存し、O (1) の時間で member に対応するスコアを見つけることができます。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 は fork を通じて子プロセスを作成し、bgsave 操作を行います。
cow: コピーオンライト、子プロセスが作成された後、親子プロセスはデータセグメントを共有し、親プロセスは引き続き読み書きサービスを提供し、書き込みの汚れたページデータは徐々に子プロセスから分離されます。

自動トリガー#

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

設定ファイルに設定された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 は高可用性に焦点を当てており、マスターがダウンした場合にスレーブを自動的にマスターに昇格させ、サービスを継続します。
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 の読み取りデータベース操作よりも短時間である必要がありますが、データベースの読み取り操作の速度は書き込み操作よりも遥かに速いため、この確率は非常に低いです。