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

School of Arts and Sciences, Computer Science

Rutgers, The State University

Research output: Contribution to conference › Paper › peer-review

9 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 language	American English
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{23812576a3c94edf9086a67a90644d85,

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 = "Funding Information: This research was supported in part by a grant from DOE Grant DE-FG02-08ER25853, NetApp, a NetApp Faculty Award, and NSF Grants CCF-0540897, CNS-0627645, CCF-0634793, CCF-0937829, CCF-0937833, CCF-0937854, CCF-0937860, and CCF-0937822, and Polit{\'e}cnico Grancolombiano. 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 = "American English",

}

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

N1 - Funding Information: This research was supported in part by a grant from DOE Grant DE-FG02-08ER25853, NetApp, a NetApp Faculty Award, and NSF Grants CCF-0540897, CNS-0627645, CCF-0634793, CCF-0937829, CCF-0937833, CCF-0937854, CCF-0937860, and CCF-0937822, and Politécnico Grancolombiano. Publisher Copyright: © USENIX Workshop on Hot Topics in Storage and File Systems, HotStorage 2011.All right reserved.

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

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