Searching 20 GB/sec: Systems Engineering Before Algorithms

I don't know that this is simple. There is a lot of fancy work going on getting data in and out fast.

I think it's more that memory is getting slower relative to CPU, as we all know, so complicated data structures that involve lots of random access to memory aren't so efficient anymore vs linear scans through memory that can benefit from cache. It's still engineering, just the tradeoffs have shifted.

They're not using any fancy algorithms...except when they implement a customized version of Boyer-Moore for better string searching in a critical section of their algorithm. Not to mention all the fancy algorithms optimizing their brute-force code underneath their immediately visible program.

A better title would be, "How we determined when to use brute force."

Say what you will, but while Boyer-Moore can be tricky to implement, it's not exactly a fancy algorithm.

Indeed, in the not too distant future we expect to move to spinning disks, with the data arranged for streaming reads. Streaming off disk can be pretty fast. LZ4 compression is fast enough to give us another big boost without turning CPU into a bottleneck. But the big enabler will be spreading data across disks, so that in principle we can use every spindle we own in service of every nontrivial query. The fact that server logs have a very high write-to-read ratio really helps us out here.

Today, we're keeping everything on SSD -- twice, in fact, to maintain a hot spare for each server. SSD prices have fallen to the point where, even renting from Amazon, we can make the cost model work; and SSD is a great crutch as we tune our storage layer. But spinning disk will be a lot cheaper.

As for Java: we've been pretty surprised ourselves. Going in, we expected to need a lot more "native" (C) code. As it turned out, currently the only non-Java code we're using is the LZ4 library, and even there we only recently moved to the non-Java implementation. We do soon expect to move a few more bits of code to C, such as the core text-search loop. But based on the performance we've been getting in pure Java, we don't anticipate any need to move more than a fraction of 1% of our overall code base.

We do have some code that lives in a sort of middle ground -- Java code written like it was in C. Our database buffers live in a set of 2GB byte arrays, soon to be replaced by native memory blocks. We do our own (very simple) memory allocation within that, and use a sprinkling of Unsafe operations to access it. This gets us closer to C performance (not all the way there), without any of the hassles of bridging across languages. This part is still well under 1% of our overall codebase.

Herb Sutter gave a talk somewhat recently going over the basics of working intelligently with the cache. He had some kinda surprising results where naive algorithms on vectors/arrays outperformed the intuitively better list/tree approaches. Circumstances where you'd think all the copying elements and re-sizing std::vector would be expensive turn out not to matter.

http://channel9.msdn.com/Events/Build/2014/2-661

The basic take-away is to always prefer std::vector and boost::flat_set/flat_map unless you have evidence to the contrary.