Redis Lastest 6.0.14 数据类型与编码-一一网

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

// redisObject::type
#define OBJ_STRING	0
#define OBJ_LIST  	1
#define OBJ_SET   	2
#define OBJ_ZSET  	3
#define OBJ_HASH  	4
#define OBJ_MODULE	5
#define OBJ_STREAM	6

// redisObject::encoding
#define OBJ_ENCODING_RAW 		0
#define OBJ_ENCODING_INT 		1
#define OBJ_ENCODING_HT 		2
#define OBJ_ENCODING_ZIPMAP		3
#define OBJ_ENCODING_LINKEDLIST	4
#define OBJ_ENCODING_ZIPLIST 	5
#define OBJ_ENCODING_INTSET 	6
#define OBJ_ENCODING_SKIPLIST 	7
#define OBJ_ENCODING_EMBSTR 	8
#define OBJ_ENCODING_QUICKLIST 	9
#define OBJ_ENCODING_STREAM		10
复制代码

Type和Encoding的对应关系，参考object.c:objectComputeSize()，OBJ_ENCODING_LINKEDLIST是旧的OBJ_LIST的编码实现，已经不再被使用了。

OBJ_STRING
- OBJ_ENCODING_INT
  - 保存可以用long表示的整型值。
- OBJ_ENCODING_EMBSTR
  - 保存小于等于44字节（OBJ_ENCODING_EMBSTR_SIZE_LIMIT ）的短字符串。
  - 内存分配1次，内存释放1次，内存连续。
  - 当存储的数据是44字节时，robj + sdshdr的大小刚好时64字节。
- OBJ_ENCODING_RAW
  - 内存分配2次，内存释放2次，两段内存不连续。
  - 为什么长字符串就要用RAW，而不用EMBSTR呢？避免大key的问题。
OBJ_LIST
- ~~OBJ_ENCODING_LINKEDLIST~~
  - 优点：两端push、pop效率高。
  - 缺点：①每个节点都维护前后两个指针，内存开销大；②节点彼此间地址并不连续，内存碎片多。
- ~~OBJ_ENCODING_ZIPLIST~~
  - 优点：一整块连续的内存，内存碎片少。
  - 缺点：数据变动可能引起连锁更新（prelen），所以只适合存储少量数据。
  - zipList在Redis 6.0.14中也不再用于编码list了。
- OBJ_ENCODING_QUICKLIST
  - linkedList和zipList的结合，增加了内存利用率，也避免了大量数据的连锁更新。
OBJ_SET
- OBJ_ENCODING_HT
- OBJ_ENCODING_INTSET
  - 集合元素都是整型值，且元素数量少于512（set-max-intset-entries）时使用intset编码。
OBJ_ZSET
- OBJ_ENCODING_ZIPLIST
  - 相邻的2个entry保存一对member:score，前者member，后者score，整体按score升序。
- OBJ_ENCODING_SKIPLIST
  - zset是同时使用dict和skipList的，dict用于存储member->score的映射。
OBJ_HASH
- OBJ_ENCODING_ZIPLIST
  - 相邻的2个entry保存一对subkey:value，前者subkey，后者value。
- OBJ_ENCODING_HT

底层编码的具体说明

OBJ_ENCODING_INT

o->encoding = OBJ_ENCODING_INT;
o->ptr = (void*)((long)value);
复制代码

OBJ_ENCODING_RAW

o->encoding = OBJ_ENCODING_RAW;
o->ptr = (void*)sdsnew("hello");
复制代码

OBJ_ENCODING_EMBSTR

robj和sdshdr的空间是挨在一起的，buf[]不占size，所以也要分配要buf[]的空间，strlen("hello") + 1，*ptr指向buf[]中保存的字符串。embstr编码适合短字符串，只会分配一次内存，raw编码robj和sdshdr不是挨在一起的，需要分配两次内存。

alloc表示分配的空间大小，len表示已用的空间大小。

robj *o = zmalloc(sizeof(robj) + sizeof(sdshdr8) + strlen("hello") + 1);
sdshdr8 *sh = (void*)(o+1);

o->encoding = OBJ_ENCODING_EMBSTR;
p->ptr = sh+1;
复制代码

OBJ_ENCODING_ZIPLIST

unsigned char *ziplistNew();用于创建一个空的ziplist，因为ziplist不是一个结构体，所以需要用指针偏移来为字段赋值，zlbytes表示整个ziplist占用的内存大小，zltail表示最后一个entry的偏移，zllen表示entry的数量，zlend表示ziplist的结尾。

初始状态下，zlbytes = 11，zltail = 10，zllen = 0，zlend = 255。

每个entry可以保存一个字节数组或一个整数值，prelen记录了前一个entry的长度，可以是1个字节或5个字节，5个字节时第1个字节置为256，后4个字节用于存储长度，因此小于上一个entry小于254字节，才会用1个字节存储。prelen相当于prev指针。

encoding记录了data保存的是什么内容（字节数组还是整数？占多少位？）可以是1字节、2字节、5字节。

OBJ_ENCODING_QUICKLIST

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;					// 所有listNode中的所有entry的数量
    unsigned long len;      				// 所有listNode的数量
    int fill:QL_FILL_BITS;    				// redis.conf:list-max-ziplist-size
    unsigned int compress:QL_COMP_BITS; 	// redis.conf:list-compress-depth
    unsigned int bookmark_count:QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;						// 没有压缩指向zipList，有压缩指向quickListLZF
    unsigned int sz;						// zipList的大小，压缩也是原zipList的大小
    unsigned int count:16;					// zipList中entry的数量
    unsigned int encoding:2;				// 1表示没有压缩 2表示使用LZF算法压缩
    unsigned int container:2;				// 1表示不用容器，2表示使用zipList容器存储
    unsigned int recompress:1;				// 被暂时解压的quickListNode会被标记为1
    unsigned int attempted_compress:1;		// 数据太少，不可被压缩
    unsigned int extra:10;					// 保留字段，尚未使用
} quicklistNode;

typedef struct quicklistLZF {
    unsigned int sz;						// compressed的大小
    char compressed[];						// 压缩后的字节数组
} quicklistLZF;
复制代码

OBJ_ENCODING_INTSET

typedef struct intset {
    uint32_t encoding;	// INTSET_ENC_INT16/32/64
    uint32_t length;	// contents字节数组长度
    int8_t contents[];	// 存储int16/int32/int64，由encoding决定
} intset;
复制代码

intset无序、无重复的保存int16/int32/int64类型的数据集合，每个元素编码是一致的，不会小整数用int16，大整数用int64，因此会有整体升级的操作，但不支持降级。

OBJ_ENCODING_HT

typedef struct dict {
    dictType* type;    			// 类型特定函数
    void* privdata;    			// 函数的参数
    dictht ht[2];      			// 哈希表
    int rehashidx;     			// rehash进度，-1表示不在进行
    int iterators;     			// 正在运行的安全迭代器数量
} dict;

typedef struct dictht {
    dictEntry** table;        	// 哈希表数组
    unsigned long size;       	// 哈希表大小
    unsigned long sizemask;   	// size-1
    unsigned long used;       	// 已有节点数量
} dictht;
复制代码

Redis中的HashTable使用拉链法（头插）解决Hash冲突。sizemask永远等于size-1，使用dictHashKey(ht, key) & ht->sizemask;计算dictEntry在table上的索引。

OBJ_ENCODING_SKIPLIST

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;	// 节点数量，不算head
    int level;				// 最高的level
} zskiplist;

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;	// 跨度
    } level[];
} zskiplistNode;
复制代码