L-Store DB
Database Systems
Image Sources
Sadoghi, Mohammad, et al. 'L-Store: A Real-time OLTP and OLAP System.' arXiv preprint arXiv:1601.04084 (2016). https://arxiv.org/pdf/1601.04084
ECS 165A Course Materials: 'L-Store Storage Architecture.' UC Davis, Winter 2025. https://expolab.org/ecs165a-winter2025/lectures/L-Store%20Storage%20Architecture.pdf
In this project, we reimplemented L-Store, a lineage-based Hybrid Transactional/Analytical Processing (HTAP) database. L-store allows for quick updates via append-only tail pages and fast queries via pointers from read-only base records to the most recent coresponding tail record. To prevent performance degradation from excessive tail records, we implemented a merge process that consolidates base and tail records asynchronously in the background. The merge process creates unused base pages so we implemented an epoch-based base page deallocation process that reclaims space from base pages that are no longer referenced by any tail records. This project was implemented in Python during the Winter 2025 quarter of ECS 165A at UC Davis.
Role
Python Developer
Collaborators
Calvin Lau
James Hu
Eugene Teng
Duration
jan 2025 - mar 2025
Tools
Python
L-Store base and tail records intuition.
Record storage structure with lineage information.
Base record points to tail record via indirection.
On update, base record points to new tail record and new tail record points to old tail record.
Merge process to consolidate base and tail records.
Merge is performed asynchronously in the background.
Epoch-based base page dealocation to reclaim space.