Efficient Ledger Database System

Abstract:

Database users and system developers are focusing more on data security today. Recently, ledger databases have been introduced to protect the integrity of data, history, and query results. There are two main challenges faced by ledger databases. First, how to provide high performance while guaranteeing the security of data. Second, as an emerging database system, there is a lack of comprehensive study on its design space and techniques. In this dissertation, we focus on the ledger database system and take a step-by-step study from analyzing its core data structure, exploring its challenges and design choices, to building an efficient ledger database system.

This thesis starts with analyzing the authenticated data structure (ADS), which is the core component of the ledger database. It maintains the full history of data and provides integrity proof. The ADS should be immutable, tamper-evident, and efficient. We identify a new category of indexes, namely Structurally Invariant and Reusable Indexes (SIRI), which fulfills all the requirements and conducts a comprehensive analysis of SIRI both theoretically and experimentally.

Inspired by the SIRI building block and to address the performance challenge, we design and implement a practical distributed ledger database system, GlassDB. GlassDB supports verifiability and transactions, as well as offers high performance. It extends POS-Tree as the authenticated data structure for efficient proof generation and adds a concurrency control mechanism for transactions. GlassDB batches independent operations from concurrent transactions when updating the core data structures. We evaluate GlassDB with the proposed verification benchmark extended from YCSB and TPC-C. Experimental results demonstrate that GlassDB is an efficient, transactional, and verifiable ledger database system.

Despite the fact that many ledger databases have been designed and implemented in recent years, there is no uniform benchmarking tool to systematically and fairly evaluate existing systems. We propose VeriBench, a benchmarking framework for verifiability-enabled database systems. Based on our study of the design choices, we include micro-benchmarks to evaluate performance impact on a single component, and macro-benchmarks adapted from a key-value benchmark (YCSB) and two OLTP benchmarks (SmallBank and TPC-C) for system-level performance. We conduct extensive experiments to illustrate the strengths and weaknesses of each design and system, which should be useful for the future development of verifiability-enabled database systems.