シングルスレッドのredisがなぜ速いのかの紹介

RedisシングルパッセンジャーQPS

. /redis-benchmark -t set,lpush -n 100000 -q
SET: 82101.80 requests per second
LPUSH: 82440.23 requests per second

自分のパソコンで10万回テストしてみると、SETとLPUSHは1秒間に約8w強で、シングルマシンで書かれた公式の10w qpsに近いことがわかる。

なぜこんなに速いのか？

インメモリデータベース

redisは完全にメモリベースであり、リクエストの大部分は純粋にメモリ内の操作であるため、非常に高速です。

シンプルなデータ構造

redisは現在、5つのデータ型（string, list, hash, set, zset）をサポートしており、比較的単純なデータ構造で、比較的高速に操作することができます。

sdsのデータ構造

文字列については、redisはSDSアプローチでデータを整理しています。

このデータの核となる考え方は、時間のための空間である

スペースの事前割り当て：スペース拡張時に、必要なスペースだけでなく、追加のスペースも割り当てる。

• もし、割り当て後のsdsの長さが1M未満であれば、同じサイズの余分な領域も割り当てる。例えば、あるキーがlen=13に変更されたとすると、free=13も割り当て、最終的にbuf=13+13+1=27となる。
• 割り当てられたlenが1M以上の場合、1Mの追加固定割り当て、修正len=30M、割り当てfree=1M、最終的にbuf=30M+1M+1byteとする。

不活性空間の解放

• len=13、free=13の文字列があったとして、このとき文字が短くなるとlen=10となり、余分な3バイトの領域は回収されずに先にfreeに入れられ、このときfree=16となります。

この割り当てでは、メモリ要求の数を減らすことで、特定のシナリオをある程度早く達成することができます

テーブルのジャンプ

Redisの順序付きコレクションで、レイヤーを使って他のノードへのアクセスを高速化するジャンプテーブルのデータ構造

各ノードはランダムな階層の高さを持ち、例えばノードo1は階層L4,スパン2を通してo3に直接ジャンプできます。redisの順序付きコレクションはこの方法でノード間のアクセスを高速化します。

シングルスレッド

redisはシングルスレッドモデルを使用しています。シングルスレッドの利点は、複数のスレッドがデータを奪い合う問題、ロック、コンテクストスイッチングを回避できることです。
公式の説明によると、redisのボトルネックはCPUではなく、メモリやネットワーク帯域にあり、その上で総合的に考えるとシングルスレッドになるとのことです。シングルスレッドとは、ネットワークリクエストの処理に1スレッドしか使わないという意味です。redis自身は永続化するときにまだ追加のスレッドを使用しています。

redis 4.0でのマルチスレッド化

redis4.0はマルチスレッドにも対応していますが、UNLINK, FLUSHALL, ASYNC, FLUSHDBといった一部のコマンドのみです。これらを導入した目的は、場合によっては少しでも効率を上げるためです。

IO多重化

redisはノンブロッキングIOマルチプレキシングを採用しています。redis自体はイベントドライバで、redisはソケットをファイルイベントに抽象化しています。ここで説明するIO多重化とは、ファイルイベントハンドラが関連するソケット（accept、read、write、close）をシングルスレッドでリッスンすることです。

IOマルチプレクサはシングルスレッドなので、複数のソケットが到着すると、それらをキューに入れる必要があり、常にキュー内で順次処理されることになります。

C10K問題

IO多重化がない場合、現在10,000のクライアント接続（fd1-10000）があるが、データを送ったのは1クライアントだけで、しかもコンピュータはどのfdにデータがあるかわからず、10,000回しかトラバースできず、そのたびにカーネルに引っかかり、オーバーヘッドも多く、実際には9999回無駄にしていると仮定する。

IO多重化

IO多重化とは、複数のネットワークIO、すなわち複数のTCPコネクションを1つのプロセスまたはスレッドで再利用することです。古典的なモデルは、select、poll、epollです。

• select: select(fds)、これは fds を一度カーネルに渡し、カーネルがどの fds が読み書き可能かを指示します (ユーザが fds を走査する代わりに、カーネルが自分自身で走査し、複数のシステムコールをひとつにします) fds は最大 1024 で、これにより select モデルの最大並行性は 1024 と決定されます。
• poll: select と似ているが、同時接続数が1024以上であることを除けば、それ以上である。
• エポール select と poll の欠点は、カーネル探索の時間複雑性が O(n) であり、ユーザ状態が探索する必要がないため、カーネル内でスタックする回数を減らすことができますが、それでもカーネルは探索する必要がある点です。epollはカーネルもトラバースする必要がなく、ユーザがfdsをカーネルに渡すと、ハードウェア割り込みに依存し、例えばNICにデータが到着すると割り込んでCPUに伝え、CPUはどのfdにデータが到着しているかを知ることができるという利点があります。

redisは、システムがサポートしていない場合を除き、デフォルトでepollを使用します。

概要

• redisはインメモリデータベースです
• redis の特殊なデータ構造
• シングルスレッドによるロック競合の回避
• ioマルチプレクシング

上記4点がシングルスレッドredisが高速である主な理由です。

シングルスレッドredisが速い理由についてはこちらの記事が全てです。シングルスレッドredisについてもっと知りたい方は、過去の記事を検索していただくか、引き続き以下の関連記事をご覧になってください。