Hlavní navigace

Jehla v kupce sena: ASPSeek

Karel Pánek

ASPSeek patří do kategorie fulltextových strojů s ukládáním dat do SQL databáze. V současné době je využíván na serveru WebSeek.cz, kde zajišťuje vyhledávací služby v doméně .cz. Jedná se o nejlepší bezplatný stroj s implementací P-rank a vah nad termy. Ani tento server však nevydržel jednoduché dotazy a složil se.

Celý softwarový balík obsahuje robota, vyhledávací server a pochopitelně i webové rozhraní na bázi CGI. Na domovské stránce projektu ASPSeek (vytvářeno společností SWsoft) se mimojiné dozvíte, že stroj podporuje indexování několika milionů stránek, vyhledávání frází, využívání pravostranné expanze (populární hvězdička, wildcards) a v neposlední řadě i dotazy v tzv. boolském zápisu.

Z vlastností, které jsou zajímavé pro integrování produktu do dalších projektů (pozor, ASPSeek je vytvářen pod nepříjemným GNU GPL), jmenujme podporu Unicode a stemming (pro češtinu bohužel jen na bázi ispell). Formátování výstupu je na poměrně vysoké úrovni a zahrnuje takové možnosti jako shlukování shodných zásahů do jednoho „koncentrovaného“ nebo vláknovou strukturu výsledků, případně zobrazování cachovaných oindexovaných stránek.

Rychlost

Přestože je stroj realizován v C/C++, tkví hlavní nedostatky ve způsobu uložení dat. To budu dokumentovat později demonstrací toho, jak je možné stroj napadnout tak, aby neodpovídal buď vůbec, nebo aby se jeho odpovědi počítaly i několik desítek sekund. Současně je však nutné podotknout, že jednou vypočítané výsledky jsou poměrně kvalitně cachovány, takže některé dotazy při častém opakování vykazují vysokou rychlost. K tomu, aby se cachování neuplatnilo, však stačí sebemenší modifikace dotazu.

Například když na hlavním serveru vyhledáváte výraz pattern*, tak se výsledek poprvé počítá 23 sekund. To rozhodně nesvědčí o kvalitě použitých algoritmů. Dle mého názoru se dotaz rozkládá na pattern OR patterns, a vyhledávání pouhých dvou slov nad bází šesti milionů dokumentů by nemělo trvat takovou dobu. Pokud ale týž dotaz vyzkoušíte znovu, výpočet trvá už jen několik desetin sekundy.

Pokračujme ale dále. Je cachovací algoritmus natolik dobrý, že by si pamatoval předchozí dotazy a využil je ke konstrukci dotazů nových? Zkusme patter*. Tento dotaz se rozkládá na pattern* OR (…něco…). Stroj by mohl využít předchozí výpočet, protože právě v tomto případě ono (…něco…) bude buď prázdné, nebo velmi malé co do počtu termů. Překvapení se nedočkáte, stroj tento dotaz počítá i bezprostředně po předchozím dotazu celých 31 sekund.

Webové stránky, které nejsou dostupné do šesti sekund, jsou pro většinu uživatelů tzv. „mrtvé“. ASPSeek poměrně nenáročné dotazy na pilotní implementaci zodpovídá 20–30 sekund. Závěr přenechávám čtenáři.

Jak to pracuje

Jak již bylo uvedeno, stroj pracuje s SQL v zádech. Aby zvládal větší zátěže než například UdmSearch (nyní MnogoSearch), jsou slova a jejich výskyty rozloženy do více SQL tabulek. To je pochopitelně do určité míry výhodné (počet vět v jedné tabulce ovlivňuje rychlost), ale při rozkladu na 16 tabulek se nezdá, že by šlo o optimum pro několik milionů stránek.

Jako backend je možné využít MySQL nebo Oracle. Zároveň ale upozorňuji, že kód ASPSeeku neobsahuje žádné výrazné optimalizace, takže se stejně jako v případě UdmSearch můžeme dočkat jen tabulek v režii B-stromů. To je současně pozitivní zpráva, protože to znamená, že lze stroj ještě výrazně urychlit.

Určité části ASPseeku pocházejí ještě z projektu UdmSearch. V čem se ale liší, je vyhodnocování podobnosti. S odvoláním na Kira (jeden z vývojářů) obsahuje kód i implementaci techniky PageRank, kterou jsem popisoval v některém z předchozích dílů. Kromě toho zahrnuje i vyhodnocování na základě vah termů. Přesto se nejedná o klasické implementace, ale o modifikace těchto technik. Přes otevřenost a výbornou čitelnost kódu se mi bohužel nepodařilo zjistit konkrétní implementační techniku, a ani nebylo možné získat patřičnou dokumentaci.

Přesto mohu potvrdit, že stroj techniky na výše uvedené bázi opravdu implementuje a pokračuje v základní podpoře sémantiky, jak ji započal UdmSearch. Z výsledků dotazů je pak patrné, že po této stránce je vskutku schopen kvalitně zpracovat báze o velikosti několik milionů dokumentů.

Jazykové dovednosti

ASPseek využívá při stemmingu program ispell, který stejně jako v případě UdmSearch trpí určitými nemocemi, a to zejména v případě češtiny.

Jedná se o klasický problém s diakritikou, kdy stroj mylně chápe některá podstatná jména jako slovesa (např. stůl oproti stul). V zásadě lze ale jazykové schopnosti při určité obezřetnosti využít k získávání kvalitnějších odpovědí, než nabízejí velké systémy, které stemming neimplementují.

Každý klad má určité negativní aspekty a těmi jsou v případě ASPseek především degradace rychlosti a výkonu při odbavování souběžně řešených dotazů.

Nasazení, závěr

Naprosto ideální je ASPseek pro menší báze (řádově několik set tisíc dokumentů), kde se již začnou projevovat kvalitní techniky jako je P-rank a váhy nad termy, ale ještě se neprojeví rychlostně-kapacitní problémy.

Rozhodnete-li se indexovat opravdu velké báze o rozsahu sedmi milionů dokumentů, jako to činí např. WebSeek.cz, znemožněte kladení pokročilých boolských dotazů – zejména pokud obsahují spojku OR. Dále nezapomeňte omezit nebo úplně zakázat pravostrannou expanzi pomocí hvězdičky. V neposlední řadě raději nepoužívejte stemming.

Nebudete-li se držet těchto pokynů, může útočník naprosto vyřadit váš server. Kromě dotazů, které jsme uplatnili vůči hlavnímu stroji, je na WebSeek.cz velice účinný dotaz web*. Nejen, že se nedočkáte výsledku, ale zároveň zpomalíte celý server. Použijete-li několik browserů, zcela určitě daný stroj zadřete (tohle si prosím vyzkoušejte výhradně na vlastním systému, nikoliv na WebSeek.cz).

Kdo očekává porovnání s UdmSearch (MnogoSearch), nebude zklamán.

Content 2017 - tip Footshop

MnogoSearch má širší podporu databází a operačních systémů. Má i rozvinutější základnu uživatelů, takže případné problémy můžete úspěšně konzultovat. Jistou výhodou je i to, že frontend je i pro PHP. Zřejmými nevýhodami – které jsem ostatně kritizoval minule – jsou: nevhodné algoritmy, výpočet podobnosti a celková stabilita.

ASPSeek využívá solidních postupů na výpočet podobnosti, je rychlejší a dovoluje podporu Unicode. Mezi jeho nevýhody patří menší uživatelská základna a náročnější modifikace související s webovým rozhraním.

Našli jste v článku chybu?
6. 3. 2002 22:06
Michal Illich (neregistrovaný)
No, ono pokud program NEDISTRIBUUJETE (jako binarku) (coz webseek nedela), tak nejste podle GPL nuceni zdrojovy kod uverejnovat... je to takova moucha GPL (proti samotne myslence otevrenosti). GPL (ktera vznikla uz velmi davno) proste nepocita se server-side programy. Tedy pro vyhledavac neni pro autora GPL moc vyhodna, protoze jini mohou smysluplne vyhledavac pouzivat a rozsirovat a nedat nic nazpet. Zrejme by to chtelo aktualizaci GPL (ted je 2.0, prijde 2.1?).