Show HN: We built a fast substring search engine in Go

http://www.tamber.com/posts/ferret.html

by alexirobbins • 13 years ago

145 41 13 years ago

jph• 13 years ago

Is this related to the Ferret search engine for Ruby? https://en.wikipedia.org/wiki/Ferret_search_library

kalv• 13 years ago

I thought the same and was going to mention something. Seeing 'Ferret' alongside search brought up bad experiences with that Ruby library.

But it looks like this Go library is not based on Lucene which the Ruby version one was and I don't think that Ruby version is maintained anymore so maybe it's not a problem to have the same name.

argusdusty7• 13 years ago

Author here: They are unrelated.

We did take the time to examine writing our own full search engine based on Lucene, like the aforementioned search library. The reasons why we didn't are briefly mentioned in the blog post, but simply put, we found Lucene too bloated for our purposes (intended for large-scale data retrievals, among many other things). We just needed a low-cost search over a relatively small dictionary, which could be used in an auto-complete field without stealing resources from other processes, such as our recommendation engine.

microtonal2• 13 years ago

It's nice to see suffix arrays being used in the real world. For anyone who is interested in suffix arrays, the following to papers are recommended:

* Sufﬁx arrays: A new method for on-line string searches, U Manber, G Myers, 1993

* Using Suffix Arrays to Compute Term Frequency and Document Frequency for All Substrings in a Corpus, M Yamamoto, KW Church, 2001

The second paper actually uses an 'inverted index' for matching sequences to documents.

ramayac• 13 years ago

URL of the paper: "Using Suffix Arrays to Compute Term Frequency and Document Frequency for All Substrings in a Corpus, M Yamamoto, KW Church, 2001"

http://acl.ldc.upenn.edu/J/J01/J01-1001.pdf

Scaevolus3• 13 years ago

Suffix arrays are useful for approximate matches too-- they're used by the binary delta program BSDiff[1] to match similar code sequences. BSDiff is used in Google products (Including Chrome)[2] and Firefox's delta updates.

[1] http://www.daemonology.net/papers/bsdiff.pdf [2]: It performs additional preprocessing to make updates smaller (Courgette).

LukeShu• 13 years ago

Courgette isn't BSDiff, it is Google's replacement for/improvement upon BSDiff. They were using BSDiff for Chrome updates before they switched to Courgette.

fnl• 13 years ago

It's nice to see suffix arrays being used in the real world.

You are apparently not working in Bioinformatics. Suffix arrays are used a LOT here, but rather the more advanced stuff like the BWT. Although, maybe Genomics and Next Generation Sequencing technology are not very "real worldy" to most... :)

drsintoma• 13 years ago

nice. I've been waiting to see some full-text search engine in Go for a while to compete with the omnipresent Lucene. Things like Go's low memory footprint could give it an important advantage in this area. This looks like a first step in that direction.

microtonal2• 13 years ago

Things like Go's low memory footprint could give it an important advantage in this area.

You know that there is a C++ version of Lucene?

http://clucene.sourceforge.net/

There's also Xapian, which is built in C++:

http://xapian.org/

So, if Java's footprint is a concern, there are alternatives.

nkurz• 13 years ago

I hadn't realized that CLucene was still active, thanks!

Apache Lucy is another option that might appeal if you consider Lucene bloated. It's written in C, and while there aren't Go bindings yet, there's great interest in providing them and a couple people starting on them: http://mail-archives.apache.org/mod_mbox/lucy-user/201308.mb...

vidarh• 13 years ago

As for other non-Java Lucene alternatives, Sphinx works great, is compact and the C++ code is fairly easy to pick up enough of to make modifications if needed:

http://www.spingxsearch.com

mumrah• 13 years ago

Since 4.0, Lucene's memory usage has dropped quite a bit actually.

moondowner• 13 years ago

There are a lot of good people working on Lucene, and every year good contributions come via GSoC.

gwu78• 13 years ago

There are certainly alternatives to Lucene.

What about idzebra? It's written in C, it predates Lucene and it was used as the indexing system for Harvest (the origin of Squid).

What is more likely than "low memory footprint" to give an indexing system written in Go an advantage over alternatives is the marketing of Go. It seems the language is being promoted nearly every day on HN's front page. If this is any indication of usage trends among developers, the Go Authors must be pleased.

Scaevolus3• 13 years ago

Related: Russ Cox wrote and documented a miniature version of Google Code Search (a fast regex search engine) in Go: http://swtch.com/~rsc/regexp/regexp4.html

Using a Suffix Array should make it possible to do fuzzy matching easily, but I haven't examined precisely how they combined it with an inverted index.

fleitz3• 13 years ago

Amazing, servicing thousands of users for $150 a month.

I'd clearly start writing my own indexing engine instead of using Posgresql, or maybe switching to digital ocean/hetzner.

pjscott• 13 years ago

You don't know the size of their dataset, or the number of queries per second they need to support, or the latency requirements they have to meet. They do, and found that the obvious solution -- prefix queries on B-trees -- was too slow in practice. That their actual measurements trump your sarcasm, and you would know this if you'd read beyond the first paragraph before contemptuously dismissing the whole thing.

fleitz3• 13 years ago

You don't know that I didn't read the whole article, and since I did I know their dataset is < 8GB because they are running EC2 medium instances and they said they have a budget of $150 which means they have a max of 2 servers. Also because I read the code I know it doesn't write to disk which means the dataset has to fit in RAM unless they are relying on the pager to swap memory for them.

Since an 8 GB dataset is a fucking joke I made fun of their post in a sarcastic way.

Also databases that lock are a fucking joke too, maybe I'll just repeat webscale a few times and that will make it performant.

Should be titled "Startup throws out Mongo DB, gets decent performance"

fspeech• 13 years ago

Very cool. Considering that the core functionality you want is done in less than 500 LOC (https://github.com/argusdusty/Ferret/blob/master/ferret.go) it seems a great way to go :) instead of depending on a large external library. OTOH you could have probably just as easily written it in another performant language. But since Go happens to be performant and is already used in other parts of your project things just turned out great for you.

rorrr2• 13 years ago

$150/month can buy you a very very good dedicated server.

http://www.hetzner.de/en/hosting/produkte_rootserver/ex10

argusdusty7• 13 years ago

The $150 per month includes several other servers we run. The server running our core app backend costs under half that, and handles our requirements just fine. Spending another $80 per month to save me development time is a cost we, as a poorly funded startup, simply cannot afford.

thedufer5• 13 years ago

What are you valuing your time at? That sounds like shaky logic at best, especially considering how much work it sounds like this took.

adcuz• 13 years ago

Future HN headline: "Startup accelerator written in Go"

oron• 13 years ago

doesn't work for me ... looks like it's stuck

6thSigma• 13 years ago

Clicking on the logo gives a 404 error by the way.

argusdusty7• 13 years ago

Thanks for the heads-up. It should be working now.

DrJosiah2• 13 years ago

There are two methods that are more typically known in the context of substring search that may help you get something even better than your prefix + Levenshtein distance 1 searches.

The first and most common is stemming, it can be useful, but it requires a lot of hand tuning and doesn't get you all that much (at least in my experience).

The second is using phonetics of words themselves to try to figure out what someone meant to type in. The grand-daddy of these is Soundex, which works, but isn't as good as Metaphone. Metaphone and Double Metaphone are algorithms that translate most latin-alphabet languages into possible abbreviated phonemes.

Double Metaphone, in particular, has allowed me to build spelling-agnostic prefix matching as an effectively trivial service for two different companies (the details of which you can read about in the Redis mailing list, and/or section 6.1.2 in my book, Redis in Action). The long and short of it is that if you used double metaphone, for the cost of 2-3x index size, you could get all of the results you are looking for in 2-3 searches instead of length(word) searches.

damian2000• 13 years ago

I'd say having spelling agnostic search would be crucial. I searched yesterday on google play music for an artist I'd heard of that sounded something like "n door" so I typed that and he came up as the top hit... "Youssou N'Dour". For this ferret search engine all I get is "Nas".

argusdusty7• 13 years ago

This is a good idea :) I'll probably add in a module for phonetic matching when I get the time.

DrJosiah2• 13 years ago

A good idea is using a paper towel to open the door on your way out of a public restroom.

This is practical advice based on experience over several months of research and development scattered over 9 years. ;)

thedufer5• 13 years ago

Reading from the harddrive is very slow.

Why were you reading from harddrive with Mongo? Prefix indexing is the only kind of string indexing that Mongo does, but it does a pretty good job with it. You must have a pretty large dataset if it couldn't keep the index in memory.

It could be easily hit with a regex injection

It should be pretty easy to regex-escape the search string. Easier than building a substring searching engine.

It couldn't handle artists with multiple names

That sounds like a data format issue.

What I'm getting at is that, while the prefix-only issue might have been enough to justify this switch, none of your other reasons make a ton of sense to me.

diego• 13 years ago

This is cool. However, I wonder why the author didn't switch to a Lucene-based server such as Elasticsearch or Solr, for which you can find decent Go clients (or use the REST api directly). The NGram tokenizer lets you do infix search out of the box. By the way, the author says Lucene is "bloated." That's just nonsense, like saying MySQL is "bloated." LinkedIn and Twitter use Lucene to handle insane numbers of QPS with real-time updates. There is no excuse for not trying a search server before deciding to hack something new.

My impression from reading the post is that they went from an extremely inefficient solution straight to one that seems way overengineered for the company's scale. The app has only 28 ratings on iTunes, which means that it's not greatly popular ($150/month is not much more than my personal AWS bill).

My guess is that the highest ROI of this code (besides the joy of hacking) comes from the HN page views. Usually, optimizing software to this level is a bad idea for a small startup. You're not Twitter, Github, DropBox. Code less and grow your business more.

Show HN: We built a fast substring search engine in Go

Related Stories