Redis公式ドキュメントのメモ

モチベーション

NoSQLの勉強をしていて、中身の実装方法とかをもう1段階理解を深めたいと思った。Redisを選んだのは本番環境でも使っていて、シンプルかつパワフルであまり嫌いな人を聞いたことが比較的ないし、一番とっかかりやすそうだったから。あとは、あまりRedisに関して深ぼった本を知らないから。
ソースコードをできれば読みたいが、C言語で断念しそうなので、一旦様子見。

感想としては、公式ドキュメント読んだだけでも、だいぶ理解が変わったので読んでよかった。データ構造・アルゴリズムやDBの基礎的な本を読んでたおかげで、かなり理解しやすくなったので、やはりCSの基礎は重要なんだなと感じた。

公式ドキュメント

この記事は、英語だがコンパクトにまとまっていた。

Overview Of Redis Architecture

読んで気になった箇所のメモ

expire

UNIX timestamp(ms単位)を使って比較している。

expireするタイミングは2種類ある。

passive: キーにアクセスされたとき
active: 1秒に10回以下を実行
1. expireが設定されているキーの集合から20個取得
2. そのうち、expireしてるものは削除
3. もし25%以上がexpireしていた場合は、1から再度実行

削除するときは、AOLには DELコマンドのログを残す。

メモリの上限とアルゴリズム

maxmemory でデータ容量の最大値を指定できる。

上限に到達したときの挙動は maxmemory-policyで指定できる。

ポリシー	説明
noeviction	エラーを返す（主には書き込みやDELなどの操作）
allkeys-lru	LRUで削除
volatile-lru	expireがセットされているデータをLRUで削除
allkeys-random	ランダムで削除
volatile-random	expireがセットされているデータをランダムで削除
volatile-ttl	ttlが短いデータから削除
volatile-lfu	expireがセットされているデータをLFUで削除
allkeys-lfu	LFUで削除

※ volatile-*は削除できるデータがない場合は、エラーを返す。

RedisのLRUアルゴリズム

厳密なLRUを実現するにはメモリが必要なため、Redisでは擬似的なLRUアルゴリズムを実装している。 maxmemory-samples で指定した数のサンプルを取得して、それらの時間が一番古いものを削除する。

LFU(4.0からサポート)

LRUのように擬似的な実装がされている。Morris Counterという1オブジェクトあたり数ビットだけでオブジェクトのアクセス頻度がわかる確率的なカウンターを利用している。

頻度は0-255で与えられ、lfu-log-factorで頻度を増加させるのにどれだけのアクセスが必要かを指定し、lfu-decay-timeで頻度が減衰する時間を指定する。

トランザクション

悲観的ロック

MULTI- EXEC コマンドで、順番に連続で実行されることが保証される（シングルスレッドなので独立性が担保）。アトミック性も保証できる。

AOLでログに書き込む際には、一度の write(2)システムコールでディスクにsyncしようとするが、Redisサーバやプロセスが途中でクラッシュしたりした場合は、トランザクションの一部のみ書き込まれる可能性がある。その場合は、リスタートしようとするとエラーで終了するので、 redis-check-aofで部分的に書き込まれたトランザクションを削除してリスタートできる。

楽観的ロック

WATCHコマンドを使えば実現できる。 WATCHコマンドを実行してから、 EXECを実行するまでに修正された場合は、エラーが発生する。

WATCHコマンドの注意事項

WATCHしたクライアントによってMULTI-EXEC間に書き換えられた場合は失敗する。
WATCHしたクライアントによってMULTI前に書き換えられた場合は成功する。
WATCHからEXECまでの間にkeyがexpireされた場合は、そのまま実行される。
コネクションが切れた場合は、UNWATCHの状態になる

クライアントサイドキャッシュ

Redis6.0からサポート。クライアント側で

default mode:
- サーバ側で、どのキーがクライアントでキャッシュされているかを管理して、修正されたらメッセージを送り、クライアントがキャッシュを削除する
- サーバ側で、どのクライアントがどのキーをキャッシュしているかを管理しないといけないので、サーバ側で余分にメモリが必要
Broadcasting mode
- 修正されたら、クライアントキャッシュを削除するようにクライアントにメッセージを送る
- subscribeするprefixを指定することができる
- サーバサイドでは、prefixがマッチするクライアントに対してメッセージを送り、keyを管理する必要はない。

コネクションが切れた場合は、キャッシュを削除する。

大量のデータのインサート

ファイルを作って、pipeモードで挿入するのが良い。

アプリケーションのloopで挿入すると、round-trip分の無駄な通信が発生するので、遅い。

cat data.txt | redis-cli --pipe

パーティション

実装方法

クライアントサイド
プロキシ
- Redisに直接リクエストを送るのではなく、プロキシを挟んで、プロキシが振り分ける。
- twemproxyなどがある。
クエリールーティング
- ランダムにインスタンスに送って、インスタンスが正しいノードにリダイレクトする。
- Redis Clusterは部分的に採用していて、直接リダイレクトはせず、クライアント側にリダイレクトを指示する。

デメリット

複数のキーにまたがる操作がサポートされていない
複数のキーにまたがるトランザクションは不可能
1つのキーで大きなデータを持つ場合は分離できない
ノードの増減でリバランスが走るので、複雑。Pre-shardingを使えば解決できる

データストアとして使う場合は、リバランスを行うにはダウンタイムが発生するので、キーとノードのmappingを固定しなければならない。キャッシュとして使う場合は、オンラインでリバランスを実行できる。

Presharding

リバランスを行うのは複雑なので、事前にシャーディングを行えばよい。

Redisノードは軽いので、一つのサーバで始める場合でもRedisノードを多数立ち上げて、シャーディングを行っておく。リソースの追加が必要になれば、新しいサーバにRedisノードを移せばよい。

実装

Redis Cluster: 基本的にはデファクト
Twemproxy: 少しの複雑性を伴う。複数ノード用意すればSPOFにならない
consistent hashing

セカンダリインデックス

ZSETはスコアが同じ場合は値の辞書順にソートされる。

ZRANGEBYLEX を使えば、値から絞ることができる

検索ワードのサジェスト
フォロー関係のグラフ

データ型

Redis keys

長いキーは良くない
- メモリを喰うし、検索にも時間がかかる
- 長いならハッシュ化した方がよい
最大サイズは512MB

SETコマンド

すでに値があるかどうかで保存するかどうかのオプションがある。

# mykeyに値がないとき
> set mykey newval nx
(nil)
> set mykey newval xx
OK

List

データ構造としてはLinkedListで実装されているので、先頭や最後尾の要素の取得、挿入、削除を一定時間で取得できる。中間の要素を取る場合でパフォーマンスが重要な場合はSortedSetsを検討すべき。

pollingを実装する場合は、 BRPOPや BLPOPが便利。

集合型データの場合は、要素挿入時にキーが存在しない場合は自動的に初期化され、要素削除時にキーが空になる場合は自動的に削除される。また、存在しないキーに対して LLENなどの読み込みコマンドや削除系のコマンドを実行すると、存在するかのように振る舞う（この場合0を返したりする）。

Sorted sets

並び順は、スコア -> 値の辞書順の順番で評価される。

スキップリストとハッシュテーブルの両方を持つデータ構造からなる。そのため、追加時の計算量は O(log(N))で、取得時はすでにソート済みなので何もしなくてよい。

Bitmaps

主な用途は以下

リアルタイム分析
- 例えば1時間ごとに、アクセスしたかどうかを記録
省スペースかつ高パフォーマンスなboolean値の保存

Twitter demo

PHPの例で、一つのLinuxサーバで10万リクエストを100のクライアントで並列で実行すると、平均で5msのレイテンシーのパフォーマンスが出たそう。

Replication

レプリケーションがどのように行われるか

レプリカがマスターにつながれると、 PSYNCコマンドでレプリケーションIDを渡して、差分のコマンドを受け取り、同期する。

マスター側にレプリケーションIDから差分がわからない場合は、以下のようにフルバックアップをとる。

スナップショットを作成するためにRDBファイルの生成を開始するとともに、新しいコマンドはバッファにため始める。
RDBファイルが完成したら、レプリカにファイルを送信し、レプリカはディスクに保存。
ディスクからメモリに読み込み終わった後にバッファに溜まったコマンドを受け取り処理をする。

Replication id

Replication idは、リスタートしたり、masterに昇格した際にランダムに生成される。offsetによってその間の時系列を把握できる。Replication idが切り替わる際には、2つ保持しておき、切り替わる前のデータをレプリカを

レプリカの接続状況によって書き込みを禁止する

データロスの可能性を減らすために、レプリカが一定以上に正常な場合にのみ書き込みを許可することができる。

Redisではレプリカがマスターに対してpingすることで死活監視を行う。マスターはレプリカが最後にpingした時刻を保存しておき、設定した時間内にpingされたかどうかで判定する。そのため、厳密なデータロスを防ぐことは保証されていない。

min-replicas-to-write: 接続が確認できるレプリカの最小数
min-replicas-max-lag: 最後にpingしてからどれぐらいのラグまでは正常な状態とみなすかどうか

expireの取り扱い

node間で時刻がずれていると、expireの扱いがノード間でずれてしまう可能性がある。

レプリカでは直接expireの処理は行わず、マスターがexpireしたDELコマンドを同期することでexpireさせる
しかし、同期が遅れてexpireしているべきオブジェクトをレプリカで読み込まれると矛盾が生じるため、データの整合性を担保できるように読み込み時のみ、論理的なexpireした結果をレプリカは返す

永続性

メモリが揮発する可能性があるので、永続性を担保するにはバックアップが必須

DBに保存する
- リカバリ時のパフォーマンスはよい
- データを一部失う可能性がある
- 大きなデータを書き込む際にCPU負荷が上がる
AOL: 全ログを保存する
- 確実に再現できる
- データ量はDBより大きくなってしまう
- fsyncの頻度によってパフォーマンスは左右される

セキュリティ

文字エスケープという概念がないから、NoSQLインジェクションは起こらない
シークレットはconfigに平文で保存して、Redisサーバにさえアクセスできなければ悪用されない。忘れたときは、そこを見ればいいので値は長い方がセキュア。
実行可能なコマンドを制限できる。もしくは rename-command を使って、空文字とかに上書いて実行できないようにする

Redis Sentinel

モニタリング、通知、自動フェイルオーバー、サービスディスカバリなどを提供し、Redisの可用性を向上させる仕組み。自身は分散システムからなっていて、複数のノードで監視することで死活監視の偽陽性を防いだり、自身の可用性を向上させられる。

設定によるが最低2つのノードで合意が得られるとフェイルオーバーを実行させるため、1つのノードが稼働しなくても問題ないように3つ以上のノードで構成すること。

Latency

ネットワーク

コネクションをできるだけ維持する
MSET, MGETなどのコマンドやパイプラインを使ってラウンドトリップを減らす

シングルスレッド

multiplexingを使って一つのプロセスで全リクエストを処理している。

Node.jsもシングルスレッドだがパフォーマンスは十分出ている。これは、システムコールでブロックされないように設計されているから。

厳密にはシングルスレッドではなく、遅いI/O処理をバックグラウンドで行っている。

コマンド

SORT, LREM, SUNIONなどのコマンドは速くはないので、必ずコマンドの計算量をドキュメントで確認すること。

KEYS は特にパフォーマンスが悪いので、あくまでもデバッグ目的で使うこと。代わりにSCANを使うこと。

AOF, disk I/O

AOFは write(2)と fdatasync(2)の2つのシステムコールを使う。

ディスクへの書き込みの頻度は appendfsyncの設定によって変わるが、他のプロセスでディスクI/Oがないようにするのが望ましい。

一般的にfsyncしている同じファイルへのwriteはブロックされる。 everysecに設定されてる場合、Redisではfsyncが行われてるとき2秒まではwriteの処理はバッファーしておくが、そのあとはwriteを実行するため、遅くなる可能性がある。

その他

Linuxではtransparent huge pagesをオフにすること。
expiresは同時刻で多数のオブジェクトのTTLを設定しないこと。
- Redisがexpireしたオブジェクトを削除するときに、通常20件サンプリングした中で、25%以上がexpireしていた場合は、25%以下になるまで削除し続けるため。

Redisクライアント

コネクションの最大数は設定で指定できる。ただし、ファイルディスクリプタの最大数が小さい場合は、異なる値に設定される（ログにエラーが出力される）。

タイムアウト

デフォルトではアイドル時間が長くても、コネクションは切れない設定になっている。

configで設定できるが、全てのコネクションをチェックするのにO(N)時間かかるので、パフォーマンスを優先して厳密な時間を保証はしていない。

シグナルハンドリング

SIGTERM, SIGINT
- 即座に終わるのではなく SHUTDOWNコマンドを実行したときと似た挙動を起こす
- コマンドの実行完了次第すぐに終了
- RDBファイルに保存失敗した場合は、終了しない
SIGSEGV, SIGBUS, SIGFPE, SIGILL
- ログファイルにバグレポートを生成
- シグナルハンドリングを解除して、自身で同じシグナルを送って終了する
RDBの子プロセス等がkillされた場合
- 永続性が担保できないので、READのみ受け付けて書き込み操作はエラーを返すようになる

次のアクション

ソースコード読むか、他のNoSQLを調べる。