跳动城乡网计算机科学家发明了一种高效但极其简单的算法，可以决定从网络缓存中丢弃哪些项目，为新项目腾出空间。这种新的开源算法被称为SIEVE，具有大规模改变网络流量管理的潜力。
SIEVE是埃默里大学、卡内基梅隆大学和百利金基金会计算机科学家的联合项目。该团队关于SIEVE的论文将于4月在加利福尼亚州圣克拉拉举行的第21届USENIX网络系统设计和实现(NSDI)研讨会上发表。
该论文的预印本已经引起了轰动。
“SIEVE的规模越来越大，不仅仅是我们，”埃默里大学博士张亚卓说道。学生和论文的共同第一作者。“它已经表现良好，但我们收到了很多好的建议来让它变得更好。这就是开源世界的美妙之处。”
张与JunCheng(Jason)Yang共同担任该论文的第一作者，后者在埃默里大学获得计算机科学硕士学位，现为该大学的博士学位。卡内基梅隆大学的候选人。
埃默里大学计算机科学系副教授YmirVigfusson表示：“SIEVE是对已经使用了几十年的久经考验的缓存驱逐算法的简单改进，这实际上就像计算世界中的几个世纪一样。”
Vigfusson和卡内基梅隆大学计算机科学系副教授RashmiVinayak是这篇论文的共同高级作者。百利金基金会的计算机工程师姚跃也是合著者。
除了速度和有效性之外，引起人们对SIEVE兴趣的一个关键因素是它的简单性以及可扩展性。
“简单就是终极的复杂，”Vigfusson说。“旨在在几分之一秒内为数十亿人提供服务的系统中的各个部分越简单，就越容易有效地实施和维护该系统。”
将“热物体”放在手边
许多人都了解定期整理衣柜的价值。从未使用过的物品可以扔掉，很少使用的物品可以移至阁楼或其他远程位置。这样一来，最常佩戴的物品就可以放在触手可及的地方，这样就可以快速找到它们，而无需到处翻找。
缓存就像一个组织良好的计算机数据储藏室。缓存中充满了用户请求的最流行对象的副本，或者IT术语中的“热对象”。缓存将这个小型热对象集合与计算机网络的主数据库分开维护，这就像一个巨大的仓库，里面装满了系统可以提供的所有信息。
缓存热对象可以使网络系统更有效地运行，快速响应用户的请求。Web应用程序可以通过弹出一个方便的储藏室来获取用户想要的大部分对象，而不是前往仓库并在庞大的数据库中搜索每个请求，从而有效地处理更多流量。
“缓存无处不在，”张说。“这对于使用Web应用程序的每个公司(无论大小)都很重要。每个网站都需要缓存系统。”
然而，在计算机科学领域，缓存的研究相对较少。
缓存的工作原理
虽然缓存可以被认为是计算机的一个组织良好的储藏室，但当数百万人在不断变化的需求中使用它时，很难知道应该放入该储藏室中的内容。
高速缓存的快速内存运行成本昂贵，但对于Web用户的良好体验至关重要。目标是将未来最有用的信息保留在缓存中。其他对象必须不断地被筛选出来，或者用技术术语来说是“驱逐”，以便为不断变化的热对象阵列腾出空间。
缓存驱逐算法确定要丢弃哪些对象以及何时丢弃。
FIFO，即“先进先出”，是20世纪60年代开发的经典驱逐算法。想象一下物体在传送带上排列。新请求的对象从左侧进入，最旧的对象在到达右侧行尾时被驱逐。
在LRU(“最近最少使用”)算法中，对象最终也会沿着线移动到驱逐。然而，如果一个对象在沿着传送带向下移动时再次被请求，它就会被移回到队列的头部。
逐出算法有数百种变体，但它们往往会变得更加复杂以提高效率。这通常意味着它们推理起来不透明并且需要大量维护，尤其是在处理大量工作负载时。
“如果一个算法非常复杂，它往往会存在更多错误，而所有这些错误都需要修复，”张解释道。
