Ing. Jan Lukavský
vedoucí týmu vývoje
jan.lukavsky@firma.seznam.cz
Jak nacrawlovat 1,5 miliardy
dokumentů pro fulltext
www.seznam.cz
●
Co je fulltextové hledání?
●
Jaká je role crawleru pro fulltext?
– jaké problémy crawler řeší?
●
Kam uložit data?
– SQL?
– co je NoSQL?
●
Jak data efektivně zpracovávat?
– co znamená efektivně?
– je Java skutečně neefektivní pro zpracování dat?
O čem to bude?
www.seznam.cz
●
vyhledávání v nestrukturovaných datech
●
jazyk "dotazů" je jiný než jazyk "výsledků"
– uživatelé hledají něco jiného, než co zadali
– zkratky, synonyma, diversifikace, ohýbání slov
●
SEO spam
– snaha uměle ovlivnit přiřozené výsledky vyhledávání
Co je fulltextové hledání?
www.seznam.cz
Frontend vyhledávače
www.seznam.cz
Backend vyhledávače
www.seznam.cz
●
"čmuchat" po webu a hledat zajímavý obsah
– jak ho poznáme?
– proč prostě "neočmuchat" všechno?
●
počítat "statický" ranking
– PageRank, informační obsah, …
●
klasifikovat dokumenty
– jazyk, porno, spam, tematizace, …
●
predikovat signály z odkazové sítě a dalších signálů
Role crawleru
www.seznam.cz
●
jedná se o instanci diskrétního optimalizačního
problému
– stavový prostor se skládá z URL
– sousední stavy reprezentují URL spojené hyperlinkem
●
optimalizaci je potřeba provádět při splnění
okrajových podmínek
– kapacita crawleru (počet navštívených stránek)
– rychlost odezvy webserverů (politeness policy)
Problémy s "čmucháním"
www.seznam.cz
●
je potřeba stanovit optimalizační kritérium
– to je trochu problém ….
– aktuálně používáme sum(score(doc))
– selection policy
●
optimalizace probíhá iterativně
– výběr dokumentů (podle selection policy)
– stažení
– nalezení nové crawler frontier
– opakování
Crawler jako optimalizační
problém
www.seznam.cz
●
co lokální extrémy?
– problém focusovaných crawlerů
– je potřeba vhodně zařadit část kapacitu crawleru na
nefocusované procházení webu
Crawler jako optimalizační
problém
www.seznam.cz
Architektura crawleru
www.seznam.cz
Crawler frontier
www.seznam.cz
●
1.5G dokumentů
– ~ 40 TiB HTML dat a extrahovaných textů
– ~ 15 TiB odkazová síť
– ~ 25 TiB metadat
– ~ 80 TiB databáze
●
nutno designovat škálovatelný systém
– vertikální škálování (scale-up)
– horizontální škálování (scale-out)
Kam uložit data?
www.seznam.cz
●
celý systém bězí na jednom fyzickém HW
●
zvětšování kapacity nákupem větších (a dražších)
disků, nakupování více pamětí
●
budování superpočítačů
●
=> pro rozumně uvažující komerční firmy příliš drahé
●
co s tím?
Vertikální škálování
www.seznam.cz
Sharding
www.seznam.cz
●
relativně škáluje
– záleží na volbě partitionování shardů
●
globální analýzy jsou velmi komplikované
– neustále dokola se řeší komunikace mezi shardy
– neustálé problémy s error handlingem
– problém je síťový partitioning
●
neexistuje systém, který toto řeší?
– naštěstí existuje
Sharding
www.seznam.cz
Horizontální škálování
www.seznam.cz
●
systém škáluje přidáním výpočetního uzlu
– "commodity hardware"
– nezaměňovat s hardwarem na odpis, jedná se o výkonné
servery
●
větší nároky na síťovou komunikaci
– výpočetní nody si musí vyměňovat data
●
větší nároky na toleranci k výpadku uzlu
– čím více výpočetních nodů, tím větší šance, že stroj odejde
v průběhu výpočtu
Horizontální škálování
www.seznam.cz
●
reimplementace GoogleFS
●
distribuovaný, replikovaný, fault tolerant systém
●
standardní filesystém rozdělený na NameNode
(alokační tabulka) a DataNode (slave držící data)
●
master (NameNode) zajišťuje kooperaci DataNodů
●
řídí replikace a replica placement policy
Hadoop - HDFS
www.seznam.cz
Hadoop - HDFS
www.seznam.cz
●
distribuované výpočty nad HDFS
– framework zajišťuje korektní dokončení výpočtu i v
prostředí failujících výpočetních uzlů
●
jednoduché pro programátora
– dvousečná zbraň, komplikované algoritmy se špatně
designují a koordinují
– většina algoritmů nejde napsat na jeden Map/Reduce job
●
existují nadstavby a obaly
Hadoop - Map / Reduce
www.seznam.cz
Hadoop - Map / Reduce
www.seznam.cz
●
z principu batch-oriented
– neumožňuje interaktivní odezvu
●
málo flexibilní
– Map a Reduce fáze jsou "zadrátované" v systému
●
komplexní algoritmy komplikované pro programátora
– nutné správně řídit data-flow
– netriviální design patterny jsou náchylné na chyby
●
iterativní algoritmy jsou neefektivní
– například výpočet PageRanku
Map / Reduce – problémy
www.seznam.cz
●
Hadoop YARN
– "operating system for the cloud"
●
umožnil vznik spoustě dalších systémů
– typicky pracují s vyššími konstrukty (operátory), než prosté
Map a Reduce
– Spark, Tez, Storm, Giraph, ...
●
zjednodušují programátorský pohled a zrychlují vývoj
●
zatím většina ve velmi ranné fázi
Map / Reduce – co dále?
www.seznam.cz
●
dnes již trochu zavádějící, NoSQL databázím se
dělají SQL vrstvy :-)
●
odlišení od RDMS, většinou existují pouze primární
indexy
●
CAP teorém
– Consistency, Availability, Partition tolerance
●
RDMS operují na CA hraně
●
pro horizontální škálovaní je nutná P hrana
– můžeme volit CP nebo AP
●
Cassandra, HBase, MongoDB, ...
Co je NoSQL?
www.seznam.cz
●
logicky se dá chápat jako nekonečně dlouhá řídká
matice
●
klíčem k datům trojice (klíč, sloupec, timestamp)
●
umožňuje neúplné dotazy
– například (klíč, sloupec, *), (klíč, *, *), (klíč*, sloupec, *)
●
matice je horizontálně rozdělená na regiony
●
regiony obsluhují RegionServery
– jednodušeně jde o velké cache servery
●
data uložena v HDFS
HBase
www.seznam.cz
HBase
www.seznam.cz
●
je Java dostatečně efektivní?
– z praxe se ukazuje, že designové rozhodnutí pro Javu
(JVM) bylo správné
– efektivita za běhu vs. efektivita při vývoji
●
je levnější nahradit drobnou neefektivitu za běhu
nákupem HW
– horizontálně škálovatelné algoritmy k tomu přímo vybízejí
●
v Javě je vývoj rychlejší, než v low-level jazycích
– časově kritické operace lze i tak psát nativně
●
většina času se "propálí" při IO operacích
– čtení z disku, síťová komunikace
Proč Java?
www.seznam.cz
●
obrnit se trpělivostí :-)
●
nevynalézat kolo – je mnohem lepší a efektivnější
použít existující (ideálně) open source řešení
– levnější je podílet se na vývoji s open source komunitou,
než psát vlastní řešení na zelené louce
●
frameworky bohužel nejsou všespásné
– i s nejlepším frameworkem se narazí na problémy se
škálovatelností a stabilitou
A jak tedy nacrawlovat
1,5G dokumentů?
www.seznam.cz
●
při vývoji algoritmů nemáte k dispozici produkční
prostředí
– produkční nasazení potom s sebou nese několik iterací,
neboť velká data důkladně prověří skutečnou stabilitu kódu
●
špatný návrh algoritmu vede k "hotspotování"
– nerovnoměrné vytěžování clusteru, různé nody jsou různě
zatížené
– systém je pouze tak rychlý, jak rychlý je nejpomalejší člen
Problémy velkých dat
www.seznam.cz
●
~ 500 serverů
– ~ 10000 jader
– ~ 5 PiB raw prostor
– ~ 25 TiB RAM
●
30 miliard záznamů v databázi
●
desítky analytických a agregačních úloh denně
●
desítky rankovacích a prediktivních úloh týdně
●
200 M denně stažených dokumentů
1,5G dokumentů
www.seznam.cz
●
180 miliard odkazů mezi dokumenty
●
30 miliard záznamů v databázi
●
zhruba 700 milionů dokumentů zaindexováno
●
z toho 150 milionů dokumentů se objeví v SERPu
●
18 milionů dotazů denně
●
3,5 milionů unikátních dotazů denně
●
17 milionů unikátních dotazů týdně
1,5G dokumentů
www.seznam.cz
Otázky?
http://vyvojari.seznam.cz/
http://seznam.sprace.cz/
www.seznam.cz
Ing. Jan Lukavský, vedoucí týmu vývoje, jan.lukavsky@firma.seznam.cz
Děkuji za pozornost