1. String(SDS)
Redis使用自定义的一种字符串结构SDS来作为字符串的表示。
127.0.0.1:6379> set name liushijie
OK
在如上操作中，name(key)和liushijie(key)就存储在SDS中。
SDS数据结构如下：
struct sdshdr {
// 所保存字符串的长度
int len;
// 未使用字节长度
int free;
// 字节数组，保存字符串
char buf[];
};
SDS遵循C字符串以'\0'空字符串结尾的惯例，所以buf的内部值为
'l' 'i' 'u' 's' 'h' 'i' 'j' 'i' 'e' '\0'，但是空字符串不算在len中，即在上面的例子中字符串的长度为9，而不是10，所以这个空字符对SDS使用者是完全透明的。这么写的好处是SDS可以直接重用一部分C字符串函数库的函数。
SDS与C字符串的区别
- SDS获取字符串长度时间复杂度为O(1)，C字符串为O(N)
杜绝缓冲区溢出
SDS在执行字符串赋值时会检查剩余空间是否足够，不够的话会先扩展SDS的空间，然后才执行赋值操作。
C不会检查，有造成溢出的风险。
减少修改字符串
通过未使用空间SDS提供了空间预分配和惰性空间释放两种优化策略
空间预分配策略：
额外分配的未使用空间数量由以下公式：
如果修改后的SDS的len小于1MB，那么程序分配和len属性同样大小的未使用空间，这时len = free
如果修改后的SDS的len大于1MB，那么程序会分配1MB的未使用使用空间
在扩展SDSk空间之前，如果足够的话，API就会直接使用未使用空间，而无须执行内存重分配。
惰性空间释放：
惰性空间释放用于优化SDS的字符串缩短操作：当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用回收要缩短的字节，而是使用free属性的将这些字节的数量记录起来。
4. 二进制安全
因为Redis SDS结构不会截断'\0'空字符，所以SDS结构不仅可以保存文本数据，也可以保存二进制数据。
2. 链表
链表的简单使用：
127.0.0.1:6379> rpush footmark jiamusi harbin dalian shenzhen beijing shenyang
(integer) 6
127.0.0.1:6379> llen footmark
(integer) 6
127.0.0.1:6379> lrange footmark 0 5
- "jiamusi"
"harbin"
"dalian"
"shenzhen"
"beijing"
"shenyang"
使用链表的相关实现：
列表键
发布与订阅
慢查询
监视器
...
链表的数据结构：
// 链表节点
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
// 整个链表
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链表的特性：
双向
无环
带表头、表尾指针
带链表长度计数器
多态
3. 字典
字典，又称符号表、关联数组或映射（map），是一种保存键值对的抽象数据结构。
每个键都是独一无二的，程序可以在字典中根据键查找与之关联的值，或者通过键来更新值，又或者根据键来删除整个键值对，等等。
- 字典的实现
Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。（注：结构算法其实相当于一个hashmap）
// 哈希表
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
// 哈希表节点
typedef struct dictEntry {
// 键
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
// 指向下个哈希表节点，形成单向链表
struct dictEntry *next;
} dictEntry;
// 字典
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
int iterators; /* number of iterators currently running */
} dict;
typedef struct dictType {
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使用MurmurHash2算法来计算键的哈希值。（注：算法相关 http://code.google.com/p/smhasher/）
解决键冲突
使用链地址法来解决键冲突。如果发生冲突，程序将新节点加在链表的表头位置。可以参考hashmap的实现。
rehash
rehash用来扩展和收缩哈希表。
rehash触发条件如下：
+ 服务器目前没有在执行
BGSAVE命令或者BGREWRITERAOF命令，并且哈希表的负载因子大于等于1；+ 服务器目前正在执行
BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负责因子大于等于5。rehash步骤如下：
为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量：
扩展操作：ht[1]的大小为第一个大于等于ht[0].used*2的2^n；
收缩操作：ht[1]的大小为ht[0].used的2^n。
将保存在ht[0]中所有的键值对rehash到ht[1]上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。
ht[0]包含的所有键值对都迁移到了ht[1]之后，释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备。
渐进式rehash
rehash动作不是一次性、集中式地完成的，而是分多次、渐进式地完成的。详细步骤：
为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。
在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始。
在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的索引键值对rehash到int[1]，当rehash工作完成后，程序将rehashidx变量的值增一。
随着字典操作的不断执行，最终在某个时间点，ht[0]的所有键值对都会被rehash至ht[1]，这时设置rehashidx变量的值设置为-1，表示rehash操作完成。
渐进式rehash执行期间的哈希表操作：
在进行渐进式rehash的过程中，字典会同时使用ht[0]和ht[1]两个哈希表，所以在渐进式rehash进行期间，字典的删除、查找、更新等操作会在两个哈希表上进行。
在渐进式rehash执行期间，新添加到字典的键值对一律会被保存到ht[1]里面，而ht[0]则不再进行任何添加操作，这一措施保证了ht[0]包含的键值对数量会只减不增，并随着rehash操作的执行而最终变成空表。
4. 跳跃表
跳跃表(skiplist)是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。
在Redis中有两个地方用到了跳跃表：实现有序集合键和用作内部数据结构的集群节点。
跳跃表的实现
// 跳跃表节点
typedef struct zskiplistNode {
// 成员对象
robj *obj;
// 分值：节点按各自保存的分值从小到大排列
double score;
// 后退指针
struct zskiplistNode *backward;
// 层
struct zskiplistLevel {
// 前进指针：用来访问表尾的其他节点
struct zskiplistNode *forward;
// 跨度：记录了前进指针所指向节点和当前节点的距离
unsigned int span;
} level[];
} zskiplistNode;
// 保存跳跃表节点的相关信息
typedef struct zskiplist {
// header：指向跳跃表的表头节点，tail：执行跳跃表的表尾节点
struct zskiplistNode *header, *tail;
// 跳跃表的长度
unsigned long length;
// 层数最大的那个节点的层数
int level;
} zskiplist;
5. 整数集合
整数集合(intset)是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。
- 整数集合的实现
typedef struct intset {
// 编码方式：用来决定contents属性的数值类型
uint32_t encoding;
// contents数组的长度
uint32_t length;
// 保存元素的数组，各个项在数组中按值的大小从小到大有序排列，并且数组不包含任何重复项
// 虽然intset结构将contents属性声明为int8_t类型的数组，但是实际上contents并不保存任何类型int8_t类型的值，content数组的真正类型取决于encoding的值
int8_t contents[];
} intset;
- 升级
将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级，然后才能将新元素添加到整数集合里。
升级的好处：
- 提升灵活性
节约内存
升级整数集合并并添加新元素共分为三步进行：
根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放在正确的位上，而且在放置元素过程中，维持底层数组有序性质不变。
将新元素添加到底层数组里。
降级
不支持降级。
6. 压缩列表
压缩列表(ziplist)是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做列表键的底层实现。
例如：
127.0.0.1:6379> rpush lst 1 2 4 "a" "b"
(integer) 5
127.0.0.1:6379> object encoding lst
"ziplist"
127.0.0.1:6379> hmset profile a 1 b 2
OK
127.0.0.1:6379> object encoding lst
"ziplist"
- 压缩列表的构成
压缩列表是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表尅包含任意多个几点，每个节点可以保存一个字节数组或者一个整数值。
| 压缩列表的各个组成部分 |
zlbytes : 记录整个压缩列表占用的内存字节数
zltail：记录压缩列表表尾节点距离压缩列表的起始地址有多少字节
zllen：记录了压缩列表包含的节点数量
entryN：压缩列表包含的各个节点，节点的长度由节点保存的内容决定
zlend：特殊值，用于标记压缩列表的末端
- 压缩列表节点的构成
|
------------------- | --
压缩列表节点的各个组成部分| previous_entry_length | encoding | content
previous_entry_length：记录前一个节点的长度
encoding：记录了节点的content属性所保存数据的类型以及长度
content：保存节点的值。值可以是字节数组或者整数，值的类型和长度由encoding决定
- 连锁更新
添加或删除节点可能会引起连锁更新。
7. 对象
Redis并没有直接使用之前介绍的基本数据结构（SDS/LIST/MAP等）来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象。
对象的好处
通过这五种不同类型的对象，Redis可以在执行命令前，根据对象的类型来判断一个对象是否可以执行给定的命令。多种不同的数据结构实现，从而优化。
- 对象的类型与编码
Redis中的每个对象都由一个redisObject结构表示，和保存数据有关的三个属性分别是type encoding ptr，具体的数据结构如下：
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;
type（常量）：记录了对象的类型，使用命令type key可以查看对象类型：
127.0.0.1:6379> set msg "hellow world"
OK
127.0.0.1:6379> type msg
string
ptr：指向对象的底层实现数据结构，这些结构由对象的encoding决定。
encoding（常量）：记录了对象所使用的编码，即是用了什么数据结构作为对象的底层实现。使用命令object encoding key可以查看一个数据库键的值对象的编码：
127.0.0.1:6379> set msg "liushijie"
OK
127.0.0.1:6379> object encoding msg
"raw"
- 字符串对象
字符串对象可以保存字符串数据，也可以保存整数值类型和long double类型的浮点数，并能提供数值运算。字符串的编码可以是int、raw或embstr。
常用命令：
set get append incrbyfloat incrby decrby strlen setrange getragne
- 列表对象
列表对象的编码可以是ziplist或者linkedlist
常用命令：
lpush rpush lpop rpop lindex llen linsert lerm ltrim lset
- 哈希对象
哈希对象的编码可以是ziplist或者hashtable
常用命令：
hset hget hexists hdel hlen hgetall
- 集合对象
集合对象的编码可以是inset或者hashtable
常用命令：
sadd scard sismember smembers srandmember spop srem
- 有序集合对象
有序集合的编码尅是zipist或者skiplist
常用命令：
zadd zcard zcount zrange zrevrange zrank zrevrank zrem zscore
类型检查与命令多态
Redis用于操作键的命令基本可以分为两种类型：
可以对任何类型的键执行，比如del、expire、rename、type、object等
只能对特定类型的键执行，比如：set、get、append、strlen等命令只能对字符串键执行；
类型检查： 在执行一个类型特定的命令之前，Redis会先检查输入键的类型是否正确，然后再决定是否执行给定的命令。类型特定命令所进行的类型检查是通过redisObject结构的type属性来实现的。成功则执行，失败则返回类型错误。
多态命令 无论输入的键是什么类型，命令都可以正确的执行。一个命令可以同时用于处理多种不同的编码。
内存回收
Redis在自己的对象系统中构建了一个引用计数技术实现的内存回收机制，程序可以通过跟踪对象的引用计数信息，在适当的时候自动释放对象并进行内存回收。
每个对象的引用技术信息由redisObject结构的refcount属性记录。
对象共享
对象共享是将数据库的键的值指针指向一个现有的值对象，被共享的值对象的引用计数增一。
对象共享可以节省内存。
对象的空转时长
redisObject结构中包含的最后一个属性为lru属性，该属性记录了对象的最后一次被命令程序访问的时间。object idletime命令可以打印给定的键的空转时长，空转时长是通过将当前时间减去键的值对象的lru时间计算出来的。
127.0.0.1:6379> set msg liushijie
OK
127.0.0.1:6379> object idletime msg
(integer) 11
object idletime不会修改lru属性。
空转时长的其他作用：
如果服务器打开了maxmemory选项，并且服务器用于回收内存的算法为volatile-lru或者allkeys-lru，那么服务器占用的内存数超过了maxmemory选项设置的上线时，服务器会优先释放空转时长较高的那部分键。
Redis命令速查
Redis学习笔记之ABC的开头部分。
