Historical - InnoDB SMP performance

This is a post about InnoDB SMP performance improvements in 200X written around 2008. It was shared at code.google.com which has since shutdown. It describes work done by my team at Google. The big-3 problems for me back then were: lack of monitoring, replication and InnoDB on many-core.

Introduction

This describes performance improvements from changes in the v2 Google patch. While the changes improve performance in many cases, a lot of work remains to be done. It improves performance on SMP servers by:

• disabling the InnoDB memory heap and associated mutex
• replacing the InnoDB rw-mutex and mutex on x86 platforms
• linking with tcmalloc

While tcmalloc makes some of the workloads much faster, we don't recommend its use yet with MySQL as we are still investigating its behavior.

Database reload

This displays the time to reload a large database shard on a variety of servers (HW + SW). Unless otherwise stated, my.cnf was optimized for a fast (but unsafe) reload with the following values. Note that

• innodb_flush_method=nosync is only in the Google patch and is NOT crash safe (kind of like MyISAM). This uses a real data set that produces a 100GB+ database.
• innodb_log_file_size=1300M
• innodb_flush_method=nosync
• innodb_buffer_pool_size=8000M
• innodb_read_io_threads=4
• innodb_write_io_threads=2
• innodb_thread_concurrency=20

The data to be reloaded was in one file per table on the db server. Each file was compressed and reloaded by a separate client. Each table was loaded by a separate connection except for the largest tables when there was no other work to be done. 8 concurrent connections were used.

The smpfix RPM is MySQL 5.0.37 plus the v1 Google patch and the SMP fixes that include:

• InnoDB mutex uses atomic ops
• InnoDB rw-mutex uses lock free methods to get and set internal lock state
• tcmalloc is used in place of glibc malloc
• the InnoDB malloc heap is disabled

The base RPM is MySQL 5.0.37 and the v1 Google patch. It does not have the SMP fixes.

The servers are:

• 8core - the base RPM on an 8-core x86 server
• 4core-128M - the base RPM on a 4-core x86 server with innodb_log_file_size=128M
• 8core-tc4 - the base RPM on an 8-core x86 server with innodb_thread_concurrency=4
• smpfix-128M - the smpfix RPM with innodb_log_file_size=128M
• 4core - the base RPM on a 4-core x86 server
• smpfix-4core - the smpfix RPM on a 4-core x86 server
• smpfix-512M - the smpfix RPM on an 8-core x86 server with innodb_log_file_size=512M
• smpfix - the smpfix RPM on an 8-core x86 server
• onlymalloc - the base RPM on an 8-core x86 server with the InnoDB malloc heap disabled
• smpfix-notcmalloc - the smpfix RPM on an 8-core x86 server without tcmalloc

The x-axis is time so larger is slower.

Sysbench readwrite

Sysbench includes a transaction processing benchmark. The readwrite version of the sysbench OLTP test is measured here using 1, 2, 4, 8, 16, 32 and 64 threads.

The sysbench command line options are:

# N is 1, 2, 4, 8, 16, 32 and 64
 --test=oltp --oltp-table-size=1000000 --max-time=600 --max-requests=0 --mysql-table-engine=innodb --db-ps-mode=disable --mysql-engine-trx=yes --num-threads=N

The my.cnf options are:

innodb_buffer_pool_size=8192M
innodb_log_file_size=1300M
innodb_read_io_threads = 4
innodb_write_io_threads = 4
innodb_file_per_table
innodb_flush_log_at_trx_commit=2
innodb_log_buffer_size = 200m
innodb_thread_concurrency=0
log_bin
key_buffer_size = 50m
max_heap_table_size=1000M
max_heap_table_size=1000M
tmp_table_size=1000M
max_tmp_tables=100

The servers are:

• base - MySQL 5.0.37 without the smp fix
• tc4 - MySQL 5.0.37 without the smp fix, innodb_thread_concurrency=4
• smpfix - MySQL 5.0.37 with the smp fix and tcmalloc
• notcmalloc - MySQL 5.0.37 with the smp fix, not linked with tcmalloc
• onlymalloc - MySQL 5.0.37 with the InnoDB malloc heap disabled
• my4026 - unmodified MySQL 4.0.26
• my4122 - unmodified MySQL 4.1.22
• my5067 - unmodified MySQL 5.0.67
• my5126 - unmodified MySQL 5.1.26
• goog5037 - the same as base, MySQL 5.0.37 without the smp fix

Results for sysbench readonly

Sysbench includes a transaction processing benchmark. The readonly version of the sysbench OLTP test is measured here using 1, 2, 4, 8, 16, 32 and 64 threads.

The sysbench command line options are:

# N is 1, 2, 4, 8, 16, 32 and 64
 --test=oltp --oltp-read-only --oltp-table-size=1000000 --max-time=600 --max-requests=0 --mysql-table-engine=innodb --db-ps-mode=disable --mysql-engine-trx=yes --num-threads=N

The my.cnf options are:

innodb_buffer_pool_size=8192M
innodb_log_file_size=1300M
innodb_read_io_threads = 4
innodb_write_io_threads = 4
innodb_file_per_table
innodb_flush_log_at_trx_commit=2
innodb_log_buffer_size = 200m
innodb_thread_concurrency=0
log_bin
key_buffer_size = 50m
max_heap_table_size=1000M
max_heap_table_size=1000M
tmp_table_size=1000M
max_tmp_tables=100

The servers are:

• base - MySQL 5.0.37 without the smp fix
• tc4 - MySQL 5.0.37 without the smp fix, innodb_thread_concurrency=4
• smpfix - MySQL 5.0.37 with the smp fix and tcmalloc
• notcmalloc - MySQL 5.0.37 with the smp fix, not linked with tcmalloc
• onlymalloc - MySQL 5.0.37 with the InnoDB malloc heap disabled
• my4026 - unmodified MySQL 4.0.26
• my4122 - unmodified MySQL 4.1.22
• my5067 - unmodified MySQL 5.0.67
• my5126 - unmodified MySQL 5.1.26
• goog5037 - the same as base, MySQL 5.0.37 without the smp fix

Concurrent joins

This test runs a query with a join. It is run using concurrent sessions. The data fits in the InnoDB buffer cache. The query is:

select count(*) from T1, T2 where T1.j > 0 and T1.i = T2.i

The data for T1 and T2 matches that used for the sbtest table by sysbench. This query does a full scan of T1 and joins to T2 by primary key.

The servers are:

• base - MySQL 5.0.37 without the smp fix
• tc4 - MySQL 5.0.37 without the smp fix, innodb_thread_concurrency=4
• smpfix - MySQL 5.0.37 with the smp fix and tcmalloc
• notcmalloc - MySQL 5.0.37 with the smp fix, not linked with tcmalloc
• onlymalloc - MySQL 5.0.37 with the InnoDB malloc heap disabled
• my4026 - unmodified MySQL 4.0.26
• my4122 - unmodified MySQL 4.1.22
• my5067 - unmodified MySQL 5.0.67
• my5126 - unmodified MySQL 5.1.26
• goog5037 - the same as base, MySQL 5.0.37 without the smp fix

I only have results for 8 and 16 core servers here. Lower times are better.

With data from the worst case:

Without data from the worst case:

With data from the worst case:

Without data from the worst case:

Concurrent inserts

This test reloads tables in parallel. Each connection inserts data for a different table. Tests were run using 1, 2, 4, 8 and 16 concurrent sessions. The regression for 5.0.37 is in the parser and was fixed by 5.0.54. A separate table is used for each connection. DDL for the tables is:

create table T$i (i int primary key, j int, index jx(j)) engine=innodb

Multi-row insert statements are used that insert 1000 rows per insert statement. Auto-commit is used. The insert statements look like:

INSERT INTO T1 VALUES (0, 0), (1, 1), (2, 2), ..., (999,999);

The servers are:

• base - MySQL 5.0.37 without the smp fix
• tc4 - MySQL 5.0.37 without the smp fix, innodb_thread_concurrency=4
• smpfix - MySQL 5.0.37 with the smp fix and tcmalloc
• notcmalloc - MySQL 5.0.37 with the smp fix, not linked with tcmalloc
• onlymalloc - MySQL 5.0.37 with the InnoDB malloc heap disabled
• my4026 - unmodified MySQL 4.0.26
• my4122 - unmodified MySQL 4.1.22
• my5067 - unmodified MySQL 5.0.67
• my5126 - unmodified MySQL 5.1.26
• goog5037 - the same as base, MySQL 5.0.37 without the smp fix

MySQL 5.0.37 has a performance regression in the parser. This was fixed in 5.0.54. See bug 29921.

Note, lower values for Time are better.

With data from the worst case:

Without data from the worst case:

With data from the worst case:

Without data from the worst case:

Fixing the InnoDB RW-lock

I hope that someone updates the InnoDB Wikipedia page to explain how it came to be. I know it started with Heikki Tuuri. At what point did he get help? Regardless, early InnoDB was an amazing accomplishment and fortunately MySQL saw the potential for it after other large DBMS vendors were not interested.

I enjoyed reading the source code -- it is well written with useful comments. Some of the comments are amusing at this point with references to HW assumptions that were valid in the early and mid 90s. InnoDB had, and might still have, a SQL parser that is used to maintain dictionary tables. Fortunately the code has aged well and been significantly improved by the InnoDB team.

InnoDB and SMP

InnoDB had a big problem in 2005. Commodity SMP hardware was changing from 4-core/1-socket to 8-core/2-socket and InnoDB wasn't ready for it. My memory is that MySQL in 2005 saturated at 10k QPS with sysbench and moving from 1 to 2 sockets hurt QPS.

InnoDB had many problems. A lot of work was done to fix them by the InnoDB team, Percona, Google, Facebook and others. I have forgotten a lot of the details but much is recorded in blog posts and slide decks. The InnoDB rw-lock was a big part of the problem. InnoDB implements a rw-lock and mutex. Both add value -- by adding monitoring for performance and debugging. The rw-lock is also required to support special use cases (I forgot the reasons, but they are valid). Unfortunately both the mutex and rw-lock were lousy on 2-socket servers under contention.

The problem was too much spinning. The rw-lock used the InnoDB mutex to protect its internal state. Both the rw-lock and mutex did some spinning before going to sleep when the lock could not be acquired. This is similar to PTHREAD_MUTEX_ADAPTIVE_NP but the spinning is configurable. The InnoDB rw-lock did spinning on its own and then could do even more spinning when using the InnoDB mutex that guarded its state. There was so much spinning.

The performance impact from this work is explained here.

A Solution

My memory is that Yasufumi Kinoshita implemented the solution first and I learned of that from his presentation at Percona Live. He might have been working at NTT at the time. Inspired by him, my team at Google implemented a similar solution, wrote a Spin model to validate the correctness and then contributed the fix to the InnoDB team who were part of Oracle. The Spin model helped convince the InnoDB team that the code might be correct. I am a huge fan of Spin.

I am proud of the work my team at Google did to fix the rw-lock and it was easy to work with the InnoDB team -- they have always been a great partner for external InnoDB contributors. But I also want to give credit for the person who first showed how to fix the InnoDB rw-lock as he has a long history of making InnoDB better.

Other fixes

Much more has been done to make InnoDB great for many-core servers. Back when the rw-lock was fixed the mutex was also changed to use atomic operations rather than pthread mutex (at least for x86, hopefully for ARM now). My early blog posts mention that and changes to the InnoDB memory heap mutex. I remember nothing about the InnoDB heap mutex. Some of my early docs were published on code.google.com (since shutdown by Google). I archived some of these before the shutdown and will try to republish them.

Still web scale

I am excited to start a new job next week working on performance at MongoDB. I have been a fan of the people and product for years and I look forward to contributing from the inside. The reasons I have been a fan include the rate at which the product has improved, WiredTiger and their contribution to MongoRocks.

I look forward to learning the modern performance analysis tool chain courtesy of Brendan Gregg. His BPF book should be ready soon and there is much content on his web site. When I had to understand off-cpu stalls from IO and mutex contention there wasn't much available 10 years ago, thus PMP was born. While it served me well it is time to move on.

I will continue to blog including performance comparisons between database engines. I look forward to writing about MongoDB, especially WiredTiger internals, but I will exclude MongoDB from the performance comparisons on my blog.

I left FB in January and spent most of the year reading applied math books and being a caregiver. I appreciate the opportunity I had there and the people who helped me -- both managers and many awesome technical contributors. I wouldn't have made it here without Domas.

FB asked one trick question in my job interview -- do I want to be hands on or an architect. I gave the correct answer -- hands on. Small & fast-growing companies need people who are hands-on. More architects will be needed post-IPO when the company gets larger. I interviewed at FB because the MySQL team at Google was ended and I had to find a new project. That was a source of stress but it turned out OK as MySQL at FB was my new project.

MyRocks and RocksDB have been in capable hands for a long time, so I expect more good things from those teams.

The MySQL community has been wonderful to me. My career wouldn't have been possible without the contributions of so many people who made MySQL better. Fortunately, clever people arrive to replace the people who leave and MySQL will continue to improve. Perhaps one day upstream will get a write-optimized storage engine. Dare to dream.

iostat output changes in Ubuntu 18.04

The output format has changed for iostat -kx 1 in Ubuntu 18.04. The changes include reordered columns, renamed columns and new columns. My benchmark scripts scrape this output and use it to compute efficiency metrics so I need to update the scripts to catch up to Ubuntu. I should also update them to deal with future output format changes, or better yet, just scrape /proc/diskstats directly.

Next up - I should determine whether bytes trimmed are still included in bytes written. It will be nice when the bytes trimmed column shows up in iostat but that requires kernel 4.18 or 4.19 per this and with Ubuntu 18.04 (latest LTS) I use 4.15.

This bug report explains the differences.

• rrqm/s and wrqm/s were moved from columns 2, 3 to 6, 7
• avgqu-sz was renamed to aqu-sz
• await was removed - r_await and w_await remain
• avgrq-sz was replaced by rareq-sz and wareq-sz

Throttling writes: LSM vs B-Tree

Reducing response time variance is important for some workloads. This post explains sources of variance for workloads with high write rates when the index structure is an LSM or a B-Tree. I previously wrote about this in my post on durability debt.

Short summary:

1. For a given write rate stalls are more likely with a B-Tree than an LSM
2. Many RocksDB write stalls can be avoided via configuration
3. Write stalls with a B-Tree are smaller but more frequent versus an LSM
4. Write stalls are more likely when the redo log isn't forced on commit
5. The worst case difference between an LSM and B-Tree is larger when the working set isn't cached
6. Life is easier but more expensive when the working set fits in cache
7. Less write amplification saves IO for other uses

Less short summary:

1. Write stalls for an LSM occur when compaction has trouble keeping up with the incoming write rate. The worst stalls occur at write rates that a B-Tree could not sustain. One way to mitigate stalls is to reduce the write rate. Another way is to use an index structure that doesn't support or is inefficient for range scans (see index+log).
2. The cost from configuring RocksDB to avoid write stalls is more CPU overhead on reads as there will be more data in the upper levels of the LSM. I am partly to blame for the default configuration in RocksDB that throttles writes when the LSM tree gets too much data in the L0, L1 and L2. But that configuration can be changed.
3. SQLite4  has a clever LSM designed for systems that don't allow background threads. It implements a pay as you go approach to durability debt. A traditional LSM takes the opposite approach - it defers the IO cost to the background. RocksDB has optional write throttling and work has been done to smooth the impact from it but it is not solved. A B-Tree in the worst-case (buffer pool full & mostly dirty, working set not cached) also implements pay as you go approach.
4. I almost always disable sync-on-commit for benchmarks because I want to observe how the DBMS observes under stress and less commit latency means more writes/second and more IO stress.
5. See item #6 where I argue that it is good to not have the working set cached.
6. A common rule of thumb has been to keep all indexes in cache or all of the working set in cache. That simplifies tuning and makes it easier to avoid performance problems. But that also might force a deployment to use 2X more HW than it needs because NAND flash SSDs are everywhere and the response time difference between reading from RAM and reading from NAND flash might not matter for many applications. But if you are using a DBMS in the cloud that charges by the IO, then keeping the working set in RAM might be a good idea.
7. An LSM usually has less write-amp than a B-Tree. So the IO capacity it saves from that can be used elsewhere to support more read or write transactions.

Worst case behavior

I am wary of faster is better. I prefer nuance but I also know that people don't have time to read long blog posts like this or long performance reports. Here I explain worst case behavior in terms of IO overheads. Worst case behavior isn't the only way to judge an index structure but it helps me to explain performance. Another way is to measure the average amount of IO per transaction (in operations and KB) and treat IO efficiency as important.

I describe worst case behavior for a write operation under a few scenarios. By worst case I mean the largest amount of IO done in the foreground (the thread handling the write) as that determines the response time. I ignore the work done in the background which favors an LSM because that defers more work to the background. For a B-Tree I ignore undo and page splits. The write is a SQL update which is read-modify-write, as opposed to a blind-write like a Put with RocksDB. Finally, I assume the update isn't to an indexed column. The scenarios are:

1. Cached, PK only - working set cached, PK index only
2. Not cached, PK only - working set not cached, PK index only
3. Cached, PK and secondary index - working set cached, PK and non-unique secondary index
4. Not cached, PK and secondary index - working set not cached, PK and non-unique secondary index 

PK only

For the cached, PK only scenario neither an LSM nor a B-Tree do IO in the foreground with the exception of the redo log fsync. Stalls are unlikely for both but more likely with a B-Tree especially when the DBMS storage uses a spinning disk.

• An LSM writes the redo log buffer, optionally syncs the redo log and then does an insert into the memtable. Both memtable flush and Ln:Ln+1 compaction are deferred to background threads. If memtable flush were too slow then there are write stalls until flush catches up to avoid too many memtables wasting memory.
• A B-Tree modifies a page in the buffer pool, writes the redo log buffer and optionally syncs the redo log. If checkpoint were too slow a full redo log can't be rotated until checkpoint catches up and there are write stalls.

For the not cached, PK only scenario the work done in the foreground is 1 IO/update for an LSM and 2 IO/update for a B-Tree. Here a B-Tree uses a pay as you go model.

• An LSM reads a page into the block cache and then repeats the work described in cached, PK only. 
• A B-Tree finds a dirty page to evict, writes that page back to storage, then reads the desired page into that slot in the buffer pool and repeats the work described in cached, PK only.

PK and secondary index

For the cached, PK and secondary index scenario there is approximately twice as much work to be done per update compared to the cached, PK only scenario. Thus stalls are more likely here. But other than the optional redo fsync there is no foreground IO for the LSM and B-Tree.

• An LSM repeats the work explained in the cached, PK only scenario. For the secondary index it does an additional insert to the memtable which is also logged as redo. This can double the demand for compaction.
• A B-Tree repeats the work explained in the cached, PK only scenario. For the secondary index it makes an additional page dirty in the buffer pool. This can double the demand for page write back.

For the not cached, PK and secondary index scenario the foreground IO difference between an LSM and B-Tree is more significant -- 1 IO for the LSM vs 4 IO for the B-Tree -- ignoring the redo log overhead. The IO difference is reduced from 1:4 to approximately 1:2 for a B-Tree like InnoDB that implements a change buffer.

• An LSM does the union of the work described in not cached, PK only and cached, PK and secondary index scenarios. Ignoring the optional redo fsync the cost is 1 read IO for the PK index and no reads for the secondary index because non-unique secondary index maintenance is read-free.
• A B-Tree repeats the work explained in the cached, PK only scenario but this is done for both the PK and secondary indexes. Thus the cost is 2 IOs to write back dirty pages and then 2 IOs to read pages from the PK and secondary indexes into the buffer pool and then make them dirty -- which then requires redo log writes. So the cost for this is 4 IOs ignoring the redo log.

Make writes fast: LSM

Writes can be fast with an LSM because most of the IO cost is deferred but that also increases the need to throttle writes. Life is good as long as that deferred cost can be repaid fast enough, otherwise there will be more response time variance.

Flush and compaction are the deferred cost for an LSM write. Flush means writing the memtable to an SST on storage. Compaction means merging SSTs to move flushed data from the root to leaf of the LSM tree. Compaction costs more than flush. RocksDB can stall writes when compaction doesn't keep up with ingest. Ingest creates durability debt, compaction reduces it and write stalls are there to bound the debt. Write stalls are enabled by default but can be disabled by configuration. Putting a bound on durability debt also puts a bound on read latency by reducing the number of SSTs that can exist in the L0, L1 and L2. So if you want to support extremely high write rates than choose one of: read stalls, write stalls.

Make writes fast: B-Tree

Writes can also be fast with a B-Tree as there are no page reads/writes to/form storage when the working set is cached and background page write back is fast enough. In that case the only IO work in the foreground is the optional redo log fsync.

Page write back is the primary deferred cost for a B-Tree write. Most of my B-Tree experience is with InnoDB which does fuzzy checkpoint. The goal is to flush dirty pages before the current redo log segment gets full. Using larger redo log segments lets InnoDB defer write back for a longer time increasing the chance that more transactions will modify the page -- reducing write amplification and helping performance.

Purge can be an additional deferred cost for a B-Tree write. I use the InnoDB name here as Postgres calls this vacuum. This is the process of reclaiming space from deleted rows that are no longer visible by open MVCC snapshots. The LSM equivalent of purge is checking the open snapshot list during compaction for KV pairs that are not the latest version of a given key to determine whether that version is still needed.

When write back and purge are fast enough then write stalls should be infrequent with a B-Tree. But write back isn't always fast enough. A B-Tree write stall occurs when a write transaction must read a page into the buffer pool prior to modifying that page but 1) the buffer pool is full and 2) write back must be done for a dirty page before the memory can be reused.

Other

A few other comments that didn't have a place above:

• In this post I assume the B-Tree uses no-force, but there is at least one nice OSS B-Tree that uses force.
• Making commit slower is another way to throttle writes and reduce the chance of stalled writes. Examples of this include redo log fsync, semisync or synchronous replication.
• The InnoDB change buffer is a wonderful feature that reduces the IO overhead for write-heavy workloads.
• NAND flash GC stalls are another source of write stalls. I wish more were written about this topic.
• Stalls during TRIM when using an LSM with NAND flash are another source of stalls. I wish there were more TRIM benchmarks. Smart friends tell me that NAND flash devices vary widely in their ability to handle TRIM. And they display different stall behavior when their TRIM capacity has been exceeded. Some of us were spoiled by FusionIO.

The delta+main index structure

A reader of my LSM for analytics blog post suggested I read Fast Scans on Key-Value Stores from VLDB 2017. It is an interesting paper and was part of the effort to build the Tell DBMS and a great PhD thesis. 

Tell might not be an answer for my problem as this was an in-memory DBMS and might have write amplification that is too high for my needs. Regardless, the paper is worth reading and discussing.

Index structure drama

I don't publish reviews for papers that aren't worth reading so keep that in mind for any criticism that follows. The index structure world tends to be low on drama and perhaps more while waiting for the next round of learned index papers.

The big questions for me are:

1. Is delta+main a new index structure?
2. Did SAP Hana pioneer delta+main?

Hana and delta+main

I will start with question 2. The paper states that delta+main was pioneered by SAP Hana (see Hana paper SIGMOD Record from 2012) and then cites a SIGMOD 2015 paper about the Analytics in Motion project. I am not an expert in this area but I suspect that C-Store/Vertica (see VLDB 2005 paper) was another pioneer in this space. 

I started to browse the cited papers. There are too many for me to read or even cite including Fast Updates from VLDB 2012 and Positional Update Handling in Column Stores from SIGMOD 2010. The earliest online paper in this space might be Differential Files from ACM TODS in 1976 and that paper cites even earlier work -- delta+main is great for data stored on tape.

Delta+main index structure

At this point I am only talking about TellStore-Col. I would classify TellStore-Log as index+log.

I am not sure that delta+main is a new index structure. It might be an LSM variant that I have called memtable+L1 where delta is the memtable and main is the L1. Or perhaps it is memtable+L0+L1 where delta is memtable and the L0 while main is the L1. I encountered memtable+L1 systems at least twice. Once at work and then again with Sophia. This is a great approach when database : RAM ratios aren't larger than 10.

However, the index structures used in Tell are more complicated than an LSM. They do clever things to make scans faster, things that you might not do with an LSM -- some fields on data pages aren't write once.

So I won't update the index structures definition just yet, but that doesn't take away from the paper.

Back to the paper

Tell is an in-memory DBMS with three index structures -- TellStore-Log, TellStore-Col and TellStore-Row. I ignore TellStore-Row. Tell supports mixed workloads -- lets call this HTAP for now -- and must be efficient for scans. It solves some of the problems I described in my LSM for Analytics post.

The paper only describes the use of a hash index but cites another Tell paper that explains how a B+Tree can be used. I assume the hash index is only (mostly) for primary key indexes.

TellStore-Log

TellStore-Log is index+log with a hash table for the index. Rows in the log are self-contained. The hash index doesn't have to be checked to determine whether a row in the log is live or visible to a transaction. Thus GC and scans don't have to probe the index which saves CPU overhead.

Rows in the log have fields for valid-from, valid-to and previous. The index points to the latest version of a key and then previous versions can be found by following the previous field. The valid-from and valid-to fields are for MVCC visibility. As part of an update the valid-to field of the previously live version of the row is updated. This confused me until I remembered that this is an in-memory DBMS, the log is in memory and it is possible to update that field in a previously written log page. But this also means that the append-only log isn't write once because the valid-to field can be updated long after the append.

Each DBMS table uses a separate log to improve scan efficiency. TellStore-Log also does clever things to piggyback GC with scans.

TellStore-Col

TellStore-Col is delta+main. It uses two logs for delta (update-log and insert-log, delete is an update) and then PAX for the main store. There is still one hash index that points to rows in update-log, insert-log and the main store.

Row visibility can be treated as a predicate to evaluate. Assume there are N rows on a page and K predicates. There can be K bitmaps, one per predicate, to indicate matching rows and then one more bitmap to indicate the rows that are visible.

Multiple versions of a row can be in the main store and would be adjacent in a page. There is also a newest pointer per key in the main store that points can point into the update log. The newest pointer would get changed each time a row with that key is appended to the update-log. Rows in the main store also have valid-from and valid-to fields to determine MVCC visibility. When the latest version of a key is in the main store and the key gets updated (appended to the update-log) then the valid-to field in the main store page would also get updated. I assume these changes to main store pages are done in place given that this is an in-memory DBMS.

Multiple versions of a key in the update log are linked via the previous field. But the oldest version of a key in the update log does not point to versions in the main store.

Eventually GC is done for pages in the main store and that uses copy-on-write in contrast to the changes mentioned above that are done in place.

The structure of pages in the main store support efficient scans. Keys that are not visible per MVCC can be excluded via the valid-from and valid-to fields. Keys that have the visible version in the update-log can be found by following the newest pointer from the main store page to the update-log. There is no need to do a merge, like an LSM requires, between rows from the main store and update-log. There is no need to probe the update-log for every key read from the main store. There is no need to scan the update-log as it gets probed on demand.

A scan would also have to read from the insert-log. But such rows are new, so there is no need to merge that data with another data structure.

Always be upgrading

On the production DBMS side I want to provide a high QoS and a stable environment helps to achieve that. Upgrades are done slowly with much testing. Upgrades include moving to a new compiler toolchain or new library version.

On the security side people don't want libraries with known security problems to be used in production. This leads to a push to always be upgrading (ABU) and this is justified when the expected value of ABU exceeds the expected cost. Alas this will be hard to figure out. I assume the expected cost can be estimated. I am skeptical there can be an estimate of the expected value.

The expected value of ABU is:

cost(security-event) X probability(security-event)

I assume it is possible to estimate the cost of a security event but will be much harder to estimate the probability. It would help if more vendors were to publish full incident reports. My guess is that old library version won't be near the top of the list of root causes, but this is not my area of expertise.

The cost of ABU is easier to quantify -- count debugging time, testing time and down time from all teams that will be upgrading frequently. Examples of things that can go wrong include Postgres depends on glibc locale, ext-4 performance changes for O_DIRECT and many more, but I will be lazy and many of the problems I experienced weren't reported in public.