Dive Deep Redis ~ 入門から実装の確認まで

2021-06-01 2022-11-26

hayashier

Redis本を執筆しました。こちらも是非合わせてご覧ください。

---------------------------------------------------------------------------------------------------------------------------------------------------------

Redis(REmote DIrectory Server)

Redisは例えば以下の特徴を持つLLOOGGを元としたインメモリの非リレーショナルのデータベースです。

String, List, Hash, Set, Sorted Setに代表される豊富なデータ型
シングルスレッド処理
イベント駆動処理 by aeライブラリ
通常RESPプロトコルによるクライアント/サーバーモデルでリクエスト/レスポンス
データは条件を満たす場合にメモリ最適化されて保存。CPUとのトレードオフ
RAXを利用したメモリ利用量の最適化(Redis 4.0~)

この記事では、入門から始まり、実装をより意識することで深く理解することを目標としています。
以下の説明中の(*)マークは、特にVanilla Redisでの話となり、サービスとしてRedisが提供されている場合には工夫されていて挙動が異なるものもあります。

なお、合わせてRedisのソースコードの各種ファイルの概要についての詳細は以下の記事をご覧ください。

Redis / Memcached Source Code Reading – Overview –

RedisのGETコマンド実行時のソースコード中のフローの詳細については、以下の記事をご覧ください。

Dive Deep Redis Internals ~ GETコマンド実行時の動作 ~

レポジトリはこちらになります。

データ型

Basic

String
- コマンド例: SET,GET,STRLEN,APPEND,SETRANGE,SETNX,MSET,MGET
- 特徴
  - キーに値を関連づけるための最もシンプルなタイプ
  - バイナリセーフな文字列(SDSによる実装。jpegのような画像データを含むバイナリデータもシリアライズ化して格納できる)
- ユースケース
  - キャッシュ
  - カウンター
  - リアルタイムメトリクス
  - その他
    - HTML フラグメント
    - ページのキャッシング
List
- コマンド例: LPUSH,RPUSH,LINSERT,LRANGE,LPUSHX,RPUSHX,LPOP,RPOP,LINDEX,LTRIM,LSET,BLPOP,BRPOP
- 特徴
  - 文字列のコレクション。挿入された順序を保つ
- メリット/デメリット
  - メリット
    - 新しい要素をリストの先頭や末尾に追加する操作は定数時間で完了。
  - デメリット
    - 中間部分へのアクセスが遅い。特に大きなデータの中間部分で顕著
- ユースケース
  - ログ
  - キュー : キューのサービスとして提供されるもの(ResqueのようなRedisを利用しないもの)と比較すると、全体的に、高速で一度だけ届けられるメッセージの順番も保証されるメリットがあるが、データロスのリスクもある。
  - スタック
  - メッセージ通過
  - SNSの最新ツイート
  - Consumer-Producer パターンを用いたプロセス間通信。Producer はアイテムをリストに Push し、Consumer (通常 worker と呼ばれる) がアイテムを消費してアクションを実行する。
    - 例) resque や sidekiq といった人気のある Ruby ライブラリはバックグラウンドジョブを実行
Hash
- コマンド例: HMSET,HMGET,HGET,HSET,HEXISTS,HSETNX,HGETALL,HSCAN
- 特徴
  - フィールドと値のペアの集合
  - フィールドと、それに関連づけられた値から構成されるマップ。フィールドと値はどちらも文字列
- ユースケース
  - オブジェクトストレージ
    - ひとつのハッシュに put できるフィールド数に実質上の制限はないため(メモリが許す限り)、アプリケーションの様々な用途に利用可能
SET
- コマンド例: SADD,SISMEMBER,SREM,SCARD,SMEMBERS,SSCAN,SUNION,SUNIONSTORE,SINTER,SINTERSTORE,SDIFF,SDIFFSTORE
- 特徴
  - ユニークで、順序づけられない文字列のコレクション。
  - 指定された要素がすでに存在するかチェックしたり、複数のセット間で共通集合や和集合や差集合をとったり、セットに対して多くの操作が可能です。
- ユースケース
  - メンバーシップ、トラッキング
  - 投票管理、タグ管理
  - その他
    - オブジェクト間の関係を表現するのに有用(たとえば、タグを実装)
      - タグを付与したいすべてのオブジェクトごとにセットを用意することです。セットには、オブジェクトに関連するタグの ID をもたせます。
    - Web ベースのポーカーゲームを実装するのに、デッキをセットで表現(SPOPでランダムな要素を一つ取り除く)
Sorted Set(ZSET) : 1.2.0~
- コマンド例: ZADD,ZREVRANGE,ZINCRBY,ZREVRANK,ZSCORE,ZUNIONSTORE
- 特徴
  - ソート済みセットは、スキップリストとハッシュテーブルの両方を含むデータ構造で実装されています。そのため、ひとつの要素を追加するたびに Redis は O(log(N)) の計算量の操作を実行します。
  - Sets に似ているが、すべての要素にはスコアと呼ばれる浮動小数点数が関連づけられます。要素は常にスコアによりソートされており、Sets とは違い特定の範囲の要素を取り出すことができる。
  - ソート済みセットは、セットとハッシュの間に似ています。セットのように、ソート済みセットはユニークで繰り返しのない文字列要素から構成されます。一方で、セットの要素は順序づけされていませんが、ソート済みセットのそれぞれの要素は、スコアと呼ばれる浮動小数点数と関連づけられています。
- ユースケース
  - 順位表(leader boards)
  - アクティビティフィード
PubSub : 2.0.0~
- コマンド例: SUBSCRIBE,PUBLISH,UNSUBSCRIBE,PSUBSCRIBE,PUBSUB
- メッセージを送るPublishする対象と受け取るSubscribeする対象があり、チャンネルを通してメッセージがPublishされると、そのチャンネルをSubscribeしている対象にメッセージが送られる
Bitmap : 2.2.0~
- コマンド例: SETBIT,GETBIT,BITCOUNT,BITIOP(AND,OR,XOR,NOT)
- 特徴
  - 実際のデータ型ではなく、文字列型で定義されたbit志向の操作の集合
  - 特殊なコマンドを使って、文字列値をビット配列のように扱うことができる。個々のビットをセットまたはクリアしたり、1 がセットされているビットの数を数えたり、最初にセットされている、またはアンセットされているビットを探したり、その他いろいろ。
  - bitmapを複数キーに分割してシャーディングすることも容易(modulo計算)
  - 内部的にはString型
- メリット
  - メモリ空間効率が良い
- デメリット
  - 実装がわかりにくく可読性が落ちる可能性
- ユースケース
  - 全種類のリアルタイム分析
  - オブジェクトIDに関連づく、空間効率が高いが、高いパフォーマンスのboolean情報の保存
HyperLogLog(HLL) : Redis 2.8.9~
- コマンド例: PFADD,PFCOUNT,PFMERGE
- 特徴
  - ユニークな数を計算するの確率的な計算手法となります。メモリー空間の効率良さと引き換えに誤差は1%未満含まれます。
- メリット/デメリット
  - メリット
    - 数え上げる対象の数に比例するメモリを必要とせず、一定量のメモリのみ
    - 最大でも12kバイトのメモリー量。要素数が非常に少ない場合はより小さい
  - デメリット
    - 標準誤差1%未満
- ユースケース
  - ユーザーが検索フォームから実行した、日々のユニーククエリの数を数える
GEO : 3.2.0~
- コマンド例: GEOADD,GEOPOS,GEORADIOUS,GEODIST,GEORADIUSBYMEMBER
- 経度・緯度等の位置情報に関するコマンド。内部ではSorted Setを使用。
Stream : 5.0.0~
- コマンド例: XADD,XDEL,XRANGE,XREAD,XINFO
- 特徴
  - エントリを追加することができるリストのようなものだが、IDで検索できる点が異なる。
  - Redis独自の機能として、コンシューマーグループのサポートでクライアントのグループが協働することが可能
    - コンシューマーを指定してデータを読み取ることが可能
    - 指定したコンシューマーがデータを正しく処理したことを確認することが可能
    - 適切に処理していなかった場合は、他の消費者に割り当てられて処理するようにすることが可能
    - 1つのストリームに処理すべきデータが多く、処理時間が長くかかった場合は、複数のコンシューマーを指定することが可能
  - データが連続的で大量に発生するような状況において追加していくのに適したデータ構造。既存のデータを変更せずに追加することが可能
    - 例) 温度、湿度、圧力、振動、傾き、照度などのセンサーデータ
  - 類似機能を持つkafkaはスケーラビリティが高く良い設計だが、複雑すぎる
- 比較
  - List
    - LISTは値（文字列）を比較します。STREAMは、ID（数字）を比較します。そのため、Streamの方が比較速度が速くなります
    - 取り出しは計算量がStreamのほうが多くなるが、削除は少ない。ただし、比較そのものがStreamの方が速い
    - LISTはフィールドと値をアプリケーションで区別（解析）する必要があります。Streamの方はRedisで識別されます。
    - Listは、値を工夫してメタデータを文字列中に含むことが出来ますが、Streamではその辺りの融通が効きにくくなります。
  - Hash
    - フィールドを持つという点で、両方のデータタイプは似ています。ところがHASHでhgetallコマンドを実行すると、入力されたフィールドの順序とは無関係に照会されますが、STREAMでは、入力された順序を維持します
  - Sorted Set
    - Score / IDでソートされるという点で、両方のデータタイプは似ています。ストリーム/ログデータをZSETに保存する場合はscoreとしてtimestampを使用します。
    - Sorted Setはデータの値の重複を許可していません。そのため、同じ値が入る場合に備えて値にtimestampように区別することができるデータを追加する必要があります。 Streamではその点については問題ありません。
    - Sorted Setは、値を工夫してメタデータを文字列中に含むことが出来ますが、Streamではその辺りの融通が効きにくくなります。
- ユースケース
  - チャットシステム
  - メッセージブローカー
  - キューイングシステム
  - 統合ログ

その他代表コマンド

キー管理
- コマンド例: DBSIZE,KEYS,SCAN,EXISTS,TYPE,RENAME,SORT
- 失効: EXPIRE,TTL,PERSIST,PEXPIRE,PEXPIREAT,SET,SETGET,*STORE,EXPIREAT,DEL,UNLINK
トランザクション
- WATCH,MULTI,EXEC,DISCARD,UNWATCH
Luaスクリプト
- EVAL,EVALSHA,SCRIPT LOAD,SCRIPT FLUSH,SCRIPT KILL,SCRIPT EXISTS
Cluster
- CLUSTER MEET,CLUSTER ADDSLOTS,CLUSTER NODES,CLUSTER REPLICATE,CLUSTER FAILOVER

UNLINKはRedis 4.0から導入されたコマンドで、サイズが小さいときはDELと同様の挙動で、そうでないときは一旦バックグラウンドでキューに入れられ、他のスレッドによって非同期に削除される挙動になります。削除対象のオブジェクトのサイズが大きいとDELは操作をブロックする問題を受けて、オブジェクトの割当て解除のコストを考慮して削除を行うコマンドが実装されました。
また、FLUSHALLで全データベース内、FLUSHDBで現在のデータベース内の全キーを削除することが可能ですが、4.0以降にASYNCオプションで、これらのコマンドでも非同期に削除できるようになりました。

内部エンコーディング

Redisでは、各種データを保存する際に、メモリ使用量を押さえるために内部エンコーディングを実施して保存することができます。その際に閾値はパラメータ等で設定を行います。

String
- int : 64bitの符号付き整数。long型
- embstr : 44バイト以下の文字列。char型配列
- raw : それより大きい文字列。sds文字列
List
- quicklist : 以下のパラメータが利用可能。Listの両端は以下の条件を満たす範囲でziplistが使用され、それ以外はLZFで圧縮される。3.2以前では以下の条件を満たすときは、ziplist、そうではないときはLinked Listを使用していた
  - list-max-ziplist-size 以下
  - list-compress-depth 以下
Hash
- ziplist
  - hasht-max-ziplist-entries 以下(2.6未満: hash-max-zipmap-entries )
  - hash-max-ziplist-value 以下(2.6未満: hash-max-zipmap-value)
- hashtable
SET
- intset
  - 全要素が整数
  - 数字の値の大きさに応じて、int 16,32,64bit長
  - set-max-intset-entries 以下
- hashtable
Sorted Set
- ziplist
  - zset-max-ziplist-entries 以下
  - zset-max-ziplist-value 以下
- skiplist
HyperLogLog
- Sparse : hll-sparase-max-bytes 以下。ランレングス符号化を利用して圧縮することによりメモリー使用量を効率化
- Dense
GEO
- GEOHASH : 52bit
Stream
- RAXのデータ構造で末尾にストリームデータを追加する際にサイズとエントリー数で制限を加えることができます。
  - stream-node-max-bytes
  - stream-node-max-entries

実行例

String

> SET key1 value1
OK
> GET key1
"value1"

List

> LPUSH list1 value1 value2 value3
(integer) 3
> LRANGE list1 0 -1
1) "value3"
2) "value2"
3) "value1"

Hash

> HMSET key1:1 element1 data1 element2 data2 element3 data3
OK
> HGETALL key1:1
1) "element1"
2) "data1"
3) "element2"
4) "data2"
5) "element3"
6) "data3"

> SADD set1 value1 value2 value3
(integer) 3
> SMEMBERS set1
1) "value3"
2) "value2"
3) "value1"

Sorted Set

> ZADD zset1 0 value1 2 value2 5 value3
(integer) 3
> ZRANGE zset1 0 2
1) "value1"
2) "value2"
3) "value3"

HyperLogLog

> PFADD pf1 value1 value2 value3 value4 value5
(integer) 1
> PFCOUNT pf1
(integer) 5

> GEOADD geo1 139.7671248 35.6812362 "Tokyo Station" 135.4937619 34.7024854 "Osaka Station"
(integer) 2
> GEOHASH geo1 "Tokyo Station" "Osaka Station"
1) "xn76urx6600"
2) "xn0m7jrs9k0"

パイプライニング/トランザクション/Luaスクリプト/モジュール

パイプライニング

パイプライニングは前のレスポンスを待たずに新しいリクエストを送ることができるようにして、複数のコマンドを送信することで、ネットワークのRTTを節約することによるネットワーク最適化を目的としたものとなります。パイプライニング内での順番は保証されているため、それを必要とするようなワークロードの場合には特に効果的です。
read()やwrite()のsyscallといったソケットI/Oは、ユーザーランドからカーネルランドへの移動でコンテキストスイッチが大きく、これらを集約することができるため、RTT以外でもこちらの観点でもレイテンシー削減の効果があります。

RTT削減という観点では、MGET/MSETやHMGET/HMSETで複数キーを送信することも可能です。
後述のトランザクション/Luaスクリプトでは処理を実行中他のクライアントが割り込むことができないためAtomicに処理が行われますが、パイプライニングでは実行中他のクライアントも処理を実行することができるため処理スクリプトがAtomicに処理が行われることは保証されません。

loopbackインターフェイス使用しているにも関わらず遅い場合は、カーネルのスケジューラーでプロセスが稼働していない可能性も考慮

Using pipelining to speedup Redis queries
- https://redis.io/topics/pipelining

トランザクション

トランザクション(Redis 1.2~)であるMULTI/EXECは実行内で他のクライアントが割り込むことなく処理をすることを保証します。
MULTIコマンド以降に宣言されたコマンドをキューイングしていきます。
トランザクション実行時は、以下のような理由で失敗することがあります。Redis 2.6.5以降は、キューイング中にエラーが発生した場合、EXECコマンド実行時にトランザクションの実行を拒否し、自動的に破棄するようになりました。以前は、キューイングに成功したコマンドはトランザクションを実行するような挙動になっていました。

1. コマンドのキューイングに失敗。コマンドの文法ミス(引数の数、コマンド名ミス、データ型ミス)やOut of Memory等
2. EXECコマンド実行時(誤った値を持ったキー操作)

Redisはロールバック機能をサポートしておらずコマンド失敗時もそのまま残りの処理を継続します。コマンド失敗は上記のような場合が考えられ、事前に検知可能と考えられるため、機能を省くことでよりシンプルかつ高速に動作するように設計しています。
DISCARDコマンドでトランザクションを途中で打ち切りキューを捨てることができます。
WATCHコマンドはCAS機能を実現し、EXEC実行前に対象のキーに変更が加えられていたらトランザクション全体を中止します。
このように競合しないことを期待して処理を行っていく種類のロックを楽観的ロックと呼びます。なお、WATCHコマンドのキーを対象から除外するためにUNWATCHコマンドもあります。

Luaスクリプト

Luaスクリプト(Redis 2.6~)は、RTT削減に加えて、Read/Writeの両方を最小レイテンシーで利用するような場面で特に効果を発揮します。一方でパイプライニングでは、writeコマンド呼び出しの前にreadコマンドのリプライを必要とするため役立ちません。パイプラインやトランザクションで可能なことは　後続で登場したLuaスクリプトで実現可能です。

Lua実行中はキーを失効しない挙動となります。同じスクリプトの同じデータセットで同じ効果があることを保証するための動作となります。
Luaスクリプトは基本的にずっとキャッシュに残る。消えるタイミングはSCRIPT FLUSH
上記動作の理由は通常スクリプトに変更が加えられて元のスクリプトが残ってもメモリーはわずかにしか消費しないので影響がないという判断のもとで行われた実装
コネクションプーリングを利用しながら、パイプライン中でSCRIPT LOADしてEVALSHAを実行といったことが可能です。
実行中のスクリプトに対して可能なコマンドは、SCRIPT KILL, SHUTDOWN NOSAVE　のみ

モジュール

モジュール機能(Redis 4.0~)では、Redisが提供しているString,List,Set,Hash,Sorted Setなどのデータ型にとどまらず独自でデータ構造を実行することができます。またコマンド等も自作することができるため、アプリケーションごとに最適な環境をRedisに実装することができます。
モジュールは互換性を意識してRedisコアとモジュールAPIを介して操作するような設計となっています。
モジュール機能をLuaスクリプトと比較すると、以下のような特徴があります。

1. 共有のCライブラリ                    : Luaスクリプトよりずっと速く動作することが期待されます
2. 独自のデータ構造、コマンド実装可能    : Luaでは既存のデータ構造、コマンドのみを利用することができました
3. クライアントから直接呼び出し可能     : LuaではEVAL/EVALSHAコマンドを通して実行する必要があります
4. サードパーティライブラリがリンク付け   : Luaだと限定的でした
5. APIが豊富                       : Luaより多く備えられています

バックアップ: RDB/AOF

RDB
- メリット
  - 1つのファイルでpoint-in-timeのデータを表しており、とてもコンパクト。障害時にも別のバージョンでリストアできる。
  - Disaster recoveryに利用でき、データセンターやS3に保存しておける。
  - Redisのパフォーマンスを最大化する。子プロセスフォーク分の処理しかせず、ディスクI/Oのようなものは実行しない
  - AOFより再起動が早い
  - LFUやLRUの情報を含むため、復元された直後からより正確にevictionされる(Redis 5.0~)
- デメリット
  - データロスの最小化には向いていない。5分間隔の取得だと障害発生の数分間は失われることになるので。
  - fork処理はデータ量が多いと時間がとてもかかりCPUを消費するので、クライアントからのリクエストを受け付けられなくなる可能性もある。
AOF
- メリット
  - データの耐久性がとても高い : no fsync at all, fsync every second(デフォルト), fsync at every query(OSに任せる形)
  - AOFログは追記するのみなので、seekする必要はなく、ディスクフルなど何らかの理由でちゃんと書き込めなかったときでも redis-check-aof tool ファイルで修復可能。
  - AOFが大きくなりすぎるとバックグラウンドで自動で書き換えが行われ、古いAOFに書き換えを行い続けた後、新しいAOFに切り替えるという安全な方法で実行する
  - AOFは全操作のログが記録されているので、理解しやすくパースもしやすい
- デメリット
  - REDOログのような形でトランザクションログが記録されていき、実際のデータを記録しているわけではないので、同じデータセットでも大抵AOFの方が大きくなる
  - AOFの方がRDBより遅くなる(fsync ポリシーに依存するが)
  - Redisサーバ、起動の際に読み込みに時間がかかる可能性
  - 過去にBRPOPLPUSHのようなブロックを伴うコマンドで、同じデータセットで正確に復元されないバグがあり、RDBではこのようなことは起き得ない。
  - ElastiCacheのようなマネージドサービスを利用している場合、基盤障害時はノードの入れ替えが行われるが、AOFはインスタンスストアに保存されるので、入れ替わったあとのノードで適用することができないため、AOFの効果がない。

AOFファイルでは、fsyncでディスクへの書き込みが行われるが、appnefsyncの設定に応じてタイミングを設定できます。

always : write毎にfsyncを実行
everysec : pthreadでバックグラウンドスレッドを生成し、毎秒fsyncを実行
no : OSにタイミングを任せる

また、以下の基準を満たすと自動でバックグラウンドスレッドの処理により、BGREWRITEAOFコマンドを実行することでAOFのrewriteでディスクへの書き込みが行われます。ただし、AOFのrewrite中やRDBファイルの保存中は実行を避けます。

auto-aof-rewrite-percentage
auto-aof-rewrite-min-size

AOFとRDBファイルの両方がある場合、appendonlyがyesの場合はAOFファイルが読み込まれ、noの場合はRDBファイルが読み込まれます。
ただし、Redis 4.0以降、RDB+AOFのMIX形式を使用することができます。
RDBファイルで定期的に完全なダンプファイルを取得し、RDBファイル以降の差分はAOFとしてコマンドを保存する形で両者の良いところ取りのような形で行われます。aof-use-rdb-preambleをyesにすることでmix型を使用できます。5.0以降デフォルトでも有効になりました。

BGSAVEのようなRDB取得によるバックアップの処理はパフォーマンスへ影響が出ることが考えられますので、以下の観点で確認しておくと良いです。

バックアップで使用するためにメモリーに余裕があるかの確認(ElastiCache のようなマネージドサービスを利用している場合、reserved-memory-percent(reserved-memory)パラメータの機能を利用することができます)
RDBはレプリカからの取得
取得時間はサービスへの影響が最も少ない時間に取得

互換性

2.4で作成されたAOF/RDBを2.6から読み取ることができません。同様に2.4のマスターからスレーブを2.6のものを使用することはできません。

メモリ管理

アーキテクチャ

OSメモリー
- Redis RSSメモリー
  - Datasetメモリー
    - Client Query Buffer
    - Client Output Buffer(動的なものと固定長のものがあり、CLIENT LISTコマンドの結果のoll,oblからそれぞれ確認できます。)
    - AOF関連
      - AOF Buffer
      - AOF Rewrite Buffer
    - Dataset関連コストのメモリー
  - メモリーフラグメンテーション
    - Replication Backlog
    - Lua

関係式

used_memory - AOF_buffer_size - slave_output_buffer_size ≦ maxmemory
used_memory_overhead = server_initial_memory_usage + repl_backlog
+ {slave,normal,pubsub}-clients_output_buffer
+ normal_clients_query_buffer
+ clients_metadata
+ AOF Buffer + AOF Rewrite Buffer

maxmemoryにはスレーブのClient Output Bufferが含まれない点に注意。

Client Output Buffer

Redis Serverは各クライアントやスレーブ、PubSub用にClient Output Buffer(以下COB)を持ちます。
クライアント出力バッファの制限は、何らかの理由でサーバーからデータをすぐに読まれないクライアントの接続を強制的に解除するために使用されます。ネットワーク帯域の狭い環境において、データサイズの大きいキーの読み込み時にはバッファにデータが溜まりやすくなります。

もし、COBを多く使用するクライアント等があれば他に影響しますので、COBが溢れた際には対象のCOBのコネクションが切断されます。

各クライアント毎にRedis ServerはCOBを用意し、サーバでの処理結果を直接クライアントへ送らずに一旦COBに保存します。その後、COBに保存された情報はまとめてクライアントに送られます。
例えばPub/SubでSubscriber側の受信が遅いとRedis Server側のメモリ使用量が増加し続ける可能性がありますが、その場合にはpubsubの制限を小さくするといった対応を行います。
スナップショット取得でforkによるバックアップが行われる際には、クラスターデータをシリアライズしてディスクへ保存処理が行われますが、この間フォアグラウンドでは、変更ログをスレーブ用のCOBに保存し、バックアップ取得が完了し転送が行われた後、キャッシュデータを変更ログをCOBからレプリカに送られます。

client-output-buffer-limitのパラメータで設定可能で、normal, replica, pubsubの3種類に対して、Hard Limit, Soft Limit(サイズ+時間)の種類があります。

zmalloc

Redis のメモリ管理はOSに大きく頼っています。メモリ確保の度に、mallocの呼び出しを行っており、OS内部の状況によってはレスポンスの処理速度にブレが出てくる可能性があります。
実際に割り当てたサイズを返すか、無理なとき(HAVE_MALLOC_SIZEでないとき)は確保の際に引数として渡したサイズだけ確保したものとしており、なるべく正確にやろうとしています。こちらの値は、INFOコマンドのused_memoryなどで確認することができます。
Memcachedでは対照的にメモリフラグメンテーションを押さえるためにSlab Allocatorという仕組みを導入しており、OSには依存しすぎず、アプリケーション側でメモリ管理を行うことが意識されているため、レスポンスの安定感が期待されます。

zmalloc.c

void *zmalloc(size_t size) {
    void *ptr = malloc(size+PREFIX_SIZE);

    if (!ptr) zmalloc_oom_handler(size);
#ifdef HAVE_MALLOC_SIZE
    update_zmalloc_stat_alloc(zmalloc_size(ptr));
    return ptr;
#else
    *((size_t*)ptr) = size;
    update_zmalloc_stat_alloc(size+PREFIX_SIZE);
    return (char*)ptr+PREFIX_SIZE;
#endif
}

HAVE_MALLOC_SIZEは、以下の条件時にtrueとします。zmalloc.h。

tcmallocのバージョン1.6以上、もしくは2以上を利用時
jemallocのバージョン2.1以上、もしくは3以上を利用時
MacOSを利用時
glibcを利用時

mallocの動作について

CPUにはMMU(Memory Management Unit)の機能があり、それらで物理メモリと仮想メモリのマッピングを行っています。

例えば、glibc のmallocでは、MMAP_THRESHOLD の値を適宜設定しながら、これらの値を超えるときはページからメモリ空間を割当て、超えないときはヒープ領域からメモリを割当てます。
ヒープ領域によるメモリ管理は、領域の一部を確保、解放なので仮想メモリ空間の連続領域の一部を使ってしまい、全体で見ると空きメモリが多くあるように見えても、連続した領域は短くなるため実際に確保できるメモリが小さくなるというメモリフラグメンテーションという事象が起きやすくなります。

malloc

Linuxの標準ではjemallocという実装が利用されており、jemallocの目標の一つとしてフラグメンテーションの削減を上げており、小さいサイズのメモリ割り当てのために複数のサイズクラスを用意して、実際に割り当てる際には対象のメモリサイズよりも大きいが最も小さいサイズクラスに割当てます。(この辺りはMemcachedのSlab Allocationに似ているものがあります)。その際、過剰に割当てられる領域は約25%以下となるようになっており、メモリーフラグメンテーションが抑えられるようになっています。

キーの失効方法

Redisでは、キーの失効方法の挙動に大きく2通りの方法が取られます。

Active way
Passive way

Redisでは、TTLが失効してもすぐに対象のキーが削除されるわけではなく、そのままメモリーに残り続けます。
通常、クライアントにより、同じキーにアクセスして、その際に失効していると判断された場合に失効します。こちらはPassive wayとなります。

Passive wayを利用して、TTLが切れた全キーを操作するために、KEYS * コマンドは、O(N)の処理で、シングルスレッドのRedisには影響が大きくなることもあるため、本番環境では推奨しておらず、SCAN/SSCAN/HSCAN/SSAN の利用が推奨されています。

なお、Redis 5.0.1からKEYS *でも失効したキーをevictionしないように変更しています。

00-RELEASENOTES

4. Don't evict expired keys when the KEYS command is called, in order to
   avoid a mass deletion event. However expired keys are not displayed
   by KEYS as usually.

一方で、Active wayでは、1秒間に10回、20個のランダムなキーをサンプリングし、失効したキーの削除を行います。その際、もし失効したキーがサンプリングの内25%以上対象であれば、再度サンプリングから操作を繰り返します。その間、他の処理はブロックされます。

EXPIRE key seconds

maxmemory-policy

メモリ使用量がmaxmemoryに達した際にはmaxmemory-policyで設定したポリシーに従ってEvictionが行われます。ポリシーとしてRedisは4.0以前は1~6のTTLの考慮の有無やLRUやランダムに基づいたもののみでしたが、4.0からは7,8のLFUに基づいたポリシーが追加されています。このLFUはMorrisアルゴリズムを利用した近似のカウント方法を取り入れています。

1. noeviction
2. volatile-random
3. allkeys-random
4. volatile-lru
5. allkeys-lru
6. volatile-ttl
(New)
7. volatile-lfu
8. allkeys-lfu

LRUの改良

初期のころはLRUの機能はありませんでしたが、その後、Redis 3.0以前のバージョンで、Redis Objectに24bitのフィールド(約194日)が確保されUnix timeを保存できるようにされました。しかしながら、Redisのアイテムは巨大なハッシュテーブルで保存するというアーキテクチャ上、最もアイドル時間が長いアイテムを取り出すことが難しく、ランダムで3つ(後に任意の数をmaxmemory-samplesパラメータで設定可能。デフォルト値を5に変更)、アイテムを選び、その中でアイドル時間が最も長いものをEvictionの対象としていました。

Redis 3.0ではLRUのアルゴリズムに改良が加えられ、キーをランダムでサンプリングする際、大きなキーのプール(デフォルトで16)をキーを集めるのに使われるようになりました。プールのキーはアイドル時間が長い順でソートされており、キーを選ぶ際、そのキーのアイドルタイムアウトがプールのキーのアイドルタイムアウトの中で最も短いものより大きければプールに加えられる。プールの中で最もアイドル時間が長いキーをEvictionの対象とします。

Morris's Algorithm (using by LFU)

Redis 4.0から導入された最も使用される頻度の少ないものをEvictionの対象とするためのLFUで使用されるアルゴリズムとなります。

Morris Countingは小さいサイズで確率論を利用したカウント方法となります。
底を決めたら、数字は指数部分のみを覚えていくことでサイズを小さく保存。指数が大きくなるにつれて、対応する数字も大きくなるので、次の指数に対応する数字になる確率は数字の差分だけどんどん小さくなっていきます。この確率に当たったときは数字が大きくなるものと想定した、かなりざっくりしたカウント方法となります。
そのため数字が大きいほど誤差は大きくなります。

Active Rehashing

Redisは一つの大きなHash Tableのような形でデータを管理しています。Active rehashingは、100ミリ秒の内1ミリ秒だけCPU時間を使い、rehashing中のテーブルに対して操作をするほど進行していき、増分rehashingの形で行われます。そのため、アクセスがあまりこないテーブルはrehashingが完了しないこともあります。add, delete, find, getRandomKey などの操作時に進行していきます。
Hash Tableは2のべき乗の単位で大きくなっていきます。
高いレイテンシー要件がある場合は、activerehasingをnoにしておく等の対応が必要となります。

Active Defragmentation

どのメモリアロケーターを使っている場合でも、徐々にメモリの断片化が発生してきます。Jemallocを使用している場合は比較的小さい傾向にあるものの、特にサイズの差が大きいデータを扱っている場合等に大きくなります。
以下のパラメータのしきい値を超えた場合、Jemallocの機能で連続したメモリ領域上に新しいデータのコピーを作り始め、古いデータを解放していきます。このプロセスは、全キーに対して、増分で繰り返し処理が行われて実行されます。
この機能は現時点ではExperimentalなものとなっており、デフォルトではactivedefragはnoとして無効化されています。

active-defrag-ignore-bytes
active-defrag-threshold-lower
active-defrag-threshold-upper
active-defrag-cycle-min
active-defrag-cycle-max
active-defrag-max-scan-fields

計算量

Big O notationでオーダーの大きいコマンドをリスト化したものです(Latencyモニタリングのfast-commandイベントではO(1)とO(log(n)まで含まれていますが一応O(log(n)まで載せてあります)。

Redisはシングルスレッドでの処理の性質上、計算量の多い処理があると処理がブロックされる原因にも繋がります。使用するアイテムの数やサイズに応じて実行するコマンドの計算量を意識することが大事となります。

問題になりがちなコマンドとしては、KEYS *, FlushAll/FlushDB, SMEMBERSの他、LUAスクリプト, MULTI/EXEC, Set型の要素削除などの操作があります。ただし、FlushAll/FlushDBはRedis 4.0以降非同期でデータを削除するオプションが追加されています。

O(N)

BITCOUNT
BITOP
BITPOS
CLIENT KILL
CLIENT LIST
CLUSTER ADDSLOTS
CLUSTER COUNT-FAILURE-REPORTS
CLUSTER DELSLOTS
CLUSTER KEYSLOT
CLUSTER RESET
CLUSTER SLOTS
COMMAND
COMMAND GETKEYS
COMMAND INFO
DEL
DUMP : キーへのアクセスでO(1), それのシリアライズでO(N*M)。Nは値を構成するRedisオブジェクト数で、Mが平均サイズ。Mが小さい場合はO(1)+O(1*M)、単純化してO(1)と見積もることができる
GETRANGE
HDEL
HGETALL
HKEYS
HMGET
HMSET
HVALS
KEYS
LINDEX
LINSERT
LREM
LSET : 最初と最後の要素の設定はO(1)
LTRIM
MEMORY USAGE
MGET
MIGRATE
MSET
MSETNX
PFMERGE
PSUBSCRIBE
PUBSUB : NUMPATサブコマンドに対してはO(1)
PUBLISH : O(N+M) Nはクライアントが受け取っているチャンネル数。Mが購読しているパターンの数
PUNSUBSCRIBE : O(N+M) Nはクライアントが受け取っているチャンネル数。Mが購読しているパターンの数
RESTORE : 新しいキーの作成はO(1)、値のシリアライズの段階で O(N*M)。Sorted Setの値は、O(N*M*log(N))(Sorted Setの挿入がO(log(N))だから)
SCRIPT EXISTS
SCRIPT FLUSH
SCRIPT LOAD
SDIFF
SDIFFSTORE
SINTER : O(N*M) ワーストケースはNが最も小さい集合のカーディナリティで、Mが集合の数
SINTERSTORE : O(N*M) ワーストケースはNが最も小さい集合のカーディナリティで、Mが集合の数
SMEMBERS
SORT : O(N+M*log(M))
SRANDMEMBER : カウントの引数がない場合はO(1)
SREM
SUBSCRIBE
SUNION
SUNIONSTORE
TOUCH
UNSUBSCRIBE
ZINTERSTORE : O(N*K)+O(M*log(M)) ワーストケースはNが最も小さい入力Sorted Setで、Kが入力Sorted Setの数、Mが結果のSorted Set中の要素数
ZUNIONSTORE : O(N)+O(M log(M)) ワーストケースはNが最も小さい入力Sorted Setで、Mが結果のSorted Set中の要素数
XINFO
XTRIM
XRANGE
XREVRANGE
XREAD
XPENDING : 数が少ないときはO(1)
XADD : O(1)。ただし、XREADGROUPがブロックしているときは、新しいデータを取得ストリーム上でブロックされているクライアントを受けるためO(N)

O(log(N))

BZPOPMIN
BZPOPMAX
CLIENT UNBLOCK
CLUSTER GETKEYSINSLOT
GEOADD
GEOHASH
GEOPOS
GEODIST
ZADD
ZCOUNT
ZINCRBY
ZLEXCOUNT
ZPOPMAX : O(log(N)*M) NはSorted Set中の要素数。Mはポップされる要素数
ZPOPMIN : O(log(N)*M) NはSorted Set中の要素数。Mはポップされる要素数
ZRANGE : O(log(N)+M) NはSorted Set中の要素数。Mは返される要素数
ZRANGEBYLEX : O(log(N)+M) NはSorted Set中の要素数。Mは返される要素数。Mが定数なら無視してO(log(N))を見積もられる。
ZREVRANGEBYLEX : O(log(N)+M) NはSorted Set中の要素数。Mは返される要素数。Mが定数なら無視してO(log(N))を見積もられる。
ZRANGEBYSCORE : O(log(N)+M) NはSorted Set中の要素数。Mは返される要素数。Mが定数なら無視してO(log(N))を見積もられる。
ZRANK
ZREM : O(M*log(N)) NはSorted Set中の要素数。Mは削除される要素数
ZREMRANGEBYLEX : O(log(N)+M) NはSorted Set中の要素数。Mは削除される要素数。Mが定数なら無視してO(log(N))を見積もられる。
ZREMRANGEBYRANK : O(log(N)+M) NはSorted Set中の要素数。Mは削除される要素数。Mが定数なら無視してO(log(N))を見積もられる。
ZREMRANGEBYSCORE : O(log(N)+M) NはSorted Set中の要素数。Mは削除される要素数。Mが定数なら無視してO(log(N))を見積もられる。
ZREVRANGE : O(log(N)+M) NはSorted Set中の要素数。Mは返される要素数
ZREVRANGEBYSCORE : O(log(N)+M) NはSorted Set中の要素数。Mは返される要素数。Mが定数なら無視してO(log(N))を見積もられる。
ZREVRANK
XCLAIM

commands.json

Redis特有の各種概念

RESP(REdis Serialization Protocol)

概要

RESPは、以下をコンセプトに特にRedis向けに設計されたプロトコルで(しかしながら他の用途にも使うことができます)、Redisのやりとりにはこちらのプロトコルが利用されます。

実装容易
パースが高速
人間が読める

RESPのフォーマットは、5つの型毎に最初に始まる文字列を以下のように定義しています。

Simple Strings: "+" ex) "+OK\r\n"
Errors : "-" ex) "-Error message\r\n"
Integers : ":" ex) ":1000\r\n"
Bulk Strings : "$" ex) "$6\r\nfoobar\r\n", 空文字 : "$0\r\n\r\n", NULL: "$-1\r\n"
Arrays : "" ex) "2\r\n$3\r\nfoo\r\n$3\r\nbar\r\n"

RESPにはバージョンがあり、2と3が利用できます。詳細は公式ドキュメントをご覧ください。

Redis Protocol specification

RESP3

背景

RESP v2では、セマンティクスの種類が少なかったために、クライアントは送ったコマンドを覚えておき後ほど変換する必要があったり、型の種類が少なかったために無駄が多かった。また、バイナリセーフなエラーを返す方法がなかった。その他、RESP v2では改行にCRLFを使用していたが、RESP3ではLFのみで良い変更とした。
MessagePackやBSONのような既存のシリアライズの実装を利用しない理由は、リクエスト/レスポンスのサーバー/クライアントモデルに最適化されていないことや、いくつかの機能が見られないことから独自実装

RESP v2と共通

Array
Blob string
Simple String
Simple error
Number

RESP v2との違い

Null : ex) "$-1" , RESP v2の *-1 を $-1 に置き換えて表現を1つにして無駄な表現を取り除く
Double : "," ex) ,1.23
Boolean : "#t\n", "#f\n"
Blob error : "!" ex) !21SYNTAX invalid syntax
Verbatim string : "=" ex) =15txtSome string
Map : "%" ex) %2+first:1+second:2
Set : "~" ex) ~5+orange+apple#t:100:999
Attribute : "|" , Map型のような属性情報を付加する補助データ

ex)

|1<LF>
    +key-popularity<LF>
    %2
        :a
        ,0.1923
        :b
        ,0.0012
*2<LF>
    :2039123
    :9543892

Push : ">" , 1. Pub/Sub 2. MONITORコマンド (3. Master-Slave リンク(除外))のときに、Push型を利用

>4<LF>
:pubsub<LF>
:message<LF>
:somechannel<LF>
:this is the message<LF>

Hello : "@" , Mapと同様の形だが、単にサーバ情報をクライアントに通知するために利用。serverは必須項目
Big Number : "(" ex) (3492890328409238509324850943850943825024385
RESP3 specification

RESP形式ではないクエリーのリクエスト処理について

telnetやNetcatでは、レスポンスはRESP形式であるものの、クライアントからのリクエストはRESPでなくても値を返しています。

$ telnet localhost 6379
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
get hoge
$4
fuga

実際にパケットキャプチャから確認しても入力したままの文字列としてクライアントから送られています($ sudo tcpdump -i eth0 port 6379 -A で確認したものとなります)

12:46:48.094733 IP localhost.35566 > localhost.6379: Flags [P.], seq 1:11, ack 1, win 342, options [nop,nop,TS val 1066207141 ecr 1066199887], length 10
E..>Xt@...%3............+zq[B.)l...V.2.....
?...?..Oget hoge

参考までに Redis クライアントから送っている場合はRESPプロトコルの形で送られていることが確認することが確認できます。

12:32:06.598721 IP ip-172-31-19-138.us-west-2.compute.internal.42652 > ip-172-31-3-150.us-west-2.compute.internal.6379: Flags [P.], seq 40:63, ack 11615, win 431, options [nop,nop,TS val 3660104825 ecr 2837207645], length 23
E..K.B@..................'@*........o......
.(.y..Z]*2
$3
get
$4
hoge

RESP形式ではないクエリーを処理できる理由は、networking.cの処理から確認することができます。

Redis Serverではリクエストを、PROTO_REQ_MULTIBULKとPROTO_REQ_INLINEの2種類に分けて処理を行っています。
実際には、クライアントから送られてきたデータのバッファ中の最初の文字が"*"であればRESPと判断しPROTO_REQ_MULTIBULKに分類し、そうでない場合は、PROTO_REQ_INLINEに分類しており、それぞれの種類に応じて処理が行われている(PROTO_REQ_MULTIBULKの場合はprocessMultibulkBuffer関数、PROTO_REQ_INLINEの場合はprocessInlineBuffer関数)ことが下記コードから確認できます。

networking.c

/* Determine request type when unknown. */
if (!c->reqtype) {
    if (c->querybuf[0] == '*') {
        c->reqtype = PROTO_REQ_MULTIBULK;
    } else {
        c->reqtype = PROTO_REQ_INLINE;
    }
}

if (c->reqtype == PROTO_REQ_INLINE) {
    if (processInlineBuffer(c) != C_OK) break;
} else if (c->reqtype == PROTO_REQ_MULTIBULK) {
    if (processMultibulkBuffer(c) != C_OK) break;
} else {
    serverPanic("Unknown request type");
}

RESP は、前述の通り、実装が簡単でパースが高速で、読みやすいことを目標としながらもバイナリープロトコル相当のパフォーマンスが実現できるように設計されています。そのため、Redis クライアントを利用しているときは多くは PROTO_REQ_MULTIBULK の種類で送られています。

上記挙動はRedis 2.8で追加されたものとなります。

00-RELEASENOTES

* [NEW] The new inline protocol now accepts quoted strings like, for example
        you can now type in a telnet session: set 'foo bar' "hello world\n".

SDS(Simple Dynamic Strings)

SDSは、以下をコンセプトに作られた文字列に関するライブラリとなり、Redisの実装での文字列は基本的にこちらの実装が利用されています。

利用簡単
バイナリセーフ
計算効率が良い
通常のC文字列と互換性(未解決)

例えば、文字列長を効率的に取得したり、都度メモリーを確保せずに文字列を末尾に足したりすることができます。
また、C言語では文字列の終わりをnull文字で認識しているため文字列の途中に含めることが出来ません。そのため、任意のバイナリデータを保持することができません。
一方で、SDSでは、末尾がnull文字で終わるか気にする必要がなくバイナリセーフであるように工夫されています。そのため、文字列の終わりは長さ情報も一緒に管理しています。

具体的な実装としては、SDSの文字列は構造体で以下のように定義されており、現在も文字列長(len)、空きスペース(free)、実際の文字列(buf)が定義されています。実際に利用する際には、sdsnewlen("redis", 5) のように文字列を生成して利用します。

struct sdshdr {
    long len;
    long free;
    char buf[];
};

文字列長を増加させるとき、SDS_MAX_PREALLOC(=1MB sds.h )と比較し、それ未満ならリクエストされたメモリの2倍を確保。それ以上ならリクエストされたサイズ+SDS_MAX_PREALLOCだけ確保。
Bitmap向けに確保するときは常に2倍で確保する(bitops.cのsetbitCommand関数の挙動)

https://github.com/antirez/redis/blob/unstable/src/sds.c#L198-L247

if (newlen < SDS_MAX_PREALLOC)
    newlen *= 2;
else
    newlen += SDS_MAX_PREALLOC;

sds.c

確保する文字列長に応じてヘッダーの種類を設定し、それに応じた構造体を定義しています。

static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5)
        return SDS_TYPE_5;
    if (string_size < 1<<8)
        return SDS_TYPE_8;
    if (string_size < 1<<16)
        return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
    if (string_size < 1ll<<32)
        return SDS_TYPE_32;
    return SDS_TYPE_64;
#else
    return SDS_TYPE_32;
#endif
}

sds.h

#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

ae

aeはイベント駆動ライブラリで、epoll,kqueue,select等をwrapしています。
SalvatoreはTclの制約を克服したJimというプログラミング言語を作成。その際にイベント駆動プログラミングのためのライブラリを実装し、Redisでも利用されている。こちらはイベント駆動処理を行うものとなっています。
epollであれば、epoll_create,epoll_ctl,epoll_wait等が利用されています。
複数のファイルディスクリプタに対してソケットリクエストがあると、I/O Multiplexing Moduleで一本化されて、イベントループによりイベントハンドラー(Accept Handler,Read Handler,Write Handler)に割り当てられます。

I/O多重化として、select, epoll, kqueueを利用することができます。

select : POSIX準拠
epoll : Linuxのデフォルト
kqueue : MacOS,FreeBSD,OpenBSD,NetBSDのデフォルト
https://github.com/antirez/redis/blob/unstable/src/config.h#L76-L90

/* Test for polling API */
#ifdef __linux__
#define HAVE_EPOLL 1
#endif

#if (defined(__APPLE__) && defined(MAC_OS_X_VERSION_10_6)) || defined(__FreeBSD__) || defined(__OpenBSD__) || defined (__NetBSD__)
#define HAVE_KQUEUE 1
#endif

#ifdef __sun
#include <sys/feature_tests.h>
#ifdef _DTRACE_VERSION
#define HAVE_EVPORT 1
#endif
#endif

https://github.com/antirez/redis/blob/unstable/src/ae.c#L47-L61

/* Include the best multiplexing layer supported by this system.
 * The following should be ordered by performances, descending. */
#ifdef HAVE_EVPORT
#include "ae_evport.c"
#else
    #ifdef HAVE_EPOLL
    #include "ae_epoll.c"
    #else
        #ifdef HAVE_KQUEUE
        #include "ae_kqueue.c"
        #else
        #include "ae_select.c"
        #endif
    #endif
#endif

https://github.com/antirez/redis/blob/unstable/src/ae.h#L70-L88

Redisには、ファイルイベントとタイマーイベントの2種類のイベントがあり、クライアントからのリクエスト処理は、ファイルイベントで処理が行われ、定期的な処理等はタイマーイベントで処理が行われます。

/* File event structure */
typedef struct aeFileEvent {
    int mask; /* one of AE_(READABLE|WRITABLE|BARRIER) */
    aeFileProc *rfileProc;
    aeFileProc *wfileProc;
    void *clientData;
} aeFileEvent;

/* Time event structure */
typedef struct aeTimeEvent {
    long long id; /* time event identifier. */
    long when_sec; /* seconds */
    long when_ms; /* milliseconds */
    aeTimeProc *timeProc;
    aeEventFinalizerProc *finalizerProc;
    void *clientData;
    struct aeTimeEvent *prev;
    struct aeTimeEvent *next;
} aeTimeEvent;

タイマーイベントでは、1秒間にhzのパラメータで指定した値の回数(Redis 5.0以降、dynamic-hzを有効にしている場合は、hzの値をベースラインとして接続クライアント数に比例させることでアイドル状態のCPU使用量の調整)だけservreCron関数を起動し、例えば以下のような処理を行っています。

Activeなキー失効収集
Software watchdog
一部統計更新
DBハッシュテーブルの増分rehashing
BGSAVE/AOF Rewriteのトリガーと終了した子プロセスの処理
異なる種類のクライアントタイムアウト
レプリケーション再接続

実装

https://github.com/antirez/redis/blob/unstable/src/server.c#L2810-L2816
https://github.com/antirez/redis/blob/unstable/src/ae.c#L208-L228
https://github.com/antirez/redis/blob/unstable/src/server.c#L1747-L2029

main関数からaeMain関数を呼び出しwhile文でずっとループを回しながら、aeEventLoop構造体を利用してaeProcessEvents関数でクライアントからのリクエストを処理しつつ処理結果をClient Output Bufferに格納しつつ、beforesleepの要素を確認して、Client Output Bufferにあるデータをクライアントに送信します。

https://github.com/antirez/redis/blob/unstable/src/ae.h#L96-L109

typedef struct aeEventLoop
{
    int maxfd;
    long long timeEventNextId;
    aeFileEvent events[AE_SETSIZE]; /* Registered events */
    aeFiredEvent fired[AE_SETSIZE]; /* Fired events */
    aeTimeEvent *timeEventHead;
    int stop;
    void *apidata; /* This is used for polling API specific data */
    aeBeforeSleepProc *beforesleep;
} aeEventLoop;

https://github.com/antirez/redis/blob/unstable/src/ae.c#L496-L503

void aeMain(aeEventLoop *eventLoop) {
    eventLoop->stop = 0;
    while (!eventLoop->stop) {
        if (eventLoop->beforesleep != NULL)
            eventLoop->beforesleep(eventLoop);
        aeProcessEvents(eventLoop, AE_ALL_EVENTS|AE_CALL_AFTER_SLEEP);
    }
}

Salvatoreがlibeventのようなイベント駆動ライブラリもある中で自前で実装した理由としては、あまり外部依存関係を持たせたくないことや、カスタムのしやすさ、外部ライブラリを利用することによる予測しないバグの混入の可能性を下げることを上げています。

https://groups.google.com/forum/#!topic/redis-db/tSgU6e8VuNA

イベント駆動処理のメリット/デメリットは以下のものが挙げられます。

メリット
- スレッド/プロセスを毎度用意しないため、メモリ消費量を抑えられる
- スレッド/プロセスの切り替えに伴うコンテキストスイッチのオーバーヘッドが小さい
- ノンブロッキングI/O利用でI/O待ち時間に他の処理を行うことができる
デメリット
- 遅い処理があると、後続処理が引きずられる
Redis Event Library
- https://redis.io/topics/internals-rediseventlib
実装
- https://github.com/antirez/redis/blob/unstable/src/ae.c

Jimの詳細は下記URLを参照ください。

The Jim Interpreter
- http://jim.tcl.tk/index.html/doc/www/www/index.html
Tcl the Misunderstood
- http://antirez.com/articoli/tclmisunderstood.html

RAX

Salvatoreが元々はRedisのパフォーマンス問題を解決するために実装したRadix tree(日本語では"基数木"と呼ばれるものです)の実装です。
Redis 4.0からRAXを利用したメモリ管理で、メモリ利用量を小さくすることが試みられています。現在は他でも利用できるようにスタンドアロンのプロジェクトとなっています。

https://github.com/antirez/redis/commit/1409c545da7861912acef4f42c4932f6c23e9937

また、Redis 5.0から利用可能になったStream型でも利用されています。

Radix treeはキーの各1ビットが二分木の左右の枝に対応しています。メモリ使用量を最適化したtrie treeのようなものとなります。
ただし、メモリ使用量を減らすだけではなく、パフォーマンスの犠牲のバランスを最適化することを意識して作られたものとなります。

Rax, an ANSI C radix tree implementation
- https://github.com/antirez/rax
実装
- https://github.com/antirez/redis/blob/unstable/src/rax.c
Radix tree
- https://ja.tech.jar.jp/network/algorithms/radix.html
基数木
- https://ja.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%9C%A8

GeoHash

RedisのGEOコマンドはGeoHashを利用しています。GeoHashは、緯度経度の二つの座標を、一つの文字列にまとめたものとなり、グリッド上の領域を表します。
例えば、緯度 35.681236, 経度 139.767125 の場合、xn76urx6606p のように表されます(http://geohash.org/xn76urx6606p )。桁が上がる毎にグリッド領域が狭まります。

Keyspace通知

Redisのデータセットに対する変更イベントをPub/Subの機能を利用して受け取る仕組みです。
KかEを最低限設定する必要があります。
全コマンドのイベントは、キーの値が変更されたタイミングでしか通知されません。どのようなイベントが通知されたかを確認するためには以下のようにします。expired イベントは、TTLが切れたタイミングではなく削除されたタイミングとなります。

$ redis-cli config set notify-keyspace-events KEA
$ redis-cli --csv psubscribe '__key*__:*'

Redis Keyspace Notifications(https://redis.io/topics/notifications )

K     Keyspace events, published with __keyspace@<db>__ prefix.
E     Keyevent events, published with __keyevent@<db>__ prefix.
g     Generic commands (non-type specific) like DEL, EXPIRE, RENAME, ...
$     String commands
l     List commands
s     Set commands
h     Hash commands
z     Sorted set commands
x     Expired events (events generated every time a key expires)
e     Evicted events (events generated when a key is evicted for maxmemory)
A     Alias for g$lshzxe, so that the "AKE" string means all the events.

レプリケーション

非同期処理でノンブロッキング。同期処理に近づけたい場合はWAITコマンドが利用可能です
マスターは全スレーブに対して定期的にデフォルトで10秒おき(repl-ping-slave-period)にpingを送信します
スレーブはマスターからpingを受け取り、前回のpingから一定時間以上(repl-timeout)空くと、マスター/スレーブ間のリンクはdownしているものと見なされます。
- repl-timeoutの値は、以下の観点で適用されます。
  - レプリカ観点
    - 同期中のバルク転送I/O
    - マスターからのデータが来ない or pingに応答が無い時間
  - マスター観点
    - レプリカからのREPLCONF ACKについて、pingを送ってから応答が来ない時間
- repl-timeoutの値は、repl-ping-replica-periodの値より大きくしておかないと、マスターレプリカ間のトラフィックが少なくなる度にタイムアウトが発生します。
レプリケーション作成の初回はフル同期を行い、以降コネクション切断時は、Redis 2.8以降、可能であれば部分同期を行います。再同期できない場合はフル同期を行うといった形で同期を行います。ただし、Redis 4.0以前のPSYNCでは、スレーブが同一のマスターへ再接続を行う場合にしか適用できないため、マスターがdownした際のフェイルオーバーの際には、新しいマスターに対してスレーブが再接続を行う際はフル同期が行われてしまってしましたが、4.0以降で改良されたPSYNC2ではその場合も部分同期が可能になりました。
スレーブ用のCOBが溢れた場合には、コネクションが切断され再同期が試みられ、その際backlog次第で部分同期が行われ、できない場合フル同期が行われます。
スレーブではキーを失効せず、失効したキーの情報はマスターから全スレーブへDELが送られる挙動となります(このときAOFにもDELが同期されます)。
レプリケーションはマスター上で稼働するため、レプリカ数が増加するとマスターへのパフォーマンスが影響することも考えられます。そのため、可能ならレプリカ数は制限することも考えると良いです。
レプリカ数が多い場合、ネットワーク帯域を意識して、多段にする方法もある(*)。4.0以降はチェイン上にレプリケーションしている場合、どのスレーブも一番上のマスターから生成された同じレプリケーションのストリームを受け取る挙動に変更されました。

(*)サービスによっては、SYNCコマンドが制限されており、多段にできないものもあります。

フェイルオーバー

マスターがdownした場合には、昇格させる新マスター上でslaveof no oneを実行し、それ以外の新スレーブはslaveof new_master_ip new_master_portを実行する(*)。
フェイルオーバー中、クライアントからの書き込みが新しいマスターへ向くようにCLIENT PAUSEコマンドでクライアントからのアクセスを一時的に中断することもできます。

(＊1)サービスで提供されている場合、自動フェイルオーバー機能が提供されていることもあります。
(＊2)マルチ AZ 対応レプリケーショングループのフェイルオーバー以外の理由で、プライマリに昇格する場合、クライアントが旧マスターへアクセスが行われ続けレプリカにwriteが行われる可能性があります。そのため、read-onlyなレプリカへのアクセスが行われた場合には、クライアントとのコネクションを切断するために、ElastiCache Redisでは、close-on-replica-write(Redis 5.0以前はclose-on-slave-write)というパラメータもあります。read intensiveなワークロードやレイテンシーが少しでも影響するような環境では、切断からの再接続までのオーバーヘッドを考慮して無効にすることも可能です。

close-on-slave-write の動作
- https://docs.aws.amazon.com/ja_jp/AmazonElastiCache/latest/red-ug/ParameterGroups.Redis.html#w2aac20c45c57c25b9

Luaの扱い

Luaスクリプトは現在、実行した結果の変更内容が1つのコマンドとしてスクリプトから生成されスレーブへ送られます(script effects replication: Redis 5.0以降はデフォルト。Redis 3.2から選択可能)。以前はスクリプト全体を送っていました(whole scripts replication)。
Redis 5ではドキュメント外のパラメータでlua-replicate-commandsをyesとする、もしくはDEBUG lua-always-replicate-commands 0を実行することで従来の方式に切り替える事が可能ですがRedis 6からは廃止予定で推奨されていません。
それぞれのメリット、デメリットは以下のとおりとなります。
- whole scripts replication
  - メリット
    - 1つのコマンド(script effects replication)を送るよりスクリプトを送る(whole scripts replication)方が早いことが有る
  - デメリット
    - ランダムな結果を返すスクリプトがあると結果がマスターとスレーブで変わってしまう。ほかにも外部要因に依存
    - Redisの対処方法
      - 外部へのアクセスを許可しない
      - ランダム関数実行でエラー
      - SMEMBERSは毎回同じ順番で返す
      - 疑似乱数は同じ値を返す
- script effects replication
  - メリット
    - whole scripts replicationの弱点が問題になるときに利用
  - デメリット
    - whole scripts replicationより遅いこともある

フル同期

マスターがリクエストを受け付けているプロセスとは別にfork()を実行して、スナップショットのためのRDB取得のプロセスを起動して、マスターのメモリー上からディスク上に保存します(ただし、2.8.18以降使用可能なディスクレプリケーションを利用している場合ディスクへ保存さずにそのままRDBをスレーブへ送ります。その場合、タイミングによってはデータロスのリスクもあります)。
ディスク上に保存したRDBファイルはソケットを通してスレーブへ行われ、スレーブ上のディスクへ保存されます。その後、スレーブ上のメモリへ読み込みが行われます。

上記処理中にマスターへwriteされたデータは一旦スレーブ用のCOBにデータを保存しておき、処理終了後にバッファに保存されたデータをスレーブへ送ります。

プロセスをforkする際、forkの操作そのものが遅い環境で実行すると実行時間という観点で影響が大きくなります。

なお、スナップショット取得のためにプロセスをforkする際、RedisはCopy On Write(CoW)という仕組みでメモリ管理が行われます。そのため、write比重のトラフィックの場合、メモリ量は、実際に保存しているデータの2倍近くのメモリを消費する可能性があります。そのため、Redisは稼働させるキャッシュノードで利用できるメモリ量の50%以下で運用することが推奨されています(*)。
スナップショット取得中にメモリを使いすぎ、OSのスワップを使い切った場合には、OOMやRedisが再起動することも考えられます。64bitではデフォルトでmaxmemoryが設定されておらず、エンジンとしてのメモリの上限が設定されていないので注意が必要です(32bitの場合は1つのキーあたりのメモリ量は少なくなりますが、大きくても4GB(2^32))。CoWの詳細は後述。

(*) 例えば、ElastiCache Redisでは、データ以外の用途にメモリを予約できるreserved-memory-percent(reserved-memory)パラメータの機能が提供されており、パラメータ設定で確保することも可能です。また、2.8.22以降のバージョンを利用している場合には、メモリを多く利用している場合等に、スナップショット取得の際にプロセスをforkせずに、リクエストを受け付けるものと同一のプロセス内でスナップショットを取得する挙動になる工夫がされています。その場合、レイテインシーやスループットに影響が出ることも考えられます。

Redis スナップショットを作成するための十分なメモリがあることの確認
- https://docs.aws.amazon.com/ja_jp/AmazonElastiCache/latest/red-ug/BestPractices.BGSAVE.html

仕組み

スレーブがマスターへレプリカになることを伝える
マスターがBGSAVE。スレーブは待機
BGSAVEが完了し、.rdbファイルをスレーブへ送る
ファイル転送時はマスターはバッファに新しく入ったデータを保存
マスターは.rdbファイルをスレーブへ送るのを完了する
マスターは4のバッファからスレーブへデータを送り始める

部分同期

レプリケーション切断時、レプリケーション切断中のマスターへのwriteはbacklogで保存しておき、回復時にbacklog中にそのReplication ID, offsetの情報があり、かつ無効な情報でなければ、フル同期ではなく部分同期の実行が可能となります。

backlogに蓄えておくデータのサイズとTTLは、パラメータのrepl-backlog-sizeとrepl-backlog-ttlで設定を行います。

Redis Cluster

Redis Clusterを利用するには、クライアントがRedis Cluster互換である必要があります。例えば、PhpRedisの場合、Redis Clusterを使用しない場合はnew Redisとオブジェクトを生成していたところ、new RedisClusterとして生成するように指定します。

クライアントは、シャード毎のスロットのマッピングを持っており、クライアントがオブジェクト生成時にCLUSTER SLOTSを取得したり、MOVEDリダイレクトを通して更新していくものとなります。
リクエストの際には、プロキシを利用することなく、DNSの名前引きとクライアントのマッピング情報を元にアクセスするノードの決定を行います。

Redisは、Raftという分散合意アルゴリズムをベースにしたフェイルオーバー機能を備えています。Raftの詳細は後述。

スロット

シャード毎にマスター1台とレプリカ(0台以上)を持っており、各シャードに対して16384のスロットを分配します。Redis Clusterに保存するキーについては、CRC16でハッシュ計算を行い16384のmodを取った値のスロットを持つシャードでリクエストの処理を行います。

HASH_SLOT = CRC16(key) mod 16384

スロット配置の様子は、CLUSTER SLOTS コマンドや CLUSTER NODES コマンドで確認することができます。

仕組み

クライアントは、Redisのエンドポイントに対して名前引きを行い、その結果から一つIPアドレスを選びその先のノードへアクセスを行います。名前引きの際に選ぶノードのIPアドレスの選び方、使用するDNSリゾルバーに依存します。
アクセス先がレプリカかプライマリの場合で以下のように処理内容が変わります。
- 2-1. アクセス先がレプリカの場合
  - Readクエリー: クライアントの設定等でREADONLYコマンドを実行しているかに応じて挙動が異なり、もし実行していて、そのキーがノードのスロット範囲内であれば、そのノードでリクエストの処理を行います。それ以外の場合、そのキーのスロットを持つシャードのマスターへリダイレクトが行われるようにMOVEDリダイレクトをクライアントへ送ります。MOVEDを受け取ったクライアントは、手元のスロットのマッピングを更新しつつ、指示されたリダイレクト先へアクセスを行います。
  - Writeクエリー: マスターへリダイレクトが行われます。
- 2-2. アクセス先がマスターの場合
  - キーがそのノードのスロットの範囲内の場合: そのマスター上で処理が行われます。
  - そうではない場合: そのキーのスロットを持つシャードのマスターへリクエストするようにMOVEDリダイレクトをクライアントへ送ります。MOVEDを受け取ったクライアントは、手元のスロットのマッピングを更新しつつ、指示されたリダイレクト先へアクセスを行います。

基本的にMOVEDリダイレクトで更新されたクライアントのスロットマップは、次回アクセス時に参考にすることで余分なリダイレクトが減らされます。そのため、Redis Clusterを利用する場合、リダイレクト時にわずかなラグがありますが、それ以外は特に影響を受けません。

パーティショニング

Redisでは、シャーディングで以下のような方法が考えられます。Redis Clusterは、この内のクライアントサイドパーティショニングとクエリールーティングを組み合わせたものと言えます。

クライアントサイドパーティショニング
プロキシベースパーティショニング ex) Twemproxy, Codis
クエリールーティング

Hash tags

Redis Clusterに対して複数キーを操作する場合、同じシャード内に対するアクセスでないと CROSSSLOT のエラーとなります。そこでハッシュタグを利用することで同じシャードに対してアクセスすることが可能となります。ハッシュタグを利用するには、キー中の共通の文字列に対して{}で囲う形となります。シャード間のリクエストの偏りの原因となり得ます。
例) {user1000}.following

Cluster Bus

Redis Clusterは、クラスター内の各ノードはTCPバスのバイナリプロトコルで互いに接続されています。Cluster Busで利用されるポート番号はRedisがListenさせるポートとして指定したものに+10,000したものとなります。例)6379であれば16379

Cluster Busで互いの状態の把握するためにGossipプロトコルが利用され、Raftという分散合意アルゴリズムをベースにしたフェイルオーバー機能を備えています(Salvatoreによるとスロット設定には完全なRaftは必要ないとしています)。

各ノードは、ランダムに他のノードを選びpingを送りpongの応答を受け取ります。このとき全体としてpingパケットの数が一定となるようにパケットが送られます。ただし、NODE_TIMEOUTの半分の時間以上の間、pingを送られていないかpongを受け取ることができていないその他のノードすべてにpingが送られるようになっています。

Gossipプロトコルと設定更新の仕組みを利用することで、メッシュ構造とノード数増加による指数関数的なメッセージの増加を避けています。
メッセージを減らしても問題ないとしていますが、帯域で特に問題が報告されていないため、現状の実装となっているとされています。

互換性

Redis 4.0と3.2のクラスターでは、Cluster Bus Protocol levelが異なるので、エンジンアップグレードの際には一斉に全ノードの再起動を要します。
Redis 5と4では、互換性があるので、再起動の必要はありません。

ハッシュスロットの設定反映のタイミング

heartbeatメッセージ : ping/pongを送る側は常に受け取るハッシュスロットの情報を付与
UPDATEメッセージ : heartbeatメッセージ時にconfigEpochの情報が含まれているので、もしreceiverがsender情報を失っていると分かればその情報を強制的に更新

Failure Detection

各キャッシュノードの状態にはPFAILとFAILの2種類があります。Redis ClusterではGossipプロトコルが利用され、他のノードのpingを送る際にGossipセクションを送り、そこにはランダムなその他のノードの状態も含まれています。信頼しているノードからの他のノードの状態の情報も信用ができるものとして、クラスター内のノードは互いの状態を把握していく形となります。
また、Raftではtermという概念がありますが、Redis Clusterではepochという言葉を使用しています。

PFAIL
- Possible failure
- あるノードが他のノードに対してpingを送りNODE_TIMEOUT以内の時間に応答が返ってこないとき、ローカル情報として、ping先のノードをPFAILとして情報を保持しておく
- マスターがこの状態でもフェイルオーバーは実行できない
FAIL
- FAIL状態になって初めてマスターはフェイルオーバーが実行可能となる。
- PFAILから以下の条件でFAILとなる。
  - 過半数以上のマスターから対象のノードがNODE_TIMEOUT * FAIL_REPORT_VALIDITY_MULT以内(現在FAIL_REPORT_VALIDITY_MULTの値は2)以内の時間でPFAIL or FAILの状態が報告されると、そのノードはFAILと判定される。

上記の通り、Redis Clusterのフェイルオーバーは、過半数以上のマスターが生き残っていることを前提としており、部分的にノードが死んでいる場合には復帰しますが、クラスター内のほとんどのキャッシュノードが死んている場合には復帰することができず、そのままの状態となります(*)。

(*)サービスで提供されている場合、その場合も回復するように工夫されていることもあります。

Slave election

以下の条件を満たすスレーブは、マスターになるための候補として選出を始めることができます。

レプリカのマスターがFAIL
マスターが1つ以上のスロットを管理
レプリカが一定時間以上マスターとリンクが切断状態
マスターがFAIL状態であることを検知したスレーブはある時間(DELAYミリ秒。詳細は後述)だけ待機して、クラスター内の各マスターにFAILOVER_AUTH_REQUESTパケットをブロードキャスト。このとき、NODE_TIMEOUT以内の時間を待機。
各マスターはパケット受け取ると、FAILOVER_AUTH_ACKで返信。その後、NODE_TIMEOUT*2の時間は、他のスレーブからのパケットに対して応答しない。
スレーブは、currentEpoch以下のepochの応答は無視して、そうでなければ受け取る。過半数以上のマスターから投票を受け取ると、そのスレーブが昇格対象としてフェイルオーバーが実行されます。もし、過半数に到達しない場合、NODE_TIMEOUT2の時間だけ待機。NODE_TIMEOUT4の時間後、再投票が行われます。
新しくマスターになったノードは、他のマスターよりも大きくなるようにconfigEpochを増加させます。

スレーブ観点

DELAYの時間について、マスターがFAIL状態であることをスレーブが検知してから以下の時間だけ待機してからvoteを各マスターに対してリクエストを送ります。

この500ミリ秒の固定時間だけ待機する理由は、クラスター内でマスターがFAIL状態である情報が伝搬することを待機するためとなります。
ランダム遅延は、スレーブが同時に選出を避けるためにずらすためとなります。
SLAVE_RANKは、スレーブ内でレプリケーションオフセットが最も進んでいるものから順に0,1,2,…となっていきます。

DELAY = 500ミリ秒 + ランダム遅延(0~500ミリ秒) + SLAVE_RANK * 1000ミリ秒.

マスター観点

マスターの観点では、スレーブへ投票を行うために以下の点に基づいている。

各マスターにはlastVoteEpochがあり、認証リクエスト中のcurrentEpochがこれより小さければ無視。正常にマスターがスレーブに応答すると、lastVoteEpochがアップデートされ、ディスク上に保存される。
スレーブのマスターがFAILとしている場合のみ、マスターはスレーブへ投票を行う。
認証リクエストのcurrentEpochがマスターのcurrentEpochより大きい場合のみパケットを受け取る。

configEpochの値の衝突時

フェイルオーバーにより、スレーブが昇格したことによりconfigEpochの値が他のノードと衝突する状況も考えられます。その場合、同じconfigEpochを持っていればノードIDを辞書順で小さい方をcurrentEpochに対して1を足すことで回避します。

レプリカマイグレーションアルゴリズム

アルゴリズムでは、同意する形式を取らないが、マスターにスレーブがないときでもスレーブが大量移動を回避するアルゴリズムを使用します。
正常なスレーブ(FAIL状態でないもの)がないマスターが1台でもあるとき、他のシャードのマスターのレプリカを、正常なスレーブがないマスターへ自動でマイグレーションすることができます。
マイグレーション対象のスレーブは、スレーブ数が最も多いマスターのシャード内から、FAIL状態でない、かつノードIDが最小のものを選択します。
クラスター設定が不安定で競合した場合は、再度アルゴリズムが実行され、スレーブが元のマスターへ戻されるので問題はない。
マイグレーション元のマスターが最低限保持しておくスレーブ数はcluster-migration-barrierパラメータで設定が可能です。

クライアント

Redis Clusterを利用するには、クライアントもRedis Clusterに対応している必要があります。
MOVEDリダイレクトを処理することができ、かつASKリダイレクトも扱える必要があります(*)。
また、シャード毎のハッシュスロットのマップはクライアントで保持しておくべきですが、そうでなくても動作します。その他MOVEDリダイレクト時に、CLUSTER NODESやCLUSTER SLOTSを取得してレイアウトを更新するといった方法も考えられます。

backlog

TCP Backlog

TCP Backlogは完全なコネクションキューを表しており、パラメータでは tcp-backlog を設定し、毎秒のリクエストが多い状況では高く設定する必要があります。

Redisでは、SYNキュー(不完全なコネクションキュー)とacceptキュー(完全なコネクションキュー)の2つのキューからなり、SYN RECEIVED時のコネクションはSYNキューに追加され、ACKを受け取ってESTABLISHEDへ変更されるとacceptキューへ移動するという挙動となります。

Linux kernel側のチューニングでtcp_max_syn_backlogが小さいとsomaxconnが大きくても十分に行かせない場合もあります。

レプリケーションバックログ

レプリケーションバックログは、最低1台のスレーブがあるときのみ作成されます。
スレーブから一時的にマスタから見えない時に差分データを溜めておくために使用します。こちらは部分同期のために使用され、フル同期では必要ありません。

スレーブがマスターへの接続時にPSYNCコマンドで古いマスターのReplication ID, offsetを伝えます。十分なバックログがマスターになかったり、無効なものだとフル再同期が実行されます。

backlogのサイズの見積もりは、writeのピーク時のINFOコマンドのmaster_repl_offsetの差を比較する方法などがあり、デフォルトの値では小さいことが多いといわれることもあります。

backlogに蓄えておくデータのサイズとTTLは、パラメータのrepl-backlog-sizeとrepl-backlog-ttlで設定を行います。バックログ

Slave Client Output Bufferは同期中のレプリケーションへのwriteをためておき、バックログはレプリケーション切断中に部分同期に使用するために利用されます。

TCP

Keep Alive

tcp-keepaliveで指定した時間ごとにSO_KEEPALIVEを使用してTCPでACKを返します。
既に接続を終了したクライアントやネットワーク経路の途中にあるファイアウォール等の観点で接続を維持するときに活用することができる機能となります。
Pub/Sub機能を使用している場合、Publishクライアントはtimeoutの対象外となります。

DEBUGコマンド

DEBUGコマンドはドキュメント上、DEBUG OBJECT / DEBUG SEGFAULT の2種類のみですが、24種類用意されています。

以下DEBUGコマンドの例です。

DEBUG POPULATE 1000 : 1000個のサンプルデータを生成
DEBUG OBJECT キー名 : キーの内部エンコーディングを確認
DEBUG HTSTATS 0 : データベース0のテーブルサイズや要素数、ハッシュの衝突によるチェイン法による対応状況などを確認
DEBUG SLEEP 5 : 実行時間に5秒かかるスロークエリーを実行
DEBUG RELOAD : SAVEによるRDBファイルのダンプ + FLASHALL + RDBファイルの読み込み
DEBUG RESTART : RDB、AOFファイルのディスク書き込み、設定ファイルのRewrite、サーバの再起動
DEBUG LOADAOF : AOFの読み込み。AOFファイルがない場合、redis-serverがエラーで終了
DEBUG LUA-ALWAYS-REPLICATE-COMMANDS 1/0 : Redis 5.0以降、Luaスクリプトによる変更内容が送られる挙動に変更され、以前はコマンドそのものをレプリケーションする挙動でしたが、DEBUGコマンドでこの動作を変更できるようになっています。
DEBUG DIGEST : 全DBのハッシュ値。マスターとスレーブのDBデータが同じであることの比較等
DEBUG DISGEST-VALUE キー名 : 指定されたキー名のハッシュ値を計算することができます。TTLの設定等メタデータの情報変更でもハッシュ値は変更されます。
DEBUG SEGFAULT : セグフォを意図的に発生
DEBUG ASSERT : assertionエラーで終了
DEBUG CRASH-AND-RECOVER 100 : クラッシュ後、100ミリ秒経過で再起動
DEBUG OOM : Redis ServerでOOMをシミュレーション
DEBUG JEMALLOC INFO : 3.2で導入されたが4.0で削除された。代わりにMEMORY MALLOC-STATSコマンドで相当する内容を確認可能となります。
DEBUG JEMALLOC PURGE : 3.2で導入されたが4.0で削除された。代わりにMEMORY PURGEコマンドで相当する内容を確認可能となります。
DEBUG STRUCT SIZE : Redisで使用される内部エンコーディングの構造体のサイズを確認可能。
DEBUG ZIPLIST キー名 : キーがziplistでエンコーディングされているときにデータ構造の詳細を確認可能。

ソースコードは以下となります。これらの説明はDEBUG HELPコマンドで確認することができます。ただし、OOMはDEBUG HELPコマンド上では表示されません。

https://github.com/antirez/redis/blob/unstable/src/debug.c#L303-L325

"ASSERT -- Crash by assertion failed.",
"CHANGE-REPL-ID -- Change the replication IDs of the instance. Dangerous, should be used only for testing the replication subsystem.",
"CRASH-AND-RECOVER <milliseconds> -- Hard crash and restart after <milliseconds> delay.",
"DIGEST -- Output a hex signature representing the current DB content.",
"DIGEST-VALUE <key-1> ... <key-N>-- Output a hex signature of the values of all the specified keys.",
"ERROR <string> -- Return a Redis protocol error with <string> as message. Useful for clients unit tests to simulate Redis errors.",
"LOG <message> -- write message to the server log.",
"HTSTATS <dbid> -- Return hash table statistics of the specified Redis database.",
"HTSTATS-KEY <key> -- Like htstats but for the hash table stored as key's value.",
"LOADAOF -- Flush the AOF buffers on disk and reload the AOF in memory.",
"LUA-ALWAYS-REPLICATE-COMMANDS <0|1> -- Setting it to 1 makes Lua replication defaulting to replicating single commands, without the script having to enable effects replication.",
"OBJECT <key> -- Show low level info about key and associated value.",
"PANIC -- Crash the server simulating a panic.",
"POPULATE <count> [prefix] [size] -- Create <count> string keys named key:<num>. If a prefix is specified is used instead of the 'key' prefix.",
"RELOAD -- Save the RDB on disk and reload it back in memory.",
"RESTART -- Graceful restart: save config, db, restart.",
"SDSLEN <key> -- Show low level SDS string info representing key and value.",
"SEGFAULT -- Crash the server with sigsegv.",
"SET-ACTIVE-EXPIRE <0|1> -- Setting it to 0 disables expiring keys in background when they are not accessed (otherwise the Redis behavior). Setting it to 1 reenables back the default.",
"SLEEP <seconds> -- Stop the server for <seconds>. Decimals allowed.",
"STRUCTSIZE -- Return the size of different Redis core C structures.",
"ZIPLIST <key> -- Show low level info about the ziplist encoding.",
"STRINGMATCH-TEST -- Run a fuzz tester against the stringmatchlen() function.",

以下、実行例となります。

127.0.0.1:6379> DEBUG POPULATE 1000
OK
127.0.0.1:6379> KEYS *
   1) "key:329"
   2) "key:854"
   3) "key:538"
   4) "key:213"
:
:
127.0.0.1:6379> DEBUG OBJECT key:329
Value at:0x7fef7d21fac0 refcount:1 encoding:embstr serializedlength:10 lru:14387812 lru_seconds_idle:24
127.0.0.1:6379> get key:329
"value:329"
127.0.0.1:6379> DEBUG DIGEST
4c3b7b7a1d8e50397e1be87b1c7f79baccf00721
127.0.0.1:6379> DEBUG RELOAD
OK
127.0.0.1:6379> DEBUG HTSTATS 0
[Dictionary HT]
Hash table 0 stats (main hash table):
 table size: 1024
 number of elements: 1003
 different slots: 659
 max chain length: 5
 avg chain length (counted): 1.52
 avg chain length (computed): 1.52
 Chain length distribution:
   0: 365 (35.64%)
   1: 400 (39.06%)
   2: 191 (18.65%)
   3: 55 (5.37%)
   4: 9 (0.88%)
   5: 4 (0.39%)
[Expires HT]
No stats available for empty dictionaries
127.0.0.1:6379> DEBUG CRASH-AND-RECOVER 100
Could not connect to Redis at 127.0.0.1:6379: Connection refused
not connected>

127.0.0.1:6379> DEBUG STRUCT SIZE
"bits:64 robj:16 dictentry:24 sdshdr5:1 sdshdr8:3 sdshdr16:5 sdshdr32:9 sdshdr64:17 "

bits: INFO Serverコマンドのarch_bitsに相当。
robj: server.h中のredisObject構造体のサイズを表す

#define LRU_BITS 24
#define LRU_CLOCK_MAX ((1<<LRU_BITS)-1) /* Max value of obj->lru */
#define LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */

#define OBJ_SHARED_REFCOUNT INT_MAX
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;

dictentry: dict.h中の下記dictEntry中のサイズを表す。

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

sdshdr5, sdshdr8, sdshdr16, sdshdr32, sdshdr64: sds.h中でそれぞれ以下のように定義されています。

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

以前は、サイズによらず8バイトの構造体が使用されています。これは後述のembstrの境界が以前は39バイトでしたが、3.2.0以降は44バイトへと基準が変更される由来となっています。

struct sdshdr {
    unsigned int len;
    unsigned int free;
    char buf[];
};

DEBUG OBJECT key
- https://redis.io/commands/debug-object
DEBUG SEGFAULT
- https://redis.io/commands/debug-segfault

データベース

Redisでは、エンジン内で複数のデータベースを使用することができ、デフォルトでは0番が使用されています。異なるデータベースの選択は、SELECTコマンドで切り替えることができます。しかしながら、非推奨の機能となっております。

database names?
- https://groups.google.com/forum/#!msg/redis-db/vS5wX8X4Cjg/8ounBXitG4sJ

Redis Clusterでは既に複数データベースは非対応となっています。

Redis Cluster Specification
- https://redis.io/topics/cluster-spec

セキュリティ

Redisの一般的なセキュリティモデル : 信頼された環境からのアクセスのみを想定して設計
ネットワークセキュリティ : bindディレクティブでIPアドレスを指定
保護モード(Protected mode)
- 有効時は以下の条件時に利用できない
  - bindディレクティブを使ってIPアドレスを明示的に指定していない
  - パスワード未設定
- デフォルト有効
- Redis 3.2~
認証機能 : AUTHコマンドでパスワード設定
暗号化 : 保存時/転送時、共に非サポート(＊)。そのためSpiped/Stunnelを利用して転送時の暗号化を利用等の必要性
特定コマンド無効化 : rename-commandパラメータ(＊)
外部クライアントからの注意深く選択された入力による攻撃
- ハッシュテーブルで同じバケットへのハッシュも文字列を入力してワーストケースのO(N)でCPU消費やDoS攻撃
- 対策として、実行ごとに擬似ランダム関数のシードを使用
- SORTコマンド(qsortアルゴリズム) : 現時点で完全にランダム化されていないので入力次第でワーストケース
文字列エスケープとNoSQLインジェクション
- Redisプロトコルでは文字列エスケープの概念がなく挿入は通常できないが、信頼できないソールから入手できる文字列を使うLuaスクリプトからボディを構成するといったことは避けるべき
コードセキュリティ
- Redisはバッファオーバーフローやフォーマットバグ、そのほかメモリ破壊問題を防止した実装にはなっている
- CONFIGコマンドでRDBファイルのディレクトリ等のパスは変更できてセキュリティ問題になりうる。Redisユーザーに稼働に必要な権限のみで稼働させる
Redis Security
- https://redis.io/topics/security
A few things about Redis security
- http://antirez.com/news/96
Using stunnel to Secure Redis
- https://redislabs.com/blog/stunnel-secure-redis-ssl/

LATENCY MONITOR

コマンドに実行がかかる際には、SLOWLOG GET 10やINFO commandstatsのusec_per_call等を確認することが有用ですが、その他内部の操作も含めて確認するには、Latency Monitorも有用です。

LATENCYイベントは、5.0時点で以下のようなイベントがあります。
LATENCY LATESTコマンドのようにイベント名が表示されたり、LATENCY HISTORY/GRAPHコマンド等の指定でも使用します。

fork : RDBやAOF取得の際にプロセスをforkするのにかかった時間
rdb-unlink-temp-file : unlinkで非同期にキーの削除処理を行う際にエラーで一時RDBファイルの削除を行う際の処理
eviction-del : キー保存でメモリーが不足した際にキーを1つ削除する処理
eviction-cycle : 上記同様にeviction間全体でデータの削除を行う処理
aof-write-pending-fsync : appendfsyncでeverysec指定時、1秒ごとに実行するAOFのスレッドがfsync実行の際に閾値以上に時間がかかったもの。
aof-write-active-child : AOFやRDB主屋時にい別スレッドによるバックグラウンド処理時にRedis Serverのwriteにかかった時間
aof-write-alone : aof-write-eventでaof-write-pending-fsync, aof-write-active-childを除いたもの。
aof-write : aof-write-pending-fsync + aof-write-active-child + aof-write-alone
aof-fsync-always : appendfsyncがalways指定時、fsync実行の際に閾値以上に時間がかかったもの。
aof-fstat : サイズなどのファイルサイズ取得にかかった時間
aof-rewrite-diff-write : AOFのスレッド処理がrewriteを終了してから親プロセスでAOFバッファの内容をwriteするのにかかった時間
aof-rename : AOFのスレッドで親プロセスがwrite完了したあとにrenameするのにかかった時間
expire-cycle : 失効したキーをActive wayにより定期的に削除する際にかかった時間
active-defrag-cycle : アクティブデフラグメント有効時に行う処理
fast-command : O(1)またはO(log(N))のコマンド
command : fast-command以外のコマンド

https://github.com/antirez/redis/blob/unstable/src/latency.c#L295-L380
https://github.com/antirez/redis/blob/unstable/src/aof.c#L390-L1754

MONITOR

Redis Server上で実行しているコマンドを確認することができます。ただし、管理者コマンドはセキュリティ上の理由で監視対象から除外されています。

MEMORY

MEMORYコマンドはサブコマンドとして以下の種類があります

DOCTOR
MALLOC-STATS
PURGE
STATS
USAGE

MEMORY DOCTOR

MEMORY DOCTORコマンドは以下の基準で判定が行われます。

メモリーが5MB以上使用されているか
ピーク時に使用されるメモリ量は現在の150%以上か
フラグメンテーションが1.4以上か
クライアントが平均で20万以上あるか
各スレーブが10MB以上、スレーブのClient Output Bufferが使用しているか

MEMORY STATS

MEMORY STATSコマンドは以下の項目に関してメモリーの詳細を確認することができます。

peak.allocated
total.allocated
startup.allocated
replication.backlog
clients.slaves
clients.normal
aof.buffer
lua.caches
overhead.hashtable.main
overhead.hashtable.expires
overhead.total
keys.count
keys.bytes-per-key
dataset.bytes
dataset.percentage
peak.percentage
allocator.allocated
allocator.active
allocator.resident
allocator-fragmentation.ratio
allocator-fragmentation.bytes
allocator-rss.ratio
allocator-rss.bytes
rss-overhead.ratio
rss-overhead.bytes
fragmentation
fragmentation.bytes

overhead.hashtable.mainとoverhead.hashtable.expiresはデータベース毎に表示されます。

一般的な概念について

Copy on Write(CoW)

RDB/AOF取得時には、forkされたバックグラウンドプロセスで動作し、その際CoWを行うので、取得中に変更(write)されたメモリ分だけメモリを必要するため、write intensiveな場合、最悪なケースとなりメモリ使用量は最大2倍となります。
CoWはfork時には子プロセスの仮想アドレス空間に親プロセスのアドレス空間をマッピングし、親と子でアドレス空間を共有します。子プロセスは、メモリの参照時には親プロセスの物理アドレス空間を参照する。一方で、メモリの書き込み時には書き込まれたページを親子で共有することはできないので、書き込み前に該当メモリページを子プロセスにコピーしてから書き込む。以降、該当ページのメモリ共有はしません。
Redisでは、saveパラメータで指定したタイミング、BGSAVEコマンド実行時、レプリケーションによるフル同期時、auto-aof-rewrite-percentage,BGREWRITEAOFコマンド等のタイミングで行われます。
/proc/<プロセスID>/smapsのPrivate_Dirtyの合計となります。

Raft

Raftは以下の特徴を持ちます。

分散合意アルゴリズム(Consensus Algorithm)の一つ
Paxosが主流だったところ理解のしずらさからわかりやすいアルゴリズムとして考案されたもの
Consensus Algorithmは分散システムで高可用性の実現に必要

ただし、過半数のサーバからvoteされたcandidateがleaderに昇格するという性質上、過半数以上のマスターが死んでしまうと機能しなくなります。Vanilla Redisに関しては、Redis Clusterでは、局所的なマスターがfailed状態になることを想定しているためそのような場合は機能しないものとなっています。

Raftは以下の2つの段階を取ります。

Leader Election
Log Replication

Leader Election

以下の登場人物が登場します。Raftではtermという概念があり、その期間内の最初にleaderの選出がされ、再投票が行われるまでの期間その状態の構成が続きます。

leader
candidate
follower

leaderがcandidate/followerに対して変更内容をログとして指示することになります。以下の形でleaderが選出されます。

Raftに加わるノードはすべてfollowerからスタート
leaderからfollowerに対して定期的にheartbeat
反応がなくなるとfollowerがcandidateになり、かつ周りにRequestVoteをばらまき選出が開始
RequestVoteを受け取ったサーバは最初に送ってきた送り元にvote
過半数のサーバからvoteされたcandidateがleaderに昇格

Log Replication

クライアントからのリクエストをleaderが受け取るとAppendEntriesとして各followerにログを送ります。その後過半数以上のfollowerから応答を受け取るとleaderはcommitを行います。
もし、ノード間で状態に差が出たら、共通箇所まで遡り再度leaderのログから情報をアップデートを行います。

詳細は以下を参照

The Raft Consensus Algorithm
- https://raft.github.io/
Raft Understandable Distributed Consensus
- http://thesecretlivesofdata.com/raft/

なお、Redis ClusterはRaftのConsensus Algorithmからアイデアを得ていますが、Redisのスロット設定には完全なRaftは必要なく実際には完全に準拠しなくても動作するようになっています。

Paxos/Raftの理解は以下のスライドが個人としてわかりやすかったです。

Raft
- https://www.slideshare.net/pfi/raft-36155398
Paxos
- https://www.slideshare.net/pfi/paxos-13615514

HyperLogLog

HyperLogLogはユニークな数を計算するの確率的な計算手法となります。メモリー空間の効率良さと引き換えに誤差は1%未満含まれます。

アイデアとしては、コインを連続して投げたときに連続して同じ目が何個でるかという試行を何回か試すとき、多くの連続した目が出たということは、多くの回数を試行したのであろうことを示すという発想に近いものとなります。偶然のこともあるので誤差も含まれます。

MinHash Sketch

HyperLogLogはMinHashの一つとなります。

Jaccard指数は、S1,S2を集合として、J(S1,S2) = |s1∩S2|/|s1∪S2| のように定義されます。
こちらを用いて、2つのハッシュ値の最小値が一致する確率は、Jaccard指数に等しいという性質があります。 Pr[min{h(a)|𝑎 ∈ 𝑆1} = min{h(b)|b ∈ 𝑆2] = J(S1,S2)
2つの共通の和集合の中でのハッシュ値の最小値と同じであることと、それぞれの集合のハッシュ値の最小値が同じであることが同じであることを意味します。

k-MinHash Sketchでは、k個のハッシュ関数を利用して、一致した数/k により、J(S1,S2)を推定します。

HyperLogLogの仕組み

MinHashを利用したハッシュ値の使い方の1つとしてBase-b Ranksというものがあり、これは集合Sについて、𝜚ℎ(𝑎) := |-logb h(a)/n| (𝑎 ∈ 𝑆)のように定義されます。
HyperLogLogではこの内のBase-2 Ranksを利用し、𝜚ℎ(𝑎) := <ℎ(a)を2進数で表記したときの先頭の0の数>となります。この連続する0の数というところが先程のコインの連続して同じ目が何回出るかという例えの部分に相当しています。

推定強化のためにk個のハッシュ関数を用意し、以下のように計算します。

レジスタとしてk=2^b個のバケットM[i]を用意
ハッシュ値h(a)の先頭b bitでバケットを振り分け
各バケットでBase-2 Ranksの最大値 maxを保存
各バケットで推定値(Cardinality)を2^max として計算
計算した各バケットの推定値の調和平均を計算、この値は求める値となります。バケット数 / (1/推定値1 + 1/推定値2 + 1/推定値3+…)

ハッシュ関数が一つの場合は、Base-2 Ranksの最大値 maxを求めたあと、2^max として推定値を求めたものとなることになります。

メモリー使用量

メモリー使用量は、レジスタの数 × <各バケットのBase-2 Ranksの最大値の保持に必要な最大のビット数> となり、それぞれの集合毎にメモリーを用意すると線形に増加していたところ大幅に削減されます。

Redisでは、16384個(=16k)のレジスタと64bit長のMurmurHash2のハッシュ関数を利用します。
64bitのうち14bitの値に応じて、用意した16384個のレジスタに分類します。
残りの50bitをCardinalityの計算のために使用します。0,1の数値を並べても最大で50個以下の数になるので、2^6(64)以下、すなわち6bitのサイズのレジスタがあれば十分ということになります。
そのため、メモリー使用量としては1つのキー辺り理論上 6bit * 16k / 8 = 12kバイト必要ということになります。

実際には、キャッシュ目的で最後に計算したCardinalityの値をエンコードして8バイト使用します。
上記の理由で正確には1つのキー辺り最大で12k + 8バイトのメモリーを必要とします。

ただし、RedisではHyperLogLogの内部エンコーディングとしてSparseとDenseの2種類を使用します。hll-sparse-max-bytes 以下のときには内部でSparseとして表現され、0bitの羅列が多いときにランレングス符号化を利用して圧縮表現を利用してメモリーを効率化して使用します。Denseのときのメモリー使用量は、12k + 8バイトのメモリーとなります。

精度

想定誤差は1.04/√k となります。
定数確率で1±ε 近似するために必要な空間は、O(ε^(-2)loglogn + logn)となり、ここに現れるloglogがこの手法の名前の由来となります。

Redisでは、16384個のレジスタを利用するので、1.04/√16384 ≒ 0.81%が標準エラーの誤差となります。

なお、Redis 5.0からは上記アルゴリズムに変更が加えられ、より高速でよいアルゴリズムになっています(http://oertl.github.io/hyperloglog-sketch-estimation-paper/paper/paper.pdf )。

Redis new data structure: the HyperLogLog
- http://antirez.com/news/75
PFCOUNT key [key …]
- https://redis.io/commands/pfcount
HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm
- http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf

RSS

メモリ関連のRSS,USS,PSS,VSSの違いは以下の通りとなります。Redisでよく使われるRSSは、Redisが実際に利用しているメモリ量ではなくOSがRedisのために確保したものという文脈で使用されています。

RSS: プロセスのメモリ量と共有ライブラリが使用しているメモリ量の合計。
USS: プロセスのみが使用しているメモリ量。
PSS: プロセスが使用しているメモリ量に、共有ライブラリが使用しているメモリ量をプロセス数分だけ分割した量だけ合計したもの。
VSS: 未使用のメモリを含めてプロセスがアクセスできるメモリ量の総和。

CRC

CRC(巡回冗長検査)は誤り検出符号の一種で、主にデータ転送などに伴う偶発的な誤りの検出によく使われています。送信側は定められた生成多項式で除算した余りを検査データとして付加して送信し、受信側で同じ生成多項式を使用してデータを除算し、その余りを比較照合することによって受信データの誤り・破損を検出します。
生成多項式は、ビット列を多項式として表したときに、それ以下の次数のある多項式で割り切れるものだけを符号として考えたときの割る側の多項式となります。

m bitの情報P(x)について、x^(n-m)を掛けて、n bitの値を考えます。生成多項式G(x)で割った余りをR(x)とすると、
x^(n-m) * P(x) = Q(x)*G(x) + R(x)

これをF(x)とします。

F(x) = Q(x)G(x) + R(x)

受信側では、送信されたF(x)に伝送路で誤りE(x)が加わりA(x)=F(x)+E(x)を受信したものとします。
A(X)に生成多項式G(x)で割り、その余りR(x)を求め0でなければ誤りであることを判定します。

RDBファイルでチェックサムを有効にする(rdbchecksumパラメータをyes)とCRC64, Redis Clusterのハッシュスロットの計算にはキーをCRC16で計算した値に16384の剰余を取ったものを利用されますが、それぞれ65bitの定数に相当する生成多項式を使用して64bitのCRCを求めるものがCRC64, 17bitの定数に相当する生成多項式を用いて16bitのCRCを求めるものがCRC16となります。

CRC16
- http://download.redis.io/redis-stable/src/crc16.c

/* CRC16 implementation according to CCITT standards.
*
* Note by @antirez: this is actually the XMODEM CRC 16 algorithm, using the
* following parameters:
*
* Name                       : "XMODEM", also known as "ZMODEM", "CRC-16/ACORN"
* Width                      : 16 bit
* Poly                       : 1021 (That is actually x^16 + x^12 + x^5 + 1)
* Initialization             : 0000
* Reflect Input byte         : False
* Reflect Output CRC         : False
* Xor constant to output CRC : 0000
* Output for "123456789"     : 31C3
*/

CRC64
- http://download.redis.io/redis-stable/src/crc64.c

* Name: crc-64-jones
* Width: 64 bites
* Poly: 0xad93d23594c935a9
* Reflected In: True
* Xor_In: 0xffffffffffffffff
* Reflected_Out: True
* Xor_Out: 0x0
* Check("123456789"): 0xe9c6d914c4b8d9ca

ACID

トランザクションシステムで持つべき性質としてACID特性と呼ばれるものがあり、下記単語の頭文字を取ったものになります。

原子性(Atomicity)
一貫性(Consistency)
独立性(Isolation)
永続性(Durability)

Redisでは、AtomicityやConsistencyはトランザクションやLuaスクリプトにより担保、Isolationはシングルスレッドで処理する性質による担保、DurabilityはAOFをappendfsyncの設定をalwaysに設定することなどでより近づける事が可能ですが、業務用件に応じて、それぞれのメリット/デメリットを比較した上で対応方針を検討する必要があります。

ベンチマーク

Redisのベンチマークには、redis-benchmark/memtier-benchmark他、rpc-perf/YCSBといったツールがあります。
redis-benchmark/memtier-benchmarkの実行例は以下の通りとなります。

$ redis-benchmark -r 1000000 -n 2000000 -t get,set,lpush,lpop -P 16 -q
$ memtier_benchmark -s localhost -p 6379 -P redis --threads 10 -c 250  --test-time=10 --ratio=1:10 --data-size-list=1000:60,5000:30,100000:10  --key-prefix=memtier-memtier-memtier- --key-maximum=100000

redis-benchmarkの詳細は、以下の記事をご覧ください。

How fast is Redis?
- https://redis.io/topics/benchmarks

memtier_benchmarkのインストール方法は以下の記事をご覧ください。

memtier_benchmark の導入 (memcached-tool で Slab の内容確認)
- https://hayashier.com/memtier_benchmark-introduction/

実装 ~ 各種定義について ~

https://github.com/antirez/redis

Redisオブジェクト

Redisには、文字列型やList型,Hash型,Set型,Sorted Set型等のデータ型や、各データ型にはエンコーディング形式もあり、それぞれredisObject構造体のtype, encodingで管理されています。
オブジェクトを共有して使用することでメモリと時間を節約して効率的に使用する内部構造となっていました。
ただし、実際のデータは ptr 変数の参照先にあり、間接参照のオーバーヘッドがあります(短い文字列のときは、文字列に対するヘッダーのオーバーヘッドが特に顕著)。そのため、Redis 4.0以降、全データ型においてredisObject構造体を利用せずSDSで直接データをポイントするようになりました。結果的によりメモリを効率的に使用できるようになりました。また、Salvatore曰く検証でパフォーマンスも上がったとしています。
オブジェクトを共有しない内部設計になったことにより、Redis 4.0以降に登場したUNLINKコマンドやFLUSHALL,FLUSHDBのASYNCオプションのような別スレッドで重い処理を非同期に行うといったことが可能になりました。

https://github.com/antirez/redis/blob/unstable/src/server.h#L633-L641

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;

https://raw.githubusercontent.com/antirez/redis/4.0/00-RELEASENOTES

all the aggregated data types
no longer use Redis Objects structures but directly SDS objects

Lazy Redis is better Redis
- http://antirez.com/news/93

Hash Table

https://github.com/antirez/redis/blob/unstable/src/dict.h#L67-L82

dict構造体ではハッシュテーブルとなるdictht構造体を2つ持っています。理由は増分rehashingで、ハッシュテーブルがサイズを占めてきたときに2乗したサイズだけ大きくしますが、その際の前後のハッシュテーブルを確保しておくためのものとなります。rehashingが実行中出ない場合は、コメントにもあるようにrehashidxの値が-1となります。

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

ハッシュの初期サイズは、4となっています。

#define DICT_HT_INITIAL_SIZE     4

dictht構造体は、dict構造体すぐ上で定義されています。

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

Hashテーブル中の各要素はdictEntryで定義されている。同じハッシュ値で衝突した場合にはChain法が使われています。

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

ハッシュが拡張されるのは、ハッシュの使用量がサイズを上回りかつバックグラウンド処理が行われていないとき、もしくはハッシュサイズの5倍の大きさとなったときに強制的に実行されます。
バックグラウンド処理が行われていないときにハッシュの拡張されるのは、バックグラウンド処理の際にプロセスをforkしたあとRedisはCoWを利用するためメモリーをあまり使いたくないという背景があります。

static int _dictExpandIfNeeded(dict *d)
{
    /* Incremental rehashing already in progress. Return. */
    if (dictIsRehashing(d)) return DICT_OK;

    /* If the hash table is empty expand it to the initial size. */
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    /* If we reached the 1:1 ratio, and we are allowed to resize the hash
     * table (global setting) or we should avoid it but the ratio between
     * elements/buckets is over the "safe" threshold, we resize doubling
     * the number of buckets. */
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
    {
        return dictExpand(d, d->ht[0].used*2);
    }
    return DICT_OK;
}

https://github.com/antirez/redis/blob/unstable/src/dict.c#L179-L231

増分rehashingは以下の箇所で行われています。移行が完了するまでは、この関数は1を返し続けます。

int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    if (!dictIsRehashing(d)) return 0;

    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        de = d->ht[0].table[d->rehashidx];
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {
            uint64_t h;

            nextde = de->next;
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;
    }

    /* Check if we already rehashed the whole table... */
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    }

    /* More to rehash... */
    return 1;
}

コマンド

https://github.com/antirez/redis/blob/unstable/src/server.h#L1375-L1394

Redisの各種コマンドは以下のような構造体で管理されています。

struct redisCommand {
    char *name;
    redisCommandProc *proc;
    int arity;
    char *sflags;   /* Flags as string representation, one char per flag. */
    uint64_t flags; /* The actual flags, obtained from the 'sflags' field. */
    /* Use a function to determine keys arguments in a command line.
     * Used for Redis Cluster redirect. */
    redisGetKeysProc *getkeys_proc;
    /* What keys should be loaded in background when calling this command? */
    int firstkey; /* The first argument that's a key (0 = no keys) */
    int lastkey;  /* The last argument that's a key */
    int keystep;  /* The step between first and last key */
    long long microseconds, calls;
    int id;     /* Command ID. This is a progressive ID starting from 0 that
                   is assigned at runtime, and is used in order to check
                   ACLs. A connection is able to execute a given command if
                   the user associated to the connection has this command
                   bit set in the bitmap of allowed commands. */
};

nameにはコマンド名、procには各コマンドを実行した際に実際に呼び出される関数のポインタとなっており、server.cのredisCommandTable変数で以下のように定義されています。コマンド実行の際にはserver.cのprocessCommand関数を経由して実行されます。

https://github.com/antirez/redis/blob/unstable/src/server.c#L75-L1002

struct redisCommand redisCommandTable[] = {
    {"module",moduleCommand,-2,
     "admin no-script",
     0,NULL,0,0,0,0,0,0},

    {"get",getCommand,2,
     "read-only fast @string",
     0,NULL,1,1,1,0,0,0},

    /* Note that we can't flag set as fast, since it may perform an
     * implicit DEL of a large key. */
    {"set",setCommand,-3,
     "write use-memory @string",
     0,NULL,1,1,1,0,0,0},
:
:
    {"lolwut",lolwutCommand,-1,
     "read-only fast",
     0,NULL,0,0,0,0,0,0},

    {"acl",aclCommand,-2,
     "admin no-script ok-loading ok-stale",
     0,NULL,0,0,0,0,0,0}
};

クライアント

https://github.com/antirez/redis/blob/unstable/src/server.h#L782-L845

Redis Serverの処理結果でクライアントに返すものは、処理結果を直接クライアントに送らず、一旦Client用のClient Output Bufferに格納されますが、このClient用のClient Output Bufferにはdynamicとstatic(16KB)なものがあり、client構造体のreplyとbufで管理されています。どちらで管理されるかはデータのサイズに応じ、bufが溢れるとreplyに格納される形となります。これらの情報はCLIENT LISTコマンドの結果のoll,oblからそれぞれ確認できます。
また、クライアントから受け取ったリクエストは一旦Query Bufferに格納されますが、client構造体のquerybufに相当します。

typedef struct client {
    uint64_t id;            /* Client incremental unique ID. */
    int fd;                 /* Client socket. */
    int resp;               /* RESP protocol version. Can be 2 or 3. */
    redisDb *db;            /* Pointer to currently SELECTed DB. */
    robj *name;             /* As set by CLIENT SETNAME. */
    sds querybuf;           /* Buffer we use to accumulate client queries. */
    size_t qb_pos;          /* The position we have read in querybuf. */
    sds pending_querybuf;   /* If this client is flagged as master, this buffer
                               represents the yet not applied portion of the
                               replication stream that we are receiving from
                               the master. */
    size_t querybuf_peak;   /* Recent (100ms or more) peak of querybuf size. */
    int argc;               /* Num of arguments of current command. */
    robj **argv;            /* Arguments of current command. */
    struct redisCommand *cmd, *lastcmd;  /* Last command executed. */
    user *user;             /* User associated with this connection. If the
                               user is set to NULL the connection can do
                               anything (admin). */
    int reqtype;            /* Request protocol type: PROTO_REQ_* */
    int multibulklen;       /* Number of multi bulk arguments left to read. */
    long bulklen;           /* Length of bulk argument in multi bulk request. */
    list *reply;            /* List of reply objects to send to the client. */
    unsigned long long reply_bytes; /* Tot bytes of objects in reply list. */
    size_t sentlen;         /* Amount of bytes already sent in the current
                               buffer or object being sent. */
    time_t ctime;           /* Client creation time. */
    time_t lastinteraction; /* Time of the last interaction, used for timeout */
    time_t obuf_soft_limit_reached_time;
    int flags;              /* Client flags: CLIENT_* macros. */
    int authenticated;      /* Needed when the default user requires auth. */
    int replstate;          /* Replication state if this is a slave. */
    int repl_put_online_on_ack; /* Install slave write handler on ACK. */
    int repldbfd;           /* Replication DB file descriptor. */
    off_t repldboff;        /* Replication DB file offset. */
    off_t repldbsize;       /* Replication DB file size. */
    sds replpreamble;       /* Replication DB preamble. */
    long long read_reploff; /* Read replication offset if this is a master. */
    long long reploff;      /* Applied replication offset if this is a master. */
    long long repl_ack_off; /* Replication ack offset, if this is a slave. */
    long long repl_ack_time;/* Replication ack time, if this is a slave. */
    long long psync_initial_offset; /* FULLRESYNC reply offset other slaves
                                       copying this slave output buffer
                                       should use. */
    char replid[CONFIG_RUN_ID_SIZE+1]; /* Master replication ID (if master). */
    int slave_listening_port; /* As configured with: SLAVECONF listening-port */
    char slave_ip[NET_IP_STR_LEN]; /* Optionally given by REPLCONF ip-address */
    int slave_capa;         /* Slave capabilities: SLAVE_CAPA_* bitwise OR. */
    multiState mstate;      /* MULTI/EXEC state */
    int btype;              /* Type of blocking op if CLIENT_BLOCKED. */
    blockingState bpop;     /* blocking state */
    long long woff;         /* Last write global replication offset. */
    list *watched_keys;     /* Keys WATCHED for MULTI/EXEC CAS */
    dict *pubsub_channels;  /* channels a client is interested in (SUBSCRIBE) */
    list *pubsub_patterns;  /* patterns a client is interested in (SUBSCRIBE) */
    sds peerid;             /* Cached peer ID. */
    listNode *client_list_node; /* list node in client list */

    /* Response buffer */
    int bufpos;
    char buf[PROTO_REPLY_CHUNK_BYTES];
} client;

サーバ

Redisサーバに関する各種状態が格納されています。パラメータで設定した内容の多くがこちらに格納される形となります。

レプリケーションは、Replication ID, offsetのペア情報を元に行います。

レプリケーションIDについて、replid,replid2のように2つもっているのは、フェイルオーバーで旧スレーブが新マスターへと昇格したときに、新マスターは旧マスターのレプリケーションIDを覚えていると、その他のスレーブが新マスターへ同期を行うとき、その旧マスターIDを使って部分同期を試みるからとなります。こちらはRedis4.0以降の部分同期に関するPSYNC2の改良によるものとなります。

レプリケーション切断中のマスターへのwriteは別で保存しておき、回復時にbacklog中にそのReplication ID, offsetの情報があり、かつ無効な情報でなければ、フル同期ではなく部分同期の実行が可能となります(実行箇所: https://github.com/antirez/redis/blob/unstable/src/replication.c#L442-L543 )

struct redisServer {
    /* General */
    pid_t pid;                  /* Main process pid. */
    char *configfile;           /* Absolute config file path, or NULL */
    char *executable;           /* Absolute executable file path. */
    char **exec_argv;           /* Executable argv vector (copy). */
    int dynamic_hz;             /* Change hz value depending on # of clients. */
    int config_hz;              /* Configured HZ value. May be different than
                                   the actual 'hz' field value if dynamic-hz
                                   is enabled. */
    int hz;                     /* serverCron() calls frequency in hertz */
    redisDb *db;
    dict *commands;             /* Command table */
    dict *orig_commands;        /* Command table before command renaming. */
    aeEventLoop *el;
    unsigned int lruclock;      /* Clock for LRU eviction */
:
:
    /* Replication (master) */
    char replid[CONFIG_RUN_ID_SIZE+1];  /* My current replication ID. */
    char replid2[CONFIG_RUN_ID_SIZE+1]; /* replid inherited from master*/
    long long master_repl_offset;   /* My current replication offset */
    long long second_replid_offset; /* Accept offsets up to this for replid2. */
    int slaveseldb;                 /* Last SELECTed DB in replication output */
    int repl_ping_slave_period;     /* Master pings the slave every N seconds */
    char *repl_backlog;             /* Replication backlog for partial syncs */
    long long repl_backlog_size;    /* Backlog circular buffer size */
    long long repl_backlog_histlen; /* Backlog actual data length */
    long long repl_backlog_idx;     /* Backlog circular buffer current offset,
                                       that is the next byte will'll write to.*/
    long long repl_backlog_off;     /* Replication "master offset" of first
                                       byte in the replication backlog buffer.*/
    time_t repl_backlog_time_limit; /* Time without slaves after the backlog
                                       gets released. */
    time_t repl_no_slaves_since;    /* We have no slaves since that time.
                                       Only valid if server.slaves len is 0. */
    int repl_min_slaves_to_write;   /* Min number of slaves to write. */
    int repl_min_slaves_max_lag;    /* Max lag of <count> slaves to write. */
    int repl_good_slaves_count;     /* Number of slaves with lag <= max_lag. */
    int repl_diskless_sync;         /* Send RDB to slaves sockets directly. */
    int repl_diskless_sync_delay;   /* Delay to start a diskless repl BGSAVE. */
:
:
    /* Mutexes used to protect atomic variables when atomic builtins are
     * not available. */
    pthread_mutex_t lruclock_mutex;
    pthread_mutex_t next_client_id_mutex;
    pthread_mutex_t unixtime_mutex;
};

Redis Cluster

ノード

マスター(slaveof)やスレーブ(slave)の状態が格納されています。Redis ClusterではHash Slotによるスロット管理が行われていますが、slots変数に情報が格納されています。また、Cluster BusでGossipプロトコルによるバイナリ通信がノード間で行われています。こちらの仕組みはRaftをベースにした実装となっており、その際に重要な概念となるconfigEpoch(Raftでいうterm)の情報を格納しています。

typedef struct clusterNode {
    mstime_t ctime; /* Node object creation time. */
    char name[CLUSTER_NAMELEN]; /* Node name, hex string, sha1-size */
    int flags;      /* CLUSTER_NODE_... */
    uint64_t configEpoch; /* Last configEpoch observed for this node */
    unsigned char slots[CLUSTER_SLOTS/8]; /* slots handled by this node */
    int numslots;   /* Number of slots handled by this node */
    int numslaves;  /* Number of slave nodes, if this is a master */
    struct clusterNode **slaves; /* pointers to slave nodes */
    struct clusterNode *slaveof; /* pointer to the master node. Note that it
                                    may be NULL even if the node is a slave
                                    if we don't have the master node in our
                                    tables. */
    mstime_t ping_sent;      /* Unix time we sent latest ping */
    mstime_t pong_received;  /* Unix time we received the pong */
    mstime_t fail_time;      /* Unix time when FAIL flag was set */
    mstime_t voted_time;     /* Last time we voted for a slave of this master */
    mstime_t repl_offset_time;  /* Unix time we received offset for this node */
    mstime_t orphaned_time;     /* Starting time of orphaned master condition */
    long long repl_offset;      /* Last known repl offset for this node. */
    char ip[NET_IP_STR_LEN];  /* Latest known IP address of this node */
    int port;                   /* Latest known clients port of this node */
    int cport;                  /* Latest known cluster port of this node. */
    clusterLink *link;          /* TCP/IP link with this node */
    list *fail_reports;         /* List of nodes signaling this as failing */
} clusterNode;

クラスターの状態

typedef struct clusterState {
    clusterNode *myself;  /* This node */
    uint64_t currentEpoch;
    int state;            /* CLUSTER_OK, CLUSTER_FAIL, ... */
    int size;             /* Num of master nodes with at least one slot */
    dict *nodes;          /* Hash table of name -> clusterNode structures */
    dict *nodes_black_list; /* Nodes we don't re-add for a few seconds. */
    clusterNode *migrating_slots_to[CLUSTER_SLOTS];
    clusterNode *importing_slots_from[CLUSTER_SLOTS];
    clusterNode *slots[CLUSTER_SLOTS];
    uint64_t slots_keys_count[CLUSTER_SLOTS];
    rax *slots_to_keys;
    /* The following fields are used to take the slave state on elections. */
    mstime_t failover_auth_time; /* Time of previous or next election. */
    int failover_auth_count;    /* Number of votes received so far. */
    int failover_auth_sent;     /* True if we already asked for votes. */
    int failover_auth_rank;     /* This slave rank for current auth request. */
    uint64_t failover_auth_epoch; /* Epoch of the current election. */
    int cant_failover_reason;   /* Why a slave is currently not able to
                                   failover. See the CANT_FAILOVER_* macros. */
    /* Manual failover state in common. */
    mstime_t mf_end;            /* Manual failover time limit (ms unixtime).
                                   It is zero if there is no MF in progress. */
    /* Manual failover state of master. */
    clusterNode *mf_slave;      /* Slave performing the manual failover. */
    /* Manual failover state of slave. */
    long long mf_master_offset; /* Master offset the slave needs to start MF
                                   or zero if stil not received. */
    int mf_can_start;           /* If non-zero signal that the manual failover
                                   can start requesting masters vote. */
    /* The followign fields are used by masters to take state on elections. */
    uint64_t lastVoteEpoch;     /* Epoch of the last vote granted. */
    int todo_before_sleep; /* Things to do in clusterBeforeSleep(). */
    /* Messages received and sent by type. */
    long long stats_bus_messages_sent[CLUSTERMSG_TYPE_COUNT];
    long long stats_bus_messages_received[CLUSTERMSG_TYPE_COUNT];
    long long stats_pfail_nodes;    /* Number of nodes in PFAIL status,
                                       excluding nodes without address. */
} clusterState;

クラスター間通信で使用されるメッセージ

https://github.com/antirez/redis/blob/unstable/src/cluster.h#L222-L248

Redis Clusterでは、他のノードの状態を知るのに、信頼しているノードが持っているその他のノードの状態について、PINGでノード間で生存確認しつつそのPINGにGossipプロトコルの情報と含めることで行います。

union clusterMsgData {
    /* PING, MEET and PONG */
    struct {
        /* Array of N clusterMsgDataGossip structures */
        clusterMsgDataGossip gossip[1];
    } ping;

    /* FAIL */
    struct {
        clusterMsgDataFail about;
    } fail;

    /* PUBLISH */
    struct {
        clusterMsgDataPublish msg;
    } publish;

    /* UPDATE */
    struct {
        clusterMsgDataUpdate nodecfg;
    } update;

    /* MODULE */
    struct {
        clusterMsgModule msg;
    } module;
};

https://github.com/antirez/redis/blob/unstable/src/cluster.h#L185-L197

typedef struct {
    char nodename[CLUSTER_NAMELEN];
    uint32_t ping_sent;
    uint32_t pong_received;
    char ip[NET_IP_STR_LEN];  /* IP address last time it was seen */
    uint16_t port;              /* base port last time it was seen */
    uint16_t cport;             /* cluster port last time it was seen */
    uint16_t flags;             /* node->flags copy */
    uint32_t notused1;
} clusterMsgDataGossip;

内部エンコーディング

int

https://github.com/antirez/redis/blob/unstable/src/object.c#L469-L474

long型の値をそのまま格納する方法となります。

} else {
    if (o->encoding == OBJ_ENCODING_RAW) sdsfree(o->ptr);
    o->encoding = OBJ_ENCODING_INT;
    o->ptr = (void*) value;
    return o;
}

embstr

https://github.com/antirez/redis/blob/unstable/src/sds.h#L51-L56

embstrはsdshdr8構造体を通してbuf中にcharの配列として格納します。

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

https://github.com/antirez/redis/blob/unstable/src/object.c#L81-L110

以下の箇所で値を設定しています。

robj *createEmbeddedStringObject(const char *ptr, size_t len) {
    robj *o = zmalloc(sizeof(robj)+sizeof(struct sdshdr8)+len+1);
    struct sdshdr8 *sh = (void*)(o+1);

    o->type = OBJ_STRING;
    o->encoding = OBJ_ENCODING_EMBSTR;
    o->ptr = sh+1;
    o->refcount = 1;
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    } else {
        o->lru = LRU_CLOCK();
    }

    sh->len = len;
    sh->alloc = len;
    sh->flags = SDS_TYPE_8;
    if (ptr == SDS_NOINIT)
        sh->buf[len] = '\0';
    else if (ptr) {
        memcpy(sh->buf,ptr,len);
        sh->buf[len] = '\0';
    } else {
        memset(sh->buf,0,len+1);
    }
    return o;
}

embstrでは、redisObjectとsdshdr、格納する値のサイズを一度にメモリ確保します。

raw

https://github.com/antirez/redis/blob/unstable/src/object.c#L75-L79

rawはsdsの文字列をそのまま格納する方法となります。

robj *createRawStringObject(const char *ptr, size_t len) {
    return createObject(OBJ_STRING, sdsnewlen(ptr,len));
}

robj *createObject(int type, void *ptr) {
    robj *o = zmalloc(sizeof(*o));
    o->type = type;
    o->encoding = OBJ_ENCODING_RAW;
    o->ptr = ptr;
    o->refcount = 1;

    /* Set the LRU to the current lruclock (minutes resolution), or
     * alternatively the LFU counter. */
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    } else {
        o->lru = LRU_CLOCK();
    }
    return o;
}

rawでは、redisObjectのメモリ確保を行ったあと、sdshdrと格納する値のメモリーを確保を分けて行います。

44バイトの境界について

44バイト以下の場合はembstrが使用され、それより大きい倍はrawを使用します。3.2.0以前では、39バイトが境界でした。

redisObjectが16バイト、SDS header(sdshdr)が3バイト、nullが1バイトで計20バイトを使用しました。
3バイトは、SDSヘッダーがデータ長に基づいて3,5,9,17バイトの4種類のデータ型を利用し、データ長が短いことによるものとなります。
3.2.0以前はsdshdrが8バイトのため計25バイトを使用していました。

jemallocは、32,64,128バイトの単位でメモリが割当てられます。その時、上記を考慮するとデータに使用できるサイズが64-20=44(64-25=39)となり、メモリーフラグメンテーションが小さくなることを考慮してエンコーディングがされています。

quicklist

List型で3.2以前では、ziplist と Linked List が使用されており、以下のような特徴がありました。3.2以降では、両者のメリットを取り入れるようにquicklistという内部エンコーディングが使用されるようになりました。

ziplist
- メリット
  - ziplistは連続したメモリ領域を利用するように設計されており、メモリの使用効率が高い
- デメリット
  - データが変更されるとメモリの再割り当てのためにコピーが発生する確率が高くなるため、データ量が大きくなるに連れてこちらのコピーのコストが大きい
  - 中間のデータ等は順番に辿っていくしかない
Linked List
- メリット
  - テーブルの両端で簡単にプッシュしてポップすることができる
- デメリット
  - 二重リンクリストの各ノードが別々のメモリブロックであり、アドレスが連続していないため、ノードがメモリフラグメントを生成する可能性が高い(メモリのオーバーヘッドが大きい)

quicklistでは、Listでアクセスされる可能性が最も高いのは両端のデータなので、一定以上の深さ(list-compress-depth)の中間のデータはあまり使用されないため、圧縮してメモリー空間を効率よく使用する工夫がされています。また、圧縮前のサイズ(list-max-ziplist-size)でも制限されます。
圧縮にはLZFが使用されます。

圧縮されていないときはziplistが使用されます。圧縮時はquicklistLZF構造体が使用されchar型配列にデータを格納します。

https://github.com/antirez/redis/blob/unstable/src/quicklist.h#L67-L80

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned long len;          /* number of quicklistNodes */
    int fill : 16;              /* fill factor for individual nodes */
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;

https://github.com/antirez/redis/blob/unstable/src/quicklist.h#L44-L55

quicklist中の各要素はquicklistNode構造体として以下のように定義されています。

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

https://github.com/antirez/redis/blob/unstable/src/quicklist.h#L57-L65

typedef struct quicklistLZF {
    unsigned int sz; /* LZF size in bytes*/
    char compressed[];
} quicklistLZF;

ziplist

ziplistは、前のエントリのサイズ、現在のエントリのサイズ、文字列そのもの、というシーケンスを格納しています。
ポインタを利用せずにオフセットのみで管理しているため、この型で管理できる範囲のサイズまで管理することができます。
ただし、ziplistは連続したメモリ領域を利用するように設計されており、メモリの使用効率が高い一方で、データが変更されるとメモリの再割り当てのためにコピーが発生する確率が高くなるため、データ量が大きくなるに連れてこちらのコピーのコストが大きくなることが想定されます。そのため、hash-max-ziplist-entries, hash-max-ziplist-valueの値を適切なものに設定する必要があります。

https://github.com/antirez/redis/blob/unstable/src/ziplist.c#L268-L289

typedef struct zlentry {
    unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
    unsigned int prevrawlen;     /* Previous entry len. */
    unsigned int lensize;        /* Bytes used to encode this entry type/len.
                                    For example strings have a 1, 2 or 5 bytes
                                    header. Integers always use a single byte.*/
    unsigned int len;            /* Bytes used to represent the actual entry.
                                    For strings this is just the string length
                                    while for integers it is 1, 2, 3, 4, 8 or
                                    0 (for 4 bit immediate) depending on the
                                    number range. */
    unsigned int headersize;     /* prevrawlensize + lensize. */
    unsigned char encoding;      /* Set to ZIP_STR_* or ZIP_INT_* depending on
                                    the entry encoding. However for 4 bits
                                    immediate integers this can assume a range
                                    of values and must be range-checked. */
    unsigned char *p;            /* Pointer to the very start of the entry, that
                                    is, this points to prev-entry-len field. */
} zlentry;

zipmap

Redis 2.6未満、Hashはzipmapという内部エンコーディングを利用することができました。現在は前述のziplistが利用されています。
zipmapはziplistのような構造体で管理せず、charのポインタとして管理されています。例えば、"foo" => "bar", "hello" => "world"のようなマッピングであれば以下の形式で保存されます。現在は、RDBファイルからの読み込みで互換性のために使用されているようです。

<zmlen><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"

https://github.com/antirez/redis/blob/unstable/src/zipmap.c#L96-L102

以下の箇所で初期化を行っています。

unsigned char *zipmapNew(void) {
    unsigned char *zm = zmalloc(2);

    zm[0] = 0; /* Length */
    zm[1] = ZIPMAP_END;
    return zm;
}

https://github.com/antirez/redis/blob/unstable/src/zipmap.c#L208-L277

以下の箇所で要素の追加を行っています。

unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char *val, unsigned int vlen, int *update) {
    unsigned int zmlen, offset;
    unsigned int freelen, reqlen = zipmapRequiredLength(klen,vlen);
    unsigned int empty, vempty;
    unsigned char *p;

    freelen = reqlen;
    if (update) *update = 0;
    p = zipmapLookupRaw(zm,key,klen,&zmlen);
    if (p == NULL) {
        /* Key not found: enlarge */
        zm = zipmapResize(zm, zmlen+reqlen);
        p = zm+zmlen-1;
        zmlen = zmlen+reqlen;

        /* Increase zipmap length (this is an insert) */
        if (zm[0] < ZIPMAP_BIGLEN) zm[0]++;
    } else {
        /* Key found. Is there enough space for the new value? */
        /* Compute the total length: */
        if (update) *update = 1;
        freelen = zipmapRawEntryLength(p);
        if (freelen < reqlen) {
            /* Store the offset of this key within the current zipmap, so
             * it can be resized. Then, move the tail backwards so this
             * pair fits at the current position. */
            offset = p-zm;
            zm = zipmapResize(zm, zmlen-freelen+reqlen);
            p = zm+offset;

            /* The +1 in the number of bytes to be moved is caused by the
             * end-of-zipmap byte. Note: the *original* zmlen is used. */
            memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));
            zmlen = zmlen-freelen+reqlen;
            freelen = reqlen;
        }
    }

    /* We now have a suitable block where the key/value entry can
     * be written. If there is too much free space, move the tail
     * of the zipmap a few bytes to the front and shrink the zipmap,
     * as we want zipmaps to be very space efficient. */
    empty = freelen-reqlen;
    if (empty >= ZIPMAP_VALUE_MAX_FREE) {
        /* First, move the tail <empty> bytes to the front, then resize
         * the zipmap to be <empty> bytes smaller. */
        offset = p-zm;
        memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));
        zmlen -= empty;
        zm = zipmapResize(zm, zmlen);
        p = zm+offset;
        vempty = 0;
    } else {
        vempty = empty;
    }

    /* Just write the key + value and we are done. */
    /* Key: */
    p += zipmapEncodeLength(p,klen);
    memcpy(p,key,klen);
    p += klen;
    /* Value: */
    p += zipmapEncodeLength(p,vlen);
    *p++ = vempty;
    memcpy(p,val,vlen);
    return zm;
}

intset

https://github.com/antirez/redis/blob/unstable/src/intset.h#L35-L398

値の大きさに応じたエンコーディングと8バイトの符号付きintの配列として定義されています。

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

上記のようにデータの格納はint8_tの配列の連続したメモリー空間を利用しているため効率的に利用することができます。

https://github.com/antirez/redis/blob/unstable/src/intset.c#L38-L42

エンコーディングの種類は以下のように定義されています。

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

https://github.com/antirez/redis/blob/unstable/src/intset.c#L44-L52

上記エンコーディングは値の大きさを元に決まります。int型の要素の最小値が2^15以下の数字(16bit数)であれば、Redisは16bit長を使い、一つでも2^15より大きく2^31以下の数字(32bit数)があれば、Redisは32bit長を使い、2^31より大きければRedis64bit長を使います。

static uint8_t _intsetValueEncoding(int64_t v) {
    if (v < INT32_MIN || v > INT32_MAX)
        return INTSET_ENC_INT64;
    else if (v < INT16_MIN || v > INT16_MAX)
        return INTSET_ENC_INT32;
    else
        return INTSET_ENC_INT16;
}

https://github.com/antirez/redis/blob/unstable/src/intset.c#L111-L154

探索には2分木探索が行われています。

while(max >= min) {
    mid = ((unsigned int)min + (unsigned int)max) >> 1;
    cur = _intsetGet(is,mid);
    if (value > cur) {
        min = mid+1;
    } else if (value < cur) {
        max = mid-1;
    } else {
        break;
    }
}

hashtable

https://github.com/antirez/redis/blob/unstable/src/dict.h#L47-L56

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

skiplist

Skip Listは、レイヤー(level)の概念を持ち、一番低いレイヤーでは、ソートされた(score順。scoreはSorted Setのデータのスコアに使用されます)リスト(zskiplistNode)を持ちます。各項目(ele)は、事前に定義された確率 ZSKIPLIST_P (=1/4 https://github.com/antirez/redis/blob/unstable/src/server.h#L383 )で、一つの上のレイヤーでも同様の項目を持つようになり、それを一つ上のレイヤーへと繰り返していきます。そのため、レイヤーが上がる毎にある項目から次の項目までの飛ばす数(span)が大きくなる傾向があります。

https://github.com/antirez/redis/blob/unstable/src/server.h#L874-L889

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

挿入や探索の際には、一番上のレイヤーから探索していき、対象の項目がなければ下のレイヤーを探索していくといった動作をします。各操作の計算量は、平均O(log(n))の計算量となり、最悪の場合O(n)となります。

平均レイヤー数は、1(1-p)+2p(1-p)+3p^2(1-p)+…. = (1-p)Σkp^(k-1)=1/(1-p)となり、Redisの場合、平均4/3のレイヤーがある計算となります。
平衡木は各項目leftとrightの2つのポインタを持つ一方で、skiplistは各項目、平均1/(1-p)のポインタを持ち、メモリー空間をより効率的に使用することができます。

現在Sorted Setでは要素数が一定数(zset-max-ziplist-entries)以下、かつ一定サイズ(zset-max-ziplist-value)以下のときにはziplistが使用され、それ以外のときにはskiplistが使用されます。
skiplist利用時にも、dictが使用され、スコアとデータの対応関係の照合に利用されます。skiplistはスコアに基づいてデータを照合するために利用されます。

ziplist
- メリット
  - ziplistは連続したメモリ領域を利用するように設計されており、メモリの使用効率が高い
- デメリット
  - データが変更されるとメモリの再割り当てのためにコピーが発生する確率が高くなるため、データ量が大きくなるに連れてこちらのコピーのコストが大きい
  - 中間のデータ等は順番に辿っていくしかない
skiplist
- メリット
  - データが増えても計算量は平均O(log(n))に抑えられる
  - 平衡木よりはメモリー空間効率が良い
  - キャッシュの局所性は他の平衡木同様に有効に利用できる
- デメリット
  - メモリー空間効率の工夫がされているもののziplistほどではない
https://github.com/antirez/redis/blob/unstable/src/t_zset.c#L118-L127

Skip Listの肝となる、確率的な挙動は以下の関数で定義されています。

int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

Sparse/Dense

https://github.com/antirez/redis/blob/unstable/src/hyperloglog.c#L182-L188

Sparse/Denseは共にhllhdr構造体にデータを格納され、エンコーディング形式に合わせてencodingが設定されます。SparseとDenseはエンコーディング方式に応じてregistersに格納される値が異なります。

struct hllhdr {
    char magic[4];      /* "HYLL" */
    uint8_t encoding;   /* HLL_DENSE or HLL_SPARSE. */
    uint8_t notused[3]; /* Reserved for future use, must be zero. */
    uint8_t card[8];    /* Cached cardinality, little endian. */
    uint8_t registers[]; /* Data bytes. */
};

https://github.com/antirez/redis/blob/unstable/src/hyperloglog.c#L349-L361

Denseの各要素は6bitの整数を並べたもので表されます。
_byteで6bitの整数の何番目のものか、_fbで6bitの整数のうちのどの場所かを示します。

#define HLL_DENSE_SET_REGISTER(p,regnum,val) do { \
    uint8_t *_p = (uint8_t*) p; \
    unsigned long _byte = regnum*HLL_BITS/8; \
    unsigned long _fb = regnum*HLL_BITS&7; \
    unsigned long _fb8 = 8 - _fb; \
    unsigned long _v = val; \
    _p[_byte] &= ~(HLL_REGISTER_MAX << _fb); \
    _p[_byte] |= _v << _fb; \
    _p[_byte+1] &= ~(HLL_REGISTER_MAX >> _fb8); \
    _p[_byte+1] |= _v >> _fb8; \
} while(0)

Sparseはランレングス圧縮した値を格納。HLL_SPARSE_VAL_SETで値とその長さをセットしています。

#define HLL_SPARSE_VAL_SET(p,val,len) do { \
    *(p) = (((val)-1)<<2|((len)-1))|HLL_SPARSE_VAL_BIT; \
} while(0)

以下の箇所で具体的な値を設定しています。

    } else {
        /* Handle splitting of VAL. */
        int curval = HLL_SPARSE_VAL_VALUE(p);

        if (index != first) {
            len = index-first;
            HLL_SPARSE_VAL_SET(n,curval,len);
            n++;
        }
        HLL_SPARSE_VAL_SET(n,count,1);
        n++;
        if (index != last) {
            len = last-index;
            HLL_SPARSE_VAL_SET(n,curval,len);
            n++;
        }
    }

長さは以下のように決定している。

https://github.com/antirez/redis/blob/unstable/src/hyperloglog.c#L778

int last = first+span-1; /* Last register covered by the sequence. */

https://github.com/antirez/redis/blob/unstable/src/hyperloglog.c#L680-L702

    while(p < end) {
        long oplen;

        /* Set span to the number of registers covered by this opcode.
         *
         * This is the most performance critical loop of the sparse
         * representation. Sorting the conditionals from the most to the
         * least frequent opcode in many-bytes sparse HLLs is faster. */
        oplen = 1;
        if (HLL_SPARSE_IS_ZERO(p)) {
            span = HLL_SPARSE_ZERO_LEN(p);
        } else if (HLL_SPARSE_IS_VAL(p)) {
            span = HLL_SPARSE_VAL_LEN(p);
        } else { /* XZERO. */
            span = HLL_SPARSE_XZERO_LEN(p);
            oplen = 2;
        }
        /* Break if this opcode covers the register as 'index'. */
        if (index <= first+span-1) break;
        prev = p;
        p += oplen;
        first += span;
    }

https://github.com/antirez/redis/blob/unstable/src/hyperloglog.c#L372-L373

#define HLL_SPARSE_VAL_VALUE(p) ((((*(p)) >> 2) & 0x1f)+1)
#define HLL_SPARSE_VAL_LEN(p) (((*(p)) & 0x3)+1)

GeoHash

https://github.com/antirez/redis/blob/unstable/src/geohash.h#L66-L69

bits変数で64ビット長のunsignedの整数で表されています。

typedef struct {
    uint64_t bits;
    uint8_t step;
} GeoHashBits;

My Twitter & RSS

@hayashier

Categories: Cloud, General, Get Started, NoSQL, and Redis