Accumulating and flushing mutations in a column store
Inventors
Assignees
Publication Number
US-12222915-B2
Publication Date
2025-02-11
Expiration Date
2036-05-07
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Abstract
Columnar storage provides many performance and space saving benefits for analytic workloads, but previous mechanisms for handling single row update transactions in column stores suffer from poor performance. A columnar data layout facilitates both low-latency random access capabilities together with high-throughput analytical access capabilities, simplifying Hadoop architectures for use cases involving real-time data. In disclosed embodiments, mutations within a single row are executed atomically across columns and do not necessarily include the entirety of a row. This allows for faster updates without the overhead of reading or rewriting larger columns.
Core Innovation
The invention provides a storage engine for structured data employing a columnar layout that enables both low-latency random access and efficient analytical access. This columnar design facilitates a combination of sequential reads and writes alongside random reads and writes, simplifying architectures such as Hadoop for real-time data applications. Mutations within a single row are executed atomically across columns, and updates do not require rewriting the entire row, allowing faster updates with less overhead.
The problem solved addresses the inefficiencies in prior database systems where update transactions in column stores suffer from poor performance due to excessive read I/O on every column in a row, regardless of how many columns actually change. Existing positional update tracking reduces some cost but adds logarithmic overhead to insert operations. The invention overcomes these drawbacks by accumulating mutations in-memory linked to rows before flushing them to disk, thereby optimizing both update and insertion performance while maintaining efficient analytical queries.
Claims Coverage
The patent includes multiple independent claims covering methods, systems, and computer-readable media for managing mutations in column-stored database tables. The main inventive features cover mutation storage, flushing, data layout, and compaction techniques.
Hybrid in-memory and on-disk mutation storage with atomic mutation application
Storing new rows in an in-memory store with separate mutation records linked to these rows before flushing, performing atomic modification of these rows by applying mutations, and then flushing the modified rows to base data files and mutations to delta files on disk, ensuring disjoint row storage across the in-memory and on-disk stores.
Timestamped mutation records with transactional tracking
Flushing separate mutation records to delta files with timestamps associated with mutation operations, enabling multi-version concurrency control and precise tracking of mutations over time.
Mutation recording for flushed rows using a second in-memory store
Upon mutations specifying rows already flushed to disk, storing mutation records in a distinct in-memory store tied to the on-disk data, which is flushed separately to delta files after reaching a flushing threshold.
Immutable base data and delta files for consistency
Ensuring that base data files and delta files stored on disk are immutable to maintain consistency and enable efficient versioning and compaction processes.
Row and key partitioning into tablets and disjoint RowSets
Dividing database tables into tablets and RowSets such that RowSets are disjoint with respect to stored keys, guaranteeing that any given key is active in at most one RowSet, enabling efficient mutation and query operations.
Concurrent read capability during flushing operations
Allowing the database table to remain readable by clients during flushing of modified rows and associated mutation records to disk, supporting continuous availability.
Support for repeated row insertion and mutation cycles
Enabling continued insertion of new rows into the in-memory store subsequent to flushing prior modified rows, supporting ongoing data updates.
Time-travel query support via delta files
Processing time-travel queries by accessing separate mutation records (delta files) in the on-disk store, allowing queries to reconstruct historical states of the data.
Bloom filter accelerated mutation routing
Using Bloom filters chunked and indexed by immutable B-trees and cached in a server-wide LRU page cache to efficiently determine the location (in-memory or on-disk) of keys for mutation operations.
Linked list implementation of mutation records
Implementing mutation records attached to new rows as singly linked lists with mutation heads and next-mutation pointers to track mutation sequences efficiently.
Delta compaction operations including minor and major compactions
Supporting background delta compaction operations that merge delta files to reduce read overhead without rewriting base data (minor), or that migrate REDO records to UNDO records while updating base data files (major).
Merging compaction of overlapping RowSets
Performing merging compactions that combine multiple overlapping RowSets on disk to maintain efficient query performance and reduce lookup cost.
The claims comprehensively cover a storage architecture and method combining in-memory mutation accumulation linked to rows with immutable on-disk base data and delta files. This includes mechanisms for atomic mutation application, transaction timestamping, efficient mutation routing via Bloom filters, and compaction operations that optimize read performance while ensuring consistency and supporting multi-version concurrency control.
Stated Advantages
Faster updates without the overhead of reading or rewriting entire rows or larger columns.
Simultaneous support for low-latency random access and high-throughput analytical access in a single storage layer.
Efficient enforcement of primary key uniqueness with minimal read I/O.
Continuous read availability during flush operations and concurrent mutation application.
Optimized read performance through delta compactions that reduce overhead of accumulated mutations.
Support for time-travel queries and multi-version concurrency control enabling snapshot and historical querying.
Reduction of expensive key-based merges by leveraging numeric row IDs for mutation applies.
Documented Applications
Real-time data applications including monitoring market data, fraud detection/prevention, risk monitoring, predictive modeling/recommendation, and network threat detection.
Use with Hadoop architectures, complementing systems like HDFS and HBase by enabling real-time analytic workloads on changing data.
Interested in licensing this patent?