关键词：web缓存；非阻塞；时钟算法；LRU；队列
摘 要：In this report, I present NbQ-CLOCK, a novel, lock-free variant of the Generalized CLOCK algorithm particularly suited for web-object caching. My solution benefits from Generalized CLOCK’s low-latency updates and high hit rates, and its non-blocking implementation makes it scalable with only 10 bytes per-object space overhead. I compare the solution to existing algorithms, including Intel’s Bag-LRU, and demonstrate that NbQ-CLOCK’s fast update operation scales well with the number of threads and in a in-memory key-value store prototype, NbQ-CLOCK offers an overall throughput improvement of as much as 9.20% over the best of the other algorithms. In addition, NbQ-CLOCK’s hit rate exceeds the next best algorithm’s hit rate by as much as 1.40%.