|
|
|
|
|
The DNS cache solution used in libspf is basically just 2 AVL trees: one tree holds all of the relevant DNS result information, while the other tracks the TTLs of the various results in the cache. The purpose of the second tree is to provide a fast and accurate means of removing entries whose TTLs have expired, arranged in such a way that the smallest nodes in the tree (i.e. the furthest to the left) have the best chance at having expired, making the expiry check (and subsequent deletion) exceptionally cheap.
Thanks to the balanced nature of AVL trees, it only takes a handful of comparisons to find a DNS record in the cache. This is slower than, say, a hash table, but unlike hash tables AVL trees can be sized dynamically at runtime. A hash table that ignores collisions can run into situations where frequently referenced cache entries fight over a position in the hash table if the table is not sufficiently large. Hash table sizes are added complication as well, since depending on the hash function used, MTA admins are forced to choose either a prime number or a power of two as a hash table size.
Of course, AVL is not without its own drawbacks. Foremost is the complexity of the insertion and deletion algorithms (namely, deletion). Searches, insertions, and deletions in AVL trees also occur in logarithmic time, while the same operations in hash tables happen in constant time (perhaps not if the table uses chaining of some sort as a means of collision resolution, but close enough). AVL trees also require an extra 8 bytes (on a 32 bit arch) per node for left and right child pointers, but it is conjecture as to whether or not this is a disadvantage since AVL trees do not need a large contiguous data structure in memory (while a hash table does). Both (collision-resolving) hash and AVL implementations would suffer from constant growth if they did not enforce TTL expiry using some method of quickly determining expired entries as described above.
Overall, it was decided that the AVL implementation was best suited for the job due to its size flexibility and, despite having an inferior time complexity when compared to hash, the implementation is still profoundly faster than querying a DNS server. The size flexibility means that libspf could be placed into any situation with no DNS cache configuration whatsoeverand still perform very well; whereas with hash, determining the optimal tablesize would require testing and some knowledge of how hash tables work.
|
|
|
|
|
|
|
Main