Day 49 - the radix tree: ngx_radix_tree_t

It all started with locations and ended as an exploration in the binary search tree algorithms. That's what I like with this trip: you never know where you are going to end up. So, for today I decided to look into the last tree structure provided by nginx (or at least, the last tree structure I could find). There might be others but I have not run into them...so far.

I already gave you hints at what a radix tree is. I told you the tree used for finding locations is a mix between a radix tree and a binary search tree. I even gave you a link to the wikipedia definition. If you haven't read it, you can look at my post about locations, queues and location trees, find the link, click on it and read the definition (I'm not doing all the link copy/pasting for you this time). So, basically, a radix tree is a tree where each node gets you further down a string. Something like:

/foo/
 \_b
 |  \_ar
 |  |  \_*
 |  \_iz
 |     \_*
 |     \_ness
 |        \_*
 \_crap
    \_*

My ascii-art is just getting better and better... ;) I think I'll make a career switch and become the Warhol of ascii-art. ;) In the meantime, I'll still comment on my masterpieces. Here there is not much to explain except that * denote a dead-end (or a string end if you prefer). Now, the example above contains the following strings:

1. /foo/bar
2. /foo/biz
3. /foo/bizness
4. /foo/crap

Now, let's look at nginx version of a radix tree (or rather at what a node looks like):

typedef struct ngx_radix_node_s  ngx_radix_node_t;
struct ngx_radix_node_s {
    ngx_radix_node_t  *right;
    ngx_radix_node_t  *left;
    ngx_radix_node_t  *parent;
    uintptr_t          value;
};

I can see your face from here: radix trees are not binary trees. Why in hell, do nodes have only a left and a right child. Maybe radix trees are binary trees in disguise. Or fig tree, while we are at it... ;) Well, the real answer is that usually they are not but sometimes they might be. And in the case at hand, they are. So, let's see what is this case.

If you look into the source code you'll see there is only one place where ngx_radix_tree_t is used in nginx code base: the HttpGeoModule. Watch out: don't mistake this module for the HttpGeoIPModule:

1. HttpGeoIPModule creates (and assigns values to) variables based on the IP address of the request client and one of Maxmind GeoIP databases. One of the common uses is to set the country of the end-user as a nginx variable.
2. HttpGeoModule lets you map IP ranges to values. For each request, the resulting value is assigned to a variable of your choice. This is a more generic mechanism but it does not come with its own database of countries so if you were to do what HttpGeoIPModule does with this module, you would have to write your own IP-to-country database (a thing most people don't want to). A quick example:

   geo  $srvr_platform  {
     default          prod;
     127.0.0.1/32     dev;
     192.168.1.0/24   int;
     10.1.0.0/16      preprod;
   }
   

Back to our radix tree. Now you probably guessed that nginx uses a radix tree to store the various IP ranges configured with the geo directive. And storing IP related information is one of the common uses of radix trees.

Here, the string is not made of characters but of bits and the IP-address is just a 32-bit address. And a bit can be only 0 or 1 (at least last time I checked). Therefore, for this use you need a max of two branches out of any node in the tree: one for 0 (the left branch) and one for 1 (the right branch). It also explains why there is no key in the ngx_radix_node_t structure: you don't need it.

Although this is named a radix tree, if you take wikipedia's definition, it's a trie because the nodes with only one child are not "merged together" like they should be in a radix tree. As a consequence, this structure "costs" a bit more memory than it should. However, if you look closely at the code you'll see that Igor put quite some effort in being extra careful with memory allocation (actually pre-allocating a big chunk of memory for this tree) and making sure the extra size does not break performance by generating page faults. That's the way Igor is if you had not figured yet... ;)

Now that you know all this, you should see there is something wrong (and that will become more and more wrong as time goes): this assumes IP addresses are 32 bit long. With IPv6 they are not anymore... Still, they keep their hierarchical nature so everything is not to be thrown away but at least the functions ngx_radix32tree_find, ngx_radix32tree_insert and ngx_radix32tree_delete are in for a serious lifting... Sounds like a nice feature improvement for anyone who cares to submit a patch.