字符串

redis的字符串采用了空间换时间的方法来提高效率, 一个redis的字符串结构称为SDS(simple dynamic string):

1
2
3
4
5
6
struct sdshdr {
    int len; // 记录buf数组中已经使用的字节数量, 也就是sds保存的字符串长度
    int free; // 记录buf中空闲的数量
    char buf[]; // 字节数组, 整个sds占用的字符串数组的长度
    // buf的长度=len+free+最后的一个空字符`\0` 
}

这样的一个好处是:

  1. 直接记录了字符串的长度, 获取字符串长度的代价是$O(1)$, c字符串的是$O(n)$
  2. 杜绝缓冲区溢出的问题, 拼接字符串的话先检查buf大小够不够, 不够的话分配足够的空间然后再拼接字符串.

为了提高修改字符串的效率, 提供了预分配和惰性删除两种策略:

  • 预分配

修改字符串的时候, 除了分配额外的需要空间外, 还根据分配后len的大小:

  • 如果sds的长度小于1mb, 那么将free设置大小为len

  • 如果sds长度大于1mb, 那么free的value设置为1mb

  • 惰性删除

如果减少字符串长度的话, 会修改字符串为需要的值, 修改len属性, 然后修改free属性, 但是不会直接的将这部分内存释放, 而是留着为今后的增长需要, 或者在需要的时候调用sdsfree释放内存.

sds使用len属性读取一个字符串而不是用\0来处理, 这样一个好处是O1的读取效率, 而且不用担心字符串的字符安全问题.

链表

redis的链表可以用作一个简单的消息队列, 或者一些别的功能. \

redis列表键的底层实现之一就是链表, 当一个列表键包含了数量比较多的元素, 或者列表中包含的元素都是比较长的字符串的时候, redis就会使用列表键的底层实现.

内部实现上, 一个链表结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value; // 这里注意value指针的类型
} listNode;

typedef struct list {
    listNode *head;
    listNode *tail;
    unsigned long len; // 链表包含的节点的数量
    void *(*dup) (void *ptr); // 节点复制函数
    void (*free) (void *ptr); // 节点释放函数
    void (*match) (void *ptr, void *key); // 节点比较函数
} list;

redis链表的特性有:

  • 双端链表
  • 无环, prev和next的指针都指向null
  • 带有链表的长度
  • 多态, 使用void*指针保存节点值, 实现了dup, free, match三个属性

字典

一个redis的字典的结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct dictht {
    dictEntry **table;
    unsigned long size; // hash表大小
    unsigned long sizemask; // 用于计算索引值, 总是size-1
    unsigned long used; // 这里为啥用long类型, 已有的节点数量
} dictht;

typedef struct dictEntry {
    void *key;
    union { // value
        void *val;
        uint64_t u64;
        uint64_t s64;
    } v;
    struct dictEntry *next; // 指向下一个hash表节点, 形成链表
    // 也就是说, redis用链表法解决key冲突的问题.
}

扩容

redis通过rehash方法实现hash表的扩展和收缩.

这里比较关键的两点:

  1. hash的ht[0]和ht[1]交替操作, 扩容和收缩的单位是>2或者<2

  2. 渐进rehash

为了不影响使用性能, redis不是一次性将ht[0]里面的所有数据全部rehash到ht[1]上, 而是渐进式进行.

  • 为ht[1]分配空间, 让字典同时持有ht[0]和ht[1]两个hash表
  • 将字典的索引计数器rehashidx设置为0, 表示rehash开始, 默认这个值没有的时候是-1
  • 字典的删除查找和更新操作会同在两个hash表上进行, 例如如果需要查找一个key, 会先在ht[0]上查找, 没有的话在ht[1]上查找
  • 在执行rehash的时候, 新添加到字典的key-value一律会保存到ht[1]里面, 而ht[0]则不再进行任何添加操作, 这个措施保证了ht[0]中包含的键值对数量只会减小不会增加最后随着rehash变成空表

小问题, 啥时候进行扩容, python貌似是死的2/3

脑洞

python字典的实现上, 扩容也是左移或者右移

分布式系统的分片数量增加, 也是一个rehash的过程.

跳跃表/跳表

redis的有序集合通过dict和跳表同时实现, 兼顾dict的O1和跳表的有序性.

跳表可以说是对平衡树的一种工程上的妥协.

redis使用跳表作为有序集合键的底层实现之一. 如果一个有序集合包含的元素数量较多, 或者有序集合中元素是比较长的字符串的话, 会使用跳表作为有序集合的底层实现.

todo, 这是因为如果量小的话, 直接使用数组效率会更高???

redis中, 跳表用在了两个地方:

  • 实现有序集合键
  • 集群节点中用作内部数据结构

redis中跳表新添加数据和删除数据如何操作