Hlavní navigace

Jehla v kupce sena: MnogoSearch

Karel Pánek 20. 2. 2002

Vyhledávací stroj s SQL back-endem pod drobnohledem. Je každý volně šiřitelný software nevhodně implementovaný aneb co oči nevidí, srdce nepálí? Jak realizovat DoS proti tomuto stroji? Pro zkoumání všech rysů jsme využívali MnogoSearch, který obsahuje mnoho zajímavých vlastností jako indexování pomocí HTTP, HTTPS apod.

Se zachmuřenou duší chápu se klávesnice… Asi tak nějak bych mohl začít dnešní článek. Důvodem je rozpolcený stav mého já cítícího značnou sympatii k autorům MnogoSearch, kteří přinášejí něco nápomocného ostatním. Na druhou stranu mě ale kvalita takového přínosu nutí psát věci, za kterými některý čtenář uvidí opět spiknutí proti programátorům nebo moji zakomplexovanost. Doufejme, že tyto názory prezentované v předešlých diskuzích k mým článkům, postupně odezní. Cílem je jen pravdivě popsat kvalitu implementace a ukázat na možná vylepšení. A to vše bez obalu. Je pak pouze na čtenáři, co na svém serveru bude používat.

Pro zkoumání všech rysů jsem využíval verzi MnogoSearch 3.1.19. Ta obsahuje mnoho zajímavých vlastností jako indexování pomocí HTTP, HTTPS, poměrně solidní podporu vícejazyčných rozhraní, a v této třídě produktů poměrně překvapivě (ale rozhodně pozitivně) i stemmer (Stemmer je podčást lematizeru. Lematizer u slov určuje např. pád, vzor a další gramatické paramatry. Stemmer na základě těchto hodnot, které nemusí mít přímo přístupné, tvoří pouze kořen/stem slova. – pozn. edit.).

Stemmer

Stemmer je modul, který ke každému slovu nalezne jeho základní tvar (stem, kořen slova). MnogoSearch stemuje všechny indexované dokumenty a stejně tak i dotazy. Proto se nemůže stát, že hledáte-li „kopytníka“, nedostanete ve výsledku stránku obsahující např. tvar „kopytník“.

Implementace stemmeru je zajištěna až třemi možnými způsoby. Zaprvé, napojením na démon, v jehož středu běží ispell. Za pomoci jeho suffixových bází dochází k zajištění požadované funkcionality.

Druhá a třetí možnost je použití konfiguračních souborů ke stemmingu, a to buď ve formě souborů nebo SQL databáze. Jejich formát je částečně vysvětlen v instalačním balíku a měl by odpovídat formátům pro ispell. Vlastní testování těchto dvou možností jsem ale neprováděl, protože jsem se zaměřoval především na výpočet podobnosti a kvalitu vyhodnocovacích algoritmů.

SQL back-end

Datové srdce stroje bije rytmem SQL databáze, kdy jsou všechna data a některé operace vyřizovány jen s využitím SQL. Takové řešení je vždy ošidné, protože většina profesionálních fulltextových strojů implementuje pouze algoritmy, které jsou v nejhorším případě lineární (tedy na zpracování báze o milionu dokumentech potřebujete zhruba milion operací stroje). SQL stroje naproti tomu standardně pracují převážně s algoritmy na bázi nlogn (za n si dosadte milion, abyste výsledek mohli porovnat s předchozím lineárním zpracováním). Čas nlogn může být ještě výrazně snížen, používá-li SQL stroj kvalitní optimalizace nebo paralelní zpracování, ale toho se nelze u volně šiřitelných databází vždy stoprocentně dovolávat.

Jisté řešení je v instruování SQL, aby tu a tam použila jiný algoritmus pro ukládání patřičné SQL tabulky (např. formou hashovací tabulky). Není mým cílem propagovat u nekomerčního MnogoSearch např. Oracle, ale postgreSQL by tyto možnosti nabízel, což v implementaci ve verzi 3.1.19 nedošlo naplnění.

Místo implementace korektního řešení se tak v dokumentaci dočtete, že MnogoSearch může být urychlen, pokud tabulky vyexportujete, externě setřídíte a znovu naimportujete do databáze. Je to pochopitelné, protože poté již zvolené algoritmy pracují nikoliv v nlogn, ale časech blížících se n+logn. Po chvíli jste ale opět tam, kde jste byli, protože při mnohých obnovách hodnot v tabulkách dojde k rozbití optimální struktury báze.

Tento nedostatek pramení ze skutečnosti, že hlavní implementací pro MnogoSearch je MySQL. Tím bohužel nejsou u kvalitnějších SQL strojů využity funkce, kterými MySQL nedisponuje. Zároveň s tím kód obsahuje určitá vylepšení pouze pro MySQL. Například, když je tento SQL stroj nedostupný, je v pětisekundových intervalech až třikrát zkoušeno spojení.

Vlastní SQL dotazy by zasloužily další inspekci. Obsahují takové operátory jako IN nebo LIKE, které při vyčíslovaní nemohou být nad velkými bázemi rychlé. Ale o vlastní práci fulltextu si podrobněji povíme ještě dále.

Jistým řešením je pak zvláštní mód, ve kterém není index ukládán do databáze, ale je držen na disku ve stylu squid-cache (MnogoSearch jej nabízí v režimu tzv. cache-mode). To má pochopitelně kladný vliv na možnost vytvářet rozsáhlejší index, ale na druhou stranu použitá implementace klade obrovské nároky na prostor.

Vyhodnocení podobnosti

MnogoSearch neobsahuje žádnou metodu pro efektivní stanovování podobnosti. Jeho metodika je blízká pouhému získávání dat, nikoliv informací. V takové situaci se zdá implementace stemmeru naprosto zbytečným přepychem.

Stroj rozlišuje několik oblastí dokumentů, ve kterých vyhledává slova. Jsou jimi: slovo odkazu, tělo dokumentu, titulek, klíčové slovo a popisek. Vlastní hledání se ale omezuje pouze na hodnoty 0–1 (obsahuje, neobsahuje), takže o jakékoliv kalkulaci tf.idf si můžete nechat jen zdát. Váha je pak stanovena pouze za-OR-ováním hodnot pro jednotlivé oblasti, kterým ve výsledné váze přísluší vždy jeden bit. Výhoda spočívá v tom, že případným AND-ováním můžete vymaskovat jen ty oblasti textu, kde si přejete vyhledávat. Například pro vyhledávání pouze v titulcích vymaskujete na 0 všechny ostatní bity, které nepřísluší 0–1 váze pro titulek (tuto funkci zajišťuje WWW front-end).

To ale není na samotné implementaci to nejhorší. Mnohem hloupější je vlastní algoritmus vyhodnocení, který je po všech stránkách náročný a patří k velice nešťastně implementovaným částem MnogoSearch. Bohužel na nejdůležitějším mís­tě.

Algoritmus pracuje tak, že si pro každé slovo dotazu nechá z SQL báze vrátit všechna ID URL, která připadají v úvahu. Všechny tyto parciální výsledky jsou v paměti quick-sortem zpracovány a dále upraveny. Chceme-li pouze výsledek, např. na páté stránce, jsou poté ID odpovídajících URL s využitím SQL dokompletována o popisku, URL, atd. Nejenže tento způsob tvorby výsledku značně přetěžuje server, ale zároveň je nadmíru neefektivní. Zneškodnit takový stroj pomocí DoS je snadné – stačí několik WWW prohlížečů a volba vhodných slov, která jsou velmi častá (pro každý separátní dotaz můžeme použít např. 10–15 takových slov). Protože by se mohlo jednat o návod k nekalé činnosti, nebudu téma dále rozvádět. Prozradím pouze, že v takovém případě značně přetížíte SQL stroj, protože bude nucen vracet velký seznam ID URL, a přetížíte i vlastní operační systém, neboť všechny parciální listiny ID (za každé slovo dotazu) budou zpracovávány v paměti.

Budete-li trpěliví, většina strojů s mnoha tisíci zaindexovanými dokumenty se záhy poroučí do věčných lovišť. Je pravda, že s novými CPU nad 1 GHz a ultra disky s přenosy nad 20 MB/s musíte použít v dotazech slova s pravostrannou expanzí, protože takové stroje zvládnou větší nápory. Na druhou stranu ale algoritmy MnogoSearch nepracují v lineárních časech (viz. kritika výše), a proto nestačí pro zdvojnásobení výkonu koupit dvakrát silnější počítač (spíše 3–4 krát silnější). Tím je pozice útočníka značně zjednodušena.

Teoretické pozadí

Výpočet podobnosti nevychází ani z kalkulace tf.idf ani z počtu hledaných slov v dokumentu nebo celé bázi. Teoreticky je MnogoSearch ve své podstatě utilita grep s možností stemmingu a vyhledáváním frází. Z tohoto důvodu lze inkriminovaný stroj doporučit pouze jako rychlé řešení v situaci, kdy by pokryl svými vlastnostmi prostředí, v němž jej hodláme nasadit.

Závěr

Je sporné, zda lze úspěšně použít MnogoSearch pro kvalitní vyhledávání nebo pro vyhledávání v bázi více než 5.000 dokumentů. V každém případě bych ale doporučoval využít režim cache-mode, který do jisté míry sníží nebezpečí plynoucí z DoS útoků. Chcete-li využít SQL back-endu a rozumně elimitovat DoS, pak doporučuji použít MySQL, který je autory využíván jako primární báze pro implementaci. Navíc ale použijte spojení s RAID podporou (využívejte pak CREATE statement-y s atributy RAID_TYPE, CHUNKS, CHUNKSIZE) a dostatkem operační paměti.

Celkově lze MnogoSearch hodnotit jako stroj s mnoha zajímavými možnostmi, mezi které řadím snadnou konfiguraci, dále pak stemming, vícejazyčnou podporu atd. Bohužel ale vlastní implementace zatím nesplňuje nároky kladené na profesionální řešení.

Je možné, že takové řešení poznáme v následujícím díle, kdy se zaměřím na další fulltext s SQL back-endem. Bude jím AspSeek ve verzi 1.2.7 a věřte, že se máte opravdu na co těšit.

Anketa

Zkoušeli jste někdy DoS útok na stroj MnogoSearch?

Našli jste v článku chybu?

21. 2. 2002 8:38

Honza Loskot (neregistrovaný)
Ten system je postaven tak ze je tam jen fulltextovy frontend takze opravdu 1k ip opravdu pouziva mnogosearch,
na druhou stranu musim priznat ze podle statistik jde o velmi jednoduche dotazy /boolean dotazy na zpusob query language pouziva necele 3%/.

S tim testem to udelam ale radeji to nasimuluji na svem developerskem serveru.


PS: Vas clanek me samozrejme trochu znepokojil, takze jsem hned nainstaloval na radu pritele htDig a testuji ho.
Mam v pacu jeste Swish tam se mi libi ze ste…






21. 2. 2002 4:20

k.p. (neregistrovaný)
Uvazte ale prosim kolik z tech 1k ip pouzije fulltext a jak casto. Vyzkousejte si to sam: najdete si 10 nejcastejsich slov a pak pustte 10x paralelne v nekonecnem cyklu wget, ktery dopravi request k hledani vsech tech 10ti slov. Samotneho by me zajimalo, jestli to soft-RAID udrzi. Nemel jsem moznost testovat to na stroji s 1/2GB a softRAID (byt jen ide).



Vitalia.cz: Mondelez stahuje rizikovou čokoládu Milka

Mondelez stahuje rizikovou čokoládu Milka

Měšec.cz: Kdy vám stát dá na stěhování 50 000 Kč?

Kdy vám stát dá na stěhování 50 000 Kč?

Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Vitalia.cz: Pečete cukroví a zbyl vám bílek?

Pečete cukroví a zbyl vám bílek?

Vitalia.cz: Znáte „černý detox“? Ani to nezkoušejte

Znáte „černý detox“? Ani to nezkoušejte

Měšec.cz: Přejete si číslo účtu na přání?

Přejete si číslo účtu na přání?

Lupa.cz: Babiš: E-shopů se EET možná nebude týkat

Babiš: E-shopů se EET možná nebude týkat

DigiZone.cz: Digi CZ výrazně zlevnila balíček HBO

Digi CZ výrazně zlevnila balíček HBO

Měšec.cz: Finančním poradcům hrozí vracení provizí

Finančním poradcům hrozí vracení provizí

Měšec.cz: Air Bank zruší TOP3 garanci a zdražuje kurzy

Air Bank zruší TOP3 garanci a zdražuje kurzy

Podnikatel.cz: Víme první výsledky doby odezvy #EET

Víme první výsledky doby odezvy #EET

DigiZone.cz: ČT má dalšího zástupce v EBU

ČT má dalšího zástupce v EBU

Vitalia.cz: Spor o mortadelu: podle Lidlu falšovaná nebyla

Spor o mortadelu: podle Lidlu falšovaná nebyla

Měšec.cz: Golfové pojištění: kde si jej můžete sjednat?

Golfové pojištění: kde si jej můžete sjednat?

Lupa.cz: Seznam mění vedení. Pavel Zima v čele končí

Seznam mění vedení. Pavel Zima v čele končí

120na80.cz: Rakovina oka. Jak ji poznáte?

Rakovina oka. Jak ji poznáte?

Vitalia.cz: Naučí vás péct kváskový chléb bez lepku i s lepkem

Naučí vás péct kváskový chléb bez lepku i s lepkem

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

Root.cz: Mirai má nový cíl 5 milionů routerů

Mirai má nový cíl 5 milionů routerů