ccran 的个人博客 ccran 的个人博客

记录精彩的程序人生

目录
Redis设计与实现(1)字符串与链表
/  

Redis设计与实现(1)字符串与链表

Redis设计与实现(1)字符串与链表

1. SDS

字符串string基本使用

127.0.0.1:6379> set name ccran
OK
127.0.0.1:6379> get name
"ccran"

Redis使用SDS(simple dynamic string)来作为string字符串默认实现

struct sdshdr{
    int len;//buf字符数组已用长度
    int free;//buf字符数组未用长度
    char buf[];//字符数组用于保存字符串
}

sds.png

  1. buf用于存储字符串。不同于c字符串,字符数组中可以包含'\0'字符,因此是二进制安全的,可以存储图片、视频之类的二进制数据(底层还是数字);以'\0'字符结尾,这点与c字符串相同,好处为可重用部分c的字符串处理库函数。
  2. len代表字符串长度。相比于c字符串需要遍历整个串O(n)的时间复杂度,SDS只需要O(1)的时间复杂度,典型的空间换时间;并且可以通过校验长度杜绝缓冲区溢出。
  3. free标志字符数组当前可用的长度。目的是减少重分配的次数(内存重分配代价太高,涉及复杂算法与系统调用)。

字符数组增长导致扩容,会通过预分配策略分配min(1MB,len)的长度;
如[0,5,redis]=>[10,10,redisredis],[0,1M,xxx]=>[1M,2M,xxxxxx]

字符数组缩短时,会惰性释放未用到的空间(有需要时调用API释放);
如[0,10,redisredis]=>[5,5,redis]

2. 链表

列表list基本使用

127.0.0.1:6379> lpush list 1
(integer) 1
127.0.0.1:6379> rpush list 0
(integer) 2
127.0.0.1:6379> lrange list 0 -1
1) "1"
2) "0"
127.0.0.1:6379> llen list
(integer) 2

Redis使用双向双端链表作为list列表的底层实现之一,发布与订阅、慢查询、监视器也用到了该结构,结构类似于Java中的LinkedList

节点结构体为:

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);//节点值释放函数
    void *(*match)(void *ptr,void *key);//节点值对比函数
}

实例如下:

list.png

  1. 双端:保证头结点和尾节点获取的时间复杂度为O(1)
  2. 无环
  3. 双向:获取一个节点的前驱和后继节点时间复杂度为O(1)
  4. 长度计数:len标志链表节点的个数
  5. 多态:节点存储的数据通过void*引用,代表可以存储任意类型

标题:Redis设计与实现(1)字符串与链表
作者:ccran
地址:https://ccran.online/articles/2020/07/21/1595261118077.html