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ístě.
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.
ČLÁNKY DO MAILU