METHOD AND SYSTEM FOR DETERMINING FIFO CACHE SIZE

摘要

Described herein are methods, systems and machine-readable media for simulating a FIFO cache using a Bloom filter ring, which includes a plurality of Bloom filters arranged in a circular log. New elements are registered in the Bloom filter at the head of the circular log. When the Bloom filter at the head of the circular log is filled to its capacity, membership information associated with old elements in the Bloom filter at the tail of the circular log is evicted (simulating FIFO cache behavior), and the head and tail of the log are advanced. The Bloom filter ring is used to determine cache statistics (e.g., cache hit, cache miss) of a FIFO cache of various sizes. In response to simulation output specifying cache statistics for FIFO cache of various sizes, a FIFO cache is optimally sized.

主权项

1. A method, comprising:
performing a first simulation of a first first-in-first-out (FIFO) cache of a first size using a first Bloom filter ring, wherein the first simulation determines cache statistics for the first FIFO cache of the first size, and wherein performing the first simulation includes periodically removing a membership of a subset of elements from the Bloom filter ring so as to simulate a periodic deletion of elements from the FIFO cache; performing a second simulation of a second FIFO cache of a second size using a second Bloom filter ring, wherein the second simulation determines cache statistics for the second FIFO cache of the second size; and determining a FIFO cache size based on (i) the cache statistics for the first FIFO cache of the first size and (ii) the cache statistics for the second FIFO cache of the second size.