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: 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 操作を実行します。周期 1 秒は設定可能です。これはデータの安全性と性能の間で妥協を行い、高性能を維持しつつ、できるだけデータの損失を少なくするためです。

参考リンク#

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 の読み取りデータベース操作よりも速いことですが、データベースの読み取り操作の速度は書き込み操作よりも遥かに速いため、この確率は非常に低いです。