Stalo sa to pred pár dňami . Chalani zo skupiny JUG.ru si pozvali rečníkov snov (Leslie Lamport! Cliff Click! Martin Kleppmann!) a dva dni venovali distribuovaným systémom a počítačom. Kontur bol jedným z troch partnerov konferencie. Rozprávali sme sa v stánku, hovorili o našom distribuovanom úložisku, hrali bingo a riešili hádanky.
Toto je príspevok s rozborom úloh v stánku Kontur od autora ich textu. Kto bol na Hydre - to je váš dôvod zapamätať si príjemný zážitok, kto nebol - šanca pretiahnuť si mozog veľký O-notácia.
Boli dokonca účastníci, ktorí rozložili flipchart na diapozitívy, aby zapísali svoje rozhodnutie. Nerobím si srandu - tento stoh papiera odovzdali na overenie:
Úlohy boli celkovo tri:
- o výbere replík podľa váh na vyváženie záťaže
- o triedení výsledkov dotazov podľa databázy v pamäti
- o prenose stavu v distribuovanom systéme s kruhovou topológiou
Úloha 1. ClusterClient
Bolo potrebné navrhnúť algoritmus na efektívny výber K z N vážených replík distribuovaného systému:
Váš tím má za úlohu vyvinúť klientsku knižnicu pre masívne distribuovaný klaster N uzlov. Knižnica by sledovala rôzne metadáta spojené s uzlami (napr. ich latencie, miery odozvy 4xx/5xx atď.) a priraďovala by im váhy s pohyblivou rádovou čiarkou W1..WN. Aby sa podporila stratégia súbežného vykonávania, knižnica by mala byť schopná vybrať K z N uzlov náhodne – šanca na výber by mala byť úmerná hmotnosti uzla.
Navrhnite algoritmus na efektívny výber uzlov. Odhadnite jeho výpočtovú náročnosť pomocou veľkého zápisu O.
Prečo je všetko v angličtine?
Pretože v tejto podobe s nimi účastníci konferencie bojovali a pretože angličtina bola oficiálnym jazykom Hydry. Úlohy vyzerali takto:
Vezmite si papier a ceruzku, premýšľajte, neponáhľajte sa hneď otvárať spoilery 🙂
Analýza riešenia (video)
Začína sa o 5:53, iba 4 minúty:
A takto chlapci s flipchartom navrhli svoje riešenie:
Analýza riešenia (text)
Nasledujúce riešenie leží na povrchu: spočítajte váhy všetkých replík, vygenerujte náhodné číslo od 0 do súčtu všetkých váh, potom vyberte i-repliku tak, že súčet váh replík od 0 do (i-1) je menšie ako náhodné číslo a súčet váh kópií od 0 do i-tej je väčší ako on. Takže bude možné vybrať jednu repliku a pre výber ďalšej je potrebné zopakovať celý postup bez zohľadnenia vybranej repliky. S takýmto algoritmom je zložitosť výberu jednej repliky O(N), zložitosť výberu K replík je O(N K) ~ O(N2).
Kvadratická zložitosť je zlá, ale dá sa zlepšiť. K tomu budeme stavať pre súčty váh. Získa sa strom hĺbky lg N, v listoch ktorého budú repliky váh a vo zvyšných uzloch čiastočné súčty až do súčtu všetkých váh v koreni stromu. Ďalej vygenerujeme náhodné číslo od 0 do súčtu všetkých váh, nájdeme i-tú repliku, odstránime ju zo stromu a zopakujeme postup, aby sme našli zvyšné repliky. S týmto algoritmom je zložitosť budovania stromu O(N), zložitosť nájdenia i-tej repliky a jej odstránenia zo stromu je O(lg N), zložitosť výberu K replík je O(N + K IgN)~XNUMX(NlgN).
Lineárna logaritmická zložitosť je lepšia ako kvadratická zložitosť, najmä pre veľké K.
Je to tento algoritmus Knižnice ClusterClient z projektu "". (Tam je strom postavený v O(N lg N), ale to nemá vplyv na konečnú zložitosť algoritmu.)
Úloha 2. Zebra
Bolo potrebné navrhnúť algoritmus na efektívne triedenie dokumentov v pamäti podľa ľubovoľného neindexovaného poľa:
Váš tím je poverený vývojom databázy dokumentov v pamäti. Bežnou úlohou by bolo vybrať prvých N dokumentov zoradených podľa ľubovoľného (neindexovaného) číselného poľa z kolekcie veľkosti M (zvyčajne N < 100 << M). O niečo menej bežnou záťažou by bolo vybrať horné N po preskočení horných S dokumentov (S ~ N).
Navrhnite algoritmus na efektívne vykonávanie takýchto dotazov. Odhadnite jeho výpočtovú zložitosť pomocou notácie veľkého O v priemernom prípade a scenári najhoršieho prípadu.
Analýza riešenia (video)
Od 34:50, iba 6 minút:
Analýza riešenia (text)
Povrchové riešenie: zoraďte všetky dokumenty (napr ), potom si vezmite doklady N+S. V tomto prípade je zložitosť triedenia v priemere O(M lg M), prinajhoršom O(M2).
Je zrejmé, že vytriediť všetky M doklady a následne vziať len malú časť je neefektívne. Aby sa netriedili všetky dokumenty, je vhodný algoritmus , ktorý vyberie N + S požadovaných dokumentov (možno ich zoradiť podľa ľubovoľného algoritmu). V tomto prípade sa zložitosť v priemere zníži na O(M), pričom najhorší prípad zostane rovnaký.
Môžete to však urobiť ešte efektívnejšie - použite algoritmus . V tomto prípade sa prvých N+S dokumentov pridá na minimálnu alebo maximálnu haldu (v závislosti od smeru triedenia) a potom sa každý ďalší dokument porovná s koreňom stromu, ktorý obsahuje aktuálny minimálny alebo maximálny dokument, a v prípade potreby sa pridá do stromu. V tomto prípade je zložitosť v najhoršom prípade, keď musíte strom neustále prestavovať, O(M lg M), zložitosť je v priemere O(M), ako pri quickselect.
Streamovanie haldy sa však ukazuje ako efektívnejšie vďaka skutočnosti, že v praxi možno väčšinu dokumentov zahodiť bez toho, aby sa hala znovu vytvorila po jedinom porovnaní s jej koreňovým prvkom. Takéto triedenie je implementované v databáze dokumentov Zebra in-memory vyvinutej a používanej v Kontur.
Úloha 3. Zámeny štátov
Bolo potrebné navrhnúť najefektívnejší algoritmus na posun stavov:
Váš tím má za úlohu vyvinúť efektný mechanizmus výmeny stavu pre distribuovaný klaster N uzlov. Stav i-tého uzla by sa mal preniesť do (i+1)-teho uzla, stav N-tého uzla by sa mal preniesť do prvého uzla. Jedinou podporovanou operáciou je výmena stavu, keď si dva uzly atómovo vymenia svoje stavy. Je známe, že výmena stavu trvá M milisekúnd. Každý uzol sa môže kedykoľvek zúčastniť na výmene jedného stavu.
Ako dlho trvá prenos stavov všetkých uzlov v klastri?
Analýza riešenia (text)
Povrchové riešenie: vymeňte stavy prvého a druhého prvku, potom prvého a tretieho, potom prvého a štvrtého atď. Po každej výmene bude stav jedného prvku v požadovanej polohe. Musíte urobiť O(N) permutácie a stráviť O(N M) čas.
Lineárny čas je dlhý, takže stavy prvkov môžete vymieňať v pároch: prvý s druhým, tretí so štvrtým atď. Po každej výmene stavu bude každý druhý prvok v správnej polohe. Musíte urobiť O(lg N) permutácie a stráviť O(M lg N) čas.
Posun je však možné ešte zefektívniť – nie v lineárnom, ale v konštantnom čase. Aby ste to dosiahli, musíte v prvom kroku vymeniť stav prvého prvku za posledný, druhého za predposledný atď. Stav posledného prvku bude v správnej polohe. A teraz potrebujeme vymeniť stav druhého prvku za posledný, tretieho za predposledný atď. Po tomto kole výmen budú stavy všetkých prvkov v správnej pozícii. Celkovo budú permutácie O(2M) ~ O(1).
Takéto riešenie vôbec neprekvapí matematika, ktorý si ešte pamätá, že rotácia je zložením dvoch osových súmerností. Mimochodom, je to triviálne zovšeobecnené na posun nie o jednu, ale o K < N pozícií. (Napíšte do komentárov ako presne.)
Mali ste radi hádanky? Poznáte iné riešenia? Podeľte sa v komentároch.
A tu je niekoľko užitočných odkazov na záver:
- naučiť sa viac o v obryse
- pozri interné záznamy o distribuovaných systémoch
- pozrite si sériu videoprednášok»
- prihláste sa na odber našich
Zdroj: hab.com