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 implementing write operations in a distributed database system that supports multi-version concurrency control (MVCC), the database configured to store structured data in a columnar manner, wherein the write operations include one or more of: an insert operation, an update operation, or a delete operation, the database including a database table that 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 row sets (RowSets), the method comprising:
implementing a first in-memory store configured to store newly inserted rows from an insert operation until one or more criteria for flushing the newly inserted rows are reached and the newly inserted rows are flushed to a persistent storage;
attaching an update operation or a delete operation to an applicable row in the newly inserted rows in the first in-memory store to form a REDO record for the applicable row, when the applicable row still exists in the newly inserted rows in the first in-memory store;
implementing an on-disk storage to receive the newly inserted rows flushed from the first in-memory store, wherein the newly inserted rows flushed to the on-disk storage include (1) a base data and (2) a delta file; and
upon flushing the newly inserted rows, including the attached update operation or the attached delete operation to the applicable row, to the on-disk storage:
storing the newly inserted rows, after having their respective REDO records applied thereto, in the base data, and
storing a history of the newly inserted rows to the delta file as a set of UNDO records.
2. The method of claim 1 , further comprising:
upon flushing the newly inserted rows to the on-disk storage, flushing the REDO records to a delta file indicating one or more timestamps at which one or more rows have been deleted.
3. The method of claim 1 , further comprising:
implementing a second in-memory store configured to store mutations to the base data until one or more criteria for flushing the mutations are reached and the mutations in the second in-memory store are flushed to the delta file or a new delta file,
wherein the mutations are in a format of a REDO record and are originated from an update operation or a delete operation to an applicable row in the base data.
4. The method of claim 3 , wherein the mutations are received after the flushing.
5. The method of claim 3 , wherein a separate in-memory store is implemented for every available set of rows flushed to the on-disk storage.
6. The method of claim 1 , wherein the base data and all delta files are immutable.
7. The method of claim 1 , wherein the number of row sets that each tablet is divided into is variable.
8. The method of claim 1 , wherein the RowSets are disjoint with respect to a stored key so that any given key is active in at most one RowSet.
9. The method of claim 1 , wherein, for a given PK, at most one RowSet contains an active copy of a row with the given PK.
10. The method of claim 1 , wherein the first in-memory store remains readable by a client of the database during the flushing.
11. The method of claim 1 , further comprising:
including a Bloom filter for a set of PKs present in the on-disk storage.
12. The method of claim 11 , further comprising:
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.
13. The method of claim 1 , further comprising:
storing a PK boundary including a minimum PK and a maximum PK present in the on-disk storage; and
indexing the RowSets in the on-disk storage using an interval tree to reduce a number of RowSets in the on-disk storage needed to consult on a given PK lookup or range scan.
14. The method of claim 1 , wherein each column in the newly inserted rows flushed to the on-disk storage is separately written to the persistent storage as a single contiguous block of data.
15. The method of claim 1 , further comprising:
performing a minor delta compaction operation that reduces a number of applicable delta files by merging the applicable delta files together, without updating the base data.
16. The method of claim 1 , further comprising:
performing a major delta compaction operation that migrates REDO records to UNDO records, and updates the base data.
17. The method of claim 16 , wherein updating the base data comprises creating new immutable base data blocks, and atomically replacing old data blocks with the new base data blocks.
18. The method of claim 1 , further comprising:
performing a merging compaction operation that merges together RowSets that overlap in range.
19. The method of claim 1 , wherein an update operation to a target row comprises:
utilizing an interval tree that contains a PK boundary for all available RowSets in the on-disk storage to locate a target RowSet in the on-disk storage that possibly includes the target row;
utilizing a Bloom filter associated the target RowSet in the on-disk storage to determine if the target row is potentially present;
searching, within the target RowSet in the on-disk storage, for the target row to determine if the target row is actually present;
upon determining that the target row is actually present in the target, Rowset in the on-disk storage, determining an offset for the target row; and
entering, using the offset, a new REDO record into a second in-memory store associated with the target RowSet in the on-disk storage.
20. The method of claim 1 , wherein the REDO record for each newly inserted row in the first in-memory store is implemented as a singly linked list.
21. The method of claim 20 , 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.
22. The method of claim 1 , wherein each mutation is tagged with a transaction identifier (TXID) or a timestamp of the mutation, and wherein the TXID is associated with changes to the data.
23. The method of claim 1 , wherein the MVCC limits read operations to observing the write operations that have been committed, and wherein the MVCC places no lock when read operations are performed.
24. The method of claim 1 , further comprising:
upon flushing the newly inserted rows to the on-disk storage:
applying REDO records to the newly inserted rows before storing the newly inserted rows in the base data.