evict

Comprehensive list of effective page replacement policies implementations.

Features

• Multi-threaded: no problem wrapping the eviction policy in an Arc<_> and sharing it across threads.
• Support for custom data structures: the eviction policies are implemented as traits operating on frame IDs, so you can implement your own data structure and use it with the policies.
• Support for custom eviction policies: the eviction policies are implemented as traits, so you can implement your own eviction policy and use it with the library.
• Both conventional and state of the art eviction policies out of the box:
  • LRU (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

TBD

License

MIT