Image: Joel Hruska / Extreme Tech

Multi-level Cache

A hierarchical cache implemented using a hash table and linked lists

Created November 2020
Hash Table
Linked List


Cache memory is a chip-based computer component that makes retrieving data from the computer's memory more efficient. It acts as a temporary storage area that the computer's processor can retrieve data from easily.

— Ben Lutkevich, Cache Memory

The cache hierarchy implemented in this project has three levels: L1, L2, & L3. These levels are organized using a hash table. Each level of the cache will constructed using a linked list. The data for a cache entry will be stored as an object within the linked list's node. This implementation is shown in the figure below.

A cache eviction algorithm is a way of deciding which element to evict when the cache is full. When the store gets full, elements are evicted.

Cache Eviction Policy

An essential part of the design is the eviction policy, either MRU (most recently used) or LRU (least recently used). When the cache is full, the given eviction policy will delete nodes from the linked list to make space for what is being inserted.


The project specifications include object attributes and special methods, as well as function types and descriptions.


This object is the foundation of the data stored within the cache. Its attributes include an ID, size, header information, and the data being stored. This object contains the method __hash__ which is essential for the implementation of the hash table.

This object is a simple node required to implement the linked list.

This object is a linked list with modified logic. The put() function is modified to accept an eviction policy for replacing nodes. The put() function uses two helper functions, lurEvict() & mruEvict, to apply the correlating eviction policy. All other function within this object contribute to the linked list logic.

This object represents the top level of the cache hierarchy. From here you can insert, update, and retrieve data, as well as clear the cache. This class contains a comprehensive doctest to test the cache’s overall functionallity.


Running the doctest with:

    python -m doctest -v

Running in interactive mode with:

    python -i