480p is my friend - video streaming when you don't have fiber

I live in a rural area and doubt I will ever get fiber. I have fixed wireless broadband. Maybe low earth orbit satellites will be an option in the future whether that is via Starlink, Amazon or OneWeb.

I get 16Mbps which is shared by 4 people. One user plays online video games and cares about latency. Video streaming can be a challenge as it frequently consumes too much download bandwidth. Upload is usually not an issue except for FaceTime and other video chat apps.

I put video streaming apps into one of 3 classes -- polite, knows better and rude.

• Polite apps have video quality settings that are sticky. Set the video quality once to 480p and things are good. 
• Knows better apps know better. Set video quality to 480p today and it resets to auto the next time you use the app. Why? Because the apps knows that HD video makes you happy even if you don't have the network bandwidth to support that.
• Rude apps have no video quality settings. They use as much bandwidth as they can get.

To make up for the lack of throttling in many of the video streaming apps I have tried traffic shaping with a Gargoyle router. That is a lot of work, must get MAC addresses for all devices, and the results weren't great. I might have to try it again.

I am not a fan of Auto video quality. Maybe that works great when there are not multiple apps coming and going on the network. But I am skeptical about the ability for it to deal with congestion and I doubt it has any concern for the impact on latency sensitive apps (like online video games).

Polite apps are great but you still have to select lower quality for apps X users for web and then apps X devices for phone/tablet. Assume you need to revisit this once per year because apps change. Another thing to do is disable autoplay for as many apps as possible. I won't explain how to do that below.

The Apps

Buggy

• Facebook - Video Settings has a Video Default Quality option. AFAIK this setting has no effect for videos in Feed and Watch.  Some might call that a bug. I set the option to SD Only but Watch videos start in 720p or 1080p and Feed videos use a variety, some are HD.

Polite

• YouTube on a browser and iOS
• YouTube TV on a browser
• Apple TV - in Settings -> Apps -> iTunes Movies and TV Shows see Limit Purchases and Rentals to SD
• iTunes - purchase movies and TV shows in SD
• Netflix on iOS - go to More -> App Settings and set Video Quality to Standard
• Netflix on web - go to Account -> Playback settings
• Hulu on iOS - go to Account -> Settings -> Cellular Data Usage and choose Data Saver
• Hulu on web - start a video, click on the gear -> Quality -> Data Saver
• Amazon Prime on iOS - select Settings -> Streaming & Downloading
• Amazon Prime on web - start a video, click the gear
• Zoom - defaults to non-HD on a Mac (hope others follow this trend)
• Twitter on web - select Settings -> Data Usage -> Data Saver. The setting doesn't mention whether it changes video quality. While there disable autoplay as well.
• Twitter on iOS - select Settings -> Data usage to disable autoplay and select lower quality videos and images

Knows Better

• YouTube TV on iOS

Rude

• FaceTime
• Chromecast - the only choice is Auto. If you are watching something in 480p on a browser and then start casting the device will try for higher quality.

Unknown

• Snapchat, Instagram, TikTok - I will figure this out when my kids get home
• Facebook Video Chat

It is all about the constant factors

Assuming I put performance bugs I worked on into one of three buckets -- too much big-O, too much constant factor and other -- then too much big-O would have the fewest entries. Maybe we worry too much about big-O and not enough about everything else? This post is inspired by a post and tweet by Dan Luu.

By too much big-O I mean using an algorithm with more computational complexity when one with less is available and the difference causes problems in production. A common problem is using an O(n^2) algorithm when O(nlgn) or O(n) are possible. By too much constant factor I mean an inefficient implementation. Everything else goes into the other bucket.

It is all about the constant factors was a reply to someone who dismissed performance concerns with it is just a constant factor. That still amuses me. I assume that too much big-O is the least likely cause of performance problems given my classification scheme. This is not a rigorous study but I wasn't able to find many too much big-O bugs from my bug history. The search is complicated because it isn't easy to search for O(n*n). What search terms do you use -- O(n*n), O(n^2), squared?

1. Pagination is O(n*n) - this happened several times in production, so it counts as many bugs. Be careful with pagination queries.
2. O(n*n) parsing in MySQL client - this was MySQL bug 34578
3. O(n*n) allocation on array resize - Dan Luu explained an example of this. I have also encountered this but my memory is vague.
4. O(n*n) common subexpression elimination - while working on a closed-source DBMS I fixed code that did CSE using an O(n*n) algorithm. It fell over on machine generated SQL that had thousands of terms in the WHERE clause.
5. The InnoDB rw-lock and mutex so many years ago had O(n*n) overhead for n threads trying to get through them (lock/unlock) because of the way that wake-all on unlock was implemented. See MySQL bug 52806.

Perhaps shared_ptr deserves its own bucket. I wrote about finding shared_ptr perf bugs in MyRocks and MongoDB. I found at least one more in MyRocks, someone else reported one for RocksDB and I have seen a few more problems from this in production.

From disk to flashcache to flash

The past decade in database storage was interesting whether you stayed with local attach storage, used block & object storage from cloud or on-prem vendors or moved to OSS scale-out storage like Ceph, GlusterFS and MinIO. I am writing about my experience and will focus on local attach.

Over the past decade the DBMS deployments I cared for went from disk to flashcache to flash on the HW side and then from MySQL+InnoDB to MySQL+MyRocks on the SW side. I assume that HW changes faster than DBMS software. DBMS algorithms that can adapt to such changes will do better in the next decade.

One comment I have heard a few too many times is that storage performance doesn't matter much because you can fit the database in RAM. More recently I hear the same except change RAM to Optane. I agree that this can be done for many workloads. I am less certain that it should be done for many workloads. That (all data in RAM/Optane) costs a lot in money, power and even space in the data center. Lets make web-scale DBMS green. Use enough RAM/Optane for cache to meet the performance SLA and then use SSD or disk arrays. At some point there is no return from cutting the DBMS query response time in half but cutting the DBMS HW cost in half is usually a big deal.

Priorities

With disk and flashcache I worried a lot about the IOPs demand because the supply was limited, usually less than 2000 operations/second. On moving to flash I stopped worrying about that and began worrying about write and space amplification (efficiency).

The context for this is small data (OLTP) workloads and deployments where reducing HW cost matters.  Overcoming the IOPs shortage was interesting at times and good for my career as there were always new problems that had to be fixed right now. Moving to flash made life easier for everyone. There was an opportunity cost from using disks -- time spent solving the latest IOPs demand crisis was time not spent on longer term projects. Moving to flash gave us time to build and deploy MyRocks.

MyRocks has better space and write efficiency than a b-tree. The cost of better space and write efficiency with an LSM is more CPU overhead for point and range queries. Sometimes that is a great trade. Better space and write efficiency means you buy less SSD and it lasts longer. Better write efficiency is a big deal with lower endurance (TLC and QLC) NAND flash. I wonder how this changes in the cloud. Cloud vendors might improve their profit margins with better space and write efficiency but they also have the ability to pass on some of the inefficiency costs to the user. A cloud user doesn't have to worry as much about write efficiency because they are renting the SSD.

Hardware

This is my history with storage for web-scale MySQL. The NUC servers I use today have similar RAM/CPU as the DBMS servers I started with in 2005 but the NUC servers have much more IO capacity.

First there were disk arrays with HW RAID and SW RAID. This was RAID 10 which was better for durability than availability. Data isn't lost on a single-disk failure but the server performance is unacceptable when a HW RAID cache battery fails (fsync is too slow) or a rebuild is in progress after a disk gets replaced.

Then there was flashcache and performance is wonderful when the read working sit fits in the flash cache but there is an abrupt change in performance when it does not. Those were exciting years. Some of the performance critical parts of flashcache were in the Linux kernel. I lack kernel skills and it took us (really, Domas) a while to identify perf problems that were eventually fixed.

Then there was flash and the abundance of IOPs was wonderful. I look forward to the next decade.

Anecdotes

If you use disk arrays at scale then you will see corruption at scale. You are likely using multiple storage devices with multiple firmware revisions. It is interesting when 99% of corruption occurs on 1% of the deployment -- all on the same, new firmware revision. That result makes it easy to focus on the HW as the probable problem and stop blaming MySQL. I can't imagine doing web-scale DBMS without per-page checksums.

Performance variance with NAND flash is to be expected. I hope that more is done to explain and document it for OLTP workloads. The common problem is that NAND flash GC can stall reads on the device. I wish it were easier to characterize device performance for enthusiasts like myself. I am sure there is an interesting paper on this topic. How much concurrency does the device provide? How are writes done? How is GC done? What is the stall distribution? What can be done to reduce stalls (see multistream and LightNVM)?

Using TRIM (mount FS with discard) at scale is exciting. RocksDB and MyRocks do a lot of TRIM while while InnoDB does not. How many GB/s and unlink/s of TRIM does the device support? TRIM performance varies greatly by vendor. I hope more is done to document these differences. Perhaps we need trimbench. People at web-scale companies have stories that never get shared because they don't want to throw their SSD vendors under the bus. I was spoiled by FusionIO. My memory is that FusionIO TRIM was a noop from a perf perspective.

Innosim is an InnoDB IO simulator that I wrote to help device vendors reproduce performance stalls we encountered with web-scale MySQL. It is easier to run than MySQL while able to generate similar IO patterns. I wrote it because InnoDB has a pattern of coordinated IO that fio wasn't able to reproduce. The pattern occurs during page write back -- first write the double write buffer (1MB or 2MB sequential write) and then do 64 or 128 random 16kb writes. Innosim also takes much less time to reach steady state -- just sequentially write out X GB of database pages versus load InnoDB and then run (for days) an update workload to fragment the indexes. Fragmentation takes time. I wish more DBMS benchmarks ran long enough to get sufficient fragmentation but that can be expensive.

Perhaps one day I will write WTsim, the WiredTiger IO simulator. I wrote ldbsim, the LevelDB IO simulator, but it was rarely used because the RocksDB benchmark client, db_bench, was easy to use even if fragmenting the LSM tree still took a long time. I am not sure that fio would be able to reproduce the special IO patterns created by RocksDB compaction. I love fio but I am not sure it should try to solve this problem for me.

What is the future of off-cpu analysis?

The answer is I don't know although I am really asking about tools I will use in 2020 and others will make different choices. I will have better answers in a few months. People have been telling me there is something better than PMP for many years. Perhaps that claim is finally true but this post from Percona suggests that PMP might have a future.

I start with Brendan Gregg when I want to learn about modern performance debugging and he has a page on off-cpu analysis. From there I learn eBPF, perf and bcc are the future and I hope that is true. For now I will summarize my use cases and potential solutions.

I have three use cases:

1. Small server (< 10 cores) doing ~100k QPS on benchmarks
2. Many-core server (<= 2 sockets, lots of cores/socket) doing x00k QPS on benchmarks.
3. Servers in production

Stalls are more tolerable in the first two cases. Crashes and multi-second stalls in production are rarely acceptable. Although when a production server is extremely unhappy then a long stall or crash might be OK. Sometimes I want my long-running benchmarks to collect some thread stacks for off and on CPU analysis. This is more important for workloads that take days to setup. But I have yet to figure out how to exclude the impact from that when collecting throughput and response time metrics. This is more of an issue for off-cpu analysis versus using perf for on-cpu analysis as the impact from perf is smaller.

Some approaches, gdb and quickstack, have a per sample overhead which is probably linear in the number of thread stacks. I assume work done by gdb and quickstack to get stack traces is single-threaded which contributes to longer stalls on busier servers.

Other approaches like eBPF have an overhead that is independent of the number of samples -- the overhead is gone once samples have been collected. The overhead is probably linear in the amount of activity on the server (linear in the number of CPU cores) and I hope that much of it is handled in parallel -- each CPU core has more work to do when scheduling threads.

The possible approaches are:

• Runtime - Java makes this easy with jstack. I am not sure whether gperftools and libunwind make this easy for C and C++.
• PMP/gdb - Percona provides PMP via pt-pmp. Percona has a great post on fast ways to get thread stacks and I look forward to evaluating their advice. This might make PMP useful for the first two use cases listed above.
• PMP/quickstack - quickstack is much faster than original PMP/gdb but was also less truthy. Regardless it made PMP much better in production.
• eBPF - I am waiting for the eBPF book to arrive. Until then I have the web.

Readahead

Q: What is the best readahead size?
A: O_DIRECT

Perhaps I agree with Dr. Stonebraker. This is my answer which might not be the correct answer. My reasons for O_DIRECT are performance, quality of service (QoS) and manageability and performance might get too much attention. I don't dislike Linux but the VM, buffered IO, readahead and page cache are there for all Linux use cases. They must be general purpose. Complex system software like a DBMS isn't general purpose and can do its own thing when needed. Also, I appreciate that kernel developers have done a lot to make Linux better for a DBMS. One of the perks at FB was easy access to many kernel developers.

Most of my web-scale MySQL/InnoDB experience is with O_DIRECT. While InnoDB can use buffered IO we always chose O_DIRECT. Eventually, RocksDB arrived and it only did buffered IO for a few years. Then O_DIRECT support was added and perhaps one day the web-scale MyRocks team will explain what they use.

I deal with readahead when running benchmarks and a common experience is using the wrong (too large) value and then repeating tests which means I spend more time and more SSD endurance thanks to buffered IO. I have many blog posts with performance results for readahead including at least one for MongoDB. Usually my goal was to find which small value is good enough. I learned that 0 is too small. Readahead can help scan-heavy workloads, but my focus is on OLTP where we avoided most scans except for logical backup.

I understand why buffered IO is used by some DBMS. Early in the product lifecycle it can be a placeholder until more features are added to make O_DIRECT performant. The benefits of the OS page cache include:

• Filesystem readahead can be used before the DBMS adds support for prefetching when doing scans. But filesystem readahead is a black box, might differ between filesystems, provides no metrics and will do the wrong thing for some workloads. InnoDB provides a prefetch feature which can help when O_DIRECT is used. I disabled it because OLTP. The Facebook MySQL team (thanks Nizam) added logical readahead to make logical backup faster and more efficient. Filesystem readahead is likely to struggle with index structure fragmentation, so it is best suited for heap-organized tables and will suffer with index scans.
• Doing writes to the OS page cache followed by fsync can be used before the DBMS adds support for async IO or background write threads. But Postgres suffered for so long from this approach because calling fsync with an unknown amount of dirty pages in the OS page cache can starve all other pending IO requests for many seconds. The situation is less dire today thanks to work by Jens Axboe to make writeback less annoying. There was much discussion in 2014 at a summit that included Postgres and Linux kernel developers. In addition to Linux improvements, features have been added to Postgres to reduce the impact from writeback storms -- read this to learn about spread checkpoints.
• For a DBMS that does compression it is easier to use the DBMS cache for uncompressed pages and the OS page cache for compressed pages. I am familiar with amazing work in InnoDB to manage both in the DBMS cache. We all agree the code is very complex. RocksDB also has an option to cache both in its block cache but I have little experience with the feature. It is hard to figure out the best way to divide the DBMS cache between compressed and uncompressed pages.

Performance advantages for O_DIRECT include:

• Does one memory copy to move data from storage to the DBMS while buffered needs two
• Avoids CPU and mutex contention overhead in the OS page cache
• Avoids wasting memory from double buffering between the DBMS cache and OS page cache

QoS advantages for O_DIRECT include:

• Filesystem readahead is frequently wrong and either wastes IO or favors the wrong user leading to worse IO response times for other users
• OS page cache will get trashed by other services sharing the host
• Writeback storms starve other IO requests. Writeback is usually a background task and can tolerate response time variance. Too much writeback makes user reads and log fsync slower and those operations don't want response time variance.
• Reduces stalls - this is a placeholder because my local expert has yet to explain this in public. But you will have a better time with Linux when moving less data through the OS page cache, especially with modern storage devices that can sustain many GB/sec of throughput. And when you aren't having a good time then you can fix the DBMS. The DBMS is involved whether or not it relies on the OS page cache so you always have to make it work.

Manageability advantages for O_DIRECT include:

• DBMS prefetch and writeback are documented, tunable and provide metrics. Such claims are less true for filesystem readahead and VM writeback. There is a lot of advice on the web and much disagreement especially on the topic of min_free_kbytes. Domas used to be my source on this but he doesn't blog enough about the Linux VM.

Slides for talks I have given on MySQL, MongoDB and RocksDB

It all started for me with the Google patch for MySQL in April 2007. The Register summary of that included a Cringely story repeated by Nick Carr that Google might have shared the patch as part of a plan to dominate IT via cloud computing. I thought that was ridiculous. AWS said hold my beer and brought us Aurora.

I donated to the Wayback Machine to offset my HW consumption for those links.

A list of talks from the RocksDB team is here.

This is an incomplete list of slide decks and videos from me:

• MySQL for High-Scale, MySQL Ignite
• MyRocks Overview, MyRocks meetup
• RocksDB: from faster to better, CMU with Coach Pavlo
• MySQL is Web Scale, Istanbul with Monty Program
• Scaling InnoDB, O'Reilly MySQL 2008 (no slides/video yet)
• This is not a web app, O'Reilly MySQL 2009
• Running MySQL at Scale, FB Tech Talk 2010
• High Throughput MySQL, O'Reilly MySQL 2010
• Success with MySQL, MySQL Sunday 2010
• MySQL at Facebook, O'Reilly MySQL 2010
• NoSQL, Hot Storage 2011
• MySQL for the datacenter, O'Reilly MySQL 2011
• High Value Transaction Processing, Percona Live SF 2011 - this has a list of bugs and fixes
• Success with MySQL, North East Database Day 2012
• What comes next for MySQL, Percona Live 2012
• InnoDB Buffer Pool Notes, 2012
• MySQL at Facebook, China 2013
• MyRocks vs Something Else, video and slides, Highload 2013
• Storage Economics, Tech Talk 2013
• Open Source at Scale, OpenWest 2013
• Web scale OLTP, 2014
• Social Graph OLTP, 2014
• MySQL at Scale, Dropbox 2014
• Running MyRocks in Production, 2015
• Storage Engine Diversity, MongoDB World 2015
• Web-Scale History, DevOps Day Camp at OSUOSL 2015
• The Case for MyRocks, 2015
• Web Scale Data Management, Percona Live Europe 2015
• Open Problems for RocksDB, CWI 2015
• Read, Write and Space Efficiency: Pick 2, ACM Applicative 2016
• Making the case for write-optimized, Yandex 2016
• Making the case for write-optimized: video and slides, Highload 2016
• Performance and Efficiency with RocksDB, CodeMesh 2016
• Updated case for MyRocks, MongoRocks and RocksDB, RocksDB Meetup 2016
• MyRocks, MongoRocks and MongoDB, Percona Live 2016
• MyRocks and MongoRocks: Performance & Efficiency, Percona Live Europe 2016
• Features we need, features that scale, Percona Live Europe 2016
• RocksDB Read Cache, MongoDB World 2016
• An Update on MyRocks, Percona Live 2017
• MongoRocks, WiredTiger and mmapv1, Percona Live 2017
• MongoRocks Improvements, Percona Live Dublin 2017
• MyRocks, FOSDEM 2017
• How to talk to me at conferences, maybe HPTS gong show

Historical - summary of the Google MySQL effort

This summarizes work we did on MySQL at Google. These posts used to be shared at code.google.com but it was shutdown. After reformatting most of these (it was a fun day for me, but sorry for the spam) I remembered that somone had already done that in 2015. Thank you.

It all started for me with the Google patch for MySQL in April 2007. The Register summary of that included a Cringely story repeated by Nick Carr that Google might have shared the patch as part of a plan to dominate IT via cloud computing. I thought that was ridiculous. AWS said hold my beer and brought us Aurora.

My reformatted posts:

• work done by several people to fix the InnoDB rw-lock for SMP
• other work for InnoDB SMP performance
• user, table, index monitoring
• crash safe replication state
• parser changes for new features
• semisync replication and design doc
• SHOW STATUS
• SHOW INNODB STATUS
• my.cnf
• adding roles to mysql
• make user delayed
• the Google patch for MySQL 5.0
• InnoDB IO performance

Posts from the git wiki pages via my fork of upstream:

• user, table, index monitoring, also see this doc
• InnoDB Async IO
• Batch Key Access
• Binlog Event Checksum
• Fast Master Promotion
• InnoDB IO tuning
• InnoDB IO configuration
• InnoDB optimizer stats sampling
• InnoDB SMP
• Making mysqldump lossless for float & double
• Mirrored binlogs - this turned out to be a problem in production. I won't say more.
• More logging
• SHOW INNODB STATUS
• SHOW STATUS
• New SQL functions
• Online data drift
• Patch for MySQL 4.0
• QPS Rate Limits
• Semisync doc and design doc
• Transactional replication
• Global transactions IDs - work by Justin Tolmer at Google to enable failover automation. This was impressive. It was done years ahead of upstream. We couldn't wait. 
• Roles
• SMP Performance
• Mutex statistics