快速阅读《Redis设计与实现》 I

2015-09-03

@(Program Primer)

熟悉Redis框架 — 读书部分 I

找工作找实习的时候,简历比较容易过关,也幸好有很多同学的内推,但是在面试环节卡住了.可以看出我的简历还是可以过关的,很少出现简历不过的情况,投递阿里巴巴C++研发工程师岗位,不少人接到了要求改变职位的通知,我还是比较顺利的通过了简历这一关.面试被拒还总结一下,也接受一下好友的建议,重点把一些最近很火的东西搞明白.Redis就是其中之一.

反省一下

先来自我反省一下,为什么简历比较容易过关,面试总是被拒,从开始今年4月份面实习到现在面内推工作,也不下10家公司了,而且多数都是互联网大佬,也不是所有的都被拒,比如某著名翻译软件,通过了一面,也安排了二面,但是做事从不按常理出牌的导师非不让去,我跟Hr协商了以后安排面试,然后就没有然后了,导师就是个坑.后来也比较顺利的通过了几个其他公司,选了一家研究性的公司实习.有好有坏,反省一下,为毛BAT会被拒绝.

面试技巧,这个真的很关键,我有点孩子气,喜欢开玩笑,面试的时候聊聊就自己放松了,忘记了怎么突出自己的亮点,掉进面试官的坑了,所以,一定要紧张一点,把自己的亮点都表现出来,有东西可以跟面试官聊.
我喜欢C++底层的东西,比如编译器原理,链接器,等等,但这些不是很熟练,只是具备常识,也喜欢C++对象模型,这些东西还是有些涉及,但是这方面的面试比较少,顶多问一下虚函数是怎么实现的,这个我比较清楚,但是描述的不好,没有把动态类型和静态类型解释一下,导致面试官认为我比较水,其实我是真的知道,所以,这期间要重点补充一下这些知识,把思路整理好,重点是对象模型这块.
几乎所有的面试官都对STL各个容器的实现原理非常感兴趣,恰好我对这些并没有太深入的了解,我仅是知道vecor空间如何增长,map是用红黑树实现的,hashmap是类似与hash表,红黑树与平衡二叉树有比较相似,等等,具体原理讲不清楚,下一步重点学习STL基本容器的理论,并且同时学习Redis的五种基本数据对象的原理以及基本使用.
把自己的课题研究重点突出,我的课题是视觉跟踪,使用的方法是压缩感知理论,我可以把压缩感知理论介绍一下,以及我用的字典学习方法,还有我之前的课题是图像超分辨率,很详细的研究过BP神经网络,这一点我可以讲的很清楚.
关于项目,我的项目都不是很难,但是也有自己收获的地方,重点总结一下.
暂时就这些吧,还要刷算法题.

Redis读书计划

面试几次后受打击还是蛮大的,有些是技术问题的确不会,但是有些确实人品+运气的问题了,运气还是要靠积累的,接受好友的建议,把Redis搞懂,买了黄的一本书,计划这个阅兵假期看完前两部分,并且总结一下.这也算是突击策略了，要达到长远的效果，还是要多编码，时间有限，不过好在自己的数据结构基础比较牢固，这是考研结束后自己独立编写数据结构基础辅导材料的缘故，这样的话突击看完前两部分，效果应该不会太差。
节省码字消耗的时间，这次读书笔记就尽量简化。尽量用思维导图代替。

数据结构与对象

这一部分的阅读思维导图，基本是根据目录设定的：

Part One

简单动态字符串

动态字符串（SDS）是对C语言字符串的封装，因为C语言字符串是作为字符串常量，也称作字面值来使用，在内存是存在常量区，不可修改，但是Redis还是需要一个可以修改的字面值，于是就是自己封装了一下，称作简单动态字都穿。
SDS用途很广：字符串对象，列表对象，缓冲区（API可以处理溢出）

SDS的定义如下：

struct sdshdr{
	int len;  // 记录字符的长度
	int free; // 记录未使用缓冲区个数
	char buf[]; // 字符数组，存储数据区
}

由于SDS定义可以看出，不用于传统的C字符串是以一个空字符'\0'结尾的，C语言字符串求长度函数strlen()就是依据的这个，所以其时间复杂度是O（N），但是SDS求字符串的长度是常数级别。

同时，SDS定义了自己的API，在内部实现避免溢出，而且还修改字符串（主要是长度修改）时采用了空间预分配和空间惰性释放的策略，避免了内存分配和回收的时间消耗。

最后，由于SDS并不像C字符串是假设以空字符'\0'结尾的，所以，在处理存储二进制的时候就不用担心这个问题了，存储二进制是安全的，而且SDS是与C语言字符串兼容的。

最后，列举SDS的API：

sdsnew 创建一个sds，参数是C语言字符串，时间复杂度O(N)
sdsempty 创建一个空的sds，时间复杂度O(1)
sdsfree 释放给定的sds，时间复杂度O(N)
sdslen 求长度，时间复杂度O(1)
sdsvail 返回可用字节，时间复杂度O(1)
sdsdup 根据一个sds创建一个新的sds，时间复杂度O(N)
sdsclear 轻松保存的字符，时间复杂度O(1)
sdscat 给定的C字符串链接到sds，时间复杂度O(N)
sdscatsds 将一个sds链接到另外一个sds结尾，时间复杂度O(N)
sdscpy 将给定的C字符串复制到sds，时间复杂度O(N)
sdsgrowzero 用空字符串将SDS扩展至给定长度，时间复杂度O(N)
sdsrange 保留范围内的字符，其他的删除，时间复杂度O(N)
sdstrim 给定一个sds和一个C字符串，从sds两端删除在C字符串出现的字符，时间复杂度O(M* N)
sdscmp 比较两个sds是否相同，时间复杂度O(N)

链表

链表是在数据结构中很常用的数据数据逻辑结构，很多高级编程语言都内置了链表，比如Qt,C++里面的STL，但是在C语言里面没有这样的结构，Redis自己定义链表数据结构。

链表节点的数据定义如下：

typedef struct listNode{
	struct listNode* prev; // 指向前一个节点
	struct listNode* next; // 指向后一个节点
	void value;            // 节点的值
}listNode;

链表的定义如下：

typedef struct list{
	listNode* head;
	listNode* tail;
	unsigned long len;
	void* (dup)(void *ptr);
	void (*free)(void *ptr);
	int (*match)(void *ptr,void *key);
}list;

实际上是一个双端队列，并添加了一些其他的属性。

另外，Redis还提供了一些自己的API：

listSetDupMethod 将给定的函数设置为节点值复制函数，时间复杂度为O(1)
listGetDupMethod 返回当前使用的节点值复制韩式指，时间复杂度为O(1)
listSetFreeMethod 将给定的函数设置为节点值释放函数，时间复杂度为O(1)
listGetFree 返回链表当前正在使用的节点值释放函数，时间复杂度为O(1)
listSetMatchMethod 设置链表节点值的对比函数，时间复杂度为O(1)
listGetMatchMethod 返回链表正在使用的节点值对比函数，时间复杂度为O(1)
listLength 获取长度时间复杂度为O(1)
listFirst 返回头节点时间复杂度为O(1)
listLast 返回尾节点时间复杂度为O(1)
listPrevNode 返回前置时间复杂度为O(1)
listNextNode 返回后置节点时间复杂度为O(1)
listNodeValue 返回节点的值时间复杂度为O(1)
listCreate 创建一个不含任何节点的链表时间复杂度为O(1)
listAddNodeHead 在头节点位置田间节点时间复杂度为O(1)
listInsertNode 在给定节点后或前面添加一个节点
listAddNodeTail 在尾部添加节点时间复杂度为O(1)
listSearchKey 查找包含一个值得节点，时间复杂度为O(N)
listIndex 返回给定索引的节点时间复杂度为O(N)
listDelNode 删除给定值的节点时间复杂度为O(N)
listRotate 将尾部节点弹出，作为头节点，时间复杂度为O(1)
listDup 复制一个链表的副本时间复杂度为O(N)
listRelease 释放所有节点时间复杂度为O(N)

字典

字典又称作是符号表，或者MAP（映射），我习惯称作所有的map为映射，其元素是一个成对存在的，一个是键（Key），一个是值（Value）。字典中的键都是独一无二的。

在其他的高级语言中，字典作为基本的数据结构存在，比如在Qt里面，还有C++的STL里面都有，但是在C语言是没有这样的结构的，Redis要使用这样的结构，就自己实现了，而且在Redis里面是，字典被用作数据底层实现，也是哈希键的底层实现(现在我还不清楚哈希键是个什么东西)。

上面说了字典可以被用来做什么，那么字典是由什么做的呢？字典的底层是由哈希表实现的，哈希表是由哈希表节点组成的，有点晕，容易记混了，不过了解其概念和实现能分清楚了。

哈希表节点的定义如下：

typedef struct dictEntry{
	void *key;             // 保存键
	union{                 // 保存值
		void* val;
		uint64_t u64;
		int64_t s64;
	}v;
	struct dictEntry* next;  // 指向下一个节点
}dictEntry;

那么哈希表的实现如下：

typedef struct dictht{
	dictEntry** table;       // 哈希表数组，每个元素是一个哈希表节点的指针（解决哈希冲突时链接地址法）
	unsigned long size;      // 哈希表的大小
	unsigned long sizemask;  // 哈希表掩码，总是= size-1
	unsigned long used;      // 使用节点数量
}dictha;

原材料准备好了，字典的实现是这样构成的：

typedef struct dict{
	dictType *type;   // 方面实现多态，针对不同类型键值对的函数簇，就是函数指针
	void* private;    // 针对这些函数的一些可选参数
	dictht ht[2];     // 保存两个哈希表，主要是h[0]，h[1]用于再哈希
	int rehashidx;    // 渐进再哈希过程中的指标，当==-1时，没有再哈希
}

在注释中我写了自己的理解。

其中这里的函数指针簇定义为数据结构：

typedef struct dictType{
	unsigned int (*hashFunction)(const void* key);  // 哈希函数
	void * (keyDup)(void *privdata,const void *key);  //复制键的函数
	void* (valDup)(void *privdata,const void *obj);   // 复制值得函数
	void (*keyCompare)(void *privdata,const void *key1,const void *key2);  // 比较两个键的值
	void (keyDestructor)(void *privdata,void *key);  // 销毁键的函数
	void (*valDestructor)(void *privdata,void *obj);  // 销毁值得函数
}dictType;

至于哈希表的的哈希函数是MurmurHash函数，解决哈希冲突的方法是链接地址法。

再哈希是为了避免哈希命中率降低的问题，也就是当装填因子超过一定范围的时候，需要修改一下Hash表，这就是两个哈希表的原因，另外一个用于再哈希，至于哈希策略，在书上29页有详细的描述。

渐进哈希是为了避免繁重的服务器消耗，而是把再哈希的过程分散到查找，添加和删除的过程中，rhashidx就是用来渐进过程的。

字典的API在Page36.

跳跃表

这算是一个比较奇怪的数据结构，可以跟双向链表对比着说明：

有一个头节点，双向链表没有；
每个节点有多个前向指针，双向链表只有一个；
这多个前向指针，可以指向任意一个前向的元素，并不局限于前置元素，双向链表的指针只能指向前置元素；
节点数据定义要比双向链表复杂。

跳跃表是一个有序数据结构，效率跟二叉平衡树查不多，但是实现要比二叉平衡树简单。被用作有序集合键的底层实现，另外也被用作集群节点的底层数据结构，用处也就这两个。

条约表节点的定义：

typedef struct zskiplistNode{
	struct zskiplistNode* backward;       // 后向指针
	double score;   // 分值
	robj*obj        // 成员对象
	struct zskiplistLevel{
		struct zskiplistNode* forward;    // 前向指针
		unsigned int span;       // 跨度
	}level[];   // 层
}zskiplistNode;

这个参考书中的图比较好理解，层就是多个前向指针的结构体，跨度用来记录两个节点的距离，分值是用来排序的，若分值相同，则根据对象的字典序排序，后向指针只能指向后置元素。

将多个这样的节点组合在一起就组成了跳跃表，是有头节点的，头节点中，这些属性都是无意义的。

header 指向头节点的指针
tail 指向尾节点的指针
level 所有节点中最大的level（不包括头节点）
length 所有节点的个数（不包含头节点）

再说一下分值和成员对象，这两个是用来排序的，分值是一个double类型的浮点数，分值是可以相同的，但是对象是不能相同的，对象是一个字符串对象，里面封装了SDS，分值相同的时候，用SDS的字典序排序。

API 参考Page 45；

整数集合

整数集是集合键的底层实现方式之一。

Intset

整数集合可以存储三种整数：

int16_t
int32_t
int64_t

整数集合的定义如下：

typedef struct intset{
	uint32_t encoding;      // 编码方式
	uint32_t length;        // 元素个数
	int8_t contents[];      // 数据存储数组
}intset;

整数集合也是有序的，按照其元素值从小到大的顺序，并且是没有重复元素的。

encoding是编码方式，用来指示存储的数据是以上哪三种类型：

INTSET_ENC_INT16 表示存储数据是 int16_t;
INTSET_ENC_INT32 表示存储数据是 int32_t;
INTSET_ENC_INT64 表示存储数据是 int64_t;

升级是比较好玩的设计，整数集合所有的元素必须是同意类型的，若此时是低级（int16_t），那么插入一个int32_t的元素，就会引起升级，所有的元素的空间都开始扩大，原理不好用文字，描述，类似与给定一个字符串，将里面的空格替换成%20，这样的操作，计算好空间从后往前整理。这样的设计是为了节省内存。

但是整数集合没有设计降级操作。

API 参考 P51；

压缩列表

压缩列表是我觉得最麻烦的东西，因为它直接对内存以字节为单位进行处理。

压缩列表是列表键和哈希键的底层实现方式的一种，具体看一下表格吧：

zlbytes	zltail	zllen	entry1	entry2	…	entryN	zlend

zlbytes 4个字节记录整个链表的字节数
zltail 4个字节记录链表的偏移量
zllen 2个字节节点数量
zlend 1个字节特殊字符0xFF用于表示链表结尾。

压缩列表节点的定义用下面的结构描述：

prrevious_entry_length	encoding	content

previous_entry_length 用来表示每个字节的长度，占用一个字节，或5个字节
encoding 用来表示存储数据类型，与后面的content配套使用

在里面最复杂的就是这个每个节点的长度属性，它会引起连锁更新，当然，概率很小。

API列表在P59

对象

前面介绍了几种数据结构，只不过是底层的数据结构而已，但是真正在数据库中使用的还是由这些数据结构组成的对象。

数据结构有：

简单动态字符串
双端链表
字典
压缩链表
整数集合

对象有：

字符串对象
列表对象
哈希对象
集合对象
有序集合对象

根据这些对象的不同，命令决定不同的操作，也就所谓的命令多态。

在Redis里面，对象来组成数据库中的键值对，键和值都是对象，键对象和值对象。

键对象都是字符串对象
值对象可以其五种对象这种的一种

这里来解释一下前面的疑惑，我一开始不知道哈希键是个什么东西，直到看到这一章内容。称作一个键为“某某键”，实际上是这个键对应的值的对象，比如列表键，就是指的该键对应的值是列表对象。
使用 Type命令可以查看一个键对应的值的对象类型

Redis每个对象都是一个redisObject结构体

typedef struct redisObject{
	unsigned type:4;
	unsigned encoding:4;
	void* ptr;
	...
}robj;

其中type表示对象类型，也就是上面的五种对象类型；
encoding表示对象的编码，也就是对象的底层数据结构是由哪几种基本的数据结构实现的。
使用命令OBJECT ENCODING查询对象的编码，也就是底层是什么数据结构实现的。

字符串对象的编码可以是：int，raw，embstr。
字符串的编码转换是：当数字后面连接字符串，int -> raw；当数字长度变大，或者课编辑 embstr -> raw。
字符串命令实现参考P68.

列表对象的编码可以是ziplist，linkedlist。
这里还提到了字符串对象是五种对象中唯一可被嵌套使用的对象。
编码转换：

所有字符串对象长度都小于64字节
对象元素个数小512

不满足两个条件就用linkedList存储，否则用ziplist存储。

哈希对象的编码可以是ziplist 和hashtable；
编码转换：

所有键和值的字符串长度都小于64字节
保存键值对的数量小于512

不满足这个条件，就使用hashtable存储，否则用ziplist存储。

集合对象 的编码可以是intset和hashtable；
编码转换：

所有对象元素都是整数
元素个数不超过512

不满足两个条件用intset存储，否则用hashtable存储。

有序集合对象的编码可以是ziplist和skiplist；
第一个比较好理解，压缩链表，数据是成对存储的，第一个存储对象，第二个存储分值用来排序。
对于skiplist其实是用两种结构结合存储的skiplist和字典，共同组成叫做zset的结构，利用的是两种结构的优点

编码转换：

元素个数少于128个
所有元素的成员都小于64字节

满足条件用ziplist存储，否则用skiplist存储。

命令多态实际上就是在执行名的时候检擦类型，然后调用不同的API。

内存回收和对象共享都是采用引用计数器实现的；

兑现的空转时长就是类似与LRU算法。