Redis中的数据结构与对象

2019-01-29  本文已影响8人  mecury

最近读了《Redis 设计与实现》，知道了Redis在存储对象中做了很多的优化，利用各种不同的存储结构实现, 减少了内存消耗，加快了增删改查的速度。这里做一下记录，方便查看。

[TOC]

1. Redis对象的类型

Redis 支持五种类型的对象，在内部由一个 redisObeject 对象表示，数据定义如下：

typedef struct redisObject {
    unsigned type:4;  //对象类型
    unsigned encoding:4;  //对象的编码，即存储类型
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    int refcount;
    void *ptr;  //对象的位置指针
} robj;
  1. type 对应 Redis 中的五种基本数据类型：
类型常量 对象的名称
REDIS_STRING 字符串对象
REDIS_LIST 列表对象
REDIS_HASH 哈希对象
REDIS_SET 集合对象
REDIS_ZSET 有序集合对象
  1. Encoding对应的编码:
编码常量 编码所对应的底层数据结构
REDIS_ENCODING_INT long 类型的整数
REDIS_ENCODING_EMBSTR embstr 编码的简单动态字符串
REDIS_ENCODING_RAW 简单动态字符串
REDIS_ENCODING_HT 字典
REDIS_ENCODING_LINKEDLIST 双端链表
REDIS_ENCODING_ZIPLIST 压缩列表
REDIS_ENCODING_INTSET 整数集合
REDIS_ENCODING_SKIPLIST 跳跃表和字典
  1. type 与 Encoding 的对应关系
类型 编码 对象
REDIS_STRING REDIS_ENCODING_INT 使用整数值实现的字符串对象。
REDIS_STRING REDIS_ENCODING_EMBSTR 使用 embstr 编码的简单动态字符串实现的字符串对象。
REDIS_STRING REDIS_ENCODING_RAW 使用简单动态字符串实现的字符串对象。
REDIS_LIST REDIS_ENCODING_ZIPLIST 使用压缩列表实现的列表对象。
REDIS_LIST REDIS_ENCODING_LINKEDLIST 使用双端链表实现的列表对象。
REDIS_HASH REDIS_ENCODING_ZIPLIST 使用压缩列表实现的哈希对象。
REDIS_HASH REDIS_ENCODING_HT 使用字典实现的哈希对象。
REDIS_SET REDIS_ENCODING_INTSET 使用整数集合实现的集合对象。
REDIS_SET REDIS_ENCODING_HT 使用字典实现的集合对象。
REDIS_ZSET REDIS_ENCODING_ZIPLIST 使用压缩列表实现的有序集合对象。
REDIS_ZSET REDIS_ENCODING_SKIPLIST 使用跳跃表和字典实现的有序集合对象。

2. 对象存储中的编码Encoding简单解释

2.1REDIS_STRING 类型的编码

如上面 type 与 Encoding 对应关系表所说。 String 类型根据不同的情况使用三种不同的编码格式进行存储：REDIS_ENCODING_INT,REDIS_ENCODING_EMBSTR,REDIS_ENCODING_RAW.下面介绍一下它们的异同，以及使用的优缺点：

REDIS_ENCODING_INT

Redis String int

使用条件： 整数集合intset是 Redis 用户保存整数值的集合抽象数据结构，它不会出现重复值。当一个集合只包含整数元素时，并且这个集合的元素数量不多时，Redis 会使用整数集合作为集合键的底层实现。
说明： intset.h/intset

typedef struct intset {
    // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];
} intset;

encoding：这里的encoding指定了 contents 数组代表的格式。可以指定为：

INTSET_ENC_INT16: 指定contents数组的格式为 int16_t 类型
INTSET_ENC_INT32: 指定contents数组的格式为 int32_t 类型
INTSET_ENC_INT64: 指定contents数组的格式为 int64_t 类型

image

整数集合的升级：

当一个新的整数元素被加入到数组中时，如果它的位数比指定的 encoding 位数大，那么集合需要进行升级，然后才能将元素添加到整数集合中去。另外，Redis 整数集合中的元素只能升级，而不支持降级。另外整数集合在使用时，里面的元素会自动排序。

函数 作用 时间复杂度
insertAdd 在集合中添加一个元素 O(N)
insertRemove 在集合中删除一个元素 O(N)
insertFind 检查给定值是否存在与集合 O(logN)
insertGet 获取给定值是否存在与集合 O(1)
insertLen 获取集合的长度 O(1)
insertBlobLen 获取集合占用的内存字节数 O(1)
REDIS_ENCODING_EMBSTR
REDIS_ENCODING_RAW

Redis String Embstr Raw

REDIS_ENCODING_EMBSTR 与 REDIS_ENCODING_RAW都是是SDS Simple Dynamic String 类型的，底层实现是一样的，这里先看下原理：

struct sdshdr {

    // 记录 buf 数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    int len;
    // 记录 buf 数组中未使用字节的数量
    int free;
    // 字节数组，用于保存字符串
    char buf[];
};
image

减少修改字符串时带来的内存重分配次数

REDIS_ENCODING_EMBSTR 与 REDIS_ENCODING_RAW 的区别：

embstr 编码是专门用于保存短字符串的一种优化编码方法，这种编码和 raw编码一样，都使用redisObject结构 和 sdshdr 结构来表示字符串对象，但 raw编码会调用两次内存分配函数来分别创建redisObject结构与sdshdr结构，而embstr编码则通过调用一次内存分配函数来分配一块连续的内存空间，空间中依次包含redisObject 和 sdshdr 两个结构

2.2 REDIS_LIST 类型的编码
REDIS_ENCODING_ZIPLIST

Redis ZipList 压缩表

REDIS_ENCODING_LINKEDLIST

Redis中的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);
    // 节点值对比函数
    int (*match)(void *ptr, void *key);

} list;
image

特点：

2.3 REDIS_HASH 类型的编码
REDIS_ENCODING_ZIPLIST
REDIS_ENCODING_HT

Redis HT（hash table）

字典的哈希表：

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

哈希表节点：

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

字典：

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

上图是 Redis 字典中的哈希表, Redis 中的字典是由容量为2的哈希表数组组成。 一般情况下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。

image
2.4 REDIS_SET 类型的编码
REDIS_ENCODING_INTSET
REDIS_ENCODING_HT
2.5 REDIS_ZSET 类型的编码
REDIS_ENCODING_ZIPLIST

Redis ZipList 压缩表

ZipList节点的组成：

image

压缩列表中的结构：

image

考虑这样一种情况：

image

压缩表的特点：

缺点：

REDIS_ENCODING_SKIPLIST

Redis SkipList 跳跃表

跳跃表节点的实现是通过 redis.h/zskiplistNode 实现的：

typedef struct zskiplistNode {
    // 后退指针
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成员对象
    robj *obj;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];

} zskiplistNode;

跳跃表：

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

Redis中的的跳跃表包含以下结构：

跳跃表节点，跳跃表节点Redis中的定义在上面：

这里简单说下跳跃表：

漫画算法：什么是跳跃表？

浅析SkipList跳跃表原理及代码实现

  1. 跳跃表的层次生成
    每个层次的节点由上一层的节点中产生，产生的方法，应该是对上一层的节点进行随机，随机决定当前节点是否需要显示在下一层。上面说因为跳跃表删除和添加的节点是不可预测的，很难使用一种有效的算法保证跳表的索引部分。

  2. 跳跃表的查询

    • 查询由最高层开始，当查找到当前节点比查找节点大的时候，进行回退上一个节点

    • 回退到上一个节点后，level层次减少，由下一层的当前节点开始查找

  3. 跳跃表的节点增加

    • 节点的增加，需要先查找到插入节点应该插入的位置
    • 然后决定该节点是否入选每个层次的节点中，构建节点在跳跃表需要显示的层次中

  4. 跳跃表的节点删除

    • 节点的删除也是需要先查找到删除节点所在的位置
    • 除了删除当前的节点，还需要删除层次中所有的该节点

3. 对象对于存储结构的选择

上面介绍了一些 Redis 存储结构的一些基本概念，对于 Redis 而言，每种 Type 类型都有超过两种类型可以进行选择，那到底什么时候使用什么对象呢？这里对于 《Redis 设计与实现》所述做一些总结。这里先看下每种对象可以选择的数据存储结构。

类型 编码 对象
REDIS_STRING REDIS_ENCODING_INT 使用整数值实现的字符串对象。
REDIS_STRING REDIS_ENCODING_EMBSTR 使用 embstr 编码的简单动态字符串实现的字符串对象。
REDIS_STRING REDIS_ENCODING_RAW 使用简单动态字符串实现的字符串对象。
REDIS_LIST REDIS_ENCODING_ZIPLIST 使用压缩列表实现的列表对象。
REDIS_LIST REDIS_ENCODING_LINKEDLIST 使用双端链表实现的列表对象。
REDIS_HASH REDIS_ENCODING_ZIPLIST 使用压缩列表实现的哈希对象。
REDIS_HASH REDIS_ENCODING_HT 使用字典实现的哈希对象。
REDIS_SET REDIS_ENCODING_INTSET 使用整数集合实现的集合对象。
REDIS_SET REDIS_ENCODING_HT 使用字典实现的集合对象。
REDIS_ZSET REDIS_ENCODING_ZIPLIST 使用压缩列表实现的有序集合对象。
REDIS_ZSET REDIS_ENCODING_SKIPLIST 使用跳跃表和字典实现的有序集合对象。
编码 编码转换条件
int 保存的字符串对象是整数值，并且这个整数值可以使用long 进行表示
Raw 字符串对象保存的是一个字符串值，并且这个字符串值的长度大于39字节，那么字符串对象将使用一个SDS保存，并设置为
embstr 字符串对象保存的是一个字符串值，并且这个字符串值的长度小于等于 39 字节
编码 编码转换条件
ZipList 1. 列表对象保存的所有字符串元素的长度都小于 64 字节；
2. 列表对象保存的元素数量小于 512 个；
LinkedList 同上相反
编码 编码转换条件
ZipList 1. 列表对象保存的所有字符串元素的长度都小于 64 字节；
2. 列表对象保存的元素数量小于 512 个；
HashTable 同上相反
编码 编码转换条件
IntSet 1. 列表对象保存的所有字符串元素都是整数值；
2. 列表对象保存的元素数量小于 512 个；
HashTable 同上相反
编码 编码转换条件
ZipList 1. 列表对象保存的所有字符串元素的长度都小于 64 字节；
2. 有序集合保存的元素数量小于 128 个；
SkipList 同上相反

参考：
1. <<Redis 设计与实现>>
2. 漫画算法：什么是跳跃表？
3. 浅析SkipList跳跃表原理及代码实现

上一篇下一篇

猜你喜欢

热点阅读