6 ms·
Searching 20 GB/sec: Systems Engineering Before Algorithms (2014)
- zachrose 10y agoWhat does 20 GB/sec mean in the context of a search?
- nomel 10y agoThe article [1] was about a log search/parsing service, so 20 GB of log files/second. Log files are usually text. [1] http://blog.scalyr.com/2014/05/searching-20-gbsec-systems-engineering-before-algorithms/ http://blog.scalyr.com/2014/05/searching-20-gbsec-systems-en...
- gravypod 10y agoEvery few years I stay in CS I see something crazy. I hope that the next crazy thing I see is a log file that isn't text. I can't imagine who would think that would have been useful to program IF it does exist.
- emcq 10y agoSome folks force every line to be Jason serializable. That can be nice for not needing to rewrite a parser for structured log lines. Another case is if you primarily send data via messages between processes, you could save those streams as log data. For example tcp streams or protobuf. The binary formats will be faster and smaller than converting all log output to text. While these scenarios may not apply to the common case, they certainly exist within the field.
- kryptiskt 10y agoDoesn't systemd do that with journald?
- duncan_bayne 10y agoYes and it's one of the many reasons I'm migrating to FreeBSD once 11.0 is out (chipset support). Not saying it's wrong for all cases, but it's not for me.
- to3m 10y agoWhy would you want your log files purely as text? It tends to take up a lot more space when you're storing a useful amount of readable information. Category prefixes and time stamps alone take up enough space that you could benefit from having them stored concisely. Indentation actually takes up space. The lines are delimited, not counted (you can have a trailing count). And so on. Space will always be a bottleneck, and generating the data will always take time; no reason to make that worse. The average log byte will be written once and then never looked at by a human. Producing ASCII text also requires a lot more code. Entire articles have been written on the correct way to print a float as decimal digits... or, you could memcpy 4 bytes into a buffer, while knowing ahead of time exactly how much space you'll need (and the value will round trip perfectly). Something similar goes for integers (using something like LEB128 encoding). In both cases the encoded data will likely take up less space than most useful text representations, even taking into account any control bytes, while being a lot quicker to produce. "But what if there's a bug?"... well, you'll probably find it in one of your first tests, when you write the first thing that sprang to mind. There's not much space for bugs to sneak in. People don't like this because we have crappy tools. If `cat' supported this kind of encoding as-is, nobody would complain about the idea. You can tell by the popularity of gzip... who complains about gzip? But good luck trying to read a gzip file without the right tools.
- falcolas 10y agoThe right tools for a gzipped log file is: less (courtesy of lesspipe). And/or zgrep. In the worst case scenario, you pipe the output of a gunzip through whatever tools you really want to use. The same tools work on compressed and uncompressed logs, and all of that "wasted space" compresses really well. Nothing like watching gigs of log files compress down to a few megs. It's even supported automatically in most Linux operating systems via logrotate.
- userbinator 10y agoSearching at several times memory bandwidth is definitely possible on reasonably modern hardware: http://www.codeproject.com/Articles/250566/Fastest-strstr-like-function-in-C http://www.codeproject.com/Articles/250566/Fastest-strstr-li... The trick is that the CPU isn't actually reading all those bytes, as the longer the string is to be sought, the more bytes can be skipped over if the last character doesn't match. I wouldn't call this "brute force" though - it's nowhere near as complex as indexing, but what I consider "brute force" is more like strcmp() in a loop.
- Everlag 10y agoThe fastest data to search through is always the data you ignore.
- zurn 10y agoYour needles (search terms) need to be quite long if you want to save on memory traffic: cache lines are 64-128 bytes and random access to standard DRAM is slower than sequential access. It can help if your data is in-cache though. (Or if you have an unusual system where memory is faster than what CPU can keep up with).
- qb45 10y agoThe high cost of random access to DRAM comes from jumping between rows (blocks of consecutive few -to- few tens of kB). If you read sequentially with gaps, you only have to open each row at most once. So it's like normal sequential reading, except that you may end up skipping few rows here and there and you may end up not transferring some parts of the rows you opened. So the time to completion can only be shorter, even if average throughput is lower.
- fizx 10y agoDeciding to do things this way is a tradeoff. Writing data into a search index is maybe 10x more expensive than writing it into a log. But doing actual search typically happens in something like log(n) time. Even for pathological queries, they're still far more efficient than scans. From a cost perspective, this system is a bet that most data it writes is rarely or never read from.
- foota 10y agoThe articles also discusses that it makes more complicated queries much easier to process. For instance, allowing regular expressions, or special character aware searches.
- rakoo 10y agoIt is possible to index content and then retrieve it with (simple) regular expressions, see (https://swtch.com/~rsc/regexp/regexp4.html https://swtch.com/~rsc/regexp/regexp4.html). The trick is that each regular expressions can be seen as a tree where leaves are n-grams to be searched for, and nodes are AND and OR logical operations of n-grams and intermediate nodes. So, a regexp like /banana/ can be seen as a search for the trigrams "ban" and "ana" and "nan" and "ana", all in that order. A regexp like /ca[tp]/ can be seen as a search for "cat" or "cap". Once you have simple n-grams like that it's trivial to index content on the way in (note that what you index doesn't actually need to interpret content, all you need is to split every n characters) and use that index to restrict potential matches.
- Retric 10y agoThis quickly falls down for searches like: /a[0-9][0-9][0-9]k[0-9][0-9][0-9]c
- MichaelGG 10y agoI think it's astounding how "easy" we can get away with stuff these days. But how does this scale to larger datasets? Say, capturing all signalling traffic for a telco. It's not hard to have 100s of GB a day - that's only a couple 10s of Mbps. Suddenly 20GB/sec means 5-10s queries just for that day. They can also leverage the bulk speed to reduce the size of posting lists. Just index each term to a chunk of, say, 1-5GB. And don't even index full terms, just hash them - a 64-bit hash gives you enough room for around 10 billion unique terms without causing much problems with collisions. New data in the last hour can be brute forced while the index is being generated. OTOH they seem successful so I suppose it's working quite fine.
- biturd 10y agoIf I read correctly, this was staged out on a single core user machine, then pushed out to an Amazon 16 core machine. Not the most powerful either, and no mention of any tuning. They mentioned looking to hit max scale out by simply adding more machines. Which is why they mention going from 20MG -> 100 -> 1000 not being an issue. In theory, wire speed is their limitation before they have to look at other methods. At 1000MB/s you could start chunking your data into result sets in advance, taking the time it takes a human to read the results visually as always being the bottleneck, and using that time to your advantage, to make the user think the app returns answers instantly all the time. I can't imagine 1000MB/s ever being too slow when you factor in their current dashboard and what it is returning. More complex dashboards and things certainly will need reworking.
- busterarm 10y agoHaving worked at a telco where our tools would take a minute or more for results to come back, 5-10 second queries that we only do a few (or even a few dozen) times a day is _fine_.
- MichaelGG 10y agoI was thinking more along the lines of SIP tracing for customers, which happens much more frequently for tech support roles, at least in my experience. With a quad core and a single 1TB drive I was able to service 100s of GB a day of SIP with ~1s response times. Use a mix of brute force (for temporary log) then index in background. The interactivity shifts quite a bit when you get close to "instant". Though I know some companies that are content with even 30s query times, but that's gotta limit flexibility.
- karterk 10y agoAlso, see the follow-up post: http://blog.scalyr.com/2014/07/impossible-problems-often-arent/ http://blog.scalyr.com/2014/07/impossible-problems-often-are... In the end, they did have to do some pre-computes (which is better than indexing, but still not 100% on-the-fly resolution).
- Radim 10y agoThis reminded me of another, related task that comes up a lot in machine learning and IR: searching by vectors (rather than keywords). Aka k-NN (k nearest neighbors) search. Just as with fulltext search, there's no shortage of clever approximate algorithms for kNN vector search (with the additional caveat of the "curse of dimensionality"). And just as here, without careful tuning, a well-optimized brute force search blows most "clever", widely popular kNN implementations out of the water on large datasets [1]. There's certainly something to be said for simplicity and good "systems engineering". [1] http://rare-technologies.com/performance-shootout-of-nearest-neighbours-contestants/ http://rare-technologies.com/performance-shootout-of-nearest...
- mempko 10y agoThis is especially true if you can fit all the data on a GPU. GPU is really really good computing cosine distance fast and in parallel.
- mattb314 10y agoYour linked blog post was a really good read, but I'm not totally sure if the correct takeaway was that brute force outperforms "clever" algorithms. Unless I misinterpreted the results, FLANN and Annoy (which implement hierarchical k-means and a binary space partitioning algorithm, respectively) both ran about 100x faster than brute force. Were you referring to the number of libraries the author couldn't get to work? This certainly might be a failure of over complicated algos, but it seemed more like an engineering failure than a performance failure to me.
- Radim 10y agoWell, complex algos and engineering failures go hand in hand :-) The approximative kNNs are superior if done well, no doubt about that. It's just that "doing them well" is a major challenge, even for well-established and well thought out tools, such as scikit-learn. So many things can go wrong, and despite the increased complexity & settling for approximative results, you can end up with worse runtime performance than O(n) brute force... The performance of brute force is pleasantly predictable and stable. I just found the parallels with OP's article (which is on fulltext search, a mostly unrelated field) interesting, that's all.
- makach 10y agoUm, what if their logs grow exponentially or faster..? Will they not struggle using that approach? The article reads like an advertisement to me.
- logicchains 10y agoIn what circumstances would logs grow exponentially? I imagine any approach would have trouble with logs that grew in size that quickly.