Redis原理深入剖析（一）数据存储原理

Redis是用C语言开发的一个开源的高性能键值对（key-value）内存数据库，相信大家工作中都有接触过，为了整明白它的原理，最近抽空深入了解了下，记录分享下学习成果，因为内容比较多，所以这次我就分三篇来讲解（上次写分布式系统一致性算法想着一篇就给介绍明白，结果拖了一周都没写完，这次吸取教训了）

Redis原理分析总共分三部分：

1. 数据存储原理
2. 数据固化方式
3. 可靠性保证方案

今天我们重点分析下第一部分，对Redis的存储原理深入分析一波，看看它数据是如何组织的

首先，既然要分析数据存储，那么就要先看下Redis的数据结构，重点以下四种数据结构

• redisDb

typedef struct redisDb {
  dict *dict;
  dict *expires;
  dict *blocking_keys;
  dict *ready_keys;
  dict *watched_keys;
  int id;
  long long avg_ttl;
  list *defrag_later;
} redisDb;

• dict

typedef struct dict {
  dictType *type;
  void *privdata;
  dictht h2[2];
  long rehashidx;
  unsigned long iterators;
} dict;

• dictht

typedef struct dictht {
  dictEntry **table;
  unsigned long size;
  unsigned long sizemask;
  unsigned long used;
} dictht;

• dictEntry

typedef struct dictEntry {
  void *key;
  union {
    void *val;
    uint64_t u64;
    int64_t s64;
    double d;
  } v;
  struct dictEntry *next;
}dictEntry;

这可能看着太直观，一图胜千言，用图描述下：

从图中可以看出，redisDb 相当于根，根分出来两个字典，分别是dict （数据）与expires （过期时间），数据最主要的是两个hash，我们只看其中一个（另一个只有扩展的时候才有用），hash可以看到是一个dictEntry，由key与value组成，key是由RedisObject描述的，RedisObject包含类型、编码、指针，因为key的值需要特殊描述，所以指针又指向一个sds，sds有长度、空间、buffer，真是存储key的内容其实就是这个buf， dictEntry之间又组成一个链表。

细心的你不难发现，key的存储空间除了需要自身大小的空间，还需要额外的sds、RedisObject和部分dictEntry空间，key还有过期时间，还延伸出来一个expires ,我们思考一个问题，一个10个字节的key需要多少空间呢？

dictEntry: 16字节

RedisObject ： 12字节

sds ： 8字节 + 字符串长度

所以，我们可以计算出，一个10个字节的key需要的空间为：16+12+8+10+1=47

因为还有个同等大小的expires，所以最终大小为47*2=94

是不是很诧异，竟然翻了差不多5倍，所以业务中我们设置key尽量设置的小一点

存储结构跟key分析完了，我们接着来看下redis的内存管理，首先看看是如何处理过期数据的：

• 定期删除

redis是如何去做定期删除的呢，通过上面介绍的数据结构，可能很容易想到直接遍历过期字典表（expires链表），判断key是否过期，过期直接清理就可以了，but，但是，仔细想想，老版本的redis是单线程的工作模型，如果工作线程跑去遍历字典表，这种非常耗时的工作，铁定影响正常服务，无法保证效率了。redis的做法呢，跟我们传统的做工程项目的思维不太一样，按照我们工程思维，可能直接就遍历字典表，或者启个后台任务去做这个事情，但是像做redis这种偏底层的服务，他会把资源利用的更合理一些，会想办法找到一个删除代价跟删除效果之间的平衡点，直接遍历删除效果是最好的，但是代价太大了，不卖关子了，来看看redis的做法，下面是工作流程图：

主要流程就循环二十次，随机清理而是个key，如果期间清理的数量大于25%，则继续循环二十次（不是无限清理，这里会有一个时间间隔，大概几十ms），开始新的一轮随机清理，别问我这个25%是怎么来的呢，问就是人家调优精算得来的。

• 惰性删除

这个就很简单了，采用被动删除策略，访问是判断是否删除，节省CPU资源

当redis内存不够用了，需要淘汰掉一部分数据才能维持正常工作，那么这种场景redis又是如何去淘汰数据，清理内存的呢

• LRU

LRU有两种删除策略

1. volatile-lru 从设置了过期时间的数据集中，选择最近最久未使用的数据释放
2. allkey-lru 从数据集中选择最近最久未使用的数据释放

我们一般采用第一种策略，第二种一般线上业务不建议使用，因为他会删除你没有设置过期时间的数据。我们看下redisObject 的数据结构

type struct redisObject {
  unsigned type:4;
  unsigned encodeing:4;
  unsigned lru:LRU_BITS;
  int refcount;
  void *ptr;
} robj;

LRU_BITS记录了最近访问时间，但是链表也不可能去按照这个访问时间排序，那怎么办呢，看图：

redis还是使用祖传伎俩，跟定期删除方法差不多，也是寻找平衡点，随机从链表里选几个元素，按LRU_BITS进行排序，然后可以选出一个最近最近未使用的元素进行删除，把这块内存淘汰掉，但是都是这么随机操作，总感觉有点不靠谱，让我们看下实际效果到底怎么样吧，对比图如下

图中灰色部分是该被删除的部分，图一是正常LRU的结果，其他三张是redis LRU曲阳数据，可以看到取样数为10个的时候，效果已经非常逼近正常LRU了，可以看出效果还是很不错的

• LFU

除了根据最近最久未被使用来做淘汰，还有另外一种淘汰策略，根据最近的使用频率来做淘汰，为什么需要根据使用频率来做淘汰呢，请看下图这种情况：

按照LRU算法，我们首先就淘汰掉了A，但是可以看出，我们真正希望淘汰掉的应该是使用频率最低的C才对，这中情况我们应该采用LFU算法进行淘汰，LFU淘汰策略也有两种配置：

1. Volatile-lfu: 对有过期时间的key采用LFU淘汰算法
2. allkeys-lfu: 对全部key采用LFU淘汰算法

生产环境还是推荐使用第一种配置，不影响没有过期时间的key

LFU使用的数据结构还是redisObject，也是使用LRU_BITS，只不过将LRU_BITS进行了拆分，拆分成了两部分，

时钟记录的就是访问时间，计数器记录的就是访问频率，但是8bits最多只能放255，线上业务岂不是随随便便就给干满咯，这个计数器位数显然是不够的的，那么位数不够的情况redis是如何处理的呢，先看着两个配置：

1. lfu-log-factor：可以调整计数器counter的增长速度，lfu-log-factor越大，counter增长速度越慢
2. lfu-decay-time：是一个以分钟为单位的数值，可以调整counter的减少速度

可以控制增长速度与减少速度，计数器位数不够的问题是不是就迎刃而解了，我们看下lfu-log-factor分别设置为0、1、10、100计数器增长的情况：

数据存储原理分享到这，下一篇继续分享redis的数据固化方式

赏

谢谢你请我吃糖果

支付宝

微信