{'fraction_non_alphanumeric': 0.03910614525139665, 'fraction_numerical': 0.006384676775738229, 'mean_word_length': 4.832558139534884, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
NbQ-CLOCK: A Non-blocking Queue-based CLOCK Algorithm for Web-Object Caching

Major Internet-based service providers rely on high-throughput web-object caches to serve millions of daily accesses to frequently viewed web content. A web-object cache’s ability to reduce user access time is dependent on its replacement algorithm and the cache hit rate it yields. In this report, I present NbQ-CLOCK, a novel, lock-free variant of the Generalized CLOCK algorithm particularly suited for web-object caching. NbQ-CLOCK is based on an unbounded non-blocking queue with no internal dynamic memory management, instead of the traditional circular buffer. 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%.