type
status
date
slug
summary
tags
category
icon
password
原文
Caching in the Real World
Reality 1 ： Cost of remote data access often not uniform 远程数据访问的成本往往不统一
- often takes the from Ax+B for x bytes
- may be more complex as x gets larger (e.g. TCP file transfer)
Ax+B
A：固定成本
x: 数据字节大小
B: 可变成本
远程数据访问存在固定成本+可变成本
固定成本 TCP 连接开销，权限验证等
可变成本：序列化和反序列化、压缩和解压缩等
“小数据”和“大数据” 缓存策略不一样。
Reality 2 : “Near by” objects often accessed soon after object access "邻近 "对象往往在访问对象后不久就被访问
- another empirical observation about real systems in real use 关于实际使用中的真实系统的另一个经验观察
- referred to as “spatial locality of reference ” or “ spatial locality” 简称“参考空间局部性”或“空间局部性”
邻近的概念取决于你对上下文的理解。
Reality 3: Remote data more coarsely addressable than local 远程数据比本地数据更难寻址
- typically a scalability tradeoff at next level of memory hierarchy
same of number of address bits can cover larger volume of data
e.g. cache line with , page size ,whole file , tape mount
- “wholesale” versus “retail”
远程数据的可寻址的粒度要比本地数据要“粗”的多
Combining observations ⇒ fetch more than you need on miss
- effectively amortizes cost of fetch
- assumption sometimes violated
- extra data fetched is then useless(may even hurt) 获取额外的数据毫无用处（甚至会造成损失）
can be viewed as crude form of prefetching
获取比需要更多的数据，当缓存未命中时，多获取一些暂时不需要，但未来可能需要的数据。
通过“批量获取”分摊成本，有效的减少未来缓存未命中的次数，但是一旦假设失效（未来可能会用到的这些额外数据），多余的数据就会变成负担。
这种策略可以看作是预取的粗略形式。
Spatial & Temporal Locality
时空局部性
Temporal and spatial locality are very different properties
- caching implementations often tightly combine these assumptions 缓存实现通常会将这些假设紧密结合起来
- one can exist without the other
spatial without temporal : linear scan of huge file 没有时间性的空间性：对巨大文件的线性扫描
temporal without spatial : tight loop accessing just one object 无空间的时间性：仅访问一个对象的紧密循环
- 时间局部性（Temporal Locality）：如果一个数据被访问过，那么它在短期内很可能被再次访问（“最近用的，马上还会用”）。
- 空间局部性（Spatial Locality）：如果一个数据被访问过，那么它相邻地址的数据（比如物理上靠近的内存块、连续的文件内容）很可能被访问（“用了这个，旁边的也会被用”）。
这两种局部性是完全不同的 “数据访问模式属性”—— 缓存设计会同时利用两者（比如按块缓存利用空间局部性，保留最近访问块利用时间局部性），但它们可以单独存在（即一种存在时，另一种可能完全不存在）。
优秀的缓存设计通常会将两者结合。
For example , consider typical implementation of “ rm -f *”
Update Propagation
更新传播
（aka “ Cache Consistency”） 缓存一致性
Update Propagation = Cache consistency
One-Copy Semantics
单副本语义
Prefect functional transparency 完美功能透明性
A caching(or replication) system has one-copy semantics iff 缓存（或复制）系统具有单副本语义
- there are no externally observable functional differences 没有外部可观察到的功能差异
- relative to same system without caching (or replication) 相对于同一系统，无缓存（或复制）
No pattern of interleaved inputs to different nodes of the system can
produce reliably distinguishable outputs in the two cases
(however , performance / timing differences may be visible)
Too difficult to achieve in practice (except in very narrow circumstances) 在实践中太难实现（极少数情况除外）
Goodness criteria for implementation 实施的良好标准
- how little safety can you give up , yet still remain scalable? 在保持可扩展性的同时，您能放弃多少安全性？
- how complex is the implementation 实现很复杂
proofs of correctness are useless if implementation is buggy
单副本语义： 完美透明性的核心目标，“带缓存（或数据复制）的系统，对外表现得和‘没有缓存 / 复制的系统’完全一样”。
功能上无差异仅允许性能差异。
安全性指的数据一致性，功能正确性。
可扩展性指的是系统支持更多的数据、更多的节点、更多的用户。
引入Cache 和 Replication ，数据存在多份。缓存的数据和原始数据可能“不同步”。
多节点复制时的并发读写可能导致不同副本之间不一致。
想要完全避免都就需要保持强一致性，比如每次读写都强制同步原始数据和缓存，但这会缓存的”加速“失去意义。随着副本的增加，同步所有副本的成本也会随之增加。
世界上有许多实现都是错误的，一个主要问题在于，你必须与原始实现保持”bug兼容“，因为人们已经习惯了那些有缺陷的语义，如果你真的修复并纠正了它，反而会让许多用户感到不满。
- Author:newrain-zh
- URL:https://alex.sh.cn/article/cmu-15-440/cache-2
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
.png?table=block&id=26b332f2-d485-807d-9f05-e01b6c17fab0&t=26b332f2-d485-807d-9f05-e01b6c17fab0)