缓存与局部性Caching and Locality

把反复要用的东西放在近处，用更少的取用成本换速度，并及时更新。

同一部电影被反复点开时，让它每次都走一趟远路，是重复付运输费。2012 年 6 月 4 日，总部位于美国加州洛斯加托斯的 Netflix，由内容分发负责人肯·弗洛伦斯宣布推出 Open Connect。Netflix 把存有影片副本的服务器放进合作运营商的网络，让附近观众直接取用。晚间，人们各自在家按下播放键，重复观看的影片便能从附近送来。影片没有变短，观众也没有少看；同样的内容提前放到了更容易拿到的地方。

为什么成立

需求集中时，少量副本就能省下大量往返

处理器反复执行一段循环时，会一遍遍读取同几条指令。把这些指令留在小而快的存储器里，就能少等慢速内存。这就是缓存：保留数据或计算结果，让后续请求复用。

局部性解释了为什么小缓存能管用。时间局部性是刚用过的东西，在接下来一段时间里容易再用；空间局部性是读过一个位置后，容易接着读附近的位置。循环会重复，数组会连续遍历，所以访问集中在一小片数据上。

节省多少，要看多少次能直接取到

设每次查缓存花 1 毫秒，没找到后再取原始数据花 100 毫秒。若十次请求有九次命中，平均耗时是 11 毫秒。

$T = t_{c} + (1 - h) t_{m}$

这里 $t_{c}$ 是查缓存的时间， $h$ 是命中率， $t_{m}$ 是未命中后额外取数的时间。白话说：每次都付查找费，只有没找到时才付远路费。缓存越能留住接下来要用的东西，平均等待越短。

快的位置有限，旧副本也会失效

缓存装满后，必须腾出位置。淘汰最久没用的条目，是利用近期需求预测下一次需求；长期高频的条目，也值得保留。原始数据改变时，副本要更新或作废。缓存值得保留的条件，是复用省下的成本超过存放、维护和用错旧副本的代价。

出处

这个模型来自计算机体系结构与操作系统，缓存并非一人一次发明。彼得·丹宁于 1967 年公开提出工作集模型，并于 1968 年发表期刊论文，用近期访问的数据集合描述程序需求。IBM 在 1968 年的 System/360 Model 85 中采用高速缓存；随后对工作集管理的实验，验证了保留近期所用数据能减少慢速存储访问。

换个领域看

技术

让处理器少等

IBM 在 1968 年公布的 System/360 Model 85，把小容量高速缓存放在处理器与主存之间。程序再次读取已缓存的数据时，就能从快处取得。它利用程序反复访问少量指令和数据的习惯，让昂贵的高速存储只覆盖眼前常用的部分。

个人生活

把早餐放手边

早餐天天做同几样东西，就值得给它们留一个近处的位置。每天早晨冲咖啡的人，把杯子、滤纸和咖啡豆放在机器旁，备用存货留在高柜。每次用完归位，滤纸快用尽时补充。少量常用品占住方便的位置，换来每天少翻几次柜子、少走几趟路。

投资

保留研究底稿

每季度跟踪同一家上市公司时，研究底稿能省掉重复找资料的时间。投资者把收入分类、债务到期表和财报页码存进固定文件，新财报发布后沿着这些入口更新数字。稳定的资料结构可以复用，估值所用的价格和盈利预测则随新信息刷新，下一次研究从已核实的事实接着做。

遇事时问自己

最近反复取用或重新计算的东西有哪些，每次花了多少时间？
接下来还会重复这些需求吗，哪些刚用过的东西最值得留在手边？
哪些东西会接连一起用，放在一起能省掉哪些往返？
方便的位置只能放有限几样东西，谁省下的取用成本最多？
原始信息改变后，什么信号会提醒我更新或丢弃旧副本？

边界与误用

需求只出现一次、访问分散，或任务切换快过复用速度时，缓存会忙着装入又淘汰，省不下多少取用成本。必须读取最新库存、账户余额等数据时，旧副本还会造成错误，要先保证更新及时。最常见的误用，是把“最近用过”当成“值得一直保留”，甚至把熟悉的结论当成可靠的结论。近期使用只能帮助预测复用，不能证明内容正确。安全装备等低频但后果重大的物品，也应按紧急取用的代价安排位置。

练一练

一位译员正在翻译输液泵操作手册，几个部件名会反复出现。查正式译名要翻多份文件，翻译软件的侧栏只能放 30 条。侧栏目前留着上个月游戏项目的常用词。医疗器械客户会在审稿期间修订译名，并发来更新通知。

哪种侧栏维护办法最站得住？

一位家长周末要缝六只帆布文具袋。每做一道接缝，都依次用划粉、直尺、夹子和剪刀，一晚要重复十几次。桌边浅盘只能放四样工具，其余放在走廊柜里。昨天补外套用过拆线器，这批文具袋暂时用不到。

怎样安排工具，最能减少今晚的来回取用？

一位个人债券投资者准备买入一笔成交稀少的公司债。券商软件的快捷面板保留了上午询到的价格和可买数量，下午打开仍能立即显示。午间发行人公布了重大诉讼，上午报价也已超过有效期。重新向交易商询价通常要等两分钟。

此时哪种判断最站得住？