A set of safe Least Recently Used (LRU) map/cache types for Rust

Related tags

Caching lrumap
Overview

LruMap

lrumap forbids unsafe code lrumap is considered alpha crate version Live Build Status HTML Coverage Report for main branch Documentation for main branch

A set of safe Least-Recently-Used (LRU) cache types aimed at providing flexible map-like structures that automatically evict the least recently used key and value when its capacity is reached.

LRU Implementation

This crate utilizes an "arena"-style linked list implementation, where all nodes of the linked list are stored in a Vec. Instead of using pointers to the nodes, all references to a node in the linked list is done using an index into the Vec.

This allows all LRU list operations to be performed in constant time and remain very efficient. Each of the implementations in this crate use this internal LRU linked list implementation.

LruHashMap

The LruHashMap type is an LRU implementation that internally uses a HashMap to track keys. Its performance characteristics will be similar to the underlying hash map and hash implementation.

For most users, this type will be the best choice.

This crate has no features enabled by default, but transparently can switch to hashbrown and its default hasher by enabling feature hashbrown.

use lrumap::{LruHashMap, Removed};

let mut lru = LruHashMap::new(3);
lru.push(1, "one");
lru.push(2, "two");
lru.push(3, "three");

// The cache is now full. The next push will evict the least recently touched entry.
let removed = lru.push(4, "four");
assert_eq!(removed, Some(Removed::Evicted(1, "one")));

LruBTreeMap

The LruBTreeMap type is an LRU implementation that internally uses a BTreeMap to track keys. Its performance characteristics will be similar to the underlying container implementation.

By using a BTreeMap to track keys, this type enables efficient range-based queries:

use lrumap::LruBTreeMap;

let mut lru = LruBTreeMap::new(5);
lru.extend([(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)]);
assert_eq!(lru.most_recent_in_range(2..=4).unwrap().key(), &4);

// Change the order by retrieving key 2.
lru.get(&2);
assert_eq!(lru.most_recent_in_range(2..=4).unwrap().key(), &2);

Why another LRU crate?

For Nebari, we needed to introduce an LRU cache to the StdFileManager to close files that haven't been used recently. Each file can have multiple readers, leading to an issue of needing to scan the LRU map for all values that match a specific file. In the end, @ecton decided an LRU implementation that used a BTreeMap instead of a HashMap would be able to solve this problem by offering an most_recent_in_range(key) function. No existing crates seemed to offer this functionality.

Open-source Licenses

This project, like all projects from Khonsu Labs, are open-source. This repository is available under the MIT License or the Apache License 2.0.

To learn more about contributing, please see CONTRIBUTING.md.

You might also like...
A read-only, memory-mapped cache.

mmap-cache A low-level API for a memory-mapped cache of a read-only key-value store. Design The [Cache] index is an [fst::Map], which maps from arbitr

Turn your discord cache back to viewable images.

discache 🦀 Every time you view an Image in Discord, it gets saved in your cache folder as an unviewable file. Discache allows you to convert those fi

Non-volatile, distributed file cache backed by content-addressed storage

blobnet A low-latency file server that responds to requests for chunks of file data. This acts as a non-volatile, over-the-network content cache. Inte

Key-value cache RESP server with support for key expirations ⌛

BADER-DB (بادِر) Key-value cache RESP server with support for key expirations ⌛ Supported Features • Getting Started • Basic Usage • Cache Eviction •

Rust binary memcached implementation

bmemcached-rs Rust binary memcached implementation (ON GOING) Usage extern crate bmemcached; use std::sync::Arc; use std::thread; use bmemcached::Me

memcache client for rust
memcache client for rust

rust-memcache rust-memcache is a memcached client written in pure rust. Install The crate is called memcache and you can depend on it via cargo: [depe

This is a Rust implementation for popular caches (support no_std).

Caches This is a Rust implementation for popular caches (support no_std). See Introduction, Installation and Usages for more details. English | 简体中文 I

This is a Rust implementation for HashiCorp's golang-lru. This crate contains three LRU based cache, LRUCache, TwoQueueCache and AdaptiveCache.

This is a Rust implementation for HashiCorp's golang-lru. This crate contains three LRU based cache, LRUCache, TwoQueueCache and AdaptiveCache.

enum-map enum-map xfix/enum-map [enum-map] — An optimized map implementation for enums using an array to store values.

enum-map A library providing enum map providing type safe enum array. It is implemented using regular Rust arrays, so using them is as fast as using r

A generational arena based LRU Cache implementation in 100% safe rust.

generational-lru Crate providing a 100% safe, generational arena based LRU cache implementation. use generational_lru::lrucache::{LRUCache, CacheError

A fast and flexible LRU map.

A fast and flexible LRU map This repository contains a fast and flexible LRU map. Blazingly fast. Up to twice as fast as the lru crate, and with less

Easy c̵̰͠r̵̛̠ö̴̪s̶̩̒s̵̭̀-t̶̲͝h̶̯̚r̵̺͐e̷̖̽ḁ̴̍d̶̖̔ ȓ̵͙ė̶͎ḟ̴͙e̸̖͛r̶̖͗ë̶̱́ṉ̵̒ĉ̷̥e̷͚̍ s̷̹͌h̷̲̉a̵̭͋r̷̫̊ḭ̵̊n̷̬͂g̵̦̃ f̶̻̊ơ̵̜ṟ̸̈́ R̵̞̋ù̵̺s̷̖̅ţ̸͗!̸̼͋

Rust S̵̓i̸̓n̵̉ I̴n̴f̶e̸r̵n̷a̴l mutability! Howdy, friendly Rust developer! Ever had a value get m̵̯̅ð̶͊v̴̮̾ê̴̼͘d away right under your nose just when

Prefix tree (ordered map and set) data structure using 100% safe Rust

PFX: A 100% safe, blob-oriented prefix tree This crate provides a prefix tree map and set data structure, implemented purely in safe Rust. The API is

Serialize/DeSerialize for Rust built-in types and user defined types (complex struct types)

Serialize/DeSerialize for Rust built-in types and user defined types (complex struct types)

Steggy CLI Tool - hides data within the least significant bit of an image
Steggy CLI Tool - hides data within the least significant bit of an image

Written in Rust, features a simple cli and a client-side webapp. This tool hides data within the least significant bit of an image. Obfuscation techniques are utilized to make the

🗑Async-dropper is probably the least-worst ad-hoc AysncDrop implementation you've seen so far.

🗑 async-dropper async-dropper is probably the least-worst ad-hoc AsyncDrop implementation you've seen, and it works in two ways: async_dropper::simpl

Rust crates with map and set with interval keys (ranges x..y).

This crates implements map and set with interval keys (ranges x..y). IntervalMap is implemented using red-black binary tree, where each node contains

Thread Safe Cache with async loader functions based on tokio-rs

cache-loader-async crates.io The goal of this crate is to provide a thread-safe and easy way to access any data structure which might is stored in a d

Comments
  • Add more mut accessors

    Add more mut accessors

    In 77b05d1e9d88d94a95429c5cb635211cebc070a9 I added LruHashMap::get_mut while working on another project.

    There is an entire class of mutable access that we should provide, in addition to adding get_mut to the LruBTreeMap type.

    enhancement 
    opened by ecton 0
Owner
Khonsu Labs
Khonsu Labs
A generational arena based LRU Cache implementation in 100% safe rust.

generational-lru Crate providing a 100% safe, generational arena based LRU cache implementation. use generational_lru::lrucache::{LRUCache, CacheError

Arindam Das 37 Dec 21, 2022
Stretto is a Rust implementation for ristretto. A high performance memory-bound Rust cache.

Stretto is a Rust implementation for ristretto. A high performance memory-bound Rust cache.

Al Liu 310 Dec 29, 2022
Rust cache structures and easy function memoization

cached Caching structures and simplified function memoization cached provides implementations of several caching structures as well as a handy macro f

James Kominick 996 Jan 7, 2023
Rust type wrapper to cache hash of potentially large structures.

CachedHash For a type T, CachedHash<T> wraps T and implements Hash in a way that caches T's hash value. This is useful when T is expensive to hash (fo

pali 3 Dec 8, 2022
A native stateless cache implementation.

fBNC fBNC, Blockchain Native Cache. A native stateless storage library for block chain. Its value is to improve the stability and security of online s

Findora Foundation 1 Jan 12, 2022
Key-Value based in-memory cache library which supports Custom Expiration Policies

Endorphin Key-Value based in-memory cache library which supports Custom Expiration Policies with standard HashMap, HashSet interface. use endorphin::H

Jun Ryung Ju 15 Oct 1, 2022
A general-purpose distributed memory cache system compatible with Memcached

memcrsd memcached server implementation in Rust memcrsd is a key value store implementation in Rust. It is compatible with binary protocol of memcache

null 274 Dec 14, 2022
A lightweight key-value cache system developed for experimental purposes

A lightweight key-value cache system developed for experimental purposes. It can also include distributed systems setup if I can.

Burak Selim Senyurt 8 Jul 23, 2022
ConstDB - an in-memory cache store which aims at master-master replications

A redis-like cache store that implements CRDTs and active-active replications.

null 27 Aug 15, 2022
Read-optimized cache of Cardano on-chain entities

Read-optimized cache of Cardano on-chain entities Intro Scrolls is a tool for building and maintaining read-optimized collections of Cardano's on-chai

TxPipe 58 Dec 2, 2022