{"id":{"repo_id":"texas","oai_identifier":"oai:repositories.lib.utexas.edu:2152/68212"},"canonical_url":"https://search.dev.ndltd.org/etd/texas/oai:repositories.lib.utexas.edu:2152/68212","repository":{"repo_id":"texas","name":"University of Texas","base_url":"https://repositories.lib.utexas.edu/server/oai/request"},"display":{"title":"PebblesDB : building key-value stores using fragmented log-structured merge trees","abstract":"Key-value stores such as LevelDB and RocksDB offer excellent write throughput, but suffer high write amplification. The write amplification problem is due to the Log-Structured Merge Trees data structure that underlies these key-value stores. To remedy this problem, this thesis presents a novel data structure that is inspired by Skip Lists, termed Fragmented Log- Structured Merge Trees (FLSM). FLSM introduces the notion of guards to organize logs (sstables or files containing the data on storage), and avoids rewriting data in the same level. Theoretically, we show how FLSM can address the problem of write amplification. We build PebblesDB, a high-performance key-value store, by modifying HyperLevelDB to use the FLSM data structure. We evaluate PebblesDB using micro-benchmarks and show that for write-intensive workloads, PebblesDB reduces write amplification by 2.4-3x compared to RocksDB, while increasing write throughput by 6.7x. We evaluate PebblesDB extensively under a variety of benchmarks, workload patterns, and environmental factors and analyze how it performs in different scenarios. We modify two widely-used NoSQL stores, MongoDB and HyperDex, to use PebblesDB as their underlying storage engine. Evaluating these applications using the YCSB benchmark shows that throughput is increased by 18-105% when using PebblesDB (compared to their default storage engines) while write IO is decreased by 35-55%.","abstract_html":"Key-value stores such as LevelDB and RocksDB offer excellent write throughput, but suffer high write amplification. The write amplification problem is due to the Log-Structured Merge Trees data structure that underlies these key-value stores. To remedy this problem, this thesis presents a novel data structure that is inspired by Skip Lists, termed Fragmented Log- Structured Merge Trees (FLSM). FLSM introduces the notion of guards to organize logs (sstables or files containing the data on storage), and avoids rewriting data in the same level. Theoretically, we show how FLSM can address the problem of write amplification. We build PebblesDB, a high-performance key-value store, by modifying HyperLevelDB to use the FLSM data structure. We evaluate PebblesDB using micro-benchmarks and show that for write-intensive workloads, PebblesDB reduces write amplification by 2.4-3x compared to RocksDB, while increasing write throughput by 6.7x. We evaluate PebblesDB extensively under a variety of benchmarks, workload patterns, and environmental factors and analyze how it performs in different scenarios. We modify two widely-used NoSQL stores, MongoDB and HyperDex, to use PebblesDB as their underlying storage engine. Evaluating these applications using the YCSB benchmark shows that throughput is increased by 18-105% when using PebblesDB (compared to their default storage engines) while write IO is decreased by 35-55%.","abstract_has_math":false,"creators":["Raju, Pandian"],"institution":"The University of Texas at Austin","degree_name":"Master of Science in Computer Sciences","degree_level":"Masters","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Chidambaram, Vijay"],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018-06-25","date_published":"2018-06-25","updated_at":"2026-07-24T05:01:06Z","subjects":["PebblesDB","Key-value stores","Log-structured merge trees","FLSM","Write-optimized data structures","Fragmented Log-Structured Merge Trees"],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["doi:10.15781/T2C53FK67"],"render_values":[{"text":"doi:10.15781/T2C53FK67","href":"https://doi.org/10.15781/T2C53FK67","code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2152/68212","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Chidambaram, Vijay"]},{"key":"dc:creator","label":"Author","values":["Raju, Pandian"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2018-08-29T23:12:59Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2018-08-29T23:12:59Z"]},{"key":"dc:date.issued","label":"Date","values":["2018-06-25"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science in Computer Sciences"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["The University of Texas at Austin"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["PebblesDB","Key-value stores","Log-structured merge trees","FLSM","Write-optimized data structures","Fragmented Log-Structured Merge Trees"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["doi:10.15781/T2C53FK67"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/2152/68212"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Key-value stores such as LevelDB and RocksDB offer excellent write throughput, but suffer high write amplification. The write amplification problem is due to the Log-Structured Merge Trees data structure that underlies these key-value stores. To remedy this problem, this thesis presents a novel data structure that is inspired by Skip Lists, termed Fragmented Log- Structured Merge Trees (FLSM). FLSM introduces the notion of guards to organize logs (sstables or files containing the data on storage), and avoids rewriting data in the same level. Theoretically, we show how FLSM can address the problem of write amplification. We build PebblesDB, a high-performance key-value store, by modifying HyperLevelDB to use the FLSM data structure. We evaluate PebblesDB using micro-benchmarks and show that for write-intensive workloads, PebblesDB reduces write amplification by 2.4-3x compared to RocksDB, while increasing write throughput by 6.7x. We evaluate PebblesDB extensively under a variety of benchmarks, workload patterns, and environmental factors and analyze how it performs in different scenarios. We modify two widely-used NoSQL stores, MongoDB and HyperDex, to use PebblesDB as their underlying storage engine. Evaluating these applications using the YCSB benchmark shows that throughput is increased by 18-105% when using PebblesDB (compared to their default storage engines) while write IO is decreased by 35-55%."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["PebblesDB : building key-value stores using fragmented log-structured merge trees"]}]}],"canonical_facts":{"dc:contributor.advisor":["Chidambaram, Vijay"],"dc:creator":["Raju, Pandian"],"dc:date.accessioned":["2018-08-29T23:12:59Z"],"dc:date.available":["2018-08-29T23:12:59Z"],"dc:date.issued":["2018-06-25"],"dc:description.abstract":["Key-value stores such as LevelDB and RocksDB offer excellent write throughput, but suffer high write amplification. The write amplification problem is due to the Log-Structured Merge Trees data structure that underlies these key-value stores. To remedy this problem, this thesis presents a novel data structure that is inspired by Skip Lists, termed Fragmented Log- Structured Merge Trees (FLSM). FLSM introduces the notion of guards to organize logs (sstables or files containing the data on storage), and avoids rewriting data in the same level. Theoretically, we show how FLSM can address the problem of write amplification. We build PebblesDB, a high-performance key-value store, by modifying HyperLevelDB to use the FLSM data structure. We evaluate PebblesDB using micro-benchmarks and show that for write-intensive workloads, PebblesDB reduces write amplification by 2.4-3x compared to RocksDB, while increasing write throughput by 6.7x. We evaluate PebblesDB extensively under a variety of benchmarks, workload patterns, and environmental factors and analyze how it performs in different scenarios. We modify two widely-used NoSQL stores, MongoDB and HyperDex, to use PebblesDB as their underlying storage engine. Evaluating these applications using the YCSB benchmark shows that throughput is increased by 18-105% when using PebblesDB (compared to their default storage engines) while write IO is decreased by 35-55%."],"dc:format.mimetype":["application/pdf"],"dc:identifier":["doi:10.15781/T2C53FK67"],"dc:identifier.uri":["http://hdl.handle.net/2152/68212"],"dc:language.iso":["en"],"dc:subject":["PebblesDB","Key-value stores","Log-structured merge trees","FLSM","Write-optimized data structures","Fragmented Log-Structured Merge Trees"],"dc:title":["PebblesDB : building key-value stores using fragmented log-structured merge trees"],"dc:type":["Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Masters"],"thesis:degree_name":["Master of Science in Computer Sciences"],"thesis:institution_name":["The University of Texas at Austin"]},"updated_at":"2026-07-24T05:01:06Z"}