Názory k článku Vyhľadávanie v peer-to-peer sieťach

Som rád, že sa páči :-)

o5 dobry clanek. kdyz ted vim, co to ta DHT je, tak mi nevadi, ze si ji azureus smrdoli na pozadi :)

a jeste dotaz z fulltextovemu vyhledavani v antsu: aby to fungovalo, tak superuzel v podstate musi mit u sebe cely obsah indexovaneho souboru, ne? to nezni moc efektivne indexuje se v te siti vsechno? nebo jen nektere typy souboru? do urcite velikosti? slova pouzite vicekrat v jednom slove nebo ve vice souborech si sice muze pamatovat jen jednou, ale i tak musi ten slovnik nabyt obrovskych rozmeru, ne? snazil jsem se o tom zjistit vic, ale nedari se mi najit podrobnosti.

a sam si odpovim: nebude to takova hruza, jaxem si puvodne myslel.

vyhrabal jsem na pocitaci 250MB "textovych souboru":

207MB pdf, 12MB html, 26MB rtf a 4,8 cisteho textu. vetsinou CZ, ENG, neco malo RU.

z toho vylezlo 30MB cisteho textu celkem. z toho jsem vyrobil jakz-takz pouzitelny slovnik (slovo = libovolny jedinecny retezec bez bilych znaku, delsi nez 2 znaky, obsahujici aspon jedno pismeno a-z a nekoncici na interpunkcni znamenko)

no a tenhle slovnik je jen 2.8MB veliky a obsahuje +-292K slov, coz je celkem v pohode.

btw pouzivate nekdo ANTs sit? je to fulltextove vyhledavani pouzitelne/uzitecne?

ANts používa Apache Lucene (http://lucene.apache.org/java/docs/index.html) na fulltextové vyhľadávanie, na otázky o použitých štruktúrach, implementácii a efektivite sa doporučujem pozrieť sa tam (dokumentácia vyzerá byť dosť dobrá).

Presnosť výsledkov závisí od počtu superuzlov v sieti, teda akej časti siete sa budete dotazovať. V ANts je každý superuzol pozná 4 iné superuzly. Im prepošle dotaz, ktorý prejde niekoľko hopov (neviem presne koľko, ale nejaké malé číslo n, ako napr. 5-10). Tak prehľadá najviac 4^n superuzlov (nie presne, pretože nie je zaručené, že sa dotaz nevráti späť k uzlu, ktorý už bol dotazovaný, v priemernom prípade vychádza 2.5 hopu na 25 unikátnych uzlov).

Úspešnosť vyhľadávania závisí od rozšírenosti súboru, ktorý hľadáme, v porovnaní k pomeru (počet dotázaných superuzlov)/(počet všetkých superuzlov).

Najprv matematicky:
Napr. predstavme si sieť s 65536 (=2^16) superuzlami a nejaký súbor s rozšírenosťou 256 (tj. 256 uzlov ho má, superuzly vrátane). Ak predpokladáme, že uzly vlastniace ten súbor sa budú uniformne pripájať k superuzlom, tak aspoň v 50% prípadoch sa pripoja "pekne rozdistribuovane", tj. žiadny z 256 sa nepripojí k rovnakému superuzlu (toto vyplýva z narodeninového paradoxu, v ostatných 50% prípadov sa niektoré pripoja na rovnaký), teda 256 superuzlov bude mať o súbore informáciu.

Na nájdenie daného súboru stačí trafiť pri dotazovaní ten správny superuzol, ak je počet hopov 4, uzol kontaktuje 4^4=256 rozličných superuzlov pri hľadaní (duplicity sa dajú riešiť, ale neviem, či ich ANts protokol naozaj rieši). Má cca 63% šancu nájsť daný súbor (vyplýva z binomického rozdelenia).

Pri zriedkavých súboroch rozšírenosti napr. 10, má v podobnom prípade má len 3.8% pravdepodobnosť nájdenia súboru.

Nematematicky:
Sieť s menším počtom superuzlov sa správa lepšie vzhľadom k úspešnosti nájdenia konkrétneho súboru, väčší výskyt znamená lepšiu pravdepodobnosť nájdenia. V tomto je na tom podobne ako Gnutella 2. Menší počet superuzlov ale zase pre každý superuzol znamená väčšie nároky na výkon (skladuje viac informácií o súboroch a odpovedá na viac dotazov).

Ak každý superuzol obsluhuje 50-100 obyčajných uzlov (typicky je maximálny počet rádovo stovky), a počet superuzlov je tých 65535, tak pri celkovej veľkosti siete 3.2 mil. až 6.5 mil. uzlov sa dajú rozumne (tj. s >50% pravdepodobnosťou) nájsť súbory s rozšírenosťou cca. >=250. Je jedno, či sa hľadajú full-textom, alebo podľa nejakého jednoznačného identifikátoru (ako napr. hash), pretože vždy bude dotázaný rovnaký počet superuzlov, jediný rozdiel je, že full-text search na superuzle je trocha pomalší než vyhľadanie podľa konkrétneho jednoznačného identifikátora. Samozrejme, hľadanie full-textom odpovedajúce viacerým unikátnym súborom vráti výsledky s oveľa väčšou pravdepodobnosťou ako keby fulltext odpovedal len jednému unikátnemu súboru.

Inak ANts som ešte neskúšal, ale myslím, že tá sieť bude ešte relatívne malá (pod pol milióna užívateľov), tak nájdenie súboru nebude až taký problém, horšie to bude ako bude rásť.

Podľa mňa je Kademlia oveľa lepšia, čo sa týka vyhľadávania. Ešte som nespomenul, ako je v Kademlii implementované vyhľadávanie podľa názvu súboru, resp. podľa slov v názve:

Názov sa rozseká na slová. Pre každé slovo sa vypočíta jeho hash, ktorý slúži ako kľúč do distribuovanej tabuľky, hodnota je identifikácia súboru a jeho názov. Na tie kľúče slov sa dá "store" u blízkych uzlov na dvojice (SHA-1(slovo), (názov, SHA-1(dáta súboru))). Vyhľadávanie na "slovo1 slovo2" najprv vyhľadá zoznam súborov odpovedajúci prvému slovu1, potom slovu2, a urobí sa ich prienik. Neviem, či niektorý klient podporuje operátory typu OR, mínus, ale implementácia by bola jednoduchá: pri OR je to jednoducho zjednotenie dvoch dotazov, pri mínus je to množinové odčítanie, pri úvodzovkách by to bol najprv prienik, potom grep.

Fulltext by zrejme šiel spraviť v Kademlii podobne, ale bolo by treba vyhádzať neplnovýznamové slová (ten kto by indexoval slovo "have" by sa z toho asi zbláznil ;-))

diky za link i vysvetleni

No zrovna nasledujúci diel bude trocha matematický, tie ostatné už budú 99,9% math-free ;-). Ale všetku zložitú matematiku som zredukoval na jednoduché sčítanie, násobenie a umocňovanie v reálnych číslach, čo na pochopenie myšlienky stačí. Vzorce sú tam len 3, ale netreba ich ani moc študovať, myslím, že ich význam sa dá pochopiť "z obkecu okolo".