Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Searching 20 GB/sec: Systems Engineering Before Algorithms

blog.scalyr.com

Post reply on HN
Print view View original

51–60 of 87 posts

Re: Searching 20 GB/sec: Systems Engineering Before Algorithms

#51

Post by twic »

jfasi wrote: post #15
j2kun wrote: post #13

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.

Moreover, however fancy Boyer-Moore is, the data structure it is being applied to is incredible simple. There are no inverted indexes, B-trees, etc - just a string.

Re: Searching 20 GB/sec: Systems Engineering Before Algorithms

#52

Post by vinkelhake »

justin66 wrote: post #36
vinkelhake wrote: post #23

I wrote a simple code search tool a number of years ago that had the ability to run arbitrary regex queries on a codebase, much like a recursive grep. I was working on a medium sized codebase and our primary platform was Windows. The problem with grep was that opening and scanning lots of small files apparently wasn't something that Windows was optimized for. If the file cache was cold, a simple search could turn int…

> The problem with grep was that opening and scanning lots of small files apparently wasn't something that Windows was optimized for. It's something hard disk drives were not optimized for.

Windows is (or at least was) a dog when it comes to this even if the files are in the cache. Like barrkel said, the number I quoted was for the case when the OS doesn't hit the drive.

Re: Searching 20 GB/sec: Systems Engineering Before Algorithms

#53

Post by neilk »

patio11 wrote: post #3

This comes up in my work modestly frequently, generally with a slightly different scenario for the tradeoff between "complicated and considered" versus "cheap and dirty but gets the job done." e.g. We could spend 3 weeks using feature vectors and backtesting against prior data to figure out what signals accounts which are likely to churn send (for the purpose of proactively identifying them and attempting to derisk t…

I see what you're saying, but the article was not about "cheap and dirty" at all. They describe a precisely tuned system, riding on the controlled application of brute force. Like a rocket to Mars.

It reminds me a lot of the paper that Poul-Henning Kamp wrote about "1975 programming". Few of us really appreciate how to use modern hardware. https://www.varnish-cache.org/trac/wiki/ArchitectNotes

Re: Searching 20 GB/sec: Systems Engineering Before Algorithms

#54

Post by sharkbot »

snewman wrote: post #44
retube wrote: post #12

In order to facilitate sub-word or wildcard searches can't you use a keycharacter index instead of a keyword index?

Yes, you can go down that road [0], and in some applications it's a good approach. However, it adds quite a bit of complexity, and the cost for creating and storing the index is substantial. For us, it doesn't pencil out to a win. [0] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.362...

I wonder if bitap [0] would be a good fit for the 4K search algorithm. It would let you do linear-time regexp matching for relatively short patterns (32 characters on a 32-bit machine, 64 characters on 64-bit, etc).

[0] http://en.wikipedia.org/wiki/Bitap_algorithm

Re: Searching 20 GB/sec: Systems Engineering Before Algorithms

#55

Post by Wilya »

jcampbell1 wrote: post #37
ddorian43 wrote: post #32

Look at their pricing. The best gb/$ public plan, is 500$ month for (worst case scenario) 300gb of data at all time. With that price, you can keep most of the data in memory-ssd and don't care to use fancy-algorithm. But what if the pricing was 10x lower ?

300 GB of ram, is going to cost ~ $3000/month. Reading 300GB from an SSD is going to be way too slow. It will take minutes per search. In a simple test on linode, the SSD seems to read at about 1GB/s. Their pricing seems like a bargain to me.

300GB of ram might cost $3000/month on AWS. There are a few dedicated server providers that offer 384GB or even 512GB configs for less than 1000$/month.

Re: Searching 20 GB/sec: Systems Engineering Before Algorithms

#56

Post by dragontamer »

TheSOB888 wrote: post #47
dragontamer wrote: post #29

I’d certainly seen this at Google, where they’re pretty good at that kind of thing. But at Scalyr, we settled on a much more brute-force approach: a linear scan through the log Art of Computer Programming mentions this methodology, and the importance of learning about it. There are entire sections of "Tape Algorithms" that maximize the "brute force linear scan" of tape drives, complete with diagrams on how a hypothet…

Why would you need a B-tree when you only append to the end of the logs?

    We use some special tricks for searches that are executed 
    frequently, e.g. as part of a dashboard. (We’ll describe 
    this in a future article.)
And...

    (You might wonder why we store log messages in this
     4K-paged, metadata-and-text format, rather than
     working with raw log files directly. There are many 
     reasons, which boil down to the fact that internally,
     the Scalyr log engine looks more like a distributed 
     database than a file system. Text searches are often 
     combined with database-style filters on parsed log 
     fields; we may be searching many thousands of logs at 
     once; and simple text files are not a good fit for our 
     transactional, replicated, distributed data 
     management.)
It sounds like they're doing more than just "appending to the end of the log". If you're going to make an index of any kind, the index will likely be fastest with some sort of B-Tree.

Re: Searching 20 GB/sec: Systems Engineering Before Algorithms

#57

Post by eternalban »

neilk wrote: post #53
patio11 wrote: post #3

This comes up in my work modestly frequently, generally with a slightly different scenario for the tradeoff between "complicated and considered" versus "cheap and dirty but gets the job done." e.g. We could spend 3 weeks using feature vectors and backtesting against prior data to figure out what signals accounts which are likely to churn send (for the purpose of proactively identifying them and attempting to derisk t…

I see what you're saying, but the article was not about "cheap and dirty" at all. They describe a precisely tuned system, riding on the controlled application of brute force. Like a rocket to Mars. It reminds me a lot of the paper that Poul-Henning Kamp wrote about "1975 programming". Few of us really appreciate how to use modern hardware. https://www.varnish-cache.org/trac/wiki/ArchitectNotes

This approach is precisely what PHK was arguing against. That position paper basically says "Go ahead and do the logically correct thing and let the OS and VM (memory) take care of making it efficient".

Re: Searching 20 GB/sec: Systems Engineering Before Algorithms

#58

Post by CHY872 »

a8da6b0c91d wrote: post #19

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…

Heard the same thing from Bjarne Stroustrup. The cache properties of vectors are incredible.

Re: Searching 20 GB/sec: Systems Engineering Before Algorithms

#59

Post by lifeisstillgood »

phserr wrote: post #42
lifeisstillgood wrote: post #30

Earlier quoted context omitted.

Amazing how much work 'simple' is :-) I am reminded of John Carmack's comment on Oculus - he was amazed that the hardware had the power but the headsets performed badly - then he looked at the code and saw seas of abstractions on abstractions. Good luck stripping out the layers guys !

Has he written anything (or talked) about this experience or was it just a brief comment? I'd love to read it if he did.

I just remember a documentary / interview - iirc a five minute interview at a trade show. It stuck in my head. I am afraid I cannot find the link now but trade show / two people sitting down, a demo of oculus rift then comments.

Re: Searching 20 GB/sec: Systems Engineering Before Algorithms

#60

Post by lifeisstillgood »

innguest wrote: post #40
lifeisstillgood wrote: post #30

Earlier quoted context omitted.

Amazing how much work 'simple' is :-) I am reminded of John Carmack's comment on Oculus - he was amazed that the hardware had the power but the headsets performed badly - then he looked at the code and saw seas of abstractions on abstractions. Good luck stripping out the layers guys !

Interesting. That must be why C/C++ is always the go-to solution. Instead of thinking "too many abstractions are making this code slow, therefore let's get rid of the abstractions" I usually had rather pick a better language where abstractions have little or no penalty (Haskell, Scheme, etc).

Maybe we are talking about different abstractions. Perhaps libraries? I reimplemented (probably badly) session handling code in wsgi (python) - because the Django code was over 2000 lines long and used other libraries and I did not understand it - especially when all I wanted was to store a 128bit number in a client cookie and then look it up when I saw it again.

So the idea is simple (cookie sessions) but the different ways of implementing it can hold complexity, errors and abstractions.

There is nothing stopping the same happening with Haskell - I can I am sure write terrible code even in the best languages (see my entire output for proof :-)

Post reply on HN