Don't thrash: How to cache your hash on flash

Michael A. Bender, Martin Farach-Colton, Rob Johnson, Bradley C. Kuszmaul, Dzejla Medjedovic, Pablo Montes, Pradeep Shetty, Richard P. Spillane, Erez Zadok

Research output: Contribution to conferencePaperpeer-review

10 Scopus citations

Abstract

Many large storage systems use approximate-membership-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, 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 flash-based SSD.

Original languageEnglish (US)
StatePublished - 2011
Event3rd USENIX Workshop on Hot Topics in Storage and File Systems, HotStorage 2011 - Portland, United States
Duration: Jun 14 2011 → …

Conference

Conference3rd USENIX Workshop on Hot Topics in Storage and File Systems, HotStorage 2011
CountryUnited States
CityPortland
Period6/14/11 → …

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Software
  • Hardware and Architecture
  • Information Systems

Fingerprint Dive into the research topics of 'Don't thrash: How to cache your hash on flash'. Together they form a unique fingerprint.

Cite this