Cedar: A Columnar LSM-Engine for Temporal Property Graphs
TL;DR
Cedar is designed and demonstrated, an LSM-tree-based columnar engine for temporal graphs that unifies vertices and edges as first-class temporal events into an append-only stream, transforming complex graph updates into a sequence of atomic records.
Abstract
Interactions among real-world entities can be modeled using temporal graphs, which evolve dynamically over time. Ensuring efficient storage and queries in graph databases is challenging. In this paper, we design and demonstrate Cedar, an LSM-tree-based columnar engine for temporal graphs. Firstly, Cedar unifies vertices and edges as first-class temporal events into an append-only stream, transforming complex graph updates into a sequence of atomic records. Each record is encoded into a compact 32-byte fixed-length key, enabling sequential writes that mitigate random I/Os and storage overhead. Secondly, to provide native support for this temporal stream, Cedar extends the LSM-tree's SkipList with a temporal version chain, enabling the system to handle temporal graph updates without incurring the cost of external management. Thirdly, to effectively store a query temporal property graphs, Cedar transitions row-oriented events into a Zone-Columnar on-disk layout. This layout optimizes storage density via vertical compaction while leveraging columnar efficiency to accelerate temporal-analytical queries. Finally, we demonstrate Cedar's efficacy through a deployment scenario on real-world power grid, showcasing substantial improvements in ingestion throughput and temporal query latency.