Redis设计与实现读书笔记

数据结构部分

字符串（SDS）

数据结构为如下：

struct sdshdr{
//记录bug中已经使用了的长度
  int len;
//记录buf中没有使用的长度
  int free;
//字节数组，用于保存字符串 
  char buf[];
}

优点：

• 可以以常数复杂度获取字符串的长度，因为记录了字符串的长度。
• 通过free空间可以减少字符串修改时带来的内存重新分配次数。   Redis里修改sdshdr的时候会对buf进行扩容，扩容的方式当buf小于1MB的时候是翻倍扩容，当大于1MB的时候是以1MB大小进行扩容。当需要对buf进行减字符操作时，不会对buf数组进行缩减，而是通过len与free的改值来实现。称为惰性空间释放，这样可以避免内存重新分配。
• 内部API杜绝了缓冲区溢出。
• 二进制安全的，因为len记录了buf的长度，而不是像C语言一样通过一个空字符来判断是否到字符的未位。
• 在buf里存字符的时候还是加上了空字符串的，这样可以兼容部分C字符串的函数。

链表

数据结构由两部分组成listNode与list，分别如下：

typedef struct listNode{
//前置节点
  struct listNode *prev;
//后置节点
  struct listNode *next;
// 节点的值
  void *value;
}listNode;

typedef struct list{
//链表头节点
  listNode *head;
//链表尾节点
  listNode *tail;
//链表长度
  unsigned long len;
}list;

特点：

• 节点通过prev和next指针实现双端链表
• 表头节点的pre与表属节点的next都指向NULL,不是个循环链表，对链表的访问会以NULL结束
• list带表头与表尾指针，程序可以快速的获取表头与表尾。 +通过len属性可以快带的获取链表的长度。

字典（HashMap）

  Redis底层的数据库采用的就是这种结构，还有哈希键的底层实现之一也是采用HashMap这种结构。 哈希表的节点结构如下：

typedef struct dictEntry{
//键
  void *key;
//值 
union{
  void *val;
  uint64_t u64;
  int64_t s64;
}v;
//指向一个哈希表的节点
struct dictEnty *next;
}dictEnty 

哈希表的结构定义如下：

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

哈希表通过数组来存储数据，通过sizemask与key的hashcode来计算数据存储的位置。当hashcode值相同时，采用的是链表的方式进行存储。   Redis的字典设计成有两个dictht的数组结构，这样设计的好处是可以采用渐进的方式对字典数据进行扩容。所谓渐进式的进行rehash指的是在rehash的过程中并不是一步完成的，在rehash的时候同时也能对外提供添加，查找，更新与删除的功能。只是在这些功能完成的时候会将相应的数据从dictht的一个哈希表移动到新的dictht表中。rehash过程中增，删，改，查这四个操作，只有增加数据是在新的dictht中，另外三个操作都要同时操作两个dictht。 优点：

• Redis的字典是数据库的底层实现，采用双哈希表的设计能在扩容时还能对象提供相应的数据查找，修改，增加与删除的功能。这是Redis哈希结构设计的亮点之一。
• Redis采用链表的方式来解决hashcode冲突的问题。

跳跃表

  跳跃表是一种有序数据结构，通过在每个节点维持多个指向其它节点的指针来达到快速访问其它节点的目地。在Redis里有序节点采用的是这种数据结构来进行实现。跳跃表节点的数据结构如下：

typedef struct zskiplistNode{
//后退指针
  struct zskiplistNode *backward;
//分值，节点以这个值从小到大进行排序
  double score;
//成员对象
  robj *obj;
//层
struct zskiplistLevel{
     //前进指针
    struct zskiplistNode *forward;
    //跨度
    unsigned int span;
  } level[];
}zskiplistNode;

这里需要重点关注的是 level[]数组，他用于表示层信息，层里包括两部分信息，指向的节点指针以及当前节点与指向节点的跨度信息。有了节点就可以组成一张跳跃表了，跟链表一样，Redis通过提供zskiplist结构来操作跳跃表的信息，数据结构如下：

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

整数集合

  整数集合是集合键的底层实现之一，条件为：1：集合中只包含整数，2：集合的元素数量不多。数据结构的定义如下：

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

上面的定义contents数组声明的是int8_t类型，实际上contents保存的类型取决于encoding属性。当向整数集合里增加一个超过当前编码的值的时候，会引发升级操作，所谓的升级就是对当前的整数进行扩容。这样做的好处主要是为了节约内存。整数集合的特点有下面几个：

• 整数集合是有序无重复的特点。
• 在有需要的时候，会根据增加数据的类型对数据进行升级操作。
• 整数集合数据量不大，所以升级操作耗时不会太多
• 整数集合不支持降级操作

压缩列表

  压缩列表是列表键和哈希键的底层实现之一。压缩列表是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型 数据结构。压缩列表的组成如下图所示：

上图中括号里记录的是对应位置所占用的字节数。里面的entry的值结构如下图所示：

因为previous_entry_length的长度不固定，会有连锁更新的情况发生。

对象

  Redis数据库基于上面的数据结构创建了一个对象系统，这个系统包括：字符串对象，列表对象，哈希对象，集合对象，有序集合对象。在 Redis里每新建一个键值对会创建两个对象，分别为键对象与值对象。每个对象都由redisObject结构表示：

typedef struct redisObject{
//类型
  unsigned type;
//编码,底层数据结构
  unsigned  encoding;
//指向底层实现数据结构的指针
  void *ptr;
//引用计数器 通过OBJECT REFCOUNT 可以查看
  int refcount;
//空转时长 通过OBJECT IDLETIME 可以查看
unsigned lru; 
}robj;

其中type值只有五种类型，分别为：string，list，hash，set，zset，可以通过TYPE key得到对象的类型。而encoding用于标识底层的数据结构，可能通过OBJCET ENCODING key来查看某个值对象的底层结构。encoding可能的输出为：int，embstr, raw，hashtable，linkedlist，ziplist，intset，skiplist。

字符串对象

  字符串的编码可能是int, embstr, raw这三种之中的一种。为int的情况是存的这个整数值可以用long类型(浮点数不在这个范围内)来表示。当存的值长度小于39字节的时候，采用的是embstr结构来存储，其它情况采用的是raw方式存储。embstr与raw的区别为：embstr专门用于存储短字符串，主要是为了在创建对象的时候只需要调用一次内存分配函数。embstr的结构如下图所示：

int类型的数据在操作的时候比如变成了浮点数会转成raw类型的编码。embstr只要有修改的操作，无论长度多少都会变成raw类型的编码。

列表对象（里面的元素允许重复）

  列表对象的编码可能是双端链表或者压缩列表。当列表对象同时满足所有字符串的长度都小于64字节且元素数量小于512个时，采用的是压缩列表的方式。其它情况采用双端列表来进行存储。

哈希对象

  哈希对象的编码可以是压缩列表或者hashtable 。只有当哈希对象保存的键值对的键和值的字符串都小于64字节且对象 保存的键数量小于512个，才使用压缩列表的方式进行存储，其它情况采用的是hashtable。当采用压缩列表来存储时有如下特点：

• 保存同一个键值对的两个节点总是紧挨在一起，键的节点在前，值的节点在后。
• 增加键值对放到压缩列表表尾。

集合对象

  集合对象的编码可以是intset或者hashtable来实现。使用intset的条件为集合中的所有元素全为整数值且对象保存的元素数量不超过512 个。采用hashtable的方式来保存的数据值为NULL,

有序集合对象

  有序集合对象可以采用压缩列表或者跳跃表加字典的方式来实现。 当保存的元素小于128个且元素长度都小于64个字节采压缩列表的方式来保存，压缩列表内在元素按分值大小进行排序，分值小的靠近表头，每个元素占用两个节点，第一个节点保存值，第二个节点保存分值。其它情况用用的是zset的结构来保存数据。zset结构如下：

typedef struct zset{
  //跳跃表指针
  zskiplist *zsl;
//字典
dict *dict;
}zset;

通过跳跃表可以对有序集合进行范围操作，而通过字典建立了元素到分值的映射，通过字典Redis可以快速的查找某个元素的分值。有序集合中每个元素都是字符串对象，每个元素的分值都是double类型的浮点数。虽然zset同时采用跳跃表与字典来保存有序集合，但他们会通过指针来共享相同元素的成员与分值

键的生存时间

  Redis里可能通过 EXPIRE，PEXPIRE，EXPIREAT，PEXPIREAT四个命令来设置键的过期时间，其中以P开头的命令设置的时间单位是毫秒。EXPIRE，PEXPIRE，EXPIREAT内部最终会转成PEXPIREAT命令。在Redis内部通过字典（expires变量）保存设置了过期时间的对象，其中字典中的键是一个指针，指向键空间中的某个键对象，字典的值为一个long类型的整数，保存了过期时间。PERSIST命令用移除键的过期时间，TTL与PTTL命令用于查看键还有多长时间过期。上面几个命令都是围绕着redisDB里的expire变量来进行操作的。   Redis对于过期键的处理采用的是惰性删除与定期删除两种方式。惰性删除通过拦截所有读写请求，判断键是否有过期，如果过期则执行删除逻辑。定期删除是通过Redis的定时任务来完成的。

持久化

RDB持久化

  Redis的是内存数据库，一旦进程退出，数据状态便没了。Redis为了解决这个问题，提供了RDB持久化方案。可以通过SAVE或者BGSAVE两个命令来手动生成RDB文件。两个命令的区别为SAVE命令是阻塞的，BGSAVE是通过子进程来生成RDB。Redis没有提供任何载入RDB文件的命令，而是在启动的时候会直接载入RDB文件，载入的顺序为AOF文件优先，如果没开启AOF功能，则使用RDB文件的方式。可以通过提供配置让Redis在满足一定的条件时自动执行BGSAVE命令，配置方式如下：

save 900 1
save 300 10

上面的配置含义为当900秒内对数据库执行了一次修改或者300秒内对数据库执行了10次修改便会执行BGSAVE命令。   Redis通过在redisServer对象上保存saveparams数组对象，修改记数器和上次执行保存的时间三个参数来判断是否执行BGSAVE命令。相关数据结构如下：

struct redisServer{
   //记录了保存条件的数组
  struct saveparam *saveparams;
//修改记数器
  long dirty;
//上一次执行保存的时间
time_t lastsave;
//AOF缓冲区
sds aof_buf;
};

struct saveparam{
  //秒数
  time_t seconds;
//修改数
  int changes;
};

AOF持久化

  AOF持久化通过保存Redis服务器所执行的写命令来记录数据库的状态。AOF的持久化实现可以分为命令追加，文件写入，文件同步三个步骤。

• 命令追加：当redis执行了一个写命令以后，会将命令写入到redisServer里的 aof_buf缓冲区里。这时候命令并没有写入到AOF文件中。
• 文件写入与同步：Redis服务器每次接收服务器的请求后都会执行flushAppendOnlyFile函数，在这个函数里会根据appendfsync配置的值不同采用不同的处理方式将aop_buf里的内容写入到内存缓存并同步。appendfsync可以取always，everysec，no。 1)always表示将缓冲区的内容写入并同步到AOF文件。（理论上可能丢失一次事件循环命令行的数据）。 2)everysec表示每秒钟同步一次（这样会丢失一秒钟的数据）。 3)no表示将数据写入到AOF内存缓存，但是何时同步由操作系统决定。

AOF重写

  AOF重写主要是为了解决AOF文件过大的问题。重写的步骤大概如下： 1：创建新的AOF文件 2：遍历数据库，并逐个选择库来进行重写 3：忽略过期的键。 4：根据不同键的类型对键进行重写 5：如果键有过期时间，将过期时间进行重写。   整个重写过程可能需要花费大量时间，而重写的过程中Redis是能接收客户端的请求的，而后台重写用于解决这个问题。后台重写需要解决客户端在重写期间执行的写命令需要写入到新的AOF文件里。 Redis重写是通过子进程来实现的，而服务进程需要执行以下三个工作： 1：执行客户端发送来的命令。 2：将执行后的写命令追加到aof缓冲区。 3：将执行后的写命令追加到AOF重写缓冲区。 当子进程完成AOF文件重写后，会给服务进程发送信号，服务进程需要将AOF重写缓冲区的内容写入到新的AOF文件里，并用新的AOF文件替换掉旧的AOF文件。这就完成了后台AOF文件重写，在服务进程接到信息之后的过程是阻塞的，这大大降低了服务阻塞的时间。

多机数据库的实现

复制

  在Redis中通过SLAVEOF IP PORT命令，可以让一台服务器设为另一台服务器（主服务）的slave。slave服务器能提供除写入功能外的其它功能，slave服务器相当于主服务器的一个镜像。这一切都是通过Redis的复制功能实现的，复制功能分为两步：

• 同步：将从服务器的状态更新到主服务器当前所处的状态。
• 命令传播：主服务器有更新命令时会将命令传给从服务器，使主从保持数据一致。

  Redis2.8以后为了提升断线后重复制的效率，提供了PSYNC命令来替换原有的SYNC命令。PSYNC能够实现部分数据重同步，实现的原理是主服务器记录了1：复制的偏移量；2：复制积压缓冲区（可以通过repl-backlog-size设置大小）3:服务器运行的ID。从服务器记录了主服务器的ID与复制的偏移量。主服务器根据服务器的ID与偏移量来决定是否可以进行部分重同步。流程如下：

PSYNC执行时可能遇到的情况

在复制操作刚开始的时候，从服务器会成为主服务器的客户端，并通过向主服务器发送命令请求执行复制步骤，而在复制操作的后期，主从服务器会互相成为对方的客户端 。 主服务器通过向从服务器传播命令来更新从服务器的状态，保持主从服务器一致。从服务器通过向主服务器发送命令进行心跳栓测（每秒发送一次，会将当前服务器的复制偏移量传入），通过这种方式检测命令丢失情况。

Sentinel

  Sentinel是Redis的高可用解决方案。他会监视Redis主从服务器，并且在主服务器下线时，自动将主服务进行故障转移，选出新的主服务器。当原来的服务器重新启动后，将为成为新主服务的从服务器。Sentinel本质上是一个运行在特殊模式下的Redis服务器。Sentinel作为Redis的高可用解决方案会经过如下几步： 1：启动并初使化Sentinel服务器，在启动后Sentinel服务保存了Redis的master机器信息，并做为master机器的客户端与master机器建立了一个命令连接与订阅连接，订阅的是master服务器的sentinel:hello频道。 2：Sentinel默认会以每十秒一次的频率，通过命令连接向被监视的主服务器发送info命令。通过info命令得到的信息可以得到从服务器的信息，如果在这期间主服务器的信息有更新，则需要更新主服务器的信息。 3：根据上面得到的从服务器的信息，创建命令连接与订阅连接到从服务器。并以每十秒一次的频率发送info命令给从服务器，以便更新Sentinel服务器保存的从服务器的信息。 4：在默认情况下，Sentinel会以每两秒一次的频率，通过命令连接向所有被监视的主服务器和从服务器发送以下格式的命令： PUBLISTH sentinel:hello "<s_ip>,<s_port>,<s_runid>,<s_epoch>,<m_ip>,<m_port>,<m_runid>,<m_epoch>," 其中以s开头的信息表求的是Sentinel服务器的信息，分别为ip, port, runid,配置纪元。以m开头的则是主服务器的信息。 5：Sentinel订阅了相应主服务器与从服务器的sentinel:hello频道，Sentinel发现这个信息是自已发送的将不处理这个信息。通过向sentinel:hello发送信息主要用于发现其它Sentinel服务器的存在。 6：当发现有新的Sentinel监视相同的主服务器，Sentinel之间会互相建立命令连接，但是相互之间不会建订阅连接。 7：检测主观下线状态 ，Sentinel会以每秒一次的频率向所有与它创建了命令连接的实例发送PING命令，并通过实例返回的回复判断实例是否在线。当实例（主服务器，从服务器，同样监视主服务器的Sentinel）在Sentinel配置的down-after-milliseconds毫秒内连续返回无效的回复,则Sentinel主观判断服务器下线。 8：检查客观下线状态：当Sentinel主观判断服务器下线后，会向同样监视这一主服务器的其它Sentinel进行询问，看他们是否认同主服务器已经进入了下线状态 。Sentinel会向其它Sentinel发送如下命令：SENTINEL is-master-down-by-addr <ip> <port> <current_epoch> <runid>,其中<current_epoch> <runid>用于选举领头Sentinel。Sentinel将统计其它Sentinel同意主服务器已下线的数量，当这一数量达到客观下线所需的数量时，Sentinel会将主服务器判断为客观下线状态。 9：当主服务器被判断为客观下线状态后，监视的各Sentinel会选举领头的Sentinel，并由领头的Sentinel对主服务器执行故障转移操作。 10：执行故障转移，首先领头Sentinel会在从服务器列表里找出一个健康的并且具有最新数据的从服务器，对其执行slaveof no one命令，将其变为master。其次会将其它从服务器成为新的主服务器的slave。如果旧的主服务器从新上线的话，会成为新主服务器的从服务器。 11：sentinel的配置文件如下：

port 36379 ##端口
daemonize yes ##是否后台运行
logfile "/var/log/sentinel_36379_log.log" ##日志文件
dir "/tmp"
sentinel monitor mymaster 10.200.10.175 6379 2 ##sentinel监视的主Redis地址，后面的2表示当有两台sentinel认为当前Redis下线后才进行客观服务器下线操作。
sentinel down-after-milliseconds mymaster 6000 ##连续6秒没接收到mymaster服务器的ping消息，将mymaster设为主观下线状态。
sentinel failover-timeout mymaster 180000 ##故障转移的时长
sentinel parallel-syncs mymaster 1 ##指定了在执行故障转移时，最多可以有多少个从Redis实例在同步新的主实例。
bind 0.0.0.0 ##这个必须设置，否则没法进行故障转移。