Redis 原理

Redis 原理

动态字符串SDS

• Redis中保存的key时字符串，value往往是字符串或字符串集合，字符串是Redis中常见的数据结构

• Redis没有直接使用C语言中的字符串，因为C语言字符串存在很多问题，使用起来不方便

• Redis构建了一种新型的字符串数据结构，称为简单动态字符串（Simple Dynamic String），简称SDS，是使用C语言实现的结构体

  struct __attribute__ ((__packed__)) sdshdr8 {
      uint8_t len; //buf已保存的字符串长度，不包含结束标识‘\0’
      uint8_t alloc; //buf申请的总的字节数，不包含结束标识
      unsigned char flages; //不同SDS的头类型，用来控制SDS的头大小有 8为、16为、32为、64为
      char buf[];
  };
  

• SDS具备自动扩容能力，如果要在原字符串基础上追加字符串，首先会申请内存空间，如果新字符串小于1M，则新空间为扩展后字符串的两倍 1；如果新字符串大于1M，则新空间为扩展后字符串长度 1M 1，称为内存预分配。

• 优点：获取字符串长度的时间复杂度为O(1)、支持动态扩容、减少内存分配次数、二进制安全

IntSet

• IntSet是Redis中Set集合的一种实现方式，基于整数数组来实现，具备长度可变、有序等特性

  typedef struct intset {
    	uint32_t encoding; //编码格式,存放格式包括：16位、32位、64位整数
      uint32_t length; //元素个数
      int8_t contents[]; //整型数组，保存集合数据
  } intset;
  

• 为了方便查找，Redis会将IntSet中所有的整数按升序排列，保存在contents数组中

• 如果添加的元素超过了存储范围，intSet会自动升级编码格式，找到合适大小，并按照新的编码方式及元素个数扩容数组，倒序依次将数组中的数据拷贝到扩容后的正确位置，并将待添加的数据放入数组末尾

• intSet特点：确保元素的唯一、有序性；具备类型升级机制，可以节省内存空间；底层采用二分查找方式查询；

• 因为intSet采用数组，内存空间是连续的，在数据量较大的时候，是不方便的，查找效率也会下降，所以适合在数据量较小时使用

Dict 字典

• Redis是一个键值型的数据库，然后根据键实现快速的增删改查，而键值的映射关系是通过Dict实现的

• Dict有三部分组成：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）；与HashMap思想类似

  typedef struct dictht {
      dictEntry **table; //entry数组，数组中存放的是指向entry的指针
      unsigned long size; //哈希表大小
      unsigned long sizemask; //哈希表大小的掩码，总等于size-1，计算hash值用
      unsigned long used; //entry 个数
  } dictht;
  

  typedef struct dictEntry {
      void *key; //键
      union {
          void *val;
          uint64_t u64;
          int64_t s64;
          double d;
      } v; //值
      //下一个Entry的指针
      struct dictEntry *next;
  } dictEntry;
  

• 当向Dict中添加键值对时，Redis首先根据key计算出hash值h，然后利用h & sizemask（和取余效果相同）来计算元素应该存储到数组中的哪个索引位置

  typedef struct dict {
      dictType *type; //dict类型，内置不同的hash函数
      void *privdata; //私有数据，在做特殊hash运算时使用
      dictht ht[2]; //一个Dict包含两个hash表，其中一个是当前数据，另一个一般是空数据，rehash使用
      long rehashidx; //rehash的进度，-1表示为进行
      int16_t pauserehash; //rehash是否暂停
  } dict;
  

Dict扩容及rehash

• 当集合元素较多时，导致哈希表冲突增多，链表过长，查询效率降低
• Dict在每次新增键值对时都会检查负载因子（LoadFactor=used/size），满足一下两种情况会触发哈希表扩容：
  • 哈希表 LoadFactor >= 1 ，并且服务器没有执行 bgsave 或 bgrewriteaof 等后台进程
  • 哈希表 LoadFactor >= 5
• 扩容也会扩容到大于容量最小的2的n次方
• Dict除了扩容，每次删除元素时，也会对负载因子做检查，当LoadFactor<0.1时，会做哈希表收缩
• rehash并不是一次性完成的，因为dict的数据量如果是百万级别的Entry，依次rehash极有可能导致主线程阻塞，因此采用渐进式的rehash过程
  • 不管扩容还是收缩，必定会创建新的哈希表，导致哈希表的size和sizemask变化，而key的查询跟sizemask有关，因此必须对哈希表中的每一个key重新计算索引，插入新的哈希表
  • 首先会计算hash表的realSize，值取决于扩容还是收缩
  • 按照新的realSize申请空间，创建Dictht，并赋值给dict.ht[1]
  • 设置dict.rehashidx=0，表示开始rehash
  • 每次增删改查时，都检查一下dict.rehashidx是否大于-1，如果是，则将dict.ht[0].table[rehashidx]的Entry链表rehash到dict.ht[1]，并且将rehashidx ；直至dict.ht[0]的所有数据都rehash到dict.ht[1]
  • 将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存
  • 将rehashidx赋值为-1，代表rehash结束
  • 在rehash过程中新增操作，直接写入ht[1]，查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查询，确保ht[0]中的数据只减不增，随着rehash最终清空

ZipList

ZipList是一种特殊的“双端链表”，由一系列特殊编码的连续内存组成，可以在任意一端进行压入/弹出操作，并且该操作的时间复杂度为O(1)

• ZipList 中的Entry并不像普通链表那样记录前后节点的指针，因为记录两个指针要占用16字节，浪费内存，而是采用下面的结构：
  

  • previous_entry_length：前一节点的长度，占用1个或5个字节
  • encoding：编码属性，记录content的数据类型（字符串还是整数）以及长度，占用1个、2个或5个字节
  • content：负责保存节点数据，可以是字符串或整数

• 特点：

  • 压缩列表可以看做是一种连续内存空间的“双向链表”
  • 列表之间不是通过指针连接，而是记录上一节点和本节点长度来寻址，内存占用较低
  • 如果列表数据过多，导致链表过长，可能影响查询性能
  • 增或删较大数据时有可能发生连续更新问题

QuickList

• ZipList虽然节省内存，但申请内存空间必须是连续的，如果内存占用较多，申请内存效率很低，该怎么办？

• 在Redis3.2中，引入了新的数据结构QuickList，他是一个双端链表，只不过链表中的每一个节点都是一个ZipList

  

• QuickList特点：

  • 是一个节点为ZipList的双端链表
  • 节点采用ZipList，解决了传统链表的内存占用问题
  • 控制了ZipList大小，解决连续内存空间申请效率问题
  • 中间节点可以压缩，进一步节省内存

SkipList

SkipList称为跳表，它是一种链表，但与传统的链表相比有几点差异：

• 元素按照升序排列存储
• 节点可能包含多个指针，指针跨度不同

特点：

• 跳表是一个双向链表，每一个节点都包含score和ele值
• 节点按照score值排序，score值一样则按照ele字典排序
• 每一个节点都可以包含多层指针，层数时1到32之间的随机数
• 不同层指针到下一个节点的跨度不同，层级越高，跨度越大
• 增删改查效率与红黑树基本一致，实现却更简单

RedisObject

Redis中任意数据类型的键值都会被封装为一个RedisObject，也叫Redis对象，不包含数据时占16字节

typedef struct redisObject {
    unsigned type:4; //对象类型，分别是string hash list set zset，占4个bit位
    unsigned encoding:4; //底层编码方式，有11中，占4bit位
    unsigned lru:LRU_BITS; //lru表示该对象最后一次被访问的时间，占24bit位
    int refcount; //引用计数器，计数器为0表示无引用，可以被回收
    void *ptr; //指针，指向存放实际数据的空间
} robj;

Redis中会根据存储的数据不同，选择不同的数据类型，选择不同的编码格式：

Redis 内存回收

Redis是基于内存存储，单节点Redis内存不宜过大，会影响持久化或者主从同步性能，可以修改配置文件来设置Redis的最大内存：

maxmemory 1gb; #最大内存为 1gb

Redis 过期策略

通过expire命令给Redis的key设置TTL（存活时间），当key的TTL到期之后，对应的内存也得到释放

DB结构：Redis本身是一个典型的key-value内存存储数据库，因此所有的key、value都保存在Dict结构中，不过在database结构体中，有两个Dict：一个用来记录key-value；另一个记录key-TTL

typedef struct redisDb {
    dict *dict; //存放了所有key及value，也称keyspace
    dict *expires; //存放每一个key的ttl存活时间，只包含设置了ttl的key
    dict *blocking_keys;
    dict *ready_keys;
    dict *watched_keys;
    int id;
    long long avg_ttl;
    unsigned long expires_cursor;
    list *defrag_later;
} redisDb;

key的TTL到期后是否立即删除？

• 惰性删除：并不是到期之后立刻删除，而是在访问该key的时候，检查key的存活时间，如果已经过期，则删除
• 周期删除：通过一个定时任务，周期性的抽样部分过期的key，然后执行删除操作

Redis 淘汰策略

内存淘汰：当Redis内存使用达到设置的阈值时，Redis主动挑选部分key删除以释放更多内存的流程

Redis 支持8中淘汰策略：

• noeviction：不淘汰任何key，但是内存满时不允许写入数据，时Redis的默认淘汰策略
• volatile-ttl：对设置了TTL的key，比较key的剩余TTL值，TTL越小越先被淘汰
• allkeys-random：对全体key，随机淘汰
• volatile-random：对设置了TTL的key，随机淘汰
• allkeys-lru：对全体key，基于lru算法进行淘汰
• volatile-lru：对设置了TTL的key，基于lru算法进行淘汰
• allkeys-lfu：对全体key，基于lfu算法进行淘汰
• volatile-lfu：对设置了TTL的key，基于lfu算法进行淘汰

LRU（Least Recently Used），最少使用，用当前时间减去最后一次访问时间，这个值越大则淘汰优先级越高

LFU（Least Frequently Used），最少使用频率，会统计每个key的访问频率，值越小，淘汰优先级越高

这篇好文章是转载于：学新通技术网