Revisiting FIFO, with more cache algorithms

The IBM Object Store traces are a public record of requests to IBM's cloud object storage service, published through SNIA's IOTTA repository in 2019. They describe real storage traffic: which objects were read, written, or deleted, and, for range reads, which bytes were requested. They contain access records rather than the objects' contents. The collection covers a week of activity for each of 99 tenants. Collection description.

That makes them useful for a cache experiment. We can replay the reads against a simulated cache, change the rule for deciding what stays in memory, and count how often the next read finds its data already there. Every policy gets the same requests. The working input for this experiment contains 418,002,964 nonempty GET requests, drawn from 110 source files.

If you are putting a cache in front of an object store, this is a practical question. A hit can save a trip to the backing store. A miss still has to fetch the data. You want enough hits to make the cache useful, but memory costs money, and keeping track of what to retain consumes CPU time and memory of its own.

A more elaborate replacement policy is worthwhile if it saves enough misses or enough RAM to pay for that work. The useful comparison is therefore how much cache each policy needs to meet a target, and what work it adds to each access. Those are the questions behind this experiment.

Ohad Eytan, Danny Harnik, Effi Ofer, Roy Friedman, and Ronen Kat examined the same tradeoff in It's Time to Revisit LRU vs. FIFO, published at HotStorage 2020. They simulated LRU and FIFO on IBM tenant traces at different capacities, then modeled access cost including cache management. LRU's hit-rate advantage was often too small to repay its additional bookkeeping, especially when a large cache's metadata spilled out of RAM. FIFO was preferable under many of their modeled conditions. Their recommendation was to take FIFO seriously as the baseline for these caches. Paper.

I repeated the FIFO/LRU comparison on the IBM traces and broadened it to include ARC, LFU, S3-FIFO, SIEVE, and W-TinyLFU. The newer policies did not produce a consistent improvement over the simple baselines in these runs. Some required much more memory to reach the same hit rate.

The simulator is native C++. It starts each run with an empty cache and expands every GET range into accesses to 4 KiB pages. All page-policy runs report 462,902,891,970 page accesses. The hit rate counts those accesses: a long read contributes more observations than a short one. It is neither a whole-GET success rate nor an exact byte-hit ratio for requests that cover partial pages.

This extends the paper's question with different simulation choices. The original paper used 4 MB blocks for large objects, with smaller requests occupying their actual length. Our experiment uses 4 KiB (4,096-byte) pages, the default in ./cachesim. The original evaluation treated tenant traces separately; here, one cache spans the binary's saved input order. The converter normally concatenates files in numeric trace and part order; the binary omits timestamps and a file manifest, so it cannot establish a global chronological merge. Repeated object IDs share cache state across files. Only GETs participate; writes and deletes do not invalidate entries. Those choices define the workload being compared. Original methodology, section 3.

The algorithms are implemented as local C++ ports. Capacity means space for cached data. The simulator stores identities and replacement metadata without allocating the corresponding payload, so its process memory use is a different quantity. A deployed RAM cache needs the table's capacity plus metadata.

Here is what each policy does, and what limits the comparison.

FIFO — first in, first out. New pages join a queue. When space runs out, the oldest resident leaves, even if it was just read. A hit does not change the eviction order. That makes FIFO simple, but it can discard frequently used pages and does not guarantee that a larger cache always has a higher hit rate.

LRU — least recently used. Each hit moves its page to the most-recently-used end of a list; eviction removes the least recently accessed page. It follows changes in what the application is reading, at the cost of maintaining that order. A long scan can displace useful pages. This implementation maintains the order exactly, rather than approximating it with occasional updates.

LFU — least frequently used. Pages accumulate access counts while resident, and eviction selects from the lowest-frequency bucket, breaking ties by recency. A page's count is lost when it is evicted, but the counts of resident pages never decay. That can favor pages that were popular earlier over newly arriving pages, even after the workload changes. These results describe this unaged LFU implementation; frequency-based policies with aging or admission filters can behave differently.

ARC — Adaptive Replacement Cache. ARC balances recently seen pages against repeatedly used pages. It also retains the identities of evicted pages in two “ghost” lists, using later accesses to adjust that balance. Ghosts consume metadata but hold no cached data. This adds adaptive behavior and list management; it does not guarantee an improvement on a particular trace. Our ARC sweep ends at 3 TiB. ARC paper.

S3-FIFO. This policy uses a small FIFO queue to filter new arrivals, a main FIFO queue for retained pages, and a ghost queue recording recent evictions from the small queue. Hits increment a small capped counter; they do not reorder the queues. The counter helps decide which pages survive eviction processing, while a ghost hit sends a returning page to the main queue. Our configuration allocates 10% of payload capacity to the small queue and 90% to the main queue. The ghost history scales with the main queue's capacity. It adds metadata and eviction work to ordinary FIFO while keeping hits inexpensive. S3-FIFO design.

W-TinyLFU — Window TinyLFU. New pages enter a small LRU window. When one leaves that window, an approximate frequency estimator decides whether it deserves space in the main cache over an existing victim. The main cache separates probationary and protected pages. Our window is fixed at 1% of capacity, with 80% of the main region protected. The estimator uses a local four-row, 8-bit-counter sketch and a Bloom doorkeeper; growing it clears its history. These are consequential choices. This is a fixed-parameter local implementation, not a benchmark of Caffeine's adaptive implementation. Caffeine's policy description.

SIEVE. Pages remain in insertion order, and a hit sets a visited flag. An eviction hand walks through the queue, clearing flags and retaining visited pages until it finds an unvisited victim. A retained page stays in place. This makes the hit path cheap and moves the search work to eviction. It has no ghost history. Our saved curve has a substantial dip as capacity increases; the results alone do not establish its cause. That limits how confidently we can generalize from this implementation's poor showing. SIEVE design.

The results put FIFO, LRU, ARC, and S3-FIFO in a fairly close group, with W-TinyLFU and SIEVE much farther to the right. LFU stays below 2% throughout the sweep. At a measured capacity of 64 GiB, FIFO reaches 80.96% hits, LRU 81.92%, ARC 81.38%, and S3-FIFO 81.09%. W-TinyLFU reaches 49.01%, SIEVE 26.00%, and LFU 0.0273%.

The table is the more useful view for sizing a cache. It shows GiB of payload RAM required for 75%, 82.5%, and 90% page hits, estimated between adjacent measured capacities. One GiB is 2³⁰ bytes. Lower is better.

For two measured capacities C0 and C1 with hit rates H0 and H1 surrounding a target T, the calculation is C0 + (T − H0) / (H1 − H0) × (C1 − C0). It is linear in bytes, even though the plot's horizontal axis is logarithmic. The two decimal places report the calculation, not measurement precision at an untested capacity. The CSV table includes every interpolation bracket.

An estimate uses the first upward crossing of its target. The asterisk matters: SIEVE reaches 77.69% at 2 TiB, drops to 67.70% at 3 TiB, then reaches 91.03% at 4 TiB. Its first 75% crossing therefore does not mean every larger cache stays above 75%. We preserve that dip rather than smoothing it away. “Not reached” means the saved measurements did not bracket the target; it is not a prediction about untested capacities.

LRU has a real advantage at the middle target. It needs about 9.10 GiB less payload space than FIFO for 82.5% hits, a 10.9% saving. At 75% and 90%, its estimated saving is only 1.7% and 1.9%, respectively. ARC is close to FIFO at the two higher targets and worse at 75%. S3-FIFO is effectively alongside FIFO at 75% and 82.5%, then needs about 4.6% more capacity at 90%. Neither delivers a substantial, consistent improvement over FIFO across these targets.

W-TinyLFU and SIEVE are a different scale of result. To reach 90%, FIFO needs about 359 GiB. W-TinyLFU needs about 3.81 TiB and SIEVE 3.96 TiB: 10.9 and 11.3 times FIFO's payload capacity. Those gaps are large enough to dominate a memory-sizing decision, while the implementation and workload limitations above still govern what the comparison establishes.

LFU is worse still in this experiment. It has 44 measurements covering the same 1 MiB to 6 TiB capacity grid as FIFO, and its best hit rate is 1.68%, at 6 TiB. None of the three table targets is reached, so there is no supported capacity estimate to put in those cells. The result is consistent with the risk of retaining old popularity without aging, but aggregate hit counts do not establish the cause. What they do establish is that this LFU implementation gives very little benefit on this input, even at the largest tested capacity.

Complete sweep: 0–100% hit rates and all measured capacities

The remaining question is what those hit rates cost to maintain. All these caches must look up the requested page. Beyond that common work, FIFO does no replacement-order update on a hit. LRU normally unlinks and relinks the page. LFU updates frequency buckets. ARC promotes or reorders entries and manages ghost lists. W-TinyLFU observes accesses in its frequency estimator as well as maintaining its LRU regions, and periodically ages the estimator. FIFO and LRU can both have constant-time operations while doing quite different amounts of work.

S3-FIFO and SIEVE deserve a distinction here. Their hit paths update a capped counter or a flag, so they avoid LRU's list movement on every ordinary hit. Their additional work falls largely on eviction, where they may inspect or retain several candidates. It would be wrong to dismiss them as necessarily more CPU-intensive than LRU. Their problem in this comparison is that S3-FIFO buys little additional cache effectiveness, while our SIEVE runs buy much less.

These are comparisons of the operations in the implementations, not measured throughput rankings. The saved elapsed times include trace processing and came from sweeps running many processes in parallel. They cannot tell us how many nanoseconds a production hit costs, or how well a concurrent cache scales. In a RAM cache, the relevant costs include metadata writes, memory traffic, and synchronization. Whether LRU's 9.10 GiB saving at the middle target pays for those costs depends on the deployment.

For this workload, I would still start with FIFO. The broader policy comparison leaves the earlier paper's practical recommendation intact: a small or inconsistent hit-rate gain needs to justify the work required to obtain it. Here FIFO remains near the best measured capacity requirements, uses a simple eviction rule, and leaves the hit path alone. The much larger RAM requirements of W-TinyLFU and SIEVE, and LFU's low hit rate across the entire sweep, give me no reason to prefer those implementations for this input. A different choice should earn its place with a measured benefit on the workload it will actually serve.

The artifact bundle contains the saved outputs, CSV tables, plot generator, and a source snapshot. Raw plotted points, sweep coverage, and the input manifest are also available separately. The output records lack build hashes; the source snapshot documents the implementation at article preparation time rather than identifying the exact binary behind every historical row. This revision regenerates the charts and table from saved data, without rerunning any trace simulations.

References

1. Ohad Eytan, Danny Harnik, Effi Ofer, Roy Friedman, and Ronen Kat. IBM Object Store Traces (SNIA IOTTA Trace Set 36305). In SNIA IOTTA Trace Repository, edited by Geoff Kuenning. Storage Networking Industry Association, July 2019.
2. Ohad Eytan, Danny Harnik, Effi Ofer, Roy Friedman, and Ronen Kat. It's Time to Revisit LRU vs. FIFO. 12th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 20). USENIX Association, July 2020.