fwq

缓存替换策略及应用(以Redis、InnoDB为例) 0浏览 收藏 本篇文章主要是结合我之前面试的各种经历和实战开发中遇到的问题解决经验整理的，希望这篇《缓存替换策略及应用(以Redis、InnoDB为例)》对你有很大帮助！欢迎收藏，分享给更多的需要的朋友学习~ 1 概述 在操作系统的页面管理中，内存会维护一部分数据以备进程使用，但是由于内存的大小必然是远远小于硬盘的，当某些进程访问到内存中没有的数据时，必然需要从硬盘中读进内存，所以迫于内存容量的压力下迫使操作系统将一些页换出，或者说踢出，而决定将哪些（个）页面踢出就是内存替换策略。 我们考虑内存中的页实际上是整个系统页的子集，所以内存可以当成系统中虚拟内存的缓存（Cache），所以页面置换算法就是缓存替换的方法。 一般意义下，选取页面置换算法即选取一个缓存命中率更高的或者说缺页率更低的算法，但实际上有时候随着算法缓存命中率提升，算法复杂度也在上升，所以带来的系统开销也是在上升的，所以我们不得不在系统开销和算法复杂程度中间取一个折中，比如Redis中采取的类LRU缓存置换策略实际上在大多数情况下比起理想LRU缓存命中率是低的，但理想LRU实现起来会给系统带来更大的开销，得不偿失。 2 页面置换算法 下面介绍最常见的五种置换策略，其中最佳置换算法是理论上很难实现的，其余的FIFO、LRU、LFU，其算法复杂度、开销是递增的，但是缺页率也是越来越低，或者说越来越接近最佳置换策略的。最后一种时钟置换算法是一种近似的LRU算法，是保证了低系统开销下同时较低的缺页率的一种折中选择。 2.1 最佳（Optimal）置换算法 最佳置换算法，其所选择的被淘汰的页面将是以后永不使用的，或是在最长（未来）时间内不再被访问的页面。听名字定义很显然页面未来的使用情况它就不可预测，所以最佳置换算法只是理论上的最优方法，实际上在大多数情况下并没法完成，所以更多的是作为衡量其他置换算法的标准。 2.2 先进先出（FIFO）置换算法 许多早期的操作系统为了保证算法的简单，避免高复杂度的算法，尝试了最简单的置换策略，即FIFO置换策略，顾名思义就是维护一个页的队列，最先进入内存的页最先被淘汰，这样的算法复杂度低，系统开销也极低，但是显然命中率会下降。 另外考虑一种情况，增大缓存时，一般意义下缓存的命中率必然会上升，但是FIFO算法则在有的时候则会下降，这种现象叫做Belady现象。原因是FIFO算法没有考虑到程序的局部性原则，踢出的页面很可能是程序经常性访问的页面。 Belady现象的实例分析可以参考 2.3 最近最少使用（Least Recently Used,LRU）置换算法 为了解决Belady现象，同时也是基于程序的局部性原则（Locality of reference，指的是在计算机科学计算机科学领域中应用程序在访问内存的时候，倾向于访问内存中较为靠近的值。）就有了LRU置换策略，从程序代码的角度理解局部性原则就是，程序一般倾向于频繁的访问某些代码（比如循环）或者数据结构（比如循环访问的数组），因此我们应该使用历史访问数据来决定，哪些页应该被踢出，哪些页不应该被踢出，具体的就是，最近没有被访问的页优先被踢出。这个其实不难理解，通过一个访问顺序的队列，每次访问某个页，就将此页移到队首，当内存（缓存）满了时优先从队尾踢出相应的页。（下面给出一个例子，表来自操作系统导论第22章） 但是显然的是，LRU会带来更大的系统开销，因为我们需要频繁的将访问过的页置于访问序列的首部，这就需要对访问队列的内容进行频繁的增删，而FIFO只需要简单排列即可。…

Redis持久化原理实例分析 0浏览 收藏 哈喽！今天心血来潮给大家带来了《Redis持久化原理实例分析》，想必大家应该对数据库都不陌生吧，那么阅读本文就都不会很困难，以下内容主要涉及到，若是你正在学习数据库，千万别错过这篇文章~希望能帮助到你！ Redis是一个内存数据库，所有的数据将保存在内存中，这与传统的MySQL、Oracle、SqlServer等关系型数据库直接把数据保存到硬盘相比，Redis的读写效率非常高。但是保存在内存中也有一个很大的缺陷，一旦断电或者宕机，内存数据库中的内容将会全部丢失。为了弥补这一缺陷，Redis提供了把内存数据持久化到硬盘文件，以及通过备份文件来恢复数据的功能，即Redis持久化机制。 Redis支持两种方式的持久化：RDB快照和AOF。 RDB持久化 RDB快照用官方的话来说：RDB持久化方案是按照指定时间间隔对你的数据集生成的时间点快照（point-to-time snapshot）。它以紧缩的二进制文件保存Redis数据库某一时刻所有数据对象的内存快照，可用于Redis的数据备份、转移与恢复。到目前为止，仍是官方的默认支持方案。 RDB工作原理 既然说RDB是Redis中数据集的时间点快照，那我们先简单了解一下Redis内的数据对象在内存中是如何存储与组织的。 默认情况下，Redis中有16个数据库，编号从0-15，每个Redis数据库使用一个redisDb对象来表示，redisDb使用hashtable存储K-V对象。为方便理解，我以其中一个db为例绘制Redis内部数据的存储结构示意图。 时间点快照也就是某一时刻Redis内每个DB中每个数据对象的状态，先假设在这一时刻所有的数据对象不再改变，我们就可以按照上图中的数据结构关系，把这些数据对象依次读取出来并写入到文件中，以此实现Redis的持久化。然后，当Redis重启时按照规则读取这个文件中的内容，再写入到Redis内存即可恢复至持久化时的状态。 当然，这个前提时我们上面的假设成立，否则面对一个时刻变化的数据集，我们无从下手。我们知道Redis中客户端命令处理是单线程模型，如果把持久化作为一个命令处理，那数据集肯定时处于静止状态。另外，操作系统提供的fork()函数创建的子进程可获得与父进程一致的内存数据，相当于获取了内存数据副本；fork完成后，父进程该干嘛干嘛，持久化状态的工作交给子进程就行了。 很显然，第一种情况不可取，持久化备份会导致短时间内Redis服务不可用，这对于高HA的系统来讲是无法容忍的。所以，第二种方式是RDB持久化的主要实践方式。由于fork子进程后，父进程数据一直在变化，子进程并不与父进程同步，RDB持久化必然无法保证实时性；RDB持久化完成后发生断电或宕机，会导致部分数据丢失；备份频率决定了丢失数据量的大小，提高备份频率，意味着fork过程消耗较多的CPU资源，也会导致较大的磁盘I/O。 持久化流程 在Redis内完成RDB持久化的方法有rdbSave和rdbSaveBackground两个函数方法（源码文件rdb.c中），先简单说下两者差别： rdbSave：是同步执行的，方法调用后就会立刻启动持久化流程。由于Redis是单线程模型，持久化过程中会阻塞，Redis无法对外提供服务； rdbSaveBackground：是后台（异步）执行的，该方法会fork出子进程，真正的持久化过程是在子进程中执行的（调用rdbSave），主进程会继续提供服务； RDB持久化的触发必然离不开以上两个方法，触发的方式分为手动和自动。手动触发容易理解，是指我们通过Redis客户端人为的对Redis服务端发起持久化备份指令，然后Redis服务端开始执行持久化流程，这里的指令有save和bgsave。自动触发是Redis根据自身运行要求，在满足预设条件时自动触发的持久化流程，自动触发的场景有如下几个（摘自这篇文章）： serverCron中save m n配置规则自动触发； 从节点全量复制时，主节点发送rdb文件给从节点完成复制操作，主节点会出发bgsave； 执行debug reload命令重新加载redis时； 默认情况下（未开启AOF）执行shutdown命令时，自动执行bgsave； 结合源码及参考文章，我整理了RDB持久化流程来帮助大家有个整体的了解，然后再从一些细节进行说明。…