Redis / Memcached Source Code Reading – Overview –

Redis 3.2.12 と Memcached 1.4.34 のソースコードのファイルの内容の概要をここではまとめました。

Redis

Redis 3.2.12 のソースコードのファイル https://github.com/antirez/redis/tree/3.2

• 各データ構造の実装

  • sds.h, sds.c, sdsalloc.h : RedisのSDS(Simple Dynaic Strings)の実装。Redisでの文字列に使用。 https://github.com/antirez/sds
  • zmalloc.h, zmalloc.c : zmalloc関数は、mallocされた領域のサイズをできるだけ正確に保持してRedis側からそれが見れるようにしておくためにwrapした関数
  • adlist.h, adlist.c : Redisの双方向リストの実装。ziplist等で利用
  • dict.h, dict.c: Redisのディクショナリ実装。SetやHashに利用されている。Redisのディクショナリは、hash table。

• 内部エンコーディングの実装

  • intset.h, intset.c : intsetデータ構造。Setで全要素が整数かつ要素数が少ないときの内部エンコーディング
  • ziplist.h, ziplist.c : ziplist のデータ構造。Hash, Sorted Setのサイズやエントリ数が小さいときの内部エンコーディング。Listでも使われていた。MurmurHash2のアルゴリズムで増分のリサイジングが行われる。ハッシュ値の衝突時はチェイン法を利用。[key1, value1, key2, value2, …]のように一列に並べる。
  • quicklist.h, quicklist.c : quicklist のデータ構造。Listの内部エンコーディング
  • zipmap.h, zipmap.c : Hashが2.6以前でziplistの前に利用していた内部エンコーディング。RDBファイルからの読み込みで使われる様子

• データ型実装

  • object.c : Redisオブジェクト（型）システム実装
  • t_string.c : 文字列キーの実装
  • t_list.c : リストキーの実装
  • t_hash.c : ハッシュキーの実装
  • t_set.c : コレクションキーの実装
  • t_zset.c : Sorted Setキーの実装
  • hyperloglog.c : HyperLogLogキーの実装
  • geo.h, geo.c : GEOコマンド(GEOADD, GEORADIOUS, GEORADIOUSBYMEMBER)の実装

• データベース実装関連

  • db.c : 全コマンド共通処理(キーの削除処理等)。Redisデータベースの実装。Latzy Expirationアルゴリズム
  • notify.c : Redisのデータベース通知関数の実装
  • rdb.h, rdb.c : RedisのRDB永続化実装
  • aof.c : RedisのAOF永続化実装

• 各種Redisの特徴実装

  • pubsub.c : パブリッシュおよびサブスクライブ機能の実装
  • multi.c : トランザクション関数の実装
  • sort.c : SORTコマンドの実装
  • bitops.c : GETBITやSETBITなどのバイナリビット操作コマンドの実装

• クライアントとサーバーの関連コード

  • ae.h, ae.c, ae_*.c(ae_epoll.c, ae_evport.c, ae_kqueue.c, ae_select.c) : Redisのイベントハンドラの実装（Reactorモードに基づく）
  • networking.c : Redisのネットワーク接続ライブラリは、コマンド応答の送信とコマンド要求の受け入れを担当し、クライアントの作成/破棄、通信プロトコル分析も担当
  • anet.h, anet.c : TCPソケット通信周りの実装。anetTcpServer関数からlistenするディスクリプターを返す処理等

• レイテンシーのトラブルシューティング + Lua 周りの実装

  • scripting.c : Luaスクリプト機能の実装
  • slowlog.c : スロークエリー機能の実装
  • monitor.c : モニタ機能の実装
  • latency.h, latency.c : LATENCY MONITORの実装

• I/O処理

  • bio.h, bio.c : スレッド間で競合しないようにI/Oのブロッキング処理
  • blocked.c : BLPOPやWAITコマンド等のブロッキングに関する処理
  • rio.h, rio.c : rioはストリーミング志向のIOの抽象化で、特定のI/Oデバイスを消費/生成するための読み書きインタフェースを提供。 rdb.cではRDBメモリの読み書きとファイルの読み書きに使用する抽象パッケージを提供
  • syncio.c : ソケットやファイルのI/O操作の同期処理。スレーブが行うSYNCコマンドを除いたほとんどの処理はノンブロッキングI/Oだが、MIGRATEコマンドのような2つのインスタンス間の整合性が必要な処理ためのブロッキング処理

• 複数ノードに関する処理の実装

  • replication.c : レプリケーション機能の実装
  • sentinel.c : Redis Sentinelの実装
  • cluster.c : Redisクラスタの実装

• 各種コマンド実装

  • server.h, server.c : Redis サーバの起動から起動時における処理。各種コマンドの実装等。redis-server 処理のメイン部分
  • config.h, config.c : 設定ファイルのパースと、CONFIG GET/SET コマンド実装

• 数学的処理

  • crc16.c : クラスターでハッシュスロット決定の HASH_SLOT = CRC16(key) motd 16384 で使用する。cluster.c で crc16(key,keylen) & 0x3FFF のように使用
  • crc64.h, crc64.c : RDB ファイルのチェックサム計算に使用。(|… RDB payload | 2 bytes RDB version | 8 bytes CRC64 |)。RDB バージョン5からの使用し、rdbchecksum 有効時(デフォルト有効)に付与される。
  • sha1.h, sha1.c : SHA1の実装
  • rand.h, rand.c : デフォルトのmath.random()のLua実装は、異なるシステム間で期待する挙動にはならないので、pysam の　drand48() 由来の独自の擬似ランダム関数(PRNG)を実装
  • lzf.h, lzf_c.c, lzf_d.c, lzfP.h : LibLZF というかなり早くて無料の圧縮/解凍手法のアルゴリズム。quicklistや、rdbcompression が有効時(デフォルト有効)にRDBファイルの圧縮に使用される様子。 http://oldhome.schmorp.de/marc/liblzf.html
  • pqsort.h, pqsort.c : NetBSD の libc qsort 実装を Redisのレンジによる部分ソートに対応するために改良した実装。Quicksort
  • endianconv.h, endianconv.c : エンディアンの変換。マクロ関数から呼ばれる。Redisは基本リトルエンディアンとして解釈して多くのプロダクション環境でもリトルエンディアンだが、いくつかのものは後方互換性のためビッグエンディアンを使用。ziplists, intsets, zipmapsなどは、メモリ上であっても、RDBファイルへのシリアライズを1回のwrite(2)で行うのでendian-neutralである必要がある。

• その他

  • util.h, util.c : C言語の型変換処理や文字列に関する処理、パス周りの処理等、一般的に利用することができる関数
  • help.h : ヘルプコマンドで利用する変数を定義。表示内容の文字列が格納されたディクショナリー等を定義
  • testhelp.h : 最低限のテストフレームワーク
  • debug.c : デバッグ用に各種レジスターの中身の情報をダンプする関数等を定義
  • debugmacro.h : 一時ファイルにログを書き込む関数定義
  • version.h : Redis のバージョンを文字列で指定するマクロ変数を定義
  • redisassert.h : ログファイルに詳細と共にスタックトレースを出力するassert()を定義
  • mkreleasehdr.sh : リリースする度にrelease.hを生成し、release.cをビルド対象にするためにtouchを実行
  • release.c : release.hで定義された定数を関数から呼び出す関数を定義
  • asciilogo.h : Redis Serverの起動時に表示されるRedisのASCII文字によるアイコン。
  • fmacros.h : OS周りの定数定義
  • sparkline.h, sparkline.c : ASPARKというASCII スパークラインを表示する実装をターミナル出力からSDS文字列で返すように改良したもの https://github.com/antirez/aspark
  • memtest.c : メモリーテスト。memtest86やmemtesterで合わせて確認することも提案している。
  • solarisfixes.h : Solaris特有部分の修正
  • setproctitle.c : Linux/Darwinのsetproctitleでプロセス名の設定に関する実装
  • valgrind.sup : Valgrindというメモリーデバッグやメモリーリークの検出のツールでのテスト内容を記述

• 各種ツール実装

  • redis-benchmark.c
  • redis-check-aof.c
  • redis-check-rdb.c
  • redis-cli.c
  • redis-trib.rb

Memcached

Memcached 1.4.34 のソースコードのファイル https://github.com/memcached/memcached/tree/1.4.34

• メイン処理

  • memcached.h, memcached.c : 処理のメイン部分。ネットワークサーバとしての接続処理。conn 構造体で接続情報の含まれる。settings構造体にmemcachedの設定オプションの要素。conn_statesで遷移状態の情報
  • slabs.h, slabs.c : キャッシュアイテムに用いるためのメモリ管理。キャッシュアイテムの大きさを十数段階に分け、階級ごとにメモリプールを作る。それぞれのメモリプールには必要に応じて1MBのメモリブロック単位(slab)でメモリを追加する。メモリプールは一定長のアイテムに分割され、要求があると大きさに応じた階級のメモリプールから空いているアイテムを返す。
  • assoc.h, assoc.c : キーからオブジェクトへマップするハッシュテーブル
  • items.h, items.c : キャッシュアイテムのモジュールやキー操作に関するコマンドの実装
  • stats.h, stats.c : 統計情報。getリクエストの数等はmemcached.cでカウントされるが、stats detailモード有効時はこのコードが利用される。

• ハッシュ関数に関する処理

  • hash.h, hash.c : Hashの初期化。jenkinsとmurmur3のアルゴリズムに対応
  • jenkins_hash.h, jenkins_hash.c : jenkinsの実装 http://burtleburtle.net/bob/hash/doobs.html
  • murmur3_hash.h, murmur3_hash.c : murmur3の実装

• キャッシュやスレッド周りの処理

  • cache.h, cache.c : オブジェクトを割り当てるためのキャッシュ作成等の実装
  • crawler.h, crawler.c : LRUのCrawler実装
  • thread.c : スレッド周りの処理
  • bipbuffer.h, bipbuffer.c : Bip Bufferの実装 https://www.codeproject.com/Articles/3479/The-Bip-Buffer-The-Circular-Buffer-with-a-Twist

• Memcachedの機能(バイナリモード、SASL認証)

  • protocol_binary.h : バイナリモードにおいて使用される数字に関する内容の定義
  • sasl_defs.h, sasl_defs.c : SASL認証の実装

• その他

  • sizes.c : ./sizes 実行で統計情報やアイテムのサイズ等を表示
  • timedrun.c : ./timedrun 実行で処理を指定した時間だけ中断
  • logger.h, logger.c : ログの処理周りの実装
  • daemon.c : NetBSDのforkしてデーモン化する処理の実装
  • globals.c : グローバル変数を6つ定義。設定や統計、スラブのrebalanceと現在時刻の変数
  • util.h, util.c : C言語の型変換やエラー出力等の一般的な処理の実装
  • solaris_priv.c : Solarisに対してfork()やexec()が実行できないように権限をなくす
  • testapp.c : テストコード。assert関数で意図した変数の値になっているか確認
  • trace.h : 処理の追跡のための関数のマクロ定義。DTrace有効時は、memcached_dtrace.d の読み込み
  • memcached_dtrace.d : DTrace による処理の追跡
  • version.sh. version.pl : バージョンに関するファイルの生成処理
  • memcached.spec.in : セットアップのためのシェルスクリプト実行