Néhány napja történt . A JUG.ru Group srácai álomhangszórókat hívtak meg (Leslie Lamport! Cliff Click! Martin Kleppmann!), és két napot az elosztott rendszereknek és a számítástechnikának szenteltek. Kontur egyike volt a konferencia három partnerének. Beszélgettünk a standnál, beszélgettünk az elosztott tárolóinkról, bingóztunk és rejtvényeket fejtettünk.
Ez a bejegyzés a Kontur standján lévő feladatok elemzésével a szöveg szerzőjétől. Ki volt a Hidrán - ez az oka annak, hogy emlékezzen a kellemes élményre, aki nem - az esélye, hogy megfeszítse az agyát nagy O-jelölés.
Még olyan résztvevők is voltak, akik a flipchart-táblát diákra szedték, hogy leírják döntésüket. Nem viccelek – ezt a papírköteget adták át ellenőrzésre:
Összesen három feladat volt:
- a replikák súly szerinti kiválasztásáról a terheléselosztáshoz
- a lekérdezések eredményeinek egy memórián belüli adatbázishoz való rendezéséről
- állapotátvitelről gyűrűtopológiájú elosztott rendszerben
Feladat 1. ClusterClient
Szükséges volt egy algoritmust javasolni egy elosztott rendszer N súlyozott replikájából K hatékony kiválasztására:
Csapata feladata egy ügyfélkönyvtár fejlesztése egy N csomópontból álló, masszívan elosztott fürt számára. A könyvtár nyomon követné a csomópontokhoz kapcsolódó különféle metaadatokat (pl. késésük, 4xx/5xx válaszarány stb.), és W1...WN lebegőpontos súlyokat rendelne hozzájuk. Az egyidejű végrehajtási stratégia támogatása érdekében a könyvtárnak képesnek kell lennie N csomópontból véletlenszerűen kiválasztani K csomópontot – a kiválasztási esélynek arányosnak kell lennie a csomópont súlyával.
Javasoljon egy algoritmust a csomópontok hatékony kiválasztásához. Becsülje meg számítási összetettségét nagy O jelöléssel.
Miért van minden angolul?
Mert ebben a formában harcoltak velük a konferencia résztvevői és mert a Hydra hivatalos nyelve az angol volt. A feladatok így néztek ki:
Fogj papírt és ceruzát, gondolkodj, ne rohanj azonnal spoilereket nyitogatni 🙂
A megoldás elemzése (videó)
5:53-kor kezdődik, mindössze 4 perc:
A flipchart-os srácok pedig így állították elő a megoldást:
A megoldás elemzése (szöveg)
A felületen a következő megoldás található: összegezze az összes replika súlyát, generál egy véletlen számot 0-tól az összes súly összegéig, majd válasszon egy i-replikát úgy, hogy a replika súlyának összege 0-tól (i-1)-ig terjedjen. kisebb, mint egy véletlen szám, és a replika súlyainak összege 0-tól i-edikig - nagyobb annál. Így lehetséges lesz egy replika kiválasztása, a következő kiválasztásához pedig meg kell ismételnie a teljes eljárást a kiválasztott replika figyelembevétele nélkül. Egy ilyen algoritmussal egy replika kiválasztásának bonyolultsága O(N), K replika kiválasztásának pedig O(N K) ~ O(N2).
A kvadratikus összetettség rossz, de javítható. Ennek érdekében építkezünk súlyok összegére. Egy lg N mélységű fát kapunk, amelynek leveleiben replikasúlyok, a többi csomópontban pedig részösszegek lesznek, a fa gyökerénél lévő összes súly összegéig. Ezután generálunk egy véletlen számot 0-tól az összes súly összegéig, megkeressük az i-edik replikát, eltávolítjuk a fából, és megismételjük az eljárást a fennmaradó replikák megtalálásához. Ezzel az algoritmussal egy fa felépítésének bonyolultsága O(N), az i-edik replika megtalálásának és a fából való eltávolításának bonyolultsága O(lg N), K replika kiválasztásának bonyolultsága O(N + K lg N) ~ O(N lg N) .
A lineáris log komplexitás szebb, mint a kvadratikus komplexitás, különösen nagy K esetén.
Ez az algoritmus ClusterClient könyvtárak a projektből "". (Ott a fa O(N lg N-be van építve), de ez nem befolyásolja az algoritmus végső összetettségét.)
Feladat 2. Zebra
Szükséges volt egy algoritmust javasolni a memóriában lévő dokumentumok tetszőleges nem indexelt mező alapján történő hatékony rendezésére:
Csapata feladata egy darabolt, memórián belüli dokumentumadatbázis fejlesztése. Gyakori munkateher az lenne, ha kiválasztunk egy tetszőleges (nem indexelt) numerikus mező szerint rendezett N legjobb dokumentumot egy M méretű gyűjteményből (általában N < 100 << M). Valamivel kevésbé gyakori munkateher az lenne, ha a felső N-t választja ki, miután kihagyta a legjobb S dokumentumokat (S ~ N).
Javasoljon egy algoritmust az ilyen lekérdezések hatékony végrehajtásához. Becsülje meg számítási bonyolultságát nagy O jelöléssel átlagos esetben és a legrosszabb forgatókönyvekben.
A megoldás elemzése (videó)
34:50-kor kezdődik, csak 6 perc:
A megoldás elemzése (szöveg)
Felületi megoldás: rendezze az összes dokumentumot (pl ), majd vegyen N+S dokumentumokat. Ebben az esetben a válogatás bonyolultsága átlagosan O(M lg M), legrosszabb esetben O(M2).
Nyilvánvaló, hogy az összes M dokumentum rendezése, majd csak egy kis részének elvétele nem hatékony. Annak érdekében, hogy ne rendezzen minden dokumentumot, megfelelő egy algoritmus , amely kiválasztja N + S a kívánt dokumentumokat (bármilyen algoritmussal rendezhetők). Ebben az esetben a komplexitás átlagosan O(M)-re csökken, míg a legrosszabb eset változatlan marad.
Azonban ezt még hatékonyabban is megteheti – használja az algoritmust . Ebben az esetben az első N+S dokumentumokat a rendszer a min- vagy max-heap-hez adja (a rendezési iránytól függően), majd minden következő dokumentumot összehasonlít a fa gyökérével, amely az aktuális minimális vagy maximum dokumentumot tartalmazza, és szükség esetén hozzáadják a fához. Ebben az esetben a bonyolultság a legrosszabb esetben, amikor folyamatosan újra kell építeni a fát, O(M lg M), a bonyolultság átlagosan O(M), mint a Quickselectnél.
A halom streaming azonban hatékonyabbnak bizonyul, mivel a gyakorlatban a legtöbb dokumentum eldobható anélkül, hogy a kupacot újra kellene építeni, miután egyetlen összehasonlítást végeztünk a gyökérelemével. Az ilyen rendezést a Konturban fejlesztett és használt Zebra in-memory dokumentumadatbázis valósítja meg.
3. feladat Államcserék
Szükséges volt a leghatékonyabb algoritmus javaslata az állapotok eltolására:
Csapata feladata egy képzeletbeli állapotcsere-mechanizmus kifejlesztése N csomópontból álló elosztott fürt számára. Az i-edik csomópont állapotát az (i+1)-edik csomópontra, az N-edik csomópont állapotát az első csomópontra kell átvinni. Az egyetlen támogatott művelet az állapotcsere, amikor két csomópont atomszerűen cseréli fel állapotát. Ismeretes, hogy az állapotcsere M milliszekundumot vesz igénybe. Minden csomópont egy adott pillanatban egyetlen állapotcserében tud részt venni.
Mennyi ideig tart egy klaszter összes csomópontjának állapotának átvitele?
A megoldás elemzése (szöveg)
Felületi megoldás: felcseréljük az első és a második elem állapotát, majd az első és a harmadik, majd az első és a negyedik, és így tovább. Minden csere után egy elem állapota a kívánt pozícióba kerül. O(N) permutációt kell készítened, és O(N M) időt kell töltened.
A lineáris idő hosszú, így az elemek állapotát páronként felcserélheti: az elsőt a másodikkal, a harmadikat a negyedikkel stb. Minden állapotcsere után minden második elem a megfelelő pozícióba kerül. O(lg N) permutációt kell készíteni, és O(M lg N) időt kell eltöltenie.
A váltást azonban még hatékonyabbá lehet tenni - nem lineárisan, hanem állandó időben. Ehhez az első lépésben fel kell cserélni az első elem állapotát az utolsóval, a másodikat az utolsó előttivel, és így tovább. Az utolsó elem állapota a megfelelő pozícióban lesz. És most fel kell cserélnünk a második elem állapotát az utolsóval, a harmadikat az utolsó előttivel, és így tovább. A cserék ezen köre után az összes elem állapota a megfelelő pozícióba kerül. Összesen O(2M) ~ O(1) permutáció lesz.
Egy ilyen megoldás egyáltalán nem fogja meglepni azt a matematikust, aki még emlékszik arra, hogy a forgatás két tengelyes szimmetria összetétele. Mellesleg triviálisan általánosított egy eltolódásra nem egy, hanem K < N pozícióval. (Kommentben írd meg, hogy pontosan hogyan.)
Szeretted a rejtvényeket? Tudsz más megoldást? Oszd meg a megjegyzésekben.
És itt van néhány hasznos link a végére:
- tudj meg többet kontúrban
- lásd a belső feljegyzéseket az elosztott rendszerekről
- nézze meg a videó előadások sorozatát»
- iratkozzon fel a mi
Forrás: will.com