计算机科学家发明了一种高效但极其简单的算法,可以决定从网络缓存中丢弃哪些项目,为新项目腾出空间。这种新的开源算法被称为 SIEVE,具有大规模改变网络流量管理的潜力。
SIEVE 是埃默里大学、卡内基梅隆大学和百利金基金会计算机科学家的联合项目。该团队关于 SIEVE 的论文将于4 月在加利福尼亚州圣克拉拉举行的第 21届USENIX 网络系统设计和实现 (NSDI) 研讨会上发表。
该论文的预印本已经引起了轰动。
“SIEVE 的规模越来越大,不仅仅是我们,”埃默里大学博士生、该论文的共同第一作者张亚卓说道。“它已经表现良好,但我们收到了很多好的建议,以使其变得更好。这就是开源世界的美妙之处。”
张与 Jun Cheng (Jason) Yang 共同担任该论文的第一作者,后者在埃默里大学获得计算机科学硕士学位,目前是卡内基梅隆大学的博士生。
埃默里大学计算机科学系副教授 Ymir Vigfusson 表示:“SIEVE 是对经过验证的缓存驱逐算法的简单改进,该算法已经使用了数十年,这实际上就像计算世界中的几个世纪一样。”
Vigfusson 和卡内基梅隆大学计算机科学系副教授 Rashmi Vinayak 是这篇论文的共同高级作者。百利金基金会的计算机工程师姚跃也是合著者。
除了速度和有效性之外,引起人们对 SIEVE 兴趣的一个关键因素是它的简单性以及可扩展性。
“简单就是终极的复杂,”Vigfusson 说。“旨在在一瞬间为数十亿人提供服务的系统中的各个部分越简单,就越容易有效地实施和维护该系统。”
将“热物体”放在手边
许多人都了解定期整理衣柜的价值。从未使用过的物品可以扔掉,很少使用的物品可以移至阁楼或其他远程位置。这样一来,最常佩戴的物品就可以放在触手可及的地方,这样就可以快速找到它们,而无需到处翻找。
缓存就像一个组织良好的计算机数据储藏室。缓存中充满了用户请求的最流行对象的副本,或者 IT 术语中的“热对象”。缓存将这个小型热对象集合与计算机网络的主数据库分开维护,这就像一个巨大的仓库,里面装满了系统可以提供的所有信息。
缓存热对象可以使网络系统更有效地运行,快速响应用户的请求。Web 应用程序可以通过弹出一个方便的储藏室来获取用户想要的大部分对象,而不是前往仓库并在庞大的数据库中搜索每个请求,从而有效地处理更多流量。
“缓存无处不在,”张说。“对于每家使用 Web 应用程序的公司(无论大小)来说都很重要。每个网站都需要一个缓存系统。”
然而,在计算机科学领域,缓存的研究相对较少。