Znajdź 10 najczęściej odwiedzanych adresów URl, dane są przechowywane w sieci

Źródło: Google Interview Question

Biorąc pod uwagę dużą sieć komputerów, z których każdy przechowuje pliki logów odwiedzanych adresów URL, Znajdź pierwszą dziesiątkę najczęściej odwiedzanych adresów URL.

Mają wiele dużych <string (url) -> int (visits)> maps.

Oblicz < string (url) -> int (sum of visits among all distributed maps) i zdobądź pierwszą dziesiątkę na mapie połączonej.

Główne ograniczenie: mapy są zbyt duże, aby przesyłać je przez sieć. Nie można również używać MapReduce bezpośrednio.

Natknąłem się teraz na kilka pytań tego typu, gdzie processjong musi odbywać się na dużych systemach rozproszonych. Nie mogę myśleć ani znaleźć odpowiedniej odpowiedzi.

wszystko, co przyszło mi do głowy, to brutalna siła, która w jakiś czy inny sposób narusza dane ograniczenie.

Author: Community, 2013-07-29
Source

2 answers

Mówi, że nie możesz używać map-reduce bezpośrednio co jest wskazówką autor pytania chce, abyś pomyślał, jak działa Map reduce, więc będziemy naśladować działania map-reduce:

  1. pre-processing: niech R będzie liczbą serwerów w klastrze, daj każdemu server unique id od 0,1,2,..., R-1
  2. (map) for each (string,id) - wyślij krotkę do serwera, który ma id hash(string) % R.
  3. (reduce) po wykonaniu kroku 2 (simple control communication), produce (string,count) z 10 pierwszych ciągów na serwer. Zauważ, że krotki, gdzie te wysłane w Kroku 2 do tego konkretnego serwera.
  4. (Mapa) każdy serwer wyśle wszystkie swoje top 10 do 1 serwera (niech będzie to serwer 0). Powinno być dobrze, jest tylko 10*R tych rekordów.
  5. (reduce) Serwer 0 uzyska top 10 w całej sieci.

Uwagi:

  • problem z algorytmem, podobnie jak większość algorytmów big-data, które nie używaj frameworków to nie działa serwery. MapReduce bierze zajmę się tym za Ciebie.
  • powyższy algorytm można przetłumaczyć na dwufazowy algorytm zmniejszania map całkiem prosto do przodu.
 12
Author: amit,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-02-23 18:20:31

W najgorszym przypadku każdy algorytm , który nie wymaga transmisji całej tabeli częstotliwości, zakończy się niepowodzeniem. Możemy stworzyć banalny przypadek, w którym globalne Top-10s znajdują się na dole każdej listy maszyn.

Jeśli założymy, że częstotliwość URI jest zgodna z prawem Zipfa, możemy wymyślić skuteczne rozwiązania. Oto jedno z takich rozwiązań.

Każda maszyna wysyła elementy top-K. K zależy wyłącznie od dostępnej przepustowości. One master machine agreguje częstotliwości i znajduje dziesiątą maksymalną wartość częstotliwości " V10 " (zauważ, że jest to dolna granica. Ponieważ globalny top-10 może nie znajdować się w top-K każdej maszyny, suma jest niekompletna).

W następnym kroku każda maszyna wysyła listę Uri, której częstotliwość wynosi V10 / m (gdzie M to liczba maszyn). Związek wszystkich takich jest wysyłany z powrotem do każdej maszyny. Każda maszyna z kolei odsyła częstotliwość dla tej konkretnej listy. Mistrz agreguje tę listę w top-10 lista.

 3
Author: ElKamina,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-07-29 16:58:59