FIFO cache simulation using a bloom filter ring

摘要

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:
simulating a first-in-first-out (FIFO) cache having a first size, the simulation including:
initializing a Bloom filter ring, Bloom filter ring including a plurality of Bloom filters arranged in a circular log, and two adjacent ones of the Bloom filters associated with a head pointer and a tail pointer, respectively;receiving a stream of cache accesses;for each of the cache accesses:
determining whether the cache access is a read or write request;(a) if the cache access is a read request, determining whether an element requested by the cache access is a member of the Bloom filter ring;
if the element requested by the cache access is a member of the Bloom filter ring, incrementing a count of a number of hits;(b) if the access is a write request, determining whether an element to be written is a member of the Bloom filter ring;
if the element to be written is not a member the Bloom filter ring, inserting a hash of the element into the Bloom filter indicated by the head pointer;determining whether the Bloom filter indicated by the head pointer is filled to its capacity; andif the Bloom filter indicated by the head pointer is filled to its capacity, deleting membership of elements from the Bloom filter indicated by the tail pointer and advancing the head and tail pointers; andcomputing cache statistics including a cache hit percentage for the FIFO cache having the first size based on the count of the number of hits and a number of read requests.