[devel] Параллельная сборочница. Алгоритмы.

Пт Фев 16 01:33:20 MSK 2018

Господа!

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

Сборочница и сейчас тормозит, а с учетом
скорого включения arm ее скорость еще упадет.

Хочу вынести на обсуждение, как можно без вложений в железо
добиться существенного увеличения скорости работы
нашей сборочницы путем оптимизации ее алгоритмов.

Итак, 
Параллельная сборочница.

----
Обозначения.
Tb (build time) - время, потраченное на сборку 
Tt (testing time) - время, потраченное на тестирование
Tm (merge time) - время, потраченное на интеграцию в репозиторий.

Однопоточная сборочница.

По порядку транзакций собираем пакеты, проверяем, сливаем в репозиторий.
По дизайну производительность такой сборочницы ограничена
1/(среднее(Tb+Tt)+Tm) транзакций за единицу времени.
Далее ускорить ее могут только вложения в железо, дающие diminishing
return на затраченные суммы.

Сборочница с параллельной сборкой и последовательной интеграцией.

Пример реализации - girar.
Если у нас много потоков выполнения, сборку и тестирование (часть) можно
вынести в параллельные потоки выполнения.
Соответственно, к окончанию интеграции одной транзакции уже должна
найтись собранная и проверенная другая транзакция, соответственно,
масксимальная скорость работы такой сборочницы 1/Tm.

Отсюда сразу ряд рецептов как можно ускорить наш girar --
выбросить из Tm (merge time) все лишнее.

* Вынести все тесты в сборочные процессы.

некоторые из них придется повторить на этапе merge,
чтобы обеспечить целостность репозитория,
но раз они будут выполнены повторно на той же транзакции,
то существенную часть данных для тестов можно закешировать в
сборочно-тестировочных потоках выполнения и повторно использовать,
чтобы не затягивать Tm

* Выбросить планировщик в отдельный процесс выполнения.
Пусть берет AVAITING и раздает сборочным потокам.
а сборочно-тестировочные потоки пусть переводят транзакцию
либо в статус FAILED, либо в статус BUILT(TESTED?)
(добавить статус).
А процесс, занятый выполнением мержа, будет брать из очереди
транзакции в статусе BUILT(TESTED?) и мержить.

* Выбросить из мержа все тесты, не связанные с поддержанием
  целостности репозитория.
Предлагаю оставить
** (кешированный) тест на наследование
** (кешированный) тест на символы в бинарниках
** тест на unmets

Все это может ускорить производительность в несколько раз.

Однако все это паллатив.
Из Tm (merge time) не выкинуть перегенерацию индексов и проверку на unmets,
которые в зависимости от железа занимают 20-40 сек.
что дает верхний теоретический потолок производительности
сборочницы с последовательной интеграцией
в 2000-3000 транзакций в сутки.
По сравнению с текущими (500?) транзакций в сутки
это хорошо, тем, что и в старой схеме есть куда расти,

однако за счет смены алгоритма работы сборочницы можно
добиться гораздо большего.

Параллельная сборочница.

Прототип параллельной сборочницы я реализовал для себя в autorepo-scripts.

Какой основной недостаток сборочницы с последовательной интеграцией?
Ее скорость принудительно ограничена скоростью шага интеграции.
Соответственно, она плохо распараллеливается. Добавляя аппаратный
ресурс для параллельных сборочно-тестировочных процессов (ПСБП)
выше определенного числа, мы не получим прирост в скорости.

В сегодняшнем girar лишние ПСБП либо простаивают, либо по нескольку раз
пересобирают транзакцию, пока наконец подойдет
ее очередь для интеграции. 
В оптимизированном рецептами выше girar при увеличении ПСБП
лишние ПСБП только простаивают.
Транзакции быстро пройдут фазы сборки и тестирования,
но явно встанут в очередь на интеграцию.

Сейчас в процессорах ядер как грязи. Как это использовать?
Чтобы не создавать пробку для ПСБП, мерж тоже нужно
делать параллельно.
Другими словами, не интегрировать из очереди на мерж
по одной транзакции,
а объединять все транзакции, накопившиеся к этому времени в очереди на
мерж, в одну мега-транзакцию, которую и пытаться интегрировать.
Дополнительная сложность здесь в алгоритме обработке ситуации, когда
мерж мега-транзакции не удался, но там тоже ничего заумного (см. далее).

Преимущество же --- полностью загруженные ПСБП и почти линейная
масштабируемость на независимых транзакциях.
Масксимальная скорость работы такой сборочницы уже не 1/Tm,
а пропорциональна (количество ПСБП)/Tm.

К примеру, ту же мегатранзакцию на удаление python*setuptools-tests,
которую наш girar обрабатывал трое суток,
girar на 128 ядрах (сервер на 4 процессора по 32 ядра) обработал бы
за 15 минут,
а на 256 ядрах --- еще быстрее, но, естественно, не быстрее, чем
сборка и тестирвание самого медленного пакета из мегатранзакции.
Я уже писал, что на altair на 32 ядрах удавалось получить на
прототипе скорость в 50.000 транзакций в сутки.

Вот что дает разница в алгоритмах на том же железе.

Алгоритм обработки ситуации, когда
мерж мега-транзакции не удался, тоже не так сложен.
Я предполагаю, что мы уже выбросили из мержа все тесты,
не связанные с поддержанием целостности репозитория.
Я предлагал оставить
* тест на наследование
* тест на символы в бинарниках
* тест на unmets

исключение по тесту на наследование просто,
там кто первый встал, того и тапки, остальные транзакции в FAILED.
с тестом на unmets и тестом на символы в бинарниках есть два пути
(можно совместить).
Либо генерировать в ПСБП доп. кеши по транзакциям,
по которым разбирать, какие транзакции вызвали проблемы,
и отправлять их на пересборку (желательно по итогам
прописывать зависимости (аналог task deps)
еще желательно, чтобы планировщик FAIL'ил циклические зависимости)

либо (или как fallback)
искать сбойную транзакцию методом половинного деления:

Накопилось в очереди на мерж от ПСБП 128 транзакций -
не получилось смержить 128 -- мержим 64, 32, 16 ...
опять же метод половинного деления можно распараллелить,
если под рукой много ядер.
Сразу пускаем log_2(N)+1 процессов
(в примере --- на мерж уйдет 8 ядер -- пытаемся смержить
128, 64, 32, 16, 8, 4, 2, 1 транзакцию, и называем
следующим репозиторием самый крупный мерж из удавшихся).

К слову, поскольку пакеты перед мега-мержем проходят независимую
проверку в ПСБП, то чтобы мега-мерж не сошелся со второй попытки
(после выноса unmets), надо постараться.

В autoimports я с таким сталкивался раза 2 или 3 за всю жизнь.
Так что можно ожидать, что очередей в incoming больше ек будет,
кроме последовательностей, вызванных необходимостью порядка сборки.

-- 

I V