Случи се преди няколко дни . Момчетата от групата JUG.ru поканиха лектори-мечта (Лесли Лампорт! Клиф Клик! Мартин Клепман!) и посветиха два дни на разпределените системи и компютрите. Контур беше един от тримата партньори на конференцията. Говорихме на щанда, говорихме за нашето разпределено хранилище, играехме бинго и решавахме пъзели.
Това е публикация с анализ на задачите на щанда на Kontur от автора на техния текст. Който е бил на Hydra - това е причината да си спомните приятното преживяване, който не е бил - шанс да разтегнете мозъка си голямо О- нотация.
Имаше дори участници, които разглобиха флипчарта на слайдове, за да запишат решението си. Не се шегувам - предадоха този тест хартия за проверка:
Имаше общо три задачи:
- относно избора на реплики по тегла за балансиране на натоварването
- относно сортирането на резултатите от заявката спрямо база данни в паметта
- върху трансфер на състояние в разпределена система с пръстеновидна топология
Задача 1. ClusterClient
Беше необходимо да се предложи алгоритъм за ефективен избор на K от N претеглени реплики на разпределена система:
Вашият екип има за задача да разработи клиентска библиотека за масово разпределен клъстер от N възли. Библиотеката ще следи различни метаданни, свързани с възли (напр. техните латентности, 4xx/5xx проценти на отговор и т.н.) и ще им присвоява тегла с плаваща запетая W1..WN. За да поддържа стратегията за едновременно изпълнение, библиотеката трябва да може произволно да избира K от N възли – шансът да бъде избран трябва да бъде пропорционален на теглото на възела.
Предложете алгоритъм за ефективен избор на възли. Оценете неговата изчислителна сложност, като използвате нотация с голямо O.
Защо всичко е на английски?
Защото в тази форма участниците в конференцията се биеха с тях и защото английският беше официалният език на Хидра. Задачите изглеждаха така:
Вземете хартия и молив, помислете, не бързайте да отваряте спойлери веднага 🙂
Анализ на решението (видео)
От 5:53, само 4 минути:
И ето как момчетата с флипчарта представиха своето решение:
Анализ на решението (текст)
Следното решение лежи на повърхността: сумирайте теглата на всички реплики, генерирайте произволно число от 0 до сумата от всички тегла, след това изберете i-реплика, така че сумата от теглата на реплики от 0 до (i-1)th е по-малко от произволно число, а сумата от теглата на репликите от 0 до i-та - по-голяма от него. Така ще бъде възможно да изберете една реплика, а за да изберете следващата, трябва да повторите цялата процедура, без да вземете предвид избраната реплика. С такъв алгоритъм сложността на избора на една реплика е O(N), сложността на избора на K реплики е O(N K) ~ O(N2).
Квадратната сложност е лоша, но може да се подобри. За да направим това, ние ще изградим за суми от тегла. Ще се получи дърво с дълбочина lg N, в чиито листа ще има репликни тегла, а в останалите възли - частични суми, до сумата от всички тегла в корена на дървото. След това генерираме произволно число от 0 до сумата от всички тегла, намираме i-тата реплика, премахваме я от дървото и повтаряме процедурата, за да намерим останалите реплики. С този алгоритъм сложността на изграждането на дърво е O(N), сложността на намирането на i-тото копие и премахването му от дървото е O(lg N), сложността на избора на K реплики е O(N + K lg N) ~ O(N lg N) .
Сложността на линейния логаритъм е по-добра от квадратичната сложност, особено за големи K.
Това е този алгоритъм ClusterClient библиотеки от проекта "". (Там дървото е изградено в O(N lg N), но това не влияе на крайната сложност на алгоритъма.)
Задача 2. Зебра
Беше необходимо да се предложи алгоритъм за ефективно сортиране на документи в паметта по произволно неиндексирано поле:
Вашият екип е натоварен със задачата да разработи шардинг база данни с документи в паметта. Обичайно работно натоварване би било да се изберат първите N документа, сортирани по произволно (неиндексирано) числово поле от колекция с размер M (обикновено N < 100 << M). Малко по-рядко работно натоварване би било да изберете най-горния N след пропускане на горния S документи (S ~ N).
Предложете алгоритъм за ефективно изпълнение на такива заявки. Оценете неговата изчислителна сложност, като използвате нотация с голямо O в средния случай и в най-лошия случай.
Анализ на решението (видео)
От 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), както при бързия избор.
Поточното предаване на купчина обаче се оказва по-ефективно поради факта, че на практика повечето от документите могат да бъдат отхвърлени без повторно изграждане на купчината след еднократно сравнение с основния елемент. Такова сортиране е реализирано в базата данни за документи Zebra in-memory, разработена и използвана в Kontur.
Задача 3. Размени на държави
Беше необходимо да се предложи най-ефективният алгоритъм за изместване на състоянията:
Вашият екип има за задача да разработи фантастичен механизъм за обмен на състояние за разпределен клъстер от N възли. Състоянието на i-тия възел трябва да бъде прехвърлено към (i+1)-ия възел, състоянието на N-тия възел трябва да бъде прехвърлено към първия възел. Единствената поддържана операция е размяната на състоянията, когато два възела обменят своите състояния атомарно. Известно е, че размяната на състояние отнема M милисекунди. Всеки възел може да участва в единичен суап на състояние във всеки даден момент.
Колко време отнема прехвърлянето на състоянията на всички възли в клъстер?
Анализ на решението (текст)
Повърхностно решение: разменете състоянията на първия и втория елемент, след това на първия и третия, след това на първия и четвъртия и т.н. След всяка смяна състоянието на един елемент ще бъде в желаната позиция. Трябва да направите O(N) пермутации и да отделите O(N M) време.
Линейното време е дълго, така че можете да обменяте състоянията на елементите по двойки: първият с втория, третият с четвъртия и т.н. След всеки обмен на състояние, всеки втори елемент ще бъде в правилната позиция. Трябва да направите O(lg N) пермутации и да отделите O(M lg N) време.
Възможно е обаче смяната да бъде още по-ефективна - не в линейно, а в постоянно време. За да направите това, на първата стъпка трябва да размените състоянието на първия елемент с последния, на втория с предпоследния и т.н. Състоянието на последния елемент ще бъде в правилната позиция. И сега трябва да разменим състоянието на втория елемент с последния, на третия с предпоследния и т.н. След този кръг на обмен, състоянията на всички елементи ще бъдат в правилната позиция. Общо ще има O(2M) ~ O(1) пермутации.
Подобно решение изобщо няма да изненада математик, който все още помни, че ротацията е композиция от две аксиални симетрии. Между другото, тривиално се обобщава за смяна не с една, а с K < N позиции. (Напишете в коментарите как точно.)
Харесахте ли пъзелите? Знаете ли други решения? Споделете в коментарите.
И накрая има няколко полезни връзки:
- научете повече за в контур
- вижте записите на вътрешните относно разпределените системи
- гледайте поредицата от видео лекции»
- абонирайте се за нашите
Източник: www.habr.com