Pr-1st-1.1-m01-Slajd41

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Schemat architektury Google

Schemat architektury Google


Serwer URL - Pobiera lokalizatory URL z indeksu dokumentów i przesyła je do automatów skanujących sieć.

Roboty skanujące (ang. crawlers) - Pobierają dokumenty z listy i przesyłają na serwer składujący, zaimplementowane w języku python, zwykle działa ich kilka (3-4),utrzymują ok. 300 aktywnych połączeń jednocześnie, są w stanie pobrać ok. 100 dokumentów/ s.

serwer składujący (ang. Store server) - Kompresuje przychodzące dokumenty, przydziela im unikalne identyfikatory (docID) oraz zapisuje w repozytorium.

Indexer - Odczytuje dokumenty z repozytorium i analizuje je w poszukiwaniu słów, dla każdego słowa tworzona jest struktura tzw. “word hit”

  • “word hit” - przechowuje dane o:
    • lokalizacji słowa w dokumencie
    • rozmiar czcionki( względny)
    • wielkość liter
  • plain hits ( zawartość treści dokumentu)
  • fancy hits (URL, anchor, metatagi, title)

URL Resolver - Analizuje pliki 'anchor text' zapisane przez indexer, względne lokalizatory URL przekształcane są w bezwzględne, tworzy bazę danych odnośników (pary elementów docID)

Algorytm PageRankTM - Internet oparty na demokratycznych zasadach, ranking strony pokazuje jej przydatność a nie jedynie zawartość słów kluczowych ,intuicyjne uzasadnienie - model “losowego” użytkownika sieci

Sorter - Tworzy tzw. indeks odwrócony (ang. inverted index) porządkujący trafienia 'hit' wg wordID, końcowy leksykon Program 'Dump Lexicon' indeksu odwrócony + indeks wygenerowany przez Indexer = leksykon użytkownika

Lexicon - Zorganizowany zarówno w postaci listy jak i tablicy laszującej, zawiera ok. 20 mln słów kluczowych.

Google Web Server - Łączenie wyników z opisem na podstawie serwerów dokumentów i formatowania wyników, sugestie (moduł sprawdzania poprawności pisowni), reklamy

Google zindeksował jak dotąd ponad 4 miliardy stron WWW, które zajmują średnio ok. 10 KB. Łącznie daje to 40 Terabajtów danych, które muszą być średnio 1000 razy w ciągu sekundy przeszukiwane i na ich podstawie wygenerowane muszą zostać wyniki zwrócone w ciągu ułamka sekundy do użytkownika.

Publikowanie treści w Internecie nie jest ustandaryzowane, dlatego proces wyszukiwania też musi być bardzo zróżnicowany i „wrażliwy” na wiele dodatkowych informacji i wskazówek. Aby zindeksować daną stronę, Google analizuje wszystkie linki pomiędzy dokumentami znajdującymi się na witrynie. Każdy link jest potencjalnym źródłem dodatkowych informacji o stronie. Tekst linku pozwoli zorientować się co znajduje się na tej stronie. Jeżeli wiadomo co znajduje się na stronie na której jest link, to pozwala to też zorientować się jaka jest jakość strony do której ten link prowadzi. Takie podejście do oceny stron internetowych jest podstawą algorytmu Page-Rank, który jest podstawowym źródłem sukcesu wyszukiwarki Google. Algorytm ten Page-Rank nie bierze pod uwagę tylko liczby linków, ale też ich jakość i wagę. W rezultacie, wyświetlane są strony, które z dużym prawdopodobieństwem będą tym czego oczekuje użytkownik. Stosowanie algorytmu Page-Rank dla każdego wyszukiwania i każdej strony jest oczywiście niemożliwe. Dlatego cały proces jest podzielony na kilka etapów i rozdzielony na różne serwery. Gdy system dostaje zapytanie od użytkownika, wędruje ono najpierw do serwerów indeksowych na których znajduje się skatalogowana zawartość całej sieci WWW. Indeks stanowi przyporządkowanie poszczególnych słów kluczowych do dokumentów, które je zawierają. Przy podawaniu wyników Google bierze pod uwagę jeszcze dodatkowe informacje takie jak miejsce występowania słowa kluczowego np. nagłówek czy stopka, pogrubienie itp.

Każdy serwer indeksowy zawiera tylko pewien fragment wiedzy na temat sieci WWW. Na jednym komputerze, a tym bardziej na tanich maszynach stosowanych w Google, indeks całej sieci by się po prostu nie zmieścił. Tak więc cały indeks sieci jest rozdzielony na wiele serwerów i zapytanie jest przesyłane jednocześnie do wielu komputerów, przy czym każdy z nich przeszukuje jedynie swój zbiór danych. Po otrzymaniu zapytanie Google wylicza ok. 1000 najlepszych wyników do których przypisuje tzw. Document-ID, czyli identyfikator dokumentu. Następnie identyfikatory te wędrują do serwerów dokumentów na których znajdują się kopie przeszukiwanych przez Google stron. Dzięki temu oprócz listy adresów Google wyświetla także tytuły oraz część tekstu znajdującego się w dokumencie. Także w tym wypadku każdy serwer zawiera tylko pewien podzbiór danych. W ostatnim etapie wyszukiwania, wyniki wędrują do Ad-serwerów, czyli serwerów reklamowych, które do listy stron dodają reklamy, stanowiące podstawowe źródło przychodów firmy. Gotowa lista wyników wraz z reklamami wysyłana jest do przeglądarki internauty.

Podstawowym zabezpieczeniem przed utratą danych jest ich replikacja. Każdy serwer, który zawiera dane, posiada nawet 10 kopii. Wydaje się że jest to drogie rozwiązanie, ale przy takim obciążeniu serwery i tak muszą być zwielokrotniane, żeby obsłużyć dużą liczbę zapytań. Gdy zatem awarii ulegnie jeden serwer to wydajność usługi spada o 10%. Z punktu widzenia użytkownika nie jest to prawie zauważalne. Awaria taka przy poprawnym rozdziale obciążenia, może być skutecznie maskowana do czasu jej usunięcia. Obecnie Google posiada nie 10, ale nawet 50 kopii każdego serwera. Firma tworzy kopie serwerów, kopie zbiorów serwerów oraz kopie centrów obliczeniowych, które rozsiane są na całym świecie. Od lutego 2000 wyszukiwarka nie miała ani jednej poważnej awarii.

Awaria sprzed 5 lat wydarzyła się, gdy Google miało tylko jedno centrum obliczeniowe w którym popsuł się główny switch. Przez pół godziny wyszukiwanie z wykorzystaniem serwisu Google nie było mozliwe. Teraz wszystkie dane posiadają swoje kopie rozsiane w różnych centrach obliczeniowych. Szefowie firmy twierdzą że utrata danych z jednego centrum nie stanowi problemu, gdyż jego uruchomienie od nowa trwa nie dłużej niż 3 dni. Dane składowane na serwerze zapisywane są na dyskach przy pomocy systemu GFS (Google File System). Pojedynczy blok ma aż 64 MB wielkości. Każdy blok zapisywany jest na trzech różnych serwerach znajdujących się w różnych szafach serwerowych podpiętych do różnych przełączników. Takie rozwiązanie gwarantuje, że awaria lub błąd zapisu/odczytu danych nie będzie miał wpływu na jakość wyników. W sumie Google posiada ponad 30 klastrów z systemem GFS. Jeden klaster może składać się nawet z 2000 serwerów i magazynować Petabajty danych. Każdy klaster ma wydajność zapisu i odczytu na poziomie ok. 2 Gbit/s.

Aby uzmysłowić sobie skalę przetwarzania i ilość gromadzonych danych wystarczy powiedzieć że na tym poziomie nawet błędy zapisu wynikające ze specyfikacji dysków twardych mogą być problemem. Gwarantują one bowiem poziom błędów na poziomie 1:10-15 bitów co oznacza że jeden na 1015 bitów może zostać zapisany błędnie, a oprogramowanie sterujące dysku twardego tego nie wykryje. Przy danych gromadzonych w PB takie wartości mają już duże znaczenie, dlatego system plików GFS posiada dodatkowe mechanizmy weryfikacji


<< Poprzedni slajd | Spis treści | Następny slajd >>