如何实现一个应用级缓存（上），实现应用级缓存
如何实现一个应用级缓存（上），实现应用级缓存
缓存真的有效？
真的。嗯，根据计算机访问数据经常会呈现出的局部性原理。局部性原理又包括空间局部性和时间局部性。空间局部性就是说，计算机访问数据，而其存储在邻近的数据也经常会被访问。时间局部性就是说，在相对的一小段时间内，计算机经常会访问相同的数据。实际中是怎么运用局部性原理的呢，比如说，计算机从硬盘中读块，计算机不会只读你要的特定块，附近的快很有可能接下来要被访问，他会把这些块也一起预读出来。接下来要读附近的快的时候，就不需要再访问硬盘了。这样，运用局部性原理就减少了访问磁盘的次数。附近的快就被缓存了起来，加快了运行速度。
缓存什么？
所有处理需要相对较长时间的内容都可以缓存，比如说，将图像显示到屏幕上，图像解码相对于渲染所需时间较长，我们就会缓存图像解码。再比如，客户端从服务器获取数据相对计算所需时间较长，我们就会缓存从服务器获取的数据。这样最终达到速度匹配，让整个处理过程中，没有那步处理时间太长。
下面就以最常见的，客户端从服务器获取数据为引子，来聊一聊缓存。
有个伟人说的好，我真tm想在客户端缓存下服务器端所有的东西，而这个伟人就是我。
但我们知道缓存下所有东西必定不可能，不仅你没有那么大的存储器，而且缓存会大大增加你编程的复杂性，所以缓存必定就是一个trade-Off的存在，权衡各种利弊，无法量化的时候甚至就靠直觉和经验了。
好，我们有了一个Basic Idea，如何开始呢？
缓存这个用空间换时间的概念存在着计算机的各个领域，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，详见:https://docs.mongodb.org/manual/faq/storage/
linux文件文件系统cache分为Page Cache、Buffer Cache，这里就不详细叙述了，此处留坑。
——————————————>此处被主题君拉了回来
继续正题，如何取出页的物理地址。他会先看是否是虚拟页，如果是虚拟页中，就直接返回，如果不是虚拟页，就会发生缺页中断。将物理页缓存在内存，生成虚拟页。再进行一次查找，这次查找就会找到虚拟页。但是，内存容量有限，不能让所有虚拟页都缓存成物理页，需要一个算法在新加入虚拟页的时候淘汰掉一些别的虚拟页。
FIFO：先进先出算法，每次淘汰掉停留时间最长的算法，这种算法并不常用，因为他很可能淘汰掉经常使用的页面。
LRU(Least Recently Used)：选择最近一段时间内未使用过的页面置换掉。这种算法非常优秀，但是操作系统实现它还需要硬件支持，实现起来相当费时，所以又涌现了很多模仿LRU的算法，更加实用，NRU、NFU、2Q、MQ、Clock等。
数据库缓存策略：
和操作系统缓存策略相似，数据库将块缓存在内存上，叫做缓冲区（buffer），由缓存区管理器管理，大多数数据库使用的算法为近似LRU算法。
数据库缓存为了在崩溃后，也要保持一致性，有时会将块强制写回，有时会限制块的写回。
让Idea不仅仅是Idea：
现在着手实现一个缓存，根据具体缓存的东西，我们可以有不同的策略，在不同的语言下，有不同的实现方式，不过，思想是一致的。
我们实际能调用的缓存只有两个层级，内存和硬盘。那么就实现一个二级缓存。
首先，我们选择一个内存缓存的数据结构，最简单的就是对哈希表的封装—字典，拥有常数级别的查询复杂度。但是如果要再加上淘汰算法，字典的复杂度就不理想了。而iOS中有系统级已实现好的NSCache，但是其效率不高，虽说提供了更多的功能，但你也可以自己实现这些功能。本文推荐大家使用LinkedHashMap，等到下文聊到淘汰算法的时候会细讲。最终，根据你要存储的内容、复杂性和性能之间的权衡，选择不同的实现方式。
我们还要确定缓存的容量，这个容量可以是缓存内容的数量或者是缓存内容的大小。取决于你实现的方式，内存中缓存的容量是不容易确定的，如果你计算出容量要花费很长的时间，那么就不要去计算，缓存本来目的就是省时间，如果要花费很长时间去做额外操作，那么就得不偿失了。
读写和两层的同步，直接参照高速缓存的思想就可以了，并且建议使用写回。什么时候写回，你可以通过两个指标来触发写回，一个是还未写回的数量和两次发生写回的时间间隔。这两个指标是或的关系，任意一个达标，都可以触发写回。每次写入缓存的时候，检查一下未写回的数量，如果超标了就写回。再用一个计时器，每隔一个时间间隔触发写回。还有当app将要退出的时候也要写回。
缓存读写：
- (void)setObject:(id)object forKeyedSubscript:(id)key {
self.memoryCache[key] = object;
self.syncDic[key] = key;
if (self.syncDic.count >= self.syncCount) {
dispatch_async(_queue, ^{
[self sync];
});
}
}
- (id)objectForKeyedSubscript:(id)key {
id object = nil;
if (self.memoryCache[key]) {
object = self.memoryCache[key];
[self.diskCache setModificationDate:[[NSDate alloc] init] forKey:key];
}else if (self.diskCache[key]) {
object = self.diskCache[key];
self.memoryCache[key] = object;
}
return object;
}
- (void)syncRecursively {
__weak typeof(self) weakSelf = self;
dispatch_after(dispatch_time(DISPATCH_TIME_NOW, (int64_t)(self.syncInterval * NSEC_PER_SEC)), _queue, ^{
__strong typeof(weakSelf) strongSelf = weakSelf;
[strongSelf sync];
[strongSelf syncRecursively];
});
}
- (void)sync {
[self.syncDic enumerateKeysAndObjectsUsingBlock:^(id _Nonnull key, id _Nonnull keyToo, BOOL * _Nonnull stop) {
id obj = self.memoryCache[key];
if (obj) {
self.diskCache[key] = obj;
}
}];
[self.syncDic removeAllObjects];
}
淘汰的算法呢，幸运的是应用层，实现LRU很简单。只要用一个上文提到的LinkedHashMap就可以了，java中有系统实现的LinkedHashMap可以参考。先用一个链表来实现最近最少使用，每次插入数据，插入到表头，读取数据也把数据插入到表头，删除数据从表尾删除，越常用的会越靠近表头，表尾就是最不常用的了。但是，链表查询复杂度是线性的，搞不好要访问的数据在表尾，就得遍历一次表。解决这个问题就是引入哈希表。利用哈希表常数级的查询复杂度。最后才叫做linkedHashMap。下面是用OC写的，翻成别的语言也不费劲。
@interface RBELinkedHashMapNode : NSObject {
@package
id _key;
id _value;
__unsafe_unretained RBELinkedHashMapNode *_prev;
__unsafe_unretained RBELinkedHashMapNode *_next;
}
@end
@implementation RBELinkedHashMapNode
@end
@interface RBELinkedHashMap : NSObject
- (id)findObjctForKey:(id)key;
- (void)insertObject:(id)obj forKey:(id)key;
- (void)eraseLastObject;
- (void)eraseObjectForKey:(id)key;
- (void)eraseAll;
- (NSUInteger)currentTotalUsage;
@end
@implementation RBELinkedHashMap {
@package
CFMutableDictionaryRef _hashMap;
NSUInteger _totalUsage;
RBELinkedHashMapNode *_head;
RBELinkedHashMapNode *_tail;
}
- (instancetype)init {
self = [super init];
if (self) {
_hashMap = CFDictionaryCreateMutable(CFAllocatorGetDefault(), 0, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);
}
return self;
}
- (void)dealloc {
CFRelease(_hashMap);
}
- (id)findObjctForKey:(id)key {
id obj = nil;
RBELinkedHashMapNode *node = CFDictionaryGetValue(_hashMap, (__bridge const void *)key);
if (node) {
[self detach:node];
[self attachToHead:node];
obj = node->_value;
}
return obj;
}
- (void)insertObject:(id)obj forKey:(id)key {
RBELinkedHashMapNode *node = CFDictionaryGetValue(_hashMap, (__bridge const void *)key);
if (node) {
node->_value = obj;
[self detach:node];
[self attachToHead:node];
return;
}
RBELinkedHashMapNode *newNode = [RBELinkedHashMapNode new];
newNode->_key = key;
newNode->_value = obj;
[self attachToHead:newNode];
CFDictionarySetValue(_hashMap, (__bridge const void *)key, (__bridge const void *)newNode);
_totalUsage ++;
}
- (void)eraseLastObject {
if (!_head) {
return;
}
RBELinkedHashMapNode *deleteNode = _tail;
if (_head == deleteNode) {
_head = nil;
_tail = nil;
}
[self detach:deleteNode];
CFDictionaryRemoveValue(_hashMap, (__bridge const void *)deleteNode->_key);
_totalUsage --;
}
- (void)eraseObjectForKey:(id)key {
if (!_head) {
return;
}
RBELinkedHashMapNode *deleteNode = CFDictionaryGetValue(_hashMap, (__bridge const void *)key);
if (deleteNode) {
if (_head == _tail) {
_head = nil;
_tail = nil;
}
if (deleteNode == _head) {
_head = _head->_next;
_head->_prev = nil;
deleteNode->_next = nil;
}
[self detach:deleteNode];
CFDictionaryRemoveValue(_hashMap, (__bridge const void *)key);
_totalUsage --;
}
}
- (void)eraseAll {
_totalUsage = 0;
if (CFDictionaryGetCount(_hashMap) > 0) {
CFDictionaryRemoveAllValues(_hashMap);
}
}
- (void)detach:(RBELinkedHashMapNode *)node {
if (_head == _tail || _head == node) {
return;
}else if (node == _tail) {
_tail = _tail->_prev;
_tail->_next = nil;
node->_prev = nil;
}else {
node->_prev->_next = node->_next;
node->_next->_prev = node->_prev;
}
}
- (void)attachToHead:(RBELinkedHashMapNode *)node {
if (_head == nil) {
_head = node;
_tail = node;
}else if (_head == node) {
return;
}else{
_head->_prev = node;
node->_next = _head;
_head = node;
}
}
- (NSUInteger)currentTotalUsage {
return _totalUsage;
}
@end
本文没有聊硬盘上的缓存怎么做，写到这里已经感觉太多了，以后有时间慢慢填吧。
注意多线程！缓存时常在多线程上进行操作，那么共享变量就一定要加锁。建议内存缓存使用自旋锁，磁盘缓存使用信号量。自旋锁，会一直询问锁是否开了，会占用大量的资源，只适合等待时间很短就能进行的操作。信号量会在问完是否开以后，睡眠一段时间，更适合长时间等待的操作。而OSSpinLock在iOS中并不是线程安全的在，可以用mutex锁替代。详见http://blog.ibireme.com/2016/01/16/spinlock_is_unsafe_in_ios/
内存缓存锁，或者使用宏预处理
- (void)mutexLock {
pthread_mutex_lock(&_mutexLock);
}
- (void)mutexUnLock {
pthread_mutex_unlock(&_mutexLock);
}
什么？这些还不够？
如果你缓存的内容是从网络获取的话，还有很多可以做的。实际上，客户端拿到数据是服务端的一个表述，一个副本，而不是原来的实体，说白了就是，客户端只有服务器端的一个缓存。而网络缓存就是使用http提供的缓存报头字段，Expires、E-Tag、Last-Modified。具体这里就不细说了，总体策略就是，定义一个过期时间，等到过期才回去服务器请求，请求还可以查看服务器的实体是否发生了变化，没有发生变化，就只需要告诉客户端没有变化，不用再返回一遍所请求数据，浪费流量。
引用：
- 缓存概念：https://zh.wikipedia.org/wiki/CPU%E7%BC%93%E5%AD%98
- 存储器山书籍：深入理解计算机系统
- 页面置换书籍：现代操作系统
- http缓存书籍：http权威指南
- 数据库缓存：http://www.devbean.net/2016/04/how-database-works-6/
- iOS端cache的性能测试以及YYCache：http://blog.ibireme.com/2015/10/26/yycache/
本系列：
- 如何实现一个应用级缓存（上）
- 如何实现一个应用级缓存（下）
用户点评