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

Це пост із розбором завдань на стенді Контуру від автора їхнього тексту. Хто був на Гідрі – це ваш привід згадати приємні враження, хто не був – шанс розім'яти мізки. великий О-нотацією.

Були навіть учасники, які розібрали фліпчарт на слайди, щоби записати своє рішення. Я не жартую - вони здали на перевірку ось таку пачку паперу:

Усього було три завдання:

• про вибір реплік за вагами для балансування навантаження
• про сортування результатів запиту до in-memory бази даних
• про передачу стану в розподіленій системі з кільцевою топологією

Завдання 1. ClusterClient

Потрібно було запропонувати алгоритм ефективного вибору K з N виважених реплік розподіленої системи:

Ваша команда є розповсюдженою з розробкою клієнта library for massively distributed cluster of N nodes. Бібліотека повинна мати клопоту з різних metadata поєднана з nodes (eg, їхніх атестатів, 4xx/5xx response rates, etc.) і assign floating point weights W1..WN to them. In order to support the concurrent execution strategy, the library should be able to pick K of N nodes randomly—a chance of being selected should be proportional to a node's weight.

Propose an algorithm до select nodes efficiently. Використовується його комп'ютерна комплексність, використовуючи велику O notation.

Чому все англійською?

Тому що у такому вигляді з ними боролися учасники конференції і тому, що англійська була офіційною мовою Гідри. Виглядали завдання так:

Візьміть папір та олівець, подумайте, не поспішайте одразу відкривати спойлери 🙂

Розбір рішення (відео)

Початок о 5:53, всього 4 хвилини:

А ось як харчували своє рішення ті самі хлопці з фліпчартом:

Розбір рішення (текст)

На поверхні лежить таке рішення: підсумувати ваги всіх реплік, згенерувати випадкове число від 0 до суми всіх ваг, потім вибрати таку i-репліку, що сума ваг реплік від 0 до (i-1) менша від випадкового числа, а сума ваг реплік від 0 до i-ої - більше за нього. Так вдасться вибрати одну репліку, а щоб вибрати наступну, потрібно повторити всю процедуру, не розглядаючи вибрану репліку. З таким алгоритмом складність вибору однієї репліки — O(N), складність вибору K реплік — O(NK) ~ 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 повинен бути вибраний top N documents sorted by arbitrary (non-indexed) numerical field from collection of size M (usually N < 100 << M). А легенько загальний загальний робочий час буде вибрано top N після skipping top S documents (S ~ N).

Propose an algorithm до execute таких дій ефективно. Прихильність його комп'ютерної комплексності використовує велику O notation в оverage case і worst case scenarios.

Розбір рішення (відео)

Початок о 34:50, всього 6 хвилин:

Розбір рішення (текст)

Рішення на поверхні: відсортувати всі документи (наприклад, за допомогою швидкий), потім взяти N+S документів. У такому разі складність сортування в середньому - O(M lg M), у гіршому - O(M2).

Очевидно, що сортувати всі M документи, щоб потім узяти лише невелику частину від них — неефективно. Щоб не сортувати всі документи, підійде алгоритм швидкий вибір, Який обере N+S потрібних документів (їх можна буде відсортувати будь-яким алгоритмом). У цьому випадку складність у середньому зменшиться до O(M), а найгірший випадок залишиться тим самим.

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

Однак heap streaming виявляється ефективнішим за рахунок того, що на практиці більшу частину документів виходить відкинути, не перебудовуючи купу, після єдиного порівняння з її кореневим елементом. Таке сортування реалізовано в документній in-memory базі даних Zebra, розробленої та використовуваної в Контурі.

Завдання 3. State swaps

Потрібно було запропонувати найефективніший алгоритм зсуву станів:

Ваша команда є розповсюдженою з розробкою фанівної системи обміну механізмом для розповсюдженого cluster of N nodes. The 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. Лише підтримувана операція є державою звільнення, коли два коди обмінюються своїми державами atomically. Це славиться те, що держава звільняється з тими, що milliseconds. Більшість повідомлень є можливим для того, щоб отримувати участь в одному штаті звільнитися на будь-який час.

Як тривалий час це перевищує стани всіх номерів в cluster?

Розбір рішення (текст)

Рішення на поверхні: обміняти стани першого та другого елемента, потім першого та третього, потім першого та четвертого тощо. Після кожного обміну стан одного елемента виявлятиметься на потрібній позиції. Прийде зробити O(N) перестановок і витратити O(N·M) часу.

Лінійний час - це довго, тому можна обмінювати стани елементів попарно: першого з другим, третього з четвертим і таке інше. Після кожного обміну стану кожного другого елемента виявлятиметься на потрібній позиції. Прийде зробити O(lg N) перестановок і витратити O(M lg N) часу.

Однак, можна зробити зрушення ще ефективнішим — не за лінійний, а за константний час. Для цього на першому кроці потрібно обміняти стан першого елемента з останнім, другого з передостаннім і таке інше. Стан останнього елемента опиниться на потрібній позиції. А тепер потрібно обміняти стан другого елемента з останнім, третього з передостаннім і таке інше. Після цього раунду обміну стану всіх елементів виявляться на потрібній позиції. Усього буде зроблено O(2M) ~ O(1) перестановок.

Таке рішення зовсім не здивує математика, який пам'ятає, що поворот — це композиція двох осьових симетрій. До речі, воно тривіально узагальнюється для зсуву не одну, але в K < N позицій. (Напишіть у коментарях, як саме.)

Сподобалися завдання? Чи знаєте інші рішення? Діліться у коментарях.

А ось кілька корисних посилань наостанок:

• дізнайтесь більше про інфраструктурної розробки у Контурі
• подивіться записи внутрішніх летучок з доповідями про розподілені системи
• перегляньте цикл відеолекцій «Незвичайні алгоритми для звичайних людей»
• підпишіться на наш канал у Телеграмі

Джерело: habr.com