Thachair beagan làithean air ais . Thug na balaich bho JUG.ru Group cuireadh do luchd-labhairt bruadar (Leslie Lamport! Cliff Click! Martin Kleppmann!) agus chuir iad seachad dà latha gu siostaman sgaoilte agus coimpiutaireachd. Bha Kontur air aon de na trì com-pàirtichean aig a’ cho-labhairt. Bhruidhinn sinn aig a ’bhothan, bhruidhinn sinn mu na stòran stòraidh sgaoilte againn, chluich sinn bingo, agus dh’ fhuasgail sinn tòimhseachain.
Seo post le mion-sgrùdadh air gnìomhan aig ionad Kontur bho ùghdar an teacsa aca. Cò a bha air an Hydra - is e seo an adhbhar agad airson cuimhneachadh air an eòlas tlachdmhor, cò nach robh - cothrom do eanchainn a shìneadh mòr O.- comharrachadh.
Bha eadhon com-pàirtichean ann a thug às a’ chairt-flip gu sleamhnagan gus an co-dhùnadh aca a sgrìobhadh sìos. Chan eil mi a’ magadh - thug iad seachad an stac pàipear seo airson dearbhadh:
Bha trì gnìomhan ann uile gu lèir:
- mu bhith a’ taghadh mac-samhail a rèir cuideaman airson cothromachadh luchdan
- mu bhith a’ rèiteach toraidhean ceist mu choinneamh stòr-dàta cuimhneachaidh
- air gluasad stàite ann an siostam sgaoilte le topology fàinne
Tasg 1. ClusterClient
Bha e riatanach algairim a mholadh airson taghadh èifeachdach de mhac-samhail K bho N de shiostam sgaoilte:
Tha e mar dhleastanas air an sgioba agad leabharlann teachdaiche a leasachadh airson cruinneachadh mòr de nodan N. Bhiodh an leabharlann a’ cumail sùil air diofar mheata-dàta co-cheangailte ri nodan (me, an ùine ghoirid, ìrean freagairt 4xx/5xx, msaa) agus a’ sònrachadh cuideaman puing-fleòdraidh W1..WN dhaibh. Gus taic a thoirt don ro-innleachd cur gu bàs aig an aon àm, bu chòir gum biodh an leabharlann comasach air nodan K de N a thaghadh air thuaiream - bu chòir cothrom a bhith air a thaghadh a rèir cuideam nód.
Mol algorithm gus nodan a thaghadh gu h-èifeachdach. Dèan tuairmse air iom-fhillteachd àireamhachd a’ cleachdadh comharradh O mòr.
Carson a tha a h-uile rud sa Bheurla?
Air sgàth anns an fhoirm seo bha com-pàirtichean na co-labhairt a’ sabaid leotha agus leis gur e Beurla cànan oifigeil Hydra. Bha na gnìomhan a’ coimhead mar seo:
Gabh pàipear is peansail, smaoinich, na dèan cabhag gus spoilers fhosgladh anns a’ bhad 🙂
Mion-sgrùdadh air an fhuasgladh (bhidio)
A’ tòiseachadh aig 5:53, dìreach 4 mionaidean:
Agus seo mar a chuir na balaich leis a’ chairt-flip air am fuasgladh:
Mion-sgrùdadh air an fhuasgladh (teacsa)
Tha am fuasgladh a leanas na laighe air an uachdar: suim cuideaman a h-uile mac-samhail, cruthaich àireamh air thuaiream bho 0 gu suim a h-uile cuideam, an uairsin tagh i-mac-samhail gus am bi suim mac-samhail cuideaman bho 0 gu (i-1)th nas lugha na àireamh air thuaiream, agus tha suim mac-samhail cuideaman bho 0 gu i-th - nas motha na e. Mar sin bidh e comasach aon mac-samhail a thaghadh, agus gus an ath fhear a thaghadh, feumaidh tu am modh-obrach gu lèir ath-aithris gun a bhith a 'beachdachadh air a' mhac-samhail a chaidh a thaghadh. Le leithid de algairim, is e iom-fhillteachd taghadh aon mac-samhail O(N), is e iom-fhillteachd taghadh mac-samhail K O(N K) ~ O(N2).
Tha iom-fhillteachd ceithir-cheàrnach dona, ach faodar a leasachadh. Gus seo a dhèanamh, bidh sinn a 'togail airson suimean cuideam. Gheibhear craobh domhainn lg N, anns na duilleagan bidh mac-samhail de chuideam, agus anns na nodan a tha air fhàgail - suimean pàirt, suas gu suim a h-uile cuideam aig freumh na craoibhe. An ath rud, bidh sinn a’ gineadh àireamh air thuaiream bho 0 gu suim a h-uile cuideam, lorg am mac-samhail i-th, thoir air falbh bhon chraoibh e, agus cuir a-rithist am modh-obrach gus na mac-samhail a tha air fhàgail a lorg. Leis an algairim seo, is e iom-fhillteachd togail craoibhe O(N), is e O(lg N) an iom-fhillteachd a bhith a’ lorg mac-samhail i-th agus ga thoirt air falbh bhon chraoibh), is e iom-fhillteachd taghadh K mac-samhail O(N + K). lg N) ~ O(N lg N).
Tha iom-fhillteachd log sreathach nas fheàrr na iom-fhillteachd ceithir-cheàrnach, gu sònraichte airson K.
Is e an algorithm seo Leabharlannan ClusterClient bhon phròiseact "". (An sin, tha a ’chraobh air a thogail ann an O (N lg N), ach chan eil seo a’ toirt buaidh air iom-fhillteachd deireannach an algairim.)
Tasc 2. Zebra
Bha e riatanach algairim a mholadh airson a bhith a’ rèiteachadh sgrìobhainnean gu h-èifeachdach mar chuimhneachan le raon neo-riaghailteach neo-chlàraichte:
Tha e mar dhleastanas air an sgioba agad stòr-dàta de sgrìobhainnean cuimhneachaidh a leasachadh. Bhiodh e na uallach obrach cumanta a bhith a’ taghadh prìomh sgrìobhainnean N air an òrdachadh le raon àireamhach neo-riaghailteach (neo-chlàraichte) bho chruinneachadh de mheud M (mar as trice N < 100 << M). Is e eallach obrach beagan nas cumanta a bhiodh ann a bhith a’ taghadh prìomh N às deidh a bhith a’ leum air na prìomh sgrìobhainnean S (S ~ N).
Mol algairim gus a leithid de cheistean a chuir an gnìomh gu h-èifeachdach. Dèan tuairmse air iom-fhillteachd àireamhachd a’ cleachdadh comharradh O mòr anns a’ chùis chuibheasach agus na suidheachaidhean as miosa.
Mion-sgrùdadh air an fhuasgladh (bhidio)
A’ tòiseachadh aig 34:50, dìreach 6 mionaidean:
Mion-sgrùdadh air an fhuasgladh (teacsa)
Fuasgladh uachdar: cuir a h-uile sgrìobhainn air dòigh (mar eisimpleir le ), an uairsin gabh sgrìobhainnean N+S. Anns a 'chùis seo, tha iom-fhillteachd an seòrsachaidh gu cuibheasach O (M lg M), aig a' char as miosa O (M2).
Tha e follaiseach gu bheil a bhith a’ rèiteach a h-uile sgrìobhainn M agus an uairsin a’ gabhail dìreach pàirt bheag dhiubh neo-èifeachdach. Gus nach tèid a h-uile sgrìobhainn a rèiteachadh, tha algorithm freagarrach , a thaghas N + S de na sgrìobhainnean a tha thu ag iarraidh (faodaidh iad a bhith air an rèiteachadh le algairim sam bith). Anns a 'chùis seo, lùghdaichidh an iom-fhillteachd gu O (M) gu cuibheasach, agus bidh a' chùis as miosa fhathast mar a tha e.
Ach, faodaidh tu a dhèanamh eadhon nas èifeachdaiche - cleachd an algairim . Anns a 'chùis seo, thèid a' chiad sgrìobhainnean N+S a chur ri min- no max-heap (a rèir an t-seòrsa stiùiridh), agus an uairsin tha gach ath sgrìobhainn air a choimeas ri freumh na craoibhe, anns a bheil an sgrìobhainn as ìsle no as àirde a th 'ann an-dràsta, agus thèid a chur ris a’ chraoibh ma tha sin riatanach. Anns a 'chùis seo, is e an iom-fhillteachd anns a' chùis as miosa, nuair a dh'fheumas tu an craobh ath-thogail gu cunbhalach, O (M lg M), is e an iom-fhillteachd gu cuibheasach O (M), mar a tha le quickselect.
Ach, tha e coltach gum bi sruthadh tiùrr nas èifeachdaiche leis gu bheil e comasach a’ mhòr-chuid de na sgrìobhainnean a chuir air falbh gun a bhith ag ath-thogail a’ charn às deidh aon choimeas ris an eileamaid bhunaiteach aige. Tha an leithid de sheòrsachadh air a chuir an gnìomh ann an stòr-dàta sgrìobhainnean cuimhne Zebra a chaidh a leasachadh agus a chleachdadh ann an Kontur.
Tasg 3. Malairt stàite
Bha e riatanach an algairim as èifeachdaiche a mholadh airson stàitean gluasadach:
Tha e mar dhleastanas air an sgioba agad uidheamachd iomlaid stàite sùbailte a leasachadh airson cruinneachadh sgaoilte de nodan N. Bu chòir staid an i-th nód a ghluasad chun (i + 1) -th nód, bu chòir staid an N-th nód a ghluasad chun chiad nód. Is e an aon obrachadh le taic an iomlaid stàite nuair a bhios dà nodan ag iomlaid an stàitean gu atamach. Tha fios gu bheil suaip stàite a’ toirt M milliseconds. Faodaidh gach nód pàirt a ghabhail ann an aon suaip stàite aig àm sònraichte sam bith.
Dè cho fada ’s a bheir e gus stàitean gach nodan a ghluasad ann am brabhsair?
Mion-sgrùdadh air an fhuasgladh (teacsa)
Fuasgladh uachdar: atharraich stàitean a 'chiad agus an dàrna eileamaid, an uairsin a' chiad agus an treas, an uairsin a 'chiad agus an ceathramh, agus mar sin air adhart. Às deidh gach iomlaid, bidh staid aon eileamaid anns an t-suidheachadh a tha thu ag iarraidh. Feumaidh tu atharrachadh O(N) a dhèanamh agus ùine O(N M) a chaitheamh.
Tha an ùine sreathach fada, gus an urrainn dhut staid nan eileamaidean iomlaid ann an càraidean: a’ chiad leis an dàrna fear, an treas fear leis a’ cheathramh, agus mar sin air adhart. Às deidh gach iomlaid stàite, bidh gach dàrna eileamaid san t-suidheachadh cheart. Feumaidh tu atharrachadh O(lg N) a dhèanamh agus ùine O(M lg N) a chaitheamh.
Ach, tha e comasach an gluasad a dhèanamh eadhon nas èifeachdaiche - chan ann ann an sreath, ach ann an ùine shìorraidh. Gus seo a dhèanamh, aig a 'chiad cheum, feumaidh tu iomlaid a dhèanamh air staid a' chiad eileamaid leis an fhear mu dheireadh, an dàrna fear leis an dàrna fear, agus mar sin air adhart. Bidh staid an eileamaid mu dheireadh san t-suidheachadh cheart. Agus a-nis feumaidh sinn staid an dàrna eileamaid atharrachadh leis an fhear mu dheireadh, an treas fear leis an dàrna fear, agus mar sin air adhart. Às deidh a’ chuairt seo de iomlaidean, bidh stàitean nan eileamaidean uile san t-suidheachadh cheart. Bidh O(2M) ~ O(1) ann uile gu lèir.
Cha chuir fuasgladh mar seo iongnadh air neach-matamataig a tha fhathast a’ cuimhneachadh gur e cuairteachadh dà cho-chothromachd aiseach a th’ ann an cuairteachadh. Air an t-slighe, tha e air a choitcheannachadh gu beag airson gluasad chan ann le aon, ach le dreuchdan K <N. (Sgrìobh anns na beachdan dè cho dìreach.)
An do chòrd tòimhseachain riut? A bheil thu eòlach air fuasglaidhean eile? Co-roinn anns na beachdan.
Agus seo cuid de cheanglaichean feumail aig a’ cheann thall:
- tuilleadh ionnsachadh mu dheidhinn ann an cumadh
- faic clàran taobh a-staigh mu dheidhinn siostaman sgaoilte
- coimhead air an t-sreath de òraidean bhidio»
- fo-sgrìobhadh don ar
Source: www.habr.com