[Paper Review] Kosmo: Efficient Online Miss Ratio Curve Generation for Eviction Policy Evaluation

Paper Info

Titile: “Kosmo: Efficient Online Miss Ratio Curve Generation for Eviction Policy Evaluation” Conference: FAST’24

읽은 이유

FAST’24에 나온 논문 탐방

My Note

(240507)
in-memory cache, clould server와 storage server의 관계에 좀 더 배경 지식이 있었으면 논문의 이의를 이해하는데 더 좋았을 듯.
내가 관심 있는 주제는 아니라 얇게 읽음 (intro 까지만).
cache size와 miss ration가 비례하지 않고 특정 부분에서 cliff가 발생하는 것을 보이는 실험이 흥미로웠음.

Summary

Miss Ratio Curves (MRCs) are an important tool.

Many MRC-generation algorithms have been developed.

Miniature Simulations (MiniSim) is only tool for capable of efficiently generating MRCs for popular eviction polices, such as LFU, FIFO, 2Q, and LRFU that do not adhere to the inclusion property.

But, it incurs significant memory overhead, precluding its use for online cache analysis at runtime in many cases.

Kosmo performs better by using less memory, plots MRCs even for policies that do not have an inclusion property, and effectively generates multiple mrcs at the same time.

Scope of Study

> In-memory Cache

In-memory caches play an important role in reducting the load on backend storage servesrs for many workloads.

These caches imporve scalability and can reduce the latency of data access requests by serving data directly from main memory.

Redis and Memcached are two popular in-memory caches.

In-memory caches can consume a large portion of a data center’s operating budget.

> Trade-off between cache size and miss ratio.

In cloud-hosted environments, such caches are priced proportionately to their size.

So, it is important to provision each cache to the “rigth” size using the cost-performance trade-offs for its workloads.
too small => higehr miss ration, higher backend storage server loads
too large => consume unnecessary resources, higher operational costs

MRC is one of the most effective tools to understand trade-off between cache size and miss ration.

MRC plots a cache’s miss ratio as a function of the cache size.

cache size와 missratio가 단순 비례 하지 않아 (cliff), knowledge of its presence is particularly useful.

> Efficiency of eviction policy dependent on workload

Eviction Policy는 workload에 따라 효율성이 다름.

Problem

Almost all existing MRC gneration algorithms only model caches operating with the inclusion property (e.g LRU).

Miniature Simulations (MiniSim) is only known MRC generation algo for non-LRU caches (LFU, FIFO, 2Q, LRFU, MRU).

MiniSim has several serious drawbacks.

• high memory usage
• more inefficient when creating multiple MRCs simultaneously

Key Idea

Introduce Kosmo which has the lower memory overhead and the higher throughput than Miniature Smulations.

Kosmo is better suited for online MRC generation.

Eviction Map a novel method of calculating reuse distances.

Can simultaneously generate MRCs MRCS for a variety of eviction polices including six eviction polices: LFU, FIFO, 2Q, LRFU, LRU, MRU.

Note for Remembering

MRCs provide insight into the trade-off between cache size (and thus costs) and miss ratio for a specific eviction policy.