给客户端写得LRU缓存
前言
由于我们的客户端的元素和资源比较多，cocos框架的各种库质量参差不齐，导致了有些地方加载速度实在很慢。并且没有一个统一的内存管理机制导致了整个内存占用不太好控制。
同时手机的硬件环境实在是千差万别，在IOS上，由于CPU和IO比较好，很多东西重算代价倒不大。 但是在Android上，CPU本来就偏弱，然后很多国产性价比机器，零件都缩水在IO设备上，还附加了各种用于节能和降低发热的降频策略，锁CPU策略。导致了很多数据重建的延迟比较高。 然而我们很容易发现，大多数Android的机器的内存都非常高，动辄2-3GB。 所以就希望说我们的应用能够最大化的利用内存作为缓存，在IOS上内存不够时重算，在Android上就拼命地用内存坐缓存，加载loading速度。
于是乎有了个写个LRU算法作为资源管理的想法。并且既然要做，就做得尽量简单、可复用，最好还能到时候服务器上也用。
LRU实现设计
由于最主要还是由客户端的问题引起的，所以最先还是考虑客户端的需求。目标如下：
首先这个管理器必须能够管理多种不同类型的资源（这是必须得，不然没存在的意义）
其次需要在不同类型的设备上用，所以一个很重要的功能就是自适应，能够弹性得自动调整在不同设备上的阈值
低性能消耗的LRU算法
为解决第一个问题，我们把LRU对象池分为两部分，LRU管理器和对象池。其中LRU管理器负责管理所管辖的多种不同类型对象的对象池，然后负责判定LRU算法的缓存和失效淘汰规则。而对象池中则实际负责保存对象缓存。
对第二个问题，考虑到在IOS上有专门的事件通知内存报警，但是在Android没有，所以为了简便起见，统一设置告警走类似IOS的报警作为LRU的主动GC操作。这样的话Android需要自己判定低内村并触发内存回收。 关键在于回收的同时需要动态调整阈值，以适应当前的内存总量。目前的策略是单触发主动回收时，各项阈值减半，并大量回收资源。而push数量过多时触发一次资源回收，但是随之会将阈值的上限+1。总体上有点像TCP的拥塞算法。
最重要的就是LRU算法设计，为了减少LRU管理器的消耗，默认情况下对LRU资源池的操作都可以认为是O(1)的。
每种对象池内部维护一个队列，记录着所有缓存的空闲对象。
LRU管理器内部维护一个队列，记录着各类对象的进入缓存池的顺序。
每种对象池对饮一个push操作，一个pull操作。
每一次push意味着一个对象进入对象池，把该对象推入队列首，同时分配一个push id，并记录到LRU管理器的push序列队列中。
LRU管理器的push序列队列只记录push id和对象池内部的缓存队列
每一次pull意味着从对象池里取出一个对象，直接从队列首取出。这个操作和上面的一起组成了后进先出（LIFO）队列，即用来判定LRU的最近使用对象。
push id使用uint64_t基本可以认为单进程内不可能会重复（实际使用中会保留如此之多的push id，所以必定唯一）
LRU管理器统计总对象数量和push序列队列长度，当总对象数量超出上限或push序列队列长度过长时触发被动GC
LRU管理器提供接口触发主动GC
每次执行GC则是从push序列队列里取最前面的节点，如果该节点的push id和里面记录的缓存队列的队列尾的push id一致，则认为该节点有效，执行该对象的gc。否则就是已失效，直接跳过。
因为存在一个对象被push，然后被pull出来，再被push进去的情况。这时候前一次的push序列记录已然已经失效，为了减少CPU消耗，pull的时候并不清理失效的push序列记录。 但是无论何时被push进对象池，push id一定是唯一的，所以只要判定push id是否有效就可以了。
另外，由于是LRU算法，所以缓存队列里的队尾的必定是最早被push进队列的，而push序列也一定是按次序排序的，所以利用它们的这个特性可以实现O(1)复杂度的对象管理。因为每次push一定只伴随着一次pull或者一次gc。
被动GC的阈值调整是指push过多，pull过少导致的缓存数量过多时调整最大上限。对应着push序列的最大上限和总对象数量上限。每次超出都+1，然后回收一个对象。
主动GC的阈值是指系统资源不足，需要主动由外部触发的缓存回收，这时候会把push序列的最大上限、总对象数量上限和总对象数量下限（即回收的时候保留的数量）调整为和当前序列数量/对象数量的平均值。然后回收的时候仅保留总对象数量下限
这一条和上一条配合使用，上一条会使缓存数量缓慢增加，这一条会使缓存数量大幅减少。这样，在高内存机器上就会很少触发主动GC，低内存机器上多触发主动GC。 目前使用这两种算法来实现各个机型上的动态缓存数量。
在实际使用过程中加入了超时机制，即即便内存很大，超过一定时间的push序列也会触发超时回收。
在实际使用过程中加入了自动调整各类上下限阈值的边界，因为在客户端场景里，有时候触发主动GC之后，有些资源会过一会再回收资源或在下一个关键点再回收。这会导致短时间内频繁触发主动GC。这会使动态调整的限制很快被调整到0值。以防这种情况再出现，加入了一个边界限制。
客户端上的应用
实际缓存池的实际使用过程中还是碰到了一些问题的。首先是cocos的很多组件本身有缓存机制，比如dragonbones和spine，还有sprite对贴图文件的缓存，对于这种对象实测缓存的影响不是特别大。
影响特别大得就是cocostudio创建的对象，我们里面实施了两层缓存。第一层是把csb文件缓存进来，这样可以减少IO操作，但是后来发现根据csb文件创建cocostudio节点反而花费了更多的时间（2/3的时间耗在这里）。 所以后来不得不对cocostudio创建的节点做缓存。然而如果是一开始就使用这个缓存的话就比较容易发现问题，我们中途开始切入这个缓存的话就发现。我们的很多UI模块代码并没有特别去重置CCNode，而是依赖析构作为资源回收和重置。 这导致了很多地方如果回收作为缓存的话，这次改动的地方，就变成下次读入以后的默认值。包括上一次添加到ListView里的节点都还在。
为了解决这个问题，我们不得不改动了cocos的源代码，对CCNode里一些公用的属性，比如children、position、anchor等属性做了快照。然后下次pull完以后恢复到快照。本来也想直接使用cocos的clone函数，无奈cocos的clone接口实现不全最后没有使用。 而cocostudio创建的一些子类的ui对象比如ListView、ImageView等等里那些不属于CCNode的属性，就要求使用前手动reset，因为如果每个子类都去加缓存的话对cocos的改动有点大，怕以后不好merge。
最后就是实际释放缓存的过程中，有些数据是在切换场景的时候释放的，这时候很多对资源的引用都会清空，不会再次使用。 比如sprite的贴图，清理的时候如果场景里还有引用到的地方，是不会清除的。 再比如dragonbones的骨骼和贴图，dragonbones自己有一层缓存和引用记录，但是它做得不好，在缓存清理的时候不通知被引用的Node，然后会导致被引用的Node在渲染时崩溃。所以清除dragonbones自身的缓存的同时还必须清理所有已有的对象。 而且特别是dragonbones和spine，即便目前没有使用在一场战斗中十有八九马上也会用到。战斗中卡一下的体验是非常不好的。所以对这些资源都会延后释放。
延后释放也会碰到一个问题，就是可能短时间内内存并没有被清理出来，然后会频繁调用主动GC。于是就有了上面第12条提到的限制。但是特别是IOS既然到了内存告警，最好先释放一部分出来。以备后用。 所以我们的缓存回收里加了一些分级，有些对象常规内存回收不做，紧急内存（IOS内存告警）回收会尽量释放一些应该不会再被引用到的资源。
服务器上的应用
暂时还未实施，但是这样的LRU算法设计也考虑了服务器上可能可以使用的场景。比如聊天服务器按活跃度来缓存玩家或者频道的聊天数据，淘汰冷数据。
另外在服务器端虽然不用太多地考虑内存回收问题，但是可以利用这个算法管理器的过期机制来提供定期保存的功能。甚至实现定期脏数据保存的功能。
定期保存: 每个对象只push一次，在gc时保存并重新push进pool
定期脏数据保存: 每个对象在写脏时先pull再push一次，在gc时保存
并且这些功能都可以利用lru管理器的各类上限来实现过载保护
代码实现
以上的代码位于： https://github.com/owent-utils/c-cpp/blob/master/include/MemPool/lru_object_pool.h 单元测试见： https://github.com/owent-utils/c-cpp/blob/master/test/case/LRUObjectPoolTest.cpp
Written with StackEdit.
Last updated