Zili Shao

In recent years, Log-Structured Merge Tree (LSM-tree) based key-value stores, such as LevelDB and RocksDB, have been widely adopted in data center systems. Though optimized for high-speed write processing, the severe I/O amplification remains a critical constraint that hinders them from reaching their maximum performance potential. Unfortunately, this problem is deeply rooted in the fundamental design of the LSM-tree structure. A small number of frequently updated key-value items could quickly pollute the entire tree structure, causing repeated changes in the structure and quickly amplifying the amount of disk I/Os across the levels in the tree. In this paper, we present a novel solution, called Log-assisted LSM (L2SM) tree, to effectively mitigate the long-existing I/O amplification problem. L2SM adopts a small-size, multi-level log structure to isolate selected key-value items that have a disruptive effect on the tree structure, accumulates and absorbs the repeated updates in a highly efficient manner, and removes obsolete and deleted key-value items at an early stage. We also establish a systematic foundation, named CAMEL, to analyze the compaction effects of key-value operations. We have prototyped the L2SM structure based on LevelDB. Our experimental evaluation with the YCSB benchmark shows promising results by reducing the amount of disk I/Os by up to 40.2%, increasing the throughput by up to 67.4%, and decreasing the average latency by up to 41%.

Storage engine is a crucial component in relational databases (RDBs). With the emergence of Internet services and applications, a recent technical trend is to deploy a Log-structured Merge Tree (LSM-tree) based storage engine. Although such an approach can achieve high performance and efficient storage space usage, it also brings a critical double-logging problem—In LSM-tree based RDBs, both the upper RDB layer and the lower storage engine layer implement redundant logging facilities, which perform synchronous and costly I/Os for data persistence. Unfortunately, such “double protection” does not provide extra benefits but only incurs heavy and unnecessary performance overhead. In this paper, we propose a novel solution, called Passive Data Persistence Scheme (PASV), to address the double-logging problem in LSM-tree based RDBs. By completely removing Write-ahead Log (WAL) in the storage engine layer, we develop a set of mechanisms, including a passive memory buffer flushing policy, an epoch-based data persistence scheme, and an optimized partial data recovery process, to achieve reliable and low-cost data persistence during normal runs and also fast and efficient recovery upon system failures. We also comprehensively analyze the recovery inefficiencies inherent in the undetermined persistence speeds in real-world workloads, and propose a hybrid persistence scheme that incorporates virtual-flush-based recovery optimizations to achieve the optimal recovery performance when performing epoch-based persistence. We implement a fully functional, open-sourced prototype of PASV based on Facebook’s MyRocks. Evaluation results show that our solution can effectively improve system performance by increasing throughput by up to 49.9% and reducing latency by up to 89.3%, and it also saves disk I/Os by up to 42.9% and reduces recovery time by up to 4.8%.

Driven by the exploding demands for real-time data analytics, hybrid transactional and analytical processing (HTAP) has become a topic of great interest in academia and the database industry. To address the well-known conflict between optimal storage formats for online transactional processing (OLTP) and online analytical processing (OLAP), the conventional practice employs a mixture of distinct indexes and dynamically migrates data across different index domains. Unfortunately, such a multi-index design is notably subject to non-trivial trade-offs among OLTP/OLAP performance and data freshness. This work advocates a single-index design to serve HTAP workloads. This is made possible by computational storage drives (CSDs) with built-in transparent compression that are emerging on the commercial market. The key is to exploit the fact that compression-capable CSDs enable sparse data management without sacrificing physical storage capacity. Leveraging this, we have developed an HTAP-oriented B ⁺ -tree design that can effectively serve HTAP workloads and meanwhile achieve almost instant data freshness. We also comprehensively analyze the inherent effects of storage fill factor and propose a dynamic adapter design to achieve optimal storage/performance efficiency for varying workloads. We have developed and open-sourced a fully functional prototype. Evaluation results show that our design can ensure data freshness and deliver high performance.

Spatio-temporal data are continuously generated and grow exponentially with the rapid proliferation of mobile devices. Efficient storage and indexing of spatio-temporal Big Data are crucial for supporting fast queries. Due to their high write throughput and scalability, distributed NoSQL data stores such as HBase are widely adopted as storage engines in spatio-temporal Big Data systems. These systems require a key-value-based storage model to convert one or a group of spatio-temporal data points into a single key-value pair. However, existing techniques cannot govern an inherent dilemma caused by adding a time dimension within spatial information, that is, we can either optimize for space-preferred or time-preferred queries but not both. In this paper, we propose Cymo, a flexible storage model with query-aware indexing that dynamically adapts to varying query patterns across different spatial regions and evolving query behaviors over time. Our key idea is to partition the spatio-temporal space into multiple subspaces, allowing each subspace to optimize its storage model based on its specific query characteristics. Cymo features a learning model that predicts query patterns for each subspace using historical workloads. Additionally, it introduces a virtual layer that abstracts the heterogeneity of different storage models, providing a unified query interface. This design ensures that storage model variations remain transparent to applications while enabling effective query optimization based on diverse query patterns. We have implemented Cymo on HBase and integrated it into GeoMesa, a representative spatio-temporal Big Data system. Experimental results on real taxi datasets demonstrate that Cymo significantly improves query performance, achieving speedups of 1.53× to 10× compared to GeoMesa. The open-source implementation of Cymo has been released for public access.

To manage massive trajectory data, we propose a novel cloud-based trajectory data management technique, Springbok, which leverages cloud storage to balance performance and monetary costs. Unlike existing key-value, relational, and time series databases, Springbok natively models trajectories as first-class data objects via a spatio-temporal series data model, enabling efficient insertion, query processing, and cost-aware storage management in cloud environments. It further employs an optimized indexing scheme that accounts for both the characteristics of trajectory data and the properties of cloud storage, enabling efficient query execution. In addition, Springbok adopts a tiered cloud storage architecture with carefully designed data layouts, flushing, access, and compression policies, guided by cloud storage performance characteristics and pricing models, to jointly optimize performance and cost. We implemented a fully functional prototype of Springbok supporting core trajectory queries, deletion, and crash recovery, and evaluated it using both real-world and synthetic datasets. The results show that Springbok achieves comparable or better performance than state-of-the-art systems in most cases while significantly reducing monetary costs, demonstrating its effectiveness in balancing performance and cost.

With the rapid growth of mobile devices and applications, a prodigious number of spatio-temporal data are generated constantly. To process these data for applications like traffic forecasting, existing spatio-temporal systems rely on the move-data-to-computation paradigm. However, this approach incurs significant data movement overhead between hosts and storage devices, particularly when a spatio-temporal query is executed on a non-preferred data layout or when the query has a small result size due to its inherent nature. To address this issue, this work introduces Groundhog, an efficient in-storage computing technique designed specifically for spatio-temporal queries, aimed at reducing unnecessary data movement and computations. Groundhog introduces three key designs for efficient in-storage computing: (i) a self-contained and segment-based storage model, which is lightweight for in-storage computing and enables fine-grained pruning for spatio-temporal queries; (ii) a set of fine-grained techniques to optimize query processing inside storage devices for spatio-temporal queries; and (iii) an in-storage-computing-aware query planner, which offloads spatio-temporal queries in a fine-grained manner using a cost-based approach. We implemented Groundhog on real hardware and demonstrated how to apply fine-grained techniques to accelerate various spatio-temporal queries. Extensive experiments conducted on real-world datasets demonstrate that Groundhog achieves significant performance improvements, with latency reductions of up to 81% for widely used spatio-temporal queries compared to host computing solutions.

Mobile devices frequently encounter runtime configuration changes, such as screen orientation adjustments, screen resizing, and language switching. The current Android framework employs a restart-based mechanism to reload resources in response to these changes. Consequently, developers must explicitly manage state preservation and restoration during activity restarts; otherwise, runtime changes may lead to state loss or even application crashes. To address these challenges, we propose RCHDroid, a transparent system-level approach for handling runtime configuration changes in Android applications. Instead of restarting the activity, RCHDroid creates a new activity based on the updated configuration and seamlessly migrates states from the old activity to the new one, while deactivating the old activity. To manage asynchronous tasks still running on the old activity, we introduce an epoch-based migration scheme, which ensures the migration of result events upon task completion. We have implemented a prototype of RCHDroid on real hardware and made the source code publicly available. Experimental results demonstrate that RCHDroid enables existing apps to handle runtime configuration changes without modifications, reducing handling time by 31.59%.