Cache 基础知识

作者: 怪小喵 | 来源:发表于2016-07-10 13:32 被阅读850次

    本文主要讲述一些 Cache 的基础知识,简单介绍一下 YYCache的实现。

    “存贮数据(使用频繁的数据)的临时地方,因为取原始数据的代价太大了,
    避免每次都要重复地向服务器请求相同的数据,既浪费用户流量,也影响APP响应速度.

    1. 缓存术语

    • 命中:当客户发起一个请求,我们的应用接受这个请求,并且如果是在第一次检查缓存的时候,需要去数据库读取产品信息。如果在缓存中,一个条目通过一个标记被找到了,这个条目就会被使用、我们就叫它缓存命中。

    • Cache Miss:但是这里需要注意两点:

      1. 如果还有缓存的空间,那么,没有命中的对象会被存储到缓存中来。
      2. 如果缓存慢了,而又没有命中缓存,那么就会按照某一种策略,把缓存中的旧对象踢出,而把新的对象加入缓存池。而这些策略统称为替代策略(缓存算法),这些策略会决定到底应该提出哪些对象。
    • 存储成本:当没有命中时,我们会从数据库取出数据,然后放入缓存。而把这个数据放入缓存所需要的时间和空间,就是存储成本。

    • 索引成本:和存储成本相仿。

    • 失效:当存在缓存中的数据需要更新时,就意味着缓存中的这个数据失效了。

    • 替代策略:当缓存没有命中时,并且缓存容量已经满了,就需要在缓存中踢出一个老的条目,加入一条新的条目,而到底应该踢出什么条目,就由替代策略决定。

    • 最优替代策略:最优的替代策略就是想把缓存中最没用的条目给踢出去,但是未来是不能够被预知的,所以这种策略是不可能实现的。但是有很多策略,都是朝着这个目前去努力。

    2. 缓存算法

    介绍一些替代策略,根据实际情况选择,没有优劣之分

    • Least Frequently Used(LFU):
      核心思想是 “如果数据过去被访问多次,那么将来被访问的频率也更高”。
      计算每个缓存对象被使用的频率 ,把最不常用的缓存对象踢走。
      LFU队列
      1. 新加入数据插入到队列尾部(因为引用计数为1);
      2. 队列中的数据被访问后,引用计数增加,队列重新排序;
      3. 当需要淘汰数据时,将已经排序的列表最后的数据块删除。
    • Least Recently User(LRU):
      算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。
      有两种方法可以实现我,array 或者是 linked list。把最新被访问的缓存对象,放到缓存池的顶部,把最近最少使用的缓存对象给踢走。所以,经常被读取的缓存对象就会一直呆在缓存池中。
    1. 新数据插入到链表头部;
    2. 每当缓存命中(即缓存数据被访问),则将数据移到链表头部;
    3. 当链表满的时候,将链表尾部的数据丢弃。

    LRU2 和 2Q 是对LRU的优化,有需要可以自己了解

    • First in First out(FIFO):

    先进先出,正好符合队列的特性,数据结构上使用队列Queue来实现。


    1. 新访问的数据插入FIFO队列尾部,数据在FIFO队列中顺序移动;
    2. 淘汰FIFO队列头部的数据;
    • Adaptive Replacement Cache(ARC):

    ARC介于 LRU 和 LFU 之间,为了提高效果,由2个 LRU 组成,第一个,也就是 L1,包含的条目是最近只被使用过一次的,而第二个 LRU,也就是 L2,包含的是最近被使用过两次的条目。因此, L1 放的是新的对象,而 L2 放的是常用的对象。

    ARC被认为是性能最好的缓存算法之一,能够自调,并且是低负载的。ARC也保存着历史对象,这样可以记住那些被移除的对象,也可以看到被移除的对象是否可以留下,取而代之的是踢走别的对象。ARC记忆力很差,但是很快,适用性也强。

    3. 缓存的实现

    手机缓存一般有两种方式,内存缓存和硬盘缓存。
    客户端每次请求数据,首先检测内存缓存是否有数据,若没有则检测硬盘,还是没有才请求服务器.请求数据成功后,把数据存入内存和硬盘中。

    现在的缓存库很多,官方自带的NSCache
    比较常见的开源缓存库SDWebImage、FastImageCache 、YYCache
    比较常见的闭源缓存库NSURLCache、Facebook的FBDiskCache


    4. YYCache 简介

    YYCache架构图
    YYMemoryCache
    实现了LRU,采用两种数据结构实现 双向链表,哈希表
    存储单元是_YYLinkedMapNode,除了key和value外,还存储了它的前后Node的地址_prev,_next,当前缓存内存开销_cost, 缓存时间_time

    整个实现基于_YYLinkedMap,它是一个双向链表, CFMutableDictionaryRef字典保存所有节点_YYLinkedMapNode。
    有新数据了插入链表头部,访问过的数据结点移到头部,内存紧张时把尾部的结点移除.就这样实现了LRU淘汰算法。

    因为内存访问速度很快,锁占用的时间少,所以用的速度最快的OSSpinLockLock。


    _YYLinkedMap

    YYDiskCache
    采用的是文件和数据库相互配合的方式 。
    有一个参数inlineThreshold,默认20KB,小于它存数据库,大于它存文件.能获得效率的提高。
    key:path,value:cache存储在NSMapTable里.根据path获得cache,进行一系列的set,get,remove操作
    更底层的是YYKVStorage,它能直接对sqlite和文件系统进行读写.
    每次内存超过限制时,select key, filename, size from manifest order by last_access_time desc limit ?1 会根据时间排序来删除最近不常用的数据。
    硬盘访问的时间比较长,如果用OSSpinLockLock锁会造成CPU消耗过大,所以用的dispatch_semaphore_wait来做.

    以上知识简单介绍,部分参考了下 面两篇文章
    YYCache作者对于各种缓存库的评测,和以上缓存库的实现思路
    还有YYCache源码分析 添加了详细的注释,可很快熟悉YYCache的结构,和一些小tips。

    阅读YYCache 你需要了解的一些基础知识,双链表,NSMapTable ,线程同步问题,GCD的使用等等

    好了就这么多,想到再补充

    相关文章

      网友评论

        本文标题:Cache 基础知识

        本文链接:https://www.haomeiwen.com/subject/erqedttx.html