Разбор задач с конференции Hydra — балансировка нагрузки и in-memory хранилища

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


    Это пост с разбором задач на стенде Контура от автора их текста. Кто был на Гидре — это ваш повод вспомнить приятные впечатления, кто не был — шанс размять мозги big O-нотацией.


    Были даже участники, которые разобрали флипчарт на слайды, чтобы записать своё решение. Я не шучу — они сдали на проверку вот такую пачку бумаги:



    Всего было три задачи:


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

    Задача 1. ClusterClient


    Нужно было предложить алгоритм эффективного выбора K из N взвешенных реплик распределённой системы:


    Your team is tasked with developing a client library for a massively distributed cluster of N nodes. The library would keep track of various metadata associated with nodes (e.g., their latencies, 4xx/5xx response rates, etc.) and 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 to select nodes efficiently. Estimate its computational complexity using big O notation.

    Почему всё на английском?

    Потому что в таком виде с ними боролись участники конференции и потому что английский был официальным языком Гидры. Выглядели задачки так:



    Возьмите бумагу и карандаш, подумайте, не торопитесь сразу открывать спойлеры :)


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

    Начало в 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 из проекта «Восток».


    Задача 2. Zebra


    Нужно было предложить алгоритм эффективной сортировки документов в памяти по произвольному неиндексированному полю:


    Your team is tasked with developing a sharded in-memory document database. A common workload would be to select top N documents sorted by an arbitrary (non-indexed) numeric field from a collection of size M (usually N < 100 << M). A slightly less common workload would be to select top N after skipping top S documents (S ~ N).

    Propose an algorithm to execute such queries efficiently. Estimate its computational complexity using big O notation in the average case and the worst case scenarios.

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

    Начало в 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-heap (в зависимости от направления сортировки), а затем каждый следующий документ сравнивается с корнем дерева, где содержится минимальный или максимальный на текущий момент документ, и при необходимости добавляется в дерево. В этом случае сложность в худшем случае, когда придётся постоянно перестраивать дерево — O(M lg (N + S)), сложность в среднем — O(M), как и при использовании quickselect.


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


    Задача 3. State swaps


    Нужно было предложить самый эффективный алгоритм для сдвига состояний:


    Your team is tasked with developing a fancy state exchange mechanism for a distributed 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. The only supported operation is the state swap when two nodes exchange their states atomically. It is known that a state swap takes M milliseconds. Every node is able to participate in a single state swap at any given moment.

    How long does it take to transfer the states of all nodes in a cluster?

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

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



    Линейное время — это долго, поэтому можно обменивать состояния элементов попарно: первого со вторым, третьего с четвёртым и так далее. После каждого обмена состояния каждого второго элемента будет оказываться на нужной позиции. Придётся сделать O(lg N) перестановок и потратить O(M lg N) времени.



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



    Такое решение совершенно не удивит математика, который ещё помнит, что поворот — это композиция двух осевых симметрий. Кстати, оно тривиально обобщается для сдвига не на одну, а на K < N позиций. (Напишите в комментариях, как именно.)


    Понравились задачки? Знаете другие решения? Делитесь в комментариях.


    А вот несколько полезных ссылок напоследок:


    • +25
    • 3,4k
    • 9
    Контур
    116,68
    Делаем веб-сервисы для бизнеса
    Поделиться публикацией

    Комментарии 9

      0
      С таким алгоритмом сложность выбора одной реплики — O(N), сложность выбора K реплик — O(N + K lg N) ~ O(N lg N)..


      Привет! Спасибо за статью.

      А можете, пожалуйста, рассказать, как у вас получилась такая оценка? Не понял перехода от O(N + K lg N) к O(N lg N). при условии произвольности K.
        0

        Привет!


        K <= N, что поэтому подставляем N вместо K. (N lg N) > N, поэтому оставляем под O большее слагаемое.


        У меня есть неплохая ссылка, кстати :)

        +1
        По второй задаче.
        В этом случае сложность в худшем случае, когда придётся постоянно перестраивать дерево — O(N lg N), сложность в среднем — O(N), как и при использовании quickselect.

        Придется пройтись по всем M документам, т.ч. сложность в среднем будет — O(M).
          0

          Конечно, здесь везде нужна M! Исправил опечатки в тексте. Спасибо!

          +2

          По первой задаче вопрос. Можете ли как-то доказать, что вероятности выбора каждой реплики будут пропорциональны w[i]? Мне кажется, ваше решение не работает совсем.


          Допустим n=3, k=2, w={1, 2, 3}.
          Тогда ваше решение с вероятностью 1/6 возьмет 1. Потом с 2/5 возьмет 2 или с 3/5 возьмет 3.
          Или же с вероятностью 1/3 сначала возьмет реплику 2, потом с 1/4 — 1 или с 3/4 — 3.
          Последний вариант с вероятностью 1/2 — 3, потом 1/3 — 1 или 2/3 — 2.


          Если все перемножить, то 6 вариантов выбра двух реплик из трех будут:
          {1, 2} — вероятность 1/15, {1,3} — 1/10, {2, 1} — 1/12, {2,3} — 1/4, {3,1} — 1/6 и {3,2} — 1/3.
          Или если забить на порядок реплик:
          {1, 2} — 9/60
          {1, 3} — 16/60
          {2, 3} — 35/60


          Т.е. реплика 3 будет взята в 51/60 случаев, 2 в 44/60, а 1 в 25/60. Соотношения 1:2:3 тут нет.


          Или совсем вырожденный пример: n=k, а веса не одинаковые. Тут решения, вообще говоря, нет. Ведь единственный вариант — это взять все реплики, и тогда каждая будет взята в 100% случаев. А если веса разные, то и вероятности не пропорциональны.


          Или я не понял условие?

            0
            Можете ли как-то доказать, что вероятности выбора каждой реплики будут пропорциональны w[i]?

            Илья, спасибо за комментарий! В рамках данной задачи я имел в виду, что для трёх реплик с весами {1; 2; 3} соотношение 1:2:3 будет выполняться для вероятности выбрать каждую из них в качестве первой, а не для вероятности, что реплика содержится в кортеже длины K.


            Или я не понял условие?

            Скорее, это я не смог сформулировать условие так, чтобы его можно было понять только безошибочно :)

            +1

            Про первую задачу опять:


            Именно этот алгоритм реализован в коде библиотеки ClusterClient из проекта «Восток». (Там дерево строится за O(N lg N), но на итоговую сложность алгоритма это не влияет.)

            Я посмотрел код, там решается другая задача: Случайно перемешать реплики так, что одна реплика встречается раньше другой с вероятностью, пропорциональной весам. При этом всегда берутся все реплики, меняется лишь порядок:


            Комментарий в коде.
                /// <para>Represents a probabilistic ordering which orders replicas based on their weights.</para>
                /// <para>A weight is a number in customizable <c>[min-weight; max-weight]</c> range where <c>min-weight >= 0</c>. </para>
                /// <para>Weight for each replica is calculated by taking a constant initial value and modifying it with a chain of <see cref="IReplicaWeightModifier"/>s. Range limits are enforced after applying each modifier.</para>
                /// <para>Weights are used to compute replica selection probabilities. A replica with weight = <c>1.0</c> is twice more likely to come first than a replica with weight = <c>0.5</c>.</para>
            /// <para>If all replicas have same weight, the ordering essentially becomes random.</para>

            Тут решение с деревом отрезков и итеративным выбором реплики отлично работает.


            В посте же задача — выбрать k реплик из n. При ее составлении, видимо, кто-то предположил, что вероятность войти в первые k у каждой реплики пропорциональна ее весу. Что не правда (опять же: n=k, все веса разные. Задача в посте вообще решения не имеет с такими входными данными). Или кто-то неверно вспомнил условие задачи на конференции или при написании поста.


            Я так понимаю, это не было какое-то официальное соревнование с призами и грамотами, а просто обсуждение задачек для интереса? В противном случае, результаты конкурса стоит отменить и принести извинения участникам.


            А задачу в посте было бы хорошо изменить или удалить совсем в любом случае. Потому что в таком виде я пока вижу только одно решение — назначить переменными вероятности каждого сочетания из k реплик, задать задачу линейного программирования, а потом прогнать симплекс метод до выбора первого не-фиктивного базиса. Потом выдать одну из n конфигураций с заданной вероятностью. Будет это все не то O(N^4), не то O(N^5).

              0
              Я посмотрел код, там решается другая задача

              Это не совсем так. Надо обратить внимание на метод SelectReplicaFromTree, который реализует решение с деревом отрезков и итеративным выбором, а не на весь класс WeighedReplicaOrdering. (Я сделал ссылку в посте на конкретный метод, чтобы это было очевиднее.)


              Я так понимаю, это не было какое-то официальное соревнование с призами и грамотами, а просто обсуждение задачек для интереса?

              Именно так!


              А задачу в посте было бы хорошо изменить… Потому что в таком виде я пока вижу только одно решение… Будет это все не то O(N^4), не то O(N^5).

              Это было бы очень непрактично — боролись с квадратом, а напоролись на четвёртую степень :)


              Как насчёт такой правки к условию? Меняем «a chance of being selected should be proportional to a node’s weight» на «a chance of being selected at every round of selection should be proportional to a node’s weight».

                +1

                Да, такая поправка почти подходит, надо только определить, что это за раунды. И надо описать, что пропорционально весу из оставшихся невзятых пока реплик. Но тут задача уже становится фактически описанием нужного алгоритма. Оригинальная задача с случайной сортировкой гораздо красивее.

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое