evict 0.2.2

Cache eviction policies: LRU, LRU-k, Clock etc
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

# evict

[![crates.io](https://img.shields.io/crates/d/evict.svg)](https://crates.io/crates/evict)
[![docs.rs](https://docs.rs/evict/badge.svg)](https://docs.rs/evict)

Comprehensive list of effective
[page replacement policies](https://en.wikipedia.org/wiki/Page_replacement_algorithm)
implementations.

## Features

- [x] Multi-threaded: no problem wrapping the eviction policy in an `Arc<_>` and sharing it across
  threads.
- [x] Support for custom data structures: this crate abstracts the eviction policy, and thus it can
  be used to support any data structure used to store actual pages (caches, buffer pools etc).
  The library is designed to do one thing, but do it well.
- [x] Support for custom eviction policies: implementing custom replacement policy is as easy as to
  implement `EvictionPolicy` for your type.
- [ ] Both conventional and state of the art eviction policies are provided out of the box:
  - [x] [`LRU`](crate::LruReplacer) (Least Recently Used)
  - [ ] `MRU` (Most Recently Used)
  - [ ] `FIFO` (First In First Out)
  - [ ] `Random`
  - [ ] `LRU-K` (Least Recently Used with K)
  - [ ] `LFU` (Least Frequently Used)
  - [ ] `2Q` (Two Queue)
  - [ ] `LIRS` (Low Inter-reference Recency Set)
  - [ ] `Clock`
  - [ ] `ARC` (Adaptive Replacement Cache)
  - [ ] `CAR` (Cache with Adaptive Replacement)
  - [ ] `LRFU` (Least Recently/Frequently Used)
  - [ ] `SLRU` (Segmented LRU)

## Motivation

Whenever an in-memory database or cache reaches its maximum size, it needs to evict some pages to
make room for new ones. The eviction policy determines which pages to page out (and possibly write
to disk) when a new page is requested.

The choice of eviction policy can have a significant impact on the performance of the database or
cache. Depending on the workload, some of these policies might work better than the others.

## Usage

Everything spins around the [`EvictionPolicy`](crate::EvictionPolicy) trait. It abstracts the
eviction functionality and provides a common interface for all eviction policies.

### Basic usage (LRU)

``` rust
use {
    evict::{EvictionPolicy, LruReplacer},
    std::sync::Arc,
};

// Create a new LRU policy with a maximum capacity of 20 frames.
let replacer = Arc::new(LruReplacer::new(20));
assert_eq!(replacer.capacity(), 20);

// By default frames are pinned and are not candidates for eviction.
assert_eq!(replacer.size(), 0);
assert_eq!(replacer.evict(), None);

// So, when creating a new page in, say, buffer pool,
// notify the replacer by unpinning frames responsible for pages.
// Once unpinned, frame is considered for eviction.
replacer.unpin(1);
replacer.unpin(2);
replacer.unpin(3);

// When a page is accessed, touch its frame in replacer.
// In most polices it affects the eviction order.
replacer.touch(1);

// Frame 1 has been touched, so Frame 2 will be evicted first.
assert_eq!(replacer.evict(), Some(2));
assert_eq!(replacer.size(), 2);

assert_eq!(replacer.evict(), Some(3));
assert_eq!(replacer.size(), 1);

assert_eq!(replacer.evict(), Some(1));
assert_eq!(replacer.size(), 0);

assert_eq!(replacer.evict(), None);
```

More advanced usage examples can be found in the documentation for each eviction policy.

## License

MIT