Accumulating and flushing mutations in a column store
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.
1. A method for a distributed database system, the method comprising:
in response to an insert operation for a database table, storing a new row in a first in-memory store, wherein the first in-memory store is configured to flush to an on-disk store after a flushing criteria is reached;
prior to the first in-memory store flushing the new row to the on-disk store, storing a separate mutation record linked to the new row that is stored in the first in-memory store, in response to a second mutation operation that is specified for the new row; and
after the flushing criteria is reached, performing:
modifying the new row stored in the first in-memory store based on applying the separate mutation record to the new row; and
flushing (i) the modified new row to one or more base data files in the on-disk store, and (ii) the separate mutation record associated with the new row to one or more delta files in the on-disk store,
wherein the first in-memory store and the on-disk store are configured for disjoint row storage such that a given row of the database table exists in one of a row set (RowSet) in the first in-memory store or a RowSet in the on-disk store.
2. The method of claim 1 , wherein the separate mutation record is flushed to the one or more delta files with a timestamp that is associated with the second mutation operation.
3. The method of claim 1 , further comprising:
in response to a third mutation operation that specifies a flushed row stored in the on-disk store, storing a mutation record in a second in-memory store that is associated with the on-disk store, wherein the second in-memory store is configured to flush to the one or more delta files in the on-disk store after a second flushing criteria is reached.
4. The method of claim 1 ,
wherein the one or more base data files and the one or more delta files are immutable.
5. The method of claim 1 ,
wherein the database table includes (1) a number of columns, including a primary key (PK) column, and (2) a number of rows, each row having a unique PK stored in its corresponding PK column, wherein the number of rows are divided into a plurality of tablets, each tablet divided into a number of RowSets,
wherein the RowSets are disjoint with respect to a stored key so that any given key is active in at most one RowSet, and
wherein, for a given PK, at most one RowSet contains an active copy of a row with the given PK.
6. The method of claim 1 , wherein the database table remains readable by a client of the database table during the flushing of the modified new row and the flushing of the separate mutation record.
7. The method of claim 1 , further comprising:
subsequent to flushing the modified new row, storing a new set of rows of the database table in the first in-memory store.
8. The method of claim 1 , further comprising:
processing a time-travel query for the modified new row in the on-disk store based on accessing the separate mutation record in the one or more delta files in the on-disk store.
9. A computing system comprising:
one or more processors; and
one or more memories storing instructions that, when executed by the one or more processors, cause the computing system to perform a process comprising:
in response to a first insert operation for a database table, storing a new row in a first in-memory store, wherein the first in-memory store is configured to flush to an on-disk store after a flushing criteria is reached;
prior to the first in-memory store flushing the new row to the on-disk store, storing a separate mutation record attached to the new row that is stored in the first in-memory store, in response to a second mutation operation that is specified for the new row; and
after the flushing criteria is reached, performing:
modifying the new row stored in the first in-memory store based on applying the separate mutation record to the new row; and
flushing (i) the modified new row to one or more base data files in the on-disk store, and (ii) the separate mutation record associated with the new row to one or more delta files in the on-disk store,
wherein the first in-memory store and the on-disk store are configured for disjoint row storage such that a given row of the database table exists in one of a row set (RowSet) in the first in-memory store or a RowSet in the on-disk store.
10. The computing system of claim 9 , wherein the process further comprises:
determining that a third mutation operation specifies a flushed row that is stored in the on-disk store based on a Bloom filter for a set of primary keys present in the on-disk store; and
storing a mutation record for the third mutation operation in a second in-memory store instead of the first in-memory store based on the third mutation operation specifying the flushed row stored in the on-disk store, wherein the second in-memory store is configured to flush to the one or more delta files in the on-disk store after a second flushing criteria is reached.
11. The computing system of claim 10 , wherein the process further comprises:
chunking available Bloom filters into pages corresponding to ranges of rows;
creating an index for the pages using an immutable B-tree; and
storing the pages and the index in a server-wide least recent used (LRU) page cache.
12. The computing system of claim 9 ,
wherein the separate mutation record attached to the new row is implemented as a singly linked list,
wherein the singly linked list includes a mutation head that points to a given mutation node, and a next mutation pointer in the given mutation node points to a subsequent mutation node.
13. A non-transitory computer-readable medium storing instructions that, when executed by a computing system, cause the computing system to perform a process comprising:
in response to a first insert operation for a database table, storing a new row in a first in-memory store, wherein the first in-memory store is configured to flush to an on-disk store after a flushing criteria is reached;
prior to the first in-memory store flushing the new row to the on-disk store, storing a separate mutation record associated with the new row that is stored in the first in-memory store, in response to a second mutation operation that is specified for the new row; and
after the flushing criteria, performing:
modifying the new row stored in the first in-memory store based on applying the separate mutation record to the new row; and
flushing (i) the modified new row to one or more base data files in the on-disk store, and (ii) flushing the separate mutation record associated with the new row to one or more delta files in the on-disk store,
wherein the first in-memory store and the on-disk store are configured for disjoint row storage such that a given row of the database table exists in one of a row set (RowSet) in the first in-memory store or a RowSet in the on-disk store.
14. The non-transitory computer-readable medium of claim 13 , wherein the process further comprises:
performing a minor delta compaction operation that reduces a number of one or more delta files in the on-disk store by merging the one or more delta files together, without updating the one or more base data files in the on-disk store.
15. The non-transitory computer-readable medium of claim 13 , wherein the separate mutation record is a REDO record, and wherein the process further comprises:
performing a major delta compaction operation that migrates REDO records to UNDO records and updatess the one or more base data files in the on-disk store.
16. The non-transitory computer-readable medium of claim 13 , wherein the process further comprises:
performing a merging compaction operation that merges together a number of RowSets, in one or more on-disk stores, that overlap in range.