Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Toronto

$46,000.00

Universal Filters for Storage Engines

EF 2023-24

Résumé
Our society is creating and storing exponentially increasing amounts of data. What is often less thought of are the storage engines that maintain this data and facilitate the extraction of knowledge from it. A storage is the software component of a database system that organizes data on a storage device. It's behavior greatly affects the performance of databases and applications running on top. Over the past fifteen years, new types of storage engines began to emerge to prioritize the efficiency of ingesting new data. The goal of such engines is to better handle the growing rate at which many modern applications insert and update their data. Such engines include Google's BigTable, Amazon's DynamoDB, Facebook's RocksDB, as well as Apache Cassandra and HBase. These engines have become indispensable for a wide range of applications, including cloud storage, blockchain, machine learning, retail, banking, etc. In contrast to traditional storage designs, which sort the underlaying data to be able to find data items quickly, these new engines structure the data more loosely (i.e., semi-sorted or not sorted at all). This less rigid organization reduces overheads on the write-path and thereby allows data to be ingested more efficiently. The trade-off is that queries can take longer to find data items that users are seeking. To keep the performance of queries fast, such storage engines employ in-memory filters. A filter is a compact representation of the data that allows to quickly rule out the existence of a data entry and thus avoid having to search for it in storage. The premise of this research program is that existing filters lack important capabilities that are needed by storage engines. These include how to efficiently (1) expand as the data that they represent grows, and (2) learn from the workload to reduce the rate at which the filters make mistakes. The inability of existing filters to implement these functionalities efficiently leads to significant performance loss. Furthermore, we argue that there are various untapped opportunities that exist for co-designing storage engine with filters. These include (3) filtering ranges of keys rather than just individual keys in a unified manner over the whole storage engine, and (4) optimizing for applications that need to insert data only if it does not already exist. The projected outcome of this program are ground-breaking performance improvements for storage engines and their users. These improvements would empower new applications that require greater performance and scale, while making existing applications less resource-hungry and thus more sustainable and green.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2023-03580
Name nom
Dayan, Niv
Department département
Computer Science
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2023
Award amount
46000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Algorithms
Research subject en
Technologie de l'information
Research subject fr
Algorithmes
Application title
Universal Filters for Storage Engines
Keyword
Design space generalization; Filters; Key-value stores; Log-structured data systems; Performance; Self-tuning; Sketches; Storage engines
Application summary
Our society is creating and storing exponentially increasing amounts of data. What is often less thought of are the storage engines that maintain this data and facilitate the extraction of knowledge from it. A storage is the software component of a database system that organizes data on a storage device. It's behavior greatly affects the performance of databases and applications running on top. Over the past fifteen years, new types of storage engines began to emerge to prioritize the efficiency of ingesting new data. The goal of such engines is to better handle the growing rate at which many modern applications insert and update their data. Such engines include Google's BigTable, Amazon's DynamoDB, Facebook's RocksDB, as well as Apache Cassandra and HBase. These engines have become indispensable for a wide range of applications, including cloud storage, blockchain, machine learning, retail, banking, etc. In contrast to traditional storage designs, which sort the underlaying data to be able to find data items quickly, these new engines structure the data more loosely (i.e., semi-sorted or not sorted at all). This less rigid organization reduces overheads on the write-path and thereby allows data to be ingested more efficiently. The trade-off is that queries can take longer to find data items that users are seeking. To keep the performance of queries fast, such storage engines employ in-memory filters. A filter is a compact representation of the data that allows to quickly rule out the existence of a data entry and thus avoid having to search for it in storage. The premise of this research program is that existing filters lack important capabilities that are needed by storage engines. These include how to efficiently (1) expand as the data that they represent grows, and (2) learn from the workload to reduce the rate at which the filters make mistakes. The inability of existing filters to implement these functionalities efficiently leads to significant performance loss. Furthermore, we argue that there are various untapped opportunities that exist for co-designing storage engine with filters. These include (3) filtering ranges of keys rather than just individual keys in a unified manner over the whole storage engine, and (4) optimizing for applications that need to insert data only if it does not already exist. The projected outcome of this program are ground-breaking performance improvements for storage engines and their users. These improvements would empower new applications that require greater performance and scale, while making existing applications less resource-hungry and thus more sustainable and green.