计算机访问数据经常会呈现出局部性原理,包括空间局部性和时间局部性

  • 空间局部性:,计算机访问数据,存储在邻近的数据也经常会被访问
  • 时间局部性:相对的一小段时间内,计算机经常会访问相同的数据

计算机从硬盘中读块,不会只读你要的特定块,附近的快很有可能接下来要被访问,会把这些块也一起预读出来

接下来要读附近的快的时候,就不需要再访问硬盘了。这样,运用局部性原理就减少了访问磁盘的次数。附近的块就被缓存了起来,加快了运行速度

缓存下所有东西必定不可能,不仅没有那么大的存储器,而且缓存会大大增加你编程的复杂性,所以缓存必定就是一个trade-Off的存在,权衡各种利弊,无法量化的时候甚至就靠直觉和经验了

缓存这个用空间换时间的概念存在着计算机的各个领域,cpu、操作系统、计算机网络、数据库

计算机缓存山

每一层都可以看做下一层的高速缓存,从山顶到山脚,计算机访问到的时间递增,而每一层的物理硬件造价递减

cpu计算数据先从山顶开始找数据,如果本层没有找到就去下层找,每向下找一层,找的层数越多,计算所需的时间自然就越多

如何找到对应的缓存?

索引+映射

为缓存的内容增加索引

对cpu运算的数据,索引按地址划分出来

对应用层来说索引就是缓存的key值

索引可以分为一对一相联、组相联、全相联

索引构成了一个的集合,缓存构成了一个的集合,这两个集合之间有映射关系,直接从索引集合查找就可以找到对应的缓存了

为什么不直接从缓存集合找?

假设缓存容量4KB,每个缓存为16B,一共256个缓存

缓存索引范围0到255,索引集合占256B

如果从索引集合查找,只需遍历256B的空间,从缓存集合查找需要遍历4KB的空间,明显索引集合可以加快查找的速度

这也就是为什么用一个小的空间去映射大的空间

cpu缓存策略:

cpu在寄存器中计算数据,而数据存储在内存中,由于cpu和内存之间的性能逐渐增大,系统设计者在cpu和内存之间插入了3层的高速缓存。高速缓存有三个层级,就是整个计算机缓存系统的一个小缩影

缓存涉及到,读操作、写操作和层级之间如何协调、缓存容量满了后的淘汰算法。淘汰下面会讲,这里关注一下读写操作和层级之间的协调

高速缓存的读很简单,先从高层读数据,如果缓存命中了就返回数据。如果不命中就去低层读,如果从低层命中,返回数据的同时将低层的数据写入高层

高速缓存的写复杂一点,先直接向高层写入数据,但何时向低层写入?

  • 直写(write-through),立即向低层写入
  • 写回(write-back),等到算法淘汰的时候再向底层写入

直写实现简单,但每次写入都会有更多的总线流量

第二种,减少了总线流量,增加了复杂度,必须为每个缓存对象保存是否修改(dirty位),即是否写入低层。向低层写,时间消耗主要在访问的时间上,每次写的量多少,差别不大。高速缓存就是使用的写回,Mongo也是写回

抽象块:

理解操作系统的缓存策略之前,有一个重要的概念就是抽象块

抽象主要的目的是为了隐藏不同层次的细节

比如,硬盘传输数据给内存,硬盘传输的是一个块(block),这个块就是对于硬盘的抽象,硬盘要想找到数据,必须进行磁盘的旋转和寻道,内存根本不管心,硬盘旋转了几圈还是数据在那条道上,内存只关心数据是什么,所以,硬盘只给内存一个块(block),硬盘向内存隐藏如何存取的细节

同样的思想也在网络五层协议中,每层都给高层或底层一个“块”(实际上叫包,packet),本层不关心其他层的细节,本层直接在块上头部和尾部加上自己层做的事,然后传给高层或者低层,应用层管本层的块叫报文,传输层叫报文段,网络层叫数据报

毕加索的牛抽象过程,一步一步隐藏细节,嗯,到最后已不能看出是牛了。。

操作系统缓存策略:

操作系统中,硬盘给内存的抽象块就是页(page)

从磁盘上读取页导致的I/O是很耗时间的,所以页就被缓存在内存中,这就是页的缓存

操作系统调用文件系统就使用这种页缓存。简单来说,内存中的页也就成了文件系统的缓存

linux的cache

主要三个关键部分,内存管理系统、虚拟文件系统(VFS)、文件系统,页实际上将他们联系在一起,文件系统负责将页从硬盘读出或写入硬盘,虚拟文件系统负责将页传递给内存管理系统和从内存管理系统接收页,内存负责管理页的分配或回收和置换策略。内存管理系统如何管理就是我们需要关注的

平时在编程的时候,包括CPU接触到的都是虚拟地址而不是真实的物理地址

这是虚拟存储器(也译作虚拟内存)的一大主要功能

假如有个页的地址,想找到一个页,需要将页的虚拟地址转化为页的物理地址

页表(page table)和MMU就负责将页的虚拟地址映射到物理地址

页表负责记录哪些虚拟页映射了物理页,以及这些页的PTE(页表条目)

而MMU是一个物理硬件,MMU负责进行虚拟地址进行物理地址的翻译,翻译过程中需要从页表获取页的PTE,MMU也会用TLB缓存页号,计算机从硬件到软件都有缓存!

页表不一定只映虚拟页,还有可能是文件本身,这样就相当于将文件直接载入了内存,直接访问内存就直接访问文件了,这个过程叫mmap(Memory Map)。MongDB使用的就是mmap

lnux文件文件系统cache分为Page Cache、Buffer Cache

如何取出页的物理地址?

先看虚拟页是否有映射物理页,如果有映射,就直接返回,如果没有映射,就会发生缺页中断。将相应的物理页缓存在内存,并与虚拟页映射。再进行一次查找,这次查找虚拟页就会映射物理页。但是,内存容量有限,不能让所有物理页都缓存,需要用算法淘汰掉不需要的物理页

FIFO:先进先出算法,每次淘汰掉停留时间最长的算法,这种算法并不常用,因为他很可能淘汰掉经常使用的页面。

LRU(Least Recently Used):选择最近一段时间内未使用过的页面置换掉。这种算法非常优秀,但是操作系统实现它还需要硬件支持,实现起来相当费时,所以又涌现了很多模仿LRU的算法,更加实用,NRU、NFU、2Q、MQ、Clock等

数据库缓存策略:

和操作系统缓存策略相似,数据库将块缓存在内存上,叫做缓冲区(buffer),由缓存区管理器管理,大多数数据库使用的算法为近似LRU算法

数据库缓存为了在崩溃后,也要保持一致性,有时会将块强制写回,有时会限制块的写回

缓存时常在多线程上进行操作,那么共享变量就一定要加锁

建议内存缓存使用自旋锁,磁盘缓存使用信号量

自旋锁,会一直询问锁是否开了,会占用大量的资源,只适合等待时间很短就能进行的操作

信号量会在问完是否开以后,睡眠一段时间,更适合长时间等待的操作

而OSSpinLock在iOS中并不是线程安全的在,可以用mutex锁替代


如果缓存的内容是从网络获取的话,还有很多可以做的

而网络缓存就是使用http提供的缓存报头字段,Expires、E-Tag、Last-Modified

总体策略就是,定义一个过期时间,等到过期才回去服务器请求,请求还可以查看服务器的实体是否发生了变化,没有发生变化,就只需要告诉客户端没有变化,不用再返回一遍所请求数据,浪费流量


linux的文件cache分为page cache和buffer cache

实际上,一个page cache对应多个buffer cache

这两个东西容易傻傻分不清楚,将他们分开很有必要

首先,page cache和buffer cache在不同层次

page cache在vfs和内存管理系统数据交换,这一文件系统逻辑层次上

而buffer cache在具体文件系统,这一文件系统物理层次上。其次page cache和buffer cache不是为了同一个目的,page cache就是页,作为文件系统在内存上的缓存

buffer cache是缓冲区,读写磁盘的时候为了减少I/O的数量,攒齐一定量的数据再写和攒齐一定数量读出的数据再返回

linux如何实现LRU

linux的页面调度算法用的是LRU,用两个双向链表实现。active_list和inactive_list

active_list存放最近被访问频路较高的,inactive_list存放最近访问频率较低的的

链表节点有是否被访问的状态,设为referenced状态表示正在被访问,设置unreferenced表示没被访问

具体算法如下,新加入的节点插入到inactive_list的首部。淘汰的时候,遍历一遍active_list的节点,将unreferenced状态的节点插入到inactive_list首部,然后从inactive_list尾部开始逐个淘汰

改良版的LRU 2Q算法,用两个优先队列完成算法。最近访问过一次,不算是“常”访问。最近没访问,也不直接淘汰

文件随机访问cache

linux用的是radix tree(基数树)来加速随机访问

radix tree将文件内偏移量和其对应的cache对应起来。radix tree分为叶子节点和非叶子节点。非叶子节点指向其他节点。叶子节点指向cache。从根节点到叶子节点的路径上所经过的节点的键值拼接起来就是文件内偏移量的地址

mmap

mmap相当于将文件的页载入内存,进程修改内存指针的内容就修改了文件

页缓存是将文件缓存进了内存,载入和缓存入是有不同的。进程通过页缓存访问文件需要经过两次拷贝,由于页缓存在内核空间中,先要将页缓存入内核空间,再将页拷贝给进程。进程通过mmap访问文件需要一次拷贝

不需要将页拷贝入内核,直接拷贝给进程就可以。所以mmap效率更高

swap

swap和文件cache的目的是完全不同的,swap是当内存容量告急,将内存上的数据交换到硬盘上

swap的内容是堆上申请的空间,本来就是内存中的计算数据,而不是像页本来是硬盘上的数据。swap在现在的操作系统中,大多默认是不开启的

swap可想而知会耗费大量I/O和内存。在iOS中,没有swap机制,才会出现内存告急的时候,系统发给你一个通知,你如果不做处理就会被kill掉

数据库为何快过文件存取?

数据库建立的索引和查询器优化都是优化速度的关键

数据库索引

分为顺序索引、B+树索引、hash索引

1.顺序索引为每个文件建立一个数组索引,块中的元组按逻辑存储的顺序用链表连接起来,加速顺序访问(类LlinkedHashMap结构)

2.B+树索引为文件建立一个B+树,B+树分为叶子节点和非叶子节点。非叶子节点包含(本层高度-1)/2到(本层高度-1)个索引和索引对应的其他节点。叶子节点包含(本层高度-1)/2到(本层高度-1)个索引和索引对应的元组地址

3.hash索引为文件建立一个hash表,映射索引和索引对应的元组地址

索引的目的就是减少磁盘块的I/O

假如存入文件,需要把文件所有块整个读取入内存

而存入数据库,只需要将存储索引的块和所查找的元组所在的块读入内存就可以了。大部分情况,存储索引的块一般已经缓存在内存了,这就需要更少的磁盘块的I/O了

查询器优化

查询器优化,这是数据库的精髓,不同数据库使用的策略不同

假设要找出两个关系之间的相同值,需要将这两个关系进行join,有3种优化方法

1.nested loop join,将所有数据取出,双层for循环两个关系的元组,O(M N)。这个方法有改进的空间,利用空间局部性,改进为包含两个块的双层for循环,先循环块再循环块内的元组,复杂度同样是O(M N),但这个M和N指的是块的数量而不是元组的数量

2.hash join,为一个关系中的所有元组建立一个拉链法的hash表,对另一个关系用同样的hash函数,再将映射到同一表项中的元组,判断是否值相等。如果内存足够的话,将hash表放入内存中,这种方法会很快,否则就要添加多次的hash表的I/O,O(M + N)

3.排序-归并-连接(merge-join),先将两个关系排序,如果两个关系装不下内存,就要外部排序。然后再像归并排序那样判断元组是否相等,O(M + N)

SQL语句会被数据库解释成关系代数,因为关系代数有等价性,也就是说可以解释成多个关系代数,形成多个查询计划

多个关系连接顺序形成多种的排序方式,每个关系连接可以使用不同种的join方式,乘起这两个数是很大的数量,找出最优查询计划会很耗时

动态规划可以帮助减少耗时,不同种的排序方式会包含很多重复的连接,存储下来节省时间。也可以使用贪心算法,每次只选择最低成本的连接来排序,这也叫最近邻居算法,3.8.0版本之前的sqlite就是使用的这个算法