Stalo se to před pár dny Konference Hydra. Kluci ze skupiny JUG.ru pozvali řečníky snů (Leslie Lamport! Cliff Click! Martin Kleppmann!) a dva dny věnovali distribuovaným systémům a počítačům. Kontur byl jedním ze tří partnerů konference. Povídali jsme si u stánku, mluvili o našem distribuovaném úložišti, hráli bingo a řešili hádanky.

Toto je příspěvek s rozborem úkolů na stánku Kontur od autora jejich textu. Kdo byl na Hydra - to je váš důvod, abyste si připomněli příjemný zážitek, kdo nebyl - šance protáhnout si mozek velký O- zápis.

Byli dokonce účastníci, kteří rozebrali flipchart na snímky, aby zapsali své rozhodnutí. Nedělám si legraci - předali k ověření tento stoh papíru:

Úkoly byly celkem tři:

• o výběru replik podle vah pro vyvažování zátěže
• o řazení výsledků dotazů podle databáze v paměti
• o přenosu stavu v distribuovaném systému s kruhovou topologií

Úkol 1. ClusterClient

Bylo nutné navrhnout algoritmus pro efektivní výběr K z N vážených replik distribuovaného systému:

Váš tým má za úkol vyvinout klientskou knihovnu pro masivně distribuovaný cluster N uzlů. Knihovna by sledovala různá metadata spojená s uzly (např. jejich latence, rychlost odezvy 4xx/5xx atd.) a přidělovala by jim váhy s plovoucí desetinnou čárkou W1..WN. Aby byla podporována strategie souběžného provádění, knihovna by měla být schopna vybrat K z N uzlů náhodně – šance na výběr by měla být úměrná váze uzlu.

Navrhněte algoritmus pro efektivní výběr uzlů. Odhadněte jeho výpočetní složitost pomocí velkého O zápisu.

Proč je vše v angličtině?

Protože v této podobě s nimi účastníci konference bojovali a protože angličtina byla oficiálním jazykem Hydry. Úkoly vypadaly takto:

Vezměte si papír a tužku, přemýšlejte, nespěchejte hned s otevíráním spoilerů 🙂

Analýza řešení (video)

Začátek v 5:53, pouhé 4 minuty:

A tady je, jak kluci s flipchartem představili své řešení:

Analýza řešení (text)

Na povrchu leží následující řešení: sečtěte váhy všech replik, vygenerujte náhodné číslo od 0 do součtu všech vah, poté vyberte i-repliku tak, aby součet vah replik od 0 do (i-1) je menší než náhodné číslo a součet vah replik od 0 do i-té je větší než on. Bude tedy možné vybrat jednu repliku a pro výběr další je třeba zopakovat celý postup bez ohledu na vybranou repliku. S takovým algoritmem je složitost výběru jedné repliky O(N), složitost výběru K replik je O(N K) ~ O(N2).

Kvadratická složitost je špatná, ale lze ji zlepšit. K tomu budeme stavět segmentový strom pro součty vah. Získá se strom hloubky lg N, v jehož listech budou repliky vah a ve zbývajících uzlech dílčí součty až do součtu všech vah v kořeni stromu. Dále vygenerujeme náhodné číslo od 0 do součtu všech vah, najdeme i-tou repliku, odstraníme ji ze stromu a zopakujeme postup pro nalezení zbývajících replik. S tímto algoritmem je složitost sestavení stromu O(N), složitost nalezení i-té repliky a její odstranění ze stromu je O(lg N), složitost výběru K replik je O(N + K IgN)~XNUMX(NlgN).

Lineární logaritmická složitost je hezčí než kvadratická složitost, zejména pro velké K.

Je to tento algoritmus implementováno v kódu Knihovny ClusterClient z projektu "Восток". (Tam je strom postaven v O(N lg N), ale to neovlivňuje konečnou složitost algoritmu.)

Úkol 2. Zebra

Bylo nutné navrhnout algoritmus pro efektivní třídění dokumentů v paměti podle libovolného neindexovaného pole:

Váš tým má za úkol vyvinout databázi sdílených dokumentů v paměti. Běžnou pracovní zátěží by bylo vybrat prvních N dokumentů seřazených podle libovolného (neindexovaného) číselného pole z kolekce velikosti M (obvykle N < 100 << M). O něco méně běžnou zátěží by bylo vybrat horní N po přeskočení horních S dokumentů (S ~ N).

Navrhněte algoritmus pro efektivní provádění takových dotazů. Odhadněte jeho výpočetní složitost pomocí velkého O zápisu v průměrném případě a scénáři nejhoršího případu.

Analýza řešení (video)

Od 34:50, pouhých 6 minut:

Analýza řešení (text)

Povrchové řešení: seřaďte všechny dokumenty (např rychlé řazení), pak si vezměte doklady N+S. V tomto případě je složitost třídění v průměru O(M lg M), v horším případě O(M2).

Je zřejmé, že vytřídit všechny M doklady a následně vzít jen malou část je neefektivní. Aby se netřídily všechny dokumenty, je vhodný algoritmus rychlý výběr, který vybere N + S požadovaných dokumentů (lze je třídit podle libovolného algoritmu). V tomto případě se složitost v průměru sníží na O(M), zatímco nejhorší případ zůstane stejný.

Můžete to však udělat ještě efektivněji - použijte algoritmus streamování binární haldy. V tomto případě jsou prvních N+S dokumentů přidány do minimální nebo maximální haldy (v závislosti na směru řazení) a poté je každý další dokument porovnán s kořenem stromu, který obsahuje aktuální minimální nebo maximální dokument, a v případě potřeby se přidá do stromu. V tomto případě je složitost v nejhorším případě, kdy musíte strom neustále přestavovat, O(M lg M), složitost je v průměru O(M), jako u quickselectu.

Streamování haldy se však ukazuje jako efektivnější díky skutečnosti, že v praxi lze většinu dokumentů zahodit bez opětovného sestavení haldy po jediném srovnání s kořenovým prvkem. Takové třídění je implementováno v databázi dokumentů Zebra in-memory vyvinuté a používané v Konturu.

Úkol 3. Záměny států

Bylo nutné navrhnout nejúčinnější algoritmus pro posun stavů:

Váš tým má za úkol vyvinout efektní mechanismus výměny stavu pro distribuovaný cluster N uzlů. Stav i-tého uzlu by měl být přenesen do (i+1)-tého uzlu, stav N-tého uzlu by měl být přenesen do prvního uzlu. Jedinou podporovanou operací je výměna stavu, kdy si dva uzly atomicky vymění své stavy. Je známo, že výměna stavu trvá M milisekund. Každý uzel je schopen se v kterémkoli okamžiku zúčastnit jediné výměny stavu.

Jak dlouho trvá přenos stavů všech uzlů v clusteru?

Analýza řešení (text)

Povrchové řešení: vyměňte stavy prvního a druhého prvku, pak prvního a třetího, pak prvního a čtvrtého a tak dále. Po každé výměně bude stav jednoho prvku v požadované poloze. Musíte udělat O(N) permutace a strávit O(N M) čas.

Lineární čas je dlouhý, takže stavy prvků můžete vyměňovat ve dvojicích: první s druhým, třetí se čtvrtým a tak dále. Po každé výměně stavu bude každý druhý prvek ve správné pozici. Musíte udělat O(lg N) permutace a strávit O(M lg N) čas.

Je však možné řazení ještě zefektivnit – ne v lineárním, ale v konstantním čase. Chcete-li to provést, musíte v prvním kroku vyměnit stav prvního prvku za poslední, druhého za předposlední a tak dále. Stav posledního prvku bude ve správné poloze. A nyní potřebujeme vyměnit stav druhého prvku za poslední, třetího za předposlední a tak dále. Po tomto kole výměn budou stavy všech prvků ve správné pozici. Celkem budou permutace O(2M) ~ O(1).

Takové řešení vůbec nepřekvapí matematika, který si ještě pamatuje, že rotace je složením dvou osových souměrností. Mimochodem, je to triviálně zobecněné pro posun ne o jednu, ale o K < N pozic. (Napište do komentářů jak přesně.)

Měli jste rádi hádanky? Znáte jiná řešení? Podělte se v komentářích.

A zde je několik užitečných odkazů na závěr:

• dozvědět se víc o rozvoj infrastruktury v obrysu
• viz záznamy interní leták s reporty o distribuovaných systémech
• podívejte se na sérii video přednášekNeobvyklé algoritmy pro obyčejné lidi»
• přihlásit se k odběru našich kanál v telegramu

Zdroj: www.habr.com