[WLANnews] dezentrale Suche in der Freifunk Wolke.

[Ruben Kelevra]

Hallo Christof,

Am 7. April 2013 17:40 schrieb Christof Schulze <christof.schulze at gmx.net>:
> Kein Mensch will suchen, jeder will finden. Deshalb möchte ich die
> Liste gern um einen Punkt erweitern: Usability.
> In Sachen Usability konkurriert jede Lösung immer mit gängigen
> Suchmaschinen, wie zum Beispiel Google.
>
> Als relevant erachte ich dabei drei Aspekte:
> * Latenz. Google liefert innerhalb einer Sekunde(!) die relevantestens
>   Ergebnisse in aufbereiteter Form auf einer Webseite zurück. Eine
>   aufbereitete Antwort muss in der selben Größenordnung erfolgen.

Mein Vorschlag hat natürlich hochgradig unterschiedliche Latenz:

Fall A
Wenn eine Anfrage im lokalen Cache des Supernodes liegt ist natürlich
das Ergebnis sofort, vorsortiert vorhanden und kann vom Node an den
Client ausgeliefert werden.

Fall B
Wenn das Ergebnis in einem Cache eines anderen Supernodes (x) liegt,
dann muss der angefragte Supernode (a) in seine Liste schauen, Kontakt
zu dem Supernode (x) aufbauen und ihn nach dem Ergebnis fragen.

Fall B.1
Hier könnten folgende Dinge passieren:
-Supernode (x) antwortet nicht.
 + Supernode (a) muss Supernode (x) als Down melden
 + Supernode (a) muss (parallel dazu) Suchhandle erlangen und Suche anschoßen
   +Antwortzeit wie in Fall C+Timeout für Cacheanfrage <-- WORST CASE

Fall B.2
-Supernode (x) antwortet mit Cachezeit abgelaufen *1
 + Supernode (a) muss Suchhandle erlangen und Suche anstoßen
   +Antwortzeit wie in Fall C+Antwortzeit für Cacheanfrage

Fall B.3
-Supernode (x) antwortet mit "Cache-Entry doesn't exist" *2
 + Supernode (a) muss Suchhandle erlangen und Suche anstoßen
   +Antwortzeit wie in Fall C+Antwortzeit für Cacheanfrage

Fall B.4
-Supernode (x) liefert fehlerhafte Daten *3
 + Supernode (a) sendet "fehlerhafte Daten für Anfrage $Suche von
Supernode(x)-Cache" durchs Netzwerk und erhält damit den Suchhandle
 + Supernode muss suche Anstoßen
   +Antwortzeit wie in Fall C+Antwortzeit für Cacheanfrage

Fall B.5
-Supernode (x) liefert Daten
   +Antwortzeit wie in Fall A+Antwortzeit für Cacheanfrage

Fall C
Der Supernode (a) hat keine Information über ein Suchergebnis im Cache

Fall C.1
-Supernode (a) versucht ein Suchhandle zu erlangen, scheitert, und
bekommt vom ersten Supernode mit der Info den Supernode (x)
  + Weiter wie in Fall B

Fall C.2
-Supernode (a) bekommt das Suchhandle
  + Stößt Suche an
    + Antwortzeit ist sehr lang.

*1 Dieses Szenario passiert sehr selten, nur wenige Sekunden um das
Ende des Cacheeintrags, wenn die Uhren nicht Syncron laufen oder die
Anfrage lange durchs Netzwerk braucht. Eigentlich sollte der Eintrag
im Supernode (a) die Ablaufzeit enthalten.

*2 Dies könnte eine Fehlfunktion oder ein Neustart mit Verlust des
Caches bedeuten.

*3 Sollte das restliche Netzwerk ähnliches feststellen (durch eigene
Suchanfragen) muss der Supernode geblacklistet werden. Dies sollte dem
Supernode bekannt gemacht werden, damit dieser seinen System-Admin
kontaktieren kann.

Notizen:
Fall B.2 könnte man entschärfen indem man 5 Minuten Überhangzeit
definiert, in denen der Cache noch im Speicher gehalten wird, aber
jedem der anfragt gesagt wird dieser Cache sei veraltet. Dies hilft
dann dem Supernode der Anfragt zu entscheiden ob er, direkt im
Anschluss an die Ausgabe des Cacheinhalts an den Benutzer selbst eine
Suche starten möchte um den Cache-Eintrag danach selbst zu halten.

Fall B.3 könnte man verbessern indem beim Verlust jeder Information
über Caches dies dem Netzwerk bekannt gegeben wird, sowas wie
"MyCacheIsEmpty", sodass alle Supernodes die Einträge für diesen
Supernode aus dem Speicher löschen können.


Generell könnte man darüber nachdenken das ein Cachehit die Cachzeit
um 1/3 verkürzt (wird lokal gespeichert) und wenn die lokal
gespeicherte Cachezeit abgelaufen ist eine "Update-Cache-Entry"-Suche
begonnen wird, die niedrig priorisiert den Cache aktualisiert.
Minimale Cachezeit sollte wohl etwa eine Stunde sein. Als maximal sehe
ich einen Tag an.


> * Bedienbarkeit der Schnittstelle. Jeder muss die Suche erreichen
>   können und die Schnittstelle muss von meiner Großmutter bedienbar
>   sein.
Ein Suchfeld. Ende? ;)

Naja man theoretisch beliebige Dateiinhalte und Dateitypen damit
durchsuchen, dem sind ja keine Grenzen gesetzt... Standardmäßig würde
ich wohl HTML/PDF/TXT/Latex/ODF etc. durchsuchen.

> * Relevanz der Ergebnisse. Die Suchergebnisse müssen einen Bezug zu
>   dem haben, was der Nutzer finden wollte.
Das muss auf Clientseite gelöst werden, mein Protokoll beschäftigt
sich nur mit dezentralem Caching und wenig Overhead bei Suchen in
vielen Nodes ohne zentralem Server.


Ich hoffe meine (chaotischen) Gedanken um diese Uhrzeit helfen weiter.


LG Ruben