Некалькі дзён таму здарылася . Рабяты з JUG.ru Group запрасілі спікераў мары (Леслі Лэмпарт! Кліф Клік! Марцін Клеппманн!) і прысвяцілі два дні размеркаваным сістэмам і вылічэнням. Контур быў адным з трох партнёраў канферэнцыі. Мы размаўлялі на стэндзе, расказвалі пра нашы размеркаваныя сховішчы, гулялі ў Бінга, вырашалі задачы.
Гэта пост з разборам задач на стэндзе Контуру ад аўтара іх тэксту. Хто быў на Гідры - гэта ваша нагода ўспомніць прыемныя ўражанні, хто не быў - шанец расцерці мазгі вялікі О-натацыяй.
Былі нават удзельнікі, якія разабралі фліпчарт на слайды, каб запісаць сваё рашэнне. Я не жартую - яны здалі на праверку вось такі пачак паперы:
Усяго было тры задачы:
- аб выбары рэплік па вагах для балансавання нагрузкі
- аб сартаванні вынікаў запыту да in-memory базы даных
- аб перадачы стану ў размеркаванай сістэме з кальцавой тапалогіяй
Задача 1. ClusterClient
Трэба было прапанаваць алгарытм эфектыўнага выбару K з N узважаных рэплік размеркаванай сістэмы:
Ваша каманда размяшчаецца з развіццём кліента library для масава распаўсюджанага cluster of N nodes. У дакуменце можна пагражаць трэк розных metadat, associated with nodes (eg, іх бланк, 4xx/5xx response rates, etc.) and assign floating point weights W1..WN to them. У адпаведнасці з выкананнем сапраўднай execution strategy, library павінен быць запушчаны да n nodes randomly-a change of being selected by resulted proportional to node's weight.
Вызначае алгарытм для select nodes efficiently. Зразумела, што яе камплектацыя захоўваецца вялікім аб'яўленнем.
Чаму ўсё на англійскай?
Таму што ў такім выглядзе з імі змагаліся ўдзельнікі канферэнцыі і таму што англійская была афіцыйнай мовай Гідры. Выглядалі задачы так:
Вазьміце паперу і аловак, падумайце, не спяшаецеся адразу адчыняць спойлеры 🙂
Разбор рашэння (відэа)
Пачатак у 5:53, усяго 4 хвіліны:
А вось як харчавалі сваё рашэнне тыя самыя хлопцы з фліпчартам:
Разбор рашэння (тэкст)
На паверхні ляжыць такое рашэнне: падсумаваць вагі ўсіх рэплік, згенераваць выпадковы лік ад 0 да сумы ўсіх шаляў, затым абраць такую i-рэпліку, што сума шаляў рэплік ад 0 да (i-1)-ой менш выпадковага ліку, а сума шаляў рэплік ад 0 да i-ай - больш за яго. Так атрымаецца абраць адну рэпліку, а каб абраць наступную, трэба паўтарыць усю працэдуру, не разглядаючы абраную рэпліку. З такім алгарытмам складанасць выбару адной рэплікі — O(N), складанасць выбару K рэплік — O(N·K) ~ O(N2).
Квадратычная складанасць - гэта дрэнна, аднак яе можна палепшыць. Для гэтага пабудуем для сум вагаў. Атрымаецца дрэва глыбінёй lg N, у лісці якога будуць вагі рэплік, а ў астатніх вузлах - частковыя сумы, аж да сумы ўсіх вагаў у корані дрэва. Далей генеруемы выпадковы лік ад 0 да сумы ўсіх шаляў, знаходзім i-ую рэпліку, выдаляны яе з дрэва і паўтараны працэдуру для пошуку пакінутых рэплік. З такім алгарытмам складанасць пабудовы дрэва - О(N), складанасць пошуку i-ай рэплікі і выдалення яе з дрэва - O(lg N), складанасць выбару K рэплік - O(N + K lg N) ~ O(N lg N) .
Лінейна-лагарыфмічная складанасць прыемней квадратычнай, асабліва для вялікіх K.
Менавіта гэты алгарытм бібліятэкі ClusterClient з праекта «». (Там дрэва будуецца за O(N lg N), але на выніковую складанасць алгарытму гэта не ўплывае.)
Задача 2. Zebra
Трэба было прапанаваць алгарытм эфектыўнага сартавання дакументаў у памяці па адвольным неіндэксаваным полі:
Ваша група месціцца з развіццем, выпрацаванай у мемуарным дакументам. У адзін workload можна будзе выйсці з верхняга N дакументаў аб'яўленых (неадпаведнай) нумеранай філіі ад зборкі памеру M (звычайна N < 100 << M). З вялікае нязграбным працоўным працоўным месцам трэба будзе выйсці з верхняга пасля скіпавання верхняга дакумента (S ~ N).
Вызначае алгарытм у ажыццяўленні такіх патрабаванняў эфектыўна. Выгадайце сваю кампанійную комплекснасць шляхам вялікіх абнаўленняў у памеры выпадку і вялікае значэнне сцэнараў.
Разбор рашэння (відэа)
Пачатак у 34:50, усяго 6 хвілін:
Разбор рашэння (тэкст)
Рашэнне на паверхні: адсартаваць усе дакументы (напрыклад, з дапамогай ), затым узяць N+S дакументаў. У такім выпадку складанасць сартавання ў сярэднім - O (M lg M), у горшым - O (M2).
Відавочна, што сартаваць усе M дакументаў, каб затым узяць толькі невялікую частку ад іх - неэфектыўна. Каб не сартаваць усе дакументы, падыдзе алгарытм , які абярэ N+S патрэбных дакументаў (іх можна будзе адсартаваць любым алгарытмам). У гэтым выпадку складанасць у сярэднім паменшыцца да O(M), а горшы выпадак застанецца тым жа.
Аднак, можна зрабіць яшчэ больш эфектыўна - скарыстацца алгарытмам . У гэтым выпадку першыя N+S дакументаў складаюцца ў min- ці max-heap (у залежнасці ад кірунку сартавання), а затым кожны наступны дакумент параўноўваецца з коранем дрэва, дзе ўтрымоўваецца мінімальны ці максімальны на бягучы момант дакумент, і пры неабходнасці дадаецца ў дрэва . У гэтым выпадку складанасць у горшым выпадку, калі прыйдзецца ўвесь час перабудоўваць дрэва - O(M lg M), складанасць у сярэднім - O(M), як і пры выкарыстанні quickselect.
Аднак heap streaming аказваецца эфектыўнейшым за кошт таго, што на практыцы большую частку дакументаў атрымліваецца адкінуць, не перабудоўваючы кучу, пасля адзінага параўнання з яе каранёвым элементам. Такое сартаванне рэалізавана ў дакументнай in-memory базе дадзеных Zebra, распрацаванай і выкарыстоўванай у Контуры.
Задача 3. State swaps
Трэба было прапанаваць самы эфектыўны алгарытм для зруху станаў:
Ваша каманда з'яўляецца пабудаваны з развіццём фанацкага дзяржаўнага абмену механізмам для мясцовага cluster of N nodes. У i-th node's state should be transferred to the (i+1)-th node, the N-th node's state should be transferred to the first node. Толькі падтрымлівае ажыццяўленне з'яўляецца State Swap, калі два цытаты атрымліваюць свае дзяржавы atomically. Гэта вядомы як тое, што сядзеў схапіць так M milliseconds. Увесь node з'яўляецца здольным да ўвагі ў цэлых штатных ліхтарах на працягу ўсяго данага моманту.
Які доўгі час гэта можа перавезці ўсе статкі ўсіх пазоў у cluster?
Разбор рашэння (тэкст)
Рашэнне на паверхні: абмяняць станы першага і другога элемента, затым першага і трэцяга, затым першага і чацвёртага і гэтак далей. Пасля кожнага абмену стан аднаго элемента будзе аказвацца на патрэбнай пазіцыі. Прыйдзецца зрабіць O(N) перастановак і выдаткаваць O(N·M) часу.
Лінейны час - гэта доўга, таму можна абменьваць станы элементаў парамі: першага з другім, трэцяга з чацвёртым і гэтак далей. Пасля кожнага абмену стану кожнага другога элемента будзе аказвацца на патрэбнай пазіцыі. Прыйдзецца зрабіць O(lg N) перастановак і выдаткаваць O(M lg N) часу.
Аднак, можна зрабіць зрух яшчэ больш эфектыўным – не за лінейны, а за канстантны час. Для гэтага на першым кроку трэба абмяняць стан першага элемента з апошнім, другога з перадапошнім і гэтак далей. Стан апошняга элемента апынецца на патрэбнай пазіцыі. А зараз трэба абмяняць стан другога элемента з апошнім, трэцяга з перадапошнім і гэтак далей. Пасля гэтага раўнда абменаў стану ўсіх элементаў апынуцца на патрэбнай пазіцыі. Усяго будзе зроблена O(2M) ~ O(1) перастановак.
Такое рашэнне зусім не здзівіць матэматыка, які яшчэ памятае, што паварот - гэта кампазіцыя двух восевых сіметрый. Дарэчы, яно трывіяльна абагульняецца для зруху не на адну, а на K<N пазіцый. (Напішыце ў каментарах, як менавіта.)
Спадабаліся задачы? Ведаеце іншыя рашэнні? Дзяліцеся ў каментарах.
А вось некалькі карысных спасылак напрыканцы:
- даведайцеся больш пра у Контуры
- паглядзіце запісы ўнутраных аб размеркаваных сістэмах
- паглядзіце цыкл відэалекцый «»
- падпішыцеся на наш
Крыніца: habr.com