A Go autocomplete Redis server.

[![Build Status](](


[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:


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

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/

Imports 13 package(s)


Test imports 2 package(s)