Don't Thrash: How to Cache your Hash on Flash Appears in the proceedings of the 3rd USENIX Workshop in Hot Topics in Storage and File Systems (HotStorage 2011)

Abstract Many large storage systems use approximatemembership-query (AMQ) data structures to deal with the massive amounts of data that they process. An AMQ data structure is a dictionary that trades off space for a false positive rate on membership queries. It is designed to fit into small, fast storage, and it is used to avoid I/Os on slow storage. The Bloom filter is a well-known example of an AMQ data structure. Bloom filters, however, do not scale outside of main memory. This paper describes the Cascade Filter TM , an AMQ data structure that scales beyond main memory, supporting over half a million insertions/deletions per second and over 500 lookups per second on a commodity flashbased SSD