Stało się to kilka dni temu . Chłopaki z JUG.ru Group zaprosili prelegentów marzeń (Leslie Lamport! Cliff Click! Martin Kleppmann!) i poświęcili dwa dni systemom rozproszonym i informatyce. Kontur był jednym z trzech partnerów konferencji. Rozmawialiśmy na stoisku, rozmawialiśmy o naszym rozproszonym magazynie, graliśmy w bingo i rozwiązywaliśmy zagadki.
To post z analizą zadań na stoisku Kontur od autora ich tekstu. Kto był na Hydrze - to jest twój powód do zapamiętania przyjemnego doświadczenia, kto nie był - szansa na rozciąganie mózgu duże O-notacja.
Byli nawet uczestnicy, którzy rozkładali flipchart na slajdy, aby zapisać swoją decyzję. Nie żartuję - przekazali ten stos papierów do weryfikacji:
W sumie były trzy zadania:
- o wybieraniu replik według wag do równoważenia obciążenia
- o sortowaniu wyników zapytania względem bazy danych w pamięci
- na transferze stanu w systemie rozproszonym o topologii pierścienia
Zadanie 1. Klient klastra
Konieczne było zaproponowanie algorytmu efektywnego wyboru K spośród N ważonych replik systemu rozproszonego:
Twój zespół ma za zadanie opracować bibliotekę kliencką dla masowo rozproszonego klastra N węzłów. Biblioteka śledziłaby różne metadane związane z węzłami (np. ich opóźnienia, współczynniki odpowiedzi 4xx/5xx itp.) i przypisywałaby im wagi zmiennoprzecinkowe W1..WN. Aby wspierać strategię wykonywania współbieżnego, biblioteka powinna mieć możliwość losowego wybierania K z N węzłów — szansa na wybranie powinna być proporcjonalna do wagi węzła.
Zaproponuj algorytm efektywnego wybierania węzłów. Oszacuj jego złożoność obliczeniową za pomocą notacji dużego O.
Dlaczego wszystko jest po angielsku?
Bo w takiej formie walczyli z nimi uczestnicy konferencji i dlatego, że językiem urzędowym Hydry był angielski. Zadania wyglądały tak:
Weź papier i ołówek, pomyśl, nie spiesz się, aby od razu otwierać spoilery 🙂
Analiza rozwiązania (wideo)
Od 5:53, tylko 4 minuty:
A oto jak faceci z flipchartem przedstawili swoje rozwiązanie:
Analiza rozwiązania (tekst)
Na powierzchni leży następujące rozwiązanie: zsumuj wagi wszystkich replik, wygeneruj liczbę losową od 0 do sumy wszystkich wag, a następnie wybierz i-replikę tak, aby suma wag replik od 0 do (i-1) jest mniejsza od liczby losowej, a suma wag replik od 0 do i-tej - większa od niej. Będzie więc można wybrać jedną replikę, a żeby wybrać następną trzeba powtórzyć całą procedurę bez brania pod uwagę wybranej repliki. Przy takim algorytmie złożoność wyboru jednej repliki wynosi O(N), złożoność wyboru K replik to O(N K) ~ O(N2).
Złożoność kwadratowa jest zła, ale można ją poprawić. Aby to zrobić, zbudujemy dla sum wag. Otrzymamy drzewo o głębokości lg N, w liściach których będą wagi replik, aw pozostałych węzłach sumy cząstkowe, aż do sumy wszystkich wag u podstawy drzewa. Następnie generujemy liczbę losową od 0 do sumy wszystkich wag, znajdujemy i-tą replikę, usuwamy ją z drzewa i powtarzamy procedurę, aby znaleźć pozostałe repliki. Przy tym algorytmie złożoność budowy drzewa wynosi O(N), złożoność znalezienia i-tej repliki i usunięcia jej z drzewa wynosi O(lg N), złożoność wyboru K replik wynosi O(N + K lg N) ~ O (N lg N) .
Złożoność logarytmu liniowego jest lepsza niż złożoność kwadratowa, zwłaszcza dla dużych K.
To jest ten algorytm Biblioteki ClusterClient z projektu "". (Tam drzewo jest zbudowane w O(N lg N), ale nie wpływa to na ostateczną złożoność algorytmu.)
Zadanie 2. Zebra
Konieczne było zaproponowanie algorytmu sprawnego sortowania dokumentów w pamięci według dowolnego nieindeksowanego pola:
Twój zespół ma za zadanie opracować podzieloną na fragmenty bazę danych dokumentów w pamięci. Typowym obciążeniem byłoby wybranie pierwszych N dokumentów posortowanych według dowolnego (nieindeksowanego) pola liczbowego ze zbioru o rozmiarze M (zwykle N < 100 << M). Nieco mniej powszechnym obciążeniem byłoby wybranie górnego N po pominięciu pierwszych S dokumentów (S ~ N).
Zaproponuj algorytm efektywnego wykonywania takich zapytań. Oszacuj jego złożoność obliczeniową za pomocą notacji dużego O w przypadku średnim i najgorszym.
Analiza rozwiązania (wideo)
Od 34:50, tylko 6 minut:
Analiza rozwiązania (tekst)
Rozwiązanie Surface: sortuj wszystkie dokumenty (np ), a następnie weź dokumenty N+S. W tym przypadku złożoność sortowania wynosi średnio O(M lg M), w najgorszym przypadku O(M2).
Oczywiste jest, że sortowanie wszystkich dokumentów M, a następnie wzięcie tylko niewielkiej ich części jest nieefektywne. Aby nie sortować wszystkich dokumentów, odpowiedni jest algorytm , który wybierze N + S żądanych dokumentów (można je posortować według dowolnego algorytmu). W takim przypadku złożoność zmniejszy się średnio do O(M), podczas gdy najgorszy przypadek pozostanie taki sam.
Możesz jednak zrobić to jeszcze wydajniej – skorzystaj z algorytmu . W tym przypadku pierwsze dokumenty N+S są dodawane do min- lub max-heap (w zależności od kierunku sortowania), a następnie każdy kolejny dokument jest porównywany z korzeniem drzewa, które zawiera aktualny dokument minimalny lub maksymalny, i jest dodawany do drzewa w razie potrzeby. . W tym przypadku złożoność w najgorszym przypadku, gdy trzeba stale przebudowywać drzewo, wynosi O(M lg M), złożoność średnio wynosi O(M), tak jak w przypadku szybkiego wyboru.
Strumieniowanie sterty okazuje się jednak bardziej wydajne ze względu na to, że w praktyce większość dokumentów można odrzucić bez odbudowywania sterty po pojedynczym porównaniu z jej elementem głównym. Takie sortowanie jest zaimplementowane w bazie danych dokumentów Zebra in-memory opracowanej i wykorzystywanej w Konturze.
Zadanie 3. Zamiany stanów
Konieczne było zaproponowanie najbardziej wydajnego algorytmu przesuwania stanów:
Twój zespół ma za zadanie opracować wymyślny mechanizm wymiany stanów dla rozproszonego klastra N węzłów. Stan i-tego węzła należy przenieść do (i+1)-tego węzła, stan N-tego węzła należy przenieść do węzła pierwszego. Jedyną obsługiwaną operacją jest zamiana stanów, gdy dwa węzły wymieniają swoje stany atomowo. Wiadomo, że zmiana stanu trwa M milisekund. Każdy węzeł może uczestniczyć w pojedynczej wymianie stanu w dowolnym momencie.
Jak długo trwa przesyłanie stanów wszystkich węzłów w klastrze?
Analiza rozwiązania (tekst)
Rozwiązanie powierzchniowe: zamień stany pierwszego i drugiego elementu, potem pierwszego i trzeciego, potem pierwszego i czwartego i tak dalej. Po każdej wymianie stan jednego elementu będzie w pożądanej pozycji. Musisz wykonać permutacje O(N) i spędzić O(N M) czasu.
Czas liniowy jest długi, więc można wymieniać stany elementów parami: pierwszy z drugim, trzeci z czwartym i tak dalej. Po każdej wymianie stanu co drugi element będzie na właściwej pozycji. Musisz wykonać permutacje O(lg N) i spędzić czas O(M lg N).
Jednak możliwe jest, aby przesunięcie było jeszcze bardziej wydajne - nie w czasie liniowym, ale w czasie stałym. Aby to zrobić, w pierwszym kroku musisz zamienić stan pierwszego elementu z ostatnim, drugiego z przedostatnim i tak dalej. Stan ostatniego elementu będzie w prawidłowej pozycji. I teraz musimy zamienić stan drugiego elementu z ostatnim, trzeciego z przedostatnim i tak dalej. Po tej rundzie wymian stany wszystkich elementów będą na właściwym miejscu. W sumie będą permutacje O(2M) ~ O(1).
Takie rozwiązanie wcale nie zdziwi matematyka, który pamięta jeszcze, że obrót jest złożeniem dwóch symetrii osiowych. Nawiasem mówiąc, jest to trywialnie uogólnione dla przesunięcia nie o jeden, ale o pozycje K < N. (Napisz w komentarzach jak dokładnie.)
Lubiłeś łamigłówki? Znasz inne rozwiązania? Podziel się w komentarzach.
A oto kilka przydatnych linków na koniec:
- dowiedz się więcej o w konturze
- zobacz zapisy wewnętrzne o systemach rozproszonych
- obejrzyj serię wykładów wideo»
- zapisz się do naszego
Źródło: www.habr.com