最近在准备面试，问到redis相关知识，只能说个皮毛，说的既不深入也不全面，所以抓紧突击一下，先学《redis设计与实现》。

选择看书的原因是：

书中全面深入，且能出书一定十分用心；

搜博客也找不到比书更全面的文章，且费时;

直接看源码一个是对C掌握不好，且易困，效率不高，所以跟着书同步学源码，是我认为现在最好的选择。

 

---

 一：五种常用数据类型

简单动态字符串

redis做了一个用作字符串的SDS，除了一些不需要修改的场景，都是用SDS

C字符串的底层实现总是一 个N+1个字符长的数组

sds.h：

struct sdshdr {
    
    // buf 中已占用空间的长度
    int len;

    // buf 中剩余可用空间的长度
    int free;

    // 数据空间
    char buf[];
};

C字符串与SDS区别

1	C字符串	SDS
2	求长度，需要遍历O(n)	直接取len就可以O(1)
3	容易造成缓冲区溢出
4		减少了内存重新分配次数 (速度要求严苛，避免分配内存耗时多)
5		二进制安全

4：SDS有free，可以比C字符串多一些预留空间。空间优化策略主要有两种：

• 空间预分配
  1. SDS进行修改时，会额外获得未使用空间。
  2. 修改后空间n
     1. n<1M;free分配n+1byte(空字符)
     2. n>=1M;free分配1M+1byte
• 惰性空间释放
  1. SDS进行缩短时，不释放删除的空间，加到free里。

SDS的API

• sdsnew 创建
• sdsempty 创建空的SDS
• sdsfree 释放
• sdslen 获取len
• sdsvail 获取free数量
• sdsdup 创建一个sds副本
• 。。

链表

 redis自己构建的链表：

/*
 * 双端链表节点
 */
typedef struct listNode {

    // 前置节点
    struct listNode *prev;

    // 后置节点
    struct listNode *next;

    // 节点的值
    void *value;

} listNode;

/*
 * 双端链表迭代器
 */
typedef struct listIter {

    // 当前迭代到的节点
    listNode *next;

    // 迭代的方向
    int direction;

} listIter;

/*
 * 双端链表结构
 */
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;

字典

也叫：符号表、关联数组、映射，用于保存键值对；

/*
 * 字典
 */
typedef struct dict {

    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

    // 目前正在运行的安全迭代器的数量
    int iterators; /* number of iterators currently running */

} dict;

 理解：

• 字典dict；
  • 属性type是指向dictType的；dictType是保存特定类型键值对的函数；redis会为不同的字典设置不同的函数。
  • 属性privateData是存储对应类型的可选参数。
  • ht是指向dictht的引用；
    • 其中table是指向dictEntry的二维引用，有两级。
    • 第一级是hash后的值，到阈值就要rehash扩缩容
      • dictEntry是哈希节点
      • key是键
      • value是值
      • 还有指向下一个节点的引用next，用于成链。

hash算法

冲突解决

哈希表使用链地址法来解决键冲突：

哈希表节点dictEntry的指针构成一个链，hash相同的就排在当前dictEntry的next

rehash

1.为ht[1]分配空间，与ht[0]比较，扩容则分配

 // 新哈希表的大小至少是目前已使用节点数的两倍
 // T = O(N)
return dictExpand(d, d->ht[0].used*2);

收缩则分配大小等于ht[0]的？

/*
 * 缩小给定字典
 * 让它的已用节点数和字典大小之间的比率接近 1:1
 * 返回 DICT_ERR 表示字典已经在 rehash ，或者 dict_can_resize 为假。
 * 成功创建体积更小的 ht[1] ，可以开始 resize 时，返回 DICT_OK。
 */
int dictResize(dict *d)
{
    int minimal;
    // 不能在关闭 rehash 或者正在 rehash 的时候调用
    if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
    // 计算让比率接近 1：1 所需要的最少节点数量
    minimal = d->ht[0].used;
    if (minimal < DICT_HT_INITIAL_SIZE)
        minimal = DICT_HT_INITIAL_SIZE;
    // 调整字典的大小
    // T = O(N)
    return dictExpand(d, minimal);
}

2.把ht[0]复制并重新hash计算到ht[1]上

3.把ht[0]释放，ht[1]设置为ht[0]。

hash表的扩容与收缩

哈希表会自动在表的大小的二次方之间进行调整。

在没有bgSave或bgRewriteAOF命令时，负载因子大于1;或者有bgSave或bgRewriteAOF命令时，负载因子大于5；时执行

负载因子= 已保存/哈希表大小

渐进式rehash

 

跳跃表

skipList 

命令：

ZRANGE

ZCARD

有序，按value值排序？

平均O(logN)复杂度

适用于有序集合元素较多或集合中元素是较长字符串等场景。

具体应用：

• 实现有序集合键
• 在集群节点中用作内部数据结构

/*
 * 跳跃表
 */
typedef struct zskiplist {

    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;

    // 表中节点的数量
    unsigned long length;

    // 表中层数最大的节点的层数
    int level;

} zskiplist;

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

 理解：

• 跳表zskipList；
  • 属性header和tail分别指向zskiplistNode的头尾指针。
    • zskiplistNode
      • 层
      • 后退
      • 分支
      • 成员对象
  • level记录层数最大的层数

整数集合

命令：

SADD numbers 1 3 5 7 9

 

typedef struct intset {
    
    // 编码方式
    uint32_t encoding;

    // 集合包含的元素数量
    uint32_t length;

    // 保存元素的数组
    int8_t contents[];

} intset;

uint32_t 　取值范围 0 ~ 4,294,967,295

int8_t 　　取值范围 -128 ~ 127

 

contents中的值从小到大排列，并且没有重复元素。

整数集合升级过程：

• 根据新元素的类型，扩展数组空间，为新元素分配空间。
• 将已有的数据转换成相同类型，保持排序。
• 将新元素加到新数组里。

升级之后不支持降级，即使没有当前等级的元素。

 

 

压缩表

 zipList 是列表键和hash键的底层实现之一。

RPUSH lst 1 3 5 10086 "hello" "world"

 

对象

• 字符串对象
• 列表对象
• 哈希对象
• 集合对象
• 有序集合对象

 每种对象都最少对应上述一种数据类型

不同的对象有不同的特性~（省略）。

 

 

 

二：单机

数据库

struct redisServer{
    
    // ~
    // 一个数组保存，保存服务器中所有数据库
    redisDb *db;
　 　// ~
　　//根据此数量决定在初始化时创建数据库个数
　　int dbnum;


} intset;

通过SELECT n 可以切换到不同的库

//TODO

原理

 

保存键值对的方法

 

过期策略

 

持久化机制

 

事件、redis初始化过程等其他

 

三：分布式

Sentinel

 

复制

 

集群

 

四：独立功能

 

发布订阅

 

事务

 

Lua脚本

 

排序

 

慢查询

 

 

 

1

1

1

1

1

1

1

1

1

1

1