Redis设计与实现的读书笔记，通过梳理结构希望能更好的理解

数据结构与对象

Redis是kv数据库，key总是一个字符串对象 string object，而键的值可以有五种类型

  • string
  • list
  • hash
  • set
  • sorted set

SDS （simple dynamic string）简单动态字符串

1
2
3
4
5
6
7
8
9

sds.h/sdshdr
struct sdshdr {
  //记录buf数组中已经使用字节的数量
  //len(buf)
	int len;
  int free;
  //保存原始字符串，最后一个字符为空字符串'\0'
  char buf[];
}

SDS遵循C字符串以空字符结尾的惯例，保存空字符的1字节空间不计算在SDS的len属性里面，并且为空字符分配额外的1字节空间，以及添加空字符到字符串末尾等操作，都是由SDS函数自动完成的，所以这个空字符对于SDS的使用者来说是完全透明的。遵循空字符结尾这一惯例的好处是，SDS可以直接重用一部分C字符串函数库里面的函数。

SDS同C中字符串的区别

  • 常数时间获取长度，O(1)

    • c中字符串需要遍历，直到遇到\0，O(n)

  • 杜绝缓冲区溢出

    缓冲区是一块连续的计算机内存区域，可保存相同数据类型的多个实例。缓冲区可以是堆栈(自动变量)、堆(动态内存)和静态数据区(全局或静态)。在C/C++语言中，通常使用字符数组和malloc/new之类内存分配函数实现缓冲区。溢出指数据被添加到分配给该缓冲区的内存块之外。缓冲区溢出是最常见的程序缺陷。

    1
2

    // c中strcat拼接字符串可能会导致缓冲区溢出
// sds中存在API sdscat函数，拼接前会检查空间是否满足要求

  • 减少修改字符串导致的内存重分配次数

    内存重分配需要执行系统调用，是一个耗时的操作，Redis数据库中的key可能会被频繁修改，对速度有较高要求。

    • 空间预分配 长度小于1MB，会分配2倍实际所需空间；大于1MB，每次多分配1MB
    • 惰性空间释放 删除后不会马上释放，可以通过API按需要释放

  • 二进制安全

    • C中字符串不能保存\0，所以只能保存文本数据，不能保存二进制数据
    • SDS的API都是binary-safe，以处理二进制的方式去处理数据，通过len字段去判断字符串是否结束

  • 兼容部分C字符串函数

链表

C语言没有内置list，Redis自己实现。

列表键list，以有序的方式存储多个可重复的值

LPUSH/RPUSH LPOP/RPOP 复杂度O(1)

LLEN：返回列表长度

LINDEX：返回给定索引的值

LRANGE：返回给定索引范围内的值

LSET：修改 LINSERT：插入 LREM：删除 LTRIM：修剪

应用：可以实现社交平台的用户时间线，即bilibili动态功能

列表的底层实现是链表。当列表键包含较多元素，或者包含的元素都是较长的字符串时，底层为链表。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

// 双向链表节点
typedef struct listNode {
  struct listNode* prev;
  struct listNode* next;
  void* value; 			// 可以保存不同类型的值
}listNode;
  
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;

list-1

字典 hash

HLEN：返回哈希键长度

HGETALL：返回所有哈希键值对

字典使用哈希表作为底层实现，一个哈希表里面有多个哈希表节点，每个哈希表节点保存字典的一个键值对

跳表 skiplist

支持平均O(logN) 最坏O(N)的节点查找，可以用跳跃表代替平衡树

跳表使用：有序集合键，集群节点内部

整数集合

inset是set的底层实现之一，set只包含整数且数量不多时

1
2
3
4
5
6
7

typedef struct intset {
  // 编码方式，决定content里面存int_8/int_16/int_32
  uint32_t encoding;
  uint32_t length;
  
  int8_t contents[];
} intset;

整数集合可以升级，以满足保存值的类型int_8 -> int_16

压缩列表 ziplist

列表键和哈希键的底层实现之一；

列表键只包含少量列表项时，哈希键只包含少量键值对时，底层用ziplist

ziplist为节约内存而开发，是由一系列特殊编码的连续内存块组成的顺序型数据结构

ziplist-1

每个压缩列表节点可以保存一个字节数组或者一个整数值

// 节点组成：
// previous_entry_length, encoding, content
// previous_entry_length：前一节点长度：可以实现从后向前遍历
// encoding：记录保存数据类型及长度

对象

Redis并没有直接使用这些数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象，每种对象都用到了至少一种我们前面所介绍的数据结构。

除此之外，Redis的对象系统还实现了基于引用计数技术的内存回收机制，当程序不再使用某个对象的时候，这个对象所占用的内存就会被自动释放；另外，Redis还通过引用计数技术实现了对象共享机制，这一机制可以在适当的条件下，通过让多个数据库键共享同一个对象来节约内存。

  • Redis数据库中的每个键值对的键和值都是一个对象。
  • Redis共有字符串、列表、哈希、集合、有序集合五种类型的对象，每种类型的对象至少都有两种或以上的编码方式，不同的编码可以在不同的使用场景上优化对象的使用效率。
  • 服务器在执行某些命令之前，会先检查给定键的类型能否执行指定的命令，而检查一个键的类型就是检查键的值对象的类型。
  • Redis的对象系统带有引用计数实现的内存回收机制，当一个对象不再被使用时，该对象所占用的内存就会被自动释放。
  • Redis会共享值为0到9999的字符串对象。只共享整数值的字符串对象
  • 目前来说，Redis会在初始化服务器时，创建一万个字符串对象，这些对象包含了从0到9999的所有整数值，当服务器需要用到值为0到9999的字符串对象时，服务器就会使用这些共享对象，而不是新创建对象。
  • 对象会记录自己的最后一次被访问的时间，这个时间可以用于计算对象的空转时间。

单机数据库的实现

多机数据库的实现

独立功能的实现