Hlavní navigace

Jak vypadá Google uvnitř?

Karel Pánek

V dnešním díle navážeme na slib z dílů předchozích a představíme profesionální stroj tak, jak vypadá uvnitř a jak je vlastně naprogramován. Z důvodů momentální atraktivity a popularity to nebude nikdo jiný než Google.

Čí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
Našli jste v článku chybu?

26. 5. 2002 12:01

Srakyi (neregistrovaný)
Uz jsem skoro prestaval Lupu pravidelne cist, ale diky tomu ze se zde objevuje obcas nejaky ze serie clanku Karla Pnaka se k ni znova a znova vracim.
Jen tak dal! Neco podobneho na ceskem internetu neni k nalezeni a proto doufam ze tento cyklus clanku vydrzi a bude rust jeste co nejdele!

26. 5. 2002 11:57

Srakyi (neregistrovaný)
Proc zminujete prave studenty CVUT? :o)
Vitalia.cz: Znáte „černý detox“? Ani to nezkoušejte

Znáte „černý detox“? Ani to nezkoušejte

Root.cz: 250 Mbit/s po telefonní lince, když máte štěstí

250 Mbit/s po telefonní lince, když máte štěstí

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Lupa.cz: Insolvenční řízení kvůli cookies? Vítejte v ČR

Insolvenční řízení kvůli cookies? Vítejte v ČR

Měšec.cz: Air Bank zruší TOP3 garanci a zdražuje kurzy

Air Bank zruší TOP3 garanci a zdražuje kurzy

Vitalia.cz: Když přijdete o oko, přijdete na rok o řidičák

Když přijdete o oko, přijdete na rok o řidičák

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

Podnikatel.cz: Vládu obejde, kvůli EET rovnou do sněmovny

Vládu obejde, kvůli EET rovnou do sněmovny

Podnikatel.cz: Alza.cz má StreetShop. Mall.cz více výdejních míst

Alza.cz má StreetShop. Mall.cz více výdejních míst

Podnikatel.cz: K EET. Štamgast už peníze na stole nenechá

K EET. Štamgast už peníze na stole nenechá

120na80.cz: Popraskané rty? Některé balzámy stav zhoršují

Popraskané rty? Některé balzámy stav zhoršují

Vitalia.cz: Jmenuje se Janina a žije bez cukru

Jmenuje se Janina a žije bez cukru

Měšec.cz: Za palivo zaplatíte mobilem (TEST)

Za palivo zaplatíte mobilem (TEST)

Root.cz: Telegram spustil anonymní blog Telegraph

Telegram spustil anonymní blog Telegraph

Vitalia.cz: Nahradí sluch, ale zvuk je zcela jiný

Nahradí sluch, ale zvuk je zcela jiný

Vitalia.cz: Spor o mortadelu: podle Lidlu falšovaná nebyla

Spor o mortadelu: podle Lidlu falšovaná nebyla

Měšec.cz: Europlatby: někde bez poplatku, jinde i 350 Kč

Europlatby: někde bez poplatku, jinde i 350 Kč

Měšec.cz: Banky mlží o nákladech na předčasnou splátku hypotéky

Banky mlží o nákladech na předčasnou splátku hypotéky

120na80.cz: Stoná vaše dítě často? Upravte mu jídelníček

Stoná vaše dítě často? Upravte mu jídelníček

DigiZone.cz: NG natáčí v Praze seriál o Einsteinovi

NG natáčí v Praze seriál o Einsteinovi