Digwyddodd ychydig ddyddiau yn ôl Cynhadledd Hydra. Gwahoddodd y bechgyn o Grŵp JUG.ru siaradwyr breuddwydiol (Leslie Lamport! Cliff Click! Martin Kleppmann!) a neilltuo dau ddiwrnod i systemau dosbarthedig a chyfrifiadura. Roedd Kontur yn un o dri phartner cynadledda. Buom yn siarad yn y stondin, yn siarad am ein storfa ddosbarthedig, yn chwarae bingo, ac yn datrys problemau.

Dyma bost gyda dadansoddiad o'r tasgau ar stondin Kontur gan awdur eu testun. I’r rhai sydd wedi bod i Hydra, dyma’ch cyfle i gofio profiadau dymunol; i’r rhai nad ydynt wedi bod, dyma gyfle i ymestyn eich ymennydd O mawr-nodiant.

Roedd hyd yn oed gyfranogwyr a ddadosododd y siart troi yn sleidiau i ysgrifennu eu datrysiad. Dydw i ddim yn twyllo - fe wnaethon nhw gyflwyno'r pentwr hwn o bapur i'w archwilio:

Roedd tair tasg i gyd:

• ynghylch dewis replicas yn ôl pwysau ar gyfer cydbwyso llwyth
• am ddidoli canlyniadau ymholiad i gronfa ddata er cof
• ar drosglwyddo gwladwriaethol mewn system ddosbarthedig gyda thopoleg gylch

Tasg 1. ClusterClient

Roedd angen cynnig algorithm ar gyfer dewis yn effeithlon atgynyrchiadau pwysol K allan o N o system ddosbarthedig:

Eich tîm sydd â'r dasg o ddatblygu llyfrgell cleientiaid ar gyfer clwstwr o nodau N sydd wedi'u dosbarthu'n aruthrol. Byddai'r llyfrgell yn cadw golwg ar fetadata amrywiol sy'n gysylltiedig â nodau (e.e., eu hwyrni, cyfraddau ymateb 4xx/5xx, ac ati) ac yn neilltuo pwysau pwynt arnawf W1..WN iddynt. Er mwyn cefnogi'r strategaeth weithredu gydamserol, dylai'r llyfrgell allu dewis K o nodau N ar hap - dylai'r siawns o gael ei ddewis fod yn gymesur â phwysau nod.

Cynigiwch algorithm i ddewis nodau'n effeithlon. Amcangyfrif ei gymhlethdod cyfrifiannol gan ddefnyddio nodiant O mawr.

Pam fod popeth yn Saesneg?

Oherwydd dyma sut y bu'r cyfranogwyr yn y gynhadledd yn eu hymladd ac oherwydd mai Saesneg oedd iaith swyddogol Hydra. Roedd y problemau'n edrych fel hyn:

Cymerwch bapur a phensil, meddyliwch, peidiwch â rhuthro i agor sbwylwyr ar unwaith :)

Dadansoddiad o'r datrysiad (fideo)

Yn dechrau am 5:53, dim ond 4 munud:

A dyma sut y gwnaeth yr un dynion hynny â'r siart troi gynnig eu datrysiad:

Dadansoddiad o'r datrysiad (testun)

Mae'r datrysiad canlynol yn gorwedd ar yr wyneb: crynhowch bwysau pob atgynhyrchiad, cynhyrchwch haprif o 0 i gyfanswm yr holl bwysau, yna dewiswch i-replica fel bod swm pwysau'r atgynyrchiadau o 0 i'r ( i-1)th yn llai na'r haprif, ac mae swm pwysau'r atgynhyrchiadau o 0 i i-th - yn fwy nag ef. Fel hyn gallwch ddewis un replica, ac i ddewis yr un nesaf, mae angen i chi ailadrodd y weithdrefn gyfan heb ystyried y replica a ddewiswyd. Gydag algorithm o'r fath, cymhlethdod dewis un replica yw O(N), cymhlethdod dewis atgynyrchiadau K yw O(N·K) ~ O(N2).

Mae cymhlethdod cwadratig yn ddrwg, ond gellir ei wella. Ar gyfer hyn byddwn yn adeiladu coeden segment am symiau o bwysau. Y canlyniad yw coeden o ddyfnder lg N, y bydd ei dail yn cynnwys pwysau'r atgynhyrchiadau, a bydd y nodau sy'n weddill yn cynnwys symiau rhannol, hyd at gyfanswm yr holl bwysau wrth wraidd y goeden. Nesaf, rydym yn cynhyrchu rhif ar hap o 0 i gyfanswm yr holl bwysau, dod o hyd i'r replica i-th, ei dynnu o'r goeden ac ailadrodd y weithdrefn i ddod o hyd i'r atgynyrchiadau sy'n weddill. Gydag algorithm o'r fath, cymhlethdod adeiladu coeden yw O(N), cymhlethdod dod o hyd i'r replica i-th a'i dynnu o'r goeden yw O(lg N), cymhlethdod dewis K replicas yw O(N + K lg N) ~ O(N lg N).

Mae cymhlethdod llinellol-logarithmig yn brafiach na chymhlethdod cwadratig, yn enwedig ar gyfer K mawr.

Dyma'r algorithm hwn gweithredu yn y cod Llyfrgelloedd Clwstwr o'r prosiect "Ddwyrain" (Yno mae'r goeden wedi'i hadeiladu yn O(N lg N), ond nid yw hyn yn effeithio ar gymhlethdod terfynol yr algorithm.)

Problem 2. Sebra

Roedd angen cynnig algorithm ar gyfer didoli dogfennau yn y cof yn effeithlon yn ôl maes mympwyol heb ei fynegeio:

Eich tîm sydd â'r dasg o ddatblygu cronfa ddata o ddogfennau cof wedi'u rhannu. Llwyth gwaith cyffredin fyddai dewis prif ddogfennau N wedi'u didoli yn ôl maes rhifol mympwyol (heb ei fynegeio) o gasgliad o faint M (N < 100 << M fel arfer). Llwyth gwaith ychydig yn llai cyffredin fyddai dewis N uchaf ar ôl hepgor y dogfennau S uchaf (S ~ N).

Cynnig algorithm i weithredu ymholiadau o'r fath yn effeithlon. Amcangyfrif ei gymhlethdod cyfrifiannol gan ddefnyddio nodiant O mawr yn yr achos cyffredin a'r senarios achos gwaethaf.

Dadansoddiad o'r datrysiad (fideo)

Yn dechrau am 34:50, dim ond 6 munud:

Dadansoddiad o'r datrysiad (testun)

Ateb ar yr wyneb: didoli pob dogfen (er enghraifft, defnyddio math cyflym), yna cymerwch ddogfennau N+S. Yn yr achos hwn, cymhlethdod didoli ar gyfartaledd yw O(M lg M), ar ei waethaf mae'n O(M2).

Yn amlwg, mae didoli holl ddogfennau M ac yna cymryd dim ond rhan fach ohonynt yn aneffeithlon. Er mwyn peidio â didoli pob dogfen, bydd algorithm yn ei wneud dewis cyflym, a fydd yn dewis dogfennau gofynnol N+S (gellir eu didoli gan unrhyw algorithm). Yn yr achos hwn, bydd y cymhlethdod yn cael ei leihau i O(M) ar gyfartaledd, a bydd yr achos gwaethaf yn aros yr un fath.

Fodd bynnag, gallwch chi ei wneud hyd yn oed yn fwy effeithlon - defnyddiwch yr algorithm ffrydio domen deuaidd. Yn yr achos hwn, mae'r dogfennau N+S cyntaf yn cael eu hychwanegu at bentwr isaf neu uchaf (yn dibynnu ar y cyfeiriad didoli), ac yna mae pob dogfen ddilynol yn cael ei chymharu â gwraidd y goeden, sy'n cynnwys y ddogfen isafswm neu uchafswm cyfredol , ac, os oes angen, yn cael ei ychwanegu at y goeden . Yn yr achos hwn, y cymhlethdod yn yr achos gwaethaf, pan fydd yn rhaid i chi ailadeiladu'r goeden yn gyson, yw O(M lg M), y cymhlethdod ar gyfartaledd yw O(M), fel wrth ddefnyddio quickselect.

Fodd bynnag, mae ffrydio tomen yn troi allan i fod yn fwy effeithlon oherwydd y ffaith y gellir taflu'r rhan fwyaf o'r dogfennau yn ymarferol heb ailadeiladu'r domen, ar ôl un gymhariaeth â'i elfen wreiddiau. Gweithredir y didoli hwn yng nghronfa ddata dogfennau cof Sebra, a ddatblygwyd ac a ddefnyddir yn Kontur.

Problem 3. Cyfnewidiadau cyflwr

Roedd angen cynnig yr algorithm mwyaf effeithlon ar gyfer cyflyrau cyfnewidiol:

Eich tîm sydd â'r dasg o ddatblygu mecanwaith cyfnewid cyflwr ffansi ar gyfer clwstwr gwasgaredig o nodau N. Dylid trosglwyddo cyflwr y nod i-th i'r (i+1)-fed nod, dylid trosglwyddo cyflwr y nod N-th i'r nod cyntaf. Yr unig weithrediad a gefnogir yw'r cyfnewid cyflwr pan fydd dau nod yn cyfnewid eu cyflwr yn atomig. Mae'n hysbys bod cyfnewid cyflwr yn cymryd milieiliadau M. Mae pob nod yn gallu cymryd rhan mewn cyfnewidiad gwladwriaeth sengl ar unrhyw adeg benodol.

Pa mor hir mae'n ei gymryd i drosglwyddo cyflwr pob nod mewn clwstwr?

Dadansoddiad o'r datrysiad (testun)

Yr ateb ar yr wyneb: cyfnewid cyflwr yr elfen gyntaf a'r ail, yna'r cyntaf a'r trydydd, yna'r cyntaf a'r pedwerydd, ac ati. Ar ôl pob cyfnewid, bydd cyflwr un elfen yn y sefyllfa ddymunol. Bydd yn rhaid i chi wneud trynewidiadau O(N) a threulio amser O(N·M).

Mae amser llinol yn hir, felly gallwch chi gyfnewid cyflwr yr elfennau mewn parau: y cyntaf gyda'r ail, y trydydd gyda'r pedwerydd, ac yn y blaen. Ar ôl pob cyfnewid cyflwr, bydd pob ail elfen yn y sefyllfa ddymunol. Bydd yn rhaid i chi wneud trynewidiadau O(lg N) a threulio amser O(M lg N).

Fodd bynnag, gallwch chi wneud y sifft hyd yn oed yn fwy effeithlon - nid yn llinol, ond mewn amser cyson. I wneud hyn, yn y cam cyntaf mae angen i chi gyfnewid cyflwr yr elfen gyntaf gyda'r olaf, yr ail gyda'r olaf ond un, ac ati. Bydd cyflwr yr elfen olaf yn y sefyllfa ddymunol. Ac yn awr mae angen i ni gyfnewid cyflwr yr ail elfen gyda'r un olaf, y trydydd un gyda'r olaf ond un, ac yn y blaen. Ar ôl y rownd hon o gyfnewidiadau, bydd cyflwr yr holl elfennau yn y sefyllfa ddymunol. Yn gyfan gwbl, bydd cyfnewidiadau O(2M) ~ O(1) yn cael eu gwneud.

Ni fydd datrysiad o'r fath yn synnu mathemategydd o gwbl, sy'n dal i gofio bod cylchdroi yn gyfansoddiad o ddau gymesuredd echelinol. Gyda llaw, caiff ei gyffredinoli'n ddibwys i symud nid gan un, ond gan safleoedd K < N. (Ysgrifennwch yn y sylwadau sut yn union.)

Oeddech chi'n hoffi'r posau? Ydych chi'n gwybod atebion eraill? Rhannwch yn y sylwadau.

Dyma rai dolenni defnyddiol terfynol:

• darganfod mwy am datblygu seilwaith yn Kontur
• edrych ar gofnodion mewnol taflen gydag adroddiadau am systemau gwasgaredig
• gwyliwch y gyfres o ddarlithoedd fideo"Algorithmau anarferol ar gyfer pobl gyffredin»
• tanysgrifio i'n Sianel telegram

Ffynhonnell: hab.com