Redis中基础数据结构

2025年7月20日
| 没有评论

SDS

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

SDS遵循C字符串以空字符串结尾的惯例，保存空字符串的1字节空间不记入在SDS的len属性中。

sds结构体相比于c字符串的优势：

  • 常数复杂度获取字符长度。strlen命令
  • 杜绝缓冲区溢出。SDS api对SDS进行修改时，会先检查SDS的空间是否满足时所需的要求，不满足则会自动拓展到所需的大小。
  • 减少修改字符串时带来的内存重分配次数。内存重分配设计复杂的算法，并且可能需要执行系统调用，所以它通常是一个比较耗时的操作。SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联。通过未使用空间，SDS实现了空间预分配和惰性空间释放两种策略
    • 空间预分配：用于优化SDS字符串增长操作：当SDS需要进行空间拓展的时候，程序不仅会为SDS分配必须的空间，还会为SDS分配额外的未使用空间。
      • 对SDS修改之后，SDS长度小于1MB，程序分配和len属性同样大小的未使用空间，len=free。SDS长度大于等于1MB，那么程序会分配1MB未使用空间。
    • 惰性空间释放：优化SDS的字符串缩短操作。SDS的API缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节。SDS也提供了相应的API，让我们可以在有需要的时候，真正进行惰性空间释放。
  • 二进制安全：SDS所有的API都会以处理二进制的方式来处理SDS存放在buf数组里的数据。

链表

当一个列表键包含比较多的元素，又或者列表中包含的元素都是比较长的字符串时，redis就会使用链表作为列表键的底层实现。

除了列表键之外，发布订阅、慢查询、监视器，redis服务器本身保存客户端的状态信息、构建客户端输出缓冲区都使用链表。

//链表节点
struct listNode{
   struct ListNode *prev;//前置节点
   struct ListNode *next;//后置节点
   void *value;//节点的值
}listNode;

struct list{
  ListNode *head;//表头节点
  ListNode *tail;//表尾节点
  long len;//链表包含的节点数量
  void *(*dup)(void *ptr);//节点复制函数
  void (*free)(void *ptr);//节点值释放函数
  int (*match)(void *ptr, void *key);//节点值对比函数
}

字典

字典在redis中的应用非常广泛，redis数据库就是使用字典作为底层实现，对数据库的增删改查操作也是构建在对字典的操作之上的。

字典还是哈希键的底层实现之一，当一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串时，redis就会使用字典作为哈希键的底层实现之一。

//哈希表实现
struct dictht{
    dictEntry **table;//哈希表数组
    long size;//哈希表大小
    long sizemask;//值为size - 1,哈希表大小索引
    long used;//已有节点数量
}
//哈希节点
struct dictEntry{
  void *key;//键
  union {
    void *val;
    uint64_tu64;
    int64_ts64; 
  }v; //值
  struct dictEntry *next;//指向下一个哈希表节点，形成链表  
}dictEntry;

//字典结构
struct dict{
   dictType *type;//类型特定函数
   void *privdata;//私有数据
   dictht ht[2];//哈希表
   int trehashidx;//当rehash不再进行时，值为以。
}

redis总是将新节点添加到链表的头部位置。

随着操作的不断进行，哈希标保存的键值会逐渐地增加或者减少，为了哈希表地负载因子维持在一个合理范围之内，当哈希表保存地键值对太多或太少，程序需要对哈希表的大小进行拓展或收缩。拓展和收缩哈希表的工作可以通过执行rehash操作完成。

rehash的步骤：

  • 为字典ht[1]哈希表分配空间。
    • 如果执行的是扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used * 2的2^n.
    • 如果是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2^n。
  • 将ht[0]的键值对rehash到ht[1]上。

负载因子 = ht[0].used / ht[0].size
以下条件任意一个满足，程序会自动开始对哈希表进行拓展：

  • 服务器没有在执行BGSAVE或者BGREWRITEAOF命令，负载因子大于等于1.
  • 服务器在执行BGSAVE或者BGREWRITEAOF，并且负载因子大于等于5.

以下条件满足，程序会自动开始对哈希表进行收缩：

  • 当哈希表的负载因子小于0.1。

写时复制技术：用于延迟或减少数据的复制。当多个任务共享相同的资源时。它们都可以指向该资源的引用，直到其中有一个任务视图修改它为止。只有在实际需要写入或修改资源时，才会创建一个真正的复制品，通常是为了确保原始资源不会被改变，而其它而南无依然可以继续使用原始资源。

渐进式rehash，rehash动作并不是一次性、集中式的完成的，而是分多次、渐进式地完成的。不然如果哈希表存储的键值对多且全部rehash到ht[1]庞大的计算可能会导致服务器在一段时间内停止服务。

rehash过程中，字典会同时使用ht[0]和ht[1]两个哈希表，所以在渐进性rehash进行期间，字典的删除、查找、、更新等操作会在两个哈希表上进行。新添加到字典的键值对一律保存到ht[1]里面。

跳跃表

跳跃表是一种有序数据结构，通过在每个节点中维持多个指向其它节点的指针，从而大块快速访问节点的目的。跳跃表支持平均O(logN)最坏O(N)复杂度的节点查找。

在大部分情况下，跳跃表的效率可以和平衡术相媲美，并且因为跳跃表的实现比平衡树要来得更为简单。

redis使用跳跃表作为有序集合键的底层实现，如果有序集合包含元素数量多，又或者有序集合中的元素成员是比较长的字符串时，redis就会使用跳跃表作为有序集合实现。

跳跃表只用于两个地方，有序集合键和集群节点中用作内部数据结构。

struct zskiplistNode{
   //层
   struct zskipListLevel {
       struct zskiplistNode *forward;//前进指针
       unsigned int span;//跨度
   } level[];
   struct zskipListNode *backward;//后退指针；
   double score;//分值
   robj *obj;//成员对象
}//zskiplistNode;

struct zskiplist{
   struct zskiplistNode *header,*tail;//表头节点和表尾节点
   long length;//表中节点数量
   int level;//表中层数最大节点的层数
}zskiplist;

每次创建一个新跳跃节点的时候，程序都根据幂次定律随机生成一个介于1和32之间的值作为level数组的大小，这个大小就是层的高度。跳跃表中所有节点都按分值从小到大来排序。

跨度是用来计算排位，在查找某个节点的过程中，将沿途访问过的所有层跨度累计就能得到目标节点的排位；。

整数集合

整数集合(intset)是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，redis就会使用整数集合作为集合键的底层实现。

//可以保存int16_t、int32_t或者int64_t的整数值
struct inset{
    uint32_t encoding;//编码方式
    uint32_t length;//集合包含的元素数量
    int_8 contents[];//保存元素的数组
} intset;

contents是整数集合的底层实现：整数集合的每个元素都是contents数组的一个数组项，各个项在数组中按值的大小从小到大有序排列。contents保存的整数类型由encoding指定。

当我们要将一个新元素添加到整数集合里面，并且新元素类型比encoding表示的范围要大时。整数集合需要先进行升级。

整数集合升级的好处：

  • 提高灵活性：避免类型出错，所有元素保持一致的编码类型。
  • 节约内存：按需分配内存。

整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。

压缩列表

压缩列表是列表键和哈希键的底层实现之一。当一个列表键只包含少量的列表项，并且每个列表项要么是小整数值要么是长度比较短的字符串，就是使用压缩列表来做列表键的底层实现。

当一个哈希键只包含少量键值对，且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，使用压缩列表作为底层实现。

压缩列表是由一系列特殊编码的连续内存块组成顺序性数据结构。一个压缩列表可以包含任意多个节点(entry)，每个节点可以保存一个字节数组或者一个整数值。

//zipList结构
struct ziplist{
    uint32_t zlbytes;//整个压缩列表占用的内存字符数
    uint32_t zltail;//记录压缩列表表尾系欸但距离压缩列表的起始地址字节
    uint16_t;//记录压缩列表的节点数量
    entryX ; //压缩列表的各个节点
    uint8_t zlend;//特殊值，用于标记压缩列表得到末端
}
// zipListNode
struct ziplistNode {
    previoue_entry_length;//可以是1字节(254)或者5字节(第一个字节254，后面四个字节是实际长度)，记录压缩列表前一个节点的长度,用于向前一个节点进行回溯
    encoding; //记录节点content属性所保存数据类型以及长度，值最高位可以代表数据类型。
    content; //保存节点的值，节点值可以是一个字节数组或者整数。 
}

由于previous_entry_length这个可变量，可能会造成ziplist的连锁更新。添加新节点和删除节点也可能会引起连锁更新。

数据库