《Redis设计与实现》读书笔记（一）

零、前言

最近项目要加Redis，之前学的redis就很浅，只会set，get，痛定思痛，决定深入学习一下Redis，大概把Redis学习分为了以下几个阶段：

1. 《Redis设计与实现》通读一遍并做笔记
2. 给项目添加Redis，把知识转为经验
3. 阅读Redis源码（往后推一推哈哈哈）

一、数据结构与对象

Redis总有5种基本类型，String，List，Hash，Set，Zset

数据结构总有6种，SDS，链表，字典，跳跃表，整数集合，压缩列表

1.1 简单动态字符串

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

struct sdshdr{
  	//记录buf已使用的字节数量
  	int len;
  	
  	//记录buf未使用的字节数量
  	int free;
  
  	//字节数组，用于保存字符串
  	char buf[];
}

SDS与C字符串的区别

1. O(1)获取字符串长度
2. 杜绝缓冲区溢出，SDS会自动扩展长度
3. 减少修改字符串时带来的内存重分配次数
   1. 空间预分配
   2. 惰性空间释放（字符串缩短并不会马上回收，会用free记录）
4. 二进制安全（'\0'不作为字符串的结束）
5. 兼容所有C字符串的函数

1.2 链表

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;

特点总结：

1. 双端链表
2. 无环
3. 带表头指针和表尾指针
4. 带链表长度计数器
5. 多态（void*保存节点值，可以保存各种不同类型的值）

1.3 字典

typedef struct dictht {
  
  	//哈希表数组
    dictEntry **table;
  
  	//哈希表大小
    unsigned long size;
  
  	//size-1，掩码
    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 dictType {
    uint64_t (*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;

typedef struct dict {
  
  	//类型特定函数，每个dictType保存一套用于操作当前kv的函数
    dictType *type;
  
  	//用于传给特定函数的可选参数
    void *privdata;
  
  	//哈希表
    dictht ht[2];
  
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

1.4 跳跃表

typedef struct zskiplistNode {
    sds ele;
  
  	//分值
    double score;
  
  	//后退指针
    struct zskiplistNode *backward;
  
  	//层
    struct zskiplistLevel {
      	//前进指针
        struct zskiplistNode *forward;
      
      	//跨度，与遍历无关，用于计算rank
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

漫画： 什么是跳跃表

跳跃表有点类似于树型结构，有着层的概念，对于新插入的节点，采取的晋升策略是50%随机晋升一层，具体看链接～

查询源码：

struct node* search(struct node*head, int key, int level)
{
    int i;
    struct node *p;
    p=head;
    for(i=level;i>=0;i--)
      while((p->forward[i]!=0)&&(p->forward[i]->key<key))
        p=p->foward[i];
    p==p->forward[0];//回到0级链，当前p或者空或者指向比搜索关键字小的前一个结点
    if(p==0)//这时若p为空则推出检索,返回0
      return 0;
    else if(p->key==key)//找到，返回成功
      return p;
    else 
      return 0;//否则仍然检索失败,返回0
}

跳跃表的优势：

“跳跃列表是在很多应用中有可能替代平衡树而作为实现方法的一种数据结构。跳跃列表的算法有同平衡树一样的渐进的预期时间边界，并且更简单、更快速和使用更少的空间。”——发明者William Pugh

1.5 整数集合

typedef struct intset {
  	//编码方式，决定了contents的类型，INTSET_ENC_INT16：int16_t
    uint32_t encoding;
  
  	//集合包含的元素数量
    uint32_t length;
  
  	//保存元素的数组
    int8_t contents[];
} intset;

新元素添加到intset中，新元素的类型比整数集合现有所有元素的类型都要长，整数集合需要先进行升级

升级步骤：

1. 根据新元素的类型，扩展整数集合底层数组空间大小，并为新元素分配空间
2. 原元素转为新元素类型，，放置到正确的位置上，维持有序性不变
3. 新元素添加到底层数组里面

不支持降级操作

1.6 压缩列表

previous_entry_length记录前一个节点的长度

encoding表示content的类型

1. 00001011:前两位表示字节数组，后六位表示长度11
2. 11000000:表示节点保存的是一个int16_t类型的整数值
3. .......

连锁更新场景：

前一个节点小于254字节：previous_entry_length使用1字节保存

前一个节点大于等于254字节：previous_entry_length使用5字节保存

可能出现的情况：一个节点的更新引发多个节点的更新，实际应用中这种情况并不多见

1.7 对象

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;

对象类型

编码类型

对象与编码的对应关系

编码转化的条件(有一个条件达到就转，排除特殊例子):

1. 有一个字符串元素长度大于等于64字节
2. 保存的元素数量大于512个（有序集合128个）

多态命令

有些命令可以通用，就是基于命令的多态

内存回收

Redis使用的是引用计数法，redisObject的refcount属性记录

对象共享

object refcount A	#查看A的引用计数

Redis服务端会在启动时创建0～9999的所有整数值，用于对象共享

对象的空转时长

redisObject的lru属性记录最后一次被命令程序访问的时间

object idletime A	#查看A的空转时长