Ayende @ Rahien

My name is Oren Eini
Founder of Hibernating Rhinos LTD and RavenDB.
You can reach me by phone or email:


+972 52-548-6969

, @ Q c

Posts: 6,130 | Comments: 45,557

filter by tags archive

Optimizations gone wild, O(N!) memory leaks

time to read 2 min | 252 words

So, after doing so much work on the indexing optimization, it turned out that we had a bug. I assume that you remember this optimization, right?


In which we were able to pre fetch data from the disk and not have to wait for data at all. This all worked beautifully when running on data sets that included simple indexes. But the moment we had map/reduce indexes, something bad happened. That something bad was that we kept missing the batch that we loaded (this relates to how we load & find the appropriate batches).

We do all the lookups by etag, and map/reduce add gaps in the etags. Which meant that we kept missing the etag, and had to start loading things up again. And because whenever we load something we also start loading the next batch…

Here is what the memory looked like:


Yup, for every batch we loaded the next 5 batches, for a total of O(N!) items in memory for everything.

Now, we had some cleanup routines, but we did NOT expect to have that much, so we would recover, eventually, but usually not before we consumed all the memory.



Harry McIntyre

Do you have automated tests for catching memory issues, and if so, how do they work?

Ayende Rahien

Harry, No, we don't. We use dog fooding for those sort of issues.


Isn't it a O(n^2) leak?

Joseph Daigle

Yeah, it's (N^2)/2 not N!. You're taking the summation of N...1, not the product.

Ayende Rahien

Paul, No, because each time it will issue a set of additional batches from the start of the next one, and so on. We will miss those, and issue another set, and so on.

Alois Kraus

For regression testing you could WMemoryProfiler (https://wmemoryprofiler.codeplex.com/). It is free. You can download the latest sources to get it up and running.

Ayende Rahien

Alois, That is a great project, I am looking forward to digging into that.

Comment preview

Comments have been closed on this topic.


  1. How to waste CPU and kill your disk by scaling 100 million inefficiently - 17 hours from now
  2. RavenDB Conference 2016–Slides - about one day from now

There are posts all the way to Jun 01, 2016


  1. The design of RavenDB 4.0 (14):
    26 May 2016 - The client side
  2. RavenDB 3.5 whirl wind tour (14):
    25 May 2016 - Got anything to declare, ya smuggler?
  3. Tasks for the new comer (2):
    15 Apr 2016 - Quartz.NET with RavenDB
  4. Code through the looking glass (5):
    18 Mar 2016 - And a linear search to rule them
  5. Find the bug (8):
    29 Feb 2016 - When you can't rely on your own identity
View all series


Main feed Feed Stats
Comments feed   Comments Feed Stats