知识总结 redis

redis

概述

一个进程16个库
都是key-value，value不同类型
二进制安全的，只存放字节
正负索引正序0123 倒序-1-2-3

Redis如何淘汰过期的keys

Redis keys过期有两种方式：被动和主动方式。

当一些客户端尝试访问它时，key会被发现并主动的过期。

当然，这样是不够的，因为有些过期的keys，永远不会访问他们。无论如何，这些keys应该过期，所以定时随机测试设置keys的过期时间。所有这些过期的keys将会从密钥空间删除。
具体就是Redis每秒10次做的事情：

测试随机的20个keys进行相关过期检测。
删除所有已经过期的keys。
如果有多于25%的keys过期，重复步奏1.
- 这是一个平凡的概率算法，基本上的假设是，我们的样本是这个密钥控件，并且我们不断重复过期检测，直到过期的keys的百分百低于25%,这意味着，在任何给定的时刻，最多会清除1/4的过期keys。

##持久化

rdb

快照落地
时点性问题（写入时数据会变化）

基础数据结构

string

底层数据

string 类型
int 类型
bitmap 类型

list

同向操作=栈反向=队列 index=数组 blpop阻塞弹出=阻塞队列/订阅
概述
当链表entry数据超过512、或单个value 长度超过64，底层就会zipList转化成linkedList编码；
在版本3.2之前，列表底层的编码是ziplist和linkedlist实现的：
- 对linkedlist来说，这些命令都是基于prev、next、head、tail指针完成的，双向链表基于指针，实现比较容易。
- 而ziplist则是通过当前entry的指针，加减位移的偏移量(前一个entry的长度)，进行跳跃节点。
在版本3.2之后，重新引入 quicklist，列表的底层都由quicklist实现；
list是如何实现阻塞队列的？
将客户端的状态设为“正在阻塞”，并记录阻塞这个客户端的各个键，以及阻塞的最长时限（timeout）等数据。
将客户端的信息记录到 server.db[i]->blocking_keys 中（其中 i 为客户端所使用的数据库号码）。
继续维持客户端和服务器之间的网络连接，但不再向客户端传送任何信息，造成客户端阻塞。
步骤 2 是将来解除阻塞的关键， server.db[i]->blocking_keys 是一个字典，字典的键是那些造成客户端阻塞的键，而字典的值是一个链表，链表里保存了所有因为这个键而被阻塞的客户端（被同一个键所阻塞的客户端可能不止一个）：

底层数据

压缩列表

压缩列表（ziplist）是为了节约内存而设计的，是由一系列特殊编码的连续内存块组成的顺序性（sequential）数据结构，一个压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者一个整数值
一个压缩列表可以包含多个节点（entry），每个节点可以保存一个字节数组或者一个整数值
各部分组成说明如下
- zlbytes：记录整个压缩列表占用的内存字节数，在压缩列表内存重分配，或者计算zlend的位置时使用
- zltail：记录压缩列表表尾节点距离压缩列表的起始地址有多少字节，通过该偏移量，可以不用遍历整个压缩列表就可以确定表尾节点的地址
- zllen：记录压缩列表包含的节点数量，但该属性值小于UINT16_MAX（65535）时，该值就是压缩列表的节点数量，否则需要遍历整个压缩列表才能计算出真实的节点数量
- entryX：压缩列表的节点
- zlend：特殊值0xFF（十进制255），用于标记压缩列表的末端
每个压缩列表节点可以保存一个字节数字或者一个整数值，结构如下
- previous_entry_ength：记录压缩列表前一个字节的长度
- encoding：节点的encoding保存的是节点的content的内容类型
- content：content区域用于保存节点的内容，节点内容类型和长度由encoding决定

hash

底层数据

字典

字典最外层结构如下

typedef struct dict {
  // 和类型相关的处理函数
  dictType *type;
  // 私有数据
  void *privdata;
  // 哈希表
  dictht ht[2];
  // rehash 索引，当rehash不再进行时，值为-1
  long rehashidx; /* rehashing not in progress if rehashidx == -1 */
  // 迭代器数量
  unsigned long iterators; /* number of iterators currently running */
} dict;

dict的ht属性是两个元素的数组，包含两个dictht哈希表，一般字典只使用ht[0]哈希表，ht[1]哈希表会在对ht[0]哈希表进行rehash（重哈希）的时候使用，即当哈希表的键值对数量超过负载数量过多的时候，会将键值对迁移到ht[1]上
rehashidx也是跟rehash相关的，rehash的操作不是瞬间完成的，rehashidx记录着rehash的进度，如果目前没有在进行rehash，它的值为-1
type属性和privdata属性是针对不同类型的键值对，用于创建多类型的字典，type是指向dictType结构的指针，privdata则保存需要传给类型特定函数的可选参数，关于dictType结构和类型特定函数可以看下面代码

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;

Redis的字典底层是使用哈希表实现的，一个哈希表里面可以有多个哈希表节点，每个哈希表节点中保存了字典中的一个键值对

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

哈希表是由数组table组成，table中每个元素都是指向dict.h/dictEntry结构的指针，哈希表节点的定义如下,其中key是我们的键；

typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    // 指向下一个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

v是键值，可以是一个指针，也可以是整数或浮点数；next属性是指向下一个哈希表节点的指针，可以让多个哈希值相同的键值对形成链表，解决键冲突问题

set

无序的
srandmember 随机抽取 x 个元素。正数不重复，负数可重复
spop 取出一个
底层数据
如果能够转成int的对象（isObjectRepresentableAsLongLong），那么就用intset保存。
如果用intset保存的时候，如果长度超过512（REDIS_SET_MAX_INTSET_ENTRIES）就转为hashtable编码。

其他情况统一用hashtable进行存储。

整数集合 intset

整数集合的定义为intset.h/intset

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

contents数组：整数集合的每个元素在数组中按值的大小从小到大排序，且不包含重复项
length记录整数集合的元素数量，即contents数组长度
encoding决定contents数组的真正类型，如INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64

hashtable

zset

概述

有序不重复

底层结构

skiplist + hash（key，score）

跳跃表其实可以把它理解为多层的链表，它有如下的性质

多层的结构组成，每层是一个有序的链表
最底层（level 1）的链表包含所有的元素
跳跃表的查找次数近似于层数，时间复杂度为O(logn)，插入、删除也为 O(logn)
跳跃表是一种随机化的数据结构(通过抛硬币来决定层数)

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    // 成员对象 （robj *obj;）
    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;

zskiplistNode结构

level数组（层）：每次创建一个新的跳表节点都会根据幂次定律计算出level数组的大小，也就是次层的高度，每一层带有两个属性-前进指针和跨度，前进指针用于访问表尾方向的其他指针；跨度用于记录当前节点与前进指针所指节点的距离（指向的为NULL，阔度为0）
backward（后退指针）：指向当前节点的前一个节点
score（分值）：用来排序，如果分值相同看成员变量在字典序大小排序
obj或ele：成员对象是一个指针，指向一个字符串对象，里面保存着一个sds；在跳表中各个节点的成员对象必须唯一，分值可以相同

zskiplist结构