Redis 高効率化の理由とデータ構造の解析

1.redisとは何か、何に使うのか？

Redisは、Remote Dictionary Serverとして知られており、オープンソース、ANSI C、ネットワーク対応、インメモリ永続化、Key-Valueデータベース、多言語APIを備えています。

MySQLデータベースとは異なり、Redisのデータはメモリ上に存在します。1秒間に10万回以上の読み書きが可能であり、非常に高速です。その結果、Redisはキャッシュに広く使用され、さらに、Redisは分散ロックによく使用されます。さらに、Redisはトランザクション、永続化、LUAスクリプト、LRU駆動イベント、および複数のクラスタリングスキームをサポートしています。

redisが何であるかが分かったところで、redisがなぜ速いのかについて説明しましょう。

2. なぜredisは速いのか？

ひとつひとつ図解していきましょう

インメモリストレージベースの実装

コンピュータサイエンスを学ぶ学生は、メモリの読み書きはディスクよりずっと速いことを知っています。Redisはインメモリベースのデータベースで、データがディスク上に存在するmysqlなどのデータベースと比較して、ディスクI/Oの消費をなくすことができるのです。

効率的なデータ構造

mysqlのインデックスが効率のためにB+のツリーデータ構造を選択したことは周知の通りですが、アプリケーションのシナリオに合った合理的なデータ構造は、アプリケーションやプログラムをより速くすることができます。Redisのデータ構造 - 内部コーディング図を見てみましょう。

String : ダイナミックストリングスSDS
List : 両端リンクリスト + 圧縮リンクジップリスト
Hash 圧縮鎖 Ziplist + 辞書 ハッシュテーブル Hashtable
Set : ハッシュテーブル(+inset)
Zset 圧縮鎖表 ziplist + ジャンプ表 skiplist

これらの内部コードについて説明しましょう。

1. SDS単純動的文字列

C言語のchar[ ]と比較してみましょう。

文字列の長さの処理。Redisは文字列の長さをO(1)の時間複雑度で取得しますが、Cではゼロからトラバースする必要があり、O(N)の複雑度を伴います。

スペースの事前割り当て。文字列の変更頻度が高くなると、メモリの割り当て頻度が高くなり、非常にパフォーマンスが低下する。一方、SDSの変更と領域拡張では、未使用の領域を追加で割り当てるため、パフォーマンスの低下が抑えられる。

不活性空間の解放。SDS短縮時に余ったメモリ領域を再利用するのではなく、freeに記録し、その後の変更ではfreeに記録された領域を直接利用することで、割り当てを削減します。

バイナリセーフ。Redisはバイナリデータを格納することができます。C 言語では文字列は '/0' にぶつかると終わりますが、SDS では len 属性が文字列の終わりを表します。

2. ディクショナリー

RedisはK-V型のインメモリデータベースであり、すべてのキーはディクショナリに格納される。辞書とはHashMapのような、キーから直接値を取得できるようなハッシュテーブルで、時間計算量O(1)で値を取得できるようなものである。

3. ジャンプテーブル

ジャンプテーブルはRedis特有のデータ構造で、チェーンテーブルをベースに、ルックアップの効率を高めるために複数レベルのインデックスを備えています。
ジャンプテーブルは平均O(logN)、最悪O(N)の複雑さでノードの検索をサポートし、順次操作することが可能です。

合理的なデータエンコーディング

Redisは複数のデータ型をサポートしており、各基本型は複数のデータ構造を持つことができます。いつ、どのデータ構造を使うか、どのエンコーディングを使うかは、redis設計者による最適化の結果です。

文字列。数値を格納する場合はint型、数値以外で39バイト未満の文字列を格納する場合はembstr、39バイト以上の場合はrawでエンコードされる。
リスト リストの要素数が512未満で、リストの各要素の値が64バイト未満（デフォルト）の場合、ziplistエンコーディングを使用し、それ以外の場合はlinkedlistエンコーディングを使用します。
ハッシュ：ハッシュ型の要素数が512未満で、すべての値が64バイト未満の場合、ziplistエンコーディングを使用し、それ以外の場合はhashtableエンコーディングを使用します。
セット。セットの要素がすべて整数で、要素数が512未満の場合はintsetエンコーディングを、それ以外の場合はhashtableエンコーディングを使用します。
Zset。順序付きセットの要素数が128未満で、各要素の値が64バイト未満の場合、Ziplistエンコーディングを使用し、それ以外の場合はSkiplist（ジャンプテーブル）エンコーディングを使用します。

合理的なスレッドモデル

1. I/O多重化

I/Oを多重化することで、1つのスレッドで複数の接続要求を効率的に処理することができる。RedisはI/O多重化技術の実装としてepollを使用している。また、Redis独自のイベント処理モデルは、epollでの接続、読み書き、クローズをイベントに変換し、ネットワークI/Oにあまり無駄な時間を割かないようにしています。

2. I/O マルチプレキシングとは？

I/O：ネットワークI/O
Multiplex : 複数のネットワーク接続
Multiplexing : 同じスレッドを多重化すること。
IO多重化は、実際には、スレッドが複数のファイルハンドルを監視することを可能にする同期IOモデルです。ファイルハンドルの準備ができると、それに応じて読み取りと書き込みを行うためにアプリケーションを通知することができます。

3. シングルスレッド・モデル

Redisはシングルスレッド・モデルであり、シングルスレッド化することで不必要なCPUのコンテキスト・スイッチングや競合ロックの消費を回避することができます。Redisは高速な実行シナリオのためのデータベースです。Redisは高速な実行シナリオのためのデータベースなので、smembersやlrange, hgetallなどのコマンドは注意して使ってください。

Redis 6.0では高速化のためにマルチスレッドを導入しましたが、メモリを操作するコマンドの実行にはまだシングルスレッドが使用されています。

仮想記憶機構

redisは独自のVMメカニズムを直接構築し、一般的なシステムがそれを処理するためにシステム関数を呼び出すように、移動して要求するいくつかの時間を無駄にしません。

Redisの仮想記憶機構とは何ですか？

仮想記憶機構とは、アクセス頻度の低いデータ（コールドデータ）を一時的にメモリからディスクにスワップし、貴重なメモリ領域を他のアクセスする必要のあるデータ（ホットデータ）のために解放するものです。VM機能により、ホットデータとコールドデータを分離し、ホットデータはメモリに、コールドデータはディスクに保存することができる。これにより、メモリ不足によるアクセス速度低下の問題を回避することができます。

<リンク