Jak Google może działać tak szybko?

Jakie technologie i decyzje programowe sprawiają, że Google jest w stanie tak szybko obsłużyć zapytanie?

Za każdym razem, gdy czegoś szukam (raz na kilka razy dziennie), zawsze zadziwia mnie to, jak podają wyniki w mniej niż 1 sekundę. Jaką konfigurację i algorytmy mogliby zastosować, aby to osiągnąć?

Uwaga dodatkowa: to trochę przytłaczające myślenie, że nawet gdybym zainstalował aplikację komputerową i używał jej na moim komputerze, prawdopodobnie nie byłbym w połowie tak szybki jak Google. Ucz się dalej, mówię.

Oto kilka wspaniałych odpowiedzi i wskazówek:

• Platforma Google
• Map Reduce
• Starannie opracowane algorytmy
• Sprzęt - farmy klastrów i ogromna liczba tanich komputerów
• Buforowanie i równoważenie obciążenia
• System plików Google

Opóźnienie jest zabijane przez dostęp do dysku. Dlatego rozsądnie jest sądzić, że wszystkie dane używane do odpowiedzi na zapytania są przechowywane w pamięci. Oznacza to tysiące serwerów, z których każdy replikuje jeden z wielu shardów. Dlatego jest mało prawdopodobne, aby krytyczna ścieżka wyszukiwania trafiła w którąkolwiek z ich flagowych technologii systemów rozproszonych GFS, MapReduce lub BigTable. Będą one używane do przetwarzania wyników przeszukiwacza.

Poręczną rzeczą w wyszukiwaniu jest to, że nie ma potrzeby posiadania ani mocno spójnych wyników, ani całkowicie aktualnych danych, więc Google nie jest pozbawione odpowiedzi na zapytanie, ponieważ stały się bardziej aktualne wyniki wyszukiwania.

Możliwa architektura jest więc dość prosta: serwery frontonu przetwarzają zapytanie, normalizują je (prawdopodobnie poprzez usuwanie słów pomijanych itp.), A następnie dystrybuują je do dowolnego podzbioru replik, które posiada tę część przestrzeni zapytania (alternatywną architekturą jest podzielenie danych przez strony internetowe, tak że w przypadku każdego zapytania należy kontaktować się z jednym z każdego zestawu replik). Prawdopodobnie wiele, wiele replik jest pytanych, a najszybsze odpowiedzi wygrywają. Każda replika ma indeksowane zapytania (lub indywidualne terminy zapytań) do dokumentów, których mogą używać do bardzo szybkiego wyszukiwania wyników w pamięci. Jeśli różne wyniki pochodzą z różnych źródeł, serwer frontonu może je uszeregować, wypluwając html.

Zwróć uwagę, że jest to prawdopodobnie bardzo różne od tego, co faktycznie robi Google - zaprojektowali życie poza tym systemem, więc może być więcej pamięci podręcznych w dziwnych obszarach, dziwne indeksy i jakiś fajny schemat równoważenia obciążenia wśród innych możliwych różnic .

To trochę za dużo, żeby ująć to w jednej odpowiedzi. http://en.wikipedia.org/wiki/Google_platform

Jednym z faktów, które wydały mi się zabawne, jest to, że Google jest w rzeczywistości prowadzony przez bioinformatykę („okej, uważam to za zabawne, ponieważ jestem bioinfekcją… rzecz). Pozwól mi wyjaśnić.

Bioinformatycy wcześnie musieli bardzo szybko przeszukiwać małe teksty w gigantycznych strunach. Dla nas „gigantyczna struna” to oczywiście DNA. Często nie jest to pojedynczy DNA, ale baza danych zawierająca kilka DNA różnych gatunków / osobników. Małe teksty to białka lub ich genetyczny odpowiednik, gen. Większość pierwszych prac biologów obliczeniowych ograniczała się do znalezienia homologii między genami. Odbywa się to w celu ustalenia funkcji nowo odkrytych genów poprzez odnotowanie podobieństw do genów, które są już znane.

Teraz te ciągi DNA stają się rzeczywiście bardzo duże i (stratne!) Wyszukiwanie musi być wykonywane niezwykle wydajnie. Większość współczesnej teorii wyszukiwania ciągów została więc rozwinięta w kontekście biologii obliczeniowej.

Jednak jakiś czas temu konwencjonalne wyszukiwanie tekstu zostało wyczerpane. Potrzebne było nowe podejście, które umożliwi przeszukiwanie dużych ciągów w czasie podliniowym, to znaczy bez patrzenia na każdy pojedynczy znak. Odkryto, że można to rozwiązać, wstępnie przetwarzając duży ciąg i budując na nim specjalną strukturę danych indeksu. Zaproponowano wiele różnych takich struktur danych. Każdy ma swoje mocne i słabe strony, ale jest jeden, który jest szczególnie niezwykły, ponieważ umożliwia wyszukiwanie w ciągłym czasie. Teraz, jeśli chodzi o rzędy wielkości, w których działa Google, nie jest to już do końca prawdą, ponieważ należy wziąć pod uwagę równoważenie obciążenia między serwerami, przetwarzanie wstępne i inne wyrafinowane rzeczy.

Ale w istocie tak zwany indeks q-gramów umożliwia wyszukiwanie w stałym czasie. Jedyna wada: struktura danych robi się śmiesznie duża. Zasadniczo, aby umożliwić wyszukiwanie ciągów zawierających do q znaków (stąd nazwa), wymaga tabeli zawierającej jedno pole dla każdej możliwej kombinacji liter q (to znaczy q ^S , gdzie S jest rozmiarem alfabetu powiedzmy 36 (= 26 + 10)). Dodatkowo musi istnieć jedno pole dla każdej pozycji litery w indeksowanym ciągu (lub w przypadku Google, dla każdej witryny internetowej).

Aby złagodzić sam rozmiar, Google prawdopodobnie użyje wielu indeksów (w rzeczywistości robi to , aby zaoferować usługi takie jak korekta pisowni). Te najwyższe nie będą działać na poziomie postaci, ale zamiast tego na poziomie słów. Zmniejsza to q, ale sprawia, że S jest nieskończenie większe, więc będą musieli używać tablic mieszania i kolizji, aby poradzić sobie z nieskończoną liczbą różnych słów.

Na następnym poziomie te zaszyfrowane słowa będą wskazywały na inne struktury danych indeksu, które z kolei będą oznaczać znaki skrótu wskazujące strony internetowe.

Krótko mówiąc, te struktury danych indeksu q- gramów są prawdopodobnie najbardziej centralną częścią algorytmu wyszukiwania Google. Niestety, nie ma dobrych artykułów nietechnicznych wyjaśniających, jak działają indeksy q -gram. Jedyna znana mi publikacja zawierająca opis działania takiego indeksu to… niestety moja praca licencjacka .

Oto kilka wspaniałych odpowiedzi i wskazówek:

• Platforma Google
• Map Reduce
• Starannie opracowane algorytmy
• Sprzęt - farmy klastrów i ogromna liczba tanich komputerów
• Buforowanie i równoważenie obciążenia
• System plików Google

Wdrożyli dobre, rozproszone algorytmy działające na ogromnej ilości sprzętu.

Jednym z najważniejszych opóźnień jest to, że serwery WWW powodują przesłanie zapytania do serwera WWW i zwrot odpowiedzi. To opóźnienie jest ograniczone prędkością światła, której nawet Google musi przestrzegać. Jednak mają centra danych na całym świecie. W rezultacie średnia odległość do dowolnego z nich jest mniejsza. Dzięki temu opóźnienie jest mniejsze. Jasne, różnica jest mierzona w milisekundach, ale ma znaczenie, jeśli odpowiedź ma nadejść w ciągu 1000 milisekund.

Wszyscy wiedzą, że to dlatego, że oczywiście używają gołębi !

O tak, to i Mapreduce.

Prawie mają lokalną kopię Internetu buforowaną na tysiącach komputerów w niestandardowych systemach plików.

Google zatrudnia najlepszych z najlepszych. W Google pracują jedni z najmądrzejszych osób w IT. Mają praktycznie nieskończone pieniądze do rzucenia w sprzęt i inżynierów.

Używają wysoce zoptymalizowanych mechanizmów przechowywania danych do wykonywanych zadań.

Mają farmy serwerów zlokalizowane geograficznie.

Próba uogólnionej listy (która nie zależy od tego, czy masz dostęp do wewnętrznych narzędzi Google):

1. Parellelize żądań (np. Podziel pojedyncze żądanie na mniejsze zestawy)
2. Asynchroniczny (aby jak najwięcej jak to możliwe asynchronious np nie będzie blokować żądania użytkownika)
3. Pamięć / pamięć podręczna (operacje wejścia / wyjścia dysku są wolne, należy zachować jak najwięcej w pamięci)
4. Oblicz wstępnie (wykonaj jak najwięcej pracy, nie czekaj, aż użytkownik poprosi o dane / przetwarzanie)
5. Dbaj o swój front-end HTML (zobacz Yslow i przyjaciele)

Na stronie głównej badań Google można znaleźć wskazówki na temat artykułów naukowych napisanych przez niektórych ludzi z Google. Powinieneś zacząć od wyjaśnienia systemu plików google i algorytmu mapowania / redukcji, aby spróbować zrozumieć, co dzieje się za stronami Google.

Ten link jest również bardzo pouczający Za kulisami zapytania Google

Sprzęt komputerowy.

Bardzo dużo sprzętu. Używają ogromnych klastrów zwykłych komputerów PC jako farmy serwerów.

TraumaPony ma rację. Mnóstwo serwerów i inteligentna architektura do równoważenia obciążenia / buforowania i voila, możesz uruchomić zapytanie w mniej niż 1 sekundę. W sieci było wiele artykułów opisujących architekturę usług Google. Jestem pewien, że możesz je znaleźć przez Google :)

HenryR prawdopodobnie ma rację.

Map Reduce nie odgrywa roli dla samego wyszukiwania, ale służy tylko do indeksowania. Obejrzyj ten wywiad wideo z wynalazcami Map Reduce .

Dodatkowym powodem wydaje się być to, że oszukują algorytm wolnego startu TCP.

http://blog.benstrong.com/2010/11/google-and-microsoft-cheat-on-slow.html

Oraz algorytmy, które potrafią wykorzystać tę moc sprzętu. Jak MapReduce na przykład.

Jeśli interesuje Cię więcej szczegółów na temat działania klastra Google, zasugeruję tę otwartą implementację ich HDFS .

Opiera się na Mapreduce firmy Google.

1. Wielostopniowe przechowywanie, przetwarzanie i odzyskiwanie danych

2. WYDAJNA dystrybucja (setki z tysięcy maszyn) powyższych zadań

3. Dobra struktura do przechowywania surowych danych i przetworzonych wyników

4. Dobre ramy do pobierania wyników

Sposób, w jaki dokładnie to wszystko jest zrobione, podsumowuje wszystkie linki, które masz w podsumowaniu pytania