Nangyari ilang araw na ang nakalipas . Ang mga lalaki mula sa JUG.ru Group ay nag-imbita ng mga dream speaker (Leslie Lamport! Cliff Click! Martin Kleppmann!) at naglaan ng dalawang araw sa mga distributed system at computing. Si Kontur ay isa sa tatlong kasosyo ng kumperensya. Nag-usap kami sa booth, nag-usap tungkol sa aming mga ibinahagi na storage, naglaro ng bingo, at nag-solve ng mga puzzle.
Ito ay isang post na may pagsusuri ng mga gawain sa Kontur stand mula sa may-akda ng kanilang teksto. Sino ang nasa Hydra - ito ang dahilan mo para alalahanin ang kaaya-ayang karanasan, kung sino ang hindi - isang pagkakataong palawakin ang iyong utak malaki O-notasyon.
May mga kalahok pa na binuwag ang flipchart sa mga slide para isulat ang kanilang desisyon. Hindi ako nagbibiro - ibinigay nila itong stack ng papel para sa pag-verify:
Mayroong tatlong mga gawain sa kabuuan:
- tungkol sa pagpili ng mga replika ayon sa mga timbang para sa pagbabalanse ng load
- tungkol sa pag-uuri ng mga resulta ng query laban sa isang in-memory na database
- sa paglipat ng estado sa isang distributed system na may ring topology
Gawain 1. ClusterClient
Kinailangan na magmungkahi ng isang algorithm para sa mahusay na pagpili ng K mula sa N weighted replika ng isang distributed system:
Ang iyong koponan ay may tungkulin sa pagbuo ng isang library ng kliyente para sa isang malawakang ipinamamahaging kumpol ng mga N node. Susubaybayan ng library ang iba't ibang metadata na nauugnay sa mga node (hal., ang kanilang mga latency, 4xx/5xx rate ng pagtugon, atbp.) at magtatalaga ng mga floating point na timbang W1..WN sa kanila. Upang masuportahan ang kasabay na diskarte sa pagpapatupad, ang library ay dapat na pumili ng K ng N node nang randomβang pagkakataong mapili ay dapat na proporsyonal sa bigat ng isang node.
Magmungkahi ng isang algorithm upang pumili ng mga node nang mahusay. Tantyahin ang computational complexity nito gamit ang big O notation.
Bakit English ang lahat?
Dahil sa pormang ito ang mga kalahok sa kumperensya ay nakipaglaban sa kanila at dahil Ingles ang opisyal na wika ng Hydra. Ang mga gawain ay ganito ang hitsura:
Kumuha ng papel at lapis, isipin, huwag magmadali upang magbukas ng mga spoiler kaagad π
Pagsusuri ng solusyon (video)
Simula sa 5:53, 4 minuto lang:
At narito kung paano itinayo ng mga taong may flipchart ang kanilang solusyon:
Pagsusuri ng solusyon (teksto)
Ang sumusunod na solusyon ay nasa ibabaw: pagsama-samahin ang mga timbang ng lahat ng mga replika, bumuo ng isang random na numero mula 0 hanggang sa kabuuan ng lahat ng mga timbang, pagkatapos ay pumili ng isang i-replica upang ang kabuuan ng mga replica na timbang mula 0 hanggang (i-1) ika ay mas mababa sa isang random na numero, at ang kabuuan ng mga replica na timbang mula 0 hanggang i-th - higit pa rito. Kaya posible na pumili ng isang replika, at upang piliin ang susunod, kailangan mong ulitin ang buong pamamaraan nang hindi isinasaalang-alang ang napiling replika. Sa ganitong algorithm, ang pagiging kumplikado ng pagpili ng isang replika ay O(N), ang pagiging kumplikado ng pagpili ng K replika ay O(N K) ~ O(N2).
Ang quadratic complexity ay masama, ngunit maaari itong mapabuti. Upang gawin ito, bubuo kami para sa mga kabuuan ng mga timbang. Ang isang puno ng lalim lg N ay makukuha, sa mga dahon kung saan magkakaroon ng mga replica na timbang, at sa natitirang mga node - mga bahagyang kabuuan, hanggang sa kabuuan ng lahat ng mga timbang sa ugat ng puno. Susunod, bumubuo kami ng isang random na numero mula 0 hanggang sa kabuuan ng lahat ng mga timbang, hanapin ang i-th replica, alisin ito mula sa puno, at ulitin ang pamamaraan upang mahanap ang natitirang mga replika. Sa algorithm na ito, ang pagiging kumplikado ng pagbuo ng isang puno ay O(N), ang pagiging kumplikado ng paghahanap ng i-th replica at pag-alis nito mula sa puno ay O(lg N), ang pagiging kumplikado ng pagpili ng K replica ay O(N + K lg N) ~ O(N lg N) .
Ang linear-log complexity ay mas maganda kaysa sa quadratic complexity, lalo na para sa malaking K.
Ito ang algorithm na ito ClusterClient library mula sa proyekto "". (Doon, ang puno ay binuo sa O(N lg N), ngunit hindi ito nakakaapekto sa panghuling kumplikado ng algorithm.)
Gawain 2. Zebra
Kinailangan na magmungkahi ng isang algorithm para sa mahusay na pag-uuri ng mga dokumento sa memorya ng isang di-makatwirang hindi na-index na patlang:
Ang iyong koponan ay nakatalaga sa pagbuo ng isang sharded in-memory na database ng dokumento. Ang isang karaniwang workload ay ang pagpili ng nangungunang N mga dokumento na pinagsunod-sunod ayon sa isang arbitrary (hindi na-index) na numeric field mula sa isang koleksyon ng laki M (karaniwan ay N <100 << M). Ang isang bahagyang hindi gaanong karaniwang workload ay ang piliin ang nangungunang N pagkatapos laktawan ang mga nangungunang S na dokumento (S ~ N).
Magmungkahi ng isang algorithm upang maisagawa ang mga naturang query nang mahusay. Tantyahin ang computational complexity nito gamit ang big O notation sa average na kaso at ang pinakamasamang sitwasyon sa sitwasyon.
Pagsusuri ng solusyon (video)
Simula sa 34:50, 6 minuto lang:
Pagsusuri ng solusyon (teksto)
Surface solution: pag-uri-uriin ang lahat ng mga dokumento (halimbawa sa ), pagkatapos ay kumuha ng mga N+S na dokumento. Sa kasong ito, ang pagiging kumplikado ng pag-uuri ay nasa average na O(M lg M), sa pinakamalala O(M2).
Malinaw na ang pag-uuri ng lahat ng M na dokumento at pagkatapos ay kunin lamang ang isang maliit na bahagi ng mga ito ay hindi mahusay. Upang hindi pag-uri-uriin ang lahat ng mga dokumento, angkop ang isang algorithm , na pipiliin ang N + S ng mga nais na dokumento (maaari silang pagbukud-bukurin ayon sa anumang algorithm). Sa kasong ito, ang pagiging kumplikado ay bababa sa O(M) sa karaniwan, habang ang pinakamasamang kaso ay mananatiling pareho.
Gayunpaman, magagawa mo ito nang mas mahusay - gamitin ang algorithm . Sa kasong ito, ang mga unang N+S na dokumento ay idinaragdag sa min- o max-heap (depende sa direksyon ng pag-uuri), at pagkatapos ay ihahambing ang bawat susunod na dokumento sa ugat ng puno, na naglalaman ng kasalukuyang minimum o maximum na dokumento, at idinaragdag sa puno kung kinakailangan. Sa kasong ito, ang pagiging kumplikado sa pinakamasamang kaso, kapag kailangan mong patuloy na muling itayo ang puno, ay O(M lg M), ang pagiging kumplikado sa karaniwan ay O(M), tulad ng sa quickselect.
Gayunpaman, lumalabas na mas mahusay ang heap streaming dahil sa katotohanan na sa pagsasagawa ang karamihan sa mga dokumento ay maaaring itapon nang hindi muling itinatayo ang heap pagkatapos ng isang paghahambing sa elementong ugat nito. Ang ganitong pag-uuri ay ipinatupad sa Zebra in-memory document database na binuo at ginamit sa Kontur.
Gawain 3. State swaps
Kinakailangan na imungkahi ang pinaka mahusay na algorithm para sa paglilipat ng mga estado:
Ang iyong koponan ay may tungkulin sa pagbuo ng isang magarbong mekanismo ng palitan ng estado para sa isang distributed cluster ng N node. Ang estado ng i-th node ay dapat ilipat sa (i+1)-th node, ang estado ng N-th node ay dapat ilipat sa unang node. Ang tanging sinusuportahang operasyon ay ang state swap kapag ang dalawang node ay nagpapalitan ng kanilang mga estado sa atomically. Alam na ang isang state swap ay tumatagal ng M millisecond. Ang bawat node ay maaaring lumahok sa isang solong state swap sa anumang naibigay na sandali.
Gaano katagal bago ilipat ang mga estado ng lahat ng node sa isang cluster?
Pagsusuri ng solusyon (teksto)
Solusyon sa ibabaw: palitan ang mga estado ng una at pangalawang elemento, pagkatapos ay ang una at pangatlo, pagkatapos ay ang una at ikaapat, at iba pa. Pagkatapos ng bawat palitan, ang estado ng isang elemento ay nasa nais na posisyon. Kailangan mong gumawa ng O(N) permutations at gumugol ng O(N M) na oras.
Ang linear na oras ay mahaba, kaya maaari mong palitan ang mga estado ng mga elemento sa mga pares: ang una sa pangalawa, ang pangatlo sa ikaapat, at iba pa. Pagkatapos ng bawat palitan ng estado, ang bawat pangalawang elemento ay nasa tamang posisyon. Kailangan mong gumawa ng O(lg N) permutations at gumugol ng O(M lg N) na oras.
Gayunpaman, posible na gawing mas mahusay ang paglilipat - hindi sa linear, ngunit sa patuloy na oras. Upang gawin ito, sa unang hakbang, kailangan mong palitan ang estado ng unang elemento sa huli, ang pangalawa sa penultimate, at iba pa. Ang estado ng huling elemento ay nasa tamang posisyon. At ngayon kailangan nating palitan ang estado ng pangalawang elemento sa huli, ang pangatlo sa penultimate, at iba pa. Pagkatapos ng round na ito ng palitan, ang mga estado ng lahat ng elemento ay nasa tamang posisyon. Magkakaroon ng O(2M) ~ O(1) permutations sa kabuuan.
Ang ganitong solusyon ay hindi magugulat sa isang mathematician na naaalala pa rin na ang isang pag-ikot ay isang komposisyon ng dalawang axial symmetries. Sa pamamagitan ng paraan, ito ay trivially pangkalahatan para sa isang shift hindi sa pamamagitan ng isa, ngunit sa pamamagitan ng K <N posisyon. (Isulat sa mga komento kung paano eksakto.)
Nagustuhan mo ba ang mga puzzle? Alam mo ba ang iba pang solusyon? Ibahagi sa mga komento.
At narito ang ilang mga kapaki-pakinabang na link sa dulo:
- Matuto ng mas marami tungkol sa sa tabas
- tingnan ang mga talaan ng panloob tungkol sa mga distributed system
- panoorin ang serye ng mga video lectureΒ»
- mag-subscribe sa aming
Pinagmulan: www.habr.com