Source: Slashdot
USENIX,这个长期致力于操作系统/网络研究的团体，还出版一本名为;login:的杂志。今天，该杂志的编辑Rik Farrow（安全顾问）来到Slashdot分享一些最新的研究。Caching意味着利用更快的存储器来存储频繁请求的数据，而确定缓存满时要丢弃哪些项最常用的算法是Least Recently Used或称为LRU。
这些研究人员提出了一种更有效和可扩展的方法，只需几行代码即可将LRU转换为SIEVE。就像筛子一样，通过一个称为“手”的指针筛选对象，“筛出不受欢迎的对象并留下受欢迎的对象”，受欢迎程度基于一个单一位来跟踪缓存对象是否被访问过：当“手”从尾部（最旧的对象）移动到头部（最新对象）时，未被访问的对象将被清除...在随后的筛选轮次中，如果在之前的轮次中幸存下来的对象仍然受欢迎，它们将保留在缓存中。在这种情况下，由于大多数旧对象不会被清除，清除手迅速越过旧受欢迎的对象到接近头部的队列位置，使新插入的对象能够快速评估和清除，对不受欢迎的项目（如“一击奇迹”）施加更大的清除压力，胜过基于LRU的清除算法。
这是“懒惰提升和快速降级”的一个例子。受欢迎的对象通过最小的努力得到保留，快速降级“至关重要，因为大多数对象在被清除之前不会被重复使用。
经过1559次跟踪（共247,017亿请求到14,852亿个对象），他们发现与FIFO相比，SIEVE将10%的跟踪中的错误率降低了42%以上，平均为21%（而且速度更快，更具可扩展性，胜过LRU）。SIEVE不仅能实现更高效率、更高吞吐量和更好的可扩展性，而且非常简单。
数据处理中的关键算法研究，对提升缓存效率和性能优化至关重要。" } ```
