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

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

尚앞으로: 2019-11-28 16:23:252493검색

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임을 나타냄) Redis의 기본 데이터 구조에 대한 심층 소개

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 버퍼 오버플로 방지

Redis의 기본 데이터 구조에 대한 심층 소개 C 문자열은 문자열의 길이를 기록하지 않습니다. 점점 높아지는 것 외에도 쉽게 버퍼 오버플로가 발생할 수 있습니다.

프로그램에 메모리에 서로 인접한 두 개의 문자열 s1과 s2가 있다고 가정합니다. 그 중 s1은 "redis" 문자열을 저장하고 두 번째 s2는 "MongoDb" 문자열을 저장합니다. 🎜🎜 #

이제 s1의 내용을 redis 클러스터로 수정했지만 s1에 충분한 공간을 다시 할당하는 것을 잊어버리면 다음과 같은 문제가 발생합니다. # 🎜🎜 #

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

s2의 원본 콘텐츠가 S1의 콘텐츠로 채워졌음을 알 수 있으며, s2는 이제 "Mongodb"가 아닌 클러스터입니다.

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

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

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

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

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

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

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

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

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

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

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

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

2.3.4 惰性空间释放

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

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

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

2.3.5 二进制安全

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

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

例如：

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

2.3.6 兼容部分C字符串函数

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

2.3.7 总结

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

3、链表

3.1 概述

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

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

3.2 链表的数据结构

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

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

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

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

我们可以通过直接操作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 组成的结构图：

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

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;
}

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

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

我们可以看到，在结构中存有指向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 采用了链地址法：

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

当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 属性是一个包含两个项（两个哈希表）的数组

普通状态下的字典：

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