What is Digest-Based Caching?

Digest-Based Caching

Digest-Based Caching uses Cache Digests to check if something is present in the cache. Cache Digests are collections of metadata that can be used to tell if something is present in the cache.

When a cache receives a URL request, it collects cache digests from its peers. After running searches on all valid cache digests, it returns the required data from the closest peer that has it, if any peer does.

Cache Digests

Cache Digests are designed to work as Bloom Filters. Bloom Filters are data structures designed to work as mathematical sets that can offer searches with $O(1)$ time complexities.

Bloom filters are essentially arrays that contain bits. These arrays are initially filled with zeros. When something, like a URL, according to the web cache example, is added to a bloom filter, a set number of hash functions are applied to it. The resulting hash values act as indices in the array and are converted to 1.

When a search is made, the searched value is used in these hash functions. The value can only be said to be present in the bloom filter if all the resultant hashed indices are set to 1. Even a single 0 will indicate that the value is not present in the bloom filter.