一、初识redis

1.1 Redis 简介

redis是一个速度非常快的非关系数据库，它可以存储建与5种不同类型的值之间的映射，可以将存储在内存的键值对持久化到硬盘，可以使用复制特性来扩展读性能，还可以使用客户端分片来扩展写性能。

1.1.1 与其他数据库和其他软件的对比

memcached与redis性能相差无几。redis能够自动以两种不同的方式将数据写入硬盘，并且redis除了能存储普通的字符串之外，还可以存储其他4中数据结构，而memcached只能存储普通的字符串键。redis可以作为主数据库使用，也可以作为其他存储系统的辅助数据库使用。

分片：是一种将数据划分为多个部分的方法，对数据的划分可以基于键包含的ID、基于键的散列值，或者基于以上两者的某种组合。通过对数据进行分片，用户可以将数据存储到多台机器里面，也可以从多台机器里面获取数据，这种方法在解决某些问题时可以获得线性级别的性能提升。

1.1.2 附加特性

持久化：时间点转储（point-in-time-dump），转储操作既可以在“指定时间段内有指定数量的写操作执行”这一条件被满足时执行，又可以通过调用两条转储到硬盘命令中的任何一条来执行；第二种持久化方法将所有修改了数据库的命令都写入一个只追加（append-only）文件里面，用户可以根据数据的重要程度，将只追加写入设置为从不同步（sync）、每秒同步一次或者每写入一个命令就同步一次。
主从复制：执行复制的从父亲会连接上主服务器，接收主服务器发生的整个数据库的初始副本（copy）；之后主服务器执行的写命令，都会被发送给所有连接着的从服务器去执行，从而实时地更新从服务器的数据集。因为从服务器包含的数据会不断地进行更新，所有客户端可以向任意一个从服务器发送读请求，以此来避免对主服务器进行集中式的访问。

1.1.2 使用redis的理由

使用redis而不是memcached来解决问题，不仅可以让代码变得更简短、更易懂、更易维护，而且还可以使代码的运行速度更快，除此之外，在其他多数情况下，redis的效率和易用性也比关系数据库要好得多。
使用redis而不是关系数据库或者其它硬盘存储数据库，可以避免写入不必要的临时数据，也免去了对临时数据进行扫描或者删除的麻烦，并最终概述程序的性能。

1.2 redis数据结构简介

redis是由C语言编写的，redis支持5种数据类型，以K-V形式进行存储，K是String类型，V支持5中不同的数据类型，分别是string，list，hash，set，sorted set。redis底层数据结构有以下数据类型：简单动态字符串（SDS）、链表、字典、跳跃表、整数集合、压缩列表、对象。

1.2.1 redis中的字符串

redis的字符串和其他编程语言或者其他键值存储提供的字符串非常相似。支持三种类型的值

• 字符串

• 整数

• 浮点数

1.2.2 redis中的列表

redis对链表结构的支持使得它在键值存储的世界中独树一帜。

1.2.3 redis的集合

redis的集合和列表都可以存储多个字符串，他们之间的不同在于，列表可以存储多个相同的字符串，而集合则通过使用散列表来保证自己存储的每个紫都城都是各不相同的。

1.2.4 redis的散列

redis的散列可以存储多个键值对之间的映射。和字符串一样，散列存储的值既可以是字符串又可以是数字值，并且用户同样可以对散列存储的数值执行自增操作或自减操作

1.2.5 redis的有序集合

有序集合和散列一样，都用于存储键值对：有序集合的键被称为成员，每个成员都是各不相同的；而有序结合的值则被称为分值，分值必须为浮点数。有序集合的是redis里面唯一一个既可以根据成员访问元素，又可以根据分值以及分值的排序来访问元素的结构

1.2.6 发布订阅

发布与订阅的特点是订阅者负责订阅频道，发送者负责向频道发送二进制字符串消息。每当有消息被发送至给定频道时，频道的所有订阅者都会受到消息。

1.2.7 其他命令

排序

事物
redis的事物通过multi 开始 exec结束，一个接一个的执行命令，最后返回所有命令的执行结果
键的过期时间

第二章 数据安全与性能保障

2.1 持久化选项

redis提供了两种不同的持久化方法来讲数据存储到硬盘里，一种是快照（snapshotting），它可以将存在于某一时刻的所有数据都写入硬盘里面；另一种方法叫只追加文件（append-only file AOF），它会在执行写命令时，将被执行的写命令复制到硬盘里面。这两种方法既可以同时使用，又可以单独使用，在某些情况下甚至两种都不使用。

2.1.1 快照持久化

在新的快照文件创建完毕之前，redis、系统、硬盘三者中的任意一个崩溃，就会丢失最近一次创建的快照之后写入的所有数据。
创建快照的几种办法：

• 客户端可以通过向redis发送bgsave命令创建快照

• 客户端还可以通过向redis发送save命令来创建一个快照，接到save命令的redis服务器在快照创建完毕之前将不再响应任何其他命令。一般不常用，因为会阻塞客户端的响应

• 如果用户设置了save配置选项，当任意一个save配置选项设置的条件被满足时，redis就会触发一次bgsave命令

• 当redis通过shutdown命令接收到关闭服务器的请求时，或者接收到标准term信号时，会执行一个save命令，并在save命令执行完毕后关闭服务器

• 当一个redis服务器连接另一个redis服务器，并向对方发送sync命令来开始一次复制操作的时候，如果主服务器目前没有在执行bgsave操作，或者主服务器并非刚刚执行完bgsave操作，那么主服务器就会执行bgsave命令。

2.1.2 AOF持久化

aof持久化会将被执行的写命令写到aof文件的末尾，以此来记录数据发生的变化。通过 appendonly yes 配置选项打开，appendfsync 配置选项对aof文件同步频率的影响

2.1.3 重写/压缩AOF文件

为了解决AOF文件体积不断增大的问题，用户可以向redis发送bgrewriteaof命令，这个命令会通过移除aof文件中的冗余命令来重写aof文件，使得aof文件的体积变得尽可能小。
可以通过auto-aof-rewrite-percentage和auto-aof-rewrite-min-size来自动执行bgrewriteaof。

2.2 复制

对于有扩展平台以适应更高负载经验的工程师和管理员来说，复制（replication）是不可避免的。redis也采用了同样的方法来实现自己的复制特性，

2.2.1 redis复制的启动过程

表2.2 从服务器连接主服务器时的步骤

从服务器在进行同步时，会清空自己的所有数据，全部替换成主服务器发来的数据
redis不支持主主复制

2.2.2 主从链

从服务器也可以有自己的从服务器，并形成主从链
从服务器对从服务器复制进行复制在操作上和从服务器对主服务器进行复制的唯一区别在于，如果从服务器X拥有从服务器Y，那么当从服务器X在执行表2.2中的步骤4时，它将断开与从服务器Y的连接，导致从服务器Y需要重新连接并重新同步。

2.2.3 检验硬盘写入

为了验证主服务器是否已经将写数据发送至从服务器，用户需要在向主服务器写入真正的数据之后，再向主服务器写入一个唯一的虚构值，然后通过检查虚构值是否存在于从服务器来判断写数据是否已经到达从服务器，这个操作很容易就可以实现。另一方面，判断数据是否已经被保存到硬盘里面则要困难得多。

2.3 处理系统故障

用户必须做好相应的准备来应对redis的系统故障。

2.3.1 验证快照文件和AOF文件

无论是快照持久化还是AOF持久化，都提供了在遇到系统故障进行数据恢复的工具。redis提供了两个命令行程序redis-check-aof和redis-check-dump，它们可以在系统故障发生之后，检查AOF文件和快照文件的状态，并在有需要的情况下对文件进行修复。
redis-check-aof —fix file.aof 会扫描给定的AOF文件，寻找不正确或者不完整的命令，当发现第一个出错命令的时候，程序会删除出错的命令以及位于出错命令之后的所有命令。但是对于快照文件，如果发现错误是无法修复的，因为经过了压缩。

2.3.2 更换故障主服务器

假设A、B两台机器运行redis，A为主服务器，当A发生故障时，用新机器C用作新的主服务器。
首先向B服务器发生save命令，创建快照文件，接着讲快照文件发送给机器V，并在机器V上启动redis，最后让B成为C的从服务器

2.4 redis事务

redis的事务以特殊命令multi开始，之后跟着用户传入的多个命令，最后exec为结束。
延迟执行事务有助于提升性能，发送exec命令后会一次性将命令发送给redis，然后等待所有回复出现，减少交互次数来提升性能。
redis为什么没有实现典型的加锁功能：加锁有可能会造成长时间的等待，redis为了尽可能地减少客户端的等待时间，并不会在执行watch命令时对数据进行加锁，只会在其他客户端修改了的情况下通知watch命令客户端，这种做法被称为乐观锁。

第三章 数据类型底层数据结构实现

redis底层数据结构有以下数据类型：简单动态字符串（SDS），链表，字典，跳跃表，整数集合，压缩列表，对象。

3.1 简单动态字符串（simple dynamic string SDS）

string的数据类型是由SDS实现的。redis没有采用C语言的字符串表示，而是自己构建了一种名为SDS的抽象类型，并将SDS作为redis的默认字符串表示。
set msg “hello world”
key=msg，value=”hello world”的键值对，它们的底层存储是：键（可以）是字符串类型，其底层实现是一个保存着“msg”的SDS。值（value）是字符串类型，其底层实现是一个保存着”hello world”的SDS
注意：SDS除了用于实现字符串类型，还被用作AOF持久化时的缓冲区
SDS的定义为：

/*  
 * 保存字符串对象的结构  
 */  
struct sdshdr {  
    // buf 中已占用空间的长度  
    int len;  
    // buf 中剩余可用空间的长度  
    int free;  
    // 数据空间  
    char buf[];  
};

为什么要用SDS：
C语言用N+1的字符数组来表示长度为N的字符串，这样做在获取字符串长度，字符串扩展等操作方面效率较低，并且无法满足redis对字符串在安全性、效率以及功能方面的要求。
获取字符串长度（SDS O（1））
在C语言中，为了获取一个字符串的长度，必须遍历整个字符串，时间复杂度为O（n），而SDS中，有专门用于保存字符串长度的变量，所以可以在O（1）时间内获得
防止缓冲区溢出
C字符串，容易导致缓冲区溢出，假设内存中紧邻的字符串s1和s2，s1保存redis，s2保存MongoDB，如果我们将s1修改为redis cluster，但忘记为s1重新分配足够的空间，因为s1和s2是紧邻的，原本s2中的内容被s1给占了，而redis中的SDS就杜绝了发生缓冲区溢出的可能。
当我们需要对SDS进行修改的时候，redis会在执行拼接的操作之前，预先检查给定SDS空间是否足够（free 记录了剩余可用的数据长度），如果不够，会先拓展SDS的空间，然后再执行拼接操作。
减少扩展或收缩字符串带来的内存重新分配次数
当字符串进行扩展或收缩时，都会对内存空间进行重新分配。
1）字符串拼接会产生字符串的内存空间的扩展，在拼接过程中，原来的字符串大小很可能小于拼接后的字符串大小，那么这样的话，就会导致一旦忘记申请分配空间，就会导致内存的溢出。
2）字符串在进行收缩的时候，内存空间会相应的收缩，而如果在进行字符串的切割的时候，没有对内存的空间进行一个重新分配，那么这部分多出了的空间就成了内存泄露。

比如：字符串”redis”，当进行字符串拼接时，redis+cluster=13，会将SDS的长度修改为13，同时将free也修改为13，这意味着进行预分配了，将buffer大小变为了26，这是为了如果再次出现字符串拼接操作，如果拼接的字符串长度<13，就不需要重新进行内存分配了。

通过这种预分配策略，SDS将连续增长N此字符串所需的内存重分配次数从必定N次降低为最多N次。通过惰性空间释放，SDS避免了缩短字符串时所需的内存重分配操作，并为将来可能可能有的增长操作提供了优化。
二进制安全
C字符串中的字符必须符合某种编码，并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串结尾，这些限制使得C字符串只能保存文本数据，而不能保存像图片、音频、视频、压缩文件这样的二进制数据。
在redis中，不是靠空字符来判断字符串的结束的，而是通过len这个属性。即便是出现了空字符，对于SDS来说，读取该字符仍然是可以的。SDS依然可以兼容部分C字符串函数。

3.2 链表

链表是list的实现方式之一。当list包含了数量较多的元素，或者列表中包含的元素都是比较长的字符串时，redis会使用链表作为实现list的底层实现。此链表是双向链表：

typedef struct listNode{
      struct listNode *prev;
      struct listNode * next;
      void * value;  
}

list

typedef struct list{
    //表头节点
    listNode  * head;
    //表尾节点
    listNode  * tail;
    //链表长度
    unsigned long len;
    //节点值复制函数
    void *(*dup) (void *ptr);
    //节点值释放函数
    void (*free) (void *ptr);
    //节点值对比函数
    int (*match)(void *ptr, void *key);
}

链表结构的特点是可以快速的在表头和表尾插入和删除元素，但是查找复杂度高，是列表的底层实现之一，也因此列表没有提供判断某一元素是否在列表中的接口，因为在链表中查找复杂度高。

3.3 字典

字典，又称为符号表、关联数组或映射，是一种用于保存键值对的抽象数据结构。
在字典中，一个键（key）可以和一个值（value）进行关联，字典中的每个键都是独一无二的。在C语言中，并没有这种数据结构，C语言并没有这种数据结构，redis中构建了自己的字典实现。
redis本身的K-V存储就是利用字典这种数据结构的，另外value类型的哈希表也是通过这个实现的。
哈希表dicy的定义为：

typedef struct dictht {
   //哈希表数组
   dictEntry **table;
   //哈希表大小
   unsigned long size;
   //哈希表大小掩码，用于计算索引值
   unsigned long sizemask;
   //该哈希表已有节点的数量
   unsigned long used;
}

dictht中，table数组的类型是：

typeof struct dictEntry{
   //键
   void *key;
   //值
   union{
      void *val;
      uint64_tu64;
      int64_ts64;
   }
   struct dictEntry *next;
}

我们存入里面的key并不是直接的字符串，而是一个hash值，通过hash算法，将字符串转换成对应的hash值，然后在dictEntry中找到对应的位置。
这时候我们会发现一个问题，如果出现hash值相同的情况怎么办？redis采用了链地址法来解决hash冲突。这与hashmap的实现类似。

typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privedata;
    // 哈希表
    dictht  ht[2];
    // rehash 索引
    in rehashidx;
}

type属性和privdata属性是针对不同类型的键值对，为创建多态字典而设置的。ht属性是一个包含两个项的数组
解决Hash冲突：采用链地址法来实现
扩充rehash：随着对哈希表的不断操作，哈希表保存的键值对会逐渐的发生改变，为了让哈希表的负载因子维持在一个合理的范围之内，我们需要对哈希表的大小进行相应的扩展或者压缩，这时候，我们可以通过rehash（重新散列）操作来完成，其实现方式和hashmap略有不同，因为dict有两个hash表dictht，所以它是通过这两个dictht互相进行转移的（扩容的时候在ht[0]和ht[1]直接进行复制，复制目标会扩展为源的两倍大小）。
渐进式rehash：在实际开发过程中，这个rehash操作并不是一次性完成的，而是分多次、渐进式完成的。采用渐进式rehash的好处在于它采取分而治之的方式，避免了集中式rehash带来的庞大计算量。详细步骤：
1、为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个hash表
2、将rehashidx的值设置为0，表示rehash开始
3、在rehash期间，每次对字典执行CRUD操作时，程序除了执行指定的操作以外，还会降ht[0]中的数据rehash到ht[1]表中，并且将rehashidx加1
4、当ht[0]中所有数据转移到ht[1]中时，将rehashidx设置成-1，表示rehash结束

3.4 跳跃表

redis只在两个地方用到了跳跃表，一个是实现有序集合键（sorted sets），另外一个是在集群节点中用作内部数据结构。
其实跳表主要是用来替代平衡二叉树的，比起平衡树来说，跳表的实现要简单直观的多
跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速查找访问节点的目的。跳跃表是一种随机化的数据，跳跃表以有序的方式在层次化的链表中保存元素，效率和平衡树媲美-查找、删除、添加等操作都可以在O（logn）期望时间下完成。
redis的跳跃表主要有两部分组成：zskiplist（链表）和zskiplistNode（节点）：

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

1、层：level数组可以包含多个元素，每个元素都包含一个指向其他节点的指针。level数组的每个元素都包含：前进指针；用于指向表尾方向的前进指针，跨度：用于记录两个节点之间的距离

2、后退指针：用于表尾向表头方向访问节点

3、分值和成员：跳跃表中的所有节点都按分值从小到大排序（按照这个进行排序的，也就是平衡二叉树（搜索树）的节点大小）。成员对象指向一个字符串，这个字符串对象保存着一个SDS值（实际存储的值）

typedef struct zskiplist {  
     //表头节点和表尾节点  
     structz skiplistNode *header,*tail;  
     //表中节点数量  
     unsigned long length;  
     //表中层数最大的节点的层数  
     int level;  
}zskiplist;

从结构图可以清晰的看到，header,tail分别指向跳跃表的头结点和尾节点。level用于记录最大的层数，length用于记录我们的节点数量

• 跳跃表是有序集合的底层实现之一

• 主要有zskiplist和zskiplistNode两个结构组成

• 每个跳跃表节点的高层都是1至32之间的随机数

• 在每个跳跃表中，多个节点可以包含相同的分值，但每个节点的对象必须是唯一的

• 节点按照分值的大小从大到小排序，如果分值相同，则按成员对象大小排序

怎么通过跳跃表来实现O（logn）的增删改查？
如果我们需要查找某个数，需要从头开始遍历，所以在数组实现中，我们可以使用二分法来实现，但是在链表中，我们没办法直接通过下标来访问元素，所以一般我们可以用二叉搜索树，平衡树来存储元素，我们知道跳表就是来替代平衡树的，那么跳表是如何快速查询呢？

从上图我们可以看到，通过第4层，只需一步就可以找到55，另外最耗时的访问46需要6次查询。即L4访问55，L3访问21/25，L2访问37/55，L1访问46。我们直觉上认为，这样的结构会让查询有序链表的某个元素更快，这种实现方式跟二分法很相似，其时间复杂度就是O（logn）。其插入、删除都是O（logn）。
我们可以看到，redis正是通过定义这种结构来实现上边的过程，其层数最高为32层，也就是他可以存储2^32次方的数据，其查找过程与上图很类似。

3.5 整数集合（Intset）

整数集合是集合键（sets）的底层实现之一，当一个集合中只包含整数，且这个结婚中的元素数量不多时，redis就会使用整数集合intset作为集合的底层实现。

typedef struct intset{
    //编码方式
    uint32_t enconding;
   // 集合包含的元素数量
    uint32_t length;
    //保存元素的数组    
    int8_t contents[];
}

整数集合的底层实现为数组，这个数组以有序、无重复的范式保存集合元素，在有需要时，程序会根据新添加的元素类型改变数组的类型。

3.6 压缩列表

压缩列表是列表键（list）和哈希键（hash）的底层实现之一。当一个列表键只有少量列表项，并且每个列表项要么就是小整数，要么就是长度比较短的字符串，那么redis就会使用压缩列表来做列表键的底层实现。

1. zlbytes：用于记录整个压缩列表占用的内存字节数

2. zltail：记录列表表尾节点距离压缩列表的起始地址有多少字节

3. zllen：记录压缩列表包含的节点数量

4. entryX：列表包含的各个节点

5. zlend：用于标记压缩列表的末端

压缩列表是一种为了节约内存而开发的顺序型数据结构
压缩列表被用做列表键和哈希键的底层实现之一
压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值
添加新节点到压缩列表，可能会引发连锁更新操作

参考列表：
https://blog.csdn.net/u013679744/article/details/79195563