lru-mem

为Rust实现的内存限制LRU（最近最少使用）缓存。它支持平均情况下的O(1)插入、获取和删除。还包括迭代器、容量管理和可变访问等附加实用方法。

请注意，每个条目所需的内存仅是一个估计值，并且忽略了一些辅助结构。因此，实际的数据结构可能比分配的内存多，但在大多数情况下，这不应该是一个过大的数量。

动机示例

想象我们正在构建一个向客户端发送大量响应的Web服务器。为了减少负载，它们被分成几部分，客户端被分配一个令牌来单独访问不同的部分。然而，每次请求重新计算部分会导致服务器负载过大，因此需要缓存。在这种情况下，LRU缓存非常有用，因为客户端很可能请求新部分的时间局部化。

现在考虑大多数响应都很小，但一些可能很大的情况。这将导致缓存的大小保守，允许缓存的响应比通常可能的情况要少，或者缓存的大小很大，如果需要缓存太多大响应，可能会溢出内存。为了防止这种情况，缓存的设计具有内存的上限而不是元素数量。

下面的代码展示了基本结构可能的样子。

use lru_mem::LruCache;

struct WebServer {
    cache: LruCache<u128, Vec<String>>
}

fn random_token() -> u128 {
    // A cryptographically secure random token.
    42
}

fn generate_sections(input: String) -> Vec<String> {
    // A complicated set of sections that is highly variable in size.
    vec![input.clone(), input]
}

impl WebServer {
    fn new(max_size: usize) -> WebServer {
        // Create a new web server with a cache that holds at most max_size
        // bytes of elements.
        WebServer {
            cache: LruCache::new(max_size)
        }
    }

    fn on_query(&mut self, input: String) -> u128 {
        // Generate sections, store them in the cache, and return token.
        let token = random_token();
        let sections = generate_sections(input);
        self.cache.insert(token, sections)
            .expect("sections do not fit in the cache");

        token
    }

    fn on_section_request(&mut self, token: u128, index: usize)
            -> Option<&String> {
        // Lookup the token and get the section with given index.
        self.cache.get(&token).and_then(|s| s.get(index))
    }
}

有关更多详细信息，请参阅文档。

链接

• 包
• 文档
• 仓库