Преди няколко дни се проведе конференция Hydra. Младежите от JUG.ru Group поканиха мечтаните лектори (Лесли Лампърт! Клиф Клик! Мартин Клеппман!) и посветиха два дни на разпределени системи и изчисления. Контур беше един от тримата партньори на конференцията. Общувахме на щанда, разказвахме за нашите разпределени хранилища, играхме бинго, решавахме задачи.

Това е пост с разбора на задачите на щанда на Контура от автора на текста. Който е бил на Гидра — това е вашата причина да си припомните приятните впечатления, а който не е бил — шанс да раздвижите мозъка си. big O-нотация.

Имаше дори участници, които разобрали флипчарта на слайдове, за да запишат решението си. Не се шегувам — те подадоха на проверка такава купчина хартия:

Имаше общо три задачи:

за избора на реплики по теглата за балансиране на натоварването
за сортиране на резултатите от запитване към in-memory база данни
за предаване на състоянието в разпределена система с кръгова топология

Задача 1. ClusterClient

Трябваше да се предложи алгоритъм за ефективен избор на K от N тежести реплики на разпределената система:

Вашият екип е натоварен с разработването на клиентска библиотека за масивен разпределен клъстер от N възела. Библиотеката ще следи различни метаданни, свързани с възлите (например, техните латентности, 4xx/5xx проценти на отговор и т.н.) и ще присвоява плаващи точки тегла W1..WN. За да подкрепи стратегията за паралелно изпълнение, библиотеката трябва да може да избере K от N възли на случаен принцип — вероятността да бъде избран трябва да е пропорционална на теглото на възела.
Предложете алгоритъм за ефективно селектиране на възлите. Оценете изчислителната му сложност, използвайки big O нотация.

Защо всичко е на английски?

Защото в такъв вид участниците на конференцията се сблъскваха с тях и защото английският беше официалният език на Гидра. Задачите изглеждаха така:

Вземете хартия и молив, помислете, не се втурвайте веднага да отваряте спойлерите 🙂

Разбор на решението (видео)

Начало в 5:53, общо 4 минути:

А ето как представиха решението си онези същите младежи с флипчарта:

Разбор на решението (текст)

На повърхността лежи такова решение: да се съберат теглата на всички реплики, да се генерира случайно число от 0 до сумата на всички тегла, след това да се избере такава i-реплика, че сумата на теглата на репликите от 0 до (i-1)-ата да е по-малка от случайното число, а сумата на теглата на репликите от 0 до i-ата — по-голяма от него. Така ще се избере една реплика, а за да се избере следващата, трябва да се повтори цялата процедура, без да се взима предвид избраната реплика. С такъв алгоритъм сложността на избора на една реплика е O(N), сложността на избора на K реплики е O(N·K) ~ O(N^2).

Квадратичната сложност е лошо, но може да бъде подобрена. За целта ще построим дърво отрязъци за сумите на теглата. Получава се дърво с дълбочина 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. Zebra

Трябваше да предложим алгоритъм за ефективна сортировка на документи в паметта по произволно неиндексирано поле:

Вашият екип е натоварен с разработването на шардирна документна база данни в паметта. Обичайна натовареност би била да се изберат най-добрите N документа, сортирани по произволно (неиндексирано) числово поле от колекция с размер M (обикновено N < 100 << M). По-малко често срещаната натовареност би била да се изберат най-добрите N след пропускането на топ S документа (S ~ N).
Предложете алгоритъм за ефективно изпълнение на такива заявки. Оценете неговата изчислителна сложност, като използвате голяма O нотация в средния случай и най-лошия случай.

Разбор на решението (видео)

Начало в 34:50, общо 6 минути:

Разбор на решението (текст)

Решение на повърхността: да се сортират всички документи (например, с помощта на quicksort), след това да се вземат N+S документа. В такъв случай сложността на сортиране в средния случай е O(M lg M), в най-лошия случай — O(M2).

Очевидно е, че да сортираме всички M документа, за да вземем само малка част от тях - е неефективно. За да не сортираме всички документи, подходящ е алгоритъмът quickselect, който ще избере N+S необходимите документа (те могат да бъдат сортирани с произволен алгоритъм). В този случай сложността в средния случай ще се намали до O(M), а най-лошият случай ще остане същият.

Въпреки това, може да се направи още по-ефективно — да се използва алгоритмът binary heap streaming. В този случай първите N+S документа се сглобяват в min- или max-купчина (в зависимост от посоката на сортиране), а след това всеки следващ документ се сравнява с корена на дървото, където се намира минималният или максималният документ в момента, и при необходимост се добавя в дървото. В такъв случай сложността в най-лошия случай, когато се налага постоянно да се преустройва дървото — O(M lg M), сложността в средния случай — O(M), както при използването на quickselect.

Въпреки това, потокът от купчини се оказва по-ефективен, тъй като в практиката голямата част от документите могат да бъдат отхвърлени, без да се пренарежда купчината, след единствено сравнение с нейния корен. Такова сортиране е реализирано в документната in-memory база данни Zebra, разработена и използвана в Контур.

Задача 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 позиции. (Напишете в коментарите как точно.)

Харесаха ли ви задачите? Знаете ли други решения? Споделете в коментарите.

А ето и няколко полезни връзки за край: