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 –
https://hayashier.com/redis-memcached-code-reading/

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

Dive Deep Redis Internals ~ GETコマンド実行時の動作 ~
https://hayashier.com/dive-deep-redis/

レポジトリは以下のURLとなります。
https://github.com/antirez/redis

データ型

Basic

  • String
    • コマンド例: SET,GET,STRLEN,APPEND,SETRANGE,SETNX,MSET,MGET
    • 特徴
      • キーに値を関連づけるための最もシンプルなタイプ
      • バイナリセーフな文字列(SDSによる実装。jpegのような画像データを含むバイナリデータもシリアライズ化して格納できる)
      • (最大512 MB以下の制限は取り除かれており、最大64bit長 https://github.com/antirez/redis/pull/2509 )
    • ユースケース
      • キャッシュ
      • カウンター
      • リアルタイムメトリクス
      • その他
        • HTML フラグメント
        • ページのキャッシング
  • List
    • コマンド例: LPUSH,RPUSH,LINSERT,LRANGE,LPUSHX,RPUSHX,LPOP,RPOP,LINDEX,LTRIM,LSET,BLPOP,BRPOP
    • 特徴
      • 文字列のコレクション。挿入された順序を保つ
    • メリット/デメリット
      • メリット
        • 新しい要素をリストの先頭や末尾に追加する操作は定数時間で完了。
      • デメリット
        • 中間部分へのアクセスが遅い。特に大きなデータの中間部分で顕著
    • ユースケース
      • ログ
      • キュー
      • メッセージ通過
      • 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独自の機能として、コンシューマーグループのサポートでクライアントのグループが協働することを可能にする。例えば、グループ内のConsumerは、ID 別に項目を検索したり、項目の処理を確認したり、または保留中のメッセージの所有権を主張したりすることができます。
      • 類似機能を持つkafkaはスケーラビリティが高く素晴らしい設計だが、複雑すぎる
    • ユースケース
      • チャットシステム
      • メッセージブローカー
      • キューイングシステム
      • 統合ログ

その他代表コマンド

  • キー管理
    • コマンド例: 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

内部エンコーディング

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

実行例

  • 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"
  • SET
> 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
  • GEO
> 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"

バックアップ: 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 ポリシーに依存するが)
      • 過去にBRPOPLPUSHのようなブロックを伴うコマンドで、同じデータセットで正確に復元されないバグがあり、RDBではこのようなことは起き得ない。
      • ElastiCacheのようなマネージドサービスを利用している場合、基盤障害時はノードの入れ替えが行われるが、AOFはインスタンスストアに保存されるので、入れ替わったあとのノードで適用することができないため、AOFの効果がない。

メモリ管理

アーキテクチャ

  • 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のコネクションが切断されます。

各クライアント毎にRedis ServerはCOBを用意し、サーバでの処理結果を直接クライアントへ送らずに一旦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には依存しすぎず、アプリケーション側でメモリ管理を行うことが意識されているため、レスポンスの安定感が期待されます。

https://github.com/antirez/redis/blob/unstable/src/zmalloc.c#L98-L110

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とします。 https://github.com/antirez/redis/blob/unstable/src/zmalloc.h#L38-L71

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

mallocの動作について

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

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

malloc
https://code.woboq.org/userspace/glibc/malloc/malloc.c.html#2263

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

jemalloc
http://jemalloc.net/
実装
https://github.com/jemalloc/jemalloc

Scalable memory allocation using jemalloc

Posted by Facebook Engineering on Monday, January 3, 2011

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

Redis特有の各種概念

RESP(REdis Serialization Protocol)

概要

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

1. 実装容易
2. パースが高速
3. 人間が読める

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
https://redis.io/topics/protocol

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関数)ことが下記コードから確認できます。

https://github.com/antirez/redis/blob/4.0.10/src/networking.c#L1332-L1347

/* 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");
}

PROTO_REQ_INLINEの際に使用されるprocessInlineBuffer関数はClient Query Bufferを消費して、client構造体に実行するコマンドを格納することになるため、Redisクライアントを利用しているときは多くはPROTO_REQ_MULTIBULKの種類で送られています。

上記挙動はRedis 2.8で追加されたものとなります。
https://raw.githubusercontent.com/antirez/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の実装での文字列は基本的にこちらの実装が利用されています。

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

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

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

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

文字列長を増加させるとき、SDS_MAX_PREALLOC(=1MB https://github.com/antirez/redis/blob/unstable/src/sds.h#L36 )と比較し、それ未満ならリクエストされたメモリの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;

https://github.com/antirez/redis/blob/unstable/src/sds.c#L60-L74
確保する文字列長に応じてヘッダーの種類を設定し、それに応じた構造体を定義しています。

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
}

https://github.com/antirez/redis/blob/unstable/src/sds.h#L45-L74

#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[];
};

Hacking Strings
https://redis.io/topics/internals-sds
Simple Dynamic Strings
https://github.com/antirez/sds
実装
https://github.com/antirez/redis/blob/unstable/src/sds.c

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;

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

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 )。桁が上がる毎にグリッド領域が狭まります。

レプリケーション

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

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

フェイルオーバー

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

(*1)サービスで提供されている場合、自動フェイルオーバー機能が提供されていることもあります。
(*2)自動フェイルオーバーを利用しない場合、クライアントが旧マスターへアクセスが行われ続けレプリカに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スクリプトは現在、実行した結果の変更内容がスレーブへ送られます(Redis 5.0~)。以前はスクリプトのコマンド自体を送っていました。
  • Lua実行中はキーを失効しない挙動となります。同じスクリプトの同じデータセットで同じ効果があることを保証するための動作となります。

フル同期

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

プロセスをforkする際、forkが遅いものを利用していると影響が大きくなります。

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

仕組み

  1. スレーブがSYNCを尋ねる
  2. マスターがBGSAVE。スレーブは待機
  3. BGSAVEが完了し、.rdbファイルをスレーブへ送る
  4. ファイル転送時はマスターはバッファに新しく入ったデータを保存
  5. マスターは.rdbファイルをスレーブへ送るのを完了する
  6. マスターは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 コマンドで確認することができます。

仕組み

  1. クライアントは、Redisのエンドポイントに対して名前引きを行い、その結果から一つIPアドレスを選びその先のノードへアクセスを行います。名前引きの際に選ぶノードのIPアドレスの選び方、使用するDNSリゾルバーに依存します。
  2. アクセス先がレプリカかプライマリの場合で以下のように処理内容が変わります。
    • 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/poingを送る側は常に受け取るハッシュスロットの情報を付与
  • 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

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

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

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で設定を行います。

DEBUGコマンド

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

  • DEBUG POPULATE 1000 : 1000個のサンプルデータを生成
  • DEBUG OBJECT キー名 : キーの内部エンコーディングを確認
  • DEBUG HTSTATS 0 : データベース0のテーブルサイズや要素数、ハッシュの衝突によるチェイン法による対応状況などを確認
  • DEBUG SLEEP 5 : 実行時間に5秒かかるスロークエリーを実行
  • DEBUG RELOAD : SAVEによるRDBファイルのダンプ + FLASHALL + RDBファイルの読み込み
  • DEBUG LOADAOF : AOFの読み込み。AOFファイルがない場合、redis-serverがエラーで終了
  • DEBUG DIGEST : 全DBのハッシュ値
  • DEBUG SEGFAULT : セグフォを意図的に発生
  • DEBUG ASSERT : assertionエラーで終了
  • CRASH-AND-RECOVER 100 : クラッシュ後、100ミリ秒経過で再起動

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> 

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

(*)サービスによっては、条件次第で制限されているものもあります。

一般的な概念について

Copy on Write(CoW)

  • RDB/AOF取得時には、forkされたバックグラウンドプロセスで動作し、その際CoWを行うので、取得中に変更(write)されたメモリ分だけメモリを必要するため、write intensiveな場合、最悪なケースとなりメモリ使用量は最大2倍となります。
  • CoWはfork時には子プロセスの仮想アドレス空間に親プロセスのアドレス空間をマッピングし、親と子でアドレス空間を共有します。子プロセスは、メモリの参照時には親プロセスの物理アドレス空間を参照する。一方で、メモリの書き込み時には書き込まれたページを親子で共有することはできないので、書き込み前に該当メモリページを子プロセスにコピーしてから書き込む。以降、該当ページのメモリ共有はしません。

Raft

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

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

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

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

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

1. Leader Election
2. Log Replication

Leader Election

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

- leader
- candidate
- follower

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

1. Raftに加わるノードはすべてfollowerからスタート
2. leaderからfollowerに対して定期的にheartbeat
3. 反応がなくなるとfollowerがcandidateになり、かつ周りにRequestVoteをばらまき選出が開始
4. RequestVoteを受け取ったサーバは最初に送ってきた送り元にvote
5. 過半数のサーバから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/

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

Raft

Raft from Preferred Networks

Paxos

Paxos from Preferred Networks

Raftについて

コンセンサスアルゴリズムであるRaftの概要
https://kiririmode.hatenablog.jp/entry/20180613/1528875088

Morris’s Algorithm (using by LFU)

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

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

Using Redis as an LRU cache
https://redis.io/topics/lru-cache

確率的カウントアルゴリズム Morris Counting の話
http://yukinoi.hatenablog.com/entry/2015/11/19/220721

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の数>となります。

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

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

ベンチマーク

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で直接データをポイントするようになりました。

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

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;

クラスターの状態

https://github.com/antirez/redis/blob/unstable/src/cluster.h#L143-L181

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;
}

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;
}

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.2 以降から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://news.ycombinator.com/item?id=1171423

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;

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です