Redis의 기본 데이터 구조에 대한 심층 소개

1. 개요

Redis를 사용해 본 학생들은 모두 Redis가 a Memcached와 유사하지만 Memcached보다 우수한 고성능 키-값 데이터베이스인 키-값 쌍의 분산 스토리지 시스템입니다.

은 "Redis 설계 및 구현"에 설명되어 있습니다.

Redis Database쌍으로 된 모든 키 값( 키-값)은 객체로 구성됩니다:

데이터베이스 키는 항상 문자열 객체입니다.

데이터베이스 값은 다섯 가지 유형의 객체 중 하나입니다: 문자열 객체, 리스트 객체(list), 해시 객체(hash), 세트 객체(set), 순서 세트(sort set) 객체입니다.

Redis가 Memcached보다 낫다고 말하는 이유는 Redis의 등장으로 인해 Memcached의 키-값 스토리지 부족이 심화된 경우도 있기 때문입니다. 데이터베이스 및 이러한 데이터 유형은 모두 푸시/팝, 추가/제거, 교차, 결합, 차이 및 다양한 작업을 지원하며 이러한 작업은 모두 원자적입니다.

오늘 논의할 내용은 Redis의 값 데이터 유형이 아니라 특정 구현, 즉 기본 데이터 유형에 관한 것입니다.

Redis 기본 데이터 구조에는 다음과 같은 데이터 유형이 있습니다:

1. 단순 동적 문자열

2. 🎜#

3, 사전

4, 점프 테이블

5, 정수 컬렉션

6, 압축 목록

# 🎜🎜 #7. 개체

2. 간단한 동적 문자열 SDS

2.1 개요

ANSI C 언어로 작성된 소스 키-값 데이터베이스. Redis의 문자열은 C 언어의 전통적인 문자열 표현을 사용한다고 주관적으로 생각할 수 있지만 실제로는 그렇지 않습니다. C 언어 대신. , 우리는 단순 동적 문자열 SDS라는 추상 유형을 구축하고 SDS를 Redis의 기본 문자열 표현으로 사용했습니다.

redis>SET msg "hello world"
OK

키 = msg, 값 = hello world를 사용하여 새 키-값 쌍을 설정합니다. 데이터 구조는 다음과 같습니다.

키(key)는 문자열 객체이고 객체의 기본 구현은 문자열 "msg"를 보유한 저장 SDS입니다.

The value(value)도 문자열 객체입니다. 객체의 기본 구현은 "hello world"라는 문자열을 포함하는 SDS입니다.

#🎜🎜 #위의 예에서 문자열이 어떤 종류의 데이터 유형인지 직관적으로 확인할 수 있습니다. 우리는 보통 redis를 사용할 때 생성합니다. SDS는 문자열을 저장하는 데 사용되는 것 외에도 버퍼 AOF 모듈에서 AOF 버퍼로도 사용됩니다.

2.2 SDS 정의

Redis에 정의된 동적 문자열의 구조:

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

1. buf에서 사용되는 공간의 길이를 기록하는 데 사용되는 len 변수(여기서는 Redis의 길이가 5임을 나타냄)

2. buf에 공간 길이를 기록하는 데 사용됩니다. 아직 여유 공간이 있습니다(처음 할당되는 공간이며 일반적으로 여유 공간이 없습니다. 문자열을 수정하면 남은 공간이 있게 됩니다)

#🎜🎜 #3, 문자열을 기록하는 데 사용되는 buf 문자 배열(Redis 기록)

2.3 SDS와 C 문자열의 차이점

Traditional C string은 길이가 N+1인 문자열 배열을 사용하여 길이가 N인 문자열을 나타냅니다. 이는 문자열 길이, 문자열 확장 및 기타 작업을 얻을 때 비효율적입니다. C 언어는 문자열 보안, 효율성 및 기능에 대한 Redis의 요구 사항을 충족할 수 없는 이 간단한 문자열 표현 방법을 사용합니다2.3.1 문자열 길이 가져오기(SDS O(1) /C 문자열 O(n))

전통적인 C 문자열은 길이가 N+1인 문자열 배열을 사용하여 길이가 N인 문자열을 나타내기 때문에 길이가 C인 문자열을 얻으려면 문자열의 길이를 순회해야 합니다.

C 문자열과 달리 SDS의 데이터 구조에는 문자열의 길이를 저장하는 데 특별히 사용되는 변수가 있습니다. len 속성의 값을 가져오면 문자열의 길이를 직접 알 수 있습니다.

2.3.2 버퍼 오버플로 방지

C 문자열은 문자열의 길이를 기록하지 않습니다. 점점 높아지는 것 외에도 쉽게 버퍼 오버플로가 발생할 수 있습니다.

프로그램에 메모리에 서로 인접한 두 개의 문자열 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 Progressive rehash# 🎜🎜#

위에서 확장하거나 압축할 때 데이터 양이 상대적으로 적기 때문에 모든 키-값 쌍을 ht[1]로 직접 다시 해싱할 수 있다고 언급했습니다. 실제 개발 과정에서 이러한 재해시 작업은 한 번 중앙에서 완료되는 것이 아니라 여러 번 점진적으로 완료됩니다.

점진적 재해시의 세부 단계:

1. 사전이 ht[0]과 ht[1] 해시 테이블을 모두 보유하도록 ht[1]에 공간을 할당합니다# 🎜🎜#

2. 인덱스 카운터 변수 rehahidx를 유지하고 해당 값을 0으로 설정하여 재해시가 시작됨을 나타냅니다

3. 사전에 지정된 작업을 수행하는 것 외에도 프로그램은 ht[0]의 데이터를 ht[1] 테이블로 다시 해시하고 rehashidx를 1

4 늘립니다. ht[0]이 ht[1]로 전송되고 rehashidx를 -1로 설정하여 rehash의 끝을 나타냅니다.

점진적 rehash 사용의 장점은 분할 정복 접근 방식을 채택하여 이를 방지한다는 것입니다. 중앙 집중식 재해시로 인해 발생하는 엄청난 양의 계산을 제거합니다.

위 내용은 Redis의 기본 데이터 구조에 대한 심층 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!