数据结构
1. 简单动态字符串
//sds.hstruct sdshdr { // buf 中已占用空间的长度 int len; // buf 中剩余可用空间的长度 int free; // 数据空间 char buf[];};
复制代码
2. 链表
//adlist.htypedef struct listNode { // 前置节点 struct listNode *prev; // 后置节点 struct listNode *next; // 节点的值 void *value;} listNode;
复制代码
3. 字典
//dict.h/* * 字典 */typedef struct dict { // 类型特定函数 dictType *type; // 私有数据 void *privdata; // 哈希表 dictht ht[2]; // rehash 索引 // 当 rehash 不在进行时，值为 -1 int rehashidx; /* rehashing not in progress if rehashidx == -1 */ // 目前正在运行的安全迭代器的数量 int iterators; /* number of iterators currently running */} dict;/* * 哈希表 * * 每个字典都使用两个哈希表，从而实现渐进式 rehash 。 */typedef struct dictht { // 哈希表数组 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩码，用于计算索引值 // 总是等于 size - 1 unsigned long sizemask; // 该哈希表已有节点的数量 unsigned long used;} dictht;/* * 哈希表节点 */typedef struct dictEntry { // 键 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; } v; // 指向下个哈希表节点，形成链表 struct dictEntry *next;} dictEntry;
复制代码
4. 跳跃表
//redis.htypedef 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;
复制代码
5. 整数集合
//intset.htypedef struct intset { // 编码方式 uint32_t encoding; // 集合包含的元素数量 uint32_t length; // 保存元素的数组 int8_t contents[];} intset;
复制代码
6. 压缩列表
ziplist.c
zlbytes 记录整个压缩列表占用的内存字节数；在对压缩列表进行内存重分配，或者计算 zlend 的位置时使用；
zltail 记录压缩列表表为节点距离压缩列表的起始地址有多少字节；通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址
zllen 记录了压缩列表包含的节点数量；当这个属性的值小于 UNIT16_MAX 时，这个属性的值就是压缩列表包含节点的数量；当这个值等于 UNIT16_MAX 时，节点的真实数量需要遍历整个压缩列表才能计算得出
entry* 压缩列表包含 的各个节点，节点的长度由节点保存的内容决定
zlend 特殊值 0xFF，用于标志压缩列表的末端
压缩列表节点的构成
7. 对象
redis 并没有直接使用数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个对象系统包含字符串对象、列表对象、集合对象和有序集合对象，每种对象都用到了至少一种之前介绍的数据结构。
//redis.htypedef struct redisObject { // 类型 unsigned type:4; // 编码 unsigned encoding:4; // 对象最后一次被访问的时间 unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */ // 引用计数 int refcount; // 指向实际值的指针 void *ptr;} robj;// 对象类型#define REDIS_STRING 0 //字符串对象#define REDIS_LIST 1 //列表对象#define REDIS_SET 2 //集合对象#define REDIS_ZSET 3 //有序集合#define REDIS_HASH 4 //哈希对象//高版本的#define OBJ_MODULE 5 /* Module object. */#define OBJ_STREAM 6 /* Stream object. */// 对象编码-> 标明这个对象使用什么数据结构作为对象的底层实现#define REDIS_ENCODING_RAW 0 /* 简单动态字符串 */#define REDIS_ENCODING_INT 1 /* 整数*/#define REDIS_ENCODING_HT 2 /* 字典 */#define REDIS_ENCODING_LINKEDLIST 4 /* 链表 */#define REDIS_ENCODING_ZIPLIST 5 /* 压缩列表 */#define REDIS_ENCODING_INTSET 6 /* 整数集合 */#define REDIS_ENCODING_SKIPLIST 7 /* 跳跃表 */#define REDIS_ENCODING_EMBSTR 8 /* embstr编码的简单动态字符串 *///高版本的#define OBJ_ENCODING_QUICKLIST 9 /* 快速列表 */#define OBJ_ENCODING_STREAM 10 /* 流结构 */
复制代码
这里稍微补充一下，字符串的数据结构，当字符串小于 39 子节点时，采用 embstr 编码，相仿则采用 raw 编码，而在高版本时，是 44 子节；代码如下：
//redis 3.0 版本#define REDIS_ENCODING_EMBSTR_SIZE_LIMIT 39robj *createStringObject(char *ptr, size_t len) { if (len <= REDIS_ENCODING_EMBSTR_SIZE_LIMIT) return createEmbeddedStringObject(ptr,len); else return createRawStringObject(ptr,len);}//redis最新的版本#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44robj *createStringObject(const char *ptr, size_t len) { if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT) return createEmbeddedStringObject(ptr,len); else return createRawStringObject(ptr,len);}
复制代码
那么它们俩的区别是：raw 是两次分配内存来保存 redisObject 结构和 sdshdr 结构 ，意味者它们俩并不是相连的，即内存并不是连续的；而 embstr 是一次分配内存来保存 redisObject 结构和 sdshdr 结构，它们俩是连续的；如下图：
数据库
//redis.htypedef struct redisDb { // 数据库键空间，保存着数据库中的所有键值对 dict *dict; /* The keyspace for this DB */ // 键的过期时间，字典的键为键，字典的值为过期事件 UNIX 时间戳 dict *expires; /* Timeout of keys with a timeout set */ // 正处于阻塞状态的键 dict *blocking_keys; /* Keys with clients waiting for data (BLPOP) */ // 可以解除阻塞的键 dict *ready_keys; /* Blocked keys that received a PUSH */ // 正在被 WATCH 命令监视的键 dict *watched_keys; /* WATCHED keys for MULTI/EXEC CAS */ struct evictionPoolEntry *eviction_pool; /* Eviction pool of keys */ // 数据库号码 int id; /* Database ID */ // 数据库的键的平均 TTL ，统计信息 long long avg_ttl; /* Average TTL, just for stats */} redisDb;
复制代码
上面是一个数据库的结构，在 redis 服务器中是被包含在 redisServer 对象，redisServer 才是真正的 redis 服务器
struct redisServer { //...... //数据库数量 int dbnum; // 数据库 redisDb *db; //......};
复制代码
汇总
这里是基于 redis3.+版本，对数据库的结构简单解释，并无过多深入解说，同时也是参照别人的备注，将其记录下来；该文章并无啥特点，粗略看即可；更多详细的介绍，可以查阅我引用的文章；在高版本 redis 中，添加了两类对象，一个是 Module 对象，另外一个是流对象；同时也增加了两种数据结构，QUICKLIST 和 STREAM。
另外有两个数据结构 hyperloglogs，geospatial。更多详细的介绍，可参考引用文章；这里有个疑惑，什么样的对象类型中会使用该结构；从对象类型枚举中，并没有明显看出哪个对象是使用该数据结构的，唯独只有 module 对象看似很可疑，觉得该俩数据结构是归 module 对象的；然而这个 module 对象，在网上介绍比较少，并不是很清楚，待找到更多资料后补充；
引用：
Redis内部数据结构详解(6)——skiplist
相关的代码，参照：https://gitee.com/Michael_Chan/redis_source_annotation，该仓库是 clone 别人的。
《redis 设计与实现》，作者黄健宏
走近源码：神奇的HyperLogLog
geospatial
个人实现的跳跃表实现：https://gitee.com/Michael_Chan/java-structure/tree/master/src/main/java/com/michael/skiplist 仅供参考
评论