A probléma: óriási adathalmazokat, amik nem férnek el egy, de egy tucat szerveren sem egyszerre kell feldolgozni, mintha csak egyetlen Excel tábla lenne.

Feltételezem belegondoltál már abba, hogy mi történik egy Google kereséskor. Az nyilván nem járható út, hogy az összes Google adatot beleverik egy MySQL-be és lenyomnak a torkán egy SQL lekérdezést. Mennyi adatról van szó? A Google kereső kábé 500 petabyte, azaz 500 000 terabyte adatban keres jelenleg, ami napról napra nő.

A feladathoz nem használnak klasszikus értelemben vett adatbáziskezelő szervereket, hanem három fő komponensre alapoznak:

MapReduce

Ez egy keretrendszer, vagy inkább modell, amit a Google fejlesztett ki a probléma megoldására. A PageRank ugyan halálra sztárolt innovációjuk, de a MapReduce-tól tud egyáltalán működni a Google gépezet, ennyire fontos ügyről van tehát szó.

A MapReduce egy 6 részre osztott folyamat, ami pongyolán magyarázva így néz ki:

1. Van egy input reader, ami beolvassa a feldolgozandó adatokat és maximum 128MB-os csomagokra osztja.
2. Minden csomag eljut egy Map funkcióhoz, ami előfeldolgozza a benne lévő adatokat. Népszerű példa: ha meg kell számolni a szavak számát az adatbázisban, akkor a Map funkció bontja szét az adatokat szavakra, de nem ő az, aki meg is számolja.
3. Partíció funkció: a Map eredményeit ő irányítja tovább, kvázi "forgalomirányító".
4. Összehasonlító (comparison) funkció: megkapja a Map eredményeket és sorba rendezi őket. Pl. a szószámolós példában ABC rendbe helyezi a szavakat, így az azonosak egymás alá kerülnek.
5. Reduce funkció: végigmegy az eredményeken és elvégzi az összesítést, pl. megszámolja az azonos szavakat. A reduce ("csökken") elnevezés találó: 500 darab "az" névelő leírása 1000 betű, ebből itt lesz mindössze öt: az500.
6. Output writer: kiírja az eredményt, általában a háttértárra. Bumm.

Általában csak a Map és Reduce részeket kell megírni, a többit elintézi a rendszer. A legtöbb Google szolgáltatás alapja egy jól megírt MapReduce. Egy MapReduce kód mérete általában 100 sor alatt van, marhára csak a lényegre kell koncentrálni, nagyon kényelmes! Nem véletlen, a Google-nél nagyon nagy agyak vannak.

GFS - Google File System

A MapReduce igényeihez nem volt megfelelő fájlrendszer. A fő probléma az, hogy az adatokat bazi nagy, általában 100GB körüli fájlokban kell tárolni, ráadásul fürtözötten, hiszen petabyte-okról van szó. A másik jellegzetesség, hogy ezeket nagyon ritkán kell csak törölni, felülírni vagy csökkenteni a méretüket, leginkább csak hozzáírnak a végükhöz (append).

Így hát a Google kifejlesztett egy sajátot, ez a GFS. Őt ne úgy képzeld viszont el, hogy felteheted rá a filmjeidet vagy az oprendszeredet, nem erre van, nem is tudja ezt.

BigTable

Nincs a Google méreteihez elegendő teljesíményű adatbáziskezelő rendszer a világon, pedig ilyenre mindig szükség van, MapReduce ide vagy oda. A Google elég nagy, csinált magának egyet.

A BigTable nagyon gyors, nagyon nagy és felrúgja a hagyományos adatbázis-kezelők fő működési elveit. A GFS nagy fájljainak kezelésére van kihegyezve és a gyorsaság érdekében rettentő sok redundancia van benne, a motorháztető alatt fittyet hány a suliban tanult relációs adatbázis-kezelésre és normalizálásra.

Ez olyan, mint amikor a fizikusok belefutottak a Newton-i elméletek határaiba, vagy méginkább a kvantumfizikába. A mi hétköznapi paramétereinkkel egy csomó hagyományos fizikai elv kiválóan működik és használható, de vannak extrém körülmények, ahol már másképp kell gondolkodni. A BigTable pontosan ez a MySQL-hez képest.

BigTable-n fut a Youtube, Google Reader, Google Maps, Google Earth, Blogger.com, Orkut... szinte mindenük.

Mi történik, ha keresek a Google-n?

Ha elindítod a keresést, akkor a Google megnézi, hogy kerestek-e már ilyet és elég friss-e az eredmény. A legtöbb keresés ilyen és ekkor szimplán megkapod a már eltárolt eredményt.

Ha viszont nem kerestek még erre vagy túl régen, akkor felizzik a gépezet. Fontos tudnod, hogy ekkor nem fut neki a rendszer átnézni mind az 500 petabytot csak neked, csak most. Előfeldolgozott, előkészített eredmények kombinációját kapod. Ezt az előfeldolgozást hívják indexálásnak és a Google folyamatosan végzi a nap 24 órájában. (Állítólag 24 óra alatt 20-25 petabyte-ot dolgoznak fel.)

A Google Robot ugye végiglátogatja az oldalakat és visszaküldi azok kódját. Ekkor a kód bekerül egy GFS fájlba, amit a folyamatosan háttérben futó "keresőindexáló" MapReduce folyamatok majd egyszer feldolgoznak. Állítólag ők huszan vannak, húsz MapReduce dolgozza fel a weblapod kódját húszféleképpen, hogy utána szerepelhessen a keresések között. Szeretnéd megnézni a PageRank MapReduce kódját, mi? Ha!

Nagyon szimpatikus vasak

A Google szervereinél nem kell valami csúcsszuper vasakra gondolni. Rendkívül szimpatikus filozófiájuk az, hogy hibatűrő, minden gagyin elfutkorászó rendszereket kell készíteni.

Jelenleg nagy valószínűséggel szimpla négymagos Intel Xeon szervereket birizgálsz 4GB RAM-mal, 1 gigás hálókártyával és kettő darab teljesen hétköznapi 160GB-os IDE vinyóval, amit a sarkon is megvehetsz. Belőlük 2006-os becslések szerint 450 000 darab volt, most már 1 mila fölött vannak és állítólag évente 500 000-et szeretnének vásárolni... el sem tudom képzelni. Olyan számok ezek, hogy már levegőnek nézem.

A többiek?

Ezt gyorsan elintézem: az eddig írt dolgok a többi nagyra is érvényesek(pl. Microsoft és Yahoo), hasonlókat írtak, hasonló elven működnek. A Yahoo megoldásának neve Hadoop, a Microsoft-é Dryad.

Nekem is lehetnek ilyen Google dolgaim?

Igen, írok majd a Hadoop-ról és kapcsolódó részeiről, mert a Yahoo-nak köszönhetően már te is játszhatsz nagyfiús dolgokkal.

Műszaki oldalon tehát a Google/Yahoo/Microsoft csata jórésze a MapReduce/Hadoop/Dryad tengelyen mozog. Állítólag a MapReduce a legjobb, a Yahoo a Hadoop kinyitásával (open-source!) próbálja utolérni, a Microsoft pedig házon belüli erőforrásokkal. Ugye innentől kezdve kap egy plusz ízt az MS/Yahoo ügy?

P.S.: nézd meg ezt a MapReduce PDF-et. 2004-ben publikálta a Google, elég sok mindent kiadtak a nyilvánosságnak. A legérdekesebb a legvégén lévő néhány sor kód a szószámolásos példáról.

5 hozzászólás

1. idézem 2008.05.23. 02:34
   • cadmagician
   grat. ez is szép bejegyzés.
2. idézem 2008.05.23. 23:32
   • thingol
   igen, remek írás
3. idézem 2008.05.26. 06:05
   • http://tesuji.eu
   A Hadoop nem szimpla Yahoo!-s megoldás, hanem az a Doug Cutting készítette, aki még a Google előtt az Exite-keresőt készítette, aztán a Lucene-t, Nutch-ot, Mahout-ot és a Solr-t. Doug-ot néhány éve felvette a Y! azért, hogy ezeket a projekteket futtassa, a Hadoop már ennek az időszaknak a terméke, de továbbra is Apachos projektekről van szó.
4. idézem 2008.05.26. 06:08
   • Gábor
   Nagyon köszönöm az infót, így pontos.
   
   De azt azért kijelenthetjük, hogy a Yahoo a Hadoop-ra alapoz és ezerrel tolja, tudással és pénzzel.
5. idézem 2008.05.31. 11:43
   • Hodicska Gergely
   Király post!
   
   Üdv,
   Felhő

Legutolsó hozzászólások

DJ PLAYER Blue Edition: Gábor: Ja, és természetesen megy iPad-en is, hiszen _minden_ iOS app megy iPad-en.

DJ PLAYER Blue Edition: Gábor: Bug report-okat itt fogadunk: http://djplayer.net/page/bug_report_fixes

DJ PLAYER Blue Edition: hohand: Hello!A dj player mukodik iPad-on is?Tegnap feltettem, wifi-n athuztam ra zeneket,de amikor ranyomtam egy zeneszamra,error-t dobott es valami is!...

Uzsidoboz LED!: zo via Google Reader: vicces dolog, csak nem értem mire való

Uzsidoboz LED!: Gábor: @Benjamin Minek forogjanak? Egy falszínezőnek olyat nem kell tudnia, így is épp elég hatásosak.