Lazy loaded image
CMU-15-440
📖Lecture 6 Cache Part 1
Words 1643Read Time≈ 5 min
2025-7-20
2025-7-20
type
status
date
slug
summary
tags
category
icon
password
原文
marking Far Look near
 
The only application-transparent technique to reduce end-to-end latency
唯一可减少端到端延迟的应用程序透明技术。
即应用程序无需任何感知，只需引入缓存，系统性能便能显著提升。
 

Basic Concept

Bare-bones idea
  1. You need to make multiple references to an object
  1. The object is far away
  1. You make a local copy and access it instead
  1. Do all this transparently to programs and users(”under the covers”) 对程序和用户透明（"隐藏"）地完成所有这些工作
 
Local storage used for copies is referred to as the cache 用于复制的本地存储被称为高速缓存
Local copy of a single object is called “a cache copy” 单个对象的本地副本称为 "缓存副本”
Transparency is key : completely invisible (except better performance) 透明度是关键：完全不可见（除了更好的性能）
 

Recap: Simple Cache Metrics

课程：15-213/513
References → number of attempts to find an object in the cache
Hits → number of success 命中次数
Misses → number of failures 未命中次数
Miss Ratio = Misses / References
Hit Ratio = Hits / References = (1- Miss Ratio)
 
Expected cost of reference = ( Miss Ratio * cost of miss) + (Hit Ratio * cost of hit)
 
Cache Advantage = (Cost of Miss / Cost of Hit)
(where cost is measured in time delay to access object) 其中，成本以访问对象的时间延迟来衡量
 

Double Win

(a “twofer” , not a tradeoff) (二选一"，而非取舍）
数据结构与算法中，常常在时间和空间之间做取舍，缓存则是对客户端和服务端都受益的行为。
Caching site obviously wins big
  • local copy → lowest possible latency 本地复制 → 尽可能低的延迟
  • many sources of end-to-end latency avoided 避免了许多端到端延迟源
      • no network queuing delays 无网络排队延迟
      no server queuing or computation delays 无服务器排队或计算延迟
      no transmission delays 无传输延迟
 
缓存的引入改变了服务器所处理的工作负载
 
Rest of the distributed system also wins big
Remember the 3 fundamental variables of queuing theory 记住排队理论的 3 个基本变量
  • utilization (aka “efficiency”) 利用率（又称 "效率）
  • latency (aka “response time” or “agility”)
  • freedom (aka “arrival discipline”)
 
Caching lowers utilization of shared resources 缓存降低了共享资源的利用率
  • less network traffic , less server load
  • you caching makes life better for everyone else
 

Deep Assumption

深层假设
“Multiple references” → caching useless for just one reference "多个引用"→缓存仅对一个引用无用
  • on any reference i how do you know there will more?
  • typical assumption: one reference ⇒ others likely 典型假设：一个参考文献⇒其他可能的参考文献
  • empirical observation about real systems in real use 对实际使用中的真实系统进行实证观察
  • “temporal locality of reference” or just “temporal locality” “参考的时间位置”或“时间局部”
  • assumption sometimes fails to be true → caching wasteful 假设有时不成立 → 缓存造成浪费
 
时间局部性
📑
时间局部性是计算机系统中缓存设计的核心原理之一，指的是如果一个数据被访问过，那么它在不久的将来很可能再次被访问。这种特性使得缓存能够显著提升系统性能，因为频繁访问的数据可以保留在更快的存储介质（如CPU缓存、内存缓存）中，减少重复访问慢速存储（如磁盘、数据库）的开销。
 

Caching is Widely Applicable

缓存的广泛适用性
 
notion image
缓存无处不在，硬件、软件中都使用了缓存这种技术手段。
  • Variable size more common 可变大小更常见
      • 缓冲中的数据单元大小不固定，而非CPU 的 Cache Line这种固定大小的。
  • More time for decision making 决策时间增加
      • 分配/回收变长数据需动态计算内存空间，算法更复杂如内存分配器需处理碎片合并
  • More space for housekeeping 元数据开销增大
      • 需额外存储管理信息记录每个对象的size、TTL、内存指针等
  • More complex success criteria 命中率判断复杂化
      • 传统缓存策略通过内存地址直接映射判断是否命中，变长缓存需 Key 匹配 → 校验数据有效性 →返回变长数据块
  • Less temporal locality 时间局部性减弱
      • 固定尺寸缓存：LRU淘汰策略移除最旧块
      变长缓存：淘汰一个大对象可以释放大量空间，但移除了“低频但最近访问”的数据
  • More complex spatial locality 空间局部性复杂化
      • 用户访问好友A的主页时，缓存需同时加载：
    • A的资料（小文本）
    • A的头像（中尺寸）
    • A的最新视频（大文件）
        • 空间局部性不再连续，需预加载多个非相邻数据块。
  • Higher cache advantage common（缓存收益反而更高）
      • 看似矛盾实则合理，虽然可变尺寸引入复杂度，但在真实业务中收益显著。
       

      Key Questions

      1. What data should you cache and when?
          2. Fetch policy
      1. How do updates become visible everywhere?
          2. Update propagation policy
      1. What old data do you know throw out to free up space?
          2. Cache replacement policy
获取策略、更新传播策略、缓存替换策略
 
if you have infinite cache space,#3 is a non-issue 如果缓存空间无限大，#3 就不是问题了（指的是缓存替换策略）
  • but “cold cache misses”(i.e., first reference still cause delay) 但 "冷缓存未命中"（即首次引用仍会造成延迟）
  • so prefetching becomes very important - 所以预取变得非常重要
预取原则和按需原则
 

How Do You Know What to Cache?

Approach 1: Full Replication
Used by DropBox and other similar services
Designate a subtree as backed by DropBox
  1. every participating machine gets a full and complete copy
  1. every new file gets transmitted to all replicas
  1. every updated file gets propagated
      2. no well-defined semantics for when updates are propagated

Shortcomings of DropBox Approach

(all such solutions are known as “sync solutions” in industry jargon) 所有这些解决方案在行业术语中被称为 "同步解决方案"）。
  1. Storage for entire subtree consumed on every replica 每个副本消耗整个子树的存储空间
  1. Significant update traffic on host spots 主机位置上的大量更新流量
      2. painful on metered networks(e.g. 4G LTE) 在以流量计费上的痛苦
      no well-defined semantics for when you see updates 没有明确定义何时看到更新的语义
  1. Machines receive updates whether they care or not 机器会收到更新无论是否在乎
      2. aka “push” model or update propagation 又称 "推送 "模式或更新传播
       
Coarse-grain , non-selective management of data 粗粒度、非选择性数据管理
 

A Much Better Approach

Transparently fetch file only if needed: on-demand caching 仅在需要时透明地获取文件：按需缓存
(aka “demand caching”)
  • approach used in AFS
      • inherited and extended from AFS-2 by Coda File System
  • requires integration with the operating system 需要与操作系统集成
  • fine-grained and selective approach to data management 细粒度和选择性的数据管理方法
 
Optional reading
“Efficient User-Level File Cache Management on the Sun Vnode Interface”
 
Support first introduced into Linux By Coda file System
  • now standardized as FUSE module
  • “FUSE” → “file system in user space”
  • original Coda kernel module continues to exist in Linux kernel
📑
Coda File System（简称 Coda） 是一个开创性的 分布式网络文件系统，诞生于20世纪80年代末的卡内基梅隆大学（CMU）。它的核心目标是解决早期分布式文件系统（如AFS，Andrew File System）的局限性，尤其是在 断网环境下的可用性 和 移动计算支持 方面。
Andrew File System (安德鲁文件系统):
  • AFS 是一种分布式网络文件系统，允许用户通过网络在多台计算机上访问和共享文件，就像在本地计算机上一样。
  • 它由卡内基梅隆大学开发，后被 IBM 商业化（称为 IBM AFS），现在有开源版本 OpenAFS。
 
📑
在谈及缓存这个技术时，MIT 和 CMU 都使用了分布式文件系统做为切入点，这是一个非常有意思的现象。
上一篇
Lecture 5 Latency
下一篇
Lecture 7 Cache Part 2
Comments
Loading...
Catalog