Ksld154's Notebook

Caching with Delayed Hits

  • Oct 07, 2020

1 Background & Issues

  • Delayed hit:
    • 在高throughput的環境中，當有多個request都要access某個item x，而x不在cache中
    • 在x被fetch進cache這段等待期間內，所發生的request x，都稱作delayed hit

  • i.e. 當fetch latency > request inter-arrival time時，就有機會發生delayed hit

  • 因此這篇paper提出 BELATEDLY cache algorithm，來預估有delayed hit的情況下，理論上的performance upper-bound
    • 再藉由BELATEDLY, 進一步推導出可以在系統上實際跑的heuristic greedy cache algo. MAD

2 THE PROBLEM WITH DELAYED HITS (現有解法的不足/設計上的挑戰)

  • 現有的cache algorithm以最大化hit rate為目標
    • 在設計時並未考慮delayed hit，導致低估整體latency
      • $Avg. Latcncy = HR*HitLatency + MR * MissLatency$
      • 會將delayed hit當成hit (Figure1)
    • 在Bursty request時，低估的特別嚴重(Figure 3)
    • 在$MissLatency$高的時候，低估的特別嚴重(Figure 4)
      • $Z = MissLatency / InterRequestTime$
  • 故考慮進delayed hit後，hit rate並不適合做為評估latency的唯一指標
  • Belady Algo 是目前hit-rate跟latency都最好的offline algo
    • 承上，也沒有考慮Delayed hit
    • BELATEDLY的對照組 　
  • Challenges
    • 合適的schedule會隨著$Z$值改變
      • => General Solution並不好找 (是NPC問題)
    • 只針對Latency優化
      • Hit rate可能會下降，導致bandwidth consumption上升

3 Introduction

  • 名詞定義:
    • Offline Algo: 理論最大值，知道未來所有request
      • e.g. Belady Algo
    • Online Algo: 實際使用，不知未來的request
  • BELATEDLY: 幾乎完美解出latency-minimal cache schedule
    • offline, slow
    • 僅作為performance upper-bound
  • MAD: heuristic解, 可以實際在系統上執行
    • online, fast
    • 透過rank function(x)算出Aggregate Delay，作為heuristic metric
      • Aggregate Delay: 考慮delayed hit的情況下，每次miss的成本
    • 再用greedy找出適合的cache schedule

4 BELATEDLY

  • Latency-minimization可以reduce成Minimum-Cost Multi-Commodity Flow (MCMCF) problem
    • NP-Complete問題，不能多項式時間內找出解
    • Optimization:
      • 在graph上剪枝
      • 改求fractional solution, rounding to integer
  • MCMCF
    • MCF(Minimum-Cost Flow)
      • 給定一張graph跟多組src-dst pair, edge有cost跟capacity限制
      • 找出一組flow滿足每組src-dst pair, 且total cost最小
    • MCMCF是多種貨物的MCF problem
      • edge上不同貨物的capacity跟cost會不一樣
  • Latency-minimization => MCMCF
    • Vertex: Object in the cache/backing-store
    • Edge: obj. state transition
      • obj. move into cache
      • obj. keep in cache
      • obj. move out from cache
    • Edge weight(cost): Aggregate Latency
      • MissLatency + Total delay caused by delayed-hit
    • Edge Capacity: 看edge的種類
  • How to Convert to MCMCF (How to build MCMCF graph)
    • Edge種類
      • 上層vertex代表cache item, 下層是memory item
      • into/keep/kick
    • MCMCF graph(Tricky)
      • 下層vertex是時間t的request, 上層是把request item移到cache的狀態
        • (都假設miss, 所以request都在下層的memory?)
      • Evicted Edges
        • 假設有k種item
        • 上層的每個vertex就會有k條Evicted Edges, 表示從cache踢出$K_i$這個item
        • 故有些evicted edge是不合理的，可以被剪掉(appendix)
    • Edge cost/capacity specification
      • Keep Edge $(V_{cch,n}, V_{cch,n+1})$
        • Capacity: $C$ (cache size)
        • Cost: 0
      • Evicted Edge $(V_{cch,n}, V_{mem,x})$
        • Capacity: 1
        • Cost:
          • $\infty$ for other items
          • $0$ for item requested at Time=x
      • Move-in Edge $(V_{mem,T}, V_{cch, T+Z})$
        • Capacity: 1
        • Cost:
          • $\infty$ for other items
          • $AggregateDelay$ for item requested at Time=T
            • MissLatency + Total delay caused by delayed-hit
  • Equivalence to Latency-Minimizing Caching
    • MCMCF:找到最小cost的flow
    • Latency-Minimizing Caching: 找到total latency最小的cache schedule
    • Appendix有證明兩者等價
      • i.e. 滿足MCMCF的一組flow variable, 可以對應到一組cache schedule
  • Compare with Belady
    • Significantly better average latency than Belady for today’s highest-latency systems
    • $Z$ is correlated with an increasing gap between Belady and belatedly
    • The gap between Belady and belatedly varies with cache size
    • Belatedly’s caching decisions are correlated with the burstiness of requests

5 APPROXIMATING BELATEDLY

  • $BELATEDLY$太慢，只能用來估計performance upper-bound
  • $BELATEDLY$的solver並不能顯示，它到底是依據什麼原則來選擇item排進schedule

    5-1 Offline Approximations: Belady-AD

  • 原則：找出一個heuristic ranking function，依據其大小決定選哪個item進schedule (greedy)
    • $TTNA(x):$ 下一次access x還要過幾個timestamp

5-2 Online Algorithm: MAD

  • online: 無法得知未來的request分布
    • 改用過去的request計算
  • 同樣的heuristic ranking function
    • 現有cache algo的目標已經是$\frac{1}{TTNA(X)}$
  • 故剩下的問題是：如何估計$AggDelay(x)$
    • 將過去的access request(x)都當成miss，並計算平均AggDelay

6 EXPERIMENTS

skip

7 Limitation

  • 並無考慮cache->backing store latency
  • 也沒考慮不同item size
  • delayed hit也不一定是item一進到cache，就馬上全部處理完
    • 可能會需要額外的queue儲存，導致latency上升
  • poor competive-ratio $\Omega(kZ)$
    • => worst-case performance不好 (因為這是determistic algo)
    • Randomized algorithms

Architecture

Figure

Search