<!DOCTYPE html><html><head><title></title><style type="text/css">p.MsoNormal,p.MsoNoSpacing{margin:0}</style></head><body><div style="font-family:Arial;">On Fri, Nov 30, 2018, at 22:09, Howard Chu wrote:<br></div><blockquote type="cite" id="fastmail-quoted"><div style="font-family:Arial;">Bron Gondwana wrote:<br></div><div style="font-family:Arial;">> Hi All,<br></div><div style="font-family:Arial;">> <br></div><div style="font-family:Arial;">> We were debugging the CPU usage in a ctl_conversationsdb rebuild yesterday, and noticed an interesting thing. 70% of the CPU utilisation for this one process<br></div><div style="font-family:Arial;">> was inside the kernel! Mostly with dirty pages.<br></div><div style="font-family:Arial;">> <br></div><div style="font-family:Arial;">> ctl_conversationsdb -R is particularly heavy on the twoskip database - it's rewriting a lot of random keys. This leads to writes all over the place, as it<br></div><div style="font-family:Arial;">> stitches records into the skiplists.<br></div><div style="font-family:Arial;">> <br></div><div style="font-family:Arial;">> Of course the "real answer"[tm] is zeroskip, which doesn't do random writes - but until then, we suspect that the cost is largely due to the face that we use<br></div><div style="font-family:Arial;">> mmap to read, and fwrite to write! We know that might be less efficient already from Linus' comments about 10 years ago! And I guess here's the proof.<br></div><div style="font-family:Arial;">> <br></div><div style="font-family:Arial;">> An option would be to switch to using mmap to write as well. We could easily modify lib/mappedfile to memcpy to do the writes.<br></div><div style="font-family:Arial;">> <br></div><div style="font-family:Arial;">> Does anybody see any strong reason not to?<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">I've covered the reasons for/against writing thru mmap in my LMDB design papers. I<br></div><div style="font-family:Arial;">don't know how relevant all of these are for your use case:<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">1: writing thru mmap loses any control over write ordering - the OS will page dirty pages out in arbitrary order.<br></div><div style="font-family:Arial;">If you're using a filesystem that supports ordered writes, it will preserve the ordering of data from write() calls.<br></div></blockquote><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">This is not a concern at all - twoskip is deliberately designed such that it does a single write and then flush to "dirty" the file, all changes made while dirty are fully revertable if it crashes, and then it does a fsync (msync now I guess!) before a single write which clears the dirty flag. So long as a single 256 byte write is consistent, it's safe.<br></div><div style="font-family:Arial;"><br></div><blockquote type="cite" id="fastmail-quoted"><div style="font-family:Arial;">2: making the mmap writable opens the possibility of undetectable data structure corruption if any other code<br></div><div style="font-family:Arial;">is doing stray writes through arbitrary pointers. You need to be very sure your code is bug-free.<br></div></blockquote><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">Yes, this is a significant concern.<br></div><div style="font-family:Arial;"><br></div><blockquote type="cite" id="fastmail-quoted"><div style="font-family:Arial;">3: if your DB is larger than RAM, writing thru mmap is slower than using write() syscalls. Whenever you<br></div><div style="font-family:Arial;">access a page for the first time, the OS will page it in. This is a wasted I/O if all you're doing is<br></div><div style="font-family:Arial;">overwriting the page with new data.<br></div></blockquote><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">I doubt it... especially now we're running on servers with 256Gb of data. These databases are usually under a gigabyte in size. I also don't think we ever overwrite a page without reading from it first - we're usually updating pointers which we've just had to read.<br></div><div style="font-family:Arial;"><br></div><blockquote type="cite" id="fastmail-quoted"><div style="font-family:Arial;">4: you can't use mmap exclusively, if you need to grow the output file. You can only write thru the mapping<br></div><div style="font-family:Arial;">to pages that already exist. If you need to grow the file, you must preallocate the space, otherwise you<br></div><div style="font-family:Arial;">get a SEGV when referencing unallocated pages.<br></div></blockquote><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">We always know what we're planning to write, so I'm fine with using an ftruncate call on the file descriptor to extend it.<br></div><div style="font-family:Arial;"><br></div><blockquote type="cite" id="fastmail-quoted"><div style="font-family:Arial;">And a side note, multiple studies have shown that skiplists are not cache-friendly, and thus have<br></div><div style="font-family:Arial;">inferior performance to B+tree organizations. A skiplist is a very poor choice for a read/write data structure.<br></div></blockquote><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">Yeah, hence zeroskip - it's coming.<br></div><div style="font-family:Arial;"><br></div><blockquote type="cite" id="fastmail-quoted"><div style="font-family:Arial;">Obviously I would recommend you use something carefully designed and heavily tested, like LMDB, instead<br></div><div style="font-family:Arial;">of whatever you're using.<br></div></blockquote><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">We tried and had a bad experience last time - it didn't fit in well with the expectations how our code uses database. I'm not super keen to try again right now. I do appreciate your persistence and passion for your project though :) It's good to see this level of engagement.<br></div><div style="font-family:Arial;"><br></div><blockquote type="cite" id="fastmail-quoted"><div style="font-family:Arial;">There's one point in favor of writing thru mmap - if you take care of all the other potential gotchas,<br></div><div style="font-family:Arial;">it will work on every OS that implements mmap. Using mmap for reads, and syscalls for writes, is only<br></div><div style="font-family:Arial;">valid on OSs with a unified buffer cache. While this isn't a problem on most modern OSs, OpenBSD is a<br></div><div style="font-family:Arial;">notable example of an OS that lacks this, and so that approach always results in file corruption there.<br></div></blockquote><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">Yeah - that's an interesting point to me as well. At the moment we use a wrapper which is called map_stupidshared (don't blame me, was named before my time) which unmaps and remaps every time if the file has been changed. Insanity. It gets tested for during the configure stage.<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">We have something even more awful called map_nommmap which just reads the entire file into a buffer every time. As you can imagine, performance is awful - but it does work!<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">Bron.<br></div><div style="font-family:Arial;"><br></div><div id="sig56629417"><div class="signature">--<br></div><div class="signature"> Bron Gondwana, CEO, FastMail Pty Ltd<br></div><div class="signature"> brong@fastmailteam.com<br></div><div class="signature"><br></div></div><div style="font-family:Arial;"><br></div></body></html>