Redis对象类型和底层数据结构

Redis对象类型（类型常量：对象名称）

• REDIS_STRING： 字符串对象
• REDIS_LIST： 列表对象
• REDIS_HASH： 哈希对象
• REDIS_SET： 集合对象
• REDIS_ZSET： 有序集合对象

Redis对象的底层数据结构（编码常量：编码所对应的底层数据结构）

• 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：跳跃表和字典

一个Redis对象的结构

/*
 * Redis 对象
 */
typedef struct redisObject {
 
    // 类型
    unsigned type:4;        
 
    // 不使用(对齐位)
    unsigned notused:2;
 
    // 编码方式
    unsigned encoding:4;
 
    // LRU 时间（相对于 server.lruclock）
    unsigned lru:22;
 
    // 引用计数
    int refcount;
 
    // 指向对象的值
    void *ptr;
 
} robj;

先介绍Redis的数据结构

1.简单动态字符串SDS

• redis实现了一个SDS结构(简单动态字符串)类型来替代C语言中的原生字符串，结构如下：

struct sdshdr { 
    //记录buf中字符串的实际长度
    int len; 
    //记录buf数组空闲长度
    int free; 
    //字节数组,用于保存字符串 
    char buf[];
};

• SDS结构和C语言原生字符串类型相比有以下优点：
  　　1、因为存储了字符串长度,可以常数复杂度获取字符串长度。
  　　2、同样由于存储了字符串实际长度和buff空闲长度,字符串变化时不需要每次都重新分配内存, 同时也避免了字符串长度变化可能导致的缓冲区溢出和内存泄漏。
  　　3、二进制安全, SDS的设计由于根据字符串长度来判断字符串的末尾,因此中间可以存储任何数据包括空字符。
• embstr和raw都是SDS结构，相比于raw使用embstr编码redis对象好处：
  　　1、创建只需要分配一次内存，而使用raw编码则需要2次(一次为sds分配内存，另一次为object分配内存，embstr编码省去了第一次)。
  　　2、释放内存的次数也由2次变为1次。
  　　3、embstr编码对象的object和sds放在一起，更好的利用缓存带来的优势。

2.整数集合 INTSET

• 有序无重复的数组, 可以通过二分法进行查找操作。

3.Hash表 HT

• redis的hash算法是MurmurHash算法(这种算法优点在于，即使输入的键是有规律的，算法仍能给出一个很好的随机分布性，并且算法的计算速度也非常快), 处理冲突使用链地址法。随着操作不断进行,当hash表保存的键值对过多或过少时,需要对hash表的槽位数组进行扩展或收缩以获得更好的性能和内存利用率,这个操作称为rehash。redis中的rehash就是通过创建一个临时的字典,将正在使用的字典中的所有键值对复制到临时字典中(这个过程需要重新计算hash值和索引值,因此称为rehash),最后释放老的字典,并将其指针指向临时字典。当数据量比较小的时候,这个过程可以一次性完成，但是数据量大的时候,庞大的计算量可能导致整个服务停止,因此redis采用了渐进式rehash(写时复制),就是同时维护两个hash表hd[0]和hd[1],设置rehash_idx设置为0，在0< rehash_idx < 槽位数组长度时, 对hash表的任何操作除了执行正常的操作过程以外，还会将hd[0]槽位数组rehash_idx索引上的所有键值对rehash到hd[1],这个过程中的查找会同时使用两个表进行操作,同时所有的添加键值对操作只会在hd[1]上进行,保证了hd[0]只减不增。rehash完成后,hash表指针指向hd[1],释放hd[0]内存。

4.压缩列表 ZIPLIST

• 为节约内存开发，由一系列特殊编码的连续内存块组成的顺序型数据结构，每个压缩列表节点可以保存一个字节数组或一个整数值。其由3部分构成：

 ----------------------------------------
| prev_entry_length | encoding | content |
 ----------------------------------------

• 其中content为实际数据,encoding存储了content的具体数据类型,prev_entry_length则保存了前一个节点的占用的内存长度,通过这个值就可以定位到前一个节点。在压缩列表中为了节省内存可能会造成连锁更新,因此存在一定的性能隐患,但是由于本身出现的概率就比较小,在节点数量不多的情况下这种影响可以忽略不计。

5.双向链表 LINKEDLIST

• 就是含有前驱和后继节点的普通双向链表，其保存头节点、尾节点和链表长度，可以接获取链表长度。

6.跳表 SKIPLIST

跳跃表是一种有序的数据结构，支持平均O(logN)的时间复杂度,平均O(N)的空间复杂度的节点查找,其效率可以和平衡树媲美，同时实现简单,而且由于不需要reblance操作,在高并发情况下表现更加出色。

Redis的5种数据类型及底层数据结构

1.字符串对象 String

• 字符串的编码可以是int、raw或embstr。
• 优先级：如果一个字符串的内容可以转换为long类型，那么该字符串就会被转换成long类型，Redis对象的ptr就会指向该long类型的对像，并且对象编码常量也用int。
• 而普通的字符串有2种，embstr或raw编码。如果字符串对象的长度小于等于32字节，就使用embstr编码。否则用传统的raw编码。
• embstr是一种短字符串的优化,其存储还是使用SDS结构,但raw编码会调用两次内存分配函数来分别创建redisObject结构和SDS结构,而embstr编码则通过调用一次内存分配函数来分配 一块连续的空间,空间中依次包含redisObject和SDS结构。

2.列表对象 List

• 列表对象的编码可以是ziplist或linkedlist。
• zpilist是压缩列表，需要使用连续的内存区域。当列表对象元素不多，元素体积不大时，Redis就采用ziplist存储。当数据量过大时，无法保证找到那么大的连续内存空间；而且插入的复杂度变为O(n)，每次插入都会重新realloc(动态内存调整，意思是当前内存无法存入更多数据时，申请分配新的连续内存)，而实际ziplist只需要一次malloc(动态内存分配，也就是初始化内存时分配一块合适的，此后不用再调整)。此时就使用linkedlist来存储对象，每当增加一个节点的时候，就需要重新malloc一块内存。

3.哈希对象 Hash

• 哈希对象的编码可以使用ziplist或hashtable。
• ziplist中的哈希对象按照key1，value1，key2，value2的顺序存放。当对象数目不多内容不大时，这种方式效率很高。
• ht是由dict结构来实现的

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;

4.集合对象 Set

• 集合对象的编码可以是intset或者hashtable。只有当Set中的所有元素均为整数类型时才会使用intset。
• intset是一个整数集合，里面存的是某种同一类型的整数，支持如下3种长度的整数：

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

• intset是一个有序集合，查找元素的复杂度为O(logN)，但插入时不一定为O(logN)，因为有可能涉及到升级操作。比如当集合里全是int16_t型的整数，这时要插入一个int32_t，那么为了维持集合中数据类型的一致，那么所有的数据都会被转换成int32_t类型，涉及到内存的重新分配(realloc)，这时插入的复杂度就为O(N)了。intset不支持降级操作。

5.有序集合对象 ZSet

• 有序集合对象的编码可以是ziplist或者skiplist与hastable的结合。
• ziplist作为集合和作为哈希对象是一样的，不同的是哈希对象是key，value顺序存放，而有序集合是member和score顺序存放。按照score从小到大排序。
• skiplist是跳表，它实现了有序集合中的快速查找，大多数情况下它的查询速度可以和平衡树差不多。但是它实现比较简单，可以作为平衡树的替代品。
• 单一用hashtable，那可以快速查找、添加和删除元素，但没法保持集合的有序性。如果单一用skiplist，有序性可以得到保障，但查找的速度太慢O(logN)。

原文：https://blog.csdn.net/caishenfans/article/details/44784131
参考：https://www.jianshu.com/p/f8ccf8806095