You'd be even more surprised what they used before tinydns. :D They wanted speed and robustness, and iterated over quite a few choices including roll-yer-own.

Source: I created a pilot project called "Doppler" that was eventually folded into this system. http://carlos.bueno.org/2011/07/doppler.html