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

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 conference › Paper › peer-review

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 language	English (US)
State	Published - 2011
Event	3rd USENIX Workshop on Hot Topics in Storage and File Systems, HotStorage 2011 - Portland, United States Duration: Jun 14 2011 → …

Conference

Conference	3rd USENIX Workshop on Hot Topics in Storage and File Systems, HotStorage 2011
Country/Territory	United States
City	Portland
Period	6/14/11 → …

ASJC Scopus subject areas

Computer Networks and Communications
Software
Hardware and Architecture
Information Systems

Cite this

@conference{71cdccb2be5b40f6aab5cfa771f0edea,

title = "Don't thrash: How to cache your hash on flash",

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.",

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

note = "Publisher Copyright: {\textcopyright} USENIX Workshop on Hot Topics in Storage and File Systems, HotStorage 2011.All right reserved.; 3rd USENIX Workshop on Hot Topics in Storage and File Systems, HotStorage 2011 ; Conference date: 14-06-2011",

year = "2011",

language = "English (US)",

}

TY - CONF

T1 - Don't thrash

T2 - 3rd USENIX Workshop on Hot Topics in Storage and File Systems, HotStorage 2011

AU - Bender, Michael A.

AU - Farach-Colton, Martin

AU - Johnson, Rob

AU - Kuszmaul, Bradley C.

AU - Medjedovic, Dzejla

AU - Montes, Pablo

AU - Shetty, Pradeep

AU - Spillane, Richard P.

AU - Zadok, Erez

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84862657456&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84862657456&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:84862657456

Y2 - 14 June 2011

ER -

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

Abstract

Conference

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this