转载部分

Redis(一)-底层数据结构

2020-11-25  本文已影响0人  进击的蚂蚁zzzliu

概述

本节主要分析Redis key-value及5大基本数据类型背后对应的具体数据结构，只有了解了底层数据结构才能真正做到灵活掌握基本数据类型的使用

1. 全局哈希表

全局哈希表用于存储所有的键值对，结构类似HashMap，由哈希桶数组 + entry链表组成


Redis全局哈希表.png

1.1 哈希桶数组

--结构定义
typedef struct dictht {  
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

1.2 dictEntry

--结构定义
typedef struct dictEntry {  
    void *key;  
    void *val;  
    struct dictEntry *next;  
} dictEntry;

1.3 RedisObject

--结构定义
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:REDIS_LRU_BITS; 
    int refcount;
    void *ptr;
} robj;

1.4 哈希冲突的处理

类比HashMap很容易想到全局哈希表这种结构的两个问题

1.4.1 哈希冲突怎么办？

通常处理哈希冲突的方法有拉链法和链表法，通过全局哈希表结构能看出Redis使用链表法

1.4.2 数组扩容怎么办？

哈希表保存的键值对逐渐地增多， dictEntry链表长度就会越来越长，导致查询变慢，就需要进行扩容；为了使rehash操作更高效，避免同时复制大量数据，Redis默认使用两个全局哈希表 + 渐进式rehash进行操作

2. int/embstr/raw

  1. 当保存64位有符号整数时，String类型会把它保存为一个8字节的Long类型整数，即int编码方式；
  2. 当保存的数据中包含字符时，String类型就会用简单动态字符串SDS结构体来保存，对应embstr或raw编码
  3. 当字符串比较短(小于44字节)时，RedisObject中的元数据(type/encoding/lru/refcount)、指针(ptr)和SDS是一块连续的内存区域，这样就可以避免内存碎片，即embstr编码
  4. 当字符串比较大(大于44字节)时，SDS的数据量就开始变多了，Redis会给SDS分配独立的空间，并用指针指向SDS结构，即raw编码
--SDS结构定义
struct sdshdr {
    int len; 
    int alloc;
    char buf[]; 
};

buf：字节数组，保存实际数据。为了表示字节数组的结束，Redis会自动在数组最后加一个“\0”，这就会额外占用1个字节的开销
len：占4个字节，表示buf的已用长度
alloc：也占个4字节，表示buf的实际分配长度，一般大于len

String编码 (1).png

3. linkedlist/ziplist/quicklist

Redis3.2之前，列表对象其底层存储结构可以有两种，即：linkedlist和ziplist，而在Redis 3.2之后，列表对象底层存储结构优化成为了另一种:quicklist。而quicklist可以认为是linkedlist和ziplist的结合体

3.1 linkedlist

linkedlist是一个双向列表，每个节点都会存储指向上一个节点和指向下一个节点的指针。linkedlist因为每个节点的空间是不连续的，所以可能会造成过多的空间碎片


redis-linkedlist.png 
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;

typedef struct listNode {
    struct listNode *prev;//前一个节点
    struct listNode *next;//后一个节点
    void *value;//值(字符串对象)
} listNode;

3.2 ziplist

ziplist是为了节省内存而开发的一种压缩列表数据结构，由一系列连续内存块组成的顺序型数据结构；ziplist和linkedlist最大的区别是ziplist不存储指向上一个节点和下一个节点的指针，存储的是上一个节点的长度和当前节点的长度，牺牲了部分读写性能来换取更高的内存利用率，是一种时间换空间的思想


redis-ziplist.png 
--entry使用时需要序列化成zlentry再使用
typedef struct zlentry {
    unsigned int prevrawlensize; /* 内存中编码后的prevrawlen用了多少字节 */
    unsigned int prevrawlen;     /* 前一个entry占用的长度，主要是为了entry之间跳转 */
    unsigned int lensize;        /* 内存中编码后的len用了多少字节 */
    unsigned int len;            /* 当前entry的长度，如果是string则表示string的长度，如果是整数，则len依赖于具体数值大小。*/
    unsigned int headersize;     /* prevrawlensize + lensize. entry的head部分用了多少字节 */
    unsigned char encoding;      /* 当前entry的编码格式 */
    unsigned char *p;            /* 指向数据域的指针 */
} zlentry;

3.3 quicklist

3.2之后引入的，统一用quicklist来存储列表对象，可以理解成是一种混合结构,quicklist 是 ziplist 和 linkedlist 的混合体，它将 linkedlist 按段切分，每一段使用 ziplist 来紧凑存储，多个 ziplist 之间使用双向指针串接起来。这样既满足了快速的插入删除性能，又不会出现太大的空间冗余


redis-quicklist.png 
typedef struct quicklist {
    quicklistNode *head;//列表头节点
    quicklistNode *tail;//列表尾节点
    unsigned long count;//ziplist中一共存储了多少元素，即:每一个quicklistNode内的count相加
    unsigned long len; //双向链表的长度，即quicklistNode的数量
    int fill : 16;//填充因子
    unsigned int compress : 16;//压缩深度 0-不压缩
} quicklist;

typedef struct quicklistNode {
    struct quicklistNode *prev;//前一个节点
    struct quicklistNode *next;//后一个节点
    unsigned char *zl;//当前指向的ziplist或者quicklistLZF
    unsigned int sz;//当前ziplist占用字节
    unsigned int count : 16;//ziplist中存储的元素个数，16字节(最大65535个)
    unsigned int encoding : 2; //是否采用了LZF压缩算法压缩节点 1：RAW 2:LZF
    unsigned int container : 2; //存储结构，NONE=1, ZIPLIST=2
    unsigned int recompress : 1; //当前ziplist是否需要再次压缩(如果前面被解压过则为true，表示需要再次被压缩)
    unsigned int attempted_compress : 1;//测试用 
    unsigned int extra : 10; //后期留用
} quicklistNode;

4. intset

当一个集合只包含整数值元素， 并且这个集合的元素数量不多时， Redis 就会使用整数集合作为集合键的底层实现，来节约内存；但是由于是连续空间，修改效率不高


redis-intset.png 
typedef struct intset {
    uint32_t encoding;   // 编码方式
    uint32_t length;     // 集合包含的元素数量
    int8_t contents[];   // 保存元素的数组，从小到大排序，无重复
} intset;

encoding记录了当前集合的编码方式，主要有三种：

5. hashtable

hashtable用来存储key-value格式数据，数据结构类似java种hashmap和全局哈希表


redis-hashtable.png 
/* 字典 */
typedef struct dict {
    dictType *type;      // 类型特定函数
    void *privdata;      // 私有数据
    dictht ht[2];        // 哈希表，注意这里是两个哈希表
    int rehashidx;       // rehash 索引，当 rehash 不在进行时，值为 -1
    int iterators;       // 目前正在运行的安全迭代器的数量
} dict;

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

/* 字典entry */
typedef struct dictEntry {  
    void *key;              //指向基本对象结构RedisObject(key都是字符串对象)的指针
    void *val;              //指向基本对象结构RedisObject的指针，val可以是String/List/Set/ZSet/Hash
    struct dictEntry *next; //指向链表中下一个dictEntry指针
} dictEntry;

6. skiplist

有序链表只能逐一查找元素，导致操作起来非常缓慢，于是就出现了跳表。跳表在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位。大部分情况下，跳跃表的效率可以等同于平衡树，但是跳跃表的实现却远远比平衡树的实现简单，所以Redis选择了使用跳跃表来实现有序集合;


redis-skiplist.png 
/* 有序集合 */
typedef struct zset {
    dict *dict;       // 字典，键为成员，值为分值， 用于支持 O(1) 复杂度的按成员取分值操作
    zskiplist *zsl;   // 跳跃表，按分值排序成员，用于支持平均复杂度为 O(log N) 的按分值定位成员操作， 以及范围操作
} zset;

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

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

小结

本文主要分析了redis底层用到的各种数据结构。redis是用 C 编写，本文列举的typedef struct可以类比java中实体对象，理解起来还是比较容易的
---------over---------

上一篇 下一篇

猜你喜欢

热点阅读