| 1 |
<!-- X-URL: http://www.libspf.org/api_cache.html --> |
| 2 |
<!-- Date: Sun, 04 Jul 2004 05:09:17 GMT --> |
| 3 |
<!-- Last-Modified: Thu, 24 Jun 2004 03:59:55 GMT --> |
| 4 |
|
| 5 |
<BASE HREF="http://www.libspf.org/api_cache.html"> |
| 6 |
|
| 7 |
<html> |
| 8 |
<title>libspf.org - The Official ANSI C SPF Library</title> |
| 9 |
<head> |
| 10 |
<style text/css> |
| 11 |
<!-- |
| 12 |
body |
| 13 |
{ |
| 14 |
background: #FFFFFF url(images/bg.gif); |
| 15 |
margin: 10px 0px 10px 0px; |
| 16 |
color: #FFFFFF; |
| 17 |
} |
| 18 |
|
| 19 |
table.encapsulate |
| 20 |
{ |
| 21 |
border: 0px; |
| 22 |
} |
| 23 |
|
| 24 |
table.main |
| 25 |
{ |
| 26 |
border: 0px; |
| 27 |
background: #FFFFFF; |
| 28 |
} |
| 29 |
|
| 30 |
table.menu |
| 31 |
{ |
| 32 |
border: 0px; |
| 33 |
background: #2F628D; |
| 34 |
} |
| 35 |
|
| 36 |
table.news |
| 37 |
{ |
| 38 |
border: 0px; |
| 39 |
background: #2F628D; |
| 40 |
} |
| 41 |
|
| 42 |
td.menu_header |
| 43 |
{ |
| 44 |
width: 125px; |
| 45 |
background: #4C7FAA; |
| 46 |
padding: 3px 3px 3px 3px; |
| 47 |
vertical-align: top; |
| 48 |
font: normal normal bold 12px sans-serif, arial, verdana; |
| 49 |
} |
| 50 |
|
| 51 |
td.menu_body |
| 52 |
{ |
| 53 |
width: 125px; |
| 54 |
padding: 3px 3px 3px 3px; |
| 55 |
vertical-align: top; |
| 56 |
font: normal normal normal 12px sans-serif, arial, verdana; |
| 57 |
} |
| 58 |
|
| 59 |
td.main |
| 60 |
{ |
| 61 |
width: 545px; |
| 62 |
padding: 5px 5px 5px 5px; |
| 63 |
vertical-align: top; |
| 64 |
font: normal normal normal 12px sans-serif, arial, verdana; |
| 65 |
} |
| 66 |
|
| 67 |
td.news_header |
| 68 |
{ |
| 69 |
background: #4C7FAA; |
| 70 |
padding: 3px 3px 3px 3px; |
| 71 |
vertical-align: top; |
| 72 |
font: normal normal bold 10px sans-serif, arial, verdana; |
| 73 |
} |
| 74 |
|
| 75 |
td.news_body |
| 76 |
{ |
| 77 |
padding: 3px 3px 3px 3px; |
| 78 |
vertical-align: top; |
| 79 |
font: normal normal normal 12px sans-serif, arial, verdana; |
| 80 |
} |
| 81 |
|
| 82 |
A:link |
| 83 |
{ |
| 84 |
text-decoration: underline; |
| 85 |
color: #ffffff; |
| 86 |
} |
| 87 |
|
| 88 |
A:visited |
| 89 |
{ |
| 90 |
text-decoration: underline; |
| 91 |
color: #ffffff; |
| 92 |
} |
| 93 |
|
| 94 |
A:active |
| 95 |
{ |
| 96 |
text-decoration: underline; |
| 97 |
color: #ffffff; |
| 98 |
} |
| 99 |
|
| 100 |
A:hover |
| 101 |
{ |
| 102 |
text-decoration: none; |
| 103 |
color: #ffffff; |
| 104 |
} |
| 105 |
|
| 106 |
--> |
| 107 |
</style> |
| 108 |
</head> |
| 109 |
<body> |
| 110 |
|
| 111 |
<!-- File: index.html --> |
| 112 |
<!-- Author: James Couzens <jcouzens@codeshare.ca> --> |
| 113 |
<!-- Date: July 2, 2004 --> |
| 114 |
<!-- Info: API Cache explanation --> |
| 115 |
|
| 116 |
<table align="center" class="encapsulate" cellspacing="0" cellpadding="0"> |
| 117 |
<tr> |
| 118 |
<td colspan="5" style="height: 1px; background-color: #9C9C9C"></td> |
| 119 |
</tr> |
| 120 |
|
| 121 |
<tr> |
| 122 |
<td style="width: 1px; height: 2px; background-color: #9C9C9C"></td> |
| 123 |
<td colspan="3" style="width: 2px; height: 2px; background-color: #FFFFFF"></td> |
| 124 |
<td style="width: 1px; height: 2px; background-color: #9C9C9C"></td> |
| 125 |
</tr> |
| 126 |
<tr> |
| 127 |
<td style="width: 1px; background-color: #9C9C9C"></td> |
| 128 |
<td style="width: 2px; background-color: #FFFFFF"></td> |
| 129 |
<td> |
| 130 |
|
| 131 |
<table class="main" cellspacing="1" cellpadding="0"> |
| 132 |
<tr> |
| 133 |
<td style="background-color: #E5E5E5"> |
| 134 |
<img src="images/top_envelope.gif"><br> |
| 135 |
<img src="images/top_header.png"> |
| 136 |
</td> |
| 137 |
</tr> |
| 138 |
<tr> |
| 139 |
<td style="height: 2px; background-color: #22537C"></td> |
| 140 |
|
| 141 |
</tr> |
| 142 |
<tr> |
| 143 |
<td style="background-color: #22537C"> |
| 144 |
<table class="encapsulate" cellspacing="0" cellpadding="5"> |
| 145 |
<tr> |
| 146 |
<td style="vertical-align: top"> |
| 147 |
|
| 148 |
<!-- start main menu table --> |
| 149 |
<table class="menu" cellpadding="0" cellspacing="0"> |
| 150 |
<tr> |
| 151 |
<td class="menu_header"><img src="images/plus.gif" align="center"> Main</td> |
| 152 |
|
| 153 |
</tr> |
| 154 |
<tr><td style="height: 1px; background: #FFFFFF"></td></tr> |
| 155 |
<tr><td style="height: 1px; background: #1C4C74"></td></tr> |
| 156 |
<tr> |
| 157 |
<td class="menu_body"> |
| 158 |
<!-- left menu area --> |
| 159 |
· <a href=/index.html target=_self>News</a><br> |
| 160 |
· <a href=/api_index.html target=_self>API / Docs <br> |
| 161 |
· <a href=/files.html target=_self>Download</a><br> |
| 162 |
· <a href=http://forums.6o4.ca/ target=_blank>Forums</a><br> |
| 163 |
· <a href=mailto:jcouzens@6o4.ca>Contact</a><br> |
| 164 |
|
| 165 |
</tr> |
| 166 |
<tr><td style="height: 1px; background: #5588B3"></td></tr> |
| 167 |
</table> |
| 168 |
<!-- end main menu table --> |
| 169 |
|
| 170 |
<br> |
| 171 |
|
| 172 |
<!-- start API Navigation table --> |
| 173 |
<table class="menu" cellpadding="0" cellspacing="0"> |
| 174 |
<tr> |
| 175 |
<td class="menu_header"><img src="images/plus.gif" align="center"> API Navigation</td> |
| 176 |
</tr> |
| 177 |
|
| 178 |
<tr><td style="height: 1px; background: #FFFFFF"></td></tr> |
| 179 |
<tr><td style="height: 1px; background: #1C4C74"></td></tr> |
| 180 |
<tr> |
| 181 |
<td class=menu_body> |
| 182 |
· <a href=/api_index.html target=_self>API Index</a><br> |
| 183 |
· <a href=/api_main.html target=_self>Public Functions</a><br> |
| 184 |
· <a href=/api_header.html target=_self>Structures</a><br> |
| 185 |
· <a href=/api_cache.html target=_self>DNS cache</a><br> |
| 186 |
· <a href=/api_avl_tree.html target=_self>AVL Tree Demo</a><br> |
| 187 |
· <a href=/api_example.html target=_self>Example Code</a><br> |
| 188 |
</td> |
| 189 |
</tr> |
| 190 |
</table> |
| 191 |
<!-- end API Navigation table --> |
| 192 |
|
| 193 |
</td> |
| 194 |
<td class="main"> |
| 195 |
|
| 196 |
<!-- start libspf DNS cache explanation --> |
| 197 |
|
| 198 |
<table class=news cellpadding=0 cellspacing=0 border=0> |
| 199 |
<tr> |
| 200 |
<td class=news_header>libspf's DNS caching explained...</td> |
| 201 |
</tr> |
| 202 |
|
| 203 |
<tr><td style="height: 1px; background: #FFFFFF"></td></tr> |
| 204 |
<tr><td style="height: 1px; background: #1C4C74"></td></tr> |
| 205 |
<tr> |
| 206 |
<td class=news_body> |
| 207 |
The DNS cache solution used in libspf is basically just 2 <a href=/api_avl_tree.html target=_self>AVL trees</a>: 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.<br> |
| 208 |
<br> |
| 209 |
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.<br> |
| 210 |
<br> |
| 211 |
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.<br> |
| 212 |
<br> |
| 213 |
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.<br> |
| 214 |
<br> |
| 215 |
</td> |
| 216 |
</tr> |
| 217 |
<tr><td style="height: 1px; background: #5588B3"></td></tr> |
| 218 |
</table> |
| 219 |
|
| 220 |
<!-- end libspf DNS cache explanation --> |
| 221 |
|
| 222 |
</td> |
| 223 |
|
| 224 |
</tr> |
| 225 |
</table> |
| 226 |
</td> |
| 227 |
</tr> |
| 228 |
<tr><td style="height: 2px; background-color: #22537C"></td></tr> |
| 229 |
<tr><td style="height: 10px; background-color: #4C7FAA"></td></tr> |
| 230 |
<tr><td style="height: 20px; background-color: #E5E5E5"></td></tr> |
| 231 |
</table> |
| 232 |
</td> |
| 233 |
|
| 234 |
<td style="width: 2px; background-color: #FFFFFF"></td> |
| 235 |
<td style="width: 1px; background-color: #9C9C9C"></td> |
| 236 |
</tr> |
| 237 |
<tr> |
| 238 |
<td style="width: 1px; height: 2px; background-color: #9C9C9C"></td> |
| 239 |
<td colspan="3" style="width: 2px; height: 2px; background-color: #FFFFFF"></td> |
| 240 |
<td style="width: 1px; height: 2px; background-color: #9C9C9C"></td> |
| 241 |
</tr> |
| 242 |
<tr> |
| 243 |
|
| 244 |
<td colspan="5" style="height: 1px; background-color: #9C9C9C"></td> |
| 245 |
</tr> |
| 246 |
</table> |
| 247 |
<br> |
| 248 |
<font face="verdana, sans-serif, arial" size=1 color=#4C7FAA><center>site design by Travis Anderson</center> |
| 249 |
</font> |
| 250 |
</body> |
| 251 |
</html> |
