Redis on steroids: Autocomplete using Redis, Nginx and Lua (opens in new tab)

(cucumbertown.com)

64 pointsalagu11y ago11 comments

11 comments

This implementation is too naive. You can't just autocomplete queries, you have to accept typos and errors and suggest the correct query. That's the hard part.

taf211y ago

This is great need to figure out a good way to do request verification maybe to ensure the request it properly signed.

Update: this looks like a good article describing a verification scheme http://www.stavros.io/posts/writing-an-nginx-authentication-...

leorocky11y ago

The usual implementation for autocomplete is to generate a trie data structure. A naive implementation will not have auto-correction or fix problems more established implementations have already addressed.

mholt11y ago

True, but tries do not automatically solve those problems, either, and most tries use lots of memory, especially on 64-bit systems (pointers, pointers everywhere!).

guiomie11y ago

I'm currently implementing my own trie (for learning) for my own autocomplete module ... and I don't see how a trie (prefix tree) can solve the issues you just wrote.

mholt11y ago

When you traverse the prefix tree and you are blocked: meaning, the prefix does not match an entry in the structure, you perform edit operations: insert, delete, transpose, and substitute. If one of those garners a match, you keep going down the tree until you reach your edit distance.

leorocky11y ago

It can't. You would have to fix the auto-correction before you searched the trie I'd think.

bithive12311y ago

I love Redis, nginx, and Lua and wrote my own autocomplete implementation using Metaphone (e.g. https://github.com/threedaymonk/text) but after a while it became clear that what I really wanted was an instance of Solr.

muxxa11y ago

I wonder if replacing nginx+lua with http://webd.is/ would be faster (and maybe easier to deploy)?

jzawodn11y ago

Could be.

We build something similar using node.js and it's working quite well. Perhaps we can open source that someday...

_bpo11y ago

nginx+lua can be exceptionally fast. It's the basis for OpenResty, which is a consistent top-performer in the Web Framework Benchmarks (http://www.techempower.com/benchmarks/)

Webdis is a neat project, but I'd be a bit wary of deploying a custom HTTP server written just for Redis interactions. Nginx is battle-hardened.

j / k navigate · click thread line to collapse

11 comments

cliveowen11y ago

This implementation is too naive. You can't just autocomplete queries, you have to accept typos and errors and suggest the correct query. That's the hard part.

taf211y ago

This is great need to figure out a good way to do request verification maybe to ensure the request it properly signed.

Update: this looks like a good article describing a verification scheme http://www.stavros.io/posts/writing-an-nginx-authentication-...

leorocky11y ago

mholt11y ago

True, but tries do not automatically solve those problems, either, and most tries use lots of memory, especially on 64-bit systems (pointers, pointers everywhere!).

guiomie11y ago

I'm currently implementing my own trie (for learning) for my own autocomplete module ... and I don't see how a trie (prefix tree) can solve the issues you just wrote.

mholt11y ago

leorocky11y ago

It can't. You would have to fix the auto-correction before you searched the trie I'd think.

bithive12311y ago

muxxa11y ago

I wonder if replacing nginx+lua with http://webd.is/ would be faster (and maybe easier to deploy)?

jzawodn11y ago

Could be.

We build something similar using node.js and it's working quite well. Perhaps we can open source that someday...

_bpo11y ago

nginx+lua can be exceptionally fast. It's the basis for OpenResty, which is a consistent top-performer in the Web Framework Benchmarks (http://www.techempower.com/benchmarks/)

Webdis is a neat project, but I'd be a bit wary of deploying a custom HTTP server written just for Redis interactions. Nginx is battle-hardened.

j / k navigate · click thread line to collapse