When observing your database stalls it
Recently, on my other blog accidentallyquadratic, I documented a case of accidentally quadratic behavior in /proc/$pid/maps on a wide range of recent Linux kernels.
While this bug is amusing, it might initially not seem that important; /proc/$pid/maps is primarily a debugging or inspection tool, and while 30s access times aren’t pleasant, they probably aren’t breaking anything too critical.
Today I want to explore, by way of some microbenchmarks, the more pernicious impact of that bug.
I wrote a microbenchmark that’s designed to simulate the load of of a network server (perhaps a database of some sort) that relies on mmap to access a large file on disk. The benchmark allocates and maps a large file, and then spawns three sets of threads:
A large number of idle threads, simulating idle connections
A number of “reader” threads, which repeatedly read from random memory pages of the mapped region. These would simulate threads servicing requests.
A number of “mapper” threads, which repeatedly mmap and munmap small regions in memory. These might simulate background threads, or connection churn, which might mmap and munmap thread stacks on a real service.
Unless stated otherwise, I ran all the following experiments on a 200GB mapping on an i2.2xlarge ec2 instance running Ubuntu Trusty on a 3.13 kernel.
We start with a baseline of 10,000 idle threads, 10 readers, and no mappers:
(blue is p90, red is p99, measured over batches of 1000 consecutive reads in a single thread)
First observation: we can invoke a page fault handler, read a page from SSD, update the page tables, and get back to userspace, in ~500µs at p99, in 10 concurrent threads. Computers are fast.
Now, in that previous chart, at t=20s, I actually ran cat /proc/$pid/maps > /dev/null in a separate shell. You can see that it had minimal if any effect, as you might hope (it ate 10s or so of CPU time, but disk speed wasn’t impacted).
However, now let’s re-run with an identical configuration, but a single thread running mmap and munmap in a tight loop:
Once again, at t=20s I’ve run a cat /proc/$pid/maps > /dev/null.
Whoa! It’s lost in the scale of the graph, but the baseline performance is pretty similar to the previous case. However, inspecting the maps file spikes performance to upwards of 100ms!
What’s Happening?
On Linux, the address space of a process (the description of which regions of memory are backed by why – anonymous mappings, file mmaps, etc) is protected by a shared reader-writer lock. All threads in a single process share an address space, and thus share the corresponding reader-writer lock (called mmap_sem in the kernel)
Handling a page fault requires a read lock on mmap_sem: A page fault has to look up the memory region containing the fault, but it doesn’t change the virtual memory layout.
Handling /proc/$pid/maps has to walk the virtual memory layout, so it also requires a read lock. Thus, it can procede in parallel with page faults.
Handling mmap mutates the memory layout, so it requires a write lock. It only needs to hold the lock long enough to insert an entry into a red-black tree, which is ~instantaneous compared to going out to disk, and thus doesn’t affect performance much by itself.
However, the Linux rw_semaphore is writer-priority, and it is when we add all of these ingredients together that we get trouble.
The /proc/$pid/maps call holds the mmap_sem for reading while it’s busy doing quadratic work looking up all those stacks. If, while it’s running, a writer attempts to enter, that writer will have to wait for it to complete.
But, because the lock is writer-priority, this blocks any new readers from entering. Thus, in the presence of a /proc/$pid/maps reader and an mmap thread, we find all readers now blocking on the slow /proc/$pid/maps readers, with disastrous results.
(Why do we see a bunch of writes get through, instead of a complete stoppage during the read? Files in /proc/ tend to only hold the lock while they write a batch of entries to userspace, and then drop and reacquire it. This behavior is necessary to avoid holding locks forever while waiting on a slow userspace reader)