Jak vypadá Google uvnitř?

Čísla, která budeme uvádět, vycházejí ze starších údajů a původní dokumentace, které je možné ověřit z veřejných zdrojů, což zajisté nedůvěřiví čtenáři ocení. Zároveň neuvádíme kompletní seznam literatury, vyjma nosné dokumentace. Tu jsme využili pouze k opravě a kontrole některých hodnot. Její kompletní seznam získáte z Googlu, jak jinak, dotazem „Google architecture“.

Historie

Autory Googlu jsou pánové Sergey Brin a Lawrence Page. Celý systém je postaven na centralizované architektuře (viz díl o architekturách fulltextových strojů) a všechny indexované HTML stránky jsou uloženy – jak jinak než v komprimované podobě – v centrálním úložisti. Primárním cílem, který měl být splněn, je zajištění vysoké přesnosti odpovědí.

Google byl (v roce 2000) tvořen Linuxovým clusterem s 80 GB diskového pole a propustností I/O sběrnic 400 Gb/s. Kompresovaná velikost HTML dat byla 53,5 GB, index dokumentů měl 9,7 GB, lexikon obsahoval 14 milionů slov, velikost báze odkazů 6,6 GB (24 milionů stránek a 259 milionů odkazů) a velikost seznamu odkazů 3,9 GB (v seznamu je pouze dvojice ID dokumentů). Jeho běh zajišťuje několik modulů, které vzájemně kooperují.

Pozn.: Index dokumentů, který zmíníme jako vstup hned u prvního modulu, musíme popsat předem, ostatní datové struktury vysvětlíme za pochodu. Jedná se o index nad položkami o dokumentech. Každá položka obsahuje kromě různých údajů o dokumentu i jeho kontrolní součet a stav. Když byl odpovídající dokument stažen, přibývají takové položky jako titulek apod. V opačném případě se vše jeví jako obyčejný seznam URL.

Architektura modulů

URL server: tento modul nedělá nic jiného, než že si vezme startovací URL, a zároveň čte další URL tak, jak jsou (nebo se objeví) v indexu dokumentů. Každá URL adresa je pak odbavena crawlerovi, který má za úkol dokument opatřit. O tom, jakým způsobem Google prochází prostor URL adres (do hloubky, do šířky), si povíme později.

Crawler modul: crawler stáhne požadovaný dokument na patřičném URL a pošle jej na úložiště. Google má kapacitu stahovaní cca 100 stránek/sekundu (méně než 1 MB/s) při 4 crawlerech a 300 aktivních koneksí na každém z nich (údaj se opět týká roku 2000). Crawlování pochopitelně probíhá distribuovanou verzí crawlovacího algoritmu.

Úložiště: na úložišti se koncentrují všechny stažené dokumenty, jsou kompresovány zlib-em (RFC1950) a získávají své vlastní unikátní ID.

Indexovač: tento modul prochází úložiště, parsuje dokumenty a vytváří pro každé slovo hit. Ten tvoří jednak samotné slovo, ale i jeho pozice, hodnota zvýraznění vůči okolnímu textu atp. Pro fungování stroje se hit rozlišuje na fiktivní a prostý. První vzniká z částí URL, titulků, textů odkazů a meta tagů. Do druhého případu spadají ostatní situace. Hit je pak uložen v barelu – částečně uspořádaném indexu, jehož strukturu najdete v originálním dokumentu (třetí obrázek…). Kromě toho indexovač vytváří seznam odkazů ve tvaru (z URL, na URL, text odkazu) a generuje lexikon.

URL Resolver: za úkol má čtení seznamu odkazů, konvertuje relativní URL na absolutní a ta zase na ID těchto dokumentů. V tomto modulu také vzniká vstup pro výpočet PageRank, protože dochází i ke generování databáze odkazů, ta neobsahuje zdrojová URL jako seznam odkazů, ale pouze jejich odpovídající ID.

Třídič: aby bylo možné vygenerovat jeden invertovaný seznam, setřídí tento modul všechny barely, které vycházejí z indexovače. Na výstupu indexovače je index seřazen podle ID dokumentu, pro práci jej ale potřebujeme řadit podle ID termů. Výstupní indexy-barely jsou de facto dva. První, označovaný jako malý, indexuje titulky a texty odkazů. Druhý, velký, kompletní těla dokumentů.

Vyhodnocování dotazu

Technika vyhodnocování doznává určitých změn v případě jednoslovného a víceslovného. V zásadě však vlastní algoritmus můžeme popsat takto:

1. Rozlož dotaz
2. Pro každé slovo zjisti jeho odpovídající ID v systému
3. Pro každé slovo zjisti začátek seznamu dokumentů v malém barelu
4. Procházej ten seznam dokud nenajdeš dokument, který plně odpovídá celému dotazu
5. Spočítej jeho relevanci
6. Když jsme v malém barelu došli na konec některého ze seznamů (dokumentů), skočíme na začátek tohoto seznamu do velkého barelu s každým termem a jdeme na 4
7. Když nejsme na konci žádného seznamu, jdeme na 4
8. Seřaď ohodnocené dokumenty