Lru在Rust中的实现, 源码解析

技术分享 3个月前 (06-08) 0 999+

关注

LRU（Least Recently Used）是一种常用的页面置换算法，其核心思想是选择最近最久未使用的页面予以淘汰。

LRU算法原理

基本思想：LRU算法基于一个假设，即如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很低。因此，当缓存空间不足时，算法会选择最久未使用的数据进行淘汰。
实现方式：LRU算法通常通过维护一个队列或链表来实现。当访问一个页面时，如果该页面已经在队列中，则将其移动到队列的头部（最近使用）；如果该页面不在队列中，则将其添加到队列的头部，并检查队列长度是否超过预设的阈值。如果队列长度超过阈值，则淘汰队列尾部的页面（最久未使用）。

LRU算法的优缺点

优点：
- LRU算法能够利用时间局部性原理，保留最近使用过的页面，提高缓存命中率。
- 算法简单，易于实现。
缺点：
- 需要维护一个队列或数组，占用额外的空间。
- 当页面访问模式具有循环周期时，LRU算法可能会淘汰掉正在使用的页面，导致缓存命中率下降。
- 对于随机访问的页面输入序列，LRU算法的表现可能不如其他算法。

结构设计

在Lru的结构中，我们要避免key或者val的拷贝。
因为key此时需要在双向列表中保存也需要在HashMap中保存，所以我们要以下方案：

Rc<K>引用计数

通过引用计数来控制生命周期
优点：不用处理不安全的代码
缺点：因为Val可能在遍历中被更改，所以不能存储在双向列表里，取得值的时候需要进行一次Hash

*mut K 裸指针

通过unsafe编码来实现
优点：在双向列表及HashMap中均存储一份数值，遍历或者根据key取值均只需一次操作
缺点：需要引入ptr，即用指针的方式来进行生命周期管理

节点设计

此时我们用的是裸指针的方式，让我们先来定义节点数据，数据将存储在该节点里面，key及val的生命周期随节点管理，在删除的时候需同时在列表及在HashMap中进行删除

/// Lru节点数据 struct LruEntry<K, V> {     /// 头部节点及尾部结点均未初始化值     pub key: mem::MaybeUninit<K>,     /// 头部节点及尾部结点均未初始化值     pub val: mem::MaybeUninit<V>,     pub prev: *mut LruEntry<K, V>,     pub next: *mut LruEntry<K, V>, }

类设计

接下来需要设计LruCache结构，将由一个map存储数据结构，一个双向链表存储访问优先级，cap表示缓存的容量。

pub struct LruCache<K, V, S> {     /// 存储数据结构     map: HashMap<KeyRef<K>, NonNull<LruEntry<K, V>>, S>,     /// 缓存的总容量     cap: usize,     /// 双向列表的头     head: *mut LruEntry<K, V>,     /// 双向列表的尾     tail: *mut LruEntry<K, V>, }

其中KeyRef仅仅只是表示裸指针的一层包装，方便重新实现Hash，Eq等trait

#[derive(Clone)] struct KeyRef<K> {     pub k: *const K, }

首先初始化对象，初始化map及空的双向链表：

impl<K, V, S> LruCache<K, V, S> {     /// 提供hash函数     pub fn with_hasher(cap: usize, hash_builder: S) -> LruCache<K, V, S> {         let cap = cap.max(1);         let map = HashMap::with_capacity_and_hasher(cap, hash_builder);         let head = Box::into_raw(Box::new(LruEntry::new_empty()));         let tail = Box::into_raw(Box::new(LruEntry::new_empty()));         unsafe {             (*head).next = tail;             (*tail).prev = head;         }         Self {             map,             cap,             head,             tail,         }     } }

元素插入

插入对象，分已在缓存内和不在缓存内：

pub fn capture_insert(&mut self, k: K, mut v: V) -> Option<(K, V)> {     let key = KeyRef::new(&k);     match self.map.get_mut(&key) {         Some(entry) => {             let entry_ptr = entry.as_ptr();             unsafe {                 mem::swap(&mut *(*entry_ptr).val.as_mut_ptr(), &mut v);             }             self.detach(entry_ptr);             self.attach(entry_ptr);              Some((k, v))         }         None => {             let (_, entry) = self.replace_or_create_node(k, v);             let entry_ptr = entry.as_ptr();             self.attach(entry_ptr);             unsafe {                 self.map                     .insert(KeyRef::new((*entry_ptr).key.as_ptr()), entry);             }             None         }     } }

存在该元素时，将进行替换

unsafe {     mem::swap(&mut *(*entry_ptr).val.as_mut_ptr(), &mut v); }

并且重新维护访问队列，需要detach然后重新attach使其在队列的最前面，保证最近访问最晚淘汰，从而实现Lru。
如果元素不存在，那么将判断是否缓存队列为满，如果满了将要淘汰的数据进行替换，如果未满创建新的元素，即replace_or_create_node。

元素删除

在将元素删除时，需要维护好我们的队列，防止出现队列错误及野指针等

pub fn remove<Q>(&mut self, k: &Q) -> Option<(K, V)>     where         K: Borrow<Q>,         Q: Hash + Eq + ?Sized, {     match self.map.remove(KeyWrapper::from_ref(k)) {         Some(l) => unsafe {             self.detach(l.as_ptr());             let node = *Box::from_raw(l.as_ptr());             Some((node.key.assume_init(), node.val.assume_init()))         },         None => None,     } }

这里因为移除时，仅仅需要一个可以转化成K的引用即可以，并不需要严格的K，利于编程。例如:

let mut map = LruCache::new(2); map.insert("aaaa".to_string(), "bbb"); map.remove("aaaa"); assert!(map.len() == 0);

在此处我们就不需要严格的构建String对象。由于map中的key我们用的是KeyRef，在这里，我们构建一个KeyWrapper进行转化。

// 确保新类型与其内部类型的内存布局完全相同 #[repr(transparent)] struct KeyWrapper<Q: ?Sized>(Q);  impl<K, Q> Borrow<KeyWrapper<Q>> for KeyRef<K> where     K: Borrow<Q>,     Q: ?Sized, {     fn borrow(&self) -> &KeyWrapper<Q> {         let key = unsafe { &*self.k }.borrow();         KeyWrapper::from_ref(key)     } }

如果移除成功，那么将从双向链表中同步移除，并且将指针中的值重新变成Rust中的对象，以便可以及时被drop，避免内存泄漏。

self.detach(l.as_ptr()); let node = *Box::from_raw(l.as_ptr()); Some((node.key.assume_init(), node.val.assume_init()))

其它操作

pop移除栈顶上的数据，最近使用的
pop_last移除栈尾上的数据，最久未被使用的
contains_key判断是否包含key值
raw_get直接获取key的值，不会触发双向链表的维护
get获取key的值，并维护双向链表
get_mut获取key的值，并可以根据需要改变val的值
retain 根据函数保留符合条件的元素

如何使用

在cargo.toml中添加

[dependencies] algorithm = "0.1"

示例

use algorithm::LruCache; fn main() {     let mut lru = LruCache::new(3);     lru.insert("now", "ok");     lru.insert("hello", "algorithm");     lru.insert("this", "lru");     lru.insert("auth", "tickbh");     assert!(lru.len() == 3);     assert_eq!(lru.get("hello"), Some(&"algorithm"));     assert_eq!(lru.get("this"), Some(&"lru"));     assert_eq!(lru.get("now"), None); }