redis底层数据结构

redis底层数据结构

SDS（simple dynamic string）:redis中使用的所有字符串都是这种类型。
- 结构：
  struct sds{
  int len //已使用的长度
  int free //未使用的长度
  char [] //装字符串的
  }
- 好处(与c原生字符串相比)：
  - 获取字符串长度时间复杂度为O(1)
  - c语言提供的strcat函数，在拼接时不检查长度，会发生溢出，而redis会在拼接前检查sds的free字段是否可以容纳拼接字符串，如果容纳不下，自动进行扩容机制。
  - sds中free的存在，所以重分配不会频繁。
  - 可以保存二进制字节，这样就可以存储视音频图片等数据。
  - 以‘/0’结尾，兼容c字符串，可重用c提供的字符串操纵函数。
- 扩容机制：
  - 如果字符串修改后len小于1M，那么会分配空间使free=len，比如修改后len是14，那么总长度就是14+14+1；
  - 如果修改后len>1M,那么free=1M，比如修改后len是22M，那么总长度是22M+1M+1byte
  - 惰性释放：字符串变小后不会重新分配更小的空间，而只是更改len和free的大小，不过redis也提供了api来真正释放大小。
双端链表
- 结构：
  - 链表节点```java typedef struct listNode { // 前置节点 struct listNode prev; // 后置节点 struct listNode next; // 节点的值 void *value;

} listNode;


      - 双端链表结构:（void* 相当于java中的object，c语言的多态。）```java
/*
 * 双端链表结构
 */
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;

场景：
列表键对应的值、发布订阅、慢查询、监视器等、服务器利用链表保存客户端状态信息等。
- 字典(hash表)
定义：
大部分时与哈希表同义，有时意义为对哈希表多了一层封装，叫做字典。
场景：
redis数据库(存储所有键值对的结构)是使用字典来实现的，对数据库的增删改查就是对字典提供api的调用、哈希键的底层实现之一。
结构：
- 哈希表java typedef struct dictht { // 哈希表数组 dictEntry **table; // 哈希表大小(能装几个元素) unsigned long size; // 哈希表大小掩码，用于计算索引值 // 总是等于 size - 1 unsigned long sizemask; // 该哈希表已有节点的数量(已经装了几个元素) unsigned long used; } dictht;
- 键值对java typedef struct dictEntry { // 键 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; } v; // 指向下个哈希表节点，形成链表 struct dictEntry *next; } dictEntry;
- 字典java 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;
- 操作函数:(因为字段较多，单独把操作提到一个结构体中)java typedef struct dictType { // 计算哈希值的函数 unsigned int (*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;
hash算法与键冲突
//murmurhash2获取hash
hash = dict->type->hashFunction(key);
//算出在数组中的位置(和sizemask与运算，就是和sizemask+1取余)
Index = hash&dictht[x].sizemask;
拉链头插法解决键冲突
rehash
- 时机：负载因子=已有节点数量/哈希表大小
  负载因子小于0.1，进行缩容
  如果正在执行bgsave或bgwriteaof，负载因子大于等于5扩容，没有执行，则大于等于1执行扩容。
- 流程
  1. 为字典的ht[1]分配空间
    - 扩容：ht[1]的大小为第一个大于等于ht[0].used*2的2^n(2的n次方)
    - 缩容：ht[1]的大小为第一个大于等于
      ht[0].used的2^n(2的n次方)
  2. 重新计算ht[0]各个key在ht[1]的索引值，并存储在ht[1]中。
    1. 在字典中维持rehashidx值设为0，表示正式开始rehash。
    2. 对字典的操作会顺带将ht[0]在rehashidx索引上的键值对rehash到ht[1]，然后将ht[0]对应rehashidx位置的指针置为null,ht[0].used减1。
    3. 其中添加操作会直接操作ht[1],查找更新操作会先遍历ht[0],没有的话再遍历ht[1]。完成后会执行rehashidx++；
    4. 当ht[0].used==0代表rehash完成，将rehashidx置为-1。
  3. ht[0]中键值对都迁移后，释放ht[0]，并将ht[1]设置成ht[0]。

跳跃表

定义：有序数据结构，可以看作是有多个前驱结点、分值的双向链表。
应用：仅在有序集合键、集群节点的内部结构。

结构：

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

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

其他：跨度主要计算元素排位的，幂次定律生成node的层数(1-32)。
- 整数集合

简介：集合键的底层实现之一

结构：

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

升级：整数集合可以存储不同类型整数(c有多种整数类型)，但是类型必须统一为所存数据最大的类型，所以新插入的数据如果类型较大，需要升级。
- 扩展整数集合数组的大小。
- 将数组现有元素类型转换成新元素相同，并将现有元素放在相应位置上。
- 放入新元素(因为新元素类型一定大，所以新元素一定是最大的)
有趣的点：
- 每次插入元素时都会扩容，无论是否升级。且每次仅仅扩容一个元素的大小。(因为数组要放多个类型的整数，所以需要升级，导致只能采用这个方式扩容，具体原因百度)
- 不支持降级。
  - 压缩列表
简介：物理机构是省空间的有序数组，因为是连续的内存空间，并且存储的元素长度不固定，且要求有序，但逻辑结构更像是双向链表，可以从前后遍历数据。
结构：
- zlbytes:4字节。整个压缩列表占用的内存数。
- zltail：4字节。起始位置到表尾节点(entryN)的偏移量。
- zllen：2字节。压缩列表中节点数量。
- entryX: 不定字节。各个节点
- zlend：1字节。标记压缩列表末端
- Previous_entry_length:代表前一个节点的字节大小。通过该属性实现表尾向前遍历。占用字节不固定。
  - 前一节点长度小于254字节，长度为1字节。
  - 大于等于254字节，长度为5字节，其中第一字节设置为OXFE代表该长度为五字节，剩下4字节存储前一节点长度。
- encoding：记录content字段存储的数据类型及长度。
  - 一字节、两字节、五字节长，值的最高位分别为00、01、10，表示content存储字节数组，长度用其他位记录。
  - 值最高位为11，则一字节长，表示content存储整数值，类型及长度用其他位记录。
- content：前两个属性固定，则content固定。
连锁更新
当插入元素或删除元素a时，a后的元素b Previous_entry_length属性记录着前一元素的大小，该属性可能会从原来的1个字节变成5个字节，由于b字节变大，而b后的元素c的该属性也可能要变，从而连锁更新，但是几率不高。