#lru-cache #lru #lfu #pi

pi_cache

Implementation of LFU-LRU cache

16 releases

0.4.3 May 7, 2024
0.4.0 Apr 28, 2024
0.3.2 May 4, 2023
0.3.1 Apr 17, 2023
0.1.5 Apr 20, 2022

#64 in Caching


Used in 3 crates (via pi_assets)

MIT/Apache

34KB
724 lines

Cache缓存 基于LFU-LRU 预设数据访问频次最高为15, 然后按照访问频次0,1,2-3,4-7,8-15分成5段,每段为一个LRU,如果数据增加频次,则可能迁移到更高段的LRU上。 为了减少缓存击穿的情况,增加了一个CuckooFilter。 当数据放入时,首先查找频次表,获得原频次, 如果没有该键,则为首次放入,接着查找CuckooFilter,如果在,则频次提升为1,如果不在则记录到过滤器。 将数据放入到指定频次LRU中后,从0频次开始进行LRU淘汰,然后依次向更大频次的LRU进行淘汰。 当过滤器的接近满的时候,清空过滤器,重新开始。默认过滤器条目数量为1024. 频降率: 总放入次数/缓存总条目数,每当频降率达到阈值后,将所有频次减半,8降为4, 4降为2,2降为1, 将1频次LRU的数据放入0频次的LRU中。 为了记录被take拿走的数据频次,并且为了快速找到指定key所在的频次LRU,需要维护一个key的频次表。 支持垃圾标记和引用整理,将数据弹出频率队列,但保留数据本身,用collect方法真正移除。 如果在collect调用前,有其他的take和active_mut,则将数据重新放入频率队列。

Dependencies

~685KB
~11K SLoC