redis设计与实现.md

内部数据结构

简单动态字符串

• Redis字符串表示问sds，而不是C字符串（以\0结尾的char*）。
• 对比C字符串，sds有以下特性，
  • 高效执行长度计算（strlen）;
  • 高效执行追加操作（append）;
  • 二进制安全；
• sds会为追加操作进行优化，加快追加操作速度，并降低内存分配次数，代价是多占用了一些内存，这些内存是不会主动释放。

双端列表

• Redis 实现了自己的双端链表结构。
• 双端链表主要有两个作用：
  • 作为 Redis 列表类型的底层实现之一；
  • 作为通用数据结构，被其他功能模块所使用；
    • 事务模块使用双端链表来按顺序保存输入的命令；
    • 服务器模块使用双端链表来保存多个客户端；
    • 订阅/发送模块使用双端链表来保存订阅模式的多个客户端；
    • 事件模块使用双端链表来保存时间事件（time event）；
• 双端链表及其节点的性能特性如下：
  • 节点带有前驱和后继指针，访问前驱节点和后继节点的复杂度为 O(1) ，并且对链表的迭代可以在从表头到表尾和从表尾到表头两个方向进行；
  • 链表带有指向表头和表尾的指针，因此对表头和表尾进行处理的复杂度为 O(1) ；
  • 链表带有记录节点数量的属性，所以可以在 O(1) 复杂度内返回链表的节点数量（长 度）；
• 迭代器：
  • Redis 为双端链表实现了一个迭代器 ，这个迭代器可以从两个方向对双端链表进行迭代：
    • 沿着节点的 next 指针前进，从表头向表尾迭代；
    • 沿着节点的 prev 指针前进，从表尾向表头迭代；

字典

• 字典由键值对构成的抽象数据结构。

• Redis 中的数据库和哈希键都基于字典来实现。

• Redis 字典的底层实现为哈希表，每个字典使用两个哈希表，一般情况下只使用 0 号哈希

  表，只有在 rehash 进行时，才会同时使用 0 号和 1 号哈希表。

• 哈希表使用链地址法来解决键冲突的问题。

• Rehash 可以用于扩展或收缩哈希表。

• 对哈希表的 rehash 是分多次、渐进式地进行的。

跳跃表

• 跳跃表是一种随机化数据结构，它的查找、添加、删除操作都可以在对数期望时间下完

  成。

• 跳跃表目前在 Redis 的唯一作用就是作为有序集类型的底层数据结构之一，另一个构

  成有序集的结构是（字典）。

• 为了适应自身的需求，Redis 基于 William Pugh 论文中描述的跳跃表进行了修改，包括：

  • score 值可重复。
  • 对比一个元素需要同时检查它的 score 和 memeber 。
  • 每个节点带有高度为 1 层的后退指针，用于从表尾方向向表头方向迭代。