E etsahetse matsatsing a 'maloa a fetileng Seboka sa Hydra. Bashemane ba tsoang Sehlopha sa JUG.ru ba ile ba memela libui tsa litoro (Leslie Lamport! Cliff Click! Martin Kleppmann!) 'me ba nehelana ka matsatsi a mabeli ho litsamaiso tse ajoang le likhomphutha. Kontur e ne e le e mong oa balekane ba bararo ba kopano. Re ile ra buisana lephepheng, ra bua ka lipolokelo tsa rona tse ajoang, ra bapala bingo, le ho rarolla lipuzzle.

Ena ke poso e nang le tlhahlobo ea mesebetsi sebakeng sa Kontur ho tsoa ho mongoli oa sengoloa sa bona. Ke mang ea neng a le Hydra - lena ke lebaka la hau la ho hopola phihlelo e monate, ea neng a se - monyetla oa ho otlolla boko ba hau kholo O-polelo.

Ho bile ho bile le barupeluoa ba ileng ba qhaqha pampiri e kholo ho e etsa li-slide ho ngola qeto ea bona. Ha ke soasoe - ba fane ka pampiri ena bakeng sa netefatso:

Ho ne ho na le mesebetsi e meraro ka kakaretso:

• mabapi le ho khetha replica ka boima bakeng sa ho leka-lekanya mojaro
• mabapi le ho hlopha liphetho tsa potso khahlanong le polokelong ea mohopolo
• phetisetso ea mmuso tsamaisong e ajoang e nang le ring topology

Mosebetsi oa 1. ClusterClient

Ho ne ho hlokahala ho fana ka maikutlo a algorithm bakeng sa khetho e nepahetseng ea K ho tsoa ho likopi tse boima tsa N tsa sistimi e ajoang:

Sehlopha sa hau se filoe mosebetsi oa ho theha laeborari ea bareki bakeng sa sehlopha se ajoang haholo sa li-N node. Laeborari e tla boloka tlaleho ea lintlha tse fapaneng tse amanang le li-node (mohlala, latency ea tsona, 4xx/5xx likarabo, joalo-joalo) le ho ba abela litekanyo tse phaphametseng W1..WN. E le ho ts'ehetsa leano la ts'ebetso le ts'oanang, laeborari e lokela ho khona ho khetha li-node tsa K tsa N ka tšohanyetso - monyetla oa ho khethoa o lokela ho lekana le boima ba node.

Etsa tlhahiso ea algorithm ho khetha li-node hantle. Hakanya ho rarahana ha eona u sebelisa notation e kholo ea O.

Ke hobane'ng ha tsohle li le ka Senyesemane?

Hobane ka sebopeho sena barupeluoa ba kopano ba ile ba loana le bona le hobane Senyesemane e ne e le puo ea molao ea Hydra. Mesebetsi e ne e shebahala tjena:

Nka pampiri le pentšele, nahana, u se ke ua potlakela ho bula ba senyang hang-hang 🙂

Tlhahlobo ea tharollo (video)

Ho qala ka 5:53, metsotso e 4 feela:

Mona ke kamoo bashanyana ba nang le pampiri e kholo ba hlahisitseng tharollo ea bona:

Tlhahlobo ea tharollo (mongolo)

Tharollo e latelang e ka holim'a metsi: akaretsa boima ba likopi tsohle, hlahisa palo e sa reroang ho tloha ho 0 ho ea ho kakaretso ea litekanyo tsohle, ebe u khetha i-replica e le hore kakaretso ea boima ba replica ho tloha 0 ho ea ho (i-1) e ka tlase ho palo e sa reroang, 'me kakaretso ea boima ba replica ho tloha ho 0 ho isa ho i-th - ho feta eona. Kahoo ho tla khonahala ho khetha replica e le 'ngoe,' me ho khetha e latelang, o hloka ho pheta ts'ebetso eohle ntle le ho nahana ka replica e khethiloeng. Ka algorithm e joalo, ho rarahana ha ho khetha replica e le 'ngoe ke O(N), ho rarahana ha ho khetha K replicas ke O(N K) ~ O(N2).

Quadratic complexity e mpe, empa e ka ntlafatsoa. Ho etsa sena, re tla haha sefate sa karolo bakeng sa boima ba 'mele. Sefate sa botebo ba lg N se tla fumanoa, makhasi ao ho tla ba le litekanyo tsa replica, le li-node tse setseng - lipalo tse sa fellang, ho fihlela kakaretso ea litekanyo tsohle tse motso oa sefate. Ka mor'a moo, re hlahisa palo e sa reroang ho tloha ho 0 ho ea ho kakaretso ea litekanyo tsohle, re fumana setšoantšo sa i-th, re se tlose sefateng, 'me u phete mokhoa oa ho fumana likopi tse setseng. Ka algorithm ena, ho rarahana ha ho aha sefate ke O(N), ho rarahana ha ho fumana i-th replica le ho e tlosa sefateng ke O(lg N), ho rarahana ha ho khetha K replicas ke O(N + K). lg N) ~ O(N lg N) .

Ho rarahana ha linear-log ho monate ho feta ho rarahana ha quadratic, haholo bakeng sa K.

Ke algorithm ena kenngwa tshebetsong ka khoutu Lilaebrari tsa ClusterClient tse tsoang morerong "Bochabela". (Moo, sefate se hahiloe ka O(N lg N), empa sena ha se ame ho rarahana ha ho qetela ha algorithm.)

Mosebetsi oa 2. Zebra

Ho ne ho hlokahala ho fana ka tlhahiso ea algorithm bakeng sa ho hlophisoa hantle ha litokomane mohopolong ka sebaka se sa reroang se sa keneng:

Sehlopha sa hau se filoe mosebetsi oa ho theha polokelo ea polokelo ea litokomane tsa memori tse sharded. Mosebetsi o tloaelehileng e ka ba ho khetha litokomane tse holimo tsa N tse hlophisitsoeng ka palo e sa reroang (e sa ngolisoeng) ho tloha pokellong ea boholo ba M (hangata N <100 << M). Mosebetsi o fokolang hanyane e ka ba ho khetha N e kaholimo kamora ho tlola litokomane tse holimo tsa S (S ~ N).

Etsa tlhahiso ea algorithm ho phethahatsa lipotso tse joalo ka katleho. Hakanya ho rarahana ha eona ka ho sebelisa lintlha tse kholo tsa O maemong a tloaelehileng le maemo a mabe ka ho fetesisa.

Tlhahlobo ea tharollo (video)

Ho qala ka 34:50, metsotso e 6 feela:

Tlhahlobo ea tharollo (mongolo)

Tharollo ea sefahleho: hlophisa litokomane tsohle (mohlala ka leboea), ebe o nka litokomane tsa N+S. Tabeng ena, ho rarahana ha ho hlopha ke ka karolelano O(M lg M), ka ho fetisisa O(M2).

Ho hlakile hore ho hlopha litokomane tsa M kaofela ebe ho nka karolo e nyane feela ho sa sebetse hantle. E le hore u se ke ua hlophisa litokomane tsohle, algorithm e loketse khethang kapele, e tla khetha N + S ea litokomane tse lakatsehang (li ka hlophisoa ka algorithm efe kapa efe). Tabeng ena, ho rarahana ho tla fokotseha ho ea ho O (M) ka karolelano, ha boemo bo bobe ka ho fetisisa bo tla lula bo tšoana.

Leha ho le joalo, u ka e etsa ka katleho le ho feta - sebelisa algorithm binary qubu phallela. Tabeng ena, litokomane tsa pele tsa N + S li kenyelletsoa ho min- kapa max-heap (ho itšetlehile ka tataiso ea mofuta), ebe tokomane e 'ngoe le e' ngoe e latelang e bapisoa le motso oa sefate, o nang le bonyane kapa tokomane e phahameng ea hona joale, mme e ekeletswa sefateng ha ho hlokahala. Tabeng ena, ho rarahana ha boemo bo bobe ka ho fetisisa, ha u tlameha ho lula u tsosolosa sefate, ke O (M lg M), ho rarahana ka karolelano ke O (M), joalo ka ka khetho e potlakileng.

Leha ho le joalo, ho phalla ha qubu ho bonahala ho sebetsa hantle ka lebaka la hore ha e le hantle litokomane tse ngata li ka lahloa ntle le ho tsosolosa qubu ka mor'a papiso e le 'ngoe le motsoako oa eona. Ho hlopha ho joalo ho kentsoe tšebetsong polokelong ea litokomane tsa mohopolo oa Zebra tse ntlafalitsoeng le ho sebelisoa Kontur.

Mosebetsi oa 3. Liphetoho tsa naha

Ho ne ho hlokahala ho fana ka tlhahiso ea algorithm e sebetsang ka ho fetisisa bakeng sa linaha tse fetohang:

Sehlopha sa hau se filoe mosebetsi oa ho theha mokhoa o majabajaba oa phapanyetsano ea mmuso bakeng sa sehlopha se ajoang sa li-N node. Boemo ba node ea i-th bo lokela ho fetisetsoa sebakeng sa (i + 1) -th, boemo ba N-th node bo lokela ho fetisetsoa ho node ea pele. Ts'ebetso e ts'ehelitsoeng feela ke phapanyetsano ea mmuso ha li-node tse peli li fapanyetsana linaha tsa tsona ka atomo. Hoa tsebahala hore phetoho ea mmuso e nka M milliseconds. Node e 'ngoe le e' ngoe e khona ho kenya letsoho phetohong e le 'ngoe ea naha ka nako efe kapa efe.

Ho nka nako e kae ho fetisetsa linaha tsa li-node kaofela sehlopheng?

Tlhahlobo ea tharollo (mongolo)

Tharollo ea holim'a sefahleho: fapanyetsana maemo a karolo ea pele le ea bobeli, ebe ea pele le ea boraro, ebe ea pele le ea bone, joalo-joalo. Ka mor'a phapanyetsano e 'ngoe le e' ngoe, boemo ba ntho e le 'ngoe bo tla ba boemong bo lakatsehang. U tlameha ho etsa litumello tsa O(N) mme u qete nako ea O(N M).

Nako ea linear e telele, kahoo o ka fapanyetsana maemo a likarolo ka bobeli: ea pele le ea bobeli, ea boraro le ea bone, joalo-joalo. Ka mor'a phapanyetsano e 'ngoe le e' ngoe ea mmuso, karolo e 'ngoe le e' ngoe ea bobeli e tla ba boemong bo nepahetseng. U tlameha ho etsa litumello tsa O(lg N) mme u qete nako ea O(M lg N).

Leha ho le joalo, hoa khoneha ho etsa hore phetoho e sebetse le ho feta - eseng ka linear, empa ka nako e sa fetoheng. Ho etsa sena, mohato oa pele, o hloka ho fapanyetsana boemo ba ntho ea pele le ea ho qetela, ea bobeli le ea penultimate, joalo-joalo. Boemo ba elemente ea ho qetela bo tla ba boemong bo nepahetseng. 'Me joale re hloka ho fapanyetsana boemo ba ntho ea bobeli le ea ho qetela, ea boraro le ea penultimate, joalo-joalo. Ka mor'a potoloho ena ea phapanyetsano, linaha tsa likarolo tsohle li tla ba boemong bo nepahetseng. Ho tla ba le litumello tsa O(2M) ~ O(1) ka kakaretso.

Tharollo e joalo e ke ke ea makatsa setsebi sa lipalo se ntseng se hopola hore ho potoloha ke motsoako oa li-axial symmetries tse peli. Ka tsela, ha e tloaelehe ka kakaretso bakeng sa phetoho eseng ka e le 'ngoe, empa ka maemo a K <N. (Ngola litlhalosong hore na hantle hakae.)

A na u ratile lipuzzle? Na u tseba litharollo tse ling? Arolelana maikutlong.

'Me mona ke lihokelo tse ling tsa bohlokoa qetellong:

• ithute haholoanyane ka ntshetsopele ya metheo ka contour
• sheba litlaleho tsa ka hare sefofane se nang le litlaleho mabapi le litsamaiso tse ajoang
• shebella letoto la lipuo tsa videoLi-algorithms tse sa tloaelehang bakeng sa batho ba tloaelehileng»
• ngolisa ho rona mocha oa Telegram

Source: www.habr.com