Emere ụbọchị ole na ole gara aga . Ụmụ okorobịa si na JUG.ru Group kpọrọ ndị na-ekwu nrọ nrọ (Leslie Lamport! Cliff Click! Martin Kleppmann!) Ma tinye ụbọchị abụọ na-ekesa usoro na mgbakọ. Kontur bụ otu n'ime ndị mmekọ atọ nke ọgbakọ ahụ. Anyị kwurịtara okwu n'ụlọ ntu ahụ, kparịta banyere ebe a na-edebe ihe ndị anyị kesara, na-akpọ bingo, ma dozie ihe mgbagwoju anya.
Nke a bụ ọkwa nwere nyocha nke ọrụ na Kontur site n'aka onye dere ederede ha. Onye nọ na Hydra - nke a bụ ihe mere ị ga-eji cheta ahụmahụ dị ụtọ, onye na-abụghị - ohere ịgbatị ụbụrụ gị nnukwu O- ndetu.
O nwedịrị ndị sonyere na-akụrisị akwụkwọ mpịakọta ka ọ bụrụ slide iji dee mkpebi ha. Anaghị m achị ọchị - ha nyefere ngwugwu akwụkwọ a maka nkwenye:
Enwere ọrụ atọ na mkpokọta:
- banyere ịhọrọ oyiri site na nha maka ịhazi ibu
- gbasara nhazi rịzọlt ajuju megide nchekwa data ebe nchekwa
- na mbufe steeti na sistemụ kesara nwere topology mgbanaka
Ọrụ 1. ClisterClient
Ọ dị mkpa ịtụpụta algọridim maka nhọrọ dị mma nke K sitere na N oyiri dị arọ nke sistemụ kesara:
Enyere ndị otu gị ọrụ ịzụlite ọbá akwụkwọ ndị ahịa maka ụyọkọ N ọnụ ekesara nke ukwuu. Ọbá akwụkwọ ahụ ga-edobe usoro metadata dị iche iche jikọtara ọnụ (dịka ọmụmaatụ, latencies ha, ọnụego nzaghachi 4xx/5xx, wdg) wee kenye ha ihe ọ̀tụ̀tụ̀ na-ese n'elu mmiri W1..WN. Iji kwado atụmatụ ogbugbu a na-eme n'otu oge, ụlọ akwụkwọ ọbá akwụkwọ kwesịrị inwe ike ịhọrọ ọnụ ọnụ K nke N na-enweghị usoro-ohere nke ịhọrọ kwesịrị ịdị nhata na ịdị arọ ọnụ ọnụ.
Tụpụta algọridim ka ịhọrọ ọnụ nke ọma. Tụlee mgbagwoju anya mgbako ya site na iji nnukwu O notation.
Gịnị kpatara ihe niile ji dị na bekee?
N'ihi na n'ụdị a ndị sonyere ogbako buso ha ọgụ na n'ihi na Bekee bụ asụsụ gọọmentị Hydra. Ọrụ ndị ahụ dị ka nke a:
Were akwụkwọ na pensụl, chee echiche, emela ngwa ngwa imeghe ndị na-emebi ihe ozugbo 🙂
Nyocha nke ngwọta (vidiyo)
Malite na 5:53, naanị nkeji 4:
Ma nke a bụ ka ụmụ okorobịa ndị nwere flipchart siri kwupụta azịza ha:
Nyocha nke ngwọta (ederede)
Ngwọta na-esote dị n'elu: chịkọta nha nke ụdị oyiri niile, mepụta ọnụọgụ na-enweghị usoro site na 0 ruo nchikota nke nha niile, wee họrọ i-replica nke na nchikota nke ihe atụ oyiri sitere na 0 ruo (i-1) th. bụ ihe na-erughị a random nọmba, na nchikota nke oyiri arọ si 0 ka i-th - karịa ya. Ya mere, ọ ga-ekwe omume ịhọrọ otu oyiri, na ịhọrọ nke na-esote, ịkwesịrị ịmegharị usoro ahụ dum n'echebaraghị oyiri ahọpụtara. Site na algọridim dị otú ahụ, mgbagwoju anya nke ịhọrọ otu oyiri bụ O(N), mgbagwoju anya nke ịhọrọ K replicas bụ O (N K) ~ O (N2).
Mgbagwoju anya anọ dị njọ, mana enwere ike imeziwanye ya. Iji mee nke a, anyị ga-ewu maka nchikota arọ. A ga-enweta osisi nke omimi lg N, n'ime akwụkwọ ya nke a ga-enwe ihe nrịbama oyiri, na n'ime oghere ndị fọdụrụ - nchikota akụkụ, ruo nchikota nke ihe ọ bụla dị na mgbọrọgwụ osisi. Na-esote, anyị na-ewepụta nọmba random site na 0 ruo nchikota nke nha niile, chọta i-th oyiri, wepụ ya n'osisi ahụ, ma megharịa usoro iji chọta ihe ndị fọdụrụnụ. Site na algọridim a, mgbagwoju anya nke iwu osisi bụ O (N), mgbagwoju anya nke ịchọta i-th oyiri na iwepụ ya na osisi bụ O (lg N), mgbagwoju anya nke ịhọrọ K replicas bụ O (N + K). lg N) ~ O(N lg N) .
Ihe mgbagwoju anya-log dị mma karịa mgbagwoju anya anọ, ọkachasị maka nnukwu K.
Nke a bụ algọridim Ọbá akwụkwọ ụyọkọ ndị ahịa sitere na ọrụ a"". (N'ebe ahụ, a na-ewu osisi ahụ na O (N lg N), ma nke a anaghị emetụta njedebe ikpeazụ nke algọridim.)
Ọrụ 2. Zebra
Ọ dị mkpa ịtụpụta algọridim maka nhazi akwụkwọ nke ọma na ebe nchekwa site na mpaghara enweghị ndenye aha aka ike:
Enyere ndị otu gị ọrụ ịmepụta nchekwa data akwụkwọ echekwara echekwabara. Ọrụ na-arụkarị ọrụ ga-abụ ịhọrọ akwụkwọ N n'elu nke mpaghara ọnụọgụ aka ike (na-abụghị indexed) hazie site na nchịkọta nha M (na-abụkarị N <100 <<M). Ọrụ na-adịkarị obere obere ga-abụ ịhọrọ n'elu N mgbe ịwụsịrị akwụkwọ S n'elu (S ~ N).
Tụpụta algọridim iji mezuo ajụjụ ndị dị otú ahụ nke ọma. Tụlee mgbagwoju anya mgbako ya site na iji nnukwu ọkwa O na nkezi ikpe yana ọnọdụ kachasị njọ.
Nyocha nke ngwọta (vidiyo)
Malite na 34:50, naanị nkeji 6:
Nyocha nke ngwọta (ederede)
Ngwọta dị n'elu: hazie akwụkwọ niile (dịka ọmụmaatụ na ), wee were akwụkwọ N+S. N'okwu a, mgbagwoju anya nke nhazi bụ na nkezi O (M lg M), na kacha njọ O (M2).
O doro anya na ịhazi akwụkwọ M niile wee were naanị obere akụkụ n'ime ha adịghị arụ ọrụ. Ka ị ghara ịhazi akwụkwọ niile, algọridim dabara adaba , nke ga-ahọrọ N + S nke akwụkwọ achọrọ (ha nwere ike ịhazi ya site na algọridim ọ bụla). N'okwu a, mgbagwoju anya ga-ebelata na O (M) na nkezi, ebe ikpe kachasị njọ ga-anọgide na-abụ otu.
Otú ọ dị, ị nwere ike ime ya ọbụna karịa nke ọma - jiri algọridim . N'okwu a, a na-agbakwunye akwụkwọ N + S nke mbụ na min- max-heap (dabere n'ụdị ntụziaka), mgbe ahụ, a na-atụnyere akwụkwọ ọ bụla na-esote ya na mgbọrọgwụ nke osisi ahụ, nke nwere akwụkwọ kachasị dị ugbu a ma ọ bụ karịa, ma tinye ya na osisi ma ọ dị mkpa. N'okwu a, mgbagwoju anya na ikpe kachasị njọ, mgbe ị na-arụghachi osisi ahụ mgbe niile, bụ O (M lg M), mgbagwoju anya na nkezi bụ O (M), dị ka ngwa ngwa.
Otú ọ dị, ikpo okwu na-atụgharị ka ọ na-arụ ọrụ nke ọma n'ihi na n'omume, enwere ike ịtụfu ọtụtụ akwụkwọ na-enweghị wughachi obo ahụ mgbe e jiri otu tụnyere ya na mgbọrọgwụ mgbọrọgwụ ya. A na-emejuputa ụdị nhazi a na nchekwa data nchekwa Zebra nke emepụtara ma jiri ya na Kontur.
Ọrụ 3. Swaps steeti
Ọ dị mkpa ịtụpụta algọridim kacha arụ ọrụ maka ntụgharị okwu:
Enyere ndị otu gị ọrụ ịmepụta usoro mgbanwe steeti mara mma maka ụyọkọ N ọnụ na-ekesa. Ekwesịrị ibufe steeti i-th node na (i+1) -th node, steeti node N-th kwesịrị ibufe ya na ọnụ nke mbụ. Naanị ọrụ akwadoro bụ mgbanwe steeti mgbe ọnụ abụọ na-agbanwe steeti ha n'ụzọ atọ. A maara na mgbanwe steeti na-ewe milliseconds m. Ọnụ ọ bụla nwere ike isonye na otu mgbanwe steeti n'oge ọ bụla.
Ogologo oge ole ka ọ na-ewe iji nyefee steeti ọnụ ọnụ niile na ụyọkọ?
Nyocha nke ngwọta (ederede)
Ngwọta dị n'elu: gbanwee steeti nke mbụ na nke abụọ, mgbe ahụ nke mbụ na nke atọ, nke mbụ na nke anọ, na ndị ọzọ. Mgbe mgbanwe ọ bụla gasịrị, ọnọdụ nke otu mmewere ga-adị n'ọnọdụ a chọrọ. Ị ga-eme ka O(N) permutations na-etinye oge O(N M).
Ogologo oge nke Linear dị ogologo, ya mere ị nwere ike ịgbanwe ọnọdụ nke ihe na ụzọ abụọ: nke mbụ na nke abụọ, nke atọ na nke anọ, na na. Mgbe mgbanwe steeti ọ bụla gasịrị, ihe nke abụọ ọ bụla ga-adị n'ọnọdụ kwesịrị ekwesị. Ị ga-eme O(lg N) permutations na-etinye oge O (M lg N).
Otú ọ dị, ọ ga-ekwe omume ime mgbanwe ahụ ọbụna karịa nke ọma - ọ bụghị na linear, ma na oge na-adịgide adịgide. Iji mee nke a, na nzọụkwụ mbụ, ịkwesịrị ịgbanwe ọnọdụ nke mmewere mbụ na nke ikpeazụ, nke abụọ na nke penultimate, na ihe ndị ọzọ. Ọnọdụ nke mmewere ikpeazụ ga-adị n'ọnọdụ ziri ezi. Ma ugbu a, anyị kwesịrị ịgbanwe ọnọdụ nke ihe nke abụọ na nke ikpeazụ, nke atọ na nke penultimate, na na. Mgbe mgbanwe mgbanwe a gasịrị, steeti nke ihe niile ga-adị n'ọnọdụ kwesịrị ekwesị. A ga-enwe O(2M) ~ O(1) permutations na mkpokọta.
Ngwọta dị otú ahụ agaghị eju onye na-ahụ maka mgbakọ na mwepụ anya ma ọlị bụ onye ka na-echeta na ntụgharị bụ ihe mejupụtara abụọ axial symmetries. Site n'ụzọ, a na-akọwakarị ya n'ụzọ nkịtị maka ngbanwe ọ bụghị otu, kama site na ọnọdụ K <N. (Dee n'ime nkọwapụta etu esi eme ya.)
egwuregwu mgbagwoju anya ọ masịrị gị? Ị maara ihe ngwọta ndị ọzọ? Kekọrịta na nkwupụta.
Na ebe a bụ ụfọdụ njikọ bara uru na njedebe:
- mụtakwuo maka na contour
- hụ ndekọ nke ime banyere usoro ekesa
- kirie usoro nkuzi vidiyo»
- denye aha na anyị
isi: www.habr.com