it-swarm-eu.dev

Jak byste implementovali Vyhledávání Google?

Předpokládalo se, že jste byli dotazováni v rozhovoru „Jak byste implementovali Vyhledávání Google?“ Jak byste odpověděl na takovou otázku? Tam mohou být zdroje, které vysvětlují, jak jsou některé části Google implementovány (BigTable, MapReduce, PageRank, ...), ale to se přesně nehodí do rozhovoru.

Jakou celkovou architekturu byste použili a jak byste to vysvětlili v časovém rozmezí 15–30 minut?

Začal bych vysvětlením, jak vytvořit vyhledávací stroj, který zpracovává ~ 100 000 dokumentů, a pak to rozšířením shardingem na přibližně 50 milionů dokumentů, pak možná dalším architektonickým/technickým skokem.

Toto je pohled na 20 000 stop. Co bych si přál, jsou podrobnosti - jak byste na to skutečně odpověděli v rozhovoru. Které datové struktury byste použili. Z jakých služeb/strojů se skládá vaše architektura. Jaká by byla typická latence dotazu? A co failover/split mozkové problémy? Atd...

47
ripper234

příspěvek na Quora přinesl původní článek publikován Sergey Brin a Larry Page. Zdá se, že je to vynikající reference pro tento typ otázky.

Google Architecture

19
ripper234

Zvažte meta-bod: co tazatel hledá?

Mamutí otázka, jako je ta, nehledá, že byste ztrácel čas tím, že budete implementovat algoritmus typu PageRank nebo jak provádět distribuované indexování. Místo toho se zaměřte na úplný obrázek toho, co by to vyžadovalo. Zní to, že už znáte všechny velké kousky (BigTable, PageRank, Map/Reduce). Otázkou tedy je, jak je vlastně dáte dohromady?

Tady je moje bodnutí.

Fáze 1: Indexování infrastruktury (strávit 5 minut vysvětlením)

První fáze implementace Google (nebo jakéhokoli vyhledávače) je vytvoření indexátoru. Toto je část softwaru, která prochází korpus dat a vytváří výsledky ve struktuře dat, která je efektivnější pro čtení.

Chcete-li to implementovat, zvažte dvě části: prolézací modul a indexátor.

Úlohou webového prolézacího modulu je spider propojení webových stránek a výpis z nich do sady. Nejdůležitějším krokem je vyhnout se zachycení v nekonečné smyčce nebo na nekonečně generovaném obsahu. Umístěte každý z těchto odkazů do jednoho velkého textového souboru (prozatím).

Za druhé, indexátor bude spuštěn jako součást úlohy Map/Reduce. (Mapujte funkci na každou položku ve vstupu a poté snižte výsledky na jednu „věc“.) Indexátor vezme jeden webový odkaz, načte web a převede jej do indexového souboru. (Diskutováno dále.) Krok redukce jednoduše sloučí všechny tyto indexové soubory do jedné jednotky. (Spíše než miliony volných souborů.) Protože kroky indexování lze provádět paralelně, můžete tuto úlohu Map/Reduce zpracovat v libovolně velkém datovém centru.

Fáze 2: Specifika indexovacích algoritmů (strávit 10 minut vysvětlením)

Poté, co jste uvedli, jak budete webové stránky zpracovávat, je v další části vysvětleno, jak lze spočítat smysluplné výsledky. Krátká odpověď je „mnohem více map/redukcí“, ale zvažte druhy věcí, které můžete udělat:

  • U každého webu spočítejte počet příchozích odkazů. (Silněji propojené stránky by měly být „lepší“.)
  • U každého webu zkontrolujte, jak byl odkaz představen. (Odkazy v <h1> nebo <b> by měly být důležitější než odkazy v <h3>.)
  • U každého webového serveru se podívejte na počet odchozích odkazů. (Nikdo nemá rád spammery.)
  • Pro každý web se podívejte na typy použitých slov. Například „hash“ a „tabulka“ pravděpodobně znamenají, že web souvisí s informatikou. 'hash' a 'brownies' na druhé straně by znamenaly, že web byl o něčem mnohem jiném.

Bohužel nevím dost o nejrůznějších způsobech, jak analyzovat a zpracovat data tak, aby byla velmi užitečná. Obecná myšlenka je škálovatelné způsoby analýzy vašich dat .

Fáze 3: Výsledky zobrazování (strávit 10 minut vysvětlením)

Závěrečná fáze skutečně slouží výsledkům. Doufejme, že jste sdíleli několik zajímavých poznatků o tom, jak analyzovat data webových stránek, ale otázkou je, jak je skutečně dotazujete? Anekdotálně 10% vyhledávacích dotazů Google každý den dosud nebylo nikdy vidět. To znamená, že nemůžete ukládat předchozí výsledky do mezipaměti.

Nemůžete mít jediné „vyhledávání“ z vašich webových indexů, tak co byste zkusili? Jak byste se dívali napříč různými indexy? (Možná kombinace výsledků - možná klíčové slovo „stackoverflow“ se objevilo ve více indexech.)

Jak byste to vlastně hledali? Jaké druhy přístupů můžete použít pro rychlé čtení dat z masivního množství informací? (Neváhejte a pojmenujte svou oblíbenou databázi NoSQL zde a/nebo se podívejte, o čem je Google BigTable.) I když máte úžasný index, který je vysoce přesný, potřebujete v něm rychle najít data. (Např. Najděte pořadové číslo „stackoverflow.com“ uvnitř souboru o velikosti 200 GB.)

Náhodné problémy (zbývající čas)

Jakmile zakryjete „kosti“ vašeho vyhledávače, neváhejte potkávat díru v jakémkoli individuálním tématu, o kterém jste obeznámeni.

  • Výkon rozhraní webové stránky
  • Správa datového centra pro úlohy Map/Reduce
  • Vylepšení vyhledávacího modulu A/B
  • Integrace předchozího objemu vyhledávání/trendů do indexování. (Např. Očekávání, že se zatížení frontendového serveru zvýší na 9–5 a brzy odejde).)

Je tu zjevně více než 15 minut materiálu na diskuzi, ale doufejme, že to stačí, abyste mohli začít.

46
Chris Smith