Compared to what?

It is common to share big numbers for web-scale database deployments. I do it frequently in presentations. I am not alone in this practice. Is is easy to get large values for QPS with web-scale OLTP (small data). The same is true for database size and rows read rates with web-scale data warehousing (big data).

I hope that So What? is the first reaction when these big numbers are shared. Big numbers only mean that a lot of hardware has been used. Context is what makes these big numbers more or less interesting. Note that I am not saying this to take away from the work done by my peers. I have been fortunate to work with extremely talented teams.

Compared to what? is another useful response. When considering stock mutual funds we look at the performance of the fund relative to a benchmark such as S&P 500. When considering database performance it helps to understand whether an alternative product would have done better. We usually don't have an answer for this because it can be too expensive to do the comparison, but is still something to keep in mind.

We aren't in the business of growing QPS, database size and rows read rates. We are in the business of answering questions with efficiency and quality of service. The goals include increasing availability, reducing response time, reducing response time variation and doing more work with less HW. Details about these goals are less likely to be shared -- for business reasons and sometimes because the data isn't collected -- so the context required to appreciate the big numbers might always be missing.

Fast index create

What is a fast way to create secondary indexes for a write-optimized database engine?

Back in the day the only way to create a secondary index for InnoDB was via incremental maintenance. Insert, update and delete statements would maintain secondary indexes as needed. The CREATE INDEX command for a secondary index would make a copy of the table, define all indexes (primary and secondary) and then scan the source table in PK order and insert rows from the scan into the copy table while maintaining secondary indexes after each insert.  In most cases the result from this is a secondary index subject to changes in a random sequence. That means the secondary index is fully fragmented immediately after index create and there was no way to defragment a secondary index. Fragmentation is bad as it means you are wasting space and using about 1.5X the space for the index compared to the index without fragmentation.

Today InnoDB is able to create a secondary index in the expected way via scan/sort/write and fragmentation is much better. The expected way is to scan the base table or another secondary index to get the columns for the new index, sort those columns and then write out the secondary index in key order. I will ignore the complexity of logging to allow other changes concurrent with the index create. Not only does this reduce fragmentation but it also reduces random IO -- the index is written sequentially and there are no random disk reads to get secondary index leaf pages during the read-modify-write cycle of an update for a b-tree.

The best-practice for fast index creation can change for a write-optimized database engine when the engine supports a blind-write in addition to a read-modify-write internally. By this standard a b-tree is not write-optimized whether it is update-in-place like InnoDB or copy-on-write like WiredTiger. Updates and inserts with a b-tree must read the old copy of the page, modify it and then eventually write the page back to storage. There is always a read before the write even with the InnoDB change buffer where the read is deferred. But with an LSM like RocksDB or WiredTiger and probably with a fractal tree like Tokutek updates can be done as blind-writes in many cases like when the secondary index to be updated is not unique. By blind-write I mean there isn't a read before the write. This means that the random reads that make incremental index maintenance for a b-tree slow can be avoided with a write-optimized engine. The random writes can also be avoided assuming the engine really is write-optimized when flushing changes to storage.

It might take some time for us to learn that the rules have changed. It might also take time for the rules to really change when there are robust write-optimized engines available for MySQL and MongoDB.

Update - today I learned the RocksDB storage engine for MongoDB doesn't do reads for non-unique secondary index maintenance.

A few possibly true facts about indexes in MongoDB, RocksDB and WiredTiger

These are probably correct as of April 1, 2015. They might not be correct next year. We have a lot of work to do to explain the storage engines available in MongoDB 3. I welcome corrections.

• The primary key index is not clustered in MongoDB for RocksDB or WiredTiger. I assume this is a limitation of the storage engine API and hope a clustered PK index is supported in the future. The PK index is a map from PK columns to RecordId and (I assume) RocksDB and WiredTiger have a clustered index on RecordId and the documents are in the leaf nodes of the RecordId index. The impact from not having a clustered PK index include:
• Much less RAM is required to cache the PK index because it is not clustered but if the table is huge and you want to guarantee that at most one disk read is required for a point query then a non-clustered PK requires much more RAM then a clustered PK. With the clustered PK you only need the level above the leaf in RAM and that only requires 1 (key, block pointer) pair per block in the leaf level. With the non-clustered PK you need one (key, block pointer) pair per row in the table.
• For RocksDB and WiredTiger going from RecordId to the document requires searching an index (b-tree or LSM for WT, LSM for RocksDB). An index search is not required for mmapv1 as the RecordId is a filename + offset in that case. This might make read-mostly workloads on a cached working set faster with mmapv1.
• If values adjacent in the PK index are not adjacent in the RecordId index then a scan in PK order can do a lot of random IO as it moves around in the RecordId index.
• The WiredTiger b-tree can use prefix compression for indexes and block compression for data. I think this means that block compression is used for the leaf nodes of the RecordId index. I am not sure if it is also used for the leaf nodes of the other indexes. I guess that only prefix compression is used for the non-leaf nodes of all indexes.
• With RocksDB we need to be careful about terminology. With leveled compaction the block-based table format is used for MongoDB and most of the data in an LSM level is from pages, and then the block index and bloom filter. This is true for secondary indexes, primary indexes and the RecordId index. Currently all data is in one column family and indexes are distinguished by using the index ID as the prefix of the key given to RocksDB but we can ignore that for now. Lets also ignore bloom filters and just focus on pages and the block index. The interesting details are:
• There is one key per page in the block index so this is unlikely to use much space compared to the pages. 
• Key value pairs are stored in the pages in key order and prefix compression is done for them. Prefix compression is not done for the block index. Logically the value in the secondary index is the PK columns but the PK columns are used here to make the secondary index key unique. Logically the value in the PK index is the RecordId, but I think that the implementation puts the RecordId at the end of the PK columns in the key. And for the RecordId index the value is the Document.
• Block compression, when configured, is done for all pages. So it might be possible that more data can get the benefit from block compression with RocksDB than with WiredTiger and this can be a big deal when wide (covering) secondary indexes are used. However I still have questions about where the block compressor is used for WT.

Formal methods in the real world

A lot of interesting work is done at Amazon but not much is written about it. There is an article on their use of formal methods via TLA+ and PlusCal. I haven't seen much use of formal methods in my career. I have spent a lot of time debugging code written by other people, so I wouldn't mind if such tools were used more frequently.

I used the Spin tool for two MySQL features. I hope other people try the tool and read the book. I first used it when we rewrote the InnoDB RW-lock at Google. The RW-lock had an awkward implementation that limited performance on many-core and many-socket servers. The new implementation was (mostly) lock free and inspired by the excellent work of Yasufumi Kinoshita. We used Spin to verify that the state transitions were probably correct. I use the word probably because Spin was used to explore the state space to find deadlocks and assertion failures. This wasn't a formal proof of correctness. We shared the Spin model with the InnoDB team when contributing the code. Our change made it into upstream InnoDB and that was one step in making MySQL better for many-core servers.

I used Spin a second time while implementing admission control for MySQL. I used a lock-free protocol to maintain per-user counts of running queries. This was done to avoid mutex contention and the code was more complex than using atomic increment/decrement. I re-read the Spin book prior to writing the Spin model and think I was better at it than during my first project.

Helping make MySQL better

My peers have been very busy the past few years helping to make MySQL better for web-scale deployments. Much of this effort is also good for deployments that aren't web-scale. Join us at Percona Live 2015 to learn more.

• Polyglot persistence @ FB keynote by Harrison Fisk
• WebScaleSQL keynote by Steaphan Greene
• MySQL for Facebook Messenger by Domas Mituzas
• MySQL Automation at Facebook Scale by Shlomo Priymak
• LSM Databases at Facebook by Yoshinori Matsunobu
• XDB: Shared MySQL Hosting at Facebook Scale by Evan Elias
• Online InnoDB Defragmentation by Rongrong Zhong
• Fast Master Failover without Data Loss by Yoshinori Matsunobu
• Row Based Replication and Incremental Logical Backup by Santosh Banda
• DocStore Document Database for MySQL at Facebook by Peng Tian and Tian Xia
• WebScaleSQL talk by Steaphan Greene
• WebScaleSQL BOF with Steaphan Greene. I hope other members from the WebScaleSQL effort will attend.
• RocksDB storage engine for MySQL BOF. I hope people from the core RocksDB team will attend.

Storage efficiency

Storage efficiency is a big deal. I have learned a lot about read, write and space amplification over the past few years. Tiered storage has been a part of my work life via flashcache, but tiered storage for an LSM doesn't require flashcache. This is going to get interesting. We have more choices for SSD at a variety of price points based on write endurance and performance.  We have write-optimized database engines (RocksDB, Tokutek, WiredTiger) arriving for OLTP workloads. We can use this with commodity hardware and open-source DBMS solutions like MySQL and MongoDB. A lot of interesting work remains to put the pieces together while matching the quality of service we get from MySQL+InnoDB and I hope to use RocksDB as part of MySQL and MongoDB.

We are beginning to engage with the community. Yoshinori Matsunobu has a talk at the MySQL UC. I have a talk at the CloudDM workshop at ICDE. I expect more talks, hopefully a few conference papers and if you are local then there are RocksDB meetups.

One benefit from RocksDB compared to a b-tree is much better compression and much less write-amplification. I have observed this via linkbench and real workloads. There are many other ways that an LSM can reduce the IO demand from an application. But I don't want to give away too many details until Yoshi and I have done our talks.

I don't get marketing

MongoDB 3.0 is almost here. It includes the WiredTiger storage engine which is very impressive. Alas, now we are told that the original storage engine has performance problems. I am shocked. Who knew? Not anyone reading their documentation. I don't understand why companies play this game. Be honest with your users as this goes a long way to building a solid and educated community. I hold MySQL to the same standard. Lets us not forget that awesome manual section on atomic operations.

Don't let the marketing team have editorial control over the documentation team.

Edit: an era has ended, the section on atomic operations has been removed from the MySQL manual.