CN111752868B

CN111752868B - Lru缓存的实现方法、装置、计算机可读存储介质及设备

Info

Publication number: CN111752868B
Application number: CN201910239405.3A
Authority: CN
Inventors: 鲁宝宏; 邓丹; 刘洋
Original assignee: Beijing Wodong Tianjun Information Technology Co Ltd
Current assignee: Beijing Wodong Tianjun Information Technology Co Ltd
Priority date: 2019-03-27
Filing date: 2019-03-27
Publication date: 2024-06-18
Anticipated expiration: 2039-03-27
Also published as: CN111752868A

Abstract

本公开涉及数据处理技术领域，具体而言，涉及一种LRU缓存的实现方法、LRU缓存的实现装置，以及实现所述LRU缓存的实现方法的计算机可读存储介质及电子设备。其中，上述LRU缓存的实现方法包括：确定目标缓存数据；响应于缓存指令，基于第一TBB容器对所述目标缓存数据进行所述缓存指令对应的缓存处理；基于第二TBB容器记录对所述第一TBB容器中LRU缓存数据的访问历史。本技术方案采用并行容器实现LRU缓存，能够提供丰富的线程安全接口，进而满足对LRU缓存数据的各种操作，有利于提高LRU缓存性能。同时，采用采用无锁设计声纹LRU缓存机制，有利于提高缓存应用程序的并发度，满足多线程并发的使用场景的需要。

Description

LRU缓存的实现方法、装置、计算机可读存储介质及设备

技术领域

本公开涉及数据处理技术领域，具体而言，涉及一种LRU缓存的实现方法、LRU缓存的实现装置，以及实现所述LRU缓存的实现方法的计算机可读存储介质及电子设备。

背景技术

最近最少使用(Least Recently Used，简称：LRU)缓存是指基于LRU算法的一种缓存机制。其中，LRU算法是计算机科学中经常使用的一种数据淘汰算法。其核心思想是：如果数据最近被访问过，那么将来被访问的几率也更高，如果数据最近很少被访问，那么将来被访问的概率也就越低。当LRU缓存容量达到预设的最大值时，则需要将最近最少使用的数据对象从LRU缓存中淘汰掉，以保证缓存的容量维持在预先设定的范围内，从而维持计算机系统的运行稳定性。

现有技术提供了一种无锁单线程LRU缓存的实现方法，但是此种方法无法支持多线程同时并发的安全读写缓存，不能满足多线程(如，广告后台服务等)应用场景。为了解决上述问题，现有技术还提供一种改进的LRU缓存的实现方法。具体的，在无锁单线程实现的基础上增加了全局锁，对于任何一个线程，在进行读缓存操作或者写缓存操之前需取得全局锁，在完成读缓存操作或者写缓存操作之后再释放全局锁。从而，在多线程并发的使用场景中，此方法能够满足读写操作的安全性要求。

然而，上述LRU缓存的实现方法不能满足对并发要求较高的使用场景。

需要说明的是，在上述背景技术部分公开的信息仅用于加强对本公开的背景的理解，因此可以包括不构成对本领域普通技术人员已知的现有技术的信息。

发明内容

本公开实施例的目的在于提供一种LRU缓存的实现方法、LRU缓存器、LRU缓存的实现装置，以及实现所述LRU缓存的实现方法的计算机可读存储介质及电子设备，进而至少在一定程度上提高LRU缓存的实现方法的并发性能，有利于满足要求较高的使用场景。

本公开的其他特性和优点将通过下面的详细描述变得显然，或部分地通过本公开的实践而习得。

根据本公开实施例的第一方面，提供了一种LRU缓存的实现方法，包括：

确定目标缓存数据；

响应于缓存指令，基于第一TBB容器对所述目标缓存数据进行所述缓存指令对应的缓存处理；

基于第二TBB容器记录对所述第一TBB容器中LRU缓存数据的访问历史。

在本公开的一些实施例中，基于前述方案，

所述第一TBB容器中存储的每一LRU缓存数据与预分配队列中的一节点对象对应；

所述第二TBB容器中存储有第一访问记录队列，所述第一访问记录队列包含多个所述节点对象的指针。

在本公开的一些实施例中，基于前述方案，其中，

响应于缓存指令，基于第一TBB容器对所述目标缓存数据进行所述缓存指令对应的缓存处理，包括：

响应于将所述目标缓存数据写入所述第一TBB容器的写入指令，将所述目标缓存数据插入所述第一TBB容器，并通过原子操作在所述预分配队列中的第一节点对象中添加所述目标缓存数据；

基于第二TBB容器记录对所述第一TBB容器中LRU缓存数据的访问历史，包括：

将所述第一节点对象的指针添加至所述第二TBB容器中第一访问记录队列的尾部，以记录访问所述LRU缓存数据的历史数据。

在本公开的一些实施例中，基于前述方案，其中，

响应于使用所述目标缓存数据更新所述第一TBB容器的更新指令，将待更新LRU缓存数据对应的第二节点对象的指针指向空洞内存；

通过原子操作在所述预分配队列中的第三节点对象中添加所述目标缓存数据，并使用所述目标缓存数据更新所述待更新LRU缓存数据；

将所述第三节点对象的指针添加至所述第二TBB容器中第一访问记录队列的尾部，以记录访问所述LRU缓存数据的历史数据。

在本公开的一些实施例中，基于前述方案，其中，

响应于从所述第一TBB容器中读取所述目标缓存数据的读取指令，将所述目标缓存数据对应的第四节点对象的指针指向空洞内存；

通过原子操作在所述预分配队列中的第五节点对象中添加所述目标缓存数据；

将所述第五节点对象的指针添加至所述第二TBB容器中第一访问记录队列的尾部，以记录访问所述LRU缓存数据的历史数据。

在本公开的一些实施例中，基于前述方案，其中，

响应于从所述第一TBB容器中删除所述目标缓存数据的删除指令，将所述目标缓存数据对应的第六节点对象的指针指向空洞内存；

从所述第一TBB容器中删除所述目标缓存数据；

所述第二TBB容器中，保持所述第六节点对象的指针在所述第一访问记录队列的位置不变。

在本公开的一些实施例中，基于前述方案，所述方法还包括：

获取所述第二TBB容器的当前容量值，并判断所述第二TBB容器的当前容量值是否超过第二预设阈值；

若所述第二TBB容器的当前容量值超过第二预设阈值，则：

由所述第一访问记录队列的头部至所述第一访问记录队列的尾部的方向上，判断所述第一访问记录队列的第i个指针是否指向空洞内存；

若第i个指针指向空洞内存，则删除所述第i个指针以压缩所述第一访问记录队列，并判断第i+1个指针是否指向空洞内存；

若第i+1个指针未指向空洞内存，则将第i+1个指针转移存放至所述第二TBB容器中第二访问记录队列的尾部，并判断第i+2个指针是否指向空洞内存。

在本公开的一些实施例中，基于前述方案，

确定目标缓存数据，包括：

确定所述目标缓存数据为所述第二访问记录队列中第j指针所对应的数据；

响应于使用所述目标缓存数据更新所述第一TBB容器的更新指令，将第j指针指向空洞内存；

通过原子操作在所述预分配队列中的第七节点对象中添加所述目标缓存数据；

使用所述目标缓存数据更新所述待更新LRU缓存数据；

将所述第七节点对象的指针添加至所述第二TBB容器中第一访问记录队列的尾部，以记录访问所述LRU缓存数据的历史数据。

在本公开的一些实施例中，基于前述方案，

确定目标缓存数据，包括：

响应于从所述第一TBB容器中读取所述目标缓存数据的读取指令，将第j指针指向空洞内存；

通过原子操作在所述预分配队列中的第八节点对象中添加所述目标缓存数据；

将所述第八节点对象的指针添加至所述第二TBB容器中第一访问记录队列的尾部，以记录访问所述LRU缓存数据的历史数据。

在本公开的一些实施例中，基于前述方案，

确定目标缓存数据，包括：

响应于从所述第一TBB容器中删除所述目标缓存数据的删除指令，将第j指针指向空洞内存；

从所述第一TBB容器中删除所述目标缓存数据；

所述第二TBB容器中，保持所述第j指针在所述第二访问记录队列的位置不变。

获取所述第一TBB容器的当前容量值，并判断所述第一TBB容器的当前容量值是否超过第一预设阈值；

若所述第一TBB容器的当前容量值超过第一预设阈值，则：

由所述第二访问记录队列的头部至所述第一访问记录队列的尾部的方向上进行遍历，判断所述第二访问记录队列的第m个指针是否指向空洞内存；

若第m个指针指向空洞内存，则判断第m+1个指针是否指向空洞内存；

若第m+1个指针未指向空洞内存，则在所述第一TBB容器中确定并删除第一待删LRU缓存数据，所述第一待删LRU缓存数据与所述第m+1个指针对应的节点对象相同。

获取所述第二访问记录队列的当前长度值，并判断所述第二访问记录队列的当前长度值是否超过第三预设阈值；

若所述第二访问记录队列的当前长度值超过第三预设阈值，则：

遍历所述第二访问记录队列，删除所述第二访问记录队列中指向空洞内存的指针。

若所述第二访问记录队列中的指针均未指向空洞内存的指针，则：

由所述第二访问记录队列的头部至所述第一访问记录队列的尾部的方向上依次删除第n个指针，直至所述第二访问记录队列的当前长度值是小于或等于所述第三预设阈值，n为正整数；

并在所述第一TBB容器中确定并删除第二待删LRU缓存数据，所述第二待删LRU缓存数据与所述第n指针对应的节点对象相同。

根据本发明实施例的第二方面，提供了一种LRU缓存的实现装置，包括：

确定模块，用于确定目标缓存数据；

处理模块，用于响应于缓存指令，基于第一TBB容器对所述目标缓存数据进行所述缓存指令对应的缓存处理；

记录模块，用于基于第二TBB容器记录对所述第一TBB容器中LRU缓存数据的访问历史。

根据本公开实施例的第三方面，提供了一种计算机可读存储介质，其上存储有计算机程序，所述程序被处理器执行时实现如上述实施例中第一方面所述的LRU缓存的实现方法。

根据本公开实施例的第四方面，提供了一种电子设备，包括：一个或多个处理器；存储装置，用于存储一个或多个程序，当所述一个或多个程序被所述一个或多个处理器执行时，使得所述一个或多个处理器实现如上述实施例中第一方面所述的LRU缓存的实现方法。

本公开实施例提供的技术方案可以包括以下有益效果：

在本公开的一些实施例所提供的技术方案中，一方面，LRU缓存机制基于TBB并行容器实现。其中，第一TBB容器存储LRU缓存数据，第二TBB容器记录对所述第一TBB容器中LRU缓存数据的访问历史。两并行容器均能够提供丰富的线程安全接口，以满足对LRU缓存数据的各种操作(如，读取操作、删除操作、写入操作等)，有利于提高LRU缓存性能，以满足多线程并发的使用场景的需要。

另一方面，相较于现有的多线程LRU缓存相关技术，本技术方案提供的LRU缓存机制采用无锁设计，避免了由于锁的特性，使得同一时刻只能有一个线程能够读写缓存，其余线程的读写请求都必须排队等待取得锁的问题。从而提高了缓存应用程序的并发度，进一步满足多线程并发的使用场景的需要。

应当理解的是，以上的一般描述和后文的细节描述仅是示例性和解释性的，并不能限制本公开。

附图说明

此处的附图被并入说明书中并构成本说明书的一部分，示出了符合本公开的实施例，并与说明书一起用于解释本公开的原理。显而易见地，下面描述中的附图仅仅是本公开的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。在附图中：

图1示出了根据本公开的实施例的LRU缓存的实现方法的流程示意图；

图2示出了根据本公开实施例的LRU缓存机制的结构示意图；

图3示出了根据本公开另一实施例的LRU缓存的实现方法的流程示意图；

图4示出了根据本发明实施例的写入LRU缓存数据的流程示意图；

图5示出了根据本公开再一实施例的LRU缓存的实现方法的流程示意图；

图6示出了根据本发明实施例的更新LRU缓存数据的流程示意图；

图7示出了根据本公开又一实施例的LRU缓存的实现方法的流程示意图；

图8示出了根据本发明实施例的读取LRU缓存数据的流程示意图；

图9示出了根据本公开一实施例的LRU缓存的实现方法的流程示意图；

图10示出了根据本发明实施例的删除LRU缓存数据的流程示意图；

图11示出了根据本公开另一实施例的LRU缓存的实现方法的流程示意图；

图12示出了根据本发明实施例的监控容量值的流程示意图；

图13示出了根据本公开再一实施例的LRU缓存的实现方法的流程示意图；

图14示出了根据本公开又一实施例的LRU缓存的实现方法的流程示意图；

图15示出了根据本公开一实施例的LRU缓存的实现方法的流程示意图；

图16示出了根据本公开的实施例的LRU缓存的实现方法的流程示意图；

图17示出了根据本公开另一实施例的LRU缓存的实现方法的流程示意图；

图18示出了根据本公开的实施例的LRU缓存的实现装置的结构示意图；

图19示意性示出一种用于实现上述LRU缓存的实现方法的计算机可读存储介质；以及，

图20示意性示出一种用于实现上述LRU缓存的实现方法的电子设备示例框图。

具体实施方式

现在将参考附图更全面地描述示例实施方式。然而，示例实施方式能够以多种形式实施，且不应被理解为限于在此阐述的范例；相反，提供这些实施方式使得本公开将更加全面和完整，并将示例实施方式的构思全面地传达给本领域的技术人员。

此外，所描述的特征、结构或特性可以以任何合适的方式结合在一个或更多实施例中。在下面的描述中，提供许多具体细节从而给出对本公开的实施例的充分理解。然而，本领域技术人员将意识到，可以实践本公开的技术方案而没有特定细节中的一个或更多，或者可以采用其它的方法、组元、装置、步骤等。在其它情况下，不详细示出或描述公知方法、装置、实现或者操作以避免模糊本公开的各方面。

附图中所示的方框图仅仅是功能实体，不一定必须与物理上独立的实体相对应。即，可以采用软件形式来实现这些功能实体，或在一个或多个硬件模块或集成电路中实现这些功能实体，或在不同网络和/或处理器装置和/或微控制器装置中实现这些功能实体。

附图中所示的流程图仅是示例性说明，不是必须包括所有的内容和操作/步骤，也不是必须按所描述的顺序执行。例如，有的操作/步骤还可以分解，而有的操作/步骤可以合并或部分合并，因此实际执行的顺序有可能根据实际情况改变。

对于多线程LRU缓存的实现方法，现有的相关技术采用锁的方式保证多线程安全LRU缓存。但是，此种方法一般是在无锁单线程实现的基础上增加了全局锁。其中，全局锁的功能是将多线程的并发访问串行化。具体地，任何一个线程想要读或者写缓存，首先必须取得全局锁，完成读写操作之后再释放锁。由于锁的特性，使得同一时刻只能有一个线程能够读写缓存，其余线程的读写请求都必须排队等待取得锁。可见，这种缓存方法降低了应用程序的并发度，不能满足对性能和并发要求较高的场景。

同时，现有的相关技术针对特定场景提供了无锁多线程LRU缓存的实现方法。例如：适用于写多读少的leveldb，其内部实现的LRU缓存支持多线程安全访问。但同时，其内部针对每个哈希桶加了锁，并且对缓存数据的key(索引)有类型限制。导致在很大程度上牺牲了实用的通用性。在实际应用场景中，若进行代码整合，二次代码改造会造成使用成本高。

又例如：Intel公司开发的并行编程开发的工具线程构建模块(Thread BuildingBlocks,简称：TBB)项目，其内部也有支持多线程安全的LRU缓存实现。但是其LRU缓存提供的接口太过单一，且其应用程序无法控制缓存总容量，无法主动删除和淘汰缓存。从而导致缓存数据量连续增长，进而导致内存持续增长，进而导致实用性差。

图1示出了根据本公开的实施例的LRU缓存的实现方法的流程示意图，至少在一定程度上克服上述现有相关技术提供的LRU缓存的实现方法存在的问题。

其中，本实施例提供的LRU缓存的实现方法的执行主体可以是具有计算处理功能的设备，比如服务器等。

参考图1，该实施例提供的LRU缓存的实现方法，包括：

步骤S101，确定目标缓存数据；

步骤S102，响应于缓存指令，基于第一TBB容器对所述目标缓存数据进行所述缓存指令对应的缓存处理；以及，

步骤S103，基于第二TBB容器记录对所述第一TBB容器中LRU缓存数据的访问历史。

在图1所示实施例所提供的技术方案中，一方面，LRU缓存机制基于TBB并行容器实现。其中，第一TBB容器存储LRU缓存数据，第二TBB容器记录对所述第一TBB容器中LRU缓存数据的访问历史。两并行容器均能够提供丰富的线程安全接口，以满足对LRU缓存数据的各种操作(如，读取操作、删除操作、写入操作等)，有利于提高LRU缓存性能，以满足多线程并发的使用场景的需要。另一方面，相较于现有的多线程LRU缓存相关技术，本技术方案提供的LRU缓存机制采用无锁设计，避免了由于锁的特性，使得同一时刻只能有一个线程能够读写缓存，其余线程的读写请求都必须排队等待取得锁的问题。从而提高了缓存应用程序的并发度，进一步满足多线程并发的使用场景的需要。

图2示出了根据本公开实施例的LRU缓存机制的结构示意图。

参考图2，在示例性的实施例中，LRU缓存机制包括：上述第一TBB容器21、上述第二TBB容器22，以及预分配队列23。

在示例性的实施例中，采用tbb::concurrent_hash_map作为Cache(缓存)的存储容器，即上述第一TBB容器21。采用tbb::concurrent_bounded_queue作为记录对Cache访问历史的容器，即第二TBB容器22。上述两TBB并行容器提供了丰富的线程安全接口，可以满足实现使用场景中对Cache所需的各种操作。同时，通过第二TBB容器22记录的对Cache访问历史，可以有效地对第二TBB容22的压缩以及对LRU K-V Cache的淘汰，从而实现对两TBB容器容量值的控制，进而能够长时间稳定地为外界提供缓存数据服务。

在示例性的实施例中，再次参考图2，第一TBB容器21的LRUK-V Cache及第二TBB容器22同时保存指向预分配队列中Node对象的指针。第一TBB容器21中存储的每一LRU缓存数据与预分配队列23中的一节点对象对应，第二TBB容器22中存储有第一访问记录队列(如，记作LRU Queue)，第一访问记录队列包含多个上述节点对象的指针。通过原子变量std::atomic<bool>ready来保证多线程操作于同一个Node节点时的线程安全问题，以保证LRUK-V Cache实现层对外接口也是多线程性能安全性。

在示例性的实施例中，本技术方案提供预分配队列23采用回收循环利用内存的方式，以减少频繁分配和释放内存带来的系统开销。

图3示出了根据本公开另一实施例的LRU缓存的实现方法的流程示意图。在本实施例中，具体介绍缓存指令为写入操作指令时的LRU缓存的实现方法，具体可以通过LRU缓存机制的Put接口实现。

参考图3，该实施例提供的LRU缓存的实现方法，包括步骤S301-步骤S304。

在步骤S301中，确定目标缓存数据。

在示例性的实施例中，缓存指令为写入操作指令时，上述目标缓存数据可以为即将写入第一TBB容器的数据。

在示例性的实施例中，在Put接口实现写入操作指令时，先查找LRU K-V Cache是否已经存在上述目标缓存数据，如果不存在，则向LRU K-V Cache添加此数据(即本实施例介绍的LRU缓存的实现方法)。如果LRU K-V Cache已经存在上述目标缓存数据，则对LRU K-V Cache中对应的待更新LRU缓存数据进行更新(即图5所示实施例介绍的LRU缓存的实现方法)。

在示例性的实施例中，步骤S302和步骤S303是图1所示实施例中步骤S102的一种具体实现方式，步骤S304是图1所示实施例中步骤S103的一种具体实现方式。具体地：

在步骤S302中，响应于将所述目标缓存数据写入所述第一TBB容器的写入指令，将所述目标缓存数据插入所述第一TBB容器；

在步骤S303中，通过原子操作在所述预分配队列中的第一节点对象中添加所述目标缓存数据；以及，

在步骤S304中，将所述第一节点对象的指针添加至所述第二TBB容器中第一访问记录队列的尾部，以记录访问所述LRU缓存数据的历史数据。

在示例性的实施例中，图4示出了根据本发明实施例的写入LRU缓存数据的流程示意图。参考图4，其中，写入操作之前，第一TBB容器41中的LRU K-V Cache当前包含key1、key2和key3。步骤S301中的目标缓存数据key4是向LRU K-V Cache添加的数据。

以下通过图4对上述步骤S302-步骤S304的具体实施方式进行解释说明。

参考图4，首先，步骤S302的具体实现方式：在第一TBB容器41中，向LRU K-V Cache插入上述目标缓存数据key4(如图4中步骤①)，并通过返回的accessor(存取器)保证上述插入key4的线程安全性，即插入key4的过程中其他线程操作不可作用于key4。

接着，步骤S303的具体实现方式：从预分配队列43获取一个Node节点对象(即第一节点对象)及其地址p4，并用上述目标缓存数据key4填充p4指向的第一节点对象(如图中步骤②)。示例性的，通过原子变量std::atomic<bool>ready保证填充操作是线程的安全性，也就是说，将key4填充至充p4指向的第一节点对象的过程中，其他线程操作不可作用于key4。然后可以更新accessor的中的Node指针。

进一步地，步骤S304的具体实现方式：在第二TBB容器42中，在LRU Queue的尾部插入相同的第一节点对象的p4(如图中步骤③)。至此，Put添加缓存操作完成。LRU Queue的尾部(tail)保存的始终是最近访问的数据，LRU Queue的头部(head)保存的是最老访问的数据。

图5示出了根据本公开再一实施例的LRU缓存的实现方法的流程示意图。在本实施例中，具体介绍缓存指令为更新操作指令时的LRU缓存的实现方法，具体也可以通过LRU缓存机制的Put接口实现。

参考图5，该实施例提供的LRU缓存的实现方法，包括步骤S501-步骤S504。

在步骤S501中，确定目标缓存数据。

在示例性的实施例中，缓存指令为更新操作指令时，上述目标缓存数据可以为即将写入第一TBB容器的数据。

在示例性的实施例中，在Put接口实现更新操作指令时，先查找LRU K-V Cache是否已经存在上述目标缓存数据，如果LRU K-V Cache已经存在上述目标缓存数据，则对LRUK-V Cache中对应的待更新LRU缓存数据进行更新。

在示例性的实施例中，步骤S502和步骤S503是图1所示实施例中步骤S102的一种具体实现方式，步骤S504是图1所示实施例中步骤S103的一种具体实现方式。具体地：

在步骤S502中，响应于使用所述目标缓存数据更新所述第一TBB容器的更新指令，将待更新LRU缓存数据对应的第二节点对象的指针指向空洞内存；

在步骤S503中，通过原子操作在所述预分配队列中的第三节点对象中添加所述目标缓存数据，并使用所述目标缓存数据更新所述待更新LRU缓存数据；以及，

在步骤S504中，将所述第三节点对象的指针添加至所述第二TBB容器中第一访问记录队列的尾部，以记录访问所述LRU缓存数据的历史数据。

在示例性的实施例中，图6示出了根据本发明实施例的更新LRU缓存数据的流程示意图。参考图6，其中，更新操作之前，第一TBB容器61中的LRU K-V Cache当前包含key1、key2、key3和key4。步骤S501中的目标缓存数据key2更新LRU K-V Cache原有的key2。

以下通过图6对上述步骤S502-步骤S504的具体实施方式进行解释说明。

参考图6，首先，步骤S502的具体实现方式：在第一TBB容器61中，当查找LRU K-VCache并且已经存在key2(待更新LRU缓存数据)时，通过返回的accessor其对应的第二节点对象设置为一个空洞内存hole，(如图6中步骤①)。

接着，步骤S503的具体实现方式：从预分配队列63获取一个新的Node对象(第三节点对象)并得到其地址p2New，并用上述目标缓存数据key2填充p2New指向的第三节点对象(如图6中步骤②)。示例性的，通过原子变量std::atomic<bool>ready保证填充操作是线程的安全性，也就是说，将key2填充至充p2New指向的第三节点对象的过程中，其他线程操作不可作用于key2。然后更新accessor的Node指针(由p2改为p2New)和value(由value2改为value2New)。

进一步地，步骤S504的具体实现方式：在第二TBB容器62中，在LRU Queue的尾部插入相同的指针p2New(如图6中步骤③)。从图6可以看出，Put更新操作使得LRU Queue的尾部(tail)保存的仍然是最近访问的数据，并且使得之前的指针p2将不再出现在LRU K-VCache的任何accessor对象内。

图7示出了根据本公开又一实施例的LRU缓存的实现方法的流程示意图。在本实施例中，具体介绍缓存指令为读取操作指令时的LRU缓存的实现方法，具体也可以通过LRU缓存机制的Get接口实现。

参考图7，该实施例提供的LRU缓存的实现方法，包括步骤S701-步骤S704。

在步骤S701中，确定目标缓存数据。

在示例性的实施例中，缓存指令为读取指令时，上述目标缓存数据可以为第一TBB容器中的命中数据。

在示例性的实施例中，步骤S702和步骤S703是图1所示实施例中步骤S102的一种具体实现方式，步骤S704是图1所示实施例中步骤S103的一种具体实现方式。具体地：

在步骤S702中，响应于从所述第一TBB容器中读取所述目标缓存数据的读取指令，将所述目标缓存数据对应的第四节点对象的指针指向空洞内存；

在步骤S703中，通过原子操作在所述预分配队列中的第四节点对象中添加所述目标缓存数据；以及，

在步骤S704中，将所述第四节点对象的指针添加至所述第二TBB容器中第一访问记录队列的尾部，以记录访问所述LRU缓存数据的历史数据。

在示例性的实施例中，图8示出了根据本发明实施例的读取LRU缓存数据的流程示意图。参考图8，其中，第一TBB容器81中的LRUK-V Cache当前包含key1、key2和key3。步骤S701中的目标缓存数据key2，则即将在上述第一TBB容器81中读取key2。

以下通过图8对上述步骤S702-步骤S704的具体实施方式进行解释说明。

参考图8，首先，步骤S702的具体实现方式：在第一TBB容器81中查找到LRU K-VCache确定待读取LRU缓存数据key2(待更新)时，通过返回的accessor其对应的第四节点对象设置为一个空洞内存hole，(如图8中步骤①)。

接着，步骤S703的具体实现方式：从预分配队列83获取一个新的Node对象(第五节点对象)并得到其地址p2New，并用上述目标缓存数据key2填充p2New指向的第五节点对象(如图8中步骤②)。示例性的，通过原子变量std::atomic<bool>ready保证填充操作是线程的安全性，也就是说，将key2填充至充p2New指向的第五节点对象的过程中，其他线程操作不可作用于key2。然后更新accessor的Node指针(由p2改为p2New)。

进一步地，步骤S704的具体实现方式：在第二TBB容器82中，在LRU Queue的尾部插入相同的指针p2New(如图8中步骤③)。从图8可以看出，Get读取操作使得LRU Queue的尾部(tail)保存的仍然是最近访问的数据。

图9示出了根据本公开一实施例的LRU缓存的实现方法的流程示意图。在本实施例中，具体介绍缓存指令为删除指令时的LRU缓存的实现方法，具体也可以通过LRU缓存机制的Remove接口实现。

参考图9，该实施例提供的LRU缓存的实现方法，包括步骤S901-步骤S904。

在步骤S901中，确定目标缓存数据。

在示例性的实施例中，缓存指令为删除指令时，上述目标缓存数据可以为第一TBB容器中的待被删除的数据。

在示例性的实施例中，步骤S902和步骤S903是图1所示实施例中步骤S102的一种具体实现方式，步骤S904是图1所示实施例中步骤S103的一种具体实现方式。具体地：

在步骤S902中，响应于从所述第一TBB容器中删除所述目标缓存数据的删除指令，将所述目标缓存数据对应的第六节点对象的指针指向空洞内存；

在步骤S903中，从所述第一TBB容器中删除所述目标缓存数据；以及，

在步骤S904中，所述第二TBB容器中，保持所述第六节点对象的指针在所述第一访问记录队列的位置不变。

在示例性的实施例中，图10示出了根据本发明实施例的删除LRU缓存数据的流程示意图。参考图10，其中，第一TBB容器101中的LRU K-V Cache当前包含key1、key2和key3。步骤S901中的目标缓存数据key2，则即将在上述第一TBB容器101中删除key2。

以下通过图10对上述步骤S902-步骤S904的具体实施方式进行解释说明。

参考图10，步骤S902的具体实现方式：在第一TBB容器101中查找LRU K-V Cache待删除LRU缓存数据key2时，将key2对应的第六节点对象设置为一个空洞内存hole(如图10中步骤①)。

步骤S903的具体实现方式：从LRU K-V Cache中移走key2对应的accessor(如图10中步骤②)。

步骤S904的具体实现方式：在第二TBB容器102中，保持第六节点对象的指针p2在所述第一访问记录队列LRU Queue的位置不变(如图10中步骤③)。

图11示出了根据本公开另一实施例的LRU缓存的实现方法的流程示意图。在本实施例中，具体介绍对第二TBB容器的容量值监控的方法，具体也可以通过LRU缓存机制的RemoveOverFlowed接口实现。

需要说明的是，一般情况下，第一访问记录队列LRU Queue中单元数量较多，若通过遍历第一访问记录队列LRU Queue中所有的单元进行容量值控制的话，将耗费系统开销。在本实施例中，第一访问记录队列LRU Queue中，由所述第一访问记录队列的头部至所述第一访问记录队列的尾部的方向上，依次删除指向空洞内存hole的指针，当第二TBB容器的容量值被控制在预设范围内时，暂停对第一访问记录队列LRU Queue中指向空洞内存hole的指针的删除。同理，当检测到第二TBB容器的容量值超出在预设范围内时，再次从LRU Queue的头部开始，依次删除指向空洞内存hole的指针。即本实施例通过周期性获取第二TBB容器的当前容量值的方式将其控制在预设范围内。

参考图11，该实施例提供的LRU缓存的实现方法，包括步骤S111-步骤S116。

在步骤S111中，获取所述第二TBB容器的当前容量值。

在步骤S112中，判断所述第二TBB容器的当前容量值是否超过第二预设阈值。

在示例性的实施例中，第二TBB容器的当前容量值未超过第二预设阈值，则周期性执行步骤S111。

在示例性的实施例中，第二TBB容器的当前容量值超过第二预设阈值，则执行步骤S113-步骤S116。

在步骤S113中，判断所述第一访问记录队列的第i个指针是否指向空洞内存。

在示例性的实施例中，由所述第一访问记录队列的头部至所述第一访问记录队列的尾部的方向上，判断所述第一访问记录队列的第i个指针是否指向空洞内存。其中，若第一访问记录队列的第i个指针指向空洞内存，则可能是上述实施例中Put接口、Get接口或Remove接口对应的操作中产生的hole。若第一访问记录队列的第i个指针未指向空洞内存，则说明第i指针存在于第一TBB容器121的LRU K-V Cache的某一个accessor对象中。

在示例性的实施例中，第一访问记录队列的第i个指针指向空洞内存，则依次执行步骤S114和步骤S115。所述第一访问记录队列的第i个指针未指向空洞内存，则依次执行步骤S116和步骤S115。

在步骤S114中，删除所述第i个指针以压缩所述第一访问记录队列。并在步骤S115中给i赋值为i+1之后，再一次执行步骤S113。即判断第i+1个(即第i个指针的下一个)指针是否指向空洞内存。参考图12，也就是说，第一访问记录队列LRU Queue中，由第一访问记录队列的头部至所述第一访问记录队列的尾部的方向上依次判断指针是否指向空洞内存hole，若Node*p4-1指向空洞内存hole，则删除Node*p4-1以压缩所述第一访问记录队列，并判断下一个指针是否指向空洞内存hole。

进一步地，在步骤S116中，将第i个指针转移存放至所述第二TBB容器中第二访问记录队列的尾部。并在步骤S115中给i赋值为i+1之后，再一次执行步骤S113。即判断第i+2个(即第i+1个指针的下一个)指针是否指向空洞内存。参考图12，也就是说，若判断Node*p4-1下一个指针Node*p1未指向空洞内存hole，则将指针Node*p1转移存放至所述第二TBB容器122中第二访问记录队列LRU Queue2的尾部。

示例性的，进一步地，参考图12，按照上述方向，判断位于Node*p1之后的指针Node*p4-2、Node*p2-1、Node*p3-1均指向空洞内存hole，则按照步骤S114删除指针以压缩所述第一访问记录队列。

示例性的，参考图12，按照上述方向，判断位于Node*p3-1之后的指针Node*p2、Node*p3、Node*p4均未指向空洞内存hole，则按照步骤S116依次将指针Node*p2、Node*p3、Node*p4转移存放至所述第二TBB容器中第二访问记录队列的尾部。

需要说明的是，第一访问记录队列的第i个指针未指向空洞内存，说明该指针对应的Cache对象很久未被访问。为了最大限度提升Cache命中率，本实施例提供的技术方案是将延长此种Cache的生命周期，而不是立刻将其从第一TBB容器中移除。

同时，在第二TBB容器的当前容量值超过第二预设阈值的情况下，又需清理处于第i指针(未指向空洞内存hole的指针)之后的若干可能的空洞内存，以便压缩LRU Queue的长度。

此时，第一访问记录队列中未指向空洞内存hole的指针类似于“拦路虎”，为了解决此问题，本实施例提供的技术方案为将第二TBB容器中引入了至少两级记录队列，参考图12，如：第一访问记录队列LRU Queue和第二访问记录队列LRU Queue2，当碰到第一访问记录队列中未指向空洞内存hole的指针时，将此指针按照原来的顺序保存到第二访问记录队列LRU Queue2中。可见，本实施例提供的技术方案通过两级LRU Queue的配合，既能够解决了LRU Queue的压缩问题，又最大程度延长了LRU缓存数据的生存周期，从一定程度上提升了非热点数据被命中的几率。

在示例性的实施例中，关于第一访问记录队列的第i个指针未指向空洞内存，将指针保存至第二访问记录队列LRU Queue2中的指针中。关于第一TBB容器中的此些Cache的几种缓存处理方法，下面将分别通过图13-图15所示实施例进行解释说明。

图13示出了根据本公开再一实施例的LRU缓存的实现方法的流程示意图。在本实施例中，对第一TBB容器中命中率较低的LRU缓存数据进行更新的方法，具体也可以通过LRU缓存机制的Put接口实现。

参考图13，该实施例提供的LRU缓存的实现方法，包括步骤S131-步骤S134。

在步骤S131中，确定所述目标缓存数据为所述第二访问记录队列中第j指针所对应的数据。

在示例性的实施例中，缓存指令为更新操作指令时，上述目标缓存数据可以为即将写入第一TBB容器的数据，且上述目标缓存数据与第二访问记录队列中第j指针所对应的数据相同。

在步骤S132中，响应于使用所述目标缓存数据更新所述第一TBB容器的更新指令，将第j指针指向空洞内存。

在示例性的实施例中，步骤S132的具体实施方式与图5中步骤S502的具体实施方式相同，在此不再赘述。

在步骤S133中，通过原子操作在所述预分配队列中的第七节点对象中添加所述目标缓存数据，并使用所述目标缓存数据更新所述待更新LRU缓存数据。

在示例性的实施例中，步骤S133的具体实施方式与图5中步骤S503的具体实施方式相同，在此不再赘述。

在步骤S134中，将所述第七节点对象的指针添加至所述第二TBB容器中第一访问记录队列的尾部，以记录访问所述LRU缓存数据的历史数据。

在示例性的实施例中，步骤S134的具体实施方式与图5中步骤S504的具体实施方式相同，在此不再赘述。

图14示出了根据本公开又一实施例的LRU缓存的实现方法的流程示意图。在本实施例中，对第一TBB容器中命中率较低的LRU缓存数据进行读取的方法，具体也可以通过LRU缓存机制的Get接口实现。

参考图14，该实施例提供的LRU缓存的实现方法，包括步骤S141-步骤S144。

在步骤S141中，确定所述目标缓存数据为所述第二访问记录队列中第j指针所对应的数据。

在示例性的实施例中，缓存指令为读取指令时，上述目标缓存数据可以为第一TBB容器中的命中数据，且上述目标缓存数据与第二访问记录队列中第j指针所对应的数据相同。

在步骤S142中，响应于从所述第一TBB容器中读取所述目标缓存数据的读取指令，将第j指针指向空洞内存。

在示例性的实施例中，步骤S142的具体实施方式与图7中步骤S702的具体实施方式相同，在此不再赘述。

在步骤S143中，通过原子操作在所述预分配队列中的第八节点对象中添加所述目标缓存数据。

在示例性的实施例中，步骤S143的具体实施方式与图7中步骤S703的具体实施方式相同，在此不再赘述。

在步骤S144中，将所述第八节点对象的指针添加至所述第二TBB容器中第一访问记录队列的尾部，以记录访问所述LRU缓存数据的历史数据。

在示例性的实施例中，步骤S144的具体实施方式与图7中步骤S704的具体实施方式相同，在此不再赘述。

图15示出了根据本公开一实施例的LRU缓存的实现方法的流程示意图。在本实施例中，对第一TBB容器中命中率较低的LRU缓存数据进行删除的方法，具体也可以通过LRU缓存机制的Remove接口实现。

参考图15，该实施例提供的LRU缓存的实现方法，包括步骤S151-步骤S154。

在步骤S151中，确定所述目标缓存数据为所述第二访问记录队列中第j指针所对应的数据。

在示例性的实施例中，缓存指令为删除指令时，上述目标缓存数据可以为第一TBB容器中的待被删除的数据，且上述目标缓存数据与第二访问记录队列中第j指针所对应的数据相同。

在步骤S152中，响应于从所述第一TBB容器中删除所述目标缓存数据的删除指令，将第j指针指向空洞内存。

在示例性的实施例中，步骤S152的具体实施方式与图9中步骤S902的具体实施方式相同，在此不再赘述。

在步骤S153中，从所述第一TBB容器中删除所述目标缓存数据。

在示例性的实施例中，步骤S153的具体实施方式与图9中步骤S903的具体实施方式相同，在此不再赘述。

在步骤S154中，所述第二TBB容器中，保持所述第j指针在所述第二访问记录队列的位置不变。

在示例性的实施例中，步骤S154的具体实施方式与图9中步骤S904的具体实施方式相同，在此不再赘述。

通过图13至图15各个实施例可以看出，第二TBB容器的第二访问记录队列中也出现了指向空洞内存hole的指针。本技术方案还通过限制第二访问记录队列LRU Queue2的最大长度，以及周期性循环遍历第二访问记录队列LRU Queue2的方式，实现了对第二访问记录队列LRU Queue2的有效压缩。

需要说明的是，由于第二访问记录队列LRU Queue2的最大容量被控制在一个很小的数值，因此遍历第二访问记录队列LRU Queue2所需的系统开销代价较小。从而，本技术方案通过遍历第二访问记录队列LRU Queue2的方式获取并删除指向hole的指针，达到压缩第二访问记录队列的目的，下面通过图16所示实施例提供的技术方案对LRUQueue2进行压缩的方法进行详细地解释说明。

参考图16，该实施例提供的LRU缓存的实现方法，包括步骤S161-步骤S165。

在步骤S161中，获取所述第二访问记录队列的当前长度值。

在步骤S162中，判断所述第二访问记录队列的当前长度值是否超过第三预设阈值。

在示例性的实施例中，第二访问记录队列的当前长度值未超过第三预设阈值，则周期性执行步骤S161。

在示例性的实施例中，第二访问记录队列的当前长度值超过第三预设阈值，则执行步骤S163和步骤S164，或执行步骤S163-步骤S166。

在步骤S163中，遍历所述第二访问记录队列，删除所述第二访问记录队列中指向空洞内存的指针。

在步骤S164中，再次获取所述第二访问记录队列的当前长度值，并判断所述第二访问记录队列的当前长度值是否超过第三预设阈值。

通过步骤S163删除第二访问记录队列中所有指向空洞内存的指针的方式长度之后，存在两种情况。一种情况是：第二访问记录队列的长度值被控制在上述第三预设阈值范围内，这种情况下则达到了压缩第二访问记录队列的长度的目标。另一种情况是：第二访问记录队列的长度值仍然超过上述第三预设阈值。产生这种情况的原因可能是删除第二访问队列中指向空洞内存的指针之后，其长度值仍超过上述第三预设阈值，也可能是第二访问记录队列中本就不存在指向空洞内存的指针，也就是在步骤S163中并未进行有效删除。这种情况下，则需对第二访问记录队列为指向空洞内存的指针进行删除。

示例性的，在步骤S165中，由所述第二访问记录队列的头部至所述第一访问记录队列的尾部的方向上依次删除第n个指针，直至所述第二访问记录队列的当前长度值是小于或等于所述第三预设阈值，n为正整数；以及，在步骤S166中，在所述第一TBB容器中确定并删除第二待删LRU缓存数据，所述第二待删LRU缓存数据与所述第n个指针对应的节点对象相同。

通过步骤S165和步骤S166所示实施例提供的技术方案，在第二访问记录队列中，越靠近头部head的指针对应的Cache，其未被命中的时间越久。因此，由第二访问记录队列的头部至尾部的方向上依次删除第指针，直至所述第二访问记录队列的当前长度值是小于或等于第三预设阈值。对应的，将被删除指针对应的Cache在第一TBB容器中删除。

图17示出了根据本公开另一实施例的LRU缓存的实现方法的流程示意图。在本实施例中，具体介绍对第一TBB容器的容量值监控的方法，具体也可以通过LRU缓存机制的RemoveOverFlowed接口实现。

需要说明的是，实际应用中，一般具体根据第一TBB容器的LRUK-V Cache过期时间内的平均命中次数确定第一TBB容器的最大容量值(第一预设阈值)。第二TBB容器中第一访问记录队列LRU Queue的最大容量值通常设置为第一TBB容器的最大容量值的数十倍(例如，20倍等)。

在示例性的实施例中，经过图11所示实施例提供的技术方案，对第一访问记录队列LRU Queue的长度进行压缩之后，其将缩短至允许的最大长度之内(即未超过第二预设阈值)。而第二访问记录队列LRU Queue2将保留那些最久未被使用Cache对应的指针。当检测到第一TBB容器中的Cache容量超限时，可以从第二访问记录队列LRUQueue2的头部依次弹出节点，并从LRU K-V Cache中移除对应LRU缓存数据，直至第一TBB容器的缓存容量值不超限。

具体地，当第一TBB容器的容量值被控制在预设范围内时，暂停对第二访问记录队列LRU Queue2中指针对应的Cache的删除。同理，当检测到第一TBB容器的容量值超出在预设范围内时，再次从LRUQueue2的头部开始，依次删除LRU Queue2中指针对应的Cache。即本实施例通过周期性获取第一TBB容器的当前容量值的方式将其控制在预设范围内。

参考图17，该实施例提供的LRU缓存的实现方法，包括步骤S171-步骤S175。

在步骤S171中，获取所述第一TBB容器的当前容量值。

在步骤S172中，判断所述第一TBB容器的当前容量值是否超过第一预设阈值。

在示例性的实施例中，第一TBB容器的当前容量值未超过第一预设阈值，则周期性执行步骤S171。

在示例性的实施例中，第一TBB容器的当前容量值超过第一预设阈值，则执行步骤S173-步骤S175。

在步骤S173中，判断所述第二访问记录队列的第m个指针是否指向空洞内存。

在示例性的实施例中，第二访问记录队列的第m个指针指向空洞内存，则执行步骤S174。第二访问记录队列的第m个指针未指向空洞内存，则依次执行步骤S175和步骤S174。

在步骤S174中，给m赋值为m+1之后，再一次执行步骤S172。即判断第m+1个(即第m个指针的下一个)指针是否指向空洞内存。也就是说，第二访问记录队列LRU Queue2中，由第二访问记录队列的头部至其尾部的方向上依次判断指针是否指向空洞内存hole，若Node*p5指向空洞内存hole，则直接判断Node*p5的下一指针是否指向空洞内存。

在步骤S175中，在所述第一TBB容器中确定并删除第一待删LRU缓存数据，所述第一待删LRU缓存数据与所述第m+1个指针对应的节点对象相同。也就是说，若第二访问记录队列中第m+1个指针未指向空洞内存hole，说明在第一TBB容器中对应的Cache在被延长生命周期的过程中，仍然一直未被访问，因此，可以淘汰Cache以减少容量值。

在步骤S175中给m赋值为m+1之后，再一次执行步骤S173。即判断第m+2个(即第m+1个指针的下一个)指针是否指向空洞内存。

图17所示实施例提供的技术方案中，第二访问记录队列存储的指针，以延长长时间未被访问的Cache的生命周期，以了最大限度提升Cache命中率。但是，在第一TBB容器的容量值超出上述第一预设阈值之后，遍历第二访问记录队列中的指针。这些指针若指向空洞内存，说明对应的Cache在被延长生命周期期间被访问过；这些指针若未指向空洞内存，说明对应的Cache在被延长生命周期期间还未被访问过。因此，可以通过删除在被延长生命周期期间还未被访问过的Cache来减少第一TBB容器的容量值，直至我容量值未超出上述第一预设阈值。

以下介绍本公开的装置实施例，可以用于执行本公开上述的LRU缓存的实现方法。

图18示出了根据本公开的实施例的LRU缓存的实现装置的结构示意图。参考图18，上述LRU缓存的实现装置180，包括：确定模块181、处理模块182，以及记录模块183。

其中，确定模块181，用于确定目标缓存数据；

处理模块182，用于响应于缓存指令，基于第一TBB容器对所述目标缓存数据进行所述缓存指令对应的缓存处理；以及，

记录模块183，用于基于第二TBB容器记录对所述第一TBB容器中LRU缓存数据的访问历史。

其中，在本公开的一些实施例中，基于前述方案，

在本公开的一些实施例中，基于前述方案，其中，

处理模块182，具体用于：

记录模块183，具体用于：

在本公开的一些实施例中，基于前述方案，其中，

处理模块182，具体用于：

记录模块183，具体用于：

在本公开的一些实施例中，基于前述方案，其中，

处理模块182，具体用于：

记录模块183，具体用于：

在本公开的一些实施例中，基于前述方案，其中，

处理模块182，具体用于：

从所述第一TBB容器中删除所述目标缓存数据；

记录模块183，具体用于：

在本公开的一些实施例中，基于前述方案，上述LRU缓存的实现装置180，还包括：第一获取模块、第一判断模块；

其中，第一获取模块，用于获取所述第二TBB容器的当前容量值，第一判断模块，用于判断所述第二TBB容器的当前容量值是否超过第二预设阈值；

若所述第二TBB容器的当前容量值超过第二预设阈值，则：

第一判断模块，还用于由所述第一访问记录队列的头部至所述第一访问记录队列的尾部的方向上，判断所述第一访问记录队列的第i个指针是否指向空洞内存；

若第i个指针指向空洞内存，则记录模块183具体用于删除所述第i个指针以压缩所述第一访问记录队列，并判断第i+1个指针是否指向空洞内存；

若第i+1个指针未指向空洞内存，则记录模块183具体用于将第i+1个指针转移存放至所述第二TBB容器中第二访问记录队列的尾部，并判断第i+2个指针是否指向空洞内存。

在本公开的一些实施例中，基于前述方案，

确定模块181，具体用于：

处理模块182，具体用于：

使用所述目标缓存数据更新所述待更新LRU缓存数据；

记录模块183，具体用于：

在本公开的一些实施例中，基于前述方案，

确定模块181，具体用于：

处理模块182，具体用于：

记录模块183，具体用于：

在本公开的一些实施例中，基于前述方案，

确定模块181，具体用于：

处理模块182，具体用于：

从所述第一TBB容器中删除所述目标缓存数据；

记录模块183，具体用于：

在本公开的一些实施例中，基于前述方案，上述LRU缓存的实现装置180，还包括：第二获取模块、第二判断模块；

其中，第二获取模块，用于获取所述第一TBB容器的当前容量值，第二判断模块，用于判断所述第一TBB容器的当前容量值是否超过第一预设阈值；

若所述第一TBB容器的当前容量值超过第一预设阈值，则：

第二判断模块，还用于由所述第二访问记录队列的头部至所述第一访问记录队列的尾部的方向上进行遍历，判断所述第二访问记录队列的第m个指针是否指向空洞内存；

若第m个指针指向空洞内存，则记录模块183还用于判断第m+1个指针是否指向空洞内存；

若第m+1个指针未指向空洞内存，则处理模块182还用于在所述第一TBB容器中确定并删除第一待删LRU缓存数据，所述第一待删LRU缓存数据与所述第m+1个指针对应的节点对象相同。

在本公开的一些实施例中，基于前述方案，上述LRU缓存的实现装置180，还包括：第三获取模块、第三判断模块、遍历模块；

其中，第三获取模块，用于获取所述第二访问记录队列的当前长度值，第三判断模块，用于判断所述第二访问记录队列的当前长度值是否超过第三预设阈值；

遍历模块，用于遍历所述第二访问记录队列，删除所述第二访问记录队列中指向空洞内存的指针。

在本公开的一些实施例中，基于前述方案，

若所述第二访问记录队列中的指针均未指向空洞内存，则：

记录模块183还用于由所述第二访问记录队列的头部至所述第一访问记录队列的尾部的方向上依次删除第n个指针，直至所述第二访问记录队列的当前长度值是小于或等于所述第三预设阈值，n为正整数；

处理模块182还用于，并在所述第一TBB容器中确定并删除第二待删LRU缓存数据，所述第二待删LRU缓存数据与所述第n指针对应的节点对象相同。

由于本公开的示例实施例的LRU缓存的实现装置的各个功能模块与上述LRU缓存的实现方法的示例实施例的步骤对应，因此对于本公开装置实施例中未披露的细节，请参照本公开上述的索引的实施例。

此外，尽管在附图中以特定顺序描述了本公开中方法的各个步骤，但是，这并非要求或者暗示必须按照该特定顺序来执行这些步骤，或是必须执行全部所示的步骤才能实现期望的结果。附加的或备选的，可以省略某些步骤，将多个步骤合并为一个步骤执行，以及/或者将一个步骤分解为多个步骤执行等。

通过以上的实施方式的描述，本领域的技术人员易于理解，这里描述的示例实施方式可以通过软件实现，也可以通过软件结合必要的硬件的方式来实现。因此，根据本公开实施方式的技术方案可以以软件产品的形式体现出来，该软件产品可以存储在一个非易失性存储介质(可以是CD-ROM，U盘，移动硬盘等)中或网络上，包括若干指令以使得一台计算设备(可以是个人计算机、服务器、移动终端、或者网络设备等)执行根据本公开实施方式的LRU缓存的实现方法。

所属技术领域的技术人员能够理解，本公开的各个方面可以实现为系统、方法或程序产品。因此，本公开的各个方面可以具体实现为以下形式，即：完全的硬件实施方式、完全的软件实施方式(包括固件、微代码等)，或硬件和软件方面结合的实施方式，这里可以统称为“电路”、“模块”或“系统”。

在本公开的示例性实施例中，还提供了一种计算机可读存储介质，其上存储有能够实现本说明书上述方法的程序产品。在一些可能的实施方式中，本公开的各个方面还可以实现为一种程序产品的形式，其包括程序代码，当所述程序产品在终端设备上运行时，所述程序代码用于使所述终端设备执行本说明书上述“示例性方法”部分中描述的根据本公开各种示例性实施方式的步骤。

参考图19所示，描述了根据本公开的实施方式的用于实现上述方法的程序产品1900，其可以采用便携式紧凑盘只读存储器(CD-ROM)并包括程序代码，并可以在终端设备，例如个人电脑上运行。然而，本公开的程序产品不限于此，在本文件中，可读存储介质可以是任何包含或存储程序的有形介质，该程序可以被指令执行系统、装置或者器件使用或者与其结合使用。

所述程序产品可以采用一个或多个可读介质的任意组合。可读介质可以是可读信号介质或者可读存储介质。可读存储介质例如可以为但不限于电、磁、光、电磁、红外线、或半导体的系统、装置或器件，或者任意以上的组合。可读存储介质的更具体的例子(非穷举的列表)包括：具有一个或多个导线的电连接、便携式盘、硬盘、随机存取存储器(RAM)、只读存储器(ROM)、可擦式可编程只读存储器(EPROM或闪存)、光纤、便携式紧凑盘只读存储器(CD-ROM)、光存储器件、磁存储器件、或者上述的任意合适的组合。

计算机可读信号介质可以包括在基带中或者作为载波一部分传播的数据信号，其中承载了可读程序代码。这种传播的数据信号可以采用多种形式，包括但不限于电磁信号、光信号或上述的任意合适的组合。可读信号介质还可以是可读存储介质以外的任何可读介质，该可读介质可以发送、传播或者传输用于由指令执行系统、装置或者器件使用或者与其结合使用的程序。

可读介质上包含的程序代码可以用任何适当的介质传输，包括但不限于无线、有线、光缆、RF等等，或者上述的任意合适的组合。

可以以一种或多种程序设计语言的任意组合来编写用于执行本公开操作的程序代码，所述程序设计语言包括面向对象的程序设计语言—诸如Java、C++等，还包括常规的过程式程序设计语言—诸如“C”语言或类似的程序设计语言。程序代码可以完全地在用户计算设备上执行、部分地在用户设备上执行、作为一个独立的软件包执行、部分在用户计算设备上部分在远程计算设备上执行、或者完全在远程计算设备或服务器上执行。在涉及远程计算设备的情形中，远程计算设备可以通过任意种类的网络，包括局域网(LAN)或广域网(WAN)，连接到用户计算设备，或者，可以连接到外部计算设备(例如利用因特网服务提供商来通过因特网连接)。

在本公开的示例性实施例中，还提供了一种能够实现上述方法的电子设备。

下面参照图20来描述根据本公开的这种实施方式的电子设备2000。图20显示的电子设备2000仅仅是一个示例，不应对本公开实施例的功能和使用范围带来任何限制。

如图20所示，电子设备2000以通用计算设备的形式表现。电子设备2000的组件可以包括但不限于：上述至少一个处理单元2010、上述至少一个存储单元2020、连接不同系统组件(包括存储单元2020和处理单元2010)的总线2030。

其中，所述存储单元存储有程序代码，所述程序代码可以被所述处理单元2010执行，使得所述处理单元2010执行本说明书上述“示例性方法”部分中描述的根据本公开各种示例性实施方式的步骤。例如，所述处理单元2010可以执行如图1中所示的：步骤S101，确定目标缓存数据；步骤S102，响应于缓存指令，基于第一TBB容器对所述目标缓存数据进行所述缓存指令对应的缓存处理；以及，步骤S103，基于第二TBB容器记录对所述第一TBB容器中LRU缓存数据的访问历史。

存储单元2020可以包括易失性存储单元形式的可读介质，例如随机存取存储单元(RAM)20201和/或高速缓存存储单元20202，还可以进一步包括只读存储单元(ROM)20203。

存储单元2020还可以包括具有一组(至少一个)程序模块20205的程序/实用工具20204，这样的程序模块20205包括但不限于：操作系统、一个或者多个应用程序、其它程序模块以及程序数据，这些示例中的每一个或某种组合中可能包括网络环境的实现。

总线2030可以为表示几类总线结构中的一种或多种，包括存储单元总线或者存储单元控制器、外围总线、图形加速端口、处理单元或者使用多种总线结构中的任意总线结构的局域总线。

电子设备2000也可以与一个或多个外部设备2100(例如键盘、指向设备、蓝牙设备等)通信，还可与一个或者多个使得用户能与该电子设备2000交互的设备通信，和/或与使得该电子设备2000能与一个或多个其它计算设备进行通信的任何设备(例如路由器、调制解调器等等)通信。这种通信可以通过输入/输出(I/O)接口2050进行。并且，电子设备2000还可以通过网络适配器2060与一个或者多个网络(例如局域网(LAN)，广域网(WAN)和/或公共网络，例如因特网)通信。如图所示，网络适配器2060通过总线2030与电子设备2000的其它模块通信。应当明白，尽管图中未示出，可以结合电子设备2000使用其它硬件和/或软件模块，包括但不限于：微代码、设备驱动器、冗余处理单元、外部磁盘驱动阵列、RAID系统、磁带驱动器以及数据备份存储系统等。

通过以上的实施方式的描述，本领域的技术人员易于理解，这里描述的示例实施方式可以通过软件实现，也可以通过软件结合必要的硬件的方式来实现。因此，根据本公开实施方式的技术方案可以以软件产品的形式体现出来，该软件产品可以存储在一个非易失性存储介质(可以是CD-ROM，U盘，移动硬盘等)中或网络上，包括若干指令以使得一台计算设备(可以是个人计算机、服务器、终端装置、或者网络设备等)执行根据本公开实施方式的方法。

此外，上述附图仅是根据本公开示例性实施例的方法所包括的处理的示意性说明，而不是限制目的。易于理解，上述附图所示的处理并不表明或限制这些处理的时间顺序。另外，也易于理解，这些处理可以是例如在多个模块中同步或异步执行的。

本领域技术人员在考虑说明书及实践这里公开的内容后，将容易想到本公开的其他实施例。本申请旨在涵盖本公开的任何变型、用途或者适应性变化，这些变型、用途或者适应性变化遵循本公开的一般性原理并包括本公开未公开的本技术领域中的公知常识或惯用技术手段。说明书和实施例仅被视为示例性的，本公开的真正范围和精神由权利要求指出。

Claims

1.一种LRU缓存的实现方法，其特征在于，包括：

确定目标缓存数据；

基于第二TBB容器记录对所述第一TBB容器中LRU缓存数据的访问历史；

其中，所述第一TBB容器中存储的每一LRU缓存数据与预分配队列中的一节点对象对应，所述预分配队列采用回收循环利用内存的方式，以减少频繁分配和释放内存带来的系统开销；

2.根据权利要求1所述的LRU缓存的实现方法，其特征在于，其中，

3.根据权利要求1所述的LRU缓存的实现方法，其特征在于，其中，

4.根据权利要求1所述的LRU缓存的实现方法，其特征在于，其中，

5.根据权利要求1所述的LRU缓存的实现方法，其特征在于，其中，

从所述第一TBB容器中删除所述目标缓存数据；

6.根据权利要求1至5中任一项所述的LRU缓存的实现方法，其特征在于，所述方法还包括：

若所述第二TBB容器的当前容量值超过第二预设阈值，则：

7.根据权利要求6所述的LRU缓存的实现方法，其特征在于，

确定目标缓存数据，包括：

通过原子操作在所述预分配队列中的第七节点对象中添加所述目标缓存数据，并使用所述目标缓存数据更新待更新LRU缓存数据；

8.根据权利要求6所述的LRU缓存的实现方法，其特征在于，

确定目标缓存数据，包括：

9.根据权利要求6所述的LRU缓存的实现方法，其特征在于，

确定目标缓存数据，包括：

从所述第一TBB容器中删除所述目标缓存数据；

10.根据权利要求7至9中任一项所述的LRU缓存的实现方法，其特征在于，所述方法还包括：

若所述第一TBB容器的当前容量值超过第一预设阈值，则：

11.根据权利要求7至9中任一项所述的LRU缓存的实现方法，其特征在于，所述方法还包括：

12.根据权利要求11所述的LRU缓存的实现方法，其特征在于，所述方法还包括：

若所述第二访问记录队列中的指针均未指向空洞内存，则：

并在所述第一TBB容器中确定并删除第二待删LRU缓存数据，所述第二待删LRU缓存数据与所述第n个指针对应的节点对象相同。

13.一种LRU缓存的实现装置，其特征在于，包括：

确定模块，用于确定目标缓存数据；

记录模块，用于基于第二TBB容器记录对所述第一TBB容器中LRU缓存数据的访问历史；

14.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述程序被处理器执行时实现如权利要求1至12中任一项所述的LRU缓存的实现方法。

15.一种电子设备，其特征在于，包括：

一个或多个处理器；

存储装置，用于存储一个或多个程序，当所述一个或多个程序被所述一个或多个处理器执行时，使得所述一个或多个处理器实现如权利要求1至12中任一项所述的LRU缓存的实现方法。