1700495300
1700495301
20世纪60年代末，威尔克斯的提议在IBM 360/85超级计算机中得以实现，人们称之为“缓存”。从那以后，计算机科学中到处都有了缓存的身影。将频繁调用的信息片段保存以备后用的效果非常好，因此这个做法在计算的各个方面都得到了应用。处理器有缓存，硬盘有缓存，操作系统有缓存，Web浏览器有缓存，连向这些浏览器提供内容的服务器也有缓存，因此我们可以立刻看到数百万人观看的猫骑真空吸尘器的视频……但是，我们的步子迈得有点儿超前了。
1700495302
1700495303
根据人们的描述，计算机在过去50多年里逐年呈指数增长，这为“摩尔定律”精准的预测了下一个注脚。1975年，英特尔的戈登·摩尔提出“摩尔定律”，称中央处理器的晶体管数量每两年翻一番。但是，存储器的性能没有按这个速度提升，这意味着访问存储器时的时间成本也在呈指数增长。例如，你写论文的速度越快，每次去图书馆带给效率的负面影响就越大。同样，如果工厂每年将制造速度提升一倍，但是零部件从海外运送到工厂的速度仍然那么慢，总数也没变，这只能意味着该工厂停工的时间将增加一倍。在一段时间内，摩尔定律似乎没有任何实际意义，它只不过预测出处理器的速度将越来越快，闲置的时间会越来越多。在20世纪90年代，人们开始把这种现象称作“内存墙”。
1700495304
1700495305
为了避免一头撞上这堵墙，计算机科学至今为止采取的最有效措施就是缓存、缓存的缓存以及缓存的缓存的缓存，如此而已。现代消费者购买的笔记本电脑、平板电脑和智能手机都有一个6层的分级存储器体系。今天，存储器的智能管理对计算机科学的重要性已经达到了史无前例的高度。
1700495306
1700495307
一提到缓存（或者具有类似功能的壁橱），我们大脑中闪现的第一个问题就是：如果它们装满了东西，我们该怎么办？下面，我们就从这个问题开始谈起。
1700495308
1700495309
1700495310
1700495311
1700495313
算法之美：指导工作与生活的算法 缓存清理与未卜先知
1700495314
1700495315
夏洛克·福尔摩斯
1700495316
1700495317
相信我，总有一天，当你增加新知识的时候，就会把以前熟知的东西忘了。所以最要紧的是，不要让一些无用的知识把有用的挤出去。
1700495318
1700495319
缓存满了后，如果你想继续在缓存中存储其他东西，就必然需要腾出一些空间。在计算机科学中，在缓存中腾出空间的过程被称为“缓存替换”或“缓存清理”。威尔克斯指出：“由于缓存的容量比主存小好几倍，不能无限度地把数据保存在其中，因此我们必须在系统中植入一个算法，逐步覆盖缓存中的数据。”这些算法被称为“替换策略”或“清理策略”，或者简单地称为缓存算法。
1700495320
1700495321
我们知道，IBM在20世纪60年代率先推动缓存系统的部署应用。不出意料，它也是早期缓存算法开创性研究的发源地，也许他们取得的任何一项成果都没有拉斯洛·贝莱迪的算法重要。1928年，贝莱迪出生于匈牙利，大学期间学的是机械工程专业。在1956年匈牙利革命期间，身无分文的他逃到了德国，随身携带的书包里只装有“一件内衣和毕业论文”。后来，他又离开德国，来到法国，并于1961年移民到美国。这一次，他带着妻子，“襁褓中的孩子，口袋里装着1000美元。除此以外，就别无他物了”。似乎在他进入IBM研究缓存清理之前，他就已经深谙此道，知道哪些东西该留下来，哪些东西可以抛弃。
1700495322
1700495323
贝莱迪于1966年发表的那篇缓存算法论文是随后15年里被引用最多的计算机科学研究成果。这篇论文解释道，缓存管理的目标是尽可能减少“页面错误”或“缓存缺失”。所谓缓存缺失，是指无法在缓存中找到所需数据，因此只能到较慢的主存中查找的现象。贝莱迪在文中写道，从本质上讲，最优缓存清理策略就是在缓存已满时，将未来最长时间内不会再次使用的数据从缓存中清理出去。
1700495324
1700495325
当然，要确切地知道什么时候会再次需要某些数据，并不像说起来那么容易。
1700495326
1700495327
今天，为了表示敬意，人们把那个无所不知、有先见之明，而且可以在分析未来情况基础上执行最优缓存策略的那个假想算法称作贝莱迪算法。该算法是被计算机科学家称为“千里眼”算法的一个实例，一个可以从未来数据中获取信息的算法。这个概念其实并不像听起来那么疯狂（在某些情况下，系统可能会对未来产生一种期望），但是一般来说，未卜先知是很难实现的，因此软件工程师在实践中试图使用贝莱迪算法时，就会开玩笑说他们遭遇了“实施难题”。因此，我们面临的挑战是找到一种接近于未卜先知的算法，当我们被当前现状遮住双眼的时候，可以借助这种算法看清楚未来的情况。
1700495328
1700495329
我们可以尝试随机清理算法，将新数据添加到缓存中，并随机覆盖旧数据。随机清理是早期高速缓存理论得出的一个令人吃惊的结果，虽然远非完美，但是效果也还不错。这也可能是一种巧合，因为只要有一个缓存，无论你如何维护，都可以提升系统的效率。不管怎么说，你经常使用的内容通常还会很快回到缓存中。另一种简单的策略叫作先进先出（FIFO）。这种算法总是清理或覆盖在缓存中保存时间最久的内容（与玛莎·斯图尔特问的“我已拥有它多长时间了”这个问题有异曲同工之妙）。第三种方法是最近最少使用（LRU），即将闲置不用时间最长的内容清理掉（与之相对应的斯图尔特的问题是“上次穿它或使用它是什么时候的事”）。
1700495330
1700495331
事实证明，斯图尔特强调的这两点暗示了两种截然不同的策略，而且她的一条建议显然比另一条更有效果。贝莱迪在若干情形下对随机清理、先进先出和最近最少使用的几个变体进行了比较，结果发现最近最少使用法始终表现出最接近未卜先知的效果。最近最少使用法的高效性得益于计算机科学家所谓的“时间局部性”：如果一个程序曾经调用过某个信息，那么在不久的将来它可能会再次调用这个信息。计算机解决问题的方式（例如，执行一个循环，使一系列相关的读和写可以快速完成）是造成时间局部性的一个原因，而人解决问题的方式是另外一个原因。在使用电脑时，你可能会在电子邮件、网页浏览器和文字处理器之间来回切换。你最近访问过这些程序的这个事实就是一个线索，表明你可能会再次访问该程序。在同等条件下，如果某个程序处于闲置状态的时间较长，就表明你在未来一段时间内应该也不会调用该程序。
1700495332
1700495333
事实上，这一原则甚至隐含于计算机向用户展示的界面中。电脑屏幕上的窗口有所谓的“Z轴顺序”，即决定程序相互叠加次序的模拟深度。最近最少使用的程序处于底部。前火狐浏览器的创意主管阿扎·拉斯金说：“使用现代浏览器（电脑）在很多时候就相当于从事数字版的文书工作。”与“文书工作”的相似性淋漓尽致地体现在微软系统Windows和苹果系统Mac OS任务切换界面中：当你按下Alt+Tab或Command+Tab组合键时，就会看到，你最近使用过的程序按你使用的时间先后逆向排列。
1700495334
1700495335
研究缓存清理策略的相关文献已经达到了令人难以想象的深度，各种算法应有尽有，不一而足，有的可以计算使用频率和最后一次使用时间，有的可以追踪倒数第二次访问的时间，而不关心最后一次访问的情况。不过，尽管创新性高速缓存方案品种繁多，其中一些在适当的条件下甚至可以击败最近最少使用法，但是最近最少使用法（以及在该策略基础上做出的一些细微调整）仍然深受计算机科学家们的喜爱，并且在开发各种应用程序时得到不同程度的应用。最近最少使用法告诉我们，我们需要的下一个程序可能就是之前我们需要的最后一个程序，接下来我们可能还需要之前需要的倒数第二个程序。我们最不需要的可能就是我们弃用时间最长的那个程序。
1700495336
1700495337
除非有充分的反对理由，否则我们可以认为对未来最有借鉴意义的就是历史的镜像。最接近于未卜先知的做法就是假定历史会重演，不过是按照相反的顺序重新上演。
1700495338
1700495339
1700495340
1700495341
1700495343
算法之美：指导工作与生活的算法 重整图书馆藏书
1700495344
1700495345
加州大学伯克利分校的地下加德纳书库是加州大学图书馆系统的一大亮点。书库在一扇锁着的门后，门上写着“闲人止步”几个显眼的大字，把想要借阅图书的人堵在门外。这里收藏着科马克·麦卡锡、托马斯·品钦、伊丽莎白·毕肖普、J.D.塞林格、阿娜伊斯·宁、苏珊·桑塔格、朱诺·迪亚斯、迈克尔、查邦、安妮·普劳克丝、马克·斯特兰德、菲利普·K·迪克、威廉·卡洛斯·威廉姆斯、恰克·帕拉尼克、托妮·莫里森、丹尼斯·约翰逊、朱莉安娜·斯帕尔、乔丽·格雷厄姆、戴维·赛达瑞斯、西尔维亚·普拉斯、戴维·马梅特、戴维·福斯特·华莱士和尼尔·盖曼等人的作品。但是，这些不是图书馆的珍本藏书，而是它的“缓存”。
1700495346
1700495347
前文讨论过，图书馆与我们自己的桌面空间相互配合，就可以恰如其分地表现出分级存储器体系的特点。实际上，图书馆由不同分区和存储设施构成，本身就是多层次分级存储器体系的一个具体实例，因此图书馆面临各种各样的缓存问题。图书馆工作人员必须决定把哪些书放在图书馆最前面的有限展示空间里，哪些书放到书架上，哪些书放到其他地方储存起来。各图书馆判断哪些书应该异地收藏的策略都不相同，但是几乎所有图书馆都会使用某种版本的最近最少使用策略。加州大学伯克利分校图书馆负责监督这个过程的贝丝·杜普斯说：“举例来说，如果一本图书12年里没有人借阅，我们就会把它撤出主馆。”
1700495348
1700495349
图书馆“粗略分类”区的情况与12年没有人借阅的图书正好处于两个极端。我们在前一章讨论过这些图书：它们刚刚被读者归还到图书馆，还没有被完全排序并重新放到书架上。具有讽刺意味的是，在某种意义上看，那些辛勤的图书馆助理在把这些图书放回书架上的时候，可能会让次序变得更乱。
[
上一页 ]
[ :1.7004953e+09 ]
[
下一页 ]