Jak wdrożyłbyś wyszukiwarkę Google? [Zamknięte]

Załóżmy, że zapytano Cię w wywiadzie „Jak wdrożyłbyś wyszukiwarkę Google?” Jak odpowiedziałbyś na takie pytanie? Mogą istnieć zasoby, które wyjaśniają, w jaki sposób niektóre elementy w Google są implementowane (BigTable, MapReduce, PageRank, ...), ale to nie pasuje do wywiadu.

Jakiej ogólnej architektury byś użył i jak wyjaśniłbyś to w 15-30 minut?

Zacznę od wyjaśnienia, jak zbudować wyszukiwarkę, która obsługuje ~ 100 000 dokumentów, a następnie rozwinąć to poprzez sharding do około 50 milionów dokumentów, a następnie być może kolejny skok architektoniczny / techniczny.

To jest widok 20 000 stóp. To, co chciałbym, to szczegóły - jak w rzeczywistości odpowiedziałbyś na to w wywiadzie. Jakich struktur danych byś użył. Z jakich usług / maszyn składa się twoja architektura. Jakie byłoby typowe opóźnienie zapytania? Co z problemami pracy awaryjnej / podziału mózgu? Itp...

Zastanów się nad meta-punktem: czego szuka ankieter?

Takie gigantyczne pytanie nie szuka dla ciebie marnowania czasu na drobiazgowe wdrażanie algorytmu typu PageRank lub jak wykonać indeksowanie rozproszone. Zamiast tego skup się na pełnym obrazie tego, co by to zrobiło. Wygląda na to, że znasz już wszystkie duże elementy (BigTable, PageRank, Map / Reduce). Pytanie brzmi zatem, jak je właściwie połączyć?

Oto moje dźgnięcie.

Faza 1: Indeksowanie infrastruktury (poświęć 5 minut na wyjaśnianie)

Pierwszym etapem wdrażania Google (lub dowolnej wyszukiwarki) jest zbudowanie indeksera. Jest to oprogramowanie, które indeksuje korpus danych i daje wyniki w strukturze danych, która jest bardziej wydajna w przypadku odczytu.

Aby to zaimplementować, rozważ dwie części: przeszukiwacz i indeksator.

Robot indeksujący ma za zadanie spajanie linków do stron internetowych i wrzucanie ich do zestawu. Najważniejszym krokiem tutaj jest uniknięcie wpadnięcia w nieskończoną pętlę lub nieskończenie generowaną zawartość. Umieść każdy z tych łączy w jednym ogromnym pliku tekstowym (na razie).

Po drugie, indeksator będzie działał jako część zadania Map / Reduce. (Przypisz funkcję do każdego elementu na wejściu, a następnie zmniejsz wyniki do jednej „rzeczy”.) Indeksator pobierze pojedyncze łącze internetowe, pobierze stronę internetową i przekształci ją w plik indeksu. (Omówiono dalej.) Krokiem redukcji będzie po prostu agregacja wszystkich tych plików indeksu w jedną jednostkę. (Zamiast milionów luźnych plików.) Ponieważ etapy indeksowania można wykonywać równolegle, możesz wykonać to zadanie Mapuj / Zmniejsz w dowolnym dużym centrum danych.

Faza 2: Specyfika algorytmów indeksowania (poświęć 10 minut na wyjaśnianie)

Po określeniu sposobu przetwarzania stron internetowych następna część wyjaśnia, w jaki sposób można obliczyć znaczące wyniki. Krótka odpowiedź brzmi: „dużo więcej map / redukcji”, ale zastanów się, jakie rzeczy możesz zrobić:

• Dla każdej strony internetowej policz liczbę linków przychodzących. (Bardziej linkowane do stron powinny być „lepsze”).
• Dla każdej strony internetowej sprawdź, jak prezentowany jest link. (Linki w <h1> lub <b> powinny być ważniejsze niż te zakopane w <h3>.)
• Dla każdej strony internetowej sprawdź liczbę linków wychodzących. (Nikt nie lubi spamerów.)
• Dla każdej strony internetowej sprawdź rodzaje użytych słów. Na przykład „skrót” i „tabela” prawdopodobnie oznaczają, że strona internetowa jest związana z informatyką. Z drugiej strony „hash” i „brownies” sugerowałyby, że strona dotyczy czegoś zupełnie innego.

Niestety nie wiem wystarczająco dużo o sposobach analizowania i przetwarzania danych, aby być bardzo pomocnym. Ale ogólną ideą są skalowalne sposoby analizy danych .

Faza 3: Podawanie wyników (poświęć 10 minut na wyjaśnianie)

Ostatnia faza faktycznie służy wynikom. Mamy nadzieję, że podzieliłeś się kilkoma interesującymi spostrzeżeniami na temat analizowania danych na stronach internetowych, ale pytanie brzmi: w jaki sposób faktycznie je przeszukujesz? Anegdotycznie 10% zapytań wyszukiwanych przez Google każdego dnia nie było nigdy wcześniej. Oznacza to, że nie można buforować poprzednich wyników.

Nie możesz mieć jednego „wyszukiwania” ze swoich indeksów internetowych, więc co byś spróbował? Jak wyglądałbyś w różnych indeksach? (Być może łączenie wyników - być może słowo kluczowe „stackoverflow” pojawiło się wysoko w wielu indeksach).

Poza tym, jak byś to wyszukał? Jakiego rodzaju podejścia możesz użyć do szybkiego odczytu danych z ogromnej ilości informacji? (Zachęcamy do nazwania ulubionej bazy danych NoSQL tutaj i / lub sprawdzenia, o co chodzi w BigTable Google.) Nawet jeśli masz niesamowity indeks, który jest bardzo dokładny, potrzebujesz sposobu, aby szybko znaleźć w nim dane. (Np. Znajdź numer rangi „stackoverflow.com” w pliku o pojemności 200 GB.)

Losowe problemy (pozostały czas)

Po zapoznaniu się z „kośćmi” swojej wyszukiwarki możesz swobodnie wyłapywać każdy indywidualny temat, o którym szczególnie wiesz.

• Wydajność frontendu strony
• Zarządzanie centrum danych dla zadań Map / Reduce
• A / B testuje ulepszenia wyszukiwarki
• Zintegrowanie poprzedniej liczby operacji wyszukiwania / trendów w indeksowaniu. (Np. Spodziewając się, że obciążenia serwera frontendowego wzrosną o 9-5 i umrą na początku AM).

Oczywiście jest tu ponad 15 minut materiału do omówienia, ale mam nadzieję, że to wystarczy, aby zacząć.

Post Quora dało oryginalny artykuł opublikowany przez Sergey Brin i Larry Page. Wydaje się być doskonałym punktem odniesienia dla tego typu pytań.