Redis の基礎となるデータ構造の詳細な紹介

1. 概要

Redis を使用したことがあるすべての学生は、Redis がキーと値のペアに基づいていることをよく知っていると思います。 Memcached に似た分散ストレージ システムですが、Memcached よりも優れた高性能のキー/値データベースです。

については、「Redis の設計と実装」で説明されています。

Redis データベース 内のすべてのキーと値のペア (キーと値) は構成されていますオブジェクトの数:

データベース キーは常に文字列オブジェクトです;

データベース値は文字列オブジェクト、リスト オブジェクト (リスト)、5 種類のオブジェクトのいずれかになります: ハッシュ、 set および set オブジェクトのソート。

Redis が Memcached よりも優れていると言えるのはなぜですか? Redis の出現により、memcached のキーと値のストレージが強化されたためです。場合によっては、Redis がリレーショナル データベースに対して非常に優れた補助的な役割を果たすことができ、これらのデータはすべて、プッシュ/ポップ、追加/削除、交差、結合、差分などの豊富な操作をサポートしており、これらの操作はすべてアトミックです。

今日私たちが議論しているのは、Redis の値のデータ型ではなく、その特定の実装、つまり基礎となるデータ型です。

Redis の基礎となるデータ構造には次のデータ型があります:

1、単純な動的文字列

2、リンクされたリスト

3、 Dictionary

4、ジャンプ テーブル

5、整数セット

6、圧縮リスト

7、オブジェクト

2 、単純な動的文字列 (単純な動的文字列) SDS

2.1 概要

Redis は、ANSI C 言語で書かれたオープン ソースのキーと値のデータベースです。 C 言語では従来の文字列で表現されますが、そうではありません。Redis は C 言語の従来の文字列表現を直接使用せず、単純な動的文字列 (単純な動的文字列 SDS) と呼ばれる独自の抽象型を構築します。 Redis のデフォルトの文字列表現として SDS を使用します:

redis>SET msg "hello world"
OK

key= msg、value = hello world で新しいキーと値のペアを設定します。その基礎となるデータ構造は次のようになります:

キー(key) は文字列オブジェクトであり、オブジェクトの基礎となる実装は文字列 "msg" を格納する SDS です;

値 (value) も文字列オブジェクトであり、オブジェクトの基礎となる実装です「hello world」という文字列を格納する SDS です。

上記の例から、普段 Redis を使用するときに作成する文字列がどのようなデータ型であるかが直感的にわかります。 SDS は、文字列の保存に使用されるだけでなく、バ​​ッファ AOF モジュールの AOF バッファとしても使用されます。

2.2 SDS の定義

Redis で定義された動的文字列の構造:

/*  
 * 保存字符串对象的结构  
 */  
struct sdshdr {  
      
    // buf 中已占用空间的长度  
    int len;  
  
    // buf 中剩余可用空间的长度  
    int free;  
  
    // 数据空间  
    char buf[];  
};

1, len buf で使用されているスペースの長さを記録するために使用される変数 (ここでは、Redis の長さが 5 であることが指摘されています)

2. 自由変数、buf の空きスペースを記録するために使用されます (スペースは初めて割り当てられます。通常、空きスペースはありません。文字列を変更すると、残りのスペースが生じます)

3. 文字列を記録するために使用される buf 文字配列 (Redis の記録)

2.3 SDS と C 文字列の違い

従来の C 文字列は、長さ N の文字列を表すために長さ N 1 の文字列配列を使用します。このように、次のことが必要です。文字列の長さの取得、文字列の展開、その他の操作が行われるため、時間効率が悪くなります。 C 言語はこの単純な文字列表現方法を使用しますが、文字列のセキュリティ、効率、機能に関する Redis の要件を満たすことができません

2.3.1 文字列の長さの取得 (SDS O(1)/C String O(n))

従来の C 文字列は、長さ N の文字列を表すために長さ N 1 の文字列配列を使用するため、C 文字列の長さを取得するには、文字列全体を走査する必要があります。

C の文字列とは異なり、SDS のデータ構造には文字列の長さを格納するための変数があり、len 属性の値を取得することで文字列の長さを直接知ることができます。

2.3.2 バッファ オーバーフローの防止

C 文字列は文字列の長さを記録しません。取得が非常に複雑であることに加えて、バッファリングが発生しやすくなり、エリアオーバーフローが発生します。

プログラムのメモリ内に隣接する 2 つの文字列 s1 と s2 があり、そのうち s1 は文字列「redis」を保存し、s2 は文字列「MongoDb」を保存するとします。

##ここで s1 の内容を Redis クラスターに変更したが、s1 に十分なスペースを再度割り当てるのを忘れた場合、次の問題が発生します。

s2 の元のコンテンツが S1 のコンテンツによって占有されており、s2 が「Mongodb」ではなくクラスターになっていることがわかります。

Redis 中SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性：

当我们需要对一个SDS 进行修改的时候，redis 会在执行拼接操作之前，预先检查给定SDS 空间是否足够，如果不够，会先拓展SDS 的空间，然后再执行拼接操作

2.3.3 减少修改字符串时带来的内存重分配次数　　　

C语言字符串在进行字符串的扩充和收缩的时候，都会面临着内存空间的重新分配问题。

1. 字符串拼接会产生字符串的内存空间的扩充，在拼接的过程中，原来的字符串的大小很可能小于拼接后的字符串的大小，那么这样的话，就会导致一旦忘记申请分配空间，就会导致内存的溢出。

2. 字符串在进行收缩的时候，内存空间会相应的收缩，而如果在进行字符串的切割的时候，没有对内存的空间进行一个重新分配，那么这部分多出来的空间就成为了内存泄露。

举个例子：我们需要对下面的SDS进行拓展，则需要进行空间的拓展，这时候redis 会将SDS的长度修改为13字节，并且将未使用空间同样修改为1字节

因为在上一次修改字符串的时候已经拓展了空间，再次进行修改字符串的时候会发现空间足够使用，因此无须进行空间拓展

通过这种预分配策略，SDS将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次

2.3.4 惰性空间释放

我们在观察SDS 的结构的时候可以看到里面的free 属性，是用于记录空余空间的。我们除了在拓展字符串的时候会使用到free 来进行记录空余空间以外，在对字符串进行收缩的时候，我们也可以使用free 属性来进行记录剩余空间，这样做的好处就是避免下次对字符串进行再次修改的时候，需要对字符串的空间进行拓展。

然而，我们并不是说不能释放SDS 中空余的空间，SDS 提供了相应的API，让我们可以在有需要的时候，自行释放SDS 的空余空间。

通过惰性空间释放，SDS 避免了缩短字符串时所需的内存重分配操作，并未将来可能有的增长操作提供了优化

2.3.5 二进制安全

C 字符串中的字符必须符合某种编码，并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串结尾，这些限制使得C字符串只能保存文本数据，而不能保存想图片，音频，视频，压缩文件这样的二进制数据。

但是在Redis中，不是靠空字符来判断字符串的结束的，而是通过len这个属性。那么，即便是中间出现了空字符对于SDS来说，读取该字符仍然是可以的。

例如：

2.3.6 兼容部分C字符串函数

虽然SDS 的API 都是二进制安全的，但他们一样遵循C字符串以空字符串结尾的惯例。

2.3.7 总结

3、链表

3.1 概述

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。

链表在Redis 中的应用非常广泛，比如列表键的底层实现之一就是链表。当一个列表键包含了数量较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis 就会使用链表作为列表键的底层实现。　

3.2 链表的数据结构

每个链表节点使用一个 listNode结构表示（adlist.h/listNode）：

typedef struct listNode{
      struct listNode *prev;
      struct listNode * next;
      void * value;  
}

多个链表节点组成的双端链表：

我们可以通过直接操作list 来操作链表会更加方便：

typedef struct list{
    //表头节点
    listNode  * head;
    //表尾节点
    listNode  * tail;
    //链表长度
    unsigned long len;
    //节点值复制函数
    void *(*dup) (void *ptr);
    //节点值释放函数
    void (*free) (void *ptr);
    //节点值对比函数
    int (*match)(void *ptr, void *key);
}

list 组成的结构图：

3.3 链表的特性

双端：链表节点带有prev 和next 指针，获取某个节点的前置节点和后置节点的时间复杂度都是O（N）

无环：表头节点的 prev 指针和表尾节点的next 都指向NULL，对立案表的访问时以NULL为截止

表头和表尾：因为链表带有head指针和tail 指针，程序获取链表头结点和尾节点的时间复杂度为O(1)

长度计数器：链表中存有记录链表长度的属性 len

多态：链表节点使用 void* 指针来保存节点值，并且可以通过list 结构的dup 、 free、 match三个属性为节点值设置类型特定函数。

4、字典

4.1 概述

字典，又称为符号表（symbol table）、关联数组（associative array）或映射（map），是一种用于保存键值对的抽象数据结构。　

在字典中，一个键（key）可以和一个值（value）进行关联，字典中的每个键都是独一无二的。在C语言中，并没有这种数据结构，但是Redis 中构建了自己的字典实现。

举个简单的例子：

redis > SET msg "hello world"
OK

创建这样的键值对（“msg”，“hello world”）在数据库中就是以字典的形式存储

4.2 字典的定义

4.2.1 哈希表

Redis 字典所使用的哈希表由 dict.h/dictht 结构定义：

typedef struct dictht {
   //哈希表数组
   dictEntry **table;
   //哈希表大小
   unsigned long size;

   //哈希表大小掩码，用于计算索引值
   unsigned long sizemask;
   //该哈希表已有节点的数量
   unsigned long used;
}

一个空的字典的结构图如下：

我们可以看到，在结构中存有指向dictEntry 数组的指针，而我们用来存储数据的空间既是dictEntry

4.2.2 哈希表节点（ dictEntry ）

dictEntry 结构定义：

typeof struct dictEntry{
   //键
   void *key;
   //值
   union{
      void *val;
      uint64_tu64;
      int64_ts64;
   }
   struct dictEntry *next;

}

在数据结构中，我们清楚key 是唯一的，但是我们存入里面的key 并不是直接的字符串，而是一个hash 值，通过hash 算法，将字符串转换成对应的hash 值，然后在dictEntry 中找到对应的位置。

这时候我们会发现一个问题，如果出现hash 值相同的情况怎么办？Redis 采用了链地址法：

当k1 和k0 的hash 值相同时，将k1中的next 指向k0 想成一个链表。

4.2.3 字典

typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privedata;
    // 哈希表
    dictht  ht[2];
    // rehash 索引
    in trehashidx;

}

type 属性 和privdata 属性是针对不同类型的键值对，为创建多态字典而设置的。

ht 属性是一个包含两个项（两个哈希表）的数组

普通状态下的字典：

4.3 解决哈希冲突

在上述分析哈希节点的时候我们有讲到：在插入一条新的数据时，会进行哈希值的计算，如果出现了hash值相同的情况，Redis 中采用了连地址法（separate chaining）来解决键冲突。

每个哈希表节点都有一个next 指针，多个哈希表节点可以使用next 构成一个单向链表，被分配到同一个索引上的多个节点可以使用这个单向链表连接起来解决hash值冲突的问题。

举个例子：

现在哈希表中有以下的数据：k0 和k1

我们现在要插入k2，通过hash 算法计算到k2 的hash 值为2，即我们需要将k2 插入到dictEntry[2]中：

在插入后我们可以看到，dictEntry指向了k2，k2的next 指向了k1，从而完成了一次插入操作（这里选择表头插入是因为哈希表节点中没有记录链表尾节点位置）

4.4 Rehash

随着对哈希表的不断操作，哈希表保存的键值对会逐渐的发生改变，为了让哈希表的负载因子维持在一个合理的范围之内，我们需要对哈希表的大小进行相应的扩展或者压缩，这时候，我们可以通过 rehash（重新散列）操作来完成。

4.4.1 目前的哈希表状态：

我们可以看到，哈希表中的每个节点都已经使用到了，这时候我们需要对哈希表进行拓展。

4.4.2 为哈希表分配空间

哈希表空间分配规则：

如果执行的是拓展操作，那么ht[1] 的大小为第一个大于等于ht[0] 的2的n次幂

如果执行的是收缩操作，那么ht[1] 的大小为第一个大于等于ht[0] 的2的n次幂

因此这里我们为ht[1] 分配 空间为8，

4.4.3 数据转移

ht[0]のデータをht[1]に転送します。転送処理中に、ハッシュテーブルノード内のデータのハッシュ値を再計算する必要があります。

データ転送後の結果：

4.4.4 ht[0]を解放します。

ht[0]を解放し、ht[1]をht[0]に設定します。最後に割り当てます。 ht[1] への空のハッシュ テーブル:

4.4.5 プログレッシブ リハッシュ

上で述べたように、展開または圧縮中に、直接次のことができます。データ量が比較的少ないため、すべてのキーと値のペアを ht[1] に再ハッシュします。実際の開発プロセスでは、この再ハッシュ操作は一度に集中的に完了するのではなく、複数回かつ段階的に完了します。

プログレッシブ リハッシュの詳細な手順:

1. ディクショナリが 2 つのハッシュ テーブル ht[0] と ht[1] を同時に保持できるように、ht[1] にスペースを割り当てます

2. インデックス カウンター変数 rehanadx をいつ維持し、その値を 0 に設定して、再ハッシュの開始を示します

3. 再ハッシュ中に、ディクショナリに対して CRUD 操作が実行されるたびに、指定された操作を実行することに加えて、プログラムは ht[0] のデータを ht[1] テーブルに再ハッシュし、rebashidx

4 に 1 を追加します。転送 ht[1] を入力するときは、rehashdx を -1 に設定して、リハッシュの終了を示します。

プログレッシブ リハッシュを使用する利点は、分割統治アプローチを採用し、発生する膨大な量の計算を回避できることです。集中的な焼き直しによって。

以上がRedis の基礎となるデータ構造の詳細な紹介の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。