Wiki: Database/Utilities / File Location Listing

The project doesn't currently rely on an external database.

During the initial design it was decided that, to get up and running quickly, rather than worrying about which database to use, we'd just implement something - the idea being that it'd be better to switch once the needs of the project were better understood.

However, the need for that switch hasn't (yet) arisen. Plus, messing about building a storage engine has probably helped keep me engaged.

This page details the inbuilt storage engine.

File Structure

The database relies on an indexed and hashed structure.

The primary key for a resource is it's URL.

In order to navigate the file structure, a hex-encoded SHA256 has of the URL is generated. The subdirectory path is calculated by taking the first and second pairs of characters (for example a080df7b239d9792fb041906cbcf563e095400a1e974f9c6e7766ccea85f32e8 would be found under a0/80).

Storage directories are created in a directory called store.

For resource types that support thumbnails, a thumbnail will be stored under the thumbs directory, using the same subdirectory structure:


On Disk Index

The index is a simple text file, with one entry per line.

Each entry consists of 4 fields separated by the string (,!,)

The format is


For example,!,73518e88ec4fabb0f24c62f79a45e29479e5d278061fd824064f0af951ea1255,!,text/html,!,BTasker Projects -

Although the hash can (obviously) be derived from the key, it's calculated and stored when building indexes to ensure that index loads do not incur unnecessary overhead.

Index Tombstone

The index tombstone is an append-only list of keys.

If an item has been deleted (whether with the delete utility, or as the result of a crawl), its key will be written into the tombstone. The next time search loads the index it will ignore any entries with keys that exist in the tombstone.

This allows deletions to have (almost) instant effect, rather than needing to wait for the index to be rebuilt.

Tags index

The Tags index is gzipped text, introduced in Issue 10

Each line is an entry for a single tag, with the second field being a JSON encapsulated array of keys using that tag.

tag!#![json array]

For example:

facebook!#!["", "
enshot-don-t-embed.html", "", "
.uk/posts/blog/general/playing-around-with-automating-syndication.html", "
ally-isnt-great.html", "", 
"", "
es-privacy-controls-on-facebook-insufficient.html", ""]

There is no Tombstoning of the tags index - the way that it's merged into the main index at load time renders them unnecessary.

Indexing of tags can be disabled by setting environment variable TAGS_ENABLED to n (to enable, set to y or leave empty).

In Memory Index

At index load time, the on-disk indexes are read and transformed into the in-memory index.

First, the tags index (if active) is read in, with two actions being performed for each tag

After this stage, we essentially have two indexes:

# Tag to id
  "foo" : 1, 
  "bar" : 2, 
  "sed" : 3, 

# Site to ids
url_tags = {
   "" : [1, 3],
   "" : [2]

If the tags index isn't active, both of these indexes will be empty.

Next, the main index tombstone (if any) is read in.

The main index is then read in, skipping any entry who's key appears in the loaded tombstone.

Each entry has the following form

idxitem = {
    "u" : index_l[0], # url
    "h" : index_l[1], # index hash
    "t" : index_l[2], # content-type
    "n" : index_l[3], # title/name
    "i" : idx_num, # Index number
    "p" : pth, # path
    "d" : dom, # domain
    "k" : [], # tag IDs

The idx_num is a calculated number used to shard the index, allowing parallelisation at search time.

pth and dom are derived from the key, allowing searches to perform fast prefix and domain matching the index alone.

The index item's key is used to look up associated tag ids (if any) in url_tags so that attribute k can be populated.

The result is something like

idxitem = {
    "u" : "", # url
    "h" : "cdbe3bcae7beadf19f97c277ab08fe7a716e482eff43d5a21cacbdf5e2a04721", # index hash
    "t" : "text/html", # content-type
    "n" : "My example Page", # title/name
    "i" : 1, # Index number
    "p" : "/somepage", # path
    "d" : "", # domain
    "k" : [1, 3], # tag IDs

Once the index has been fully loaded, the in-memory copy of the tombstone and url_tags are discarded.

Storage Files

Storage files are gzipped text files containing headers and a payload:


<JSON payload>

Headers are primarily consumed when building the index and allow index builds to occur without needing to unnecessarily consume potentially large payloads.

If, during, reindexing, it's considered that a file is corrupt, it will be moved to have a file extension of .invalid