Zvakaitika mazuva mashoma apfuura Hydra Musangano. Vakomana vanobva kuJUG.ru Group vakakoka vatauri vezviroto (Leslie Lamport! Cliff Click! Martin Kleppmann!) uye vakapa mazuva maviri kugovera masisitimu uye komputa. Kontur aive mumwe wevatatu vadyidzani vemusangano. Taitaura paimba yacho, taitaura nezvenzvimbo dzedu dzokuchengetera dzakanga dzaparadzirwa, tairidza bhingo, uye taigadzirisa mapuzzle.

Ichi chinyorwa chine ongororo yemabasa panzvimbo yeKontur kubva kumunyori wechinyorwa chavo. Ndiani akanga ari paHydra - ichi ndicho chikonzero chako chekuyeuka chiitiko chinofadza, uyo akanga asiri - mukana wekutambanudza uropi hwako. hombe O-notation.

Paitove nevatori vechikamu vakabvisa pafiripi chati kuita masiraidhi kuti vanyore sarudzo yavo. Ini handisi kuita jee - vakapa iyi stack yepepa kuti ionekwe:

Paiva nemabasa matatu pamwe chete:

• nezve kusarudza replicas nezviyereso zvekuenzanisa mitoro
• nezve kurongedza zvawanikwa uchipikisa mu-memory dhatabhesi
• pamusoro pekutamisa nyika mune yakagoverwa system ine ring topology

Basa 1. ClusterClient

Zvaive zvakafanira kupa algorithm yekusarudzwa kwakanaka kweK kubva kuN inorema replicas yeyakagoverwa system:

Chikwata chako chine basa rekugadzira raibhurari yemutengi kune yakakura yakagovaniswa cluster yeN node. Raibhurari yaizochengeta mametadata akasiyana-siyana ane hukama nemanodhi (semuenzaniso, kunonoka kwadzo, 4xx/5xx mhinduro dzemiyero, nezvimwewo) uye kugovera zviremu zvinoyangarara W1..WN kwavari. Kuti utsigire zano rekuuraya rakafanana, raibhurari inofanirwa kukwanisa kusarudza K yeN node zvisina tsarukano-mukana wekusarudzwa unofanirwa kuenzana nehuremu hwenodhi.

Kurudzira algorithm yekusarudza node zvakanaka. Kufungidzira kuomarara kwayo uchishandisa hombe O notation.

Sei zvese zviri muChirungu?

Nekuti mune iyi fomu vatori vechikamu vakarwa navo uye nekuti Chirungu chaive mutauro wepamutemo weHydra. Mabasa acho aiita seizvi:

Tora pepa nepenzura, funga, usamhanye kuvhura vaparadzi ipapo 🙂

Kuongororwa kwemhinduro (vhidhiyo)

Kutanga na5:53, maminetsi mana chete:

Uye heino nzira iyo vakomana vane flipchart vakaisa mhinduro yavo:

Ongororo yemhinduro (zvinyorwa)

Mhinduro inotevera iri pamusoro: unganidza huremu hwese replicas, gadzira nhamba isina kurongeka kubva pa0 kusvika pahuwandu hwehuremu hwese, wobva wasarudza i-replica zvekuti huwandu hwehuremu hwereplica kubva pa0 kusvika (i-1) isingasviki nhamba isina kurongeka, uye huwandu hwezviremera zve replica kubva pa0 kusvika ku-i-th - kupfuura iyo. Saka zvinokwanisika kusarudza imwe replica, uye kusarudza inotevera, unofanirwa kudzokorora maitiro ese usingatarise yakasarudzwa replica. Nealgorithm yakadai, kuoma kwekusarudza imwe replica ndeye O(N), kuoma kwekusarudza K replicas ndeye O(N K) ~ O(N2).

Quadratic yakaoma, asi inogona kuvandudzwa. Kuti tiite izvi, tichavaka chikamu muti nokuda kwezviyero. Muti wakadzika lg N uchawanikwa, mumashizha ayo pachava nezviyereso zvekufananidza, uye mumanodhi akasara - zvikamu zvishoma, kusvika kuhuwandu hwehuremu hwose pamudzi wemuti. Tevere, isu tinogadzira nhamba isina kurongeka kubva pa0 kusvika kuhuwandu hwehuremu hwese, tsvaga i-th replica, ibvise pamuti, uye dzokorora maitiro ekutsvaga asara replicas. Neiyi algorithm, kuoma kwekuvaka muti ndeye O(N), kuoma kwekutsvaga i-th replica uye kuibvisa kubva pamuti ndeye O(lg N), kuoma kwekusarudza K replicas ndeye O(N + K). lg N) ~ O(N lg N) .

Linear-log kuomarara kwakanaka pane quadratic kuomarara, kunyanya kune yakakura K.

Iyi ndiyo algorithm yakaitwa mukodhi ClusterClient maraibhurari kubva kupurojekiti "East". (Iko, muti wakavakwa muO (N lg N), asi izvi hazvikanganisi kuoma kwekupedzisira kwegorgorithm.)

Basa 2. Mbizi

Zvaive zvakafanira kupenengura algorithm yekurongeka kwakanaka kwemagwaro mundangariro nendima isina kuverengerwa isina indexed:

Chikwata chako chine basa rekugadzira yakaomeswa in-memory gwaro dhatabhesi. Basa rakajairwa rinenge riri rekusarudza magwaro epamusoro eN akarongwa nendima yenhamba (isina-indexed) kubva muunganidzwa wehukuru M (kazhinji N <100 << M). Basa rakanyanya kushomeka kungava kusarudza kumusoro N mushure mekusvetuka magwaro epamusoro S (S ~ N).

Rongedza algorithm yekuita mibvunzo yakadaro nemazvo. Kufungidzira kuomarara kwayo uchishandisa hombe O notation mune avhareji kesi uye yakaipisisa mamiriro ezvinhu.

Kuongororwa kwemhinduro (vhidhiyo)

Kutanga na34:50, maminetsi matanhatu chete:

Ongororo yemhinduro (zvinyorwa)

Surface solution: rongedza zvese zvinyorwa (semuenzaniso ne suka), wobva watora zvinyorwa zveN+S. Muchiitiko ichi, kuoma kwekugadzirisa kuri paavhareji O(M lg M), pakaipisisa O(M2).

Zviripachena kuti kuronga magwaro ese M wozotora chikamu chidiki chawo hakuna zvakunobatsira. Kuti urege kuronga magwaro ese, algorithm yakakodzera kukurumidza kusarudza, iyo ichasarudza N + S yemagwaro anodiwa (anogona kurongwa nechero algorithm). Muchiitiko ichi, kuoma kunoderera kusvika kuO (M) paavhareji, asi iyo yakaipisisa icharamba yakafanana.

Nekudaro, iwe unogona kuzviita zvakatonyanya - shandisa iyo algorithm binary murwi kuyerera. Muchiitiko ichi, magwaro ekutanga eN + S anowedzerwa kune min- kana max-heap (zvichienderana negwara rei), uyezve rimwe nerimwe rinotevera rinofananidzwa nemudzi wemuti, uyo une hushoma huripo kana huwandu hwegwaro, uye inowedzerwa pamuti kana zvichidikanwa. . Muchiitiko ichi, kuoma mumamiriro ezvinhu akaipisisa, kana iwe uchifanira kugara uchivakazve muti, ndeye O (M lg M), iyo yakaoma paavhareji ndeye O (M), sekunge nekukurumidzaselect.

Nekudaro, kutenderera kwemurwi kunobva kwawedzera kushanda nekuda kwekuti mukuita mazhinji ezvinyorwa anogona kuraswa pasina kuvakazve murwi mushure mekuenzanisa kamwe chete nemudzi wayo. Kurongeka kwakadaro kunoitwa muZebra mu-memory gwaro dhatabhesi rakagadzirwa uye rinoshandiswa muKontur.

Basa 3. State swaps

Zvaive zvakafanira kupa algorithm inoshanda kwazvo yekuchinja nyika:

Chikwata chako chakapihwa basa rekugadzira yakasarudzika mamiriro ekutsinhana maitiro eboka rakagoverwa reN node. Iyo i-th node's state inofanirwa kuendeswa kune (i+1) -th node, iyo N-th node mamiriro anofanira kuendeswa kune yekutanga node. Kushanda kunotsigirwa chete ndiko kuchinjisa nyika kana nodhi mbiri dzichichinjana nyika dzadzo maatomu. Zvinozivikanwa kuti shanduko yenyika inotora M milliseconds. Yese node inokwanisa kutora chikamu mune imwe nyika shanduko panguva ipi zvayo.

Zvinotora nguva yakareba sei kuendesa nyika dzese node musumbu?

Ongororo yemhinduro (zvinyorwa)

Surface solution: chinjanai nyika yekutanga neyechipiri element, ipapo yekutanga neyechitatu, ipapo yekutanga neyechina, zvichingodaro. Mushure mekuchinjana kwega kwega, mamiriro echimwe chinhu achange ari munzvimbo inodiwa. Iwe unofanirwa kuita O(N) mvumo uye kushandisa O(N M) nguva.

Linear nguva yakareba, saka iwe unogona kuchinjanisa nyika dzezvinhu muzviviri: yekutanga neyechipiri, yechitatu neyechina, zvichingodaro. Mushure mekuchinjana kwega kwega kwenyika, chechipiri chese chinenge chiri munzvimbo chaiyo. Iwe unofanirwa kugadzira O(lg N) mvumo uye kushandisa O(M lg N) nguva.

Zvisinei, zvinokwanisika kuita kuti kuchinja kuwedzere kushanda - kwete mumutsara, asi munguva inogara. Kuti uite izvi, padanho rekutanga, unofanirwa kuchinjana mamiriro echinhu chekutanga neyokupedzisira, yechipiri neyekupedzisira, zvichingodaro. Mamiriro echikamu chekupedzisira achange ari panzvimbo chaiyo. Uye zvino isu tinoda kuchinjana mamiriro echikamu chechipiri neicho chekupedzisira, chechitatu chine pekupedzisira, zvichingodaro. Mushure mekutenderera uku kwekuchinjana, nyika dzezvinhu zvese dzichange dziri munzvimbo chaiyo. Pachave neO(2M) ~ O(1) mvumo yese.

Mhinduro yakadaro haizomboshamisi nyanzvi yemasvomhu ichiri kuyeuka kuti kutenderera kuumbwa kweaxial symmetries mbiri. Nenzira, iyo inofananidzwa zvishoma kune shanduko kwete neimwe, asi neK <N zvinzvimbo. (Nyora mumashoko kuti sei chaizvo.)

Wakada puzzles here? Unoziva dzimwe mhinduro here? Govera mumhinduro.

Uye heano mamwe anobatsira links pakupedzisira:

• dzidza zvakawanda nezve kuvandudzwa kwezvivakwa mu contour
• ona zvinyorwa zvemukati flyer ine mishumo pamusoro pezvirongwa zvakagoverwa
• tarisa nhevedzano yehurukuro dzevhidhiyoZvisina kujairika algorithms kune vanhuwo zvavo»
• nyoresa kune yedu chiteshi muTeregiramu

Source: www.habr.com