redis——数据结构(字典、链表、字符串)

举报
兔老大 发表于 2021/04/19 23:27:50 2021/04/19
2.3k+ 0 0
【摘要】 1 字符串 redis并未使用传统的c语言字符串表示,它自己构建了一种简单的动态字符串抽象类型。 在redis里,c语言字符串只会作为字符串字面量出现,用在无需修改的地方。 当需要一个可以被修改的字符串时,redis就会使用自己实现的SDS(simple dynamic string)。比如在redis数据库里,包含字符串的键值对底层都是SDS实现的,不止如此,SDS还...

1 字符串

redis并未使用传统的c语言字符串表示,它自己构建了一种简单的动态字符串抽象类型。

在redis里,c语言字符串只会作为字符串字面量出现,用在无需修改的地方。

当需要一个可以被修改的字符串时,redis就会使用自己实现的SDS(simple dynamic string)。比如在redis数据库里,包含字符串的键值对底层都是SDS实现的,不止如此,SDS还被用作缓冲区(buffer):比如AOF模块中的AOF缓冲区以及客户端状态中的输入缓冲区。

下面来具体看一下sds的实现:


      struct sdshdr
      {
      int len;//buf已使用字节数量(保存的字符串长度)
      int free;//未使用的字节数量
      char buf[];//用来保存字符串的字节数组
      };
  
 

sds遵循c中字符串以'\0'结尾的惯例,这一字节的空间不算在len之内。

这样的好处是,我们可以直接重用c中的一部分函数。比如printf;

    sds相对c的改进

    获取长度:c字符串并不记录自身长度,所以获取长度只能遍历一遍字符串,redis直接读取len即可。

    缓冲区安全:c字符串容易造成缓冲区溢出,比如:程序员没有分配足够的空间就执行拼接操作。而redis会先检查sds的空间是否满足所需要求,如果不满足会自动扩充。

    内存分配:由于c不记录字符串长度,对于包含了n个字符的字符串,底层总是一个长度n+1的数组,每一次长度变化,总是要对这个数组进行一次内存重新分配的操作。因为内存分配涉及复杂算法并且可能需要执行系统调用,所以它通常是比较耗时的操作。   

    redis内存分配:

1、空间预分配:如果修改后大小小于1MB,程序分配和len大小一样的未使用空间,如果修改后大于1MB,程序分配  1MB的未使用空间。修改长度时检查,够的话就直接使用未使用空间,不用再分配。 

2、惰性空间释放:字符串缩短时不需要释放空间,用free记录即可,留作以后使用。

    二进制安全

c字符串除了末尾外,不能包含空字符,否则程序读到空字符会误以为是结尾,这就限制了c字符串只能保存文本,二进制文件就不能保存了。

而redis字符串都是二进制安全的,因为有len来记录长度。

2 链表

作为一种常用数据结构,链表内置在很多高级语言中,因为c并没有,所以redis实现了自己的链表。

链表在redis也有一定的应用,比如列表键的底层实现之一就是链表。(当列表键包含大量元素或者元素都是很长的字符串时)

发布与订阅、慢查询、监视器等功能也用到了链表。

具体实现:


      //redis的节点使用了双向链表结构
      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;
  
 

总结一下redis链表特性:

双端、无环、带长度记录、

多态:使用 void* 指针来保存节点值, 可以通过 dup 、 free 、 match 为节点值设置类型特定函数, 可以保存不同类型的值。

3、字典

其实字典这种数据结构也内置在很多高级语言中,但是c语言没有,所以redis自己实现了。

应用也比较广泛,比如redis的数据库就是字典实现的。不仅如此,当一个哈希键包含的键值对比较多,或者都是很长的字符串,redis就会用字典作为哈希键的底层实现。

来看看具体是实现:


      //redis的字典使用哈希表作为底层实现
      typedef struct dictht {
      // 哈希表数组
       dictEntry **table;
      // 哈希表大小
      unsigned long size;
      // 哈希表大小掩码,用于计算索引值
      // 总是等于 size - 1
      unsigned long sizemask;
      // 该哈希表已有节点的数量
      unsigned long used;
      } dictht;
  
 

table 是一个数组, 数组中的每个元素都是一个指向dictEntry 结构的指针, 每个 dictEntry 结构保存着一个键值对

图为一个大小为4的空哈希表。

我们接着就来看dictEntry的实现:


      typedef struct dictEntry {
      // 键
      void *key;
      // 值
      union {
      void *val;
      uint64_t u64;
      int64_t s64;
       } v;
      // 指向下个哈希表节点,形成链表
      struct dictEntry *next;
      } dictEntry;
  
 

(v可以是一个指针, 或者是一个 uint64_t 整数, 又或者是一个 int64_t 整数。)

next就是解决键冲突问题的,冲突了就挂后面,这个学过数据结构的应该都知道吧,不说了。

下面我们来说字典是怎么实现的了。


      typedef struct dict {
      // 类型特定函数
       dictType *type;
      // 私有数据
      void *privdata;
      // 哈希表
       dictht ht[2];
      // rehash 索引
      int rehashidx; //* rehashing not in progress if rehashidx == -1 
      } dict;
  
 

type 和 privdata 是对不同类型的键值对, 为创建多态字典而设置的:

type 指向 dictType , 每个 dictType 保存了用于操作特定类型键值对的函数, 可以为用途不同的字典设置不同的类型特定函数。

而 privdata 属性则保存了需要传给那些类型特定函数的可选参数。

而dictType就暂时不展示了,不重要而且字有点多。。。还是讲有意思的东西吧
 

    rehash(重新散列)

随着我们不断的操作,哈希表保存的键值可能会增多或者减少,为了让哈希表的负载因子维持在合理的范围内,有时需要对哈希表进行合理的扩展或者收缩。 一般情况下, 字典只使用 ht[0] 哈希表, ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。

redis字典哈希rehash的步骤如下:

1)为ht[1]分配合理空间:如果是扩展操作,大小为第一个大于等于ht[0]*used*2的,2的n次幂。

                                           如果是收缩操作,大小为第一个大于等于ht[0]*used的,2的n次幂。

2)将ht[0]中的数据rehash到ht[1]上。

3)释放ht[0],将ht[1]设置为ht[0],ht[1]创建空表,为下次做准备。

    渐进rehash

数据量特别大时,rehash可能对服务器造成影响。为了避免,服务器不是一次性rehash的,而是分多次。

我们维持一个变量rehashidx,设置为0,代表rehash开始,然后开始rehash,在这期间,每个对字典的操作,程序都会把索引rehashidx上的数据移动到ht[1]。

随着操作不断执行,最终我们会完成rehash,设置rehashidx为-1.

需要注意:rehash过程中,每一次增删改查也是在两个表进行的。

文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。

原文链接:fantianzuo.blog.csdn.net/article/details/89337191

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

作者其他文章

评论(0

抱歉,系统识别当前为高风险访问,暂不支持该操作

    全部回复

    上滑加载中

    设置昵称

    在此一键设置昵称,即可参与社区互动!

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。