Cache-Eviction Policy Comparison for a Campus E-Learning Proxy: LRU, LFU, ARC and TinyLFU under Traced Workloads

This dissertation asks a practical question: which cache-replacement policy should an engineering-college content proxy actually run when most of its traffic is e-learning content — recorded lecture videos, PDF notes, question papers and e-books? Every policy claims to be better on the author's benchmark; this project finds out what happens on our workload.

A cache-eviction policy decides which object to discard when the cache is full. The classic policies — LRU (evict the least recently used), LFU (evict the least frequently used) and Random — are taught in every operating-systems course, while ARC (Adaptive Replacement Cache) and TinyLFU (a frequency-sketch admission policy) are well-known industrial refinements. Each behaves differently depending on the request stream: recency-friendly, frequency-friendly, scan-resistant or noisy.

The project builds a trace-driven discrete-event simulator in Java: request logs collected from a college e-learning proxy (with client addresses anonymised) and synthetic Zipf-distributed workloads are replayed through identical implementations of the four policies plus a Random baseline and an Oracle (Belady's OPT) lower bound. For every policy and cache size, the simulator records hit ratio, byte hit ratio, retrieval latency and per-policy memory and CPU overhead. Because the same traces are replayed through each policy, paired statistical tests (paired t-test and Wilcoxon signed-rank on cache-size slices) can attach significance and effect sizes to the differences — the experimental-design discipline taught in RM4151.

The deliverable is a defensible recommendation — which policy, at which cache sizes, under which access patterns — with evidence to answer every examiner's "how do you know?"

A college e-learning portal generates highly skewed, bursty request traffic, and the campus proxy that serves it must keep the right objects in a cache that is always much smaller than the full content library. Choosing the eviction policy is currently guesswork: recency-based policies are known to be polluted by full-course downloads and antivirus scans, frequency-based policies fail to adapt when a semester changes the popular set, and the published claims for modern policies are all evaluated on foreign CDN or storage traces whose object sizes and popularity shapes differ greatly from lecture videos and PDFs. There is no measured, statistically tested answer to the question "which policy gives the best hit ratio and latency for our traffic at our cache sizes?" — and an untested choice either wastes scarce memory or subjects students to avoidable re-downloads. This project closes that gap with a controlled, paired, reproducible experimental study.

Abstract

Campus e-learning portals are the heaviest single load on most college networks: lecture videos and notes are requested thousands of times a day by hundreds of concurrent users. A caching proxy placed at the campus edge can serve a large fraction of these requests from local memory, cutting external bandwidth cost and average download time. Its effectiveness depends almost entirely on the eviction policy — the algorithm deciding what to keep when the cache is full. This dissertation implements four classic and modern eviction policies, replays real and synthetic campus workloads through a controlled simulator, and compares them with statistical rigour.

Introduction

A 3,000-student engineering college serving recorded lectures, notes and previous-year question papers generates strongly skewed request traffic: a handful of files (the current-semester videos, yesterday's uploaded notes) attract most requests, while a long tail of old material is touched rarely. Policies that track only recency (LRU) can be polluted by one-time scans; policies that track only frequency (LFU) adapt slowly when the semester changes and a new set of "hot" files appears. ARC adapts between recency and frequency; TinyLFU keeps a compact frequency sketch and refuses likely-useless admissions. Which one wins depends on the workload — so the workload must be measured, and the comparison controlled.

Existing Work and the Gap

• LRU, LFU and Belady's OPT are textbook algorithms; their behaviour on scan-heavy or shifted workloads is documented qualitatively but rarely quantified on Indian campus traffic.
• ARC (Megiddo and Modha, FAST 2003) and TinyLFU (Einziger et al., 2017) report large gains on CDN and storage traces, but neither paper targets e-learning traffic with a few hundred popular objects and strong weekly periodicity.
• Most comparisons report mean hit ratios only, without variance, confidence intervals or significance tests, making small differences impossible to trust.
• Gap: a reproducible, statistically tested comparison of these policies on a measured Indian campus e-learning trace.

Proposed System

A trace-driven simulator with five interchangeable policies (LRU, LFU, Random, ARC, TinyLFU) plus an OPT lower bound, fed by two workload sources: (1) an anonymised two-week HTTP log from a college e-learning proxy, and (2) parameterised synthetic generators (Zipf with varying skew, controlled popularity-shift and scan injections) that let cache sizes and patterns be swept systematically. Identical replay conditions — same trace, same cache sizes, same object-size accounting — make the comparison paired and therefore testable. The analysis reports hit ratio, byte hit ratio, latency under a simple cost model, and per-request overhead, with 95% confidence intervals and paired significance tests.

Feasibility

• Technical: the simulator is a few thousand lines of Java; all algorithms are published and well specified. Traces of 5–10 million requests replay in minutes. No special hardware is needed — an 8 GB laptop suffices.
• Economic: no licensing cost; Java, Python and the plotting libraries are free.
• Operational: log collection needs only proxy-log access, anonymisation and the network administrator's written approval; the rest runs entirely offline.

In scope

• Single-campus HTTP-object proxy traffic (e-learning portal objects: video segments, PDFs, images, packages).
• Five eviction policies plus OPT, at identical cache sizes, replayed on identical traces.
• Byte-aware caching (objects have sizes; the cache is a byte budget, not an object count).
• A deterministic latency cost model (cache hit = 5 ms; miss = backend fetch proportional to object size), clearly declared as a model, not a live measurement.
• Synthetic workloads: Zipf skew 0.6–1.2, popularity-shift and scan injections.

Out of scope (v1)

• Live deployment on the production proxy; the study is simulation-based.
• Disk-tier (L2) caching, CDN cooperation, and admission decisions on the write path.
• TLS performance and protocol-level effects; requests are modelled as (object-id, size, timestamp) triples.
• Multi-cache (distributed or coordinated) eviction policies.

Research design: quantitative, controlled, trace-driven simulation study with paired comparison across policies and cache sizes — the classical experimental-evaluation methodology of Raj Jain: fixed factors, measured response variables, replicated runs, confidence intervals and hypothesis tests.

Protocol controls: all policies replay the identical request stream (same seed order); cache budget is bytes; warm-up (first 10% of trace) is discarded before metrics are computed; each synthetic condition is replicated with 5 seeds; the analysis script regenerates every table from raw CSVs so no number is typed by hand.

The system is a pipeline of five stages, wired by a configuration file so that any policy, trace and cache size can be combined without code changes.

1. Trace layer — parses proxy logs or generates synthetic streams into a common (timestamp, object-id, size) record file.
2. Replay engine — a single-pass, byte-accounted simulator loop; on each request it consults the active policy, records hit or miss, and updates the byte ledger.
3. Policy library — LRU and LFU on hash-maps with doubly-linked lists, ARC with its four lists (T1, B1, T2, B2) and adaptive parameter p, TinyLFU with a 4-bit Count-Min sketch, doorkeeper and periodical halving, plus Random and OPT (Belady, via offline next-use indices).
4. Cost model & metrics — hit = 5 ms, miss = 5 ms + size-dependent backend fetch; computes hit ratio, byte hit ratio, mean latency and policy memory/CPU samples per 10,000 requests.
5. Analysis layer (Python) — pandas for aggregation, SciPy for paired t-tests and Wilcoxon signed-rank, matplotlib for plots; a one-command script regenerates every table from the raw CSVs.

flowchart LR
  T["Trace sources: proxy log / synthetic generator"] --> P["Parser: (timestamp, object-id, size) CSV"]
  P --> R["Replay engine: byte-accounted cache"]
  C["Policy library: LRU, LFU, Random, ARC, TinyLFU, OPT"] --> R
  R -->|"hit / miss events"| M["Metrics: hit ratio, byte hit ratio, latency, overhead"]
  M -->|"raw CSVs"| A["Analysis: pandas + SciPy paired tests"]
  A --> F["Figures and result tables"]
  K["Config matrix: policy x cache size x trace x seed"] --> R

The replay engine and policies are pure Java with no I/O during replay except a buffered event sink, which keeps bookkeeping overhead comparable across policies; the analysis layer is deliberately separate so that statistics are computed from the same raw event stream for every policy.

• Add admission policies as a second factor (TinyLFU as admission over LRU/ARC, as in W-TinyLFU) for a two-factor design.
• Couple the simulator to a live Redis or Varnish instance replaying the same trace to validate the cost model against a real deployment.
• Extend traces with HTTP Range requests to model video seeking, the dominant real-world behaviour for recorded lectures.
• Explore learned admission (predicting whether an object will be re-requested) as a third-generation policy and compare it honestly against TinyLFU.
• Multi-campus study: repeat the characterisation on two or three college traces and test whether the recommended policy is stable across institutions.