面试题】Redis常用数据类型,以及底层实现

2021/12/28 2:07:19

本文主要是介绍面试题】Redis常用数据类型,以及底层实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一、Redis的常用数据类型

字符串(string),队列(list),哈希(hash),集合(sets),有序集合(sorted sets)。

二、底层实现

1、字符串

Redis中的字符串都是由动态字符串(simple dynamic string SDS)实现的

  • 所有非数字的key。例如set msg "hello world" 中的key msg.
  • 字符串数据类型的值。例如`` set msg "hello world"中的msg的值"hello wolrd"
  • 非字符串数据类型中的“字符串值”。例如RPUSH fruits "apple" "banana" "cherry"中的"apple" "banana" "cherry"。

SDS数据结构定义:

struct sdshdr {
  int len;// buf 中已占用字节数
  int free;// buf 中剩余可用字节数
  char buf[];// 数据空间
};

Redis 3.2之前的SDS这样设计的有点:

1)有单独的统计变量len和free(称为头部)。可以很方便地得到字符串长度。
2)内容存放在柔性数组buf中,SDS对上层暴露的指针不是指向结构体SDS的指针,而是直接指向柔性数组buf的指针。上层可像读取C字符串一样读取SDS的内容,兼容C语言处理字符串的各种函数。
3)由于有长度统计变量len的存在,读写字符串时不依赖“\0”终止符,保证了二进制安全。

2、队列(list)

list的底层数据结构时链表。Redis 3.2之前的版本(包含3.2)使用的时ziplist或者linkedlist,Redis 3.2之后版本使用的quicklist。

ziplist

压缩列表是为了节约内存而开发的,是存储在连续内存块上的顺序数据结构。一个压缩列表可以包含任意多的 entry 节点,每个节点包含一个字节数组或整数。redis 中并没有显式定义 ziplist 的数据结构,仅仅提供了一个描述结构 zlentry 用于操作数据。

typedef struct zlentry {
    unsigned int prevrawlensize;// 用于记录前一个 entry 长度的字节数
    unsigned int prevrawlen;    // 前一个 entry 的长度
    unsigned int lensize        // 用于记录当前 entry 类型/长度的字节数
    unsigned int len;           // 实际用于存储数据的字节数
    unsigned int headersize;    // prevrawlensize + lensize
    unsigned char encoding;     // 用于指示 entry 数据的实际编码类型
    unsigned char *p;           // 指向 entry 的开头
} zlentry;

各字段含义如下:

  • 1、zlbytes:压缩列表的字节长度,占4个字节,因此压缩列表最长(2^32)-1字节;
  • 2、zltail:压缩列表尾元素相对于压缩列表起始地址的偏移量,占4个字节;
  • 3、zllen:压缩列表的元素数目,占两个字节;那么当压缩列表的元素数目超过(2^16)-1怎么处理呢?此时通过zllen字段无法获得压缩列表的元素数目,必须遍历整个压缩列表才能获取到元素数目;
  • 4、entryX:压缩列表存储的若干个元素,可以为字节数组或者整数;entry的编码结构后面详述;
  • 5、zlend:压缩列表的结尾,占一个字节,恒为0xFF

该数据结构具有以下特征:

  • 结构紧凑:一整块连续内存,没有多余的内存碎片,更新会导致内存 realloc 与内存复制,平均时间复杂度为 O(N)
  • 逆向遍历:从表尾开始向表头进行遍历
  • 连锁更新:对前一条数据的更新,可能导致后一条数据的 prev_entry_length 与 encoding 所需长度变化,产生连锁反应,更新操作最坏时间为 O(N2)
quicklist

在较早版本的 redis 中,list 有两种底层实现:

  • 当列表对象中元素的长度比较小或者数量比较少的时候,采用压缩列表 ziplist 来存储
  • 当列表对象中元素的长度比较大或者数量比较多的时候,则会转而使用双向列表 linkedlist 来存储

两者各有优缺点:

  • ziplist 的优点是内存紧凑,访问效率高,缺点是更新效率低,并且数据量较大时,可能导致大量的内存复制
  • linkedlist 的优点是节点修改的效率高,但是需要额外的内存开销,并且节点较多时,会产生大量的内存碎片.

为了结合两者的优点,在 redis 3.2 之后,list 的底层实现变为快速列表 quicklist。
快速列表是 linkedlist 与 ziplist 的结合: quicklist 包含多个内存不连续的节点,但每个节点本身就是一个 ziplist。

typedef struct quicklistNode {
    struct quicklistNode *prev;  // 上一个 ziplist 
    struct quicklistNode *next;  // 下一个 ziplist 
    unsigned char *zl;           // 数据指针,指向 ziplist 结构,或者 quicklistLZF 结构
    unsigned int sz;             // ziplist 占用内存长度(未压缩)
    unsigned int count : 16;     // ziplist 记录数量
    unsigned int encoding : 2;   // 编码方式,1 表示 ziplist ,2 表示 quicklistLZF
    unsigned int container : 2;  // 
    unsigned int recompress : 1;         // 临时解压,1 表示该节点临时解压用于访问
    unsigned int attempted_compress : 1; // 测试字段
    unsigned int extra : 10;             // 预留空间
} quicklistNode;

typedef struct quicklistLZF {
    unsigned int sz;    // 压缩数据长度
    char compressed[];  // 压缩数据
} quicklistLZF;

typedef struct quicklist {
    quicklistNode *head;  // 列表头部
    quicklistNode *tail;  // 列表尾部
    unsigned long count;  // 记录总数
    unsigned long len;    // ziplist 数量
    int fill : 16; // ziplist 长度限制,每个 ziplist 节点的长度(记录数量/内存占用)不能超过这个值
    unsigned int compress : 16; // 压缩深度,表示 quicklist 两端不压缩的 ziplist 节点的个数,为 0 表示所有 ziplist 节点都不压缩
} quicklist;

该数据结构有以下特征:

  • 无缝切换:结合了 linkedlist 与 ziplist 的优点,无需在两种结构之间进行切换
  • 中间压缩:作为队列使用的场景下,list 中间的数据被访问的频率比较低,可以选择进行压缩以减少内存占用。
3、哈希(hash)

hash 类型是 Redis 常用数据类型之一,其底层存储结构有两种实现方式。

当存储的数据量较少的时,hash 采用 ziplist 作为底层存储结构,此时要求符合以下两个条件:

  • 哈希对象保存的所有键值对(键和值)的字符串长度总和小于 64 个字节。
  • 哈希对象保存的键值对数量要小于 512 个。

当无法满足上述条件时,hash 就会采用 dict(字典结构)来存储数据,数据结构如下:

typedef struct dictEntry {
    void* key;  // 键
    union {     // 值,可以为指针、有符号长整,无符号长整,双精度浮点
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

typedef struct dictht {
    dictEntry **table;      // 哈希表数组,数组中的每个元素是一个单向链表
    unsigned long size;     // 哈希表数组大小
    unsigned long sizemask; // 哈希掩码,用于计算索引
    unsigned long used;     // 已有节点数量
} dictht;

typedef struct dictType {
    unsigned int (*hashFunction) (const void *key);             // 哈希函数,用于计算哈希值
    int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 键比较函数
    void *(*keyDup)(void *privdata, const void *key);           // 键复制函数
    void *(*valDup)(void *privdata, const void *obj);           // 值复制函数
    void *(*keyDestructor)(void *privdata, const void *key);    // 键销毁函数
    void *(*valDestructor)(void *privdata, const void *obj);    // 值销毁函数
} dictType;

typedef struct dict {
    dictType *type;     // 类型函数,用于实现多态
    void *privdata;     // 私有数据,用于实现多态
    dictht ht[2];       // 哈希表,字典使用 ht[0] 作为哈希表,ht[1] 用于进行 rehash
    int rehashidx;      // rehash索引,当没有执行 rehash 时,其值为 -1
} dict;

数据结构有以下特征:

  • 哈希算法:使用 murmurhash2 作为哈希函数,时间复杂度为O(1)
  • 冲突解决:使用链地址法解决冲突,新增元素会被放到表头,时间复杂度为O(1)
4、集合(sets)

Redis set 采用了两种方式相结合的底层存储结构,分别是 intset(整型数组)与 hash table(哈希表),当 set 存储的数据满足以下要求时,使用 intset 结构:

  • 集合内保存的所有成员都是整数值;
  • 集合内保存的成员数量不超过 512 个。

当不满足上述要求时,则使用 hash table 结构。

intset 的结构体定义如下:

typedf struct inset{
    uint32_t encoding;//指定编码方式,默认为INSET_ENC_INT16
    uint32_t length;//集合内成员的总个数
    int8_t contents[];//实际存储成员的数组,并且数组中的数值从小到大依次排列
}inset;
  • encoding:用来指定编码格式,共有三种,分别是 INTSET_ENC_INT16、INSET_ENC_INT32 和 INSET_ENC_INT64,它们对应不同的数值范围。Redis 为了尽可能地节省内存,它会根据插入数据的大小来选择不同的编码格式。
  • length:集合内成员的数量,记录 contents 数组中共有多少个成员。
  • contents:存储成员的数组,数组中的成员从小到大依次排列,且不允许重复。

有序整型集合,具有紧凑的存储空间,添加操作的时间复杂度为O(N)

5、有序集合(sorted sets)

有序集合(zset)同样使用了两种不同的存储结构,分别是 zipList(压缩列表)和 skipList(跳跃列表),当 zset 满足以下条件时使用压缩列表:

  • 成员的数量小于128 个;
  • 每个 member (成员)的字符串长度都小于 64 个字节。

当有序结合不满足使用压缩列表的条件时,就会使用 skipList 结构来存储数据。

跳跃列表(skipList)又称“跳表”是一种基于链表实现的随机化数据结构,其插入、删除、查找的时间复杂度均为 O(logN)。从名字可以看出“跳跃列表”,并不同于一般的普通链表,它的结构较为复杂,本节只对它做浅显的介绍,如有兴趣可自行研究。

在 Redis 中一个 skipList 节点最高可以达到 64 层,一个“跳表”中最多可以存储 2^64 个元素,每个节点都是一个 skiplistNode(跳表节点)。skipList 的结构体定义如下:

typedf struct zskiplist{
    //头节点
    struct zskiplistNode *header;
    //尾节点
    struct zskiplistNode *tail;
    // 跳表中的元素个数
    unsigned long length;
    //表内节点的最大层数
    int level;
}zskiplist;
  • header:指向 skiplist 的头节点指针,通过它可以直接找到跳表的头节点,时间复杂度为 O(1);
  • tail:指向 skiplist 的尾节点指针,通过它可以直接找到跳表的尾节点,时间复杂度为 O(1);
  • length:记录 skiplist 的长度,也就跳表中有多少个元素,但不包括头节点;
  • level:记录当前跳表内所有节点中的最大层数(level);

跳跃列表的每一层都是一个有序的链表,链表中每个节点都包含两个指针,一个指向同一层的下了一个节点,另一个指向下一层的同一个节点。最低层的链表将包含 zset 中的所有元素。如果说一个元素出现在了某一层,那么低于该层的所有层都将包含这个元素,也就说高层是底层的子集。

该数据结构有以下特征:

  • 查找:平均查找时间为O(logN),最坏查找时间为O(N),并且支持范围查找
  • 概率:每次创建节点的时候,程序根据幂次定律随机生成一个 1 至 32 之间的随机数,用于决定层高
  • 排位:在查找节点的过程中,沿途访问过所有的跨度 span 累计起来,得到目标节点在表中的排位


这篇关于面试题】Redis常用数据类型,以及底层实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程