Redis がなぜこれほど速いのかを詳しく分析しますか?

Redis が非常に高速で、その QPS が 100,000 (1 秒あたりのリクエスト) に達する可能性があることは誰もが知っています。 なぜ Redis はこんなに速いのですか?、この記事で皆さんと一緒に学びましょう。 [関連する推奨事項: Redis ビデオ チュートリアル ]

メモリベースの実装

メモリの読み取りと書き込みが、他の実装よりも高速であることは誰もが知っています。ディスクの読み書きがたくさんあります。 Redis はメモリ ストレージをベースに実装されたデータベースであり、データがディスクに保存されるデータベースと比較して、ディスク I/O の消費がありません。 MySQL などのディスク データベースでは、クエリの効率を高めるためにインデックスを作成する必要がありますが、Redis データはメモリに保存され、メモリ上で直接動作するため、非常に高速です。

効率的なデータ構造

効率を向上させるために、MySQL インデックスは B ツリー データ構造を選択することがわかっています。実際、合理的なデータ構造により、アプリケーション/プログラムを高速化できます。まず、Redis のデータ構造と内部エンコード図を見てみましょう。

#SDS 単純な動的文字列

#

struct sdshdr { //SDS简单动态字符串
    int len;    //记录buf中已使用的空间
    int free;   // buf中空闲空间长度
    char buf[]; //存储的实际内容
}

文字列の長さ処理

C言語では、文字列カタツムリを拾う小さな男の子の長さを取得するには、それを最初からたどる必要があり、複雑さはO(n)です。 Redis には、現在の文字列の長さを記録する len フィールドがすでにあり、これを直接取得でき、時間計算量は O(1) です。

メモリの再割り当ての回数を減らす

C 言語では、文字列を変更するにはメモリの再割り当てが必要です。変更の頻度が高くなるほど、メモリの割り当ても頻繁になり、メモリの割り当ては 消費パフォーマンス。 Redis では、SDS は、スペースの事前割り当てと遅延スペースの解放という 2 つの最適化戦略を提供します。

スペースの事前割り当て

SDS の単純な動的文字列の変更とスペースの拡張では、必要なメモリ スペースの割り当てに加えて、追加の未使用スペースが割り当てられます。割り当てルールは紫色です:

• SDS が変更された後、len の長さが 1M 未満になり、len と同じ長さの追加の未使用スペースが割り当てられます。たとえば、len=100 の場合、再割り当て後の buf の実際の長さは、100 (使用済みスペース) 100 (余分なスペース) 1 (ヌル文字) = 201 になります。
• SDS が変更された後、len の長さが 1M より大きい場合、プログラムは 1M の未使用スペースを割り当てます。

遅延領域解放

SDS が短縮されると、余分なメモリ領域を再利用する代わりに、free を使用して余分な領域が記録されます。後続の変更操作がある場合は、空き領域が直接使用されてメモリ割り当てが削減されます。

Hash

Redis は K-V インメモリ データベースであり、グローバル ハッシュを使用してすべてのキーと値のペアを保存します。このハッシュ テーブルは複数のハッシュ バケットで構成されており、ハッシュ バケット内のエントリ要素には *key と *value ポインタが格納されており、そのうち *key は実際のキー、*value は実際の値を指します。

ハッシュ テーブルの検索速度は非常に速く、Java の HashMap に似ており、O(1)# を実行できます。 ## キーと値のペアを素早く見つけるのにかかる時間の複雑さ。まず、キーを通じてハッシュ値を計算し、対応するハッシュ バケットの場所を見つけて、次にエントリを見つけて、エントリ内の対応するデータを見つけます。

友人の中には、こんな疑問を持つ人もいるかもしれません。大量のデータをハッシュ テーブルに書き込むと、

ハッシュ競合 問題が発生し、効率が低下するのではないかということです。

ハッシュの競合: 同じハッシュ値が異なるキーを通じて計算され、結果として同じハッシュ バケットが生成されます。

ハッシュの競合を解決するために、Redis は

チェーン ハッシュ を使用します。連鎖ハッシュとは、同じハッシュ バケット内の複数の要素がリンク リストに格納され、ポインタを使用して順番に接続されることを意味します。

#まだ疑問を持っている友人もいるかもしれません。ハッシュ競合チェーン上の要素は、ポインターを介して 1 つずつ検索して操作することしかできません。大量のデータがハッシュ テーブルに挿入されると、競合が多くなり、競合リンク リストが長くなり、クエリの効率が低下します。

効率を維持するために、Redis はハッシュ テーブルに対して

再ハッシュ操作 を実行します。これは、ハッシュ バケットを追加して競合を減らすことを意味します。再ハッシュをより効率的にするために、Redis はデフォルトで 2 つのグローバル ハッシュ テーブルも使用します。1 つはメイン ハッシュ テーブルと呼ばれる現在使用用で、もう 1 つは拡張用でありバックアップ ハッシュ テーブルと呼ばれます。

跳跃表

跳跃表是Redis特有的数据结构，它其实就是在链表的基础上，增加多级索引，以提高查找效率。跳跃表的简单原理图如下:

• 每一层都有一条有序的链表，最底层的链表包含了所有的元素。
• 跳跃表支持平均 O（logN）,最坏 O（N）复杂度的节点查找，还可以通过顺序性操作批量处理节点。

压缩列表ziplist

压缩列表ziplist是列表键和字典键的的底层实现之一。它是由一系列特殊编码的内存块构成的列表， 一个ziplist可以包含多个entry， 每个entry可以保存一个长度受限的字符数组或者整数，如下：

• zlbytes ：记录整个压缩列表占用的内存字节数
• zltail: 尾节点至起始节点的偏移量
• zllen : 记录整个压缩列表包含的节点数量
• entryX: 压缩列表包含的各个节点
• zlend : 特殊值0xFF(十进制255)，用于标记压缩列表末端

由于内存是连续分配的，所以遍历速度很快。。

合理的数据编码

Redis支持多种数据基本类型，每种基本类型对应不同的数据结构，每种数据结构对应不一样的编码。为了提高性能，Redis设计者总结出，数据结构最适合的编码搭配。

Redis是使用对象（redisObject）来表示数据库中的键值，当我们在 Redis 中创建一个键值对时，至少创建两个对象，一个对象是用做键值对的键对象，另一个是键值对的值对象。

//关注公众号：捡田螺的小男孩
typedef struct redisObject{
    //类型
   unsigned type:4;
   //编码
   unsigned encoding:4;
   //指向底层数据结构的指针
   void *ptr;
    //...
 }robj;

redisObject中，type 对应的是对象类型，包含String对象、List对象、Hash对象、Set对象、zset对象。encoding 对应的是编码。

• String：如果存储数字的话，是用int类型的编码;如果存储非数字，小于等于39字节的字符串，是embstr；大于39个字节，则是raw编码。
• List：如果列表的元素个数小于512个，列表每个元素的值都小于64字节（默认），使用ziplist编码，否则使用linkedlist编码
• Hash：哈希类型元素个数小于512个，所有值小于64字节的话，使用ziplist编码,否则使用hashtable编码。
• Set：如果集合中的元素都是整数且元素个数小于512个，使用intset编码，否则使用hashtable编码。
• Zset：当有序集合的元素个数小于128个，每个元素的值小于64字节时，使用ziplist编码，否则使用skiplist（跳跃表）编码

合理的线程模型

单线程模型：避免了上下文切换

Redis是单线程的，其实是指Redis的网络IO和键值对读写是由一个线程来完成的。但Redis的其他功能，比如持久化、异步删除、集群数据同步等等，实际是由额外的线程执行的。

Redis的单线程模型，避免了CPU不必要的上下文切换和竞争锁的消耗。也正因为是单线程，如果某个命令执行过长（如hgetall命令），会造成阻塞。Redis是面向快速执行场景的内存数据库，所以要慎用如lrange和smembers、hgetall等命令。

什么是上下文切换？举个粟子：

• 比如你在看一本英文小说，你看到某一页，发现有个单词不会读，你加了个书签，然后去查字典。查完字典后，你回来从书签那里继续开始读，这个流程就很舒畅。
• 如果你一个人读这本书，肯定没啥问题。但是如果你去查字典的时候，别的小伙伴翻了一下你的书，然后溜了。你再回来看的时候，发现书不是你看的那一页了，你得花时间找到你的那一页。
• 一本书，你一个人怎么看怎么打标签都没事，但是人多了翻来翻去，这本书各种标记就很乱了。可能这个解释很粗糙，但是道理应该是一样的。

I/O 多路复用

什么是I/O多路复用？

• I/O: ネットワーク I/O
• マルチチャネル: 複数のネットワーク接続
• 多重化: 同じスレッドを多重化します。
• IO 多重化は実際には同期 IO モデルであり、複数のファイル ハンドルを監視できるスレッドを実装します。ファイル ハンドルの準備が完了すると、対応する読み取りおよび書き込み操作を実行するようにアプリケーションに通知できます。ファイル ハンドルがない場合は、準備ができている場合、アプリケーションはブロックされ、CPU が引き渡されます。

複数の I/O 多重化テクノロジにより、単一のスレッドで複数の接続リクエストを効率的に処理できます。Redis は、I/O として epoll を使用します。多重化テクノロジの実装。さらに、Redis 独自のイベント処理モデルは、ネットワーク I/O にあまり時間を費やすことなく、epoll での接続、読み取り、書き込み、および終了をイベントに変換します。

仮想メモリ機構

Redis は VM 機構を自ら直接構築するため、通常のシステムのようにシステム関数を呼び出したり、移動やリクエストに一定の時間を浪費したりすることはありません。

Redis の仮想メモリ メカニズムとは何ですか?

仮想メモリ メカニズムは、アクセス頻度の低いデータ (コールド データ) をメモリからディスクに一時的に交換し、アクセスする必要がある他のデータ (ホット データ) のために貴重なメモリ領域を解放します。 。 データ）。 VM 機能は、ホット データとコールド データの分離を実現できるため、ホット データはメモリ内に残り、コールド データはディスクに保存されます。これにより、メモリ不足によるアクセス速度の低下の問題を回避できます。

プログラミング関連の知識について詳しくは、プログラミング ビデオをご覧ください。 ！

以上がRedis がなぜこれほど速いのかを詳しく分析しますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。