Redis公式ドキュメントのメモ
モチベーション
NoSQLの勉強をしていて、中身の実装方法とかをもう1段階理解を深めたいと思った。Redisを選んだのは本番環境でも使っていて、シンプルかつパワフルであまり嫌いな人を聞いたことが比較的ないし、一番とっかかりやすそうだったから。あとは、あまりRedisに関して深ぼった本を知らないから。
ソースコードをできれば読みたいが、C言語で断念しそうなので、一旦様子見。
感想としては、公式ドキュメント読んだだけでも、だいぶ理解が変わったので読んでよかった。データ構造・アルゴリズムやDBの基礎的な本を読んでたおかげで、かなり理解しやすくなったので、やはりCSの基礎は重要なんだなと感じた。
この記事は、英語だがコンパクトにまとまっていた。
Overview Of Redis Architecture
読んで気になった箇所のメモ
expire
UNIX timestamp(ms単位)を使って比較している。
expireするタイミングは2種類ある。
- passive: キーにアクセスされたとき
- active: 1秒に10回以下を実行
- expireが設定されているキーの集合から20個取得
- そのうち、expireしてるものは削除
- もし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
パーティション
実装方法
- クライアントサイド
- プロキシ
- クエリールーティング
デメリット
- 複数のキーにまたがる操作がサポートされていない
- 複数のキーにまたがるトランザクションは不可能
- 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を調べる。