Sambal

Commentor Paul asks why we would use a list instead of a set, since a set has an efficient lower_bound() method and has cheaper insertion/deletion than a sorted vector; set insertion also preserves iterators.

First, recall the the lower_bound() on a list problem is purely a hypothetical, and I’m not using this data structure anywhere.  The point of the series is that the STL lower_bound() algorithm is suboptimal when used with bidirectional and forward iterators, not that you should use lists to store sorted data.

But to answer Paul’s question: they’re different data structures.  I would certainly choose a set if it was the most appropriate data structure for the job: if there were many random access insertions and deletions, only one instance of each key, and the data not dense enough to justify an array or a bit vector.  But a set is not a drop-in replacement for a list.

STL’s set is implemented as a red-black tree.  So the cost of insertion is O( lg N ) to find the insertion point, and potentially another O( lg N ) to rebalance the tree.  With a list, in contrast, it costs O( N ) to find the insertion point and O( 1 ) for each element inserted.

Now you’d have to make a heck of a lot of insertions at one point to make that pay off in the list’s favor.  In general.  

But the situation changes if the data structure is a concurrent shared resource.  With a set, you have to lock the whole data structure for an insertion, because the tree rebalancing operation can touch quite a few nodes and the tree is in an inconsistent state until the rebalance completes.

But with a list, you can use hand-over-hand locking during the search and also during the insertion, locking only the two nodes where the insertion occurs.  So a list offers better behavior with multiple concurrent accesses.

Finally, even if you use a set, you can’t take advantage of its efficient lower_bound method while using generic programming.  You’d have to know the data structure was a set.  In code:

set s<int>;
list l<int>;
// populate data structures
s.lower_bound( 5 );  // this is fast
lower_bound( l.begin(), l.end(), 5 ); // this is slow

// this is slow too because it can't use s.lower_bound()
lower_bound( s.begin(), s.end(), 5 );

Obviously if you’re in the scope that s is declared, you know it’s a set.  But if you have a generic routine that takes an iterator pair and then uses lower_bound(), you don’t get any benefit from using a set.

In a dynamic language such as Ruby, it doesn’t matter how the lower_bound method gets called: it ultimately would dispatch to the class-specific one if it existed.  But in C++ / STL generic programming, where you would use the lower_bound() template function defined in <algorithm>, all STL knows is what type of iterator it is, by looking at the iterator tag.  Both list and set have bidirectional iterators.

I’m not even sure it would work to try to provide specializations for lower_bound specific to sets —

template< class T >
set<T>::iterator lower_bound(
  set<T>::iterator first, set<T>::iterator last, const T& v )
{// and so on, for set<T>::const_iterator
// and don't forget multiset and reverse iterators too!

Because to my relatively untutored C++ eyes, that looks like a partial template specialization of a function, and those aren’t allowed.  And even if they were, how do you get from the iterator to the parent object in order to call its lower_bound() method?

You know you’ve been coding for the Intel platform too long when “eax” looks more like a word than “wax”.

I typed “wax”; it looked wrong, so I semi-consciously backspaced out and retyped it as “eax”. Which looked more correct. Then my conscious mind realized I really did want “wax” so I changed it back.

Here are the before and after pictures. We used to have two independent single points of failure.

If boris was down, nobody could get an IP address, and internal name resolution didn’t work because the cache couldn’t see the tinydns server (on boris) that is authoritative for the internal network.

If draco the firewall was down, not only could nobody connect to the internet (after all, that is the point of having a firewall), and external name resolution didn’t work. But internal name resolution didn’t work either, because the single caching name server (dnscache) lived on draco.

That’s a result of the “djb way,” where name servers are separate from caches. Tinydns won’t answer queries for a domain which it’s not authoritative over, and dnscache won’t ever give an authoritative answer, but only process requests from clients, get answers from authoritative servers, and cache the results.

In the new setup, there are no single points of failure for dhcp or name service. (There’s still a single firewall host.) We moved all functions off of boris, which is slated for decommissioning.

Draco keeps a dnscache, since it has easy access to outside name servers. It picks up a dhcpd server and associated tinydns. I made it the dhcpd master, because it’s the least-frequently-rebooted server.

Since dnscache and tinydns use the same port (53/udp, the domain service), I had to configure an ethernet alias on draco to serve the tinydns off of. (I couldn’t use localhost, because it needs to be visible to the other dnscache server if the other tinydns server is down.)

Taurus, a new machine still figuring out its identity (external web/intranet/wiki/login/database/…?), gets the dhcpd slave server and an associated tinydns. At first I thought it made sense to separate the dhcpd from the tinydns server, but eventually I recognized that if one dhcpd server was down, it would not do any good to be trying to fetch its dhcpd.leases file to build a dns table. The functions are so closely associated — dhcp gives named hosts an IP address while tinydns reports what the IP address is.

Scorpio, the backup server (BackupPC/snapback), picks up an additional function as an internal name cache. That was a last-minute decision when I realized I needed a second name cache, and I’m not entirely happy about it. Since scorpio carries backup data, I’d like to be able to unplug it and take it offsite (e.g., if I’m reconstructing a crashed machine from its backups) without disrupting the network. So that’s going to have to change. I suppose there’s no deep reason why I can’t put the dnscache on taurus, but I’d have to configure another alias…

That’s the overall layout for redundant dhcpd and internal name service using tinydns and dnscache. Next post: “challenges” (aka annoying problems) I encountered making this work.

DHCP assigns IPs to hosts; DNS reports IPs by hostname. The popular dhcp server is even written by the folks who brought you BIND.

But in our shop, we run djbdns.

I am not a full convert to the djb way. (We run postfix, for example.). I have never met the man in person. I would probably find him infuriating. But I find his claims about BIND and DNS convincing. And I’ve been using his software for the last eight years without a major glitch.

I selected djbdns when I was setting up DNS for my first real website. I had bought the DNS and BIND O’Reilly book and was puzzling through the man pages and just feeling stupider and stupider the more time I spent on it. I figured there must be a better way, so I looked around and found djbdns. The setup instructions were clear and simple. I followed them and everything worked. I felt smart and competent.

Users like software that makes them feel good. There’s a lesson for us all there, I suspect.

Anyway, one of the quirks of djbdns is it doesn’t honor UPDATE requests. Unsecure, you see. Which makes it hard to do DHCP….