Nahitabo pipila ka adlaw ang milabay Komperensya sa Hydra. Ang mga lalaki gikan sa JUG.ru Group nagdapit sa mga mamumulong sa damgo (Leslie Lamport! Cliff Click! Martin Kleppmann!) Si Kontur usa sa tulo ka kauban sa komperensya. Nag-istoryahanay mi sa booth, naghisgot bahin sa among gipang-apod-apod nga mga storage, nagdula og bingo, ug nagsulbad og mga puzzle.

Kini usa ka post nga adunay pagtuki sa mga buluhaton sa Kontur stand gikan sa tagsulat sa ilang teksto. Kinsa ang naa sa Hydra - kini ang imong hinungdan nga hinumdoman ang makapalipay nga kasinatian, kinsa wala - usa ka higayon nga ma-stretch ang imong utok dako O- notasyon.

May mga partisipante pa gani nga nagbungkag sa flipchart ngadto sa mga slide aron isulat ang ilang desisyon. Wala ko nagbiaybiay - gihatag nila kini nga stack sa papel alang sa pag-verify:

Adunay tulo ka mga buluhaton sa kinatibuk-an:

• mahitungod sa pagpili sa mga replika pinaagi sa mga gibug-aton alang sa pagbalanse sa load
• mahitungod sa paghan-ay sa mga resulta sa pangutana batok sa usa ka in-memorya nga database
• sa pagbalhin sa estado sa usa ka gipang-apod-apod nga sistema nga adunay topolohiya sa singsing

Buluhaton 1. ClusterClient

Gikinahanglan ang pagsugyot og algorithm alang sa episyente nga pagpili sa K gikan sa N gibug-aton nga mga replika sa usa ka gipang-apod-apod nga sistema:

Ang imong team gitahasan sa paghimo sa usa ka librarya sa kliyente alang sa usa ka kaylap nga gipang-apod-apod nga cluster sa N node. Ang librarya magsubay sa lain-laing metadata nga nalangkit sa mga node (pananglitan, ilang mga latency, 4xx/5xx response rates, ug uban pa) ug magbutang ug floating point weights nga W1..WN ngadto kanila. Aron masuportahan ang dungan nga estratehiya sa pagpatuman, ang librarya kinahanglan nga makapili sa K sa N nga mga node nga random-usa ka higayon nga mapili kinahanglan nga proporsyonal sa gibug-aton sa usa ka node.

Isugyot ang usa ka algorithm aron mapili ang mga node nga epektibo. Pagbanabana sa pagkakompyut sa computational niini gamit ang dagkong O notation.

Nganong English man ang tanan?

Tungod kay sa niini nga porma ang mga partisipante sa komperensya nakig-away uban kanila ug tungod kay ang English mao ang opisyal nga pinulongan sa Hydra. Ang mga buluhaton ingon niini:

Pagkuha ug papel ug lapis, hunahunaa, ayaw pagdali sa pag-abli sa mga spoiler dayon 🙂

Pagtuki sa solusyon (video)

Sugod sa 5:53, 4 ka minuto lang:

Ug ania kung giunsa ang mga lalaki nga adunay flipchart nagbutang sa ilang solusyon:

Pagtuki sa solusyon (teksto)

Ang mosunod nga solusyon anaa sa ibabaw: summa sa mga gibug-aton sa tanang mga replika, makamugna og random nga numero gikan sa 0 ngadto sa sumada sa tanang gibug-aton, unya pagpili og i-replica nga ang sumada sa mga gibug-aton sa replika gikan sa 0 ngadto sa (i-1) ika mao ang ubos pa kay sa usa ka random nga numero, ug ang sumada sa replica gibug-aton gikan sa 0 ngadto sa i-th - labaw pa niini. Mao nga posible nga makapili usa ka kopya, ug aron mapili ang sunod, kinahanglan nimo nga balikon ang tibuuk nga pamaagi nga wala gikonsiderar ang napili nga replika. Sa ingon nga algorithm, ang pagkakomplikado sa pagpili sa usa ka kopya mao ang O (N), ang pagkakomplikado sa pagpili sa K replika mao ang O (N K) ~ O (N2).

Ang quadratic complexity dili maayo, apan kini mahimong mapauswag. Aron mahimo kini, magtukod kami bahin nga kahoy alang sa gidaghanon sa mga gibug-aton. Makuha ang usa ka punoan sa giladmon lg N, sa mga dahon diin adunay mga gibug-aton nga hulad, ug sa nahabilin nga mga node - partial nga kantidad, hangtod sa kantidad sa tanan nga gibug-aton sa gamut sa kahoy. Sunod, makamugna kami og random nga numero gikan sa 0 ngadto sa sumada sa tanang gibug-aton, pangitaa ang i-th replica, kuhaa kini gikan sa kahoy, ug balika ang pamaagi aron makit-an ang nahabilin nga mga replika. Uban niini nga algorithm, ang pagkakomplikado sa pagtukod sa usa ka kahoy mao ang O(N), ang pagkakomplikado sa pagpangita sa i-th replica ug pagtangtang niini gikan sa kahoy mao ang O(lg N), ang pagkakomplikado sa pagpili sa K replika mao ang O(N + K lg N) ~ O(N lg N) .

Ang pagkakomplikado sa linear-log mas nindot kay sa quadratic complexity, ilabina sa dagkong K.

Kini mao ang algorithm gipatuman sa code Mga librarya sa ClusterClient gikan sa proyekto "Silangan". (Didto, ang kahoy gitukod sa O(N lg N), apan dili kini makaapekto sa katapusang pagkakomplikado sa algorithm.)

Buluhaton 2. Zebra

Gikinahanglan ang pagsugyot og usa ka algorithm alang sa episyente nga paghan-ay sa mga dokumento sa panumduman pinaagi sa usa ka arbitraryong non-indexed field:

Ang imong team gitahasan sa paghimo og sharded in-memory document database. Ang kasagarang workload mao ang pagpili sa pinakataas nga N nga mga dokumento nga gihan-ay sa usa ka arbitraryong (dili-index) nga numeric field gikan sa koleksyon sa gidak-on M (kasagaran N <100 << M). Ang usa ka gamay nga dili kaayo komon nga workload mao ang pagpili sa top N human sa paglaktaw sa top S nga mga dokumento (S ~ N).

Isugyot ang usa ka algorithm aron mapatuman ang ingon nga mga pangutana nga epektibo. Pagbanabana sa pagkakompyut sa computational niini gamit ang dagkong O notation sa kasagaran nga kaso ug ang pinakagrabe nga sitwasyon sa kaso.

Pagtuki sa solusyon (video)

Sugod sa 34:50, 6 ka minuto lang:

Pagtuki sa solusyon (teksto)

Solusyon sa nawong: pagsunud sa tanan nga mga dokumento (pananglitan sa quicksort), dayon kuhaa ang N+S nga mga dokumento. Niini nga kaso, ang pagkakomplikado sa paghan-ay sa kasagaran O(M lg M), sa pinakagrabe nga O(M2).

Klaro nga ang paghan-ay sa tanan nga mga dokumento sa M ug unya pagkuha lamang sa gamay nga bahin niini dili epektibo. Aron dili maihap ang tanan nga mga dokumento, usa ka algorithm ang angay dali nga pagpili, nga mopili sa N + S sa gitinguha nga mga dokumento (mahimong ihan-ay sa bisan unsang algorithm). Niini nga kaso, ang pagkakomplikado mokunhod ngadto sa O(M) sa kasagaran, samtang ang pinakagrabe nga kaso magpabilin nga pareho.

Bisan pa, mahimo nimo kini nga labi ka episyente - gamita ang algorithm binary heap streaming. Niini nga kaso, ang unang N+S nga mga dokumento idugang ngadto sa min- o max-heap (depende sa matang sa direksyon), ug unya ang matag sunod nga dokumento itandi sa gamut sa kahoy, nga naglangkob sa kasamtangan nga minimum o maximum nga dokumento, ug idugang sa kahoy kon gikinahanglan. Sa kini nga kaso, ang pagkakomplikado sa pinakagrabe nga kaso, kung kinahanglan nimo kanunay nga tukuron ang kahoy, mao ang O (M lg M), ang pagkakomplikado sa kasagaran mao ang O (M), sama sa quickselect.

Bisan pa, ang heap streaming nahimo nga labi ka episyente tungod sa kamatuoran nga sa praktis kadaghanan sa mga dokumento mahimong ilabay nga dili matukod pag-usab ang tambak pagkahuman sa usa ka pagtandi sa elemento sa ugat niini. Ang maong paghan-ay kay gipatuman sa Zebra in-memory document database nga naugmad ug gigamit sa Kontur.

Buluhaton 3. State swaps

Gikinahanglan nga isugyot ang labing episyente nga algorithm alang sa pagbalhin sa mga estado:

Ang imong team gitahasan sa paghimo sa usa ka uso nga mekanismo sa pagbinayloay sa estado alang sa usa ka gipang-apod-apod nga cluster sa N node. Ang estado sa i-th node kinahanglang ibalhin sa (i+1)-th node, ang estado sa N-th node kinahanglang ibalhin sa unang node. Ang gisuportahan ra nga operasyon mao ang state swap kung ang duha ka node nagbaylo sa ilang mga estado sa atomically. Nasayran nga ang state swap mokabat ug M milliseconds. Ang matag node makahimo sa pag-apil sa usa ka swap sa estado sa bisan unsang oras.

Unsa ka dugay ang pagbalhin sa mga estado sa tanan nga mga node sa usa ka cluster?

Pagtuki sa solusyon (teksto)

Surface solution: ibaylo ang mga estado sa una ug ikaduha nga elemento, dayon ang una ug ikatulo, dayon ang una ug ikaupat, ug uban pa. Pagkahuman sa matag pagbinayloay, ang kahimtang sa usa ka elemento naa sa gitinguha nga posisyon. Kinahanglan ka nga maghimo og O(N) permutasyon ug mogahin og O(N M) nga oras.

Ang linear nga oras taas, aron mahimo nimong ibaylo ang mga estado sa mga elemento nga managsama: ang una sa ikaduha, ang ikatulo sa ikaupat, ug uban pa. Pagkahuman sa matag pagbinayloay sa estado, ang matag ikaduha nga elemento naa sa husto nga posisyon. Kinahanglang maghimo ka og O(lg N) permutasyon ug mogahin og O(M lg N) nga panahon.

Bisan pa, posible nga himuon ang pagbalhin nga labi ka episyente - dili sa linear, apan sa kanunay nga oras. Aron mahimo kini, sa una nga lakang, kinahanglan nimo nga ibaylo ang kahimtang sa una nga elemento sa katapusan, ang ikaduha sa penultimate, ug uban pa. Ang kahimtang sa kataposang elemento anaa sa hustong posisyon. Ug karon kinahanglan naton ibaylo ang kahimtang sa ikaduha nga elemento sa katapusan, ang ikatulo nga adunay penultimate, ug uban pa. Pagkahuman niini nga hugna sa mga pagbinayloay, ang mga estado sa tanan nga mga elemento naa sa husto nga posisyon. Adunay O(2M) ~ O(1) permutasyon sa kinatibuk-an.

Ang ingon nga solusyon dili gyud makapakurat sa usa ka mathematician nga nahinumdom pa nga ang usa ka rotation usa ka komposisyon sa duha ka axial symmetries. Pinaagi sa dalan, kini trivially generalized alang sa usa ka pagbalhin dili sa usa, apan sa K <N posisyon. (Isulat sa mga komento kung unsa ka eksakto.)

Ganahan ka ba sa mga puzzle? Nahibal-an ba nimo ang ubang mga solusyon? Ipakigbahin sa mga komento.

Ug ania ang pipila ka mapuslanon nga mga link sa katapusan:

• pagkat-on og dugang mahitungod sa pagpalambo sa imprastraktura sa contour
• tan-awa ang mga rekord sa internal flyer nga adunay mga taho mahitungod sa gipang-apod-apod nga mga sistema
• tan-awa ang serye sa mga video lectureTalagsaon nga mga algorithm alang sa ordinaryong mga tawo»
• subscribe sa among channel sa Telegram

Source: www.habr.com