FAST 存储大会 2025 笔记（三）

该系统的大多数组件至少能使用10年并且其中许多组件的合同保证可更换期长达10年。因此他们开始研究回收利用设备并将其与可用的替换部件结合以提供成本更低的完整系统因为他们重复使用了仍可工作的设备从而分摊原始制造过程中的环境代价。这是非常出色的工作鼓励您去观看那个视频内容也很有趣。在Erik去世后FAST指导委员会意识到社区的巨大损失决定将最佳论文奖更名为Erik Riedel最佳论文奖我们即将颁发此奖。我认为这非常棒。我期待明天晚上与任何想来和我们聊聊Erik Riedel及其成就的人们交谈。谢谢。https://github.com/OpenDocCN/cs-notes-pt1-zh/raw/master/docs/fast25/img/73ca7eea5294ad2150c49b4808d6c0b0_3.pnghttps://github.com/OpenDocCN/cs-notes-pt1-zh/raw/master/docs/fast25/img/73ca7eea5294ad2150c49b4808d6c0b0_4.png总结本节课中我们一起学习了Erik Riedel对存储社区的贡献。从他的博士论文“Active Disks”开始我们看到了计算存储这一核心概念的早期探索即利用设备内部不断增强的计算能力来优化特定应用如数据库查询。其核心思想是通过FPGA等处理器在存储设备端进行数据预处理和缩减以减少带宽需求。这项开创性工作为今天的NVMe CSD等标准奠定了基础。此外我们还了解了他晚年对IT设备全生命周期碳足迹的关注以及社区通过命名最佳论文奖来纪念他的方式。他的工作体现了将前沿学术研究与实际工程问题相结合的持久影响力。039Test of Time Award 获奖演讲与缓存算法演进 https://github.com/OpenDocCN/cs-notes-pt1-zh/raw/master/docs/fast25/img/f0c4134676e64c40dfe30aadd92d2658_1.png在本节课中我们将学习FAST 2025存储大会上颁发的“Test of Time Award”经得起时间考验奖的详情并深入了解获奖论文背后的核心思想——一种高效构建缓存未命中率曲线MRC的算法。我们将从奖项背景开始逐步解析获奖研究的技术突破、历史渊源及其深远影响。奖项介绍与评选过程 “Test of Time Award”设立至今已有13年。该奖项旨在表彰那些对存储社区产生重大影响的论文。参评论文必须至少发表10年。其理念在于获奖成果不应仅是发表时引人注目或获得最佳论文奖的工作而应是真正产生了深远影响的研究。因此需要给予足够的时间来验证其影响力。评选工作由FAST指导委员会和往届程序委员会主席负责具体流程由Raju和我管理。以下是历届获奖者名单我们在此不逐一回顾。你可以回顾这些论文或许会想起其中一些真正出色的研究。https://github.com/OpenDocCN/cs-notes-pt1-zh/raw/master/docs/fast25/img/f0c4134676e64c40dfe30aadd92d2658_1.png今年的评选过程如下我们共有四篇提名论文17位评审提交了总计63份评审意见。随后Raji和我审阅了这些意见并于一月份开会做出了最终选择。我们选出的论文相信大家会一致认为是真正杰出的工作。评审委员会对这篇论文给出了一些评价。一位评审提到“我见过一些商业系统包括存储系统和数据库系统都从这项工作中汲取灵感为客户和现场服务工程师提供了关于为其缓存分配更多或更少内存的预期效果的洞察。”https://github.com/OpenDocCN/cs-notes-pt1-zh/raw/master/docs/fast25/img/f0c4134676e64c40dfe30aadd92d2658_3.pnghttps://github.com/OpenDocCN/cs-notes-pt1-zh/raw/master/docs/fast25/img/f0c4134676e64c40dfe30aadd92d2658_5.png另一位评审说“这篇论文真正革新了在线环境中的MRC使用。据我所知它在已知的MRC曲线算法中性能最佳或者至少是难以被超越的并且非常精确。”还有评审表示“这篇论文使MRC变得实用并推广了其使用。事实上我们公司经常使用所提出的算法或其变体研究缓存策略的人员将这篇论文视为一个里程碑。”基于这些评价有些人可能已经猜到了获奖论文。获奖论文是《Efficient MRC Construction with SHARDS》作者是Carl Waldspurger、Noham Park、Alexander Garthwaite和Irfan Ahmad。我们很幸运他们今天都在现场领奖。现在我将把讲台交给他们。https://github.com/OpenDocCN/cs-notes-pt1-zh/raw/master/docs/fast25/img/f0c4134676e64c40dfe30aadd92d2658_3.png恭喜你们所有人。获奖感言与研究起源 感谢Jeff也感谢奖项委员会我们很荣幸获得这个奖项。我想花点时间回顾一下这项工作的起源和背景。当时我们四人都在一家名为Cloud Physics的初创公司工作该公司专注于虚拟化系统中的资源管理。这项研究源于一个真实的客户挑战一个现实世界的问题为闪存缓存确定合适的大小。当时闪存缓存与传统存储一起变得越来越流行。这提醒我们尽管初创公司节奏紧迫但优秀的研究仍然可以诞生而且需求往往是激发最佳创意的动力。我们首先从客户站点收集IO轨迹并测试缓存大小启发式方法但结果不如预期。我们意识到的一个更有原则的方法是生成未命中率曲线。这个概念可以追溯到1970年的Mattson。然而即使是最好的现有方法也过于耗费资源尤其是对于大型轨迹。由于在之前的项目中使用过采样方法和技术我们探索了采样是否能使MRC构建更高效。但这具有挑战性因为在一个大型稀疏地址空间中进行采样同时跟踪重用情况是前所未有的事情。关键洞察在于使用确定性空间哈希可以驱动随机采样这构成了SHARDS算法的基础。我们的一些同事最初相当怀疑但早期实验超出了预期。有一段时间结果好得令人难以置信我甚至担心可能有一个错误人为地夸大了我们的准确性。但一切顺利。随后我们继续开发了SHARDS的恒定空间变体该变体能够用不到1MB的内存为任意长度的轨迹构建精确的MRC这使得即使在资源最受限的系统中也变得可行。在我们向FAST提交初稿和最终定稿之间我们增加了将空间哈希应用于非堆栈替换算法如ARC或LRS的初步结果为我们后续的微型模拟研究铺平了道路。多年来看到人们在这些想法基础上进行构建真的非常令人兴奋。我们对此认可深表感激谢谢。缓存管理的历史脉络 我是Irfan Ahmad。感谢Carl他是这篇论文的领导者、第一作者也是许多后续工作的主要贡献者。正如Carl所说回顾内存资源管理领域的工作追溯到计算技术的黎明时期那是一段非常有趣的时光。Carl向大家介绍了导致这项特定研究的背景而我想从更早的时候开始分享。让我们回到起点分享一些我们学到的东西其中许多你们可能知道但有些人可能不了解。当我们回顾并试图理解内存资源管理、置换算法通常我们只称之为“缓存”时我们追溯并寻找它的起源。这张图片是Atlas系统的控制台。描述其虚拟内存的论文发表于1962年这意味着这项工作可能大约在1961年完成。据我所知该系统在这篇论文于1962年4月发表时就已经在交付使用了。实际上这是一篇非常出色的论文。当我阅读它时感觉就像在读一篇两天前发表的论文。它写得非常好我们只需要将“磁鼓”替换为“SSD”将“磁芯”替换为“DRAM”它就能讲得通甚至可能今天还能发表在FAST上。这台机器使用了位并试图以此来管理内存。但这是我所知的第一个虚拟内存系统。我们早些时候讨论过我们都不记得有比这更早的了。有趣的是为什么这具有相关性因为这台机器尽管具有创新性但在生产部署中却遇到了灾难性的系统颠簸。系统运行良好但突然会发生颠簸整个系统就会卡住控制台会变得无响应你无法提交新任务。情况非常糟糕。不仅如此这在20世纪60年代实际上是一个相当普遍的问题。问题如此严重以至于IBM在认为自己解决这个问题之前不愿意交付基于虚拟内存的系统。当时市场上已经有多款其他系统了。因此在20世纪60年代中期IBM启动了一个大型项目研究其虚拟内存系统的置换算法。这是因为现场的程序员提出了需求他们除了虚拟内存外不想用任何其他方式编程——既然有了虚拟内存一切都变得简单得多因为你可以获得零基址和连续的内存分配范围。因此出于无奈或必要性他们启动了这个项目这实际上引发了一系列事件最终促成了我们的工作。1966年作为该项目的一部分Belady在尝试研究LRU时发表了一篇论文这篇论文被引用了极高的次数因为我们几乎所有人在某个时间点都在处理内存管理或缓存替换策略并且不得不与那个令人敬畏的MIN算法进行比较。这个离线最优算法可以追溯到1966年。现在你可以看到从1962年到1966年我们已经经历了这个理解周期嘿你必须做更好的内存管理你必须从根本和形式上研究这个问题。这篇半经典的论文发表了。有趣的是这同样可能像是今年FAST的论文“希望通过基于先前引用来预测未来引用以改进替换决策”。我们确实是站在巨人的肩膀上。一些有趣的事情左侧是Belady论文中的图表X轴是缓存大小Y轴是访问频率。这真的很有趣类似的图表在今天发表的论文中仍然出现。这是我发现的第一个实际绘制了未命中率曲线的图表。可能之前就存在我只是不知道。他们构建这个曲线的方法是通过运行多个实验并在它们之间画线。这样你就可以看出工作负载在缓存效率方面的形状。这是非常重要的事情。从1966年到1970年人们已经厌倦了运行大量实验来绘制这些曲线。因此在1970年IBM的Dick Mattson再次发表了他的开创性工作一个单遍算法可以为特定类型即堆栈距离算法的算法绘制整个曲线。正如Carl提到的这在当时是革命性的因为现在你只需要运行一遍就能得到完整的曲线只要算法是堆栈距离型的当时许多算法都是只是最近其他算法才变得越来越流行。现在到了1971年。这篇论文发表了但在工业环境中的采用率很低因为对于长轨迹来说运行起来非常困难因为它是一个昂贵的算法。在随后的几十年里数据结构得到了改进但算法的复杂性没有改变。这就是Carl、Alex、Noham和我在2011年、2012年所处的位置我们试图解决这个问题从那里开始并意识到这个算法对于你想做的事情来说太昂贵了这导致了Carl之前提到的近似算法。研究轶事与算法精进 一些有趣的故事当我们写这篇论文时你应该引用你想引用的东西的最早实例。在这个案例中这是一个时钟算法。我们几个人讨论说“嘿你上次读原始的时钟算法论文是什么时候”我没有读过我想去找找看。我们在Google和你能想到的每个搜索引擎上搜索试图找到这篇论文的PDF。我们找不到。这怎么可能在2014年也许是2015年互联网上怎么会没有这篇论文于是我们联系了一些朋友去麻省理工学院图书馆的书架上找看看能否找到CorbatóFernando Corbato图灵奖得主领导了Multics项目Unix由此而来进而衍生出我们今天使用的所有东西包括这台笔记本电脑上的操作系统的论文。Sam我猜是他去了在麻省理工学院图书馆也找不到这篇论文随后一阵恐慌。这篇被引用了成千上万次的论文怎么会不在互联网上也不在图书馆里那我们一直在引用什么有人读过这篇论文吗它在哪里https://github.com/OpenDocCN/cs-notes-pt1-zh/raw/master/docs/fast25/img/f0c4134676e64c40dfe30aadd92d2658_7.png幸运的是麻省理工学院的Simon教授联系上了Corbató他当时已经退休很久80多岁了正在度假。Corbató在度假时回复说“嘿我很惊讶没有副本我想我阁楼的一个盒子里有一份。”恐慌继续我们希望他有一份因为其他人都没有。总之他度假回来找到了论文。我们得到了PDF。现在它终于可以在multicians.org上找到了你可以直接搜索到它。这只是有趣的故事我们都经历过一些有趣的冒险和趣事我们想分享其中的几个。算法核心调整采样与误差分布 我也想感谢委员会和合著者。这是一个有趣的项目我仍然记得很清楚尽管那是大约10年前的事了。我第一次想到这个想法是在我面试Cloud Physics时我还没有入职。在一次乘车途中我不确定是不是出租车Carl提到了这个想法。我当时想“这行不通。”因为过程是非平稳的如果你采样你不会得到平均行为。我实际上这么说了。那是我第一次见到Irfan。然后Carl说“哦好吧但我还是想试试。”我回到学校。几周后Carl给我发来了数据“嘿这是初步数据。我们做了这些轨迹。”我花了整整一天试图证明它为什么行不通。在几个月里我相当怀疑。直到我深入其中后我感到困惑并试图弄清楚它为什么实际上有效。这对我来说是一段有趣的旅程。我也想感谢大家。这是一次非常美妙的经历。我想接着Carl提到的一点来说那就是算法的惊人准确性。特别值得一提的是我们提出了调整后的SHARDS算法的概念。基本观察是你希望从样本和模拟中得到的是对完整事件集的保真度就像你根本没有采样一样。这里的关键观察是我们如何获取关于整个轨迹运行的、易于测量的某些信息并将其与我们的特定样本的表现进行比较然后调整样本以更接近原始情况。对于MRC来说基本观察是你在MRC中测量的基本上是事件。尽管我们将其打印为比率但实际上你得到的是每个距离上的计数。观察发现距离越远在某种意义上距离越长这类事件的数量就越少因为它们依赖于中间发生了许多其他事件。一个有趣的性质是在采样的情况下因为距离越大导致该距离发生的事件就越多所以你的采样捕捉到该信号的可能性就越大你会在那里得到一些结果。另一方面如果你过度采样那些具有最大距离的事件这很难做到因为这类事件并不多因为它们依赖于中间发生了太多其他事情。观察结果是如果存在误差误差实际上会出现在小距离处。并非全部都在最小距离处但大部分会集中在那里。这些是你可能少计或多计的地方。当你这样做时会产生相当显著的影响。因此调整后的SHARDS算法本质上是计算完整运行发生的事件总数将其与我们样本中实际得到的事件数量进行比较。你期望的是如果样本大小是整个集合的某个百分比你测量到的事件数量也应该有类似的比例关系。如果不是那么这实际上是对你误差程度的一个很好的估计。因此调整后的SHARDS算法基本上利用了这个差值来进行调整主要调整最短距离因为那是大部分误差所在。这实际上对提高准确性产生了深远的影响。我喜欢这个故事的地方在于它试图在样本显示的内容与你易于测量的整体真实情况之间建立联系然后结合识别误差分布中的某些偏差使你的模拟实际上变得更好。我真心认为这是一个更通用的技术我一直在思考如何将其用于其他地方。研究后续与未来展望 我想给大家快速更新一下研究进展。记得和我的合著者们坐下来讨论时我们对这篇论文感到非常兴奋那种兴奋感是巨大的因为你感觉你真的发现了一些有趣的东西。我们当时想好吧其他研究人员会跟进这项工作吗这实际上是一个有趣的问题。其他人会尝试改进它或以我们未曾想到的方式应用它吗我非常高兴在论文发表后很长一段时间里我们之间不断来回发送基于这项工作并改进它或修复某些特定边界情况的论文。我们中的许多人也在该领域发表了额外的著作正如Carl所提到的。我们现在已经有了一个证明证明采样算法有效并且有其准确性的界限这真的令人兴奋。此外作为这项工作一部分形成的想法和模式现在已经衍生出一家新公司名为Magnian。它是一家商业公司帮助设计存储设备、云块存储或内容分发网络的公司使用这些技术来优化其内存层次结构。最后我相信我们可以代表这里的每个人说这项工作尚未完成。如果你来和我们交谈我们会告诉你其他一些尚未探索的有趣领域。所以如果你是对高影响力工作感兴趣的学生在缓存和内存层次结构的预测性能建模领域存在着巨大的机会并且在减少全球闲置内存所浪费的总能耗千兆瓦级别方面有着实际的世界性影响机会。真正高影响力的工作等待着大家。https://github.com/OpenDocCN/cs-notes-pt1-zh/raw/master/docs/fast25/img/f0c4134676e64c40dfe30aadd92d2658_9.pnghttps://github.com/OpenDocCN/cs-notes-pt1-zh/raw/master/docs/fast25/img/f0c4134676e64c40dfe30aadd92d2658_10.png总结 https://github.com/OpenDocCN/cs-notes-pt1-zh/raw/master/docs/fast25/img/f0c4134676e64c40dfe30aadd92d2658_9.pnghttps://github.com/OpenDocCN/cs-notes-pt1-zh/raw/master/docs/fast25/img/f0c4134676e64c40dfe30aadd92d2658_10.png在本节课中我们一起学习了FAST 2025“Test of Time Award”的获奖研究。我们回顾了该奖项的意义与评选标准深入探讨了获奖论文《Efficient MRC Construction with SHARDS》的核心贡献一种利用确定性空间哈希驱动随机采样从而高效、精确构建缓存未命中率曲线MRC的算法。我们追溯了缓存管理算法从20世纪60年代虚拟内存系统到现代研究的历史脉络理解了像MINBelady算法和Mattson算法这样的奠基性工作。最后我们看到了这项研究如何从解决实际工业问题出发通过创新的调整采样技术精进算法并最终衍生出新的商业应用和未来的研究方向。这项工作是连接理论算法与工业实践、并持续产生影响的典范。