10 ms·
I don't think those are the same problem -- could you provide a link? The problem isn't paging, per se -- the paging system is doing exactly what it should be
by wheels 16y ago
I don't think those are the same problem -- could you provide a link?
The problem isn't paging, per se -- the paging system is doing exactly what it should be doing, paging in blocks off of the disk and into memory as they become hot, which for this use case is always.
The problem is that you get fragmentation in your pages. If you allocate three records in a row that are 300 bytes, and then need to rewrite the first one to make it 400 bytes, or delete it altogether, you end up creating a hole there.
The typical strategy for dealing with those holes it to maintain a list of free blocks which can be used and hope that the distribution of incoming allocations neatly fits into unused chunks.
However, as they note, if you have a fully compacted 64 GB active data set and remove 5% of it you just end up with address space that looks like swiss cheese; it's not set up to elegantly shrink, but to recycle space as it grows.
There are a couple of things that I find a bit odd here though: they should have seen this coming before migrating data; it's pretty obvious from the architecture. Second is that they mention the solution being auto-compacting, which wouldn't have actually helped them.
Auto-compaction is in fact useful, but all that it does is, well, compact stuff. It means they would have hit the limits later, but once the threshold was crossed, they'd have the exact same problem. Auto-compaction is either an offline process that runs in the background or a side-effect of smarter allocation algorithms. Both of those things need time once you remove data from an instance to reclaim the holes in the address / memory / disk space ... which is exactly what they did manually.
The only really sane ways to handle something like this are notifications at appropriate levels, or block-aware data removal -- e.g. "give me stuff from the end of the file". I don't know if mongo uses continuation records and stuff like that enough to know how difficult that would be for them.
(Note: Directed Edge's graph database uses a similar IO scheme, so I'm doing some projecting of our architecture onto theirs, but I assume that the problems are very similar.)
- donaldc 16y agoI don't think those are the same problem -- could you provide a link? You are correct, the actual problem is paging out LRU keys as opposed to memory holes. The issue is related but not the same. From http://antirez.com/post/what-is-wrong-with-2006-programming.html http://antirez.com/post/what-is-wrong-with-2006-programming.... Multiply this for all the keys you have in memory and try visualizing it in your mind: These are a lot of small objects. What happens is simple to explain, every single page of 4k will have a mix of many different values. For a page to be swapped on disk by the OS it requires that all contained objects should belong to rarely used keys. In practical terms the OS will not be able to swap a single page at all even if just 10% of the dataset is used.
- wheels 16y agoWhat antirez is getting at there is actually a much harder (and more interesting) problem that could be generalized as something like "efficient data locality for mixed latency access". However, assuming that all data must actually be in memory (as stated in the posted email), you don't actually solve the Mongo problem with more efficient organization of the data set, though compacting could be considered a sub-problem of the one that antirez describes. But as I noted in my earlier comment, compacting wouldn't have actually solved their problems, it just would have delayed them. It's reasonable to ask if all of their data truly needs to be hot, but even there, you'd eventually hit diminishing returns as you approached the threshold where your active set couldn't fit in memory, and there smarter data organization wouldn't actually fix things once you started pulling chunks out for sharding; you'd still need to recompact.
- donaldc 16y agoI doubt every last bit of their data needs to be hot (i.e. in memory) at any given time, but without specialized paging along the lines of what antirez has discussed for redis, enough of their data probably needs to be hot that, from a paging perspective, all of the vm pages of their data need to be hot.
- Nate75Sanders 16y agoIt seems that if you know your page size and you know your record size, you can compute the optimal size into which you should break your records into chunks and link the chunks with pointers. This causes more memory accesses, but surely that's worth keeping everything in memory? More chunks per record means more pointers and more accesses, but it should still be way faster in many cases. How to compare this to compaction, in the general case, isn't immediately obvious to me.