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同时采用跳跃表与字典来保存有序集合，但他们会通过指针来共享相同元素的成员与分值