created_at2023-01-07 08:50:01.530601
updated_at2024-03-17 13:44:50.00668
descriptionDiskLRU is an experimental LRU store.
Christian Mauduit




# DiskLRU [DiskLRU](https://gitlab.com/liberecofr/disklru) is an experimental LRU store implemented in [Rust](https://www.rust-lang.org/). It works as a simple key-value store and is powered by [sled](https://crates.io/crates/sled/) which is _a lightweight pure-rust high-performance transactional embedded database_. It expires entries automatically passed a given number, following the LRU (least recently used) strategy, which is a quite [common cache replacement policy]( https://en.wikipedia.org/wiki/Cache_replacement_policies). It comes with a cost but is sometimes more adapted than just expiring the old keys in FIFO mode (first-in, first-out) as you may have a key-value pair which has been introduced a very long time ago in the store, but is still relevant. With DiskLRU, if your code is reading the value often, it will ensure the key stays alive and does not disappear. ![DiskLRU icon](https://gitlab.com/liberecofr/disklru/raw/main/disklru.png) * [HashLRU](https://gitlab.com/liberecofr/hashlru) is very similar in its design, and acts as an in-memory cache, as opposed to DiskLRU being a persistent store. * [MenhirKV](https://gitlab.com/liberecofr/menhirkv) solves the same problem that DiskLRU addresses, which is "store stuff, keep most used value at hand, drop the rest". It does it in a less pedantic and precise way, but much more efficiently. # Status For now this is a toy project, clearly *NOT* suitable for production use. It has at least 2 significant flaws: * it is very (very) slow compared to other alternatives, the fact it is so slow motivated me to start [MenhirKV](https://gitlab.com/liberecofr/menhirkv) which has a much more pragmatic approach to expiration. * it has serious stability issues, among other things, turning on disk writes (eg: not using a temporary store) on my arm64-based laptop causes benchmarks to just hang, with symptoms of a deadlock. [![Build Status](https://gitlab.com/liberecofr/disklru/badges/main/pipeline.svg)](https://gitlab.com/liberecofr/disklru/pipelines) [![Crates.io](https://img.shields.io/crates/v/disklru.svg)](https://crates.io/crates/disklru) [![Gitlab](https://img.shields.io/gitlab/last-commit/liberecofr/disklru)](https://gitlab.com/liberecofr/disklru/tree/main) [![License](https://img.shields.io/gitlab/license/liberecofr/disklru)](https://gitlab.com/liberecofr/disklru/blob/main/LICENSE) # Usage ```rust use disklru::Store; let mut store = Store::open_temporary(4).unwrap(); store.insert(&1, &10).unwrap(); store.insert(&2, &20).unwrap(); store.insert(&3, &30).unwrap(); store.insert(&4, &40).unwrap(); store.insert(&5, &50).unwrap(); // key1 has been dropped, size is limited to 4 assert_eq!(Some(2), store.lru().unwrap()); assert_eq!(Some(20), store.get(&2).unwrap()); // getting key2 has made key3 the least recently used item assert_eq!(Some(3), store.lru().unwrap()); assert_eq!(Some(40), store.get(&4).unwrap()); // getting key4 makes it the most recently used item assert_eq!("[3: 30, 5: 50, 2: 20, 4: 40]", format!("{}", store)); store.flush().unwrap(); // commit ``` # Benchmarks Taken from a random CI job: ``` running 12 tests test tests::bench_read_usize_disklru_compress ... bench: 169,738 ns/iter (+/- 21,901) test tests::bench_read_usize_disklru_persistent ... bench: 111,211 ns/iter (+/- 12,312) test tests::bench_read_usize_disklru_temporary ... bench: 105,257 ns/iter (+/- 25,468) test tests::bench_read_usize_hashlru ... bench: 157 ns/iter (+/- 16) test tests::bench_read_usize_hashmap ... bench: 40 ns/iter (+/- 10) test tests::bench_read_usize_lru ... bench: 34 ns/iter (+/- 15) test tests::bench_write_usize_disklru_compress ... bench: 151,871 ns/iter (+/- 15,723) test tests::bench_write_usize_disklru_persistent ... bench: 100,999 ns/iter (+/- 5,399) test tests::bench_write_usize_disklru_temporary ... bench: 95,390 ns/iter (+/- 15,908) test tests::bench_write_usize_hashlru ... bench: 239 ns/iter (+/- 32) test tests::bench_write_usize_hashmap ... bench: 117 ns/iter (+/- 26) test tests::bench_write_usize_lru ... bench: 84 ns/iter (+/- 25) test result: ok. 0 passed; 0 failed; 0 ignored; 12 measured; 0 filtered out; finished in 98.17s ``` This is not the result of extensive, thorough benchmarking, just a random snapshot at some point in development history. TL;DR -> performance is not great. Granted, the comparison is made with non-persistent LRU caches, so it is expected to have "some performance loss", but the gap here is huge. Another project I started, using a Bloom filter to expire old entries, is about [10X faster](https://gitlab.com/liberecofr/menhirkv). To run the benchmarks: ```shell cd bench rustup default nightly cargo bench ``` # Links * [crate](https://crates.io/crates/disklru) on crates.io * [doc](https://docs.rs/disklru/) on docs.rs * [source](https://gitlab.com/liberecofr/disklru/tree/main) on gitlab.com * [sled](https://github.com/spacejam/sled), the database powering this LRU store * [HashLRU](https://gitlab.com/liberecofr/disklru), a similar in-memory cache * [MenhirKV](https://gitlab.com/liberecofr/menhirkv), recommended alternative # License DiskLRU is licensed under the [MIT](https://gitlab.com/liberecofr/disklru/blob/main/LICENSE) license.
Commit count: 0

cargo fmt