Cóż, nie jestem pewien, czy to MapReduce rozwiązuje problem, ale na pewno nie MapReduce sam by rozwiązać wszystkie te pytania. Ale oto ważne rzeczy, które należy wziąć pod uwagę, a to sprawia, że możliwe jest tak niskie opóźnienie na zapytania z wszystkich tych TB danych na różnych komputerach:
- przetwarzanie rozproszone: rozproszenie nie oznacza, że indeksy są po prostu dystrybuowane na różnych maszynach, w rzeczywistości są replikowane wzdłuż różnych klastrów, co pozwala wielu użytkownikom wykonywać różne zapytania przy krótkim czasie pobierania (tak, wielkie firmy mogą sobie na to pozwolić maszyn);
- buforowanie: pamięci podręczne znacznie skracają czas wykonywania, czy to dla etapu indeksowania, pobierania stron, czy rankingu i wyświetlania wyników;
- wiele ulepszeń: wszystkie powyższe i bardzo wydajne algorytmy / rozwiązania mogą być skuteczne tylko wtedy, gdy wdrożenie jest również wydajne. Istnieje mnóstwo optymalizacji (zakodowanych na stałe), takich jak lokalizacja odniesienia, kompresja, buforowanie; wszystkie z nich zwykle mają zastosowanie do różnych części przetwarzania.
Biorąc to pod uwagę, spróbujmy odpowiedzieć na twoje pytania:
ale wyobrażam sobie, że niemożliwe jest indeksowanie wyników każdego możliwego zapytania
Tak, byłoby i faktycznie jest niemożliwe uzyskanie wyników dla każdego możliwego zapytania . Na świecie istnieje nieskończona liczba haseł (nawet jeśli założymy, że zostaną wprowadzone tylko terminy poprawnie pisane), i istnieje wykładnicza liczba zapytań z tych n -> infterminów ( 2^n). Co jest zrobione? Buforowanie Ale jeśli jest tyle zapytań / wyników, które z nich buforować? Zasady buforowania. Najczęstsze / popularne / odpowiednie dla użytkownika zapytania są buforowane.
czy opóźnienie sprzętowe w sprzęcie Google nie byłoby ogromne? Nawet jeśli wszystkie dane w Google były przechowywane na dyskach SSD TB / s
W dzisiejszych czasach, przy tak wysoko rozwiniętych procesorach, ludzie myślą, że każde możliwe zadanie, które musi zakończyć się w ciągu sekundy (lub krócej) i które zajmuje tak dużo danych, musi być przetwarzane przez niezwykle wydajne procesory z wieloma rdzeniami i dużą ilością pamięci. Jednak jedyną rzeczą rządzącą rynkiem są pieniądze, a inwestorzy nie są zainteresowani ich marnowaniem. Co jest zrobione?
W rzeczywistości preferowane jest posiadanie dużej liczby maszyn, z których każda używa prostych / dostępnych (pod względem kosztów) procesorów, co obniża cenę tworzenia wielu klastrów. I tak, to działa. Główne wąskie gardło zawsze sprowadza się do dysku, jeśli weźmie się pod uwagę proste pomiary wydajności . Ale gdy jest już tak wiele maszyn, można sobie pozwolić na ładowanie rzeczy do pamięci głównej zamiast pracy na dyskach twardych.
Karty pamięci są dla nas drogie , zwykli ludzie, ale są bardzo tanie dla przedsiębiorstw, które kupują wiele takich kart naraz. Ponieważ nie jest to kosztowne, posiadanie wystarczającej ilości pamięci potrzebnej do ładowania indeksów i trzymania pod ręką pamięci podręcznej nie stanowi problemu. A ponieważ jest tak wiele maszyn, nie ma potrzeby stosowania superszybkich procesorów, ponieważ można kierować zapytania do różnych miejsc i mieć klastry maszyn odpowiedzialne za uczestnictwo w określonych regionach geograficznych , co pozwala na bardziej wyspecjalizowane buforowanie danych i jeszcze lepszą reakcję czasy.
Czy MapReduce pomaga rozwiązać ten problem?
Chociaż nie sądzę, aby korzystanie z MapReduce było ograniczonymi informacjami w Google, nie znam się na tym. Jednak implementacja MapReduce przez Google (która z pewnością nie jest Hadoop) musi zawierać wiele optymalizacji, z których wiele dotyczy aspektów omówionych powyżej. Tak więc architektura MapReduce prawdopodobnie pomaga ustalić, w jaki sposób obliczenia są fizycznie rozłożone, ale istnieje wiele innych punktów, które należy wziąć pod uwagę, aby uzasadnić taką szybkość w czasie zapytania.
Ok, rozumiem, że popularne wyszukiwania mogą być przechowywane w pamięci podręcznej. Ale co z niepopularnymi wyszukiwaniami?
Poniższy wykres przedstawia krzywą występowania rodzajów zapytań. Widać, że istnieją trzy główne rodzaje wyszukiwań, z których każde zawiera około 1/3 liczby zapytań (obszar poniżej krzywej). Fabuła pokazuje prawo mocy i potwierdza fakt, że mniejsze zapytania są najbardziej popularne. Druga trzecia część zapytań jest nadal możliwa do przetworzenia, ponieważ zawierają kilka słów. Ale zestaw tak zwanych niejasnych zapytań , które zwykle składają się z zapytań użytkowników nie doświadczonych, nie są nieistotną częścią zapytań.
I jest miejsce na nowe rozwiązania. Ponieważ nie jest to tylko jedno lub dwa zapytania (ale jedna trzecia z nich), muszą mieć odpowiednie wyniki. Jeśli wpiszesz coś zbyt niejasnego w wyszukiwarce Google, zwrócenie listy wyników nie zajmie więcej czasu, ale najprawdopodobniej pokaże ci coś, co można było wywnioskować . Lub może po prostu stwierdzić, że nie ma dokumentu z takimi terminami - lub nawet ograniczyć wyszukiwanie do 32 słów (co właśnie mi się przydarzyło podczas losowego testu tutaj).
Istnieją dziesiątki możliwych do zastosowania heurystyk, które mogą polegać na zignorowaniu niektórych słów lub próbie podzielenia zapytania na mniejsze i zebranie najbardziej popularnych wyników. A wszystkie te rozwiązania można dostosować i dostosować, aby szanowały możliwe czasy oczekiwania , powiedzmy, krótsze niż sekunda? :RE
MapReduce nie ma nic wspólnego z czymkolwiek w czasie rzeczywistym. Jest to zorientowana na partie struktura przetwarzania odpowiednia do niektórych zadań offline, takich jak ETL i budowanie indeksu. Google zrezygnował z MapReduce w przypadku większości zadań, a nawet ekosystem Hadoop robi to samo.
Odpowiedzią na małe opóźnienia jest na ogół zachowanie wstępnie obliczonych wskaźników w pamięci. Wszystko, co dotyka dysku, jest trudne do szybkiego i skalowania. W ten sposób silniki SQL nowej generacji, takie jak Impala, osiągają tak dużą prędkość w porównaniu z infrastrukturą opartą na MapReduce , na przykład Hive .
Infrastruktura wyszukiwania nie może buforować wyników każdego pojedynczego zapytania. Ale z pewnością może buforować wyniki pośrednie lub bardziej kompletne wyniki dla najpopularniejszych zapytań. Przy odrobinie buforowania możesz podawać wyniki dla znacznej mniejszości wszystkich zapytań.
Wyszukiwanie jest również podzielone na serwery. Tak więc jedna maszyna może delegować do 100, aby każdy uzyskał część wyniku, a następnie połączył je.
Możesz także uciec z pewnym przybliżeniem. Google nie tworzy dosłownie tysiąca stron wyników wyszukiwania; po prostu musi uzyskać pierwszą stronę.
Pamiętaj, że Google ma miliony komputerów na całym świecie. Twoje zapytania trafiają do centrum danych blisko ciebie, a to służy tylko twojej lokalizacji. Zmniejsza to większość opóźnień, którymi są sieci, a nie czas przetwarzania w centrum danych.
źródło
MapReduce nie jest używany podczas wyszukiwania. Dawno temu był używany do budowania indeksu; ale jest to struktura przetwarzania wsadowego, a większość sieci nie zmienia się cały czas, więc nowsze architektury są przyrostowe, a nie zorientowane wsadowo.
Wyszukiwanie w Google będzie w dużej mierze działać tak samo, jak działa w Lucene i Elastic Search, z wyjątkiem wielu drobiazgowych dodatków i optymalizacji. Ale w głębi serca będą używać jakiejś formy odwróconego indeksu . Innymi słowy, nie wyszukują kilku terabajtów po wprowadzeniu zapytania (nawet jeśli nie jest ono buforowane). Prawdopodobnie wcale nie patrzą na rzeczywiste dokumenty. Ale używają tabeli odnośników, która zawiera listę dokumentów pasujących do wyszukiwanego hasła (z wyszukiwaniem, pisownią, synonimami itp. - wszystkie wstępnie przetworzone). Prawdopodobnie pobierają listę 10000 najlepszych dokumentów dla każdego słowa (10 000 liczb całkowitych - zaledwie kilka kb!) I obliczają z nich najlepsze dopasowania. Tylko jeśli na tych listach nie ma dobrych dopasowań, są one rozwijane do następnych takich bloków itp.
Zapytania o typowe słowa można łatwo buforować; a dzięki przetwarzaniu wstępnemu możesz zbudować listę 10 000 najlepszych wyników, a następnie przesłać je ponownie zgodnie z profilem użytkownika. Obliczanie „dokładnej” odpowiedzi również nie daje żadnych korzyści. Prawdopodobnie wystarczy spojrzeć na 10 000 najlepszych wyników; nie ma poprawnej odpowiedzi; a jeśli lepszy wynik gdzieś na pozycji 10001 zostanie pominięty, nikt nie będzie wiedział ani nie zauważył (ani nie dbał). Prawdopodobnie został już sklasyfikowany w rankingu w procesie wstępnego przetwarzania i nie znalazłby się w pierwszej dziesiątce, która jest prezentowana użytkownikowi na końcu (lub w pierwszej trójce, na którą patrzy użytkownik)
Z drugiej strony rzadkie terminy nie stanowią większego wyzwania - jedna z list zawiera tylko kilka pasujących dokumentów i możesz natychmiast odrzucić wszystkie pozostałe.
Polecam przeczytanie tego artykułu:
I tak, to twórcy Google, którzy to napisali. To nie jest najnowszy stan, ale będzie już działał na dość dużą skalę.
źródło