Ya faru kwanaki kadan da suka gabata . Mutanen daga ƙungiyar JUG.ru sun gayyaci masu magana da mafarki (Leslie Lamport! Cliff Click! Martin Kleppmann!) Kuma sun ba da kwana biyu don rarraba tsarin da lissafi. Kontur na ɗaya daga cikin abokan haɗin gwiwa guda uku na taron. Mun yi magana a rumfar, mun yi magana game da wuraren ajiyarmu da aka rarraba, mun buga wasan bingo, da warware wasanin gwada ilimi.
Wannan matsayi ne tare da nazarin ayyuka a Kontur daga mawallafin rubutun su. Wanene ya kasance a kan Hydra - wannan shine dalilinku don tunawa da kwarewa mai dadi, wanda ba shine damar da za ku iya shimfiɗa kwakwalwarku ba babban O- sanarwa.
Akwai ma mahalarta da suka tarwatsa faifan takarda zuwa zane-zane don rubuta shawararsu. Ba na wasa ba - sun ba da wannan tarin takarda don tabbatarwa:
Akwai ayyuka guda uku gabaɗaya:
- game da zabar kwafi ta ma'auni don daidaita nauyi
- game da rarrabuwar sakamakon tambaya akan ma'ajin bayanai na cikin ƙwaƙwalwar ajiya
- a kan canja wurin jihar a cikin tsarin da aka rarraba tare da topology na zobe
Aiki 1. ClisterClient
Ya zama dole a ba da shawarar algorithm don ingantaccen zaɓi na K daga ma'aunin N na tsarin da aka rarraba:
Ƙungiyar ku tana da alhakin haɓaka ɗakin karatu na abokin ciniki don tarin tarin N nodes da aka rarraba. Laburaren zai ci gaba da bin diddigin metadata daban-daban masu alaƙa da nodes (misali, latencies, ƙimar amsawar 4xx/5xx, da sauransu) kuma ya sanya ma'aunin nauyi W1..WN gare su. Domin tallafawa dabarun aiwatarwa na lokaci guda, ɗakin karatu ya kamata ya iya zaɓar K na N nodes ba da gangan ba - damar zaɓin ya kamata ya yi daidai da nauyin kumburi.
Ba da shawarar algorithm don zaɓar nodes da kyau. Yi ƙididdige wahalar lissafin sa ta amfani da babban bayanin O.
Me yasa komai yake cikin Ingilishi?
Domin a cikin wannan tsari mahalarta taron sun yi yaƙi da su kuma saboda Ingilishi shine harshen hukuma na Hydra. Ayyukan sun kasance kamar haka:
Ɗauki takarda da fensir, tunani, kada ku yi gaggawar buɗe masu ɓarna nan da nan 🙂
Analysis na mafita (bidiyo)
Fara daga 5:53, mintuna 4 kacal:
Ga kuma yadda mutanen da ke da kwalta suka kafa mafita:
Analysis na mafita (rubutu)
Magani mai zuwa ya ta'allaka ne akan saman: tara ma'auni na duk kwafi, samar da lambar bazuwar daga 0 zuwa jimlar duk ma'aunin nauyi, sannan zaɓi i-replica kamar jimlar ma'aunin ma'auni daga 0 zuwa (i-1)th kasa da lambar bazuwar, kuma jimillar ma'aunin ma'auni daga 0 zuwa i-th - fiye da shi. Don haka zai yiwu a zaɓi kwafi ɗaya, kuma don zaɓar na gaba, kuna buƙatar sake maimaita tsarin gaba ɗaya ba tare da la'akari da kwafin da aka zaɓa ba. Tare da irin wannan algorithm, rikitarwa na zabar kwafi ɗaya shine O(N), rikitarwar zaɓar K replicas shine O (N K) ~ O (N2).
Hadaddiyar ma'auni ba shi da kyau, amma ana iya inganta shi. Don yin wannan, za mu gina don jimlar nauyi. Za a sami bishiyar zurfin lg N, a cikin ganyayyakin da za a sami ma'auni na kwafi, kuma a cikin ragowar nodes - jimlar juzu'i, har zuwa jimlar duk ma'auni a tushen bishiyar. Na gaba, muna samar da lambar bazuwar daga 0 zuwa jimlar duk ma'auni, nemo kwafin i-th, cire shi daga bishiyar, sannan maimaita hanya don nemo sauran kwafin. Tare da wannan algorithm, ƙayyadaddun ginin bishiya shine O (N), rikitarwa na gano kwafin i-th da cire shi daga itacen shine O (lg N), rikitarwa na zabar K replicas shine O (N + K). lg N) ~ O(N lg N) .
Rubutun layin layi yana da kyau fiye da hadaddun quadratic, musamman ga manyan K.
Wannan shine algorithm ClusterClient dakunan karatu daga aikin"". (A can, an gina itacen a cikin O (N lg N), amma wannan ba zai shafi ƙayyadaddun ƙididdiga na ƙarshe ba.)
Aiki 2. Zebra
Ya wajaba a ba da shawarar algorithm don ingantaccen rarraba takardu a cikin ƙwaƙwalwar ajiya ta hanyar filin da ba na son rai ba:
Ƙungiyar ku tana da alhakin haɓaka bayanan daftarin aiki da aka share cikin ƙwaƙwalwar ajiya. Yawan aiki na gama gari shine zaɓi manyan takaddun N da aka jera su ta hanyar lambobi na sabani (marasa fihirisa) daga tarin girman M (yawanci N <100 <<M). Ƙayyadaddun aikin da ba a gama gari ba zai kasance zaɓi saman N bayan tsallake manyan S takardun (S ~ N).
Ba da shawarar algorithm don aiwatar da irin waɗannan tambayoyin yadda ya kamata. Yi ƙididdige wahalar lissafin sa ta amfani da babban bayanin O a matsakaicin yanayin da mafi munin yanayi.
Analysis na mafita (bidiyo)
Fara daga 34:50, mintuna 6 kacal:
Analysis na mafita (rubutu)
Maganin saman: warware duk takaddun (misali tare da ), sannan ku ɗauki takardun N+S. A wannan yanayin, rikitaccen rarrabuwa yana kan matsakaicin O (M lg M), a mafi munin O (M2).
A bayyane yake cewa rarrabuwar duk takaddun M sannan ɗaukar ɗan ƙaramin sashi kawai ba shi da inganci. Don kada a warware duk takaddun, algorithm ya dace , wanda zai zaɓi N + S na takaddun da ake buƙata (ana iya daidaita su ta kowane algorithm). A wannan yanayin, rikitarwa zai ragu zuwa O (M) a matsakaici, yayin da mafi munin yanayi zai kasance iri ɗaya.
Koyaya, zaku iya yin shi har ma da inganci - amfani da algorithm . A wannan yanayin, ana ƙara takaddun N + S na farko zuwa min- ko max-heap (ya danganta da nau'in shugabanci), sannan kowane takarda na gaba ana kwatanta shi da tushen bishiyar, wanda ya ƙunshi mafi ƙanƙanta ko matsakaicin takaddar yanzu. kuma ana saka shi a bishiyar idan ya cancanta. A wannan yanayin, rikitarwa a cikin mafi munin yanayi, lokacin da dole ne ku sake gina itacen kullum, shine O (M lg M), rikitarwa akan matsakaici shine O (M), kamar yadda tare da mai sauri.
Duk da haka, yawo da tulin ya zama mafi inganci saboda gaskiyar cewa a aikace mafi yawan takaddun ana iya zubar da su ba tare da sake gina tsibin ba bayan kwatancen tushen sa. Ana aiwatar da irin wannan rarrabuwa a cikin bayanan tarihin daftarin ajiya na Zebra da aka haɓaka kuma aka yi amfani da su a cikin Kontur.
Aiki 3. Canjin Jiha
Ya zama dole don ba da shawarar mafi inganci algorithm don jujjuya jihohi:
Ƙungiyar ku tana da alhakin haɓaka kyakkyawan tsarin musaya na jiha don tari na nodes masu rarraba. Ya kamata a canja wurin jihar i-th node zuwa (i+1) -th node, jihar node ta N-th yakamata a canza shi zuwa kumburin farko. Ayyukan da ake goyan baya kawai shine musanya jihar lokacin da nodes biyu ke musayar jihohin su ta atomatik. An san cewa musanyawar jiha tana ɗaukar millise seconds. Kowane kumburi zai iya shiga cikin musanyar jaha ɗaya a kowane lokaci.
Yaya tsawon lokacin da ake ɗauka don canja wurin jihohin duk nodes a cikin tari?
Analysis na mafita (rubutu)
Maganin sararin sama: musanya jihohin kashi na farko da na biyu, sannan na farko da na uku, sannan na farko da na hudu, da sauransu. Bayan kowace musayar, yanayin kashi ɗaya zai kasance a matsayin da ake so. Dole ne ku sanya O(N) permutations kuma ku ciyar da lokacin O(N M).
Lokacin layi yana da tsayi, don haka zaka iya musanya jihohin abubuwa a cikin nau'i-nau'i: na farko tare da na biyu, na uku tare da na hudu, da sauransu. Bayan kowace jiha, kowane kashi na biyu zai kasance a daidai matsayi. Dole ne ku sanya O (lg N) permutations kuma ku ciyar da lokacin O (M lg N).
Duk da haka, yana yiwuwa a sa motsi ya fi dacewa - ba a cikin layi ba, amma a cikin lokaci mai tsawo. Don yin wannan, a mataki na farko, kuna buƙatar musanya yanayin kashi na farko tare da na ƙarshe, na biyu tare da penultimate, da sauransu. Halin kashi na ƙarshe zai kasance a daidai matsayi. Kuma yanzu muna buƙatar musanya yanayin kashi na biyu tare da na ƙarshe, na uku tare da na ƙarshe, da sauransu. Bayan wannan zagaye na musayar, jihohin dukkan abubuwa za su kasance cikin matsayi mai kyau. Za a sami O(2M) ~ O(1) permutations gabaɗaya.
Irin wannan bayani ba zai yi mamakin masanin lissafi ba wanda har yanzu yana tuna cewa juyawa shine abun da ke tattare da alamomin axial guda biyu. Af, an haɗa shi da ƙima don motsi ba ɗaya ba, amma ta matsayi K <N. (Rubuta a cikin sharhi yadda daidai.)
Kuna son wasan wasa? Shin kun san sauran mafita? Raba a cikin sharhi.
Kuma ga wasu hanyoyin haɗin gwiwa masu amfani a ƙarshe:
- ƙarin koyo game da a kwane-kwane
- duba bayanan ciki game da tsarin rarrabawa
- kalli jerin laccocin bidiyo»
- ku yi subscribing din mu
source: www.habr.com