《Redis设计与实现》底层数据结构

2019-09-0706:03:30数据结构与算法Comments2,121 views字数 10372阅读模式

Redis的数据结构,我们大概会很快想到Redis的5种常见数据结构:字符串(String)、列表(List)、散列(Hash)、集合(Set)、有序集合(Sorted Set),以及他们的特点和运用场景。不过它们是Redis对外暴露的数据结构,用于API的操作,而组成它们的底层基础数据结构又是什么呢文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

  • 简单动态字符串(SDS)
  • 链表
  • 字典
  • 跳跃表
  • 整数集合
  • 压缩列表

简单动态字符串(SDS)

Redis是用C语言写的,但是Redis并没有使用C的字符串表示(C是字符串是以\0空字符结尾的字符数组),而是自己构建了一种简单动态字符串(simple dynamic string,SDS)的抽象类型,并作为Redis的默认字符串表示文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

在Redis中,包含字符串值的键值对底层都是用SDS实现的文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

SDS的定义

SDS的结构定义在sds.h文件中,SDS的定义在Redis 3.2版本之后有一些改变,由一种数据结构变成了5种数据结构,会根据SDS存储的内容长度来选择不同的结构,以达到节省内存的效果,具体的结构定义,我们看以下代码文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

// 3.0
struct sdshdr {
    // 记录buf数组中已使用字节的数量,即SDS所保存字符串的长度
    unsigned int len;
    // 记录buf数据中未使用的字节数量
    unsigned int free;
    // 字节数组,用于保存字符串
    char buf[];
};

// 3.2
/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
复制代码

3.2版本之后,会根据字符串的长度来选择对应的数据结构文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5)  // 32
        return SDS_TYPE_5;
    if (string_size < 1<<8)  // 256
        return SDS_TYPE_8;
    if (string_size < 1<<16)   // 65536 64k
        return SDS_TYPE_16;
    if (string_size < 1ll<<32)  // 4294967296 4G
        return SDS_TYPE_32;
    return SDS_TYPE_64;
}
复制代码

下面以3.2版本的sdshdr8看一个示例文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

《Redis设计与实现》底层数据结构
  • len:记录当前已使用的字节数(不包括'\0'),获取SDS长度的复杂度为O(1)
  • alloc:记录当前字节数组总共分配的字节数量(不包括'\0'
  • flags:标记当前字节数组的属性,是sdshdr8还是sdshdr16等,flags值的定义可以看下面代码
  • buf:字节数组,用于保存字符串,包括结尾空白字符'\0'
// flags值定义
#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4
复制代码

上面的字节数组的空白处表示未使用空间,是Redis优化的空间策略,给字符串的操作留有余地,保证安全提高效率文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

SDS与C字符串的区别

C语言使用长度为N+1的字符数组来表示长度为N的字符串,字符数组的最后一个元素为空字符'\0',但是这种简单的字符串表示方法并不能满足Redis对于字符串在安全性、效率以及功能方面的要求,那么使用SDS,会有哪些好处呢文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

参考于《Redis设计与实现》文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

常数复杂度获取字符串长度文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

C字符串不记录字符串长度,获取长度必须遍历整个字符串,复杂度为O(N);而SDS结构中本身就有记录字符串长度的len属性,所有复杂度为O(1)。Redis将获取字符串长度所需的复杂度从O(N)降到了O(1),确保获取字符串长度的工作不会成为Redis的性能瓶颈文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

杜绝缓冲区溢出,减少修改字符串时带来的内存重分配次数文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

C字符串不记录自身的长度,每次增长或缩短一个字符串,都要对底层的字符数组进行一次内存重分配操作。如果是拼接append操作之前没有通过内存重分配来扩展底层数据的空间大小,就会产生缓存区溢出;如果是截断trim操作之后没有通过内存重分配来释放不再使用的空间,就会产生内存泄漏文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

而SDS通过未使用空间解除了字符串长度和底层数据长度的关联,3.0版本是用free属性记录未使用空间,3.2版本则是alloc属性记录总的分配字节数量。通过未使用空间,SDS实现了空间预分配惰性空间释放两种优化的空间分配策略,解决了字符串拼接和截取的空间问题文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

二进制安全文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

C字符串中的字符必须符合某种编码,除了字符串的末尾,字符串里面是不能包含空字符的,否则会被认为是字符串结尾,这些限制了C字符串只能保存文本数据,而不能保存像图片这样的二进制数据文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

而SDS的API都会以处理二进制的方式来处理存放在buf数组里的数据,不会对里面的数据做任何的限制。SDS使用len属性的值来判断字符串是否结束,而不是空字符文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

兼容部分C字符串函数文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

虽然SDS的API是二进制安全的,但还是像C字符串一样以空字符结尾,目的是为了让保存文本数据的SDS可以重用一部分C字符串的函数文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

C字符串与SDS对比文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

C字符串SDS
获取字符串长度复杂度为O(N)获取字符串长度复杂度为O(1)
API是不安全的,可能会造成缓冲区溢出API是安全的,不会造成缓冲区溢出
修改字符串长度必然会需要执行内存重分配修改字符串长度N次最多会需要执行N次内存重分配
只能保存文本数据可以保存文本或二进制数据
可以使用所有<string.h>库中的函数可以使用一部分<string.h>库中的函数

链表

链表是一种比较常见的数据结构了,特点是易于插入和删除、内存利用率高、且可以灵活调整链表长度,但随机访问困难。许多高级编程语言都内置了链表的实现,但是C语言并没有实现链表,所以Redis实现了自己的链表数据结构文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

链表在Redis中应用的非常广,列表(List)的底层实现就是链表。此外,Redis的发布与订阅、慢查询、监视器等功能也用到了链表文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

链表节点和链表的定义

链表上的节点定义如下,adlist.h/listNode文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点值
    void *value;
} listNode;
复制代码

链表的定义如下,adlist.h/list文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

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

每个节点listNode可以通过prevnext指针分布指向前一个节点和后一个节点组成双端链表,同时每个链表还会有一个list结构为链表提供表头指针head、表尾指针tail、以及链表长度计数器len,还有三个用于实现多态链表的类型特定函数文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

  • dup:用于复制链表节点所保存的值
  • free:用于释放链表节点所保存的值
  • match:用于对比链表节点所保存的值和另一个输入值是否相等

链表结构图文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

《Redis设计与实现》底层数据结构

链表特性

  • 双端链表:带有指向前置节点和后置节点的指针,获取这两个节点的复杂度为O(1)
  • 无环:表头节点的prev和表尾节点的next都指向NULL,对链表的访问以NULL结束
  • 链表长度计数器:带有len属性,获取链表长度的复杂度为O(1)
  • 多态:链表节点使用 void*指针保存节点值,可以保存不同类型的值

字典

字典,又称为符号表(symbol table)、关联数组(associative array)或映射(map),是一种用于保存键值对(key-value pair)的抽象数据结构。字典中的每一个键都是唯一的,可以通过键查找与之关联的值,并对其修改或删除文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

Redis的键值对存储就是用字典实现的,散列(Hash)的底层实现之一也是字典文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

我们直接来看一下字典是如何定义和实现的吧文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

字典的定义实现

Redis的字典底层是使用哈希表实现的,一个哈希表里面可以有多个哈希表节点,每个哈希表节点中保存了字典中的一个键值对文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

哈希表结构定义,dict.h/dictht文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码,用于计算索引值,等于size-1
    unsigned long sizemask;
    // 哈希表已有节点的数量
    unsigned long used;
} dictht;
复制代码

哈希表是由数组table组成,table中每个元素都是指向dict.h/dictEntry结构的指针,哈希表节点的定义如下文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

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

其中key是我们的键;v是键值,可以是一个指针,也可以是整数或浮点数;next属性是指向下一个哈希表节点的指针,可以让多个哈希值相同的键值对形成链表,解决键冲突问题文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

最后就是我们的字典结构,dict.h/dict文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

typedef struct dict {
    // 和类型相关的处理函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引,当rehash不再进行时,值为-1
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 迭代器数量
    unsigned long iterators; /* number of iterators currently running */
} dict;
复制代码

type属性和privdata属性是针对不同类型的键值对,用于创建多类型的字典,type是指向dictType结构的指针,privdata则保存需要传给类型特定函数的可选参数,关于dictType结构和类型特定函数可以看下面代码文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

typedef struct dictType {
    // 计算哈希值的行数
    uint64_t (*hashFunction)(const void *key);
    // 复制键的函数
    void *(*keyDup)(void *privdata, const void *key);
    // 复制值的函数
    void *(*valDup)(void *privdata, const void *obj);
    // 对比键的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    // 销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);
    // 销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);
} dictType;
复制代码

dictht属性是两个元素的数组,包含两个dictht哈希表,一般字典只使用ht[0]哈希表,``ht[1]哈希表会在对ht[0]哈希表进行rehash(重哈希)的时候使用,即当哈希表的键值对数量超过负载数量过多的时候,会将键值对迁移到ht[1]`上文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

rehashidx也是跟rehash相关的,rehash的操作不是瞬间完成的,rehashidx记录着rehash的进度,如果目前没有在进行rehash,它的值为-1文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

结合上面的几个结构,我们来看一下字典的结构图(没有在进行rehash)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

《Redis设计与实现》底层数据结构

在这里,哈希算法和rehash(重新散列)的操作不再详细说明,有机会以后单独介绍文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

当一个新的键值对要添加到字典中时,会根据键值对的键计算出哈希值和索引值,根据索引值放到对应的哈希表上,即如果索引值为0,则放到ht[0]哈希表上。当有两个或多个的键分配到了哈希表数组上的同一个索引时,就发生了键冲突的问题,哈希表使用链地址法来解决,即使用哈希表节点的next指针,将同一个索引上的多个节点连接起来。当哈希表的键值对太多或太少,就需要对哈希表进行扩展和收缩,通过rehash(重新散列)来执行文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

跳跃表

一个普通的单链表查询一个元素的时间复杂度为O(N),即便该单链表是有序的。使用跳跃表(SkipList)是来解决查找问题的,它是一种有序的数据结构,不属于平衡树结构,也不属于Hash结构,它通过在每个节点维持多个指向其他节点的指针,而达到快速访问节点的目的文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

跳跃表是有序集合(Sorted Set)的底层实现之一,如果有序集合包含的元素比较多,或者元素的成员是比较长的字符串时,Redis会使用跳跃表做有序集合的底层实现文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

跳跃表的定义

跳跃表其实可以把它理解为多层的链表,它有如下的性质文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

  • 多层的结构组成,每层是一个有序的链表
  • 最底层(level 1)的链表包含所有的元素
  • 跳跃表的查找次数近似于层数,时间复杂度为O(logn),插入、删除也为 O(logn)
  • 跳跃表是一种随机化的数据结构(通过抛硬币来决定层数)

那么如何来理解跳跃表呢,我们从最底层的包含所有元素的链表开始,给定如下的链表文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

《Redis设计与实现》底层数据结构

然后我们每隔一个元素,把它放到上一层的链表当中,这里我把它叫做上浮(注意,科学的办法是抛硬币的方式,来决定元素是否上浮到上一层链表,我这里先简单每隔一个元素上浮到上一层链表,便于理解),操作完成之后的结构如下文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

《Redis设计与实现》底层数据结构

查找元素的方法是这样,从上层开始查找,大数向右找到头,小数向左找到头,例如我要查找17,查询的顺序是:13 -> 46 -> 22 -> 17;如果是查找35,则是 13 -> 46 -> 22 -> 46 -> 35;如果是54,则是 13 -> 46 -> 54文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

《Redis设计与实现》底层数据结构

上面是查找元素,如果是添加元素,是通过抛硬币的方式来决定该元素会出现到多少层,也就是说它会有 1/2的概率出现第二层、1/4 的概率出现在第三层......文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

跳跃表节点的删除和添加都是不可预测的,很难保证跳表的索引是始终均匀的,抛硬币的方式可以让大体上是趋于均匀的文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

假设我们已经有了上述例子的一个跳跃表了,现在往里面添加一个元素18,通过抛硬币的方式来决定它会出现的层数,是正面就继续,反面就停止,假如我抛了2次硬币,第一次为正面,第二次为反面文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

《Redis设计与实现》底层数据结构

跳跃表的删除很简单,只要先找到要删除的节点,然后顺藤摸瓜删除每一层相同的节点就好了文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

跳跃表维持结构平衡的是比较低的,完全是依靠随机,相比二叉查找树,在多次插入删除后,需要Rebalance来重新调整结构平衡文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

跳跃表的实现

Redis的跳跃表实现是由redis.h/zskiplistNoderedis.h/zskiplist(3.2版本之后redis.h改为了server.h)两个结构定义,zskiplistNode定义跳跃表的节点,zskiplist保存跳跃表节点的相关信息文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    // 成员对象 (robj *obj;)
    sds ele;
    // 分值
    double score;
    // 后退指针
    struct zskiplistNode *backward;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度
        // 跨度实际上是用来计算元素排名(rank)的,在查找某个节点的过程中,将沿途访过的所有层的跨度累积起来,得到的结果就是目标节点在跳跃表中的排位
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    // 表中节点的数量
    unsigned long length;
    // 表中层数最大的节点的层数
    int level;
} zskiplist;
复制代码

zskiplistNode结构文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

  • level数组(层):每次创建一个新的跳表节点都会根据幂次定律计算出level数组的大小,也就是次层的高度,每一层带有两个属性-前进指针跨度,前进指针用于访问表尾方向的其他指针;跨度用于记录当前节点与前进指针所指节点的距离(指向的为NULL,阔度为0)
  • backward(后退指针):指向当前节点的前一个节点
  • score(分值):用来排序,如果分值相同看成员变量在字典序大小排序
  • objele:成员对象是一个指针,指向一个字符串对象,里面保存着一个sds;在跳表中各个节点的成员对象必须唯一,分值可以相同

zskiplist结构文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

  • headertail表头节点和表尾节点
  • length表中节点的数量
  • level表中层数最大的节点的层数

假设我们现在展示一个跳跃表,有四个节点,节点的高度分别是2、1、4、3文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

《Redis设计与实现》底层数据结构

zskiplist的头结点不是一个有效的节点,它有ZSKIPLIST_MAXLEVEL层(32层),每层的forward指向该层跳跃表的第一个节点,若没有则为NULL,在Redis中,上面的跳跃表结构如下文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

《Redis设计与实现》底层数据结构
  • 每个跳跃表节点的层数在1-32之间
  • 一个跳跃表中,节点按照分值大小排序,多个节点的分值是可以相同的,相同时,节点按成员对象大小排序
  • 每个节点的成员变量必须是唯一的

整数集合

整数集合(intset)是Redis用于保存整数值的集合抽象数据结构,可以保存类型为int16_t、int32_t、int64_t的整数值,并且保证集合中不会出现重复元素文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

整数集合是集合(Set)的底层实现之一,如果一个集合只包含整数值元素,且元素数量不多时,会使用整数集合作为底层实现文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

整数集合的定义实现

整数集合的定义为inset.h/inset文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

typedef struct intset {
    // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];
} intset;
复制代码
  • contents数组:整数集合的每个元素在数组中按值的大小从小到大排序,且不包含重复项
  • length记录整数集合的元素数量,即contents数组长度
  • encoding决定contents数组的真正类型,如INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64
《Redis设计与实现》底层数据结构

整数集合的升级

当想要添加一个新元素到整数集合中时,并且新元素的类型比整数集合现有的所有元素的类型都要长,整数集合需要先进行升级(upgrade),才能将新元素添加到整数集合里面。每次想整数集合中添加新元素都有可能会引起升级,每次升级都需要对底层数组已有的所有元素进行类型转换文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

升级添加新元素:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

  • 根据新元素类型,扩展整数集合底层数组的空间大小,并为新元素分配空间
  • 把数组现有的元素都转换成新元素的类型,并将转换后的元素放到正确的位置,且要保持数组的有序性
  • 添加新元素到底层数组

整数集合的升级策略可以提升整数集合的灵活性,并尽可能的节约内存文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

另外,整数集合不支持降级,一旦升级,编码就会一直保持升级后的状态文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

压缩列表

压缩列表(ziplist)是为了节约内存而设计的,是由一系列特殊编码的连续内存块组成的顺序性(sequential)数据结构,一个压缩列表可以包含多个节点,每个节点可以保存一个字节数组或者一个整数值文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

压缩列表是列表(List)和散列(Hash)的底层实现之一,一个列表只包含少量列表项,并且每个列表项是小整数值或比较短的字符串,会使用压缩列表作为底层实现(在3.2版本之后是使用quicklist实现)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

压缩列表的构成

一个压缩列表可以包含多个节点(entry),每个节点可以保存一个字节数组或者一个整数值文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

《Redis设计与实现》底层数据结构

各部分组成说明如下文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

  • zlbytes:记录整个压缩列表占用的内存字节数,在压缩列表内存重分配,或者计算zlend的位置时使用
  • zltail:记录压缩列表表尾节点距离压缩列表的起始地址有多少字节,通过该偏移量,可以不用遍历整个压缩列表就可以确定表尾节点的地址
  • zllen:记录压缩列表包含的节点数量,但该属性值小于UINT16_MAX(65535)时,该值就是压缩列表的节点数量,否则需要遍历整个压缩列表才能计算出真实的节点数量
  • entryX:压缩列表的节点
  • zlend:特殊值0xFF(十进制255),用于标记压缩列表的末端

压缩列表节点的构成

每个压缩列表节点可以保存一个字节数字或者一个整数值,结构如下文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

《Redis设计与实现》底层数据结构
  • previous_entry_ength:记录压缩列表前一个字节的长度
  • encoding:节点的encoding保存的是节点的content的内容类型
  • content:content区域用于保存节点的内容,节点内容类型和长度由encoding决定

对象

上面介绍了Redis的主要底层数据结构,包括简单动态字符串(SDS)、链表、字典、跳跃表、整数集合、压缩列表。但是Redis并没有直接使用这些数据结构来构建键值对数据库,而是基于这些数据结构创建了一个对象系统,也就是我们所熟知的可API操作的Redis那些数据类型,如字符串(String)、列表(List)、散列(Hash)、集合(Set)、有序集合(Sorted Set)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

根据对象的类型可以判断一个对象是否可以执行给定的命令,也可针对不同的使用场景,对象设置有多种不同的数据结构实现,从而优化对象在不同场景下的使用效率文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

类型编码BOJECT ENCODING 命令输出对象
REDIS_STRINGREDIS_ENCODING_INT"int"使用整数值实现的字符串对象
REDIS_STRINGREDIS_ENCODING_EMBSTR"embstr"使用embstr编码的简单动态字符串实现的字符串对象
REDIS_STRINGREDIS_ENCODING_RAW"raw"使用简单动态字符串实现的字符串对象
REDIS_LISTREDIS_ENCODING_ZIPLIST"ziplist"使用压缩列表实现的列表对象
REDIS_LISTREDIS_ENCODING_LINKEDLIST'"linkedlist'使用双端链表实现的列表对象
REDIS_HASHREDIS_ENCODING_ZIPLIST"ziplist"使用压缩列表实现的哈希对象
REDIS_HASHREDIS_ENCODING_HT"hashtable"使用字典实现的哈希对象
REDIS_SETREDIS_ENCODING_INTSET"intset"使用整数集合实现的集合对象
REDIS_SETREDIS_ENCODING_HT"hashtable"使用字典实现的集合对象
REDIS_ZSETREDIS_ENCODING_ZIPLIST"ziplist"使用压缩列表实现的有序集合对象
REDIS_ZSETREDIS_ENCODING_SKIPLIST"skiplist"使用跳跃表表实现的有序集合对象

参考:《Redis设计与实现》文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

作者:TurboSnail
链接:https://juejin.im/post/5d71d3bee51d453b5f1a04f1
来源:掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16150.html
  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/16150.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定