深入解析Redis——数据结构_深入理解redis redis内部结构

简单动态字符串 SDS

 

Redis 没有使用C语言传统的字符串表示，而是自己构建了一种简单动态字符串的抽象类型，用为Redis的默认字符串表示

除了用了保存数据库的字符串值之外，SDS还被用作缓冲区：AOF模块中的AOF缓冲区，以及客户端状态中的输入缓冲区，都是由SDS实现的。

struct shshdr{
	int len; // 记录buf数据中已使用字节的数量
	int free; // 记录buf数组中未使用字节的数量
	char buf[]; // 字节数组，用于保存字符串
}

SDS与C字符的区别在于，C语言使用的这种简单字符串表示方式，并不能满足Redis对字符串安全性、效率的要求。

• 由于C字符串并没有保存字符串的长度信息，当想要获取长度的时候，必须要遍历字符串，时间复杂度为O(N)；而SDS 的len变量保存了字符串的长度信息，时间复杂度为O(1)。
• C中若想要增加或者减少字符串的长度，需要妥善地处理分配或者删除内存，否则会导致缓冲区溢出；SDS则采用了一种空间预分配和惰性空间两种方式来优化这个问题。

**空间预分配：**空间预分配用于优化SDS的字符串增长操作。当SDS的API对一个SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配修改所必须要的空间，还会为SDS分配额外的未使用空间。

当修改后SDS的长度小于 1MB的时候，为程序分配和len一样大小的空间，即 free=len；若修改后的长度大于1MB，则分配 1MB的未使用空间。

**惰性空间释放：**惰性空间释放用于优化SDS的字符串缩短操作。当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，并等待将来使用。当然，SDS也提供了相应的API，在需要的时候真正地释放未使用的内存空间！

**二进制安全：**SDS的API都是二进制安全的（binary-safe），所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设，数据在写入时是什么样的，它被读取时就是什么样。SDS使用len属性的值而不是空字符来判断字符串是否结束，同时SDS可以兼容部分C字符串函数。

链表 Linked List

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

链表在Redis中的应用非常广泛，比如列表键的底层实现之一就是链表，发布与订阅、慢查询、监视器等功能也用到了链表，Redis服务器本身还使用链表来保存多个客户端的状态信息，以及使用链表来构建客户端输出缓冲区（output buffer）。

 // 每个链表节点用一个listNode结构来表示
 struct listNode{
		struct listNode *prev; // 前置节点
		struct listNode *next; // 后置节点
		void *value; //节点的值
}

多个listNode结构就可以组成链表，但是我们通常使用list来持有链表

struct list {
		listNode * head;//表头节点
		listNode * tail;//表尾节点
		unsigned long len;//链表所包含的节点数量
		void *(*dup)(void *ptr);//节点值复制函数，用于复制链表节点所保存的值
		void (*free)(void *ptr);//节点值释放函数，用于释放链表节点所保存的值
		int (*match)(void *ptr,void *key);//节点值对比函数，用于对比链表节点所保存的值和另一个输出值是否相等
} 

Redis的链表实现的特性可以总结如下：

• 每个链表节点由一个listNode结构来表示，每个节点都有一个指向前置节点和后置节点的指针，所以Redis的链表实现是双端链表。
• 每个链表使用一个list结构来表示，这个结构带有表头节点指针、表尾节点指针，以及链表长度等信息。
• 因为链表表头节点的前置节点和表尾节点的后置节点都指向NULL，所以Redis的链表实现是无环链表。
• 通过为链表设置不同的类型特定函数，Redis的链表可以用于保存各种不同类型的值。

字典 Dick

在字典中，一个键（key）可以和一个值（value）进行关联，这些关联的键和值就称为键值对，字典中的每一个键都是独一无二的。

Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希节点，而每个哈希节点就保存了字典中的一个键值对。

// 哈希表
struct dicthashTabale{
		dictEntry **table;// 哈希表数组 table 其实是一个HashEntry的数组，数组中每个元素都是一个指向HashEntry结构的指针
		unsigned long size;//哈希表大小
		unsigned long sizemask;//哈希表大小掩码，用于计算索引值，总是等于size-1
		unsigned long used;//该哈希表已有节点的数量
}

// 哈希表节点
struct dictEntry {
		void *key;// 键
		union{
				void *val;
				uint64_tu64;
				int64_ts64;
		} v;//值, v属性保存着键值对中的值，其中键值对的值可以是一个指针，或者是一个uint64_t整数，又或者是一个int64_t整数。
		struct dictEntry *next; //指向下个哈希表节点，形成链表
}

//Redis中的字典由 dict结构来表示
struct dict {
		dictType *type;//类型特定函数，指向一个dictType结构的指针，每个dictType保存了一组用于操作特定类型键值对的函数
		void *privdata;//私有数据 保存了需要传给那些类型特定函数的可选参数 
		dictht ht[2];//哈希表，通常只使用 ht[0]作为哈希表，ht[1]只会在对ht[0]rehash的时候使用
		// rehash索引，rehash不在进行时，值为-1
	  int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} 

redis的哈希算法不太复杂，先计算key的hash值，再将hash值与sizemask进行与运算，算出在hashtable中的索引值；面对哈希冲突的情况，redis采用的是拉链法，为了速度来考虑，采用头插法，将新节点插入到链表的头位置。

**Rehash：**为了让哈希表的负载因子（load factor）维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。Redis对字典的哈希表rehash的步骤如下：

• 为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量。

  <aside>

  声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/157425