Bekövetkezett, ami már régen várható volt: nincs többé titok, immár mindenki megtudhatja, hogyan képes a világ legnagyobb keresője a szakadatlanul szaporodó weblapmilliárdok ellenére a másodperc töredéke alatt megválaszolni tetszőleges kérdést.

Az információ a Google belső köreiből szivárgott ki, és amilyen gyorsan megjelent a világhálón, olyan gyorsan el is tűnt. Csupán néhány tízezer internetező láthatta 2010. március 31-én (Közép-Európai idő szerint éjjel fél egy és 0:52 perc között.) Én szerencsére éppen neteztem, úgyhogy meg tudom osztani a titkot a magyar internetezőkkel. Linkeket tehát nem mutatok, minek. Úgyis a semmibe mutatnának. A tömör technikai dokumentumok és diagramok helyett pedig saját szavaimmal mondom el a lényeget. Jó?

Először az információforrásról: a G. J. monogrammal publikáló szerző a Google egyik programozója, aki azzal indokolta az információ nyilvánosságra hozatalát, hogy ennek a technológiának közkinccsé kell válnia, mert a világ számos problémájára nyújthat megoldást a hiperteljesítményű információkeresés. Mivel több mint fél órára nyilvánosságra került, valószínűleg G. J. elérte célját, de a Google sem kerül veszélybe, mert az ingyenes keresőszolgáltatással, és az ezt lehetővé tévő többszázezer számítógéppel eddig is csak olyan pénzügyileg jól elengedett gigászok tudták egyáltalán bármilyen szinten versenyre kényszeríteni, mint a Microsoft.

És akkor jöjjenek a technikai részletek.

Hogyan készítsünk a végtelenségig skálázható információkereső rendszert?

A titoknak nem egy nyitja van, hanem legalább három-négy. Az eddig is köztudott volt, hogy a Google nem használ semmilyen forgalomban lévő szoftvert a keresőmotor közelében, még az operációs rendszer szintjén sem. Az oprendszerük olyannyira Googlizált, hogy még a TCP/IP stack is saját fejlesztés. Hamarosan meg fogjuk érteni, miért.

Szintén közismert, hogy bár a Google-nek több százezer szervere van, ezek egyike sem komoly, drága szerverhardver, sokkal inkább hasonlít az otthonokban használt asztali számítógépekhez. Kezdetben talán pénzügyi okok (is) álltak a nagy gyártók redundáns, nagy rendelkezésre állású szervervasainak elkerülésében, mára azonban ez már a stratégia részévé vált.

Lássuk, Móricka hogyan gyorsítana fel egy lekérdezést. Valószínűleg egy adatbázisba hordaná az összes adatot, és építene rá egy indexfa-szerkezetet, amivel néhány lépésben lekérdezhető lenne tetszőleges adat. Az igazi probléma ezzel a megközelítéssel, hogy az adatmennyiség növekedésével (márpedig az exponenciálisan növekszik) a központi adattárolós, központi indexes módszer egészen bizonyosan meghal. Bizonyítékért nem kell messzire menni: már egy nagyobbacska elektronikus kereskedelmi weboldal is komoly teljesítményproblémákkal számolhat, ha az adatbázisát egy központi helyen tárolja.

Rendben, akkor osszuk szét az adatbázist és az indexeket több számítógépre! Itt egy újabb problémával szembesülünk: melyik gépen van az az adat, amit én keresek? Nyilvánvaló, hogy míg tíz adatbázis esetén van értelme sorra lekérdezni a számítógépeket, melyikük a nyerő, ezt már pár ezer számítógép esetén megkísérelni is felesleges, négyszázezerről nem is beszélve. Inkább rá kellene venni a gépeket, hogy maguktól jelentkezzenek, ha náluk van a keresett adat.

Hasonlat: ha egy osztályteremben megkérdezzük, ki tett rajzszöget a tanítóbácsi székére, egyszerre stimuláljuk az összes nebulót, de jó eséllyel csak az egyikük veszi magára a kérdést, és jelentkezik. A teljesítménynövekedés egyértelmű: nincs szükség arra, hogy a teljes osztályt egyesével kivallassuk. Skálázható ez a modell? Igen.

El tudunk képzelni egy olyan képet, hogy egy téren áll százezer ember, és hangosbemondón megkérjük, emelje fel a kezét, akit Kovács Dénesnek hívnak? Gyorsan megy? Mint a villám. Működne ez egymillió emberrel is? Igen, ha találunk olyan módszert, amivel kérdéseket lehet eljuttatni hozzájuk. Mondjuk egy rádióadás megfelelne…

Ha most valaki nekiállna a forgalomban kapható operációs rendszerekkel (Windows, Linux stb.) egy ilyen rendszer kifejlesztésének, falakba ütközne. Mégpedig azért, mert bár van olyan hálózati forgalomtípus, amivel sok-sok gépet meg lehet egyszerre szólítani (Multicast), és erre a gyártók építettek is terheléselosztó megoldásokat (Network Load Balancing), azok mindegyike süket és vak az adatokra. El tudja osztani a TCP/IP kéréseket és kész. De itt nem azt, hanem keresőkifejezéseket kell szétosztani, ráadásul több ezer gép között!

Ezzel vissza is érkeztünk ahhoz a ponthoz, hogy miért nem volt jó a fiúknak (Szergej Brin és Larry Page) semelyik operációs rendszer, miért kellett majdnem a nulláról írni maguknak egyet. Egyébként ez a lépés egyenesen zseniális abból a szempontból, hogy a kezdetekkor nem volt milliárdnyi weboldal, nem lehetett előre látni, hogy egyszer majd a végtelenségig kell növelni a kapacitást. És mégis, ezt az utat járták végig, mert folyamatosan szemük előtt tartották azt a célt, amit a kor konkurensei nem: mikroszekundumok alatt kell válaszolni a kérdésekre! Ehhez pedig a kilencvenes évek végének Pentiumaival már akkor is sok-sok, akár egy tucat gépre is szükség volt.

Tehát íródik egy search term load balancing mechanizmus, amely nem a TCP/IP kapcsolatokat szórja szét a szerverek között, hanem a keresőkifejezéseket, és nagyjából a következőképpen épül fel (ez itt az eredeti háromrétegű modell, ennél ez ma már bonyolultabb, akit érdekel, annak megírom):

A rétegek nevei:

• Front End szerverek, ezek láthatók az internet felől. Ezekből viszonylag kevés van, néhány ezer.
• Index- vagy keresőszerverek, ezeken elosztva található a világ összes weboldalának indexe (~szószedete), de maga a weboldal/dokumentum NEM! Ezekből már több tízezer van.
• Tárolószerverek. A weboldalak és dokumentumok békésen szundikálhatnak a harmadik rétegben, a tárolószervereken. Ritkán van rájuk szükség: indexépítésnél és ha a felhasználó a találati listában arra kattint, hogy „kérem a Google által tárolt verziót” – vagyis tízezer lekérdezésenként egyszer. Tárolószerverből van a legtöbb: százezres nagyságrend.

Lássuk magát a keresési folyamatot!

• legyen a keresendő kifejezés az alábbi két szó: „search term”. Ezt beírjuk a Google keresőjébe, Enter.
• A felhasználók egy Front End számítógéppel találkoznak, a kérésünk befut ezek egyikéhez. A Front End gépek a kérést változatlan formában továbbkiabálják a második rétegben a hátuk mögött álló indexszervereknek, ahol a szószedet (és egy darabka környező szöveg) található. És ez itt a kulcs. Mármint az, hogy
  • a Front End gépek NEM állnak neki a keresés szétcincálásának, ehelyett úgy, ahogy van, továbbdobják a keresőszervereknek,
  • a keresőkifejezéseket mindegyik keresőszerver „hallja”, de csak az reagál, akinél a kért adat van.
• A keresőszerverek adatbázisa fel van osztva az ABC alapján egy bizonyos algoritmus szerint (lásd később), azaz mindegyikük érzékeny bizonyos szavakra. A sokezer gép közül kettő fog „gerjedni”, az egyik az, amelyik az „s” betű környékéért felel („search” szó), a másik pedig az, amelyik a „t” betű környékéért felelős („term” szó).
• A két „begerjedt” gép válaszol a Front Endnek, mely ekkor már tényleg dolgozni fog: összeállítja a sorbarendezett találatlistát (jobban mondva csak az első találati oldalt!) a két forrás alapján, és válaszol, mint a villám.

G. J. itt megjegyzi, hogy az eredeti kód hiányossága miatt a Google a mai napig nem tud úgynevezett „NEAR” kereséseket elvégezni, vagyis olyan lapokat visszaadni, ahol a „search” és a „term” szavak egymáshoz közel állnak. Az Altavista tudta. Az Infoseek tudta. Azok viszont mára garantáltan megdöglöttek volna a Google térnyerése nélkül is: nem lehetett őket elég jól skálázni. A hiányosság okait G. J., a renitens alkalmazott abban látja, hogy a search term load balancing kód mind a mai napig változatlanul ugyanaz, amit Szergej és Larry a 90-es évek végén készített. Senki nem mer hozzányúlni!

Egy dolog maradt hátra, a világ összes weboldalának indexelési algoritmusa. Hogyan osszunk szét X milliárd weboldal szavait pár tízezer gép között?

Az elosztási, indexelési algoritmus

Az elosztással az a probléma, hogy állandóan újra és újra kell osztani a weboldalakat, ahogy az interneten sokasodnak a lapok. Ennek ellenére egy eléggé egyszerű elosztás áll a rendszer hátterében, az alábbihoz hasonló: aaa-tól abb-ig az első gépé, abc-től ade-ig a második gépé stb.

Hogy pontosan hány karakteres szóhossznál van a tördelés, azt könnyű megbecsülni: ha tízezres nagyságrendű keresőszerver van, tízezerfelé kell osztani a világ összes angol nyelvű szavát, vagyis a három karakter nagyjából jó becslés (26^3=17576). Ebbe még beleszólnak bizonyos betűkombinációk előfordulási valószínűségei (aaa kezdetű szó egy sincs), valamint az a tény, hogy szóból lényegesen több van, mint weboldalból, meg hogy bizonyos szavakra sokkal több kérés érkezik, mint másokra, de ez már bonyolult matek, hagyjuk. Megvan nekem a képlet, de nem értem :)

(Na jó, bonyolítsuk még egy picit: minden indexszerver több testvérrel hagyományos terheléselosztási fürtben van, hogy egy milliók által keresett szót (sex, illetve választási évben Barack Obama) egyszerre több indexszerver is kezeljen, és elosztottan válaszolgatnak a Front Endeknek. Az indexek duplázását-triplázását, vagy számuk csökkentését automatikusan, a keresési igények függvényében végzik.)

Egy Google keresőgép tartalma

A második rétegben lévő keresőszerverek nem tárolják magukat a weboldalakat, csupán azok indexét (kivonatát), így egy gépre akár sok százmillió lap indexe fér fel, ami nem rossz arány!

Hogyan fér el egy gépre százmilliónyi leindexelt kulcsszó? Simán. A kulcsszavak átlagos hossza 5-6 bájt, de legyen tíz, azzal könnyebb számolni. Minden szó többmillió weblapon szerepel, az átlagos weblap URL-je mondjuk 70 bájt. Eddig 80 bájtnál tartunk. Most ezt szorozzuk meg százmillióval: nyolcmilliárdhoz jutunk, ami 8 GB, vagyis a mai asztali számítógépek esetében is a memóriában tartható, nem is kell a merevlemezre írni! És akkor az URL-ek tömöríthetőségét még nem is vettük figyelembe!

Ez persze durva egyszerűsítése a képnek, mert az indexnek nyilvánvalóan szerkezete van, az is helyet visz el, meg van egy csúnya trükk is: mivel a keresőket maximum az első tíz találati oldal érdekli, szavanként néhány tucat találatot elég a memóriában tartani, a többi ugyan megvan lemezen, de soha senki nem fogja valóban keresni (ha csak nem szűkít egy országra vagy weboldalra).

És ami a legszebb: a Google határozza meg, mit tart fontosnak, mit tart memóriában! Ez a Google Rank! Más sorrendben, más fontosság alapján kéred az adatokat? Nem lehet. Mindig Google Rank sorrendben kapod, maximum be van korlátozva egy országra, egy weboldalra stb.

Már közel a történet vége: a gyors kereséshez az kell, hogy a kulcsszóindex memóriában legyen. Mi van akkor a Google-számítógépek merevlemezén? A Google-oprendszeren és a 8 GB-nyi indexadaton kívül szinte semmi. Üres hely. Mivel azonban merevlemez kell a gépekbe, hogy legyen honnan bootolni és betölteni az indexadatbázist, és a legkisebb merevlemez ma már lassan 1 TB-os, a Google indexgépein hemzseg a „felesleges” tárolókapacitás. Nem véletlen, hogy iszonyat mennyiségű tárhelyet tudnak adni a Gmail postafiókokhoz!

Tök jó, nem?

Az eredeti doksi megvan nekem, nem merem ide kitenni, mert egy véletlen baleset esetleg leviszi a lábamat vagy a fejemet, de ha valaki kéri, elküldöm "titokban".