缓存系统设计精要

在计算机领域,缓存在程序设计过程中扮演着重要角色。浏览器的资源缓存策略是影响web网站性能的一个关键因素;mysql的Buffer Pool极大的提高了数据库的查询效率;redis作为被广泛应用的缓存数据库,提供了丰富的数据结构和缓存策略来满足开发者的需求。缓存在现代计算机系统中无处不在,是一个非常深入、广泛的话题,本文的目的是从众多已有的系统设计中,提取出有关系统缓存设计的精要,主要从三个方面展开:

  • 多级缓存
  • 缓存淘汰策略
  • 缓存安全

在讨论这些话题的同时,笔者会结合很多实际的例子阐述,其中会涉及到PHP源码、redis源码、浏览器的缓存策略、mysql数据存储设计、缓存淘汰算法等偏底层的内容,如果你是一个比较资深的开发工程师,对这些内容都比较了解,本文将非常适合您。为了照顾初学者,涉及到难懂重要的知识点笔者也将会尽可能的描述清楚。本文篇幅有点长,请读者做好心理预期!

1.多级缓存

1.1 存储器层次结构

计算机使用不同的存储技术对数据进行访问,时间差异很大。速度较快的技术每个字节的成本要比速度较慢的技术高,而且容量较小。CPU和主存(内存)之间的速度差距在增大。基于这种特性,所有的现代计算机系统都使用了金字塔式的存储器层次结构。如下图所示:

存储器层次结构

从高层往低层走,存储设备变得更慢、更便宜、容量更大。最高层(L0)是少量快速的CPU寄存器,CPU可以在一个时钟周期内访问它们 (一个时钟周期通常小于1ns);接下来是一个或多个中小型SRAM高速缓存存储器,可以在几个CPU时钟周期内访问它们;然后是一个大的基于DRAM的主存,可以在几十到几百个CPU时钟周期内访问它们;接下来是慢速但是容量很大的本地磁盘(通常是SSD);最后有些系统甚至包括了一层附加的网络文件系统(Network File System,NFS),比如说腾讯云提供的CFS服务就可以通过挂载到多个服务器实现分布式的数据共享。

下面我们从 CPU 的角度以具体的数据来量化对比CPU、磁盘、网络的速度,对计算机各个组件不同的速度差异有个更直观的认识。

类型缓存内容缓存位置读取数据需要时长对比基本单位时长
CPU寄存器4字节 & 8字节芯片上的CPU寄存器0.38ns1s
L1高速缓存64字节块芯片上的L1高速缓存0.5ns1.3s
L2高速缓存64字节块芯片上的L2高速缓存7ns18.2s
L3高速缓存64字节块芯片上的L3高速缓存35ns91s
内存4KB页主存100ns4分钟
固态硬盘SSD磁盘扇区磁盘控制器150us4.5天
网络磁盘(NFS本地挂载)部分文件本地磁盘1.5ms一个半月

CPU 和内存之间的瓶颈被称为冯诺依曼瓶颈, 它们之间至少有着几百倍的速差,可以想象成天上人间,天上一天,地下一年。普通的磁盘读取数据就更慢了,寻址时间10ms,对比CPU的基本单位时长是10个月,可以生一次孩子了!所以说IO 设备是计算机系统的瓶颈。以此想到我们网络中的API请求,动不动就是一百多毫秒,对比CPU的基本单位就是十几年!

相信通过以上描述,读者对计算机组件之间数据处理速度有了深入的印象。

1.2 局部性原理

一个编写良好的计算机程序通常具有良好的局部性(locality)。也就是,它们倾向于引用邻近于其他最近引用过的数据项的数据项,或者最近引用过的数据项本身。这种倾向性,被称为局部性原理(principle of locality),是一个持久的概念,对硬件和软件系统的设计和性能都有着极大的影响。

局部性通常有两种不同的形式: 时间局部性(temporal locality)空间局部性(spatial locality)

  • 时间局部性:被引用过一次的内存位置很可能在不远的将来再被多次引用。
  • 空间局部性:如果一个内存位置被引用了一次,那么程序很可能在不远的将来引用附近的一个内存位置。

Mysql数据库Innodb引擎的设计就很好的考虑了局部性原理。

Innodb引擎以页的形式组织数据,页的默认大小是16KB,存放用户数据记录的页叫“数据页”,为了实现数据更快的查找,InnoDB使用B+树的结构组织存放数据,最下层的叶子节点存放“数据页”,在“数据页”的上层抽出相应的“目录页”,最终形成的基本结构如下图所示:

InnoDB数据存储

数据页中记录是连续存放的,当需要访问某个页的数据时,就会把完整的页的数据全部加载到内存中,也就是说即使我们只需要访问一个页的一条记录,那也需要先把整个页的数据加载到内存中。这就利用了局部性原理中的“空间局部性”。将整个页加载到内存中后就可以进行读写访问了,在进行完读写访问之后并不着急把该页对应的内存空间释放掉,而是将其缓存到Buffer Pool中,这样将来有请求再次访问该页面时,就可以省去磁盘IO的开销了,这又利用了局部性原理中的“时间局部性”。

局部性原理是系统缓存设计中非常重要的理论基石,下文还会多次提到。

1.3 Cpu 高速缓存

本节我们来聊一聊Cpu 高速缓存,Cpu 高速缓存是影响程序性能的一个关键因素。

1.3.1 什么是Cpu 高速缓存?

笔者直接引用维基百科中对Cpu 高速缓存的描述:

在计算机系统中,CPU高速缓存(英语:CPU Cache,在本文中简称缓存)是用于减少处理器访问内存所需平均时间的部件。在金字塔式存储体系中它位于自顶向下的第二层,仅次于CPU寄存器。其容量远小于内存,但速度却可以接近处理器的频率。
当处理器发出内存访问请求时,会先查看缓存内是否有请求数据。如果存在(命中),则不经访问内存直接返回该数据;如果不存在(失效),则要先把内存中的相应数据载入缓存,再将其返回处理器。
缓存之所以有效,主要是因为程序运行时对内存的访问呈现局部性(Locality)特征。这种局部性既包括空间局部性(Spatial Locality),也包括时间局部性(Temporal Locality)。有效利用这种局部性,缓存可以达到极高的命中率。
在处理器看来,缓存是一个透明部件。因此,程序员通常无法直接干预对缓存的操作。但是,确实可以根据缓存的特点对程序代码实施特定优化,从而更好地利用缓存。

1.3.2 为什么需要有Cpu 高速缓存?

上文中我们提到冯诺依曼瓶颈。随着工艺的提升,最近几十年CPU的频率不断提升,而受制于制造工艺和成本限制,目前计算机的内存在访问速度上没有质的突破。因此,CPU的处理速度和内存的访问速度差距越来越大,这种情况下传统的 CPU 直连内存的方式显然就会因为内存访问的等待,导致计算资源大量闲置,降低 CPU 整体吞吐量。同时又由于内存数据访问的热点集中性,在 CPU 和内存之间用较为快速而成本较高(相对于内存)的介质做一层缓存,就显得性价比极高了。

1.3.3 Cpu 高速缓存架构

早期计算机系统的存储器层次结构只有三层:CPU寄存器、DRAM主存储器和磁盘存储。由于CPU和主存之间逐渐增大的差距,系统设计者被迫在CPU寄存器文件和主存之间插入了一个小的SRAM高速缓存存储器,称为L1高速缓存(一级缓存),如下图所示。L1高速缓存的访问速度几乎和寄存器相差无几。

CPU芯片示意图

随着CPU和主存之间的性能差距不断增大,系统设计者在L1高速缓存和主存之间又插入了一个更大的高速缓存,称为L2高速缓存,可以在大约10个时钟周期内访问到它。现代的操作系统还包括一个更大的高速缓存,称为L3高速缓存,在存储器的层次结构中,它位于L2高速缓存和主存之间,可以在大约50个周期内访问到它。下图是简单的高速缓存架构:

高速缓存架构

数据的读取和存储都经过高速缓存,CPU 核心与高速缓存有一条特殊的快速通道;主存与高速缓存都连在系统总线上(BUS),这条总线还用于其他组件的通信。

1.3.4 PHP7数组的设计

关于Cpu 高速缓存的应用,PHP7数组的设计是一个非常经典的案例。在PHP中数组是最常用的一种数据类型,提升数组的性能会使程序整体性能得到提升。我们通过对比PHP7和PHP5 数组的设计,来学习一下PHP
设计者为了提升PHP数组的性能,都进行了哪些思考。

我们先来总结一下PHP数组的特性:

  • php中的数组是一个字典dict,存储着key-value对,通过key可以快速的找到value,其中key可以是整形,也可以是字符串(hash array 和 packed array)。
  • 数组是有序的:插入有序、遍历有序。

PHP中数组使用hashTable实现,我们先来了解一下什么是hashTable。

hashTable是一种通过某种hash函数将特定的key映射到特定value的一种数据结构,它维护着键和值的一一对应关系,并且可以快速的根据键找到值(o(1)). 一般HashTable的示意图如下:

hashTable示意图

1) key: 通过key可以快速找到value。一般可以为数字或者字符串。
2) value: 值可以为复杂结构
3) bucket: 桶,HashTable存储数据的单元,用来存储key/value以及其他辅助信息的容器
4) slot:槽,HashTable有多少个槽,一个bucket必须属于具体的某一个slot,一个slot可以有多个
   bucket
5) 哈希函数:一般都是自己实现(time33),在存储的时候,会将key通过hash函数确定所在的slot
6) 哈希冲突: 当多个key经过哈希计算后,得到的slot位置是同一个,那么就会冲突,一般这个时候会有
   2种解决办法:链地址法和开放地址法。其中php采用的是链地址法,即将同一个slot中的bucket通过
   链表连接起来

为了实现数组的插入有序和遍历有序,PHP5使用hashTable + 双链表实现数组,如下图是将key分别为:“a”,”b”,”c”,”d”,值为“1”,”2″,”3″,”4″ 插入到数组中后的效果:

PHP5数组实现

上图中b,c,d所在的bucket被存分配到了同一个slot,为了解决hash冲突,slot中多个bucket通过双向链表关联,称为局部双向链表;为了实现有序,slot之间也通过双向链表关联,称为全局双向链表

了解php5数组的实现原理之后,我们发现其中影响性能的两个关键点:

  1. 频繁的内存分配!每向数组中添加一个元素,都需要申请分配一个bucket大小的内存,然后维护多个指针。虽然php是基于内存池的管理方式(预先申请大块内存进行按需分配),但是内存分配带来的性能损耗是不可忽略的。
  2. Cpu 高速缓存命中率低!因为bucket与bucket之间是通过链表指针连接的,bucket随机分配,内存基本不连续,导致Cpu cache降低,不能给遍历数组带来性能提升。

针对以上两点,php7对hashTable的设计进行了改造。既然是字典,还是要使用hashTable,但php7数组的实现去掉了slot,bucket的分配使用了连续内存;bucket间不再使用真实存在的指针进行维护,bucket只维护一个在数组中的索引,bucket与bucket之间通过内存地址进行关联,如下图所示:

PHP7中hashTable实现

PHP7中数组是如何解决hash冲突的?

PHP7对zval进行了改造,zval中有一个u2的union联合体,占用4字节大小,存放一些辅助信息。PHP7数组中的value也是一个个的zval指针,当发生hash冲突时,zval中u2部分存放的next指针存放指向下一个bucket数组中的索引,通过这样一种逻辑上的链表就巧妙解决hash冲突。关于PHP7中zval的设计,推荐大家阅读鸟哥的文章:深入理解PHP7内核之zval

可以看到,php7中hashTable对性能提升最重要的改动是bucket的分配使用了连续内存。这样不仅省去了数组元素插入时频繁的内存分配开销;遍历数组也只需要一个bucket一个bucket的访问就好了,Cpu 高速缓存命中率非常高,极大的提升了数组性能;符合局部性原理。

更多关于PHP5和PHP7数组的设计细节,推荐大家研究这篇文章:【PHP7源码学习】系列之数组实现

1.4 浏览器的多级缓存机制

举一个多级缓存的应用案例:浏览器对我们生活的影响是不言而喻的,现代的浏览器已经不同往昔了,快速的信息加载,顺畅的用户交互,这一切都得益于网络技术的普及、H5标准特性的推广应用,当然还有一个重要因素,那就是浏览器的缓存策略。本节我们就来简单介绍一下浏览器的多级缓存机制。

对于一个数据请求来说,可以分为发起网络请求、后端处理、浏览器响应三个步骤。浏览器缓存可以帮助我们在第一和第三步骤中优化性能。比如说直接使用缓存而不发起请求,或者发起了请求但后端存储的数据和前端一致,那么就没有必要再将数据回传回来,这样就减少了响应数据。

浏览器有四种缓存级别,它们各自都有优先级。

  • Service Worker
  • Memory Cache
  • Disk Cache
  • Push Cache

当依次查找缓存且都没有命中的时候,才会去请求网络。

1.4.1 Service Worker

Service Worker 是运行在浏览器背后的独立线程,一般可以用来实现缓存功能。使用 Service Worker的话,传输协议必须为 HTTPS。因为 Service Worker 中涉及到请求拦截,所以必须使用 HTTPS 协议来保障安全。Service Worker 的缓存与浏览器其他内建的缓存机制不同,它可以让我们自由控制缓存哪些文件、如何匹配缓存、如何读取缓存,并且缓存是持续性的

Service Worker 实现缓存功能一般分为三个步骤:首先需要先注册 Service Worker,然后监听到 install 事件以后就可以缓存需要的文件,那么在下次用户访问的时候就可以通过拦截请求的方式查询是否存在缓存,存在缓存的话就可以直接读取缓存文件,否则就去请求数据。

当 Service Worker 没有命中缓存的时候,我们需要去调用 fetch 函数获取数据。也就是说,如果我们没有在 Service Worker 命中缓存的话,会根据缓存查找优先级去查找数据。但是不管我们是从 Memory Cache 中还是从网络请求中获取的数据,浏览器都会显示我们是从 Service Worker 中获取的内容。

1.4.2 Memory Cache

Memory Cache 也就是内存中的缓存,主要包含的是当前页面中已经抓取到的资源,例如页面上已经下载的样式、脚本、图片等。读取内存中的数据肯定比磁盘快,内存缓存虽然读取高效,可是缓存持续性很短,会随着进程的释放而释放。 一旦我们关闭 Tab 页面,内存中的缓存也就被释放了。

当我们访问过页面以后,再次刷新页面,可以发现很多数据都来自于内存缓存

浏览器内存缓存

内存缓存中有一块重要的缓存资源是preloader相关指令(例如<link rel=”prefetch”>)下载的资源。众所周知preloader的相关指令已经是页面优化的常见手段之一,它可以一边解析js/css文件,一边网络请求下一个资源。

需要注意的事情是,内存缓存在缓存资源时并不关心返回资源的HTTP缓存头Cache-Control是什么值,同时资源的匹配也并非仅仅是对URL做匹配,还可能会对Content-Type,CORS等其他特征做校验。

为什么浏览器数据不都存放在内存中?

这个问题就算我不回答,读者肯定也都想明白了,计算机中的内存一定比硬盘容量小得多,操作系统需要精打细算内存的使用,所以能让我们使用的内存必然不多。谷歌浏览器是公认的性能出众的,但是它占用的内存也是很大的。

1.4.3 Disk Cache

Disk Cache 也就是存储在硬盘中的缓存,读取速度慢点,但是什么都能存储到磁盘中,比之 Memory Cache 胜在容量和存储时效性上。

在所有浏览器缓存中,Disk Cache 覆盖面基本是最大的。它会根据 HTTP Herder 中的字段判断哪些资源需要缓存,哪些资源可以不请求直接使用,哪些资源已经过期需要重新请求。并且即使在跨站点的情况下,相同地址的资源一旦被硬盘缓存下来,就不会再次去请求数据。绝大部分的缓存都来自 Disk Cache。

浏览器会把哪些文件丢进内存中?哪些丢进硬盘中?

关于这点,网上说法不一,不过有些观点比较靠得住:对于大文件来说,大概率是不存储在内存中的,另外如果当前系统内存使用率高的话,文件优先存储进硬盘。

1.4.4 Push Cache

Push Cache(推送缓存)是 HTTP/2 中的内容,当以上三种缓存都没有命中时,它才会被使用。它只在会话(Session)中存在,一旦会话结束就被释放,并且缓存时间也很短暂,在Chrome浏览器中只有5分钟左右,同时它也并非严格执行HTTP头中的缓存指令。

Push Cache 在国内能够查到的资料很少,也是因为 HTTP/2 在国内不够普及。这里推荐阅读Jake Archibald的 HTTP/2 push is tougher than I thought 这篇文章,文章中的几个结论是:

  • 所有的资源都能被推送,并且能够被缓存,但是 Edge 和 Safari 浏览器支持相对比较差
  • 可以推送 no-cache 和 no-store 的资源
  • 一旦连接被关闭,Push Cache 就被释放
  • 多个页面可以使用同一个HTTP/2的连接,也就可以使用同一个Push Cache。这主要还是依赖浏览器的实现而定,出于对性能的考虑,有的浏览器会对相同域名但不同的tab标签使用同一个HTTP连接。
  • Push Cache 中的缓存只能被使用一次
  • 浏览器可以拒绝接受已经存在的资源推送
  • 你可以给其他域名推送资源

如果以上四种缓存都没有命中的话,那么只能发起请求来获取资源了。

浏览器的多级缓存机制到这里就介绍完了,大家可以看到,浏览器多级缓存机制的实现思路,和我们前边说到的计算机系统多级缓存的知识是相呼应的,并且也满足局部性原理。浏览器缓存还有更多值得我们深入学习的内容,感兴趣的读者可以研究一下这篇文章:深入理解浏览器的缓存机制

2. 缓存淘汰策略

根据金字塔存储器层次模型我们知道:CPU访问速度越快的存储组件容量越小。在业务场景中,最常用的存储组件是内存和磁盘,我们往往将常用的数据缓存到内存中加快数据的读取速度,redis作为内存缓存数据库的设计也是基于这点考虑的。但是服务器的内存有限,不可能不断的将数据存入内存中而不淘汰。况且内存占用过大,也会影响服务器其它的任务,所以我们要做到通过淘汰算法让内存中的缓存数据发挥最大的价值。

本节将介绍业务中最常用的三种缓存淘汰算法:

  • 先进先出算法(FIFO)
  • Least Frequently Used(LFU)淘汰一定时期内被访问次数最少的页面,以次数作为参考
  • Least Recently Used(LRU)淘汰最长时间未被使用的页面,以时间作为参考

笔者会结合Redis、Mysql中缓存淘汰的具体实现机制来帮助读者学习到,Mysql和Redis的开发者是怎样结合各自的业务场景,对已有的缓存算法进行改进来满足业务需求的。

2.1 Least Recently Used(LRU)

LRU是Least Recently Used的缩写,这种算法认为最近使用的数据是热门数据,下一次很大概率将会再次被使用。而最近很少被使用的数据,很大概率下一次不再用到。使用链表就可以实现LRU:

lru缓存策略实现

新数据插入到链表头部;每当缓存命中(即缓存数据被访问),则将数据移到链表头部;当链表满的时候,将链表尾部的数据丢弃。

2.1.1 Mysql缓冲池LRU算法

在使用Mysql的业务场景中,如果使用上述我们描述的LRU算法来淘汰策略,会有一个问题。例如执行下面一条查询语句:

select * from table_a;

如果 table_a 中有大量数据并且读取之后不会继续使用,则LRU头部会被大量的 table_a 中的数据占据,这样会造成热点数据被逐出缓存从而导致大量的磁盘IO。所以Mysql缓冲池采用the least recently used(LRU)算法的变体,将缓冲池作为列表进行管理

Mysql的缓冲池

缓冲池(Buffer Pool)是主缓存器的一个区域,用于缓存索引、行的数据、自适应哈希索引、插入缓存(Insert Buffer)、锁 还有其他的内部数据结构。Buffer Pool的大小是可以根据我们实际的需求进行更改,那么Buffer Pool的size取多少比较合适?MySQL官网上是这么介绍,在专用服务器上(也就是服务器只承载一个MySQL实例),会将80%的物理内存给到Buffer Pool。Buffer Pool允许直接从内存中读常用数据去处理,会加快很多的速度。为了提高大容量读取操作的效率,Buffer Pool被分成可以容纳多行的页面。为了提高缓存管理的效率,Buffer Pool被实现为页面对应的链接的列表(a linked list of pages)。

Mysql数据库Buffer Pool结构:

Mysql中Buffer Pool结构

当需要空间将新页面缓存到缓冲池的时候,最近最少使用的页面将被释放出去,并将新的页面加入列表的中间。这个中间点插入的策略将列表分为两个子列表:

  • 1.头部是存放最近访问过的新页面的子列表

  • 2.尾部是存放那些最近访问较少的旧页面的子列表

该算法将保留 new sublist(也就是结构图中头部)中大量被查询使用的页面。而old sublist 里面较少被使用的页面作为被释放的候选项。

Buffer Pool的工作原理

理解以下几个关键点是比较重要的:

  • 3/8的缓冲池专用于old sublist(也就是3/8来保存旧的页面,其余部分用来存储热数据,存储热数据的部分相对大一些,当然这个值可以自己去调整,通过innodb_old_blocks_pct,其默认值是37,也就是3/8*100,上限100,可调整 5-95,可以改小一些,但是调整后尽量保证这个比例内的数据也就是old sublist中的数据只会被读取一次,若不是了解非常业务数据负载建议不要去修改。)
  • 列表的中点是新子列表的尾部与旧子列表的头部相交的边界。
  • 当InnoDB将页面读入缓冲池时,它最初将其插入中点(旧子列表的头部)。一个页面会被读取是因为它是用户指定的操作(如SQL查询)所需,或者是由InnoDB自动执行的预读操作的一部分 。
  • 访问旧子列表中的页面使其 “ 年轻 ”,将其移动到缓冲池的头部(新子列表的头部)。如果页面是被需要比如(SQL)读取的,它会马上访问旧列表并将页面推入新列表头部。如果预读需要读取的页面,则不会发生对旧列表的first access。
  • 随着数据库的运行,在缓冲池的页面没有被访问则向列表的尾部移动。新旧子列表中的页面随着其他页面的变化而变旧。旧子列表中的页面也会随着页面插入中点而老化。最终,仍未使用的页面到达旧子列表的尾部并被释放。默认情况下,页面被查询读取将被立即移入新列表中,在Buffer Pool中存在更长的时间。

通过对LRU算法的改进,InnoDB引擎解决了查询数据量大时,热点数据被逐出缓存从而导致大量的磁盘IO的问题

2.1.2 Redis近似LRU实现

由于真实LRU需要过多的内存(在数据量比较大时);并且Redis以高性能著称,真实的LRU需要每次访问数据时都做相关的调整,势必会影响Redis的性能发挥;这些都是Redis开发者所不能接受的,所以Redis是使用一种随机抽样的方式,来实现一个近似LRU的效果。

在Redis中有一个参数,叫做 “maxmemory-samples”,是干嘛用的呢?

 1 # LRU and minimal TTL algorithms are not precise algorithms but approximated 
 2 # algorithms (in order to save memory), so you can tune it for speed or 
 3 # accuracy. For default Redis will check five keys and pick the one that was 
 4 # used less recently, you can change the sample size using the following 
 5 # configuration directive. 
 6 # 
 7 # The default of 5 produces good enough results. 10 Approximates very closely 
 8 # true LRU but costs a bit more CPU. 3 is very fast but not very accurate. 
 9 # 
10 maxmemory-samples 5

上面我们说过了,近似LRU是用随机抽样的方式来实现一个近似的LRU效果。这个参数其实就是作者提供了一种方式,可以让我们人为干预样本数大小,将其设的越大,就越接近真实LRU的效果,当然也就意味着越耗内存。(初始值为5是作者默认的最佳)

Redis中近LRU的实现

左上图为理想中的LRU算法,新增加的key和最近被访问的key都不应该被逐出。可以看到,Redis2.8当每次随机采样5个key时,新增加的key和最近访问的key都有一定概率被逐出;Redis3.0增加了pool后效果好一些(右下角的图)。当Redis3.0增加了pool并且将采样key增加到10个后,基本等同于理想中的LRU(虽然还是有一点差距)。

Redis中对LRU代码实现也比较简单。Redis维护了一个24位时钟,可以简单理解为当前系统的时间戳,每隔一定时间会更新这个时钟。每个key对象内部同样维护了一个24位的时钟,当新增key对象的时候会把系统的时钟赋值到这个内部对象时钟。比如我现在要进行LRU,那么首先拿到当前的全局时钟,然后再找到内部时钟与全局时钟距离时间最久的(差最大)进行淘汰,这里值得注意的是全局时钟只有24位,按秒为单位来表示才能存储194天,所以可能会出现key的时钟大于全局时钟的情况,如果这种情况出现那么就两个相加而不是相减来求最久的key。

struct redisServer {
       pid_t pid; 
       char *configfile; 
       //全局时钟
       unsigned lruclock:LRU_BITS; 
       ...
};
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    /* key对象内部时钟 */
    unsigned lru:LRU_BITS;
    int refcount;
    void *ptr;
} robj;

总结一下:Redis中的LRU与常规的LRU实现并不相同,常规LRU会准确的淘汰掉队头的元素,但是Redis的LRU并不维护队列,只是根据配置的策略要么从所有的key中随机选择N个(N可以配置)要么从所有的设置了过期时间的key中选出N个键,然后再从这N个键中选出最久没有使用的一个key进行淘汰

2.2 Least Frequently Used(LFU)

LFU(Least Frequently Used)算法根据数据的历史访问频率来淘汰数据,其核心思想是“如果数据过去被访问多次,那么将来被访问的频率也更高”。LFU的每个数据块都有一个引用计数,所有数据块按照引用计数排序,具有相同引用计数的数据块则按照时间排序。LFU需要记录所有数据的访问记录,内存消耗较高;需要基于引用计数排序,性能消耗较高。在算法实现复杂度上,LFU要远大于LRU。

2.2.1 LFU缓存算法实现

本节笔者以leetcode上的一道算法题为例,使用代码实现LFU算法,帮助读者更深入的理解LFU算法的思想。

leetcode 460: LFU缓存

请你为 最不经常使用(LFU)缓存算法设计并实现数据结构。它应该支持以下操作:get 和 put。

  • get(key) – 如果键存在于缓存中,则获取键的值(总是正数),否则返回 -1。
  • put(key, value) – 如果键已存在,则变更其值;如果键不存在,请插入键值对。当缓存达到其容量时,则应该在插入新项之前,使最不经常使用的项无效。在此问题中,当存在平局(即两个或更多个键具有相同使用频率)时,应该去除最久未使用的键。
    「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。
    示例:
LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回 1
cache.put(3, 3);    // 去除 key 2
cache.get(2);       // 返回 -1 (未找到key 2)
cache.get(3);       // 返回 3
cache.put(4, 4);    // 去除 key 1
cache.get(1);       // 返回 -1 (未找到 key 1)
cache.get(3);       // 返回 3
cache.get(4);       // 返回 4

上一节我们聊到LRU算法,LRU的实现是一个哈希表加上一个双链表,比较简单。而LFU则要复杂多了,需要用两个哈希表再加上N个双链表才能实现
我们先看看LFU的两个哈希表里面都存了什么。

第一个哈希表是key-value的哈希表(以下简称kv哈希表)

LFU表中的kv

这里的key就是输入的key,没什么特别的。关键是value,它的value不是一个简单的value,而是一个节点对象。
节点对象Node包含了key,value,以及频率,这个Node又会出现在第二个哈希表的value中。
至于为什么Node中又重复包含了key,因为某些情况下我们不是通过k-v哈希表拿到Node的,而是通过其他方式获得了Node,之后需要用Node中的key去k-v哈希表中做一些操作,所以Node中包含了一些冗余信息。

第二张哈希表,频率哈希表,这个就要复杂多了

LFU中的hash表

这张哈希表中的key是频率,也就是元素被访问的频率(被访问了1次,被访问了两次等等),它的value是一个双向链表
刚才说的Node对象,现在又出现了,这里的Node其实是双向链表中的一个节点。
第一张图中我们介绍了Node中包含了一个冗余的key,其实它还包含了一个冗余的频率值,因为某些情况下,我们需要通过Node中的频率值,去频率哈希表中做查找,所以也需要一个冗余的频率值。

下面我们将两个哈希表整合起来看看完整的结构:

LFU整合数据结构

k-v哈希表中key1指向一个Node,这个Node的频率为1,位于频率哈希表中key=1下面的双链表中(处于第一个节点)。

根据上边的描述就可以定义出我们要使用到的数据结构和双链表的基本操作代码(使用Go语言):

type LFUCache struct {
    cache               map[int]*Node
	freq                map[int]*DoubleList
	ncap, size, minFreq int
}
//节点node
type Node struct {
	key, val, freq int
	prev, next     *Node
}
//双链表
type DoubleList struct {
	tail, head *Node
}
//创建一个双链表
func createDL() *DoubleList {
	head, tail := &Node{}, &Node{}
	head.next, tail.prev = tail, head
	return &DoubleList{
		tail: tail,
		head: head,
	}
}
func (this *DoubleList) IsEmpty() bool {
	return this.head.next == this.tail
}
//将node添加为双链表的第一个元素
func (this *DoubleList) AddFirst(node *Node) {
	node.next = this.head.next
	node.prev = this.head
	this.head.next.prev = node
	this.head.next = node
}
func (this *DoubleList) RemoveNode(node *Node) {
	node.next.prev = node.prev
	node.prev.next = node.next
	node.next = nil
	node.prev = nil
}
func (this *DoubleList) RemoveLast() *Node {
	if this.IsEmpty() {
		return nil
	}
	lastNode := this.tail.prev
	this.RemoveNode(lastNode)
	return lastNode
}

下边我们来看一下LFU算法的具体的实现吧,get操作相对简单一些,我们就先说get操作吧。
get操作的具体逻辑大致是这样:

  • 如果key不存在则返回-1
  • 如果key存在,则返回对应的value,同时:
    • 将元素的访问频率+1
      • 将元素从访问频率i的链表中移除,放到频率i+1的链表中
      • 如果频率i的链表为空,则从频率哈希表中移除这个链表

第一个很简单就不用说了,我们看下第二点的执行过程:

LFU中get的实现

假设某个元素的访问频率是3,现在又被访问了一次,那么就需要将这个元素移动到频率4的链表中。如果这个元素被移除后,频率3的那个链表变成空了(只剩下头结点和尾节点)就需要删除这个链表,同时删除对应的频率(也就是删除key=3),我们看下执行过程:

LFU中get元素删除链表

LFU中Get方法代码实现:

func (this *LFUCache) Get(key int) int {
    if node, ok := this.cache[key]; ok {
		this.IncrFreq(node)
		return node.val
	}
	return -1
}
func(this *LFUCache) IncrFreq(node *Node) {
	_freq := node.freq
	this.freq[_freq].RemoveNode(node)
	if this.minFreq == _freq && this.freq[_freq].IsEmpty() {
		this.minFreq++
		delete(this.freq, _freq)
	}
	node.freq++
	if this.freq[node.freq] == nil {
		this.freq[node.freq] = createDL()
	}
	this.freq[node.freq].AddFirst(node)
}

put操作就要复杂多了,大致包括下面几种情况

  • 如果key已经存在,修改对应的value,并将访问频率+1
    • 将元素从访问频率i的链表中移除,放到频率i+1的链表中
    • 如果频率i的链表为空,则从频率哈希表中移除这个链表
  • 如果key不存在
    • 缓存超过最大容量,则先删除访问频率最低的元素,再插入新元素
      • 新元素的访问频率为1,如果频率哈希表中不存在对应的链表需要创建
    • 缓存没有超过最大容量,则插入新元素
      • 新元素的访问频率为1,如果频率哈希表中不存在对应的链表需要创建

我们在代码实现中还需要维护一个minFreq的变量,用来记录LFU缓存中频率最小的元素,在缓存满的时候,可以快速定位到最小频繁的链表,以达到 O(1) 时间复杂度删除一个元素。
具体做法是:

  • 更新/查找的时候,将元素频率+1,之后如果minFreq不在频率哈希表中了,说明频率哈希表中已经没有元素了,那么minFreq需要+1,否则minFreq不变。
  • 插入的时候,这个简单,因为新元素的频率都是1,所以只需要将minFreq改为1即可。

我们重点看下缓存超过最大容量时是怎么处理的:

LFU中put操作

LFU中Put方法代码实现:

func (this *LFUCache) Put(key int, value int)  {
    if this.ncap == 0 {
		return
	}
	//节点存在
    if node, ok := this.cache[key]; ok {
		node.val = value
		this.IncrFreq(node)
	} else {
		if this.size >= this.ncap {
			node := this.freq[this.minFreq].RemoveLast()
			delete(this.cache, node.key)
			this.size--
		}
		x := &Node{key: key, val: value, freq: 1}
		this.cache[key] = x
		if this.freq[1] == nil {
			this.freq[1] = createDL()
		}
		this.freq[1].AddFirst(x)
		this.minFreq = 1
		this.size++
	}
}

通过对一道LFU基本算法的分析与实现,相信读者已经领悟到了LFU算法的思想及其复杂性。很多算法本身就是复杂的,不但要整合各种数据结构,还要根据应用场景进行分析,并不断改进。但是算法确确实实的解决很多实际的问题,我们已经知道了缓存的重要性,但一个好的缓存策略除了要充分利用各种计算机存储组件,良好的算法设计也是必不可少的。所以我们再来总体回顾一下本节LFU算法的实现吧:

type LFUCache struct {
    cache               map[int]*Node
	freq                map[int]*DoubleList
	ncap, size, minFreq int
}
func(this *LFUCache) IncrFreq(node *Node) {
	_freq := node.freq
	this.freq[_freq].RemoveNode(node)
	if this.minFreq == _freq && this.freq[_freq].IsEmpty() {
		this.minFreq++
		delete(this.freq, _freq)
	}
	node.freq++
	if this.freq[node.freq] == nil {
		this.freq[node.freq] = createDL()
	}
	this.freq[node.freq].AddFirst(node)
}
func Constructor(capacity int) LFUCache {
    return LFUCache{
		cache: make(map[int]*Node),
		freq:  make(map[int]*DoubleList),
		ncap:  capacity,
	}
}
func (this *LFUCache) Get(key int) int {
    if node, ok := this.cache[key]; ok {
		this.IncrFreq(node)
		return node.val
	}
	return -1
}
func (this *LFUCache) Put(key int, value int)  {
    if this.ncap == 0 {
		return
	}
	//节点存在
    if node, ok := this.cache[key]; ok {
		node.val = value
		this.IncrFreq(node)
	} else {
		if this.size >= this.ncap {
			node := this.freq[this.minFreq].RemoveLast()
			delete(this.cache, node.key)
			this.size--
		}
		x := &Node{key: key, val: value, freq: 1}
		this.cache[key] = x
		if this.freq[1] == nil {
			this.freq[1] = createDL()
		}
		this.freq[1].AddFirst(x)
		this.minFreq = 1
		this.size++
	}
}
//节点node
type Node struct {
	key, val, freq int
	prev, next     *Node
}
//双链表
type DoubleList struct {
	tail, head *Node
}
//创建一个双链表
func createDL() *DoubleList {
	head, tail := &Node{}, &Node{}
	head.next, tail.prev = tail, head
	return &DoubleList{
		tail: tail,
		head: head,
	}
}
func (this *DoubleList) IsEmpty() bool {
	return this.head.next == this.tail
}
//将node添加为双链表的第一个元素
func (this *DoubleList) AddFirst(node *Node) {
	node.next = this.head.next
	node.prev = this.head
	this.head.next.prev = node
	this.head.next = node
}
func (this *DoubleList) RemoveNode(node *Node) {
	node.next.prev = node.prev
	node.prev.next = node.next
	node.next = nil
	node.prev = nil
}
func (this *DoubleList) RemoveLast() *Node {
	if this.IsEmpty() {
		return nil
	}
	lastNode := this.tail.prev
	this.RemoveNode(lastNode)
	return lastNode
}

2.2.2 Redis LFU淘汰策略

一般情况下,LFU效率要优于LRU,且能够避免周期性或者偶发性的操作导致缓存命中率下降的问题,在如下情况下:

~~~~~A~~~~~A~~~~~A~~~~A~~~~~A~~~~~A~~|
~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~|
~~~~~~~~~~C~~~~~~~~~C~~~~~~~~~C~~~~~~|
~~~~~D~~~~~~~~~~D~~~~~~~~~D~~~~~~~~~D|

会将数据D误认为将来最有可能被访问到的数据。

Redis作者曾想改进LRU算法,但发现Redis的LRU算法受制于随机采样数maxmemory_samples,在maxmemory_samples等于10的情况下已经很接近于理想的LRU算法性能,也就是说,LRU算法本身已经很难再进一步了。

于是,将思路回到原点,淘汰算法的本意是保留那些将来最有可能被再次访问的数据,而LRU算法只是预测最近被访问的数据将来最有可能被访问到。我们可以转变思路,采用LFU(Least Frequently Used)算法,也就是最频繁被访问的数据将来最有可能被访问到。在上面的情况中,根据访问频繁情况,可以确定保留优先级:B>A>C=D。

在LFU算法中,可以为每个key维护一个计数器。每次key被访问的时候,计数器增大。计数器越大,可以约等于访问越频繁。

上述简单算法存在两个问题:

  • 在LRU算法中可以维护一个双向链表,然后简单的把被访问的节点移至链表开头,但在LFU中是不可行的,节点要严格按照计数器进行排序,新增节点或者更新节点位置时,时间复杂度可能达到O(N)。
  • 只是简单的增加计数器的方法并不完美。访问模式是会频繁变化的,一段时间内频繁访问的key一段时间之后可能会很少被访问到,只增加计数器并不能体现这种趋势。
    第一个问题很好解决,可以借鉴LRU实现的经验,维护一个待淘汰key的pool。第二个问题的解决办法是,记录key最后一个被访问的时间,然后随着时间推移,降低计数器。

Redis对象的结构如下:

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;

在LRU算法中,24 bits的lru是用来记录LRU time的,在LFU中也可以使用这个字段,不过是分成16 bits与8 bits使用:

       16 bits      8 bits
      +----------------+--------+
      + Last decr time | LOG_C  |
      +----------------+--------+

高16 bits用来记录最近一次计数器降低的时间ldt,单位是分钟,低8 bits记录计数器数值counter。

Redis4.0之后为maxmemory_policy淘汰策略添加了两个LFU模式:

  • volatile-lfu:对有过期时间的key采用LFU淘汰算法
  • allkeys-lfu:对全部key采用LFU淘汰算法

还有2个配置可以调整LFU算法:

lfu-log-factor 10
lfu-decay-time 1
  • lfu-log-factor可以调整计数器counter的增长速度,lfu-log-factor越大,counter增长的越慢。

  • lfu-decay-time是一个以分钟为单位的数值,可以调整counter的减少速度

源码实现

在lookupKey中:

robj *lookupKey(redisDb *db, robj *key, int flags) {
    dictEntry *de = dictFind(db->dict,key->ptr);
    if (de) {
        robj *val = dictGetVal(de);
        /* Update the access time for the ageing algorithm.
         * Don't do it if we have a saving child, as this will trigger
         * a copy on write madness. */
        if (server.rdb_child_pid == -1 &&
            server.aof_child_pid == -1 &&
            !(flags & LOOKUP_NOTOUCH))
        {
            if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
                updateLFU(val);
            } else {
                val->lru = LRU_CLOCK();
            }
        }
        return val;
    } else {
        return NULL;
    }
}

当采用LFU策略时,updateLFU更新lru:

/* Update LFU when an object is accessed.
 * Firstly, decrement the counter if the decrement time is reached.
 * Then logarithmically increment the counter, and update the access time. */
void updateLFU(robj *val) {
    unsigned long counter = LFUDecrAndReturn(val);
    counter = LFULogIncr(counter);
    val->lru = (LFUGetTimeInMinutes()<<8) | counter;
}

降低LFUDecrAndReturn

首先,LFUDecrAndReturn对counter进行减少操作:

/* If the object decrement time is reached decrement the LFU counter but
 * do not update LFU fields of the object, we update the access time
 * and counter in an explicit way when the object is really accessed.
 * And we will times halve the counter according to the times of
 * elapsed time than server.lfu_decay_time.
 * Return the object frequency counter.
 *
 * This function is used in order to scan the dataset for the best object
 * to fit: as we check for the candidate, we incrementally decrement the
 * counter of the scanned objects if needed. */
unsigned long LFUDecrAndReturn(robj *o) {
    unsigned long ldt = o->lru >> 8;
    unsigned long counter = o->lru & 255;
    unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
    if (num_periods)
        counter = (num_periods > counter) ? 0 : counter - num_periods;
    return counter;
}

函数首先取得高16 bits的最近降低时间ldt与低8 bits的计数器counter,然后根据配置的lfu_decay_time计算应该降低多少。

LFUTimeElapsed用来计算当前时间与ldt的差值:

/* Return the current time in minutes, just taking the least significant
 * 16 bits. The returned time is suitable to be stored as LDT (last decrement
 * time) for the LFU implementation. */
unsigned long LFUGetTimeInMinutes(void) {
    return (server.unixtime/60) & 65535;
}
/* Given an object last access time, compute the minimum number of minutes
 * that elapsed since the last access. Handle overflow (ldt greater than
 * the current 16 bits minutes time) considering the time as wrapping
 * exactly once. */
unsigned long LFUTimeElapsed(unsigned long ldt) {
    unsigned long now = LFUGetTimeInMinutes();
    if (now >= ldt) return now-ldt;
    return 65535-ldt+now;
}

具体是当前时间转化成分钟数后取低16 bits,然后计算与ldt的差值now-ldt。当ldt > now时,默认为过了一个周期(16 bits,最大65535),取值65535-ldt+now。

然后用差值与配置lfu_decay_time相除,LFUTimeElapsed(ldt) / server.lfu_decay_time,已过去n个lfu_decay_time,则将counter减少n,counter – num_periods。

增长LFULogIncr

增长函数LFULogIncr如下:

/* Logarithmically increment a counter. The greater is the current counter value
 * the less likely is that it gets really implemented. Saturate it at 255. */
uint8_t LFULogIncr(uint8_t counter) {
    if (counter == 255) return 255;
    double r = (double)rand()/RAND_MAX;
    double baseval = counter - LFU_INIT_VAL;
    if (baseval < 0) baseval = 0;
    double p = 1.0/(baseval*server.lfu_log_factor+1);
    if (r < p) counter++;
    return counter;
}

counter并不是简单的访问一次就+1,而是采用了一个0-1之间的p因子控制增长。counter最大值为255。取一个0-1之间的随机数r与p比较,当r<p时,才增加counter,这和比特币中控制产出的策略类似。p取决于当前counter值与lfu_log_factor因子,counter值与lfu_log_factor因子越大,p越小,r<p的概率也越小,counter增长的概率也就越小。增长情况如下:

# +--------+------------+------------+------------+------------+------------+
# | factor | 100 hits   | 1000 hits  | 100K hits  | 1M hits    | 10M hits   |
# +--------+------------+------------+------------+------------+------------+
# | 0      | 104        | 255        | 255        | 255        | 255        |
# +--------+------------+------------+------------+------------+------------+
# | 1      | 18         | 49         | 255        | 255        | 255        |
# +--------+------------+------------+------------+------------+------------+
# | 10     | 10         | 18         | 142        | 255        | 255        |
# +--------+------------+------------+------------+------------+------------+
# | 100    | 8          | 11         | 49         | 143        | 255        |
# +--------+------------+------------+------------+------------+------------+

可见counter增长与访问次数呈现对数增长的趋势,随着访问次数越来越大,counter增长的越来越慢。

新生key策略

另外一个问题是,当创建新对象的时候,对象的counter如果为0,很容易就会被淘汰掉,还需要为新生key设置一个初始counter,createObject:

robj *createObject(int type, void *ptr) {
    robj *o = zmalloc(sizeof(*o));
    o->type = type;
    o->encoding = OBJ_ENCODING_RAW;
    o->ptr = ptr;
    o->refcount = 1;
    /* Set the LRU to the current lruclock (minutes resolution), or
     * alternatively the LFU counter. */
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    } else {
        o->lru = LRU_CLOCK();
    }
    return o;
}

counter会被初始化为LFU_INIT_VAL,默认5。

至此,对Redis的LFU淘汰策略已经分析完了,相信读者也发现了:Redis中LFU实现策略比LRU还是要复杂很多的。

2.3 先进先出算法(FIFO)

FIFO(First in First out),先进先出。在FIFO Cache设计中,核心原则就是:如果一个数据最先进入缓存中,则应该最早淘汰掉。实现方法很简单,只要使用队列数据结构即可实现。

FIFO缓存淘汰过程

因为缓存命中率比较低,FIFO缓存策略通常不会在项目中使用。每一种淘汰算法都有其存在使用的价值。熟悉Redis主从复制过程的读者应该有印象,主从复制过程中的复制积压缓冲区就是一个FIFO的队列。

什么是复制挤压缓冲区?

复制挤压缓冲区是一个先进先出(FIFO)的环形队列,用于存储服务端执行过的命令,每次传播命令,master节点都会将传播的命令记录下来,保存在这里。

复制积压缓冲区由两部分组成:偏移量和字节值。字节值是redis指令字节的存储(redis指令以一种Redis序列化文本协议的格式存储),偏移量offset就是当前字节值在环形队列中的偏移量。

不太明白复制积压缓冲区是什么,有什么作用的读者可以阅读我的另外一篇博客:Redis高可用——主从复制,在这里我们只需要知道FIFO是一种简单的缓存淘汰策略就可以了,它也有自己的一些应用场景。

2.4 FIFO、LRU、LFU缓存淘汰策略对比

本节花费了大量篇幅介绍缓存淘汰策略,我们再来从缓存命中率、实现复杂度、存储成本、缺陷这四个方面来对这三种缓存策略做一个对比:

缓存淘汰策略缓存命中率实现复杂度存储成本缺陷
FIFO非常简单很低速度很快,不过没有什么实用价值
LRU相对简单偶发性的、周期性的批量操作会导致LRU命中率急剧下降,缓存污染情况比较严重。
LFU非常高相对复杂很高,需要很大的存储空间L存在历史数据影响将来数据的“缓存污染”

针对各种缓存淘汰策略的缺陷,Redis、Mysql都结合自身的业务场景进行了改进,虽然不可能做到完美,也极大的提升了缓存命中率。

3. 缓存安全

//TODO

https://juejin.im/post/5e9ad171518825738f2b30de

「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论