引言
从本次开始，对Redis设计与实现进行浏览及相干读书笔记的记录。Redis版本为3.0
<!-- more -->
数据结构
简略动静字符串SDS
sds数据结构位于sds.h/sdshdr
/* * 保留字符串对象的构造 */struct sdshdr { // buf 中已占用空间的长度 int len; // buf 中残余可用空间的长度 int free; // 数据空间 char buf[];};绝对于C语言的字符串，SDS的长处在于
- 常数复杂度获取字符串长度
- 杜绝缓冲区溢出
- 缩小批改字符串所带来的内存重新分配（留神，开释空间时候，不会真的开释，而是设置free的值）
链表
链表的相干代码在adlist.h中
链表节点listNode
/* * 双端链表节点 */typedef struct listNode { // 前置节点 struct listNode *prev; // 后置节点 struct listNode *next; // 节点的值 void *value;} listNode;由多个listNode组成的双端链表
链表构造list
/* * 双端链表构造 */typedef struct list { // 表头节点 listNode *head; // 表尾节点 listNode *tail; // 节点值复制函数 void *(*dup)(void *ptr); // 节点值开释函数 void (*free)(void *ptr); // 节点值比照函数 int (*match)(void *ptr, void *key); // 链表所蕴含的节点数量 unsigned long len;} list;字典
redis中的字典应用哈希表实现，其代码在dict.h中
哈希表构造dictht
/* * 哈希表 * * 每个字典都应用两个哈希表，从而实现渐进式 rehash 。 */typedef struct dictht { // 哈希表数组 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩码，用于计算索引值 // 总是等于 size - 1 比方7号，当计算索引时候， 7&sizemask就能够失去 unsigned long sizemask; // 该哈希表已有节点的数量 unsigned long used;} dictht;其中dictEntry为一个键值对
/* * 哈希表节点 */typedef struct dictEntry { // 键 void *key // 值 union { void *val; uint64_t u64; int64_t s64; } v; // 指向下个哈希表节点，造成链表 表明是一个链地址法解决哈希抵触 struct dictEntry *next;} dictEntry;上面为了形象示意一个哈希表，给出一个例子
上面给出一个多个dictEntry连贯的哈希表
最终Redis中的字典数据结构如下
/* * 字典 */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;/* * 字典类型特定函数 */typedef struct dictType { // 计算哈希值的函数 redis默认的函数算法为murmurhash2 unsigned int (*hashFunction)(const void *key); // 复制键的函数 void *(*keyDup)(void *privdata, const void *key); // 复制值的函数 void *(*valDup)(void *privdata, const void *obj); // 比照键的函数 int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 销毁键的函数 void (*keyDestructor)(void *privdata, void *key); // 销毁值的函数 void (*valDestructor)(void *privdata, void *obj);} dictType;跳跃表
redis中的跳跃表构造代码为redis.h/zskiplistNode和redis.h/zskiplist
/* ZSETs use a specialized version of Skiplists *//* * 跳跃表节点 */typedef struct zskiplistNode { // 成员对象 robj *obj; // 分值 留神redis跳跃表依照节点从小到大排列 double score; // 后退指针 struct zskiplistNode *backward; // 层 数组大小依照幂次定律（越大的数呈现概率越小）1-32随机数字 struct zskiplistLevel { // 后退指针 struct zskiplistNode *forward; // 跨度 unsigned int span; } level[];} zskiplistNode;/* * 跳跃表 */typedef struct zskiplist { // 表头节点和表尾节点 struct zskiplistNode *header, *tail; // 表中节点的数量 unsigned long length; // 表中层数最大的节点的层数 int level;} zskiplist;上面给出一个简略的跳跃表例子
后退指针用于遍历跳跃表，上面的虚线为遍历过程
整数汇合 intset
当一个汇合外面只有整数值元素时候，且元素数量不超过REDIS_SET_MAX_INTSET_ENTRIES时候，汇合底层采纳整数汇合
#define REDIS_SET_MAX_INTSET_ENTRIES 512 /*汇合中元素个数小于该值，set底层应用intset*/redis中整数汇合代码位于intset.h/intset
typedef struct intset { // 编码方式 uint32_t encoding; // 汇合蕴含的元素数量 uint32_t length; // 保留元素的数组 依照从小到大的程序，且不反复 int8_t contents[];} intset;contents数组尽管是int8_t，然而外面寄存的数据的实在类型由encoding字段决定
- 降级操作
如果往下面的整数汇合中append类型为int32的65535，则会产生降级，降级的过程次要包含将每个元素所占空间进行裁减，而后设置encoding，降级完后为
- 降级操作
留神整数汇合无奈进行降级，降级之后，会始终继续该编码
压缩列表 ziplist
压缩列表其实就是一块间断内存，一个压缩列表包含多个节点（entry），每个entry保留一个字节数组或者整数值。在redis源码中， 压缩列表没有数据结构代码定义，压缩列表是一种通过内存非凡编码方式实现的数据结构。他是通过定义一些基地址，而后应用偏移量来定义ziplist，其中大量应用了宏函数定义
/* * ziplist 属性宏 */// 定位到 ziplist 的 bytes 属性，该属性记录了整个 ziplist 所占用的内存字节数// 用于取出 bytes 属性的现有值，或者为 bytes 属性赋予新值#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl)))// 定位到 ziplist 的 offset 属性，该属性记录了达到表尾节点的偏移量// 用于取出 offset 属性的现有值，或者为 offset 属性赋予新值#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))// 定位到 ziplist 的 length 属性，该属性记录了 ziplist 蕴含的节点数量// 用于取出 length 属性的现有值，或者为 length 属性赋予新值#define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))// 返回 ziplist 表头的大小#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))// 返回指向 ziplist 第一个节点（的起始地位）的指针#define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE)// 返回指向 ziplist 最初一个节点（的起始地位）的指针#define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))// 返回指向 ziplist 末端 ZIP_END （的起始地位）的指针#define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)其中，redis对entry应用了数据结构形容，如下代码ziplist.c/zlentry
/* * 保留 ziplist 节点信息的构造 */typedef struct zlentry { // prevrawlen ：前置节点的长度 // prevrawlensize ：编码 prevrawlen 所需的字节大小 unsigned int prevrawlensize, prevrawlen; // len ：以后节点值的长度 // lensize ：编码 len 所需的字节大小 unsigned int lensize, len; // 以后节点 header 的大小 // 等于 prevrawlensize + lensize unsigned int headersize; // 以后节点值所应用的编码类型 unsigned char encoding; // 指向以后节点的指针 unsigned char *p;} zlentry;- ziplist的创立
/* Create a new empty ziplist. * * 创立并返回一个新的 ziplist * * T = O(1) */unsigned char *ziplistNew(void) { // ZIPLIST_HEADER_SIZE 是 ziplist 表头的大小 // 1 字节是表末端 ZIP_END 的大小 unsigned int bytes = ZIPLIST_HEADER_SIZE+1; // 为表头和表末端调配空间 unsigned char *zl = zmalloc(bytes); // 初始化表属性 ZIPLIST_BYTES(zl) = intrev32ifbe(bytes); ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE); ZIPLIST_LENGTH(zl) = 0; // 设置表末端 zl[bytes-1] = ZIP_END; return zl;}因为压缩列表次要就是为了节约内存，因而对于不同的数据，其编码方式不一样，后面咱们曾经晓得，entry中次要放字节数组和整数，下表给出两种数据不同长度时候的编码
<div> <!--块级封装-->
<center> <!--将图片和文字居中--><img src="https://smypicture.oss-cn-bei...g"
alt="无奈显示图片时显示的文字" style="zoom:这里写图片的缩放百分比"/><br> <!--换行-->字节数组编码 <!--题目--></center></div>
<div> <!--块级封装-->
<center> <!--将图片和文字居中--><img src="https://smypicture.oss-cn-bei...g"
alt="无奈显示图片时显示的文字" style="zoom:这里写图片的缩放百分比"/><br> <!--换行-->整数编码 <!--题目--></center></div>
对象
本次首先对Redis的相干数据结构进行介绍。Redis对象次要分为5种：REDIS_STRING、REDIS_LIST、REDIS_HASH、REDIS_SET、REDIS_ZSET。上面首先给出Redis中对对象的代码示意
// 对象类型#define REDIS_STRING 0#define REDIS_LIST 1#define REDIS_SET 2#define REDIS_ZSET 3#define REDIS_HASH 4#define REDIS_LRU_BITS 24#define REDIS_LRU_CLOCK_MAX ((1<<REDIS_LRU_BITS)-1) /* Max value of obj->lru */#define REDIS_LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */typedef struct redisObject { // 类型 类型说明符 位域名：位域长度 标识type占4个二进制位 因为有可能不须要一个残缺的字节 // 1个字节8位 unsigned type:4; // 编码 unsigned encoding:4; // 对象最初一次被拜访的工夫 unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */ // 援用计数 int refcount; // 指向理论值的指针 void *ptr;} robj;首先看到有2个字段，为类型和编码，类型就是redis的5种类型，编码就是这个类型底层是用什么编码方式实现
但实际上，Redis的外部并不只是这5种对象，对于下面5种对象，都有几种底层实现形式，上面给出各数据结构底层实现的对应形式
REDIS_STRING
REDIS_STRING示意redis中的字符串类型，其底层由以下三种实现形式
REDIS_ENCODING_INT
如果一个字符串对象保留的是整数值，且这个整数值能够用long类型示意，则字符串对象会奖整数值保留在字符串对象的ptr属性中，此时会将ptr的void*转换为long
127.0.0.1:6379> set number "1"OK127.0.0.1:6379> object encoding number"int"REDIS_ENCODING_RAW
如果字符串保留的是一个字符串值，且长度大于32字节，redis的字符串对象就会采纳简略动静字符串（SDS）实现
127.0.0.1:6379> set longstr "Hello, my name is Shi Linkun, is a programmer who loves code, I hope that each blog can let myself consolidate their knowledge, but also let everyone get a little knowledge, thank you"OK127.0.0.1:6379> object encoding longstr"raw"这里先不对SDS进行具体简介，后续独自对其进行形容
REDIS_ENCODING_EMBSTR
如果字符串对象保留的是一个字符串，且长度小于等于32字节，则应用embstr编码实现
127.0.0.1:6379> set story "hello my name is shilinkun"OK127.0.0.1:6379> object encoding story"embstr"留神redis3.0版本中理论距离为39字节
#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);}为什么是39字节，这里参考这个知乎的解释
embstr是一块间断的内存区域，由redisObject和sdshdr组成。其中redisObject占16个字节，当buf内的字符串长度是39时，sdshdr的大小为8+39+1=48，那一个字节是'\0'。加起来刚好64。是不是发现了什么？
typedef struct redisObject { unsigned type:4; unsigned encoding:4; unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */ int refcount; void *ptr;} robj;struct sdshdr { unsigned int len; unsigned int free; char buf[];};从2.4版本开始，redis开始应用jemalloc内存分配器。这个比glibc的malloc要好不少，还省内存。在这里能够简略了解，jemalloc会调配8，16，32，64等字节的内存。embstr最小为16+8+8+1=33，所以最小调配64字节。当字符数小于39时，都会调配64字节。
三个编码的转换
int->raw
向一个保留整数数值的字符串对象应用APPEND命令，就会使得int转变为raw
embstr->raw
对embstr类型的字符串，执行任何的批改命令，都会变为raw
相干命令
字符串命令的实现在t_string.c中
REDIS_LIST
列表对象底层次要由2种编码方式：REDIS_ENCODING_ZIPLIST、REDIS_ENCODING_LINKEDLIST
REDIS_ENCODING_ZIPLIST
ziplist是指应用压缩列表实现
REDIS_ENCODING_LINKLIST
linklist是应用双端链表实现
编码转换
redis.h
#define REDIS_LIST_MAX_ZIPLIST_ENTRIES 512 /*list中元素个数小于该值，list底层应用ziplist*/#define REDIS_LIST_MAX_ZIPLIST_VALUE 64 /*list中所有的字符串长度小于该值，list底层应用ziplist*/上述两个宏定义别离与redis的配置文件中list-max-ziplist-entries和list-max-ziplist-value对应
REDIS_HASH
哈希对象次要有2种编码方式，REDIS_ENCODING_ZIPLIST和REDIS_ENCODING_HT
REDIS_ENCODING_ZIPLIST
ziplist作为底层实现，先放入键，后放入值
REDIS_ENCODING_HT
编码转换
#define REDIS_HASH_MAX_ZIPLIST_ENTRIES 512 //哈希对象保留的键值对数量小于512个，应用ziplist;#define REDIS_HASH_MAX_ZIPLIST_VALUE 64 //哈希对象保留的所有键值对的键和值的字符串长度都小于64字节,应用ziplist;上述两个宏定义别离与redis的配置文件中hash-max-ziplist-entries和hash-max-ziplist-value对应
REDIS_SET
汇合的底层编码方式也是两种：REDIS_ENCODING_INTSET和REDIS_ENCODING_HT
REDIS_ENCODING_INTSET
应用该编码方式作为汇合的底层实现时候，个别是整数汇合，比方
REDIS_ENCODING_HT
应用哈希表作为汇合的底层实现形式时，所有的值作为键，但对应的值为null
编码转换
#define REDIS_SET_MAX_INTSET_ENTRIES 512 /*汇合中元素个数小于该值，且全为整数，set底层应用intset*/对应的redis配置文件选项为set-max-intset-entries
REDIS_ZSET
有序汇合底层实现为：REDIS_ENCODING_ZIPLIST和REDIS_ENCODING_SKIPLIST
REDIS_ENCODING_ZIPLIST
当应用压缩列表作为有序汇合的底层实现时候，压缩列表的entry有2个值，一个是值，一个是得分，同时依照得分由小到大进行排列
REDIS_ENCODING_SKIPLIST
当应用跳跃表进行底层实现时候，一个有序汇合同时包含：
- 一个跳跃表
- 一个字典
为什么有序汇合须要同时应用跳跃表和字典来实现?
在实践上，有序汇合能够独自应用字典或者跳跃表的其中一种数据结构来实现，但无论独自应用字典还是跳跃表，在性能上对比起同时应用字典和跳跃表都会有所升高。举个例子，如果咱们只应用字典来实现有序汇合，那么尽管以O(1)复杂度查找成员的分值这一个性会被保留，然而，因为字典以无序的形式来保留汇合元素，所以每次在执行范畴型操作——比方ZRANK、ZRANGE等命令时，程序都须要对字典保留的所有元素进行排序，实现这种排序须要至多O(NlogN)工夫复杂度，以及额定的O(N)内存空间（因为要创立一个数组来保留排序后的元素)。
另一方面，如果咱们只应用跳跃表来实现有序汇合，那么跳跃表执行范畴型操作的所有长处都会被保留，但因为没有了字典，所以依据成员查找分值这一操作的复杂度将从O(1)回升为O(logN)。因为以上起因，为了让有序汇合的查找和范畴型操作都尽可能快地执行，Redis 抉择了同时应用字典和跳跃表两种数据结构来实现有序汇合。
编码转换
#define REDIS_ZSET_MAX_ZIPLIST_ENTRIES 128 /*有序汇合中元素个数小于该值，zset底层应用ziplist*/#define REDIS_ZSET_MAX_ZIPLIST_VALUE 64 /*有序汇合中元素长度小于该值，zset底层应用ziplist*/上述两个宏定义别离与redis的配置文件中zset-max-ziplist-entries和zset-max-ziplist-value对应
总结
这一次把redis的数据结构和对应的对象实现形式大抵说了一遍，最重要的还是什么时候应用什么数据结构，并且各种数据结构一些命令的工夫复杂度等，这些其实还没有进行论述，前面会独自开一章进行解说，因为在理论我的项目中，咱们要针对不同场景对数据结构进行选取
本人的网址：www.shicoder.top
欢送加群聊天 452380935本文由博客一文多发平台 OpenWrite 公布！