DNS Cache implementieren - sinnvoll?

[Robert S. (razer)]

Hallo an alle,

Ich schreibe gerade meinen eigenen TCP/IP Stack für einen ARM Cortex M3 
und bin gerade beim DNS Resolver.

Ich habe mir überlegt ich implementiere einen Cache, indem ich die 
letzten 10 Anfragen speichere. Jeder Eintrag hat eine Leasetime die bei 
jedem Zugriff zurückgesetzt wird und nach einer bestimmten Zeit abläuft. 
Um jeden Eintrag eindeutig identifizieren zu können habe ich mir gedacht 
ich speichere eine CRC aus Querry-Adresse.

Ist dieses Konzept so eine gute Lösung?

Danke im Voraus
lg Robert

[Karl H. (kbuchegg)]

Ich denke mal bei 10 Einträgen ist die CRC Berechnung langsamer, als wie 
wenn du in einer Schleife mittels strcmp einfach alle DNS Namen 
durchgehst.
Bei so kleinen Datenmengen muss man immer berücksichtigen, dass man 
jegliche 'Beschleuniger' auch nicht umsonst bekommt.

[Jörg W. (dl8dtl) (Moderator)]

Robert S. schrieb:

> Jeder Eintrag hat eine Leasetime die bei
> jedem Zugriff zurückgesetzt wird und nach einer bestimmten Zeit abläuft.

Die Antwort eines DNS-Servers beinhaltet ohnehin eine Gültigkeits-
dauer.  Das sollte deine obere Schranke für das Caching sein.  Falls
der Cache überfüllt wird, musst du ggf. vorher Einträge rauswerfen.

CRCs sind so konzipiert, dass sie bestmöglich Bitfehler bei einer
bitorientierten Übertragung erkennen können, für allgemeine Hashes
gibt's andere Algorithmen.  Wenn du sowas machst, musst du natürlich
immer die Möglichkeit von hash collisions mit einbeziehen.

[Robert S. (razer)]

Karl heinz Buchegger schrieb:
> Ich denke mal bei 10 Einträgen ist die CRC Berechnung langsamer, als wie
> wenn du in einer Schleife mittels strcmp einfach alle DNS Namen
> durchgehst.
> Bei so kleinen Datenmengen muss man immer berücksichtigen, dass man
> jegliche 'Beschleuniger' auch nicht umsonst bekommt.

Da der Domainname 255 Zeichen lang sein kann, wird der DNS Chache 
ziemlich groß. Da ich RAM beschränkt bin denke ich ist es keine gute 
Idee.

Der Hash muss ja für jede Querry nur einmal generiert werden. Somit 
denke ich schon, dass es schneller ist.

Welche Hash Algorithmen sind den in einer solchen Situation passend?

lg Robert

[Karl H. (kbuchegg)]

Robert S. schrieb:

> Der Hash muss ja für jede Querry nur einmal generiert werden. Somit
> denke ich schon, dass es schneller ist.

Du scheinst in der Vorstellung zu leben, dass es genügt nur den Hash zu 
speichern. Dem ist aber nicht so. Der Hash kann dir nur das Auffinden 
des Eintrags beschleunigen. Danach musst du sowieso noch vergleichen, ob 
die Strings übereinstimmen!

Wenn es so einfach wäre, hättest du einen perfekten 
Kompressionsalgorithmus gefunden. 255 Bytes in einen einzigen int 
quetschen, sodass jede der möglichen 255 Bytes Kombinationen einen 
eindeutigen Hash-Code hat.

Beim Hashen schmeisst man immer Information weg! Mehrere 
unterschiedliche Strings können daher denselben Hashcode erzeugen. Man 
nennt das Kollisionen. Im Extremfall (zugegeben: konstruiert) sind alle 
deine 10 Hashcodes identisch, obwohl jedesmal nach einer anderen DNS 
gesucht wurde.

> Der Hash muss ja für jede Querry nur einmal generiert werden. Somit
> denke ich schon, dass es schneller ist.

Kommt drauf an.
Um den Hashcode zu erzeugen, musst du quer durch den kompletten String. 
Ein Vergleich kann aber auch dann schon abbrechen, wenn die ersten 
beiden Bytes unterschiedlich sind.

Ich will dich nicht davon abhalten, da etwas Komplizierters zu benutzen. 
Ich möchte nur darauf hinweisen, dass es praktisch immer einen Breakeven 
Point gibt, an dem die Optimierung mehr kostet als sie bringt.

[Robert S. (razer)]

Karl heinz Buchegger schrieb:
> Du scheinst in der Vorstellung zu leben, dass es genügt nur den Hash zu
> speichern. Dem ist aber nicht so. Der Hash kann dir nur das Auffinden
> des Eintrags beschleunigen. Danach musst du sowieso noch vergleichen, ob
> die Strings übereinstimmen!

Danke für die Information. Genau das dachte ich. Wieder was gelernt =)

> Ich will dich nicht davon abhalten, da etwas Komplizierters zu benutzen.
> Ich möchte nur darauf hinweisen, dass es praktisch immer einen Breakeven
> Point gibt, an dem die Optimierung mehr kostet als sie bringt.

Ich werde mal in den sauren Apfel beißen und die Domain als Klartext 
speichern. Optimieren kann man ja immer noch.

Danke für die Hilfe und noch einen schönen Tag
lg Robert