Skip to content
This repository has been archived by the owner on Apr 20, 2019. It is now read-only.

peterbe/autocompeter

Folders and files

NameName
Last commit message
Last commit date

Latest commit

43fa2d8 · Jun 29, 2017
Jun 14, 2016
Jun 9, 2016
Sep 8, 2015
Jun 9, 2016
Jun 14, 2016
Sep 8, 2015
Jun 9, 2016
Apr 17, 2015
Jun 14, 2016
Apr 23, 2015
Feb 21, 2015
Apr 23, 2015
Jun 9, 2016
Apr 28, 2016
Jun 9, 2016
Feb 27, 2015
Mar 10, 2015
Jun 29, 2017
Feb 17, 2015
Sep 8, 2015
Apr 23, 2015
Apr 9, 2015
Mar 9, 2015

Repository files navigation

A Go autocomplete Redis server.

Build Status

Documentation

Documentation on Read the Docs

Running tests

Both the unit test and integration test will connect to Redis on database 8. It will do a flush on this database.

To run the unit tests run:

go test -v

To run the end-to-end test run:

nosetests

To run the python end-to-end tests you need to install some dependencies:

pip install -r requirements.txt

Database structure

First we take the domain and hash it into a unique 6 character string. Let's call this E.

Secondly we take the URL and hash it into a unique 6 character string too. Let's call this U. The un-encoded URL we'll called URL.

The popularity is a floating point number. Let's call it P.

For every prefix of every word in every title, e.g. "w", "wo", "wor", "word", we store:

ZADD E+w P U
ZADD E+wo P U
ZADD E+wor P U
ZADD E+word P U

When you use ZADD you're basically storing a "sorted set". I.e. the keys are never repeated (if you two two ZADD with the same key only).

The equivalent in Python would be something like this:

urls = {}
urls[U] = []
urls[U].append((P, E+w))
urls[U].append((P, E+wo))
urls[U].append((P, E+wor))
urls[U].append((P, E+word))

But unlike Python, in Redis you can reverse the search by a key, e.g E+wor and get all URLs sorted by their score.

Next we store a simple hash table of the encoded URL to the un-encoded URL. We do this under a key specific to the domain:

HSET E+$urls U URL

The difference between HSET and HMSET is that you can do multiples with HMSET in one sweep. E.g.:

HMSET E+$urls U1 URL1 U2 URL2 Un URLn

Since the scoring search we use gives us the encoded URL (U) we'll use this hash table to retrieve back to the full un-encoded URL (URL).

The equivalent in Python would be something like:

urls = {}
urls[E+$urls] = {}
urls[E+$urls][U1] = URL1
urls[E+$urls][U2] = URL2
urls[E+$urls][Un] = URLn

Lastly we store a hash table of the encoded URLs to the title (T). This is used so we can retrieve the title back from the encoded URL (U).

HSET E+$titles U T

The equivalent in Python would be:

titles = {}
titles[E+$titles] = {}
titles[E+$titles][U1] = T1
titles[E+$titles][U2] = T2
titles[E+$titles][Un] = Tn

At this point, to retrieve a title (T) back from an encoded URL (U)

Now, if we want to reverse the storage, e.g. remove a URL+title record, we first need to go from URL to title so we can get all its prefixes.

Now we can reverse every ZADD that was done without knowing the popularity. This you do with a ZREM and simply knowing every prefix and its encoded URL.

Once we've removed each prefix, we can remove the title by that encoded URL.

Writing documentation

If you want to work on the documentation, cd into the directory ./doc and make sure you have mkdocs pip installed. (see ./requirements.txt).

Then simple run:

mkdocs build
open site/index.html

If you have a bunch of changes you want to make and don't want to run mkdocs build every time you can use this trick:

mkdocs serve
open http://localhost:8000/