LUR闲时卸载

问题背景

游戏中存在较多对象管理系统，如常见的部队，道具，邮件等等。随着系统的增多，内存必然无序膨胀，为了避免内存膨胀，这些对象管理器都需要定期检查内存中是否闲置的对象数据是否可以卸载，因此实现一种通用且高效的闲时卸载组件就有比较高的应用价值。

那有什么方法可以卸载掉进程中闲置的对象呢？

首先想到的最笨的也是最快的方法大概是使用暴力遍历，即通过定时遍历全部存储对象，检测它的当前状态和最近使用时间，根据一定自定义策略卸载掉当前被判定为闲置的对象。但是如此，会存在许多问题：运行效率低，时间复杂度为O(n)。

解决方案

现在市面上有两种算法可以用来解决该问题：LRU和LFU。

LRU：网上的说法是，LRU基于一种假设：如果某个数据长期不被使用，在未来被用到的几率也不大；因此缓存容量达到上限时，应在写入新数据之前卸载最久未使用的数据，从而为新数据腾出空间，或者定时（10分钟）检测卸载符合闲置条件的对象。

LFU：LFU同样有这样的假设：如果一个数据在最近一段时间被访问到的频率很低，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最小频率访问的数据最先被卸载；当存在多个键具有相同的使用频次时，则淘汰最久未使用的数据。

LFU和LRU类似，LFU主要在意访问频率，LRU主要在意最近的访问时间，实现上来说LFU会比LRU复杂一些，但是这也是LRU的优点，维护比较容易，且适合游戏的使用场景。比如说，玩家可能在某个时间段上线活跃，之后下线长时间不活跃。

LRU实现方案

衡量指标（缓存淘汰机制）：

• 使用的时间
• 使用的次数（次要）

利用双向链表+字典（哈希表）的方式实现LRU，可以保证在链表中对节点进行读取，插入，访问 *** 作时间复杂度都为O(1)。定义好头节点、尾节点，最近使用的节点会出现在头节点，而最久未使用过的节点则慢慢向尾节点靠近，保证了链表尾部的一定是最久未使用的节点。

• 使用字典结构存储对象的索引对应双向列表中的节点
• 使用双向链表将每个对象信息节点连接起来，其中节点信息记录该对象的索引及最近使用时间
• 当刷新节点对象时，若节点不存在，则创建节点，添加到链表头，成为新头节点；如果节点存在，节点位置移动到链表头部，刷新节点的最近使用时间。

基于LRU算法的对象闲时卸载方案

利用LRU算法对接入的各个系统进行对象淘汰，当对象命中条件后进入卸载队列，统一管理，协调卸载。

• 每个系统独立生成自己的LRU缓存对象，管理自己系统的双向链表，可自定义卸载策略（对象超时时间、卸载回调函数，最近未使用的检测时间）
• 生成一个单例LRU缓存管理对象，管理系统中卸载队列，当每个系统中通过自己的卸载策略检测出需要卸载的对象时，在双向列表中去掉节点，将该节点信息添加到全局管理器的卸载队列中，等待执行对象的卸载函数。
• LRU缓存管理对象通过卸载队列有序进行一定时间（5秒）卸载一定数量（100）的闲置对象。