Kwenzeke ezinsukwini ezimbalwa ezedlule Hydra Conference. Abafana beQembu le-JUG.ru bameme izikhulumi zamaphupho (Leslie Lamport! Cliff Click! Martin Kleppmann!) futhi banikela izinsuku ezimbili kumasistimu asabalalisiwe nakukhompyutha. U-Kontur ubengomunye wabalingani abathathu bengqungquthela. Saxoxa edokodweni, sakhuluma ngesitoreji sethu esisabalalisiwe, sadlala ibhingo, futhi saxazulula izindida.

Lokhu okuthunyelwe okunokuhlaziywa kwemisebenzi endaweni yesitendi ye-Kontur evela kumbhali wombhalo wabo. Ubani owayeku-Hydra - lesi yisizathu sakho sokukhumbula isipiliyoni esimnandi, owayengeyena - ithuba lokwelula ubuchopho bakho omkhulu O-notation.

Kwakukhona ngisho nabahlanganyeli abahlakaza i-flipshart benza amaslayidi ukuze babhale phansi isinqumo sabo. Angidlali - banikeze lesi sitaki sephepha ukuze siqinisekiswe:

Kwakunemisebenzi emithathu isiyonke:

• mayelana nokukhetha izifaniso ngezisindo zokulinganisa umthwalo
• mayelana nokuhlunga imiphumela yombuzo ngokuqhathanisa nesizindalwazi esisenkumbulo
• ekudluliselweni kombuso ohlelweni olusabalalisiwe olune-topology eyindandatho

Umsebenzi 1. ClusterClient

Bekudingeka ukuphakamisa i-algorithm yokukhethwa okuphumelelayo kwe-K kusukela kuzifaniso ezinesisindo esingu-N zesistimu esabalalisiwe:

Ithimba lakho linomsebenzi wokuthuthukisa umtapo wolwazi weklayenti weqoqo elisatshalaliswe kakhulu lama-N node. Ilabhulali izolandelela imethadatha ehlukahlukene ehlotshaniswa namanodi (isb, ukubambezeleka kwawo, izilinganiso zokuphendula ezingu-4xx/5xx, njll.) futhi inikeze izisindo zamaphoyinti antantayo u-W1..WN kuwo. Ukuze kusekelwe isu lokusebenza ngesikhathi esisodwa, ilabhulali kufanele ikwazi ukukhetha amanodi angu-K kwangu-N ngokungahleliwe—ithuba lokukhethwa kufanele lilingane nesisindo senodi.

Phakamisa i-algorithm ukuze ukhethe amanodi ngokuphumelelayo. Linganisela ubunkimbinkimbi bayo bekhompyutha usebenzisa notation enkulu ye-O.

Kungani yonke into ingesiNgisi?

Ngoba ngale ndlela abahlanganyeli benkomfa balwa nabo futhi ngenxa yokuthi isiNgisi kwakuwulimi olusemthethweni lwaseHydra. Imisebenzi yayibukeka kanje:

Thatha iphepha nepensela, cabanga, ungajahi ukuvula abaphangi ngaso leso sikhathi 🙂

Ukuhlaziywa kwesixazululo (ividiyo)

Iqala ngo-5:53, imizuzu emi-4 kuphela:

Futhi nansi indlela abafana abane-flipchart abasibeka ngayo isisombululo sabo:

Ukuhlaziywa kwesixazululo (umbhalo)

Isixazululo esilandelayo siphezu komhlaba: hlanganisa izisindo zazo zonke izifaniso, khiqiza inombolo engahleliwe ukusuka ku-0 iye kwisamba sazo zonke izisindo, bese ukhetha i-i-replica ukuze isamba sesisindo sekhophi sisuke ku-0 siye ku-(i-1)th. ingaphansi kwenombolo engahleliwe, kanye nesamba sezisindo eziyifaniso ukusuka ku-0 kuye ku-i-th - ngaphezu kwayo. Ngakho-ke kuzokwazi ukukhetha i-replica eyodwa, futhi ukukhetha elandelayo, udinga ukuphinda yonke inqubo ngaphandle kokucabangela i-replica ekhethiwe. Nge-algorithm enjalo, inkimbinkimbi yokukhetha ikhophi eyodwa ingu-O(N), inkimbinkimbi yokukhetha ama-K replicas ithi O(N K) ~ O(N2).

I-Quadratic complexity yimbi, kodwa ingathuthukiswa. Ukwenza lokhu, sizokwakha isihlahla sesigaba ngezibalo zezisindo. Isihlahla sokujula lg N sizotholakala, emaqabunga ayo kuzoba nezisindo eziphindaphindayo, futhi kuma-node asele - izibalo eziyingxenye, kuze kufike esilinganisweni sazo zonke izisindo empandeni yesihlahla. Okulandelayo, sikhiqiza inombolo engahleliwe ukusuka ku-0 kuye esilinganisweni sazo zonke izisindo, sithole i-i-th replica, siyisuse esihlahleni, bese siphinda inqubo ukuze sithole izifaniso ezisele. Ngalolu hlelo lokusebenza, inkimbinkimbi yokwakha isihlahla ingu-O(N), inkimbinkimbi yokuthola i-i-th replica bese uyisusa esihlahleni ngu-O(lg N), inkimbinkimbi yokukhetha ama-K replicas ngu-O(N + K). lg N) ~ O(N lg N) .

Ubunkimbinkimbi bomugqa womugqa bungcono kunobunzima obuyi-quadratic, ikakhulukazi ku-K enkulu.

Yile algorithm yenziwe ngekhodi Imitapo yolwazi ye-ClusterClient evela kuphrojekthi "EMpumalanga". (Lapho, isihlahla sakhiwe ngo-O(N lg N), kodwa lokhu akuthinti ubunkimbinkimbi bokugcina be-algorithm.)

Umsebenzi 2. Idube

Bekudingekile ukwenza isiphakamiso se-algorithm yokuhlunga kahle amadokhumenti enkumbulweni kusetshenziswa inkambu engafakwanga ohlwini ngokungafanele:

Ithimba lakho linikezwe umsebenzi wokwakha isizindalwazi semibhalo yenkumbulo ehlanganisiwe. Umsebenzi ovamile uzoba ukukhetha amadokhumenti aphezulu angu-N ahlungwe ngenkambu yezinombolo ngokunganaki (engenayo inkomba) eqoqweni likasayizi M (ngokuvamile u-N <100 << M). Umsebenzi ovamile kancane kancane kungaba ukukhetha u-N ophezulu ngemva kokweqa imibhalo ye-S ephezulu (S ~ N).

Phakamisa i-algorithm ukuze wenze imibuzo enjalo ngempumelelo. Linganisela ubunkimbinkimbi bayo bekhompyutha usebenzisa i-O big notation esimweni esimaphakathi kanye nezimo ezimbi kakhulu.

Ukuhlaziywa kwesixazululo (ividiyo)

Iqala ngo-34:50, imizuzu engu-6 kuphela:

Ukuhlaziywa kwesixazululo (umbhalo)

Isixazululo esingaphezulu: hlela wonke amadokhumenti (isibonelo nge usuthu), bese uthatha amadokhumenti e-N+S. Kulokhu, inkimbinkimbi yokuhlunga ngokwesilinganiso i-O(M lg M), kokubi kakhulu u-O(M2).

Kusobala ukuthi ukuhlunga wonke amadokhumenti angu-M bese uthatha ingxenye encane yawo kungasebenzi kahle. Ukuze ungahlungi wonke amadokhumenti, i-algorithm ifanelekile ukukhetha okusheshayo, ezokhetha u-N + S wemibhalo oyifunayo (angahlelwa nganoma iyiphi i-algorithm). Kulokhu, inkimbinkimbi izokwehla ibe ngu-O(M) ngokwesilinganiso, kuyilapho isimo esibi kakhulu sizohlala sinjalo.

Nokho, ungakwenza ngokuphumelelayo nakakhulu - sebenzisa i-algorithm ukusakaza kwenqwaba kanambambili. Kulokhu, imibhalo yokuqala ye-N+S yengezwa ku-min- noma i-max-heap (kuye ngokuthi isiqondiso sohlobo luni), bese idokhumenti ngayinye elandelayo iqhathaniswa nempande yesihlahla, equkethe ubuncane bamanje noma idokhumenti ephezulu, futhi yengezwe esihlahleni uma kunesidingo. Kulokhu, inkimbinkimbi esimweni esibi kakhulu, lapho kufanele uhlale wakha kabusha isihlahla, i-O(M lg M), inkimbinkimbi ngokwesilinganiso i-O(M), njengokukhetha okusheshayo.

Kodwa-ke, ukusakazwa kwenqwaba kubonakala kusebenza kahle kakhulu ngenxa yokuthi empeleni amadokhumenti amaningi angalahlwa ngaphandle kokwakha kabusha inqwaba ngemva kokuqhathanisa okukodwa nesici sayo esiyimpande. Ukuhlunga okunjalo kwenziwa kusizindalwazi sedube senkumbulo esenziwe sasetshenziswa e-Kontur.

Umsebenzi 3. Ukushintshashintsha kwesimo

Kwakudingeka ukuphakamisa i-algorithm esebenza kahle kakhulu yokushintsha izifunda:

Ithimba lakho linikezwe umsebenzi wokwakha indlela yokushintshisana yezwe esezingeni eliphezulu yeqoqo elisabalalisiwe lamanodi angu-N. Isimo se-i-th node kufanele sidluliselwe kunodi (i+1)-th, isimo se-N-th node kufanele sidluliselwe kunodi yokuqala. Okuwukuphela komsebenzi okusekelwayo ukushintshana kombuso lapho amanodi amabili eshintshanisa izifundazwe zawo nge-athomu. Kuyaziwa ukuthi ukushintshwa kombuso kuthatha ama-millisecond angu-M. Yonke i-node iyakwazi ukubamba iqhaza ekushintsheni izwe elilodwa nganoma yisiphi isikhathi.

Kuthatha isikhathi esingakanani ukudlulisa izifunda zawo wonke ama-node kuqoqo?

Ukuhlaziywa kwesixazululo (umbhalo)

Isixazululo se-Surface: ukushintshanisa izifunda zesici sokuqala nesesibili, bese kuba eyokuqala neyesithathu, bese kuba eyokuqala neyesine, njalonjalo. Ngemva kokushintshana ngakunye, isimo se-elementi eyodwa sizoba sendaweni oyifunayo. Kufanele wenze izimvume zika-O(N) futhi usebenzise isikhathi esingu-O(N M).

Isikhathi somugqa side, ngakho-ke ungakwazi ukushintshanisa izimo zezakhi ngamabili: eyokuqala neyesibili, eyesithathu neyesine, njalonjalo. Ngemva kokushintshana kwezwe ngalinye, yonke into yesibili izoba sendaweni efanele. Kufanele wenze izimvume ze-O(lg N) futhi usebenzise isikhathi esingu-O(M lg N).

Kodwa-ke, kungenzeka ukwenza ukuguqulwa kuphumelele nakakhulu - hhayi ngomugqa, kodwa ngesikhathi esifanayo. Ukuze wenze lokhu, esinyathelweni sokuqala, udinga ukushintshanisa isimo sesici sokuqala nesokugcina, okwesibili nesokugcina, njalonjalo. Isimo se-elementi yokugcina sizoba sendaweni efanele. Futhi manje sidinga ukushintshanisa isimo sesici sesibili nesokugcina, esesithathu nesokugcina, njalonjalo. Ngemuva kwalo mzuliswano wokushintshana, izifunda zazo zonke izici zizoba sesimweni esifanele. Kuzoba nezimvume zika-O(2M) ~ O(1) seziphelele.

Isixazululo esinjalo ngeke neze simmangaze isazi sezibalo esakhumbula ukuthi ukujikeleza kuyinhlanganisela yama-axial symmetries amabili. By the way, it is attly generalized for shift not by one, but by K <N positions. (Bhala kumazwana ukuthi kanjani kahle.)

Uwathandile ama-puzzle? Uyazazi ezinye izixazululo? Yabelana kumazwana.

Futhi nazi izixhumanisi eziwusizo ekugcineni:

• funda kabanzi mayelana ukuthuthukiswa kwengqalasizinda ku-contour
• bona amarekhodi angaphakathi iflaya enemibiko mayelana nezinhlelo ezisatshalaliswa
• bukela uchungechunge lwezinkulumo zevidiyoAma-algorithms angajwayelekile kubantu abajwayelekile»
• bhalisa kweyethu isiteshi kuTelegram

Source: www.habr.com