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.

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.

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.

Massive spatio-temporal data are continuously generated by various moving objects. To process these data for applications such as traffic forecasting, existing spatio-temporal systems all employ the move-data-to-computation paradigm. However, this approach suffers from significant data movement overhead between hosts and drives. 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 a real hardware board. 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.

Massive trajectory data are continuously generated with the rapid development of location-acquisition devices such as vehicles and smartphones. To provide services for applications such as mobility pattern discovery, how to manage such gigantic trajectory data to support queries in an efficient and cost-effective way becomes vitally important. Due to its low cost, large storage capacity, and reliability, cloud storage such as S3 becomes a new paradigm for storing gigantic data and is used in some general-purpose data management systems to strike a balance between performance and monetary costs. However, few systems exploit the inherent features of cloud storage for trajectory data. In this paper, we propose a novel cloud-based trajectory data management technique, called Springbok, to bridge the gap between massive trajectory data and cloud storage. Springbok is designed to address several key issues related to cloud-based trajectory data management. First, Springbok treats trajectories as first-class citizens using a new spatio-temporal series data model that can benefit insertion, query processing, and storage management in the cloud. Second, a holistic indexing scheme that considers features of trajectory data and cloud storage is designed to facilitate efficient queries. Third, based on performance features and billing models of cloud storage, we design effective data layouts for trajectory data and corresponding data flushing and access policies in a tiered cloud storage architecture for performance improvement and cost reduction. We have implemented a fully functional prototype of Springbok and conducted evaluations using both real-world and synthetic datasets, demonstrating its ability to achieve a good tradeoff between performance and monetary costs. Springbok has been open-sourced for public access.

For enterprise storage systems, users' directory/file and IO access traces are critical for fine-tuning and new designs. However, once these systems are deployed, only trace features with small sizes are allowed to be sent back to vendors. Therefore, it is crucial to develop effective techniques for highly compressed feature extraction and feature-based high-fidelity trace regeneration. Existing works primarily focus on I/O trace modeling and regeneration without considering the directory/file access information. In this paper, we propose a new technique, called Sketcher, that can sketch massive traces into highly compressed “joint features” with both directory/file and I/O characteristics, and then based on these features regenerate high-fidelity traces with a learning-based approach. For trace feature extraction, one key idea is to divide traces into multiple distance-associated segments, where each segment contains all files and IO accesses operating under the same directory and the differences between segments are represented as displacement of segment inside the directory tree. A dynamic weight scaling technique is proposed to further compress features considering feature criticality and the size quota, thereby achieving high compression ratios with critical characteristics (e.g., abnormal IO access patterns). For trace regeneration, a new learning-based RNN model is proposed to regenerate high-fidelity traces from extracted features based on sampling directory trees. We have implemented a fully functional prototype based on typical enterprise storage systems and evaluated Sketcher with real applications and benchmarks on Huawei OceanStor Dorado storage server. Results show that Sketcher can effectively extract features with marginal runtime overheads while achieving compression ratios up to 15.2K and regenerating high-fidelity traces.

The Log-Structure Merged tree (LSM-tree) based key-value (KV) store has been widely adopted as the storage engine for blockchain systems, such as Ethereum, in which blockchain data are uniformly transformed into randomly distributed KV items for persistence. However, blockchain semantics are ignored during this process, making the blockchain storage suffer from heavy read/write amplification problems. Moreover, as the Ethereum network scales up, tremendous data further exacerbates its storage burden. Until now, most studies have focused on sharding, data archiving, decentralized distributed storage, etc., to mitigate the burden of the storage layer. However, the incompatibility between Ethereum semantics and the characteristics of the storage engine is ignored. In this paper, we present ChainKV, a new semantics-aware storage paradigm to improve the storage management performance for the Ethereum system. Firstly, based on Ethereum blockchain semantics, ChainKV separately stores different types of data in multiple storage zones in the KV store to mitigate the read/write amplification problem. Secondly, following the mechanism of the verification process in the authenticated data structure (ADS), a new ADS data transformer is proposed to exploit the data locality when persisting ADS. Moreover, a new space gaming caching policy is adopted to coordinate the cache space management for two independent storage zones. Finally, we propose an optional lightweight node crash recovery mechanism to eliminate functional redundancy between the Ethereum protocol and the storage engine. The experimental results indicate that ChainKV outperforms the prior Ethereum systems by up to 1.99× and 4.20× for synchronization and query operations, respectively

Timeseries management systems play an important role in IoT and performance monitoring. As the data volume scales up, absorbing data memory efficiently with high throughput becomes a growing requirement for timeseries management systems. However, the designs of the existing systems, especially the in-memory data structures, suffer from two issues. First, they suffer from the trade-off between memory efficiency and performance. Second, they are not scalable because of lock contention where they cannot benefit from parallel insertion and querying. In this paper, we propose ForestTI, a scalable inverted-index-oriented timeseries management system where the balance point between memory efficiency and performance can be flexibly adjusted under the increasing memory pressure. First, we present a two-level inverted index, which is scalable with optimistic lock coupling, and its internal structure can be gradually converted to more memory efficient representations. Second, we propose a two-level pointer swizzling mechanism to actively swap out the cold posting lists and in-memory timeseries objects as the number of timeseries increases. Finally, we further optimize the on-disk data structures (i.e. write-ahead logs and LSM-tree) to adapt to the high insertion throughput from the in-memory components. We prototype ForestTI with C++ from scratch, and compared to the storage engine of Prometheus, ForestTI achieves 1.79x higher insertion throughput, 52.1% lower query latency, and 56.9% lower memory occupation. We have released the open-source code of ForestTI for public access.

LSM-based key-value stores have been leveraged in many state-of-the-art data-intensive applications as storage engines. As data volume scales up, a cost-efficient approach is to deploy these applications on hybrid cloud storage with hot/cold separation, which splits the LSM-tree into two parts and thus brings new challenges on how to split and how to close the significant performance gap between these two parts. Existing LSM-tree key-value stores mainly focus on the optimizations of local storage, which incurs sub-optimal performance when directly applied to hybrid storage. In this paper, we present MirrorKV for efficient compaction and querying on hybrid cloud storage. First, based on the capacities of fast and slow cloud storage, MirrorKV vertically separates hot/cold data of different levels stored in different cloud storage with different compaction mechanisms. To avoid compaction in slow storage being the bottleneck of the write path, MirrorKV proposes a novel virtual split to only compact the metadata during the compaction, which postpones the actual compaction until it reaches deep enough levels. Second, to reduce accessing slow storage during querying, MirrorKV horizontally separates keys and values into two mirrored LSM-trees to differentiate caching priorities; the maintained tree structures preserve the data locality for efficient sequential reading without incurring the overhead of the traditional key-value separation solutions. Finally, MirrorKV leverages cached data to guide the compaction where the hot data is retained in the fast storage while the cold data is compacted to deeper levels in slow storage. Compared with RocksDB-cloud, MirrorKV achieves 2.4× higher random insertion throughput, 29% higher random read throughput, and 99% less compaction time.

Timeseries management systems have attracted considerable attention during the last decade with the rise of IoT and performance monitoring. With the rapidly increasing data scale in the production environment, deploying timeseries management systems on cloud with cloud storage is a natural trend because of its high availability, reliability, and scalability. However, the state-of-the-art designs are not tailored for cloud environments; they suffer from the limited number of timeseries a single compute node can handle because of the imbalanced resource usage.

In recent years, Log-Structured Merge Tree (LSMtree) 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 LSMtree 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 IOs across the levels in the tree. In this paper, we present a novel scheme, called Log-assisted LSM-tree (L2SM), to fundamentally address 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 have prototyped the L2SM structure based on LevelDB. Our evaluation with the YCSB benchmark shows promising results by reducing the amount of disk IOs by up to 40.2%, increasing the throughput by up to 67.4%, and decreasing the average latency by up to 40.1%.

Similarity computation is a core subroutine of many mining tasks on multi-dimensional data, which are often massive datasets at high dimensionality. In these mining tasks, the performance bottleneck is caused by the `memorywall' problem as substantial amount of data needs to be transferred from memory to processors. Recent advances in non-volatile memory (NVM) enable processing-in-memory (PIM), which reduces data transfer and thus alleviates the performance bottleneck. Nevertheless, NVM PIM supports specific operations only (e.g., dot-product on non-negative integer vectors) but not arbitrary operations. In this paper, we tackle the above challenge and carefully exploit NVM PIM to accelerate similarity-based mining tasks on multi-dimensional data without compromising the accuracy of results. Experimental results on real datasets show that our proposed method achieves up to 10.5x and 8.5x speedup for state-of-artkNN classification andk-means clustering algorithms, respectively.

Performance-monitoring timeseries systems such as Prometheus and InfluxDB play a critical role in assuring reliability and operationally. These systems commonly adopt a column-oriented storage model, by which timeseries samples from different time-series are separated, and all samples (with both numeric values and timestamps) in one timeseries are grouped into chunks and stored together. As a group of timeseries are often collected from the same source with the same timestamps, managing timestamps and metrics in a group manner provides more opportunities for query and insertion optimization but posts new challenges as well. Besides, for performance monitoring systems, to support better compression and efficient queries for most recent data that are most likely accessed by users, huge volumes of data are first cached in memory and then periodically flushed to disks. Periodic data flushing incurs high IO overhead, and simply discarding flushed data, which can still serve queries, not only is a waste but also brings huge memory reclamation cost. In this paper, we propose Heracles which integrates two techniques - (1) a new storage model, which enables efficient queries on compressed data by utilizing the shared timestamp column to easily locate corresponding metric values; (2) a novel two-level epoch-based memory manager, which allows the system to gradually flush and reclaim in-memory data while unreclaimed data can still serve queries. Heracles is implemented as a standalone module that can be easily integrated into existing performance monitoring timeseries systems. We have implemented a fully functional prototype with Heracles based on Prometheus tsdb, a representative open-source performance monitoring system, and conducted extensive experiments with real and synthetic timeseries data. Experimental results show that, compared with Prometheus, Heracles can improve the insertion throughput by 171%, and reduce the query latency and space usage by 32% and 30%, respectively, on average. Besides, to compare with other state-of-the-art storage techniques, we have integrated LevelDB (for LSM-tree-based structure) and Parquet (for column stores) into Prometheus tsdb, respectively, and experimental results show Heracles outperform these two integrations. We have released the open-source code of Heracles for public access.