Archiv rubriky: Programování

Apache Hadoop

hadoop

Konečně jsem se dostal k paralelizaci! Posledních několik dnů pracuji s Apache Hadoop. Musím říct, že mě to baví mnohem víc než nějaké řešení bugů apod. A konečně se začínám přibližovat k cíli…

Instalace virtuálního Apache Hadoop clusteru

Tento týden jsem se zabýval převážně instalací virtuálního Apache Hadoop clusteru. Jako virtualizační platformu jsem použil VirtualBox a Debian Linux. Zprovoznění clustru není zas tak složité, ale narazil jsem na jeden velice nepříjemný bug. Týká se verze XML parseru Xerces. Hadoop vyžaduje k běhu určitou verzi této knihovny, ale v JRE se nachází jiná verze. A Hadoop si není schopen říci o tu správnou ani v případě, že je přiložena do .jar souboru. Nepodařilo se mi najít nějaké „správné“ řešení, a tak jsem to vyřešil workaroundem – na začátku main metody volám [code lang=“java“]System.setProperty("javax.xml.parsers.DocumentBuilderFactory",
"com.sun.org.apache.xerces.internal.jaxp.DocumentBuilderFactoryImpl");[/code].

Map/Reduce

Apache Hadoop je dělaný pro řešení problémů pomocí algoritmu Map/Reduce. Nejprve se přivede vstup do Mapperu, který jako vstup očekává kolekci hodnot key-value. V tomto Mapperu se provedou nějaké operace (například transformace, agregace hodnot apod.) a výstupem je opět kolekce key-value. Dále se provede seskupení do kolekce key-(value-list) a ta se přivede na vstup Reduceru. Reducer jí následně zpracuje a výstupem je hodnota kolekce hodnot value. Moc pěkně zpracovaný příklad je na Slideshare. Velice dobře zpracovaný je i tutorial na Yahoo, který se zabývá i pokročilejšími věcmi v Hadoopu.

Když používáte Hadoop na něco, na co není určený

Bohužel problém, který řeším, se pro Hadoop vůbec nehodí. Já potřebuji v ideálním případě nějakou sdílenou paměť a v ní frontu úloh, do které budou jednotlivé nody přistupovat. To je ovšem zcela proti logice Hadoopu – ten naopak nepředpokládá žádnou sdílenou paměť. Očekává, že nody budou pracovat se soubory, které se nacházejí na distribuovaném systému souborů HDFS. Hadoop taky předpokládá, že jednotlivé úlohy budou náročné, ale nejen časově, ale také množstvím zpracovávaných dat. Hadoop je vhodný, pokud potřebujete zpracovávat velké množství dat, řádově desítky terabytů a více. Naopak se naprosto nehodí na úlohy, které potřebujete zpracovat rychle. Pokud vám tedy jde o množství zpracovaných dat, je Hadoop správnou volbou. Pokud potřebujete co nejrychleji výsledek, měli byste se poohlédnout po nějakém jiném nástroji.

Map/Reduce očekává vstup a to v podobě souborů. Já vlastně žádný vstup nemám, mám pouze parametr, se kterým potřebuji úlohu spustit. Ano, onen parametr by se dal nazvat vstupem, ale jak ho Mapperu předat? Navíc nepotřebuji žádný Reducer, stačí mi pouze Mapper.

Pokud chcete na Hadoopu spouštět úlohy typu Map/Reduce, naleznete příkladů a tutoriálů plný internet. Pokud chcete něco netypického, nenaleznete bohužel nic 🙁 Vůbec nic… Všechno co jsem o Hadoopu našel se týkalo Map/Reduce a nikdo nikde nikdy neřešil úlohu, která by tomuto paradigmatu neodpovídala. Bohužel jediná dokumentace, kterou Hadoop nabízí, je JavaDoc + jednoduchý tutoriál, jak vyřešit typický problém, kde si vystačíte na 90% s nabízenými výchozími třídami. Abych tedy vyřešil svůj problém, s úlohou, která vůbec neodpovídá paradigmatu Map/Reduce, musel jsem jí přiohnout, aby tak alespoň vzdáleně vypadala. Musel jsem dělat různé psí kusy, aby se mi to povedlo. Připadal jsem si jako krotitel lvů nutící slona skákat skrz obruče.

Krkolomné – ale funkční řešení

Ale nakonec se mi to podařilo! Po několikadenním úsilí mi konečně na Hadoopu běží i mé atypické úlohy! Abych spustil jednu úlohu, s jedním jednoduchý parametrem, musel jsem napsat 4 třídy. InputSplit, InputFormat a RecordReader a samozřejmě samotný Mapper. Většina těch tříd, kromě mapperu, nemá žádnou užitkovou hodnotu, jedná se pouze o balast nutný pro donucení Hadoopu spustit onu úlohu, která neodpovídá paradigmatu Map/Reduce. Je to smutné, ale je to tak 🙁

Mé řešení funguje vpodstatě tak, že vygeneruje parametry pro všechny úlohy, vytvoří pro ně instanci třídy InputSplit a následně všechny instance vrátí jako kolekci. Toto dělá třída InputFormat. Následně se nějakým způsobem něco s těmito instancemi InputSplit udělá, a končí to tím, že se na ně zavolají metody write a read – přesně v tomto pořadí. Tyto metody asi zapíší data do HDFS nebo kdoví co, ale něco na ten způsob to bude. Následně si třída RecordReader převezme instanci třídy InputSplit a vytvoří z ní kolekci key-value párů. Jelikož potřebuji pouze 1 parametr, používám pouze hodnoty key. Následně si Hadoop sám volá čtení z RecordReaderu, a předává hodnoty Key do Mapperu, který je dále zpracovává. Byla to fuška, spoustu debugování, psaní kódu stylem pokus-omyl, ale funguje to!

Jsem v půlce stáže

Právě se nacházím zhruba tak v půlce stáže a myslím, že to je ta správná chvíle na napsání článku :). Co jsem tady ten měsíc a půl dělal? Možná se budu trošku opakovat, ale pokusím se navázat na článek první zážitky ze stáže.

Seznámení se s projektem

První zhruba tak týden, dva, jsem se seznamoval s projektem. Nejprve jsem musel projekt dostat do kompilovatelného stavu, což se ukázalo jako úkol na dlouhou dobu. Musím říct, že hned po prvním dni jsem si říkal ZLATÝ MAVEN! Ano, kdyby používali na takto rozsáhlý projekt Maven a správně nastavené závislosti mezi projekty, nemusel bych strávit několik dní nad hledáním a nastavováním závislostí, ale byl bych schopen projekt zkompilovat během 5 minut.

Poté, co se mi podařilo projekt úspěšně zkompilovat, na mě čekal další nelehký úkol – brodit se stovkami souborů a tisíci řádky kódu a pochopit, jak že to vlastně funguje. Nebylo to snadné, styl, jakým je kód psaný, mi to vůbec neusnadňoval. Soubory jsou plné komentářů a poznámek, které jsou mnohdy i několik let staré a na 99% neaktuální a zcela jistě naprosto zbytečné. Ovšem jsou tam… Nevím proč, ale jsou. A dokonce si ten zvyk psát ke každé úpravě kódu komentář se jménem, kdo a kdy to upravil, udržují dodnes. Přestože používají SVN a tyto změny by si mohly vyhledat tam.

Hlavní úkol stáže

Na konci prvního týdne jsme si dali meeting s vedoucím projektu a ten mi vysvětlil, co že vlastně budu dělat. Popsal mi pro mě důležité části projektů, co dělají apod. Projekt má 3 hlavní části, na kterých budu pracovat – POM – nástroj na počítání metrik kódu, SAD – nástroj na detekci tzv. code smells a Ptidej – nástroj na detekci návrhových vzorů. Pak jsme se dostali k tomu, jak spolu ony nástroje souvisí atd. Dozvěděl jsem se, že mým hlavním úkolem bude pracovat na nástroji Ptidej – ten je ze všech nejpomalejší a nejvíc potřebuje paralelizaci. Následně jsme se velice povrchně dostali k tomu, jak Ptidej funguje.

A hned jsme zabrousili do dalších souvisejících projektů. Aby bylo možné hledat návrhové vzory, je nutné nejprve vytvořit graf tříd. Takovýto graf obohacený o různé informace tvoří model tříd. Projekt, který se zabývá popisem modelu tříd, a vlastně nejdůležitější ze všech projektů, je PADL. Tento projekt tvoří meta-model pro model tříd.

Samotné vyhledávání návrhových vzorů je založené na principu isomorfismu podgrafu. Musím říct, že mě to poměrně zaskočilo. Celkově jsem byl velice překvapený, jaké psí kusy se zdrojovými kódy dělají, aby udělali nějaké ty analýzy. Původně jsem se mylně domníval, že půjde o něco jako lexikální analýzu. Celkově jsem očekával mnohem více práce se zdrojovými kódy, než s modelem tříd apod.

Když vyprchal můj prvotní šok, dali jsme do vymýšlení způsobu, jak to vyřešit. Vedoucí mi navrhoval, že by nejraději rozdělil model tříd na několik částí, a prováděl analýzu na těchto dílčích částech. Ovšem bylo potřeba vymyslet, jak model dělit, a jak jeho rozdělené části zase spojit zpět. Zpočátku to vůbec nevypadalo jasně, ale domluvili jsme se, že budeme model dělit na úroveň balíčků či namespaců. První úkol zněl jasně – analyzovat kód balíček po balíčku.

Metriky kódu

Nástroj, na kterém budu prvně pracovat je POM. POM dělá několik analýz kódu. V první fázi vypočítává metriky, jako je například CBO (coupling between objects), DIT (depth of inheritance tree) apod. Těchto metrik je celkem 72. Většina metrik je unárních, tedy počítají se vzhledem k 1 třídě, ale také je tam několik binárních metrik, které vyjadřují vztah mezi 2 třídami. Většina metrik je závislých na celkovém modelu, takže na ně není možné použít navrhovaný způsob rozdělení modelu do několika menších částí. Ovšem některé závislé nejsou, a tak jsem se dal do identifikace těch nezávislých. Postupně jsem prošel všechny metriky, prozkoumal jejich zdrojové kódy, zjistil, zda vyžadují celkový model či ne, a ty, které ne, jsem otagoval příslušným interfacem. Na závěr jsem si napsal unit test, který zkouší spočítat metriky na úrovni balíčků a porovnává hodnoty s metrikami z celkového modelu.

Nástroj na slučování dílčích modelů – PADL Merger

Dalším krokem bylo vyřešit ony metriky závislé na celkovém modelu. A tady přišlo na řadu spojování dílčích částí modelu. Nejprve jsem musel dopodrobna prozkoumat, jak vypadá zdrojový kód tříd modelu, jak se model sestavuje apod. Zjistil jsem, že každá entita z analyzovaného zdrojového kódu (balíček, třída, interface, metoda, parametr…) má svou reprezentaci ve zdrojových kódech onoho nástroje na analýzu a tvoří tak meta-model. Třídy, ke kterým není k dispozici zdrojový kód (například vnitřní implementace standardních tříd Javy), jsou reprezentovány pomocí interface IGhost.

Rozhodl jsem se tedy vytvořit nástroj, který nalezne všechny ghosty v modelu a shromáždí jejich reference na jednom místě – v hash mapě. Už to samo o sobě mi dalo docela zabrat, ale docela mě to bavilo. Naučil jsem se přitom používat návrhový vzor Visitor 🙂 Dalším logickým krokem bylo nahrazení těchto ghostů entitami, které reprezentují plně analyzovanou implementaci daného ghosta. Těmto entitám interně říkám implementing entities nebo zkráceně implementors. Nahrazení ghostů funguje tak, že se pracuje se 2 modely. V prvním modelu, nazvěme ho třeba cílový, se postupně projdou všichni ghostové a zkusí se vyhledat podle ID v druhém modelu, zdrojovém modelu. Pokud zdrojový model obsahuje entitu s daným ID, máme vyhráno. Stačí ji vyjmout ze zdrojového modelu a vložit do cílového 🙂 Ovšem tahle sranda není vůbec jednoduchá a dala mi docela zabrat. Zdrojové kód třídy, která toto dělá, má skoro 1000 řádek.

Unit testing

Když jsem dokončil slučovací nástroj, dal jsem se do psaní testů. Vůbec jsem nevěděl, jak ověřit, jestli jsou modely sloučené správně. A tak mě napadlo zkusit porovnat počet entit ve sloučeném modelu a v modelu, který byl vytvořen bez slučování. Pak mě napadlo porovnat také metriky, pokud jsou modely stejné, měly by být i metriky stejné…

Bugy

Ovšem tady jsem narazil. Metriky stejné nebyly 🙁 A tak jsem se dal do hledání bugů. Po opravení několika svých bugů jsem narazil na neočekávané chování několika tříd z projektu PADL. Nahlásil jsem toto chování profesorovi, který je hlavním vedoucím projektu. Ten mi potvrdil, že je to neočekávané, a že se s největší pravděpodobností jedná o bug. A tím začalo moje hledání bugů v projektu PADL 🙂 Doposud jsem jich našel a opravil nemalé množství, ale mnohé stále zůstávají neobjeveny. Když už jsem se hrabal ve zdrojových kódech PADLu, napadlo mě, že spustím unit testy z projektu zvaného All Tests. To jsem asi neměl dělat.. Testů tam bylo obrovské množství (asi 500), běžely poměrně dlouho (odhaduji to na 20 minut), a výsledkem bylo, že jich více než polovina neprošla. Zajímavé.. Bohužel toto je výsledkem poměrně nekoordinovaného způsobu práce, který tu provozují. Na projektu dělá několik lidí, vždycky někdo někde něco upraví, commitne a dál se o to moc nestará. Nějaké konvence, návrhové vzory apod. se tu moc neřeší. Je to trošku paradox, projekt na analýzu kódů, vyhledávání návrhových vzorů a code smells je, bohužel, plný code smells 😀

Paralelizace? Ještě ne…

V první části stáže jsem se tedy (bohužel) vůbec nedostal k žádné paralelizaci. Zatím jsem pouze řešil nástroj na spojování modelů a opravoval bugy. Také jsem radil kolegovi z Mexika, který měl tu smůlu, že musel tento projekt používat na analýzu kódu. Sice jsem byl trochu zklamaný z toho, že jsem s tím moc nepohnul, ale měl jsem radost z toho, že tomu rozumím natolik, že jsem schopný radit ostatním 🙂 Také jsem byl rád, že jsem nalezl a opravil několik bugů. Celkově mi první část projektu dala trošku jiný pohled na rozsáhlé a zejména teoretické projekty.

První zážitky ze stáže

Mám za sebou první 3 dny studijní stáže na Polytechnique de Montreál a tak je na čase podělit se o své první zážitky.

Oficiální název mé stáže zní: Parallelizing a Large Scale Static Analysis using the Hadoop Map/Reduce Framework. Je to poměrně krkolomný, dlouhý a nic neříkající název. Ve skutečnosti se jedná o poměrně zajímavou věc – přizpůsobení již existujících algoritmů na statickou analýzu kódu pro využití v cloudu. Tedy aby ty algoritmy neběžely na jednom počítači, ale třeba na stovce…

První seznámení s projektem

V pondělí 26. 8. jsem po vyřízení několika formalit zamířil za profesorem a k laboratořím. Po příchodu do laboratoře jsme narazili na problém s nefunkčním počítačem. A tak jsem se zatím dočasně usídlil na sousedním místě, kde počítač funguje. Profesor mi dal přístup k SVN repozitáři, ze kterého jsem si měl stáhnout zdrojáky, a poslal mi soubor se seznamem projektů, které budu potřebovat. Bylo mi jasné, že se nejprve musím seznámit s tím, jak je nástroj naprogramovaný, jak funguje apod., než začnu dělat nějaké modifikace. Ale už jsem netrpělivě očekával své první seznámení s tím jejich úžasným nástrojem pro statickou analýzu kódu, který budu následující 3 měsíce paralelizovat. To jsem ovšem nevěděl, co mě čeká…

V repozitáři se nachází několik stovek projektů (odhadoval bych to tak na 200-300), které mezi sebou mají různé závislosti. Když se mi po několika desítkách minut čekání podařilo konečně stáhnout několik set MB dat z repozitáře, doufal jsem, že už to půjde hladce. To byl ovšem omyl. Všechny projekty jsou dělané v Eclipse a NEMAJÍ mezi sebou nijak nastavené závislosti. A že těch závislostí tam je… Takže po kliknutí na tlačítko Build all se objevilo asi 3000 chyb při kompilaci a dalších pár tisíc warningů (které raději ignoruji). Většina chybových hlášek se týkala chybějících závislostí. No a mě nezbývalo než ručně se proklikat chybami ke konkrétnímu zdrojáku, nastavit pro projekt správné závislosti a kompilovat znovu. A znovu. Občas jsem dokonce narazil i na závislost na projektech, které jsem ještě neměl stažené z repozitáře, a tak jsem je musel stáhnout.

Resolve dependency, build, debug…

Druhý den vypadal víceméně stejně, pokračoval jsem v řešení závislostí a nekonečným kompilováním projektů. Pak se mi konečně podařilo zkompilovat a spustit projekt, který měl sloužit jako ukázka, jak se používá onen nástroj na statickou analýzu. Bohužel jsem stále neměl vyhráno. Projekt jsem sice spustil, ale hnedka na mě vykoukla výjimka a program spadl. A tak jsem strávil celý den debugováním desítek tříd kódu, ke kterým prakticky neexistuje dokumentace, a o kterých jsem neměl ani potuchy co a jak vlastně mají dělat. Byl jsem poměrně zklamaný, protože tohle nebylo zrovna to, co jsem očekával. Nakonec se mi podařilo program dostat do takové fáze, že již nevyhazoval výjimky a tvářil se, že je vše vpořádku. Bohužel nebylo – program nedělal vůbec nic. Statická analýza neproběhla. Profesorovi se to zdálo nějaké divné a tak poslal výpis stack-trace jinému profesorovi, který je vedoucím tohoto projektu.

Třetí den ráno dorazila odpověď. Verze projektu v repozitáři je nějaká rozbitá, máme použít jinou. Tak jsem tedy smazal vše, co jsem doposud dělal a stáhl jsem si novou verzi projektu. A začalo řešení závislostí znovu, nanovo… Naštěstí už jsem tak nějak věděl, který projekt na kterém je závislý a kde tyto závislosti nastavit, takže mi netrvalo dlouho zkompilovat a spustit aplikaci. Běžela. Hurá! S radostí jsem napsal e-mail profesorovi, který přišel a konečně mi taky trošku vysvětlil, co že tam vlastně mají a na čem budu pracovat. A pak mi dal za úkol rozjet další část projektu. Ta už se mi ovšem rozjet nepodařila, protože některé zdrojové kódy v projektu jsou psané pro Javu 1.7 a na mém počítači byla jen verze 1.5.