Skip to content

tim-chow/lru-cache

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

2 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

LRU Cache 简介

在 LRU Cache 中,每个缓存条目的元数据被保存在内存中,而真正的缓存数据可以被保存到各种存储介质中,比如内存、文件等。

在启动时,LRU Cache会创建一个“管理线程”,该线程负责将程序上次运行时产生的缓存的元数据加载到内存中,以及管理缓存数据,比如:定期地清理过期的缓存;当缓存的数据总量超过配置的限额时,根据 LRU 策略清理未被使用的缓存。

任何对 LRU Cache 对象的操作都需要先获取其内部的锁,因此使用该对象的线程之间可能产生严重的竞争,所以提供了 ProxyCache 类,每个 ProxyCache 对象内部维护若干个 LRU Cache 对象,其根据 key 进行哈希,得到要使用的 LRU Cache 对象,相当于对锁进行分段。

LRU Cache 的另一个特性是:当多个线程同时访问一个未被缓存的 key 时,只有一个线程会去存储介质中读取,其它线程会等待到缓存更新完成或超时,这样可以防止后端雪崩。


类简介

1,SkipListMap

Python 中的 list 本质上是可变长数组,它将数据存储在一段连续的存储空间上,这种顺序存储结构对于读取友好,但是在插入、删除时,需要移动元素,甚至会引起缩容、扩容、复制等繁重操作。类似地,Python 使用伪随机探测(pseudo-random probing)的散列表(hash table)作为字典的底层数据结构。SkipListMap 是基于跳表实现的映射表,跳表是一种链式存储结构,对于大量的、频繁的插入、删除等操作效率较好

2,LinkedQueue

一个双向循环链队列实现

3,AbstractCache

该抽象基类主要提供启动、停止 Cache 对象的方法、维护 Cache 对象的状态、以及实现管理线程的主要逻辑。

4,AbstractLRUCache

该抽象基类是 AbstractCache 的子类,其主要功能是:

  • 基于 SkipListMap 和 LinkedQueue 维护缓存条目的元数据(包括缓存大小、过期时间等)

  • 提供打开、清除缓存的方法

  • 定义子类需要实现的抽象方法

5,FileLRUCache

该实现类是 AbstractLRUCache 的子类,它是基于文件存储的 LRU Cache 实现。

About

Python LRU cache implementation

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

 
 
 

Languages