基本数据类型

2019-03-24 本文已影响0人 zxRay

redisObject

typedef struct redisObject {
    unsigned type:4;     
    unsigned encoding:4; 
    unsigned lru:24; 
    int refcount; 
    void *ptr;
} robj;

redis中用redisObject包装数据类型，其中

type：表示redis对外支持的数据结构，如string、list、set、hash等
encoding：表示各个数据结构的内部实现方式，如string可有embstr、raw、int 三种实现方式
ptr：指向实际数据结构的指针
refcount：该对象的引用计数。C语言中没有垃圾回收机制，内存的申请跟释放都需要自行控制，一个对象在多个函数间传递时很容易出现内存泄漏或者过早释放。所以redis采用引用计数方法来管理对象的生命周期

methodA(robj *key)：
  incrRefCount(key)
  methodB(key)
  incrRefCount(key)

sds-encoding

typedef char *sds;

sds表示一个字符串，它实际上就是char * . redis为了让字符串更容量管理，为字符串添加了元数据信息即sdshdrX（X表示字符串的长度），以sdshdr8为例:

#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

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 实际字符串长度不包含\0 */
    uint8_t alloc; /* buf的大小，不包含\0 */
    unsigned char flags; /* sdshdrX X类型 */
    char buf[]; // 数据，这是个柔性数组，内容跟sdshdr连在一起，并非指针
};

举个例子, "hello"用sds表示如下图(用sdshdr8表示)，sds指向实际的字符串，通过sds可以很容易计算出header，然后拿到该字符串的元数据信息

整数-encoding

redis对外不提供整数类型，但是内部存储可以保存为整数，这有两个目的：
1、一些命令需要使用整数指，比如incr、decr等
2、整数比字符串省内存，比如123456789用字符串存储需要10个字节，而用整数最多8个字节

同时，redis为10000以下的数字做了缓存。1跟123456789在redis的表示为

字符串-type

redis中对外提供的字符串数据结构，在内部有3个编码方式来实现：
1、embstr，当字符串小于44个字节时，redisObject的ptr直接存储字符串,减少指针解析时间，同时redisObject刚好小于64个字节
2、raw，上面的sds编码
3、int，上面的整数编码

以"hello", "aaaaa..."(100个a), "1"为例

linkedlist-encoding

redis中的链表是一个非常简单的结构

ziplist-encoding

ziplist是redis为了节省内存而开发的数据结构，可以用来做为链表、字典、有序表的底层实现。其结构为：

entry的定义为：

/* We use this function to receive information about a ziplist entry.
 * Note that this is not how the data is actually encoded, is just what we
 * get filled by a function in order to operate more easily. */
typedef struct zlentry {
    unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
    unsigned int prevrawlen;     /* Previous entry len. */
    unsigned int lensize;        /* Bytes used to encode this entry type/len.
                                    For example strings have a 1, 2 or 5 bytes
                                    header. Integers always use a single byte.*/
    unsigned int len;            /* Bytes used to represent the actual entry.
                                    For strings this is just the string length
                                    while for integers it is 1, 2, 3, 4, 8 or
                                    0 (for 4 bit immediate) depending on the
                                    number range. */
    unsigned int headersize;     /* prevrawlensize + lensize. */
    unsigned char encoding;      /* Set to ZIP_STR_* or ZIP_INT_* depending on
                                    the entry encoding. However for 4 bits
                                    immediate integers this can assume a range
                                    of values and must be range-checked. */
    unsigned char *p;            /* Pointer to the very start of the entry, that
                                    is, this points to prev-entry-len field. */
} zlentry;

这个结构实在太复杂了，看起来一点都不省内存，注意看作者的注释，这个结构体并不是enrty实际存储格式，而是为了方便操作而定义的。其真正的存储为

1、prev_entry_length，表示上一个节点的字节数，所以ziplist是一个逆向遍历的列表。其中，它是一个可变长字段，可以是1个字节或者5个字节

大小
1个字节	表示前一个节点的大小, [0X00, 0XFD]
5个字节	第一个字节保留为0XFE用以区分，后4个字节表示大小

总结下这个数据结构的特点为：
1、内存连续，相比普通的链表结构节省内存
2、插入、删除需要进行内存拷贝
3、因为prev_entry_length是个可变字段，所以一旦一个节点变更后，它后续节点的大小可能发生变化，从而导致后续的后续节点大小也可能发生变化，导致连锁更新

quicklist-encoding

quicklist是redis在版本3.2之后引入的数据结构，作为list的默认实现，其引入的目的为：
1、linkedlist的内存开销比较大，主要是要保存*prev跟*next指针，同时内存地址不连续，可能产生内存碎片
2、ziplist的问题在于增删改需要进行内存拷贝，极端情况下可能发生连锁更新

为了解决问题2，引入了quicklist，其想法是采用数据的分片的思想，减少每一片ziplist的大小，从而减少拷贝的成本。大致的结构为：

hashtable-encoding

redis中的hashtable采用链表解决冲突，结构如下

维护了两个hashtable是因为再扩容时需要进行渐进性rehash

intset-encoding

整数集合就是一个整数数组。但是为了节省内存，每个数组元素的大小有2个字节，4字节，8字节3种。元素的大小有数组中最大元素决定。所以，整数集合会进行升级操作，但不会进行降级。所谓升级，比如，[1,2,3] 每个元素可以用16个字节表示，加入2^17 后，2^17需要4个字节表示，所以1,2,3同时也升级为4个字节

skiplist-encoding

一个有序的数组可以进行二分查找，而一个有序的链表却只能一个一个的遍历。skiplist进行一个可以进行二分查找的有序链表，在redis的结构为