PACE: Penalty Aware Cache Modeling with Enhanced AET

Abstract

  • support varied-size data objects
  • support update and delete operations (in addition to reads and writes)
  • support non-uniform miss penalties

Introduction

Modeling an lru stack

  • Read Operation. Access a d-byte object in an LRU cache. A hit will move the d bytes to the top of the LRU stack. On a miss, we must bring the missed data from lower storage or other places to the cache.
  • Delete Operation. Delete a d-byte object from an LRU cache. The effect is that all the data in the LRU stack that reside below the deleted object will move d bytes toward the LRU stack top. If the object being deleted is not present in cache, there will be no data movement.
  • Write and Update Operation. Write or update a d -byte value with an address/key. If the address/key is not present in cache, the write/update operation will result in an insertion to the stack top such that every data object moves d bytes towards the LRU stack bottom. Otherwise, the update can change the size of an object. Assume that the update changes a d1-byte item to d2 bytes. If d1 is larger than d2, we can consider that d2 bytes are reused and d1 − d2 bytes are deleted. If d1 is equal or smaller than d2, d1 bytes in the original data will be reused and the additional d2 − d1 bytes are treated as a new write (cold miss).

Enhanced AET modeling

  • byte-level minimum granularity

Penalty aware cache management

Impacts of Miss Penalty on MRC

miss penalty 来自一个 Read 之后紧接着的 Write，因为现实生活中可能只有这样的 req 必须要等。但不知道怎么把这种 “penalty” 融入 miss ratio curve。

Memory Partitioning Guided by MRC

Dynamic Programming 是万金油

Evaluation

MRC Accuracy of Enhanced AET

不懂为什么 EAET 会快很多：

Penalty Management

To manage the miss penalty, we measure the time interval between the miss of a GET request and the SET of the same key immediately following the GET request.

略

评价

abstract 说的三个方面基本都做到了，byte-level granularity 确实可以解决 varied-size 问题，增加了 operation 的 model 也确实挺干净漂亮。但我有几个疑虑：

  • byte-level 会不会粒度太细，导致计算开销大/计算时间长？
  • EAET 的速度也太快了，怎么做到粒度更细却速度更快？Dynamic Programming 的效率怎么做到很高的？
  • 只考虑 GET 之后紧挨着 SET 的情况来计算 penalty 会不会 cover 太少了？