[TOC] ## 概述 redis有7中基础类型，字符串string、列表list、哈希表hash、集合set、有序集合zset、stream、GEO。我着重记录前面五个类型的数据，并给出对应的redis源码的数据结构。 对应的五个处理文件，断点调试的文件： t_string.c 、 t_list.c、t_hash.c、 t_set.c、t_zset.c、t_stream ## 字符串string ### 字符串的使用方式 设置键值对 ``` set k v get k ``` redis服务接收到设置键值对的指令的流程 * 尝试对值对象进行编码 * 设置键值对，存储到字典的哈希表的一个节点中 * 通知给redis客户端 ### 字符串编码 Redis为了将内存的使用率做到极致，针对字符串对象，提供了三种数据结构 ```cpp #define REDIS_ENCODING_RAW 0 /* Raw representation */ #define REDIS_ENCODING_INT 1 /* Encoded as integer */ #define REDIS_ENCODING_EMBSTR 8 /* Embedded sds string encoding */ ``` 1. `REDIS_ENCODING_INT`类型的数据编码流程 * 只对长度小于或等于 21 字节，并且可以被解释为整数的字符串进行编码, 如果值小于1000，则被存储到共享对象中，引用计数+1，通过复用来减少内存碎片，以及减少操作耗时的共享对象。 * 如果编码类型为`REDIS_ENCODING_RAW`, 则销毁掉原来的内存，把编码改为`REDIS_ENCODING_INT`，并重新赋值，代码如下： ```cpp if (len <= 21 && string2l(s,len,&value)) { if (server.maxmemory == 0 && value >= 0 && value < REDIS_SHARED_INTEGERS) { decrRefCount(o); //销毁原来的内存 incrRefCount(shared.integers[value]);// 引用计数+1 return shared.integers[value]; //使用共享内存 } else { if (o->encoding == REDIS_ENCODING_RAW) sdsfree(o->ptr); //销毁原来的内存 o->encoding = REDIS_ENCODING_INT;//修改编码状态 o->ptr = (void*) value; return o; } } ``` 2.针对`REDIS_ENCODING_RAW`的编码方式，redis的处理是尝试从 SDS 中移除所有空余空间 * raw 编码会调用两次内存分配函数来分别创建 redisObject 结构和 sdshdr 结构,而 embstr 编码则通过调用一次内存分配函数来分配一块连续的空间， 空间中依次包含 redisObject 和 sdshdr 两个结构 3. 当字符串长度小于`44`，则使用`REDIS_ENCODING_EMBSTR`的编码方式 ``` #define REDIS_ENCODING_EMBSTR_SIZE_LIMIT 44 ``` *embstr类型是如何存放字符串的【重点】* 我们知道一般cpu从内存中读取数据会先读取到 cache line（缓存行）， 一个缓存行基本占64个字节，其中redisObject最少占16个字节（根据属性的类型计算得出），所以如果要读取一个 redisObject，会发现只读取了16个字节，剩下的48个字节的空间相当于浪费，所以为了提高性能（主要减少了内存读取的次数），所以再RedisObject空间后又开辟48个字节的连续空间，将ptr指向的值存入其中，注意此处存入的是字符串类型，48个字节对应的是sdshdr8存储结构。而 sdshdr8 在不存入数据的情况下，最少要 4 个字节（其中一个字节是字符串尾部的'\\0'）,那么还剩余 44 个字节，所以如果在 44 个字节以内字符串就可以放在缓存行里面，从而减少了内存I/O次数 *embstr 编码方式的优点*： * embstr 编码将创建字符串对象所需的*内存分配次数从 raw 编码的两次降低为一次*。 * 释放 embstr 编码的字符串对象*只需要调用一次内存释放函数*，而释放 raw 编码的字符串对象需要调用两次内存释放函数。 * 因为 embstr 编码的字符串对象的所有数据都保存在一块连续的内存里面，所以这种编码的字符串对象比起 raw ，*编码的字符串对象能够更好地利用缓存带来的优势*。 ### 字符串在Redis中所使用的内部数据结构 在Redis中使用字典dict来存储键值对。设置key的值 ``` void setKey(redisDb *db, robj *key, robj *val) ``` 添加或覆盖数据库中的键值对: ``` if (lookupKeyWrite(db,key) == NULL) { dbAdd(db,key,val); //添加 } else { dbOverwrite(db,key,val);//覆盖 } ``` 可以看到底层键值对是存储在字典里的哈希表里的一个节点中。 ## 列表list Redis列表是简单的字符串列表，按照插入顺序排序。你可以添加一个元素到列表的头部（左边）或者尾部（右边）. 一个列表最多可以包含 2^32- 1 个元素 (4294967295, 每个列表超过40亿个元素)。 使用方式： ``` >lpush k v ``` ### 查看列表list的使用流程 * redis服务收到客户端的`lpush`指令 * 尝试将字符串编码，参考上面的字符串编码 * 是否需要转换编码？指的是list的编码，3.2版本以前编码格式有两种`REDIS_ENCODING_ZIPLIST`,`REDIS_ENCODING_LINKEDLIST`，3.2(包括3.2)版本之后升级为双向链表quicklist ## hash列表 redis的哈希对象的底层存储可以使用ziplist（压缩列表）和hashtable。当hash对象可以同时满足下面两个条件时，哈希对象使用ziplist编码。 * 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节 * 哈希对象保存的键值对数量小于512个 ziplist的数据结构请看：[ziplist压缩列表](ziplist.md). 判断条件的代码如下： ``` if (sdsEncodedObject(argv[i]) && sdslen(argv[i]->ptr) > server.hash_max_ziplist_value) { hashTypeConvert(o, OBJ_ENCODING_HT); break; } //server.hash_max_ziplist_value = 64 ``` ### hash存储过程源码分析 以`hset`命令为例进行分析，整个过程如下： * 首先查看hset中key对应的value是否存在，`hashTypeLookupWriteOrCreate`。 * 判断`key`和`value`的长度确定是否需要从`zipList`到`hashtable`转换，`hashTypeTryConversion`。 * 对`key/value`进行`string`层面的编码，解决内存效率问题。 * `hashTypeSet`,判断是否使用ziplist或hashtable * 更新`hash`节点中`key/value`问题。 * 其他后续操作的问题 ``` void hashTypeConvertZiplist(robj *o, int enc) { serverAssert(o->encoding == OBJ_ENCODING_ZIPLIST); if (enc == OBJ_ENCODING_ZIPLIST) { /* Nothing to do... */ } else if (enc == OBJ_ENCODING_HT) { hashTypeIterator *hi; dict *dict; int ret; hi = hashTypeInitIterator(o); dict = dictCreate(&hashDictType, NULL); //分配内存 while (hashTypeNext(hi) != C_ERR) { sds key, value; key = hashTypeCurrentObjectNewSds(hi,OBJ_HASH_KEY); //编码key value = hashTypeCurrentObjectNewSds(hi,OBJ_HASH_VALUE);//编码value ret = dictAdd(dict, key, value);//把key-value添加到字典里 if (ret != DICT_OK) { serverLogHexDump(LL_WARNING,"ziplist with dup elements dump", o->ptr,ziplistBlobLen(o->ptr)); serverPanic("Ziplist corruption detected"); } } hashTypeReleaseIterator(hi); zfree(o->ptr); //销毁之前的内存 o->encoding = OBJ_ENCODING_HT; o->ptr = dict; //把新的hashtable赋值给ptr } else { serverPanic("Unknown hash encoding"); } } ``` ## set集合 Redis 的 Set 是 String 类型的无序集合。集合成员是唯一的，这就意味着集合中不能出现重复的数据。 Redis 中集合是通过哈希表实现的，所以添加，删除，查找的复杂度都是 O(1)。 集合中最大的成员数为 232 - 1 (4294967295, 每个集合可存储40多亿个成员)。 ### set集合的底层数据 **Redis使用Dict和IntSet保存Set数据**。 * 当所有数据都是整数的时候使用`intset` * 否则就使用`dict`。 `intset.h`： ``` //inset 数据结构，在set数据量小且都是整型数据时使用 typedef struct intset { // 编码范围，由具体存储值决定 uint32_t encoding; // 数组长度 uint32_t length; // 具体存储元素的容器 int8_t contents[]; } intset; ``` ### set集合数据操作流程 以`sadd`操作为例子，分析流程 ``` redis-cli> sadd 11 20 3 ``` 收到客户端的指令，进入函数 ``` void saddCommand(client *c) ``` 循环添加进入集合 ``` int setTypeAdd(robj *subject, sds value) ``` 判断是否是整数类型数据, 使用`intset`存储数据： ``` if (isSdsRepresentableAsLongLong(value,&llval) == C_OK) { ... subject->ptr = intsetAdd(subject->ptr,llval,&success); ... } ``` 如果有不是整数类型的数据，则转化为`dict`数据类型 ``` setTypeConvert(subject,OBJ_ENCODING_HT); ``` ## zset有序集合 Redis 有序集合和集合一样也是 string 类型元素的集合,且不允许重复的成员。 不同的是每个元素都会关联一个 double 类型的分数。redis 正是通过分数来为集合中的成员进行从小到大的排序。 有序集合的成员是唯一的,但分数(score)却可以重复。 集合是通过哈希表实现的，所以添加，删除，查找的复杂度都是 O(1)。 集合中最大的成员数为 232 - 1 (4294967295, 每个集合可存储40多亿个成员)。 ### zset的底层数据结构 zset的底层数据使用`ziplist`和`zset` * 有序集合保存的元素数量小于128个 * 有序集合保存的所有元素的长度小于64字节 当满足上述条件时，使用`ziplist`, 否则就使用`zset`。 server.h ``` typedef struct zskiplistNode { sds ele; double score; struct zskiplistNode *backward; struct zskiplistLevel { struct zskiplistNode *forward; unsigned long span; } level[]; } zskiplistNode; typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; int level; } zskiplist; typedef struct zset { dict *dict; //方便查询某一个key zskiplist *zsl; //方面范围查询 } zset; ``` ### zset添加数据流程 以`zadd`为例子 ``` redis> zadd t1 2 a 1 c 3 b ``` 收到客户端数据，进入函数 ``` void zaddGenericCommand(client *c, int flags) ``` 判断是否有该key ``` zobj = lookupKeyWrite(c->db,key) ``` 检查是否是`OBJ_ZSET`数据类型： ``` if (checkType(c,zobj,OBJ_ZSET)) goto cleanup; ``` 如果所有元素的长度小于64字节，则使用`ziplist`编码，否则使用`OBJ_ENCODING_SKIPLIST`. 遍历元素，添加到集合中 ``` zsetAdd(zobj, score, ele, &retflags, &newscore); ``` 使用ziplist编码的时候会判断，"有序集合保存的元素数量小于128个，有序集合保存的所有元素的长度小于64字节", 不满足上述条件则转化为`OBJ_ENCODING_SKIPLIST`编码 ``` if (zzlLength(zobj->ptr) > server.zset_max_ziplist_entries || sdslen(ele) > server.zset_max_ziplist_value) zsetConvert(zobj,OBJ_ENCODING_SKIPLIST); ``` 使用`OBJ_ENCODING_SKIPLIST`编码,数据结构是`zset`，`zset`包含一个`dict`和一个`zskiplist`,`dict`用来查询数据到分数(score)的对应关系，而`zskiplist`用来根据分数查询数据（可能是范围查找）。 ### **范围操作命令** `zset`中有很多跟范围相关的命令，大致可以归纳为以下三种： 1. 获取或删除指定排位区间内的元素，如zrange、zrevrange、zremrangebyrank命令。 2. 获取或删除指定分值区间内的元素，如zrangebyscore、zrevrangebyscore、zremrangebyscore命令。 3. 获取或删除指定字典序区间内的元素，如zrangebylex、zremrangebylex。对于这种情况，需要注意：只有当插入到有序集合（Sorted set）中的所有元素的分值score都相同时，使用zrangebylex或zremrangebylex命令可以认为存储在有序集合中的元素是按字典序排序（Lexicographical ordering）的，然后返回或删除元素值在最小值 min 及最大值 max 之间的所有元素。如果有序集合中的元素存在不同的分值，所返回或删除的元素是不确定的。