728 x 90

Dlaczego Google działa dobrze?

Dlaczego Google działa dobrze?

Każdego dnia użytkownicy internetu wykonują dziesiątki lub setki wyszukiwań w znanych wyszukiwarkach, wśród których prym wiedzie niezmiennie od lat wyszukiwarka Google. Czy zastanawialiście się jednak kiedyś, co stoi za jej sukcesem? Dlaczego zwraca dobre wyniki? Jeśłi tak, zapraszam do lektury.

Kiedy to było?

Page i Brin stworzyli Google w 1996 roku. Wtedy jeszcze wyszukiwarka pracowała na zaledwie czterech komputerach stojących w pewnym garażu. Wystarczyło to jednak, żeby zrewolucjonizować rynek wyszukiwarek. Wszystko przez sprytne podejście do algorytmu wyszukiwania, nazwanego PageRank. Wprawdzie od 1996 roku algorytm ulegał wielu modyfikacjom, usprawnieniom oraz dodatkowym możliwościom, jednak główna idea pozostaje wciąż taka sama.

Jak w pewnym artykule napisali twórcy Google (Page, Lawrence, Brin, Sergey, Motwani, Rajeev, & Winograd, Terry. 1999 (November). The pagerank citation ranking: Bringing order to the web. Technical Report 1999-66. Stanford InfoLab. Previous number = SIDLWP-1999-0120. Dostępne na: http://ilpubs.stanford.edu:8090/422/.) Page Rank jest przełomowa technologia zmieniająca podejście do wyszukiwania materiałów w sieci. Opiera sie na ocenie ważności strony.

Page Rank każdej strony wyznaczany jest na podstawie ilości odnośników, które na te strone wskazuja. Sa one interpretowane jak głosy na te strone.

Teraz trochę matematyki

Tak więc zakładając, ze na stronach {X1,X2, …,Xn} znajdują się odnośniki wskazujące na stronę A, oraz ||Xi|| oznacza ilosc wszystkich odnosników na stronie Xi, ||Xi||A oznacza ilosc wszystkich odnosników na stronie Xi wskazujących na stronę A oraz PR(Xi) oznacza PageRank strony Xi a N to ilość wszystkich stron, wówczas PageRank strony A bedzie równy

PR(A) = (1 − d)/N + d*(PR(X1)*(||X1||A)/(||X1||) + … + PR(Xn)*(||Xn||A)/(||Xn||))

 

Przez d nalezy rozumieć prawdopodobieństwo wejscia na pojedynczą stronę przez użytkownika. Wielkosc te ustalono początkowo na podstawie badań i testów na 0.85.

Powyższe równanie pokazuje następujące rzeczy:

  • PageRank strony zależy od wszystkich innych stron internetowych.
  • Im więcej odnośników wskazuje na konkretną stronę, tym lepszy jest jej ranking.
  • Ważne są też rankingi wskazujących na daną stronę stron (czyli nic nie warta strona, nic nie zdziała w algorytmie, choćby nie wiem jak mocno linkowała do innej)
  • Skoro tych stron jest tak dużo, to równania, które trzeba rozwiązać są bardzo długie.
  • Skoro PageRank strony zależy od PageRanku innych stron… to po jednym przeliczeniu całości internetu, kolejne przeliczenie zmieni wynik, bo zmieniły się elementy równania!

W celu określenia PageRank dla każdej z istniejących stron, poszukuje się rozwiązania równania zawierającego ponad 500 milionów zmiennych Przykładowe działanie podstawowego algorytmu PageRank jest pokazane na ilustracji poniżej:

Kolejne iteracje algorytmu powoduja modyfikacje wag poszczególnych stron. I tak w (a) pokazane sa wagi poczatkowe, (b)-(i) modyfikacje wag, (j) to waga nowo dodanej strony.

Kompletny opis podstawowego algorytmu PageRank przedstawiony jest w pracy Avrachenkov, Konstantin, & Litvak, Nelly. 2004. Decomposition of the Google PageRank and Optimal Linking Strategy. Research Report RR- 5101. INRIA. Dostępne na: http://hal.inria.fr/inria-00071482/PDF/ RR-5101.pdf.. W algorytmie tym konstruowana jest macierz przejścia i wykorzystywane łańcuchy Markova, ale do tej literatury odsyłam tylko chętnych.

A gdzie tu wyszukiwanie?

Rzeczywiście. Na razie zajęliśmy się określeniem wag stron. Tymczasem szukając w Google, szukamy zwykle jakiejś frazy. I tutaj przychodzi zwykłe wyszukiwanie słownikowe. Strony zawierające wyszukiwane słowo zostają uporządkowane zgodnie z rankingiem określonym przez PageRank i mamy gotowy wynik wyszukiwania. W procesie uczestniczą więc

  1. serwery indeksujące – w celu wyznaczenia stron zawierających słowo,
  2. serwery PageRank – określające kolejność wyników,
  3. serwery treści – generujące fragmenty treści stron zawarte pod wynikami.

No dobrze, ale jak to jest zorganizowane od strony technicznej?

Po pierwsze: serwery –  od 1996 roku do 2010 roku ilość serwerów obsługujących wyszukiwanie wzrosła do 1 000 000 (miliona!), 2 000 000 w roku 2013 i 3 000 000 w roku 2017.

Po drugie: serwery – kwartalnie Google wydaje na nowy sprzęt około 5 miliardów dolarów.

Po trzecie: prąd – w 2010 roku (a teraz dużo inaczej nie jest) można było szacować tak:

• 1 serwer ~ 1 kilowat

• Przez godzinę wszystkie serwery zużywają – 1 milion kilowatogodzin

• Przez godzinę Google dostarcza wyników dla 10 000 000 wyszukiwań

• Jedno zapytanie = koszt włączenia żarówki 100-watowej na 1 godzinę

Po czwarte: w jednym wyszukiwaniu bierze udział bardzo dużo maszyn! Są serwery indeksu, serwery dokumentów (fragmentów stron) i serwery odpowiadające.

Po piąte: ogromna sieć dostawców treści – każde zapytanie do Google jest obsługiwane przez najbliższy geograficznie serwer (przypomnijmy sobie ponad 10 000 000 wyszukiwań na godzinę w roku 2010!)

Koszty dla Google.

Jak łatwo się domyślić koszty utrzymania tak gigantycznej sieci wyszukiwania są ogromne. Nie licząc kosztów nowego sprzętu, sam prąd, serwerownie, klimatyzacja, obsługa są niewyobrażalne

Wystarczy sobie prosto oszacować:

  1. W 2017 roku, co sekundę mamy 60 500 wyszukiwań (za http://www.internetlivestats.com/google-search-statistics/)
  2. Rocznie tych wyszukiwań jest 1.907928e+12 (czyli 1907 miliardów)
  3. Jedna kilowatogodzina w USA to koszt 0.05 USD, więc jedno wyszukiwanie kosztuje 0.005 USD
  4. Zatem roczny koszt prądu! używanego do obsługi wszystkich wyszukiwań w Google to 9.5 miliarda dolarów 

Jakość wyszukiwania.

Podstawy PageRank pozwalały na łatwe generowanie fałszywych stron, które służyły do tak zwanego Black SEO. W związku z tym, do algorytmu są wciąż wprowadzane zmiany, eliminujące te problemy. Między innymi z powodu tych zmian zdarzało się, że znane strony znanych dużych firm wypadały nagle z rankingu z powodu używania nieuczciwych praktyk. Jedną z bardziej znaczących zmian w ubiegłych latach jest dodatkowe promowanie stron, które mają wersję dla urządzeń mobilnych. Inną, było wprowadzenie wcale nie tak dawno temu wyszukiwania natychmiastowego, wymuszonego przez rozwój internetu 2.0 i mediów społecznościowych.

Aktualna wersja algorytmu jest tajemnicą. Wiemy jednak, że ewoluuje i to chyba w dobrym kierunku.

 

Obraz tytułowy pochodzi z: http://xsenz.com/

1 comment

Leave a Comment

Your email address will not be published. Required fields are marked with *

Cancel reply

1 Comment

Inne artykuły