01.09.2020 22:17:56 |
Автор: 
Давайте посмотрим, какие решения есть у этой задачи.
Распределение объектов по мощности
Чтобы не углубляться в неинтересные абстракции, будем рассматривать на примере конкретной задачи мониторинга. Соотнести предлагаемые методики на свои конкретные задачи, уверен, вы сможете самостоятельно.
Равномощные объекты мониторинга
В качестве примера можно привести наши коллекторы метрик для Zabbix, которые исторически имеют с коллекторами логов PostgreSQL общую архитектуру.
И правда, каждый объект мониторинга (хост) генерирует для zabbix практически стабильно один и тот набор метрик с одной и той же частотой все время:
Как видно на графике, разница между min-max значениями количества генерируемых метрик не превышает 15%. Поэтому мы можем считать все объекты равными в одинаковых попугаях.
Сильный дисбаланс между объектами
В отличие от предыдущей модели, для коллекторов логов наблюдаемые хосты совсем не являются однородными.
Например, база рабочего один хост может генерировать в лог миллион планов за сутки, другой десятки тысяч, а какой-то и вовсе единицы. Да и сами эти планы по объему и сложности и по распределению во времени суток сильно отличаются. Так и получается, что нагрузку сильно качает, в разы:
Ну, а раз нагрузка может меняться настолько сильно, то надо учиться ей управлять
Координатор
Сразу понимаем, что нам явно понадобится масштабирование системы коллекторов, поскольку один отдельный узел со всей нагрузкой когда-то точно перестанет справляться. А для этого нам потребуется координатор тот, кто будет управлять всем зоопарком.
Получается примерно такая схема:
Каждый worker свою нагрузку в попугаях и в процентах CPU периодически сбрасывает master'у, те коллектору. А он, на основании этих данных, может выдать команду типа новый хост посадить на ненагруженный worker#4 или hostA надо пересадить на worker#3.
Тут еще надо помнить, что, в отличие от объектов мониторинга, сами коллекторы имеют вовсе не равную мощность например, на одном у вас может оказаться 8 ядер CPU, а на другом только 4, да еще и меньшей частоты. И если нагрузить их задачами поровну, то второй начнет затыкаться, а первый простаивать. Отсюда и вытекают
Задачи координатора
По сути, задача всего одна обеспечивать максимально равномерное распределение всей нагрузки (в %cpu) по всем доступным worker'ам. Если мы сможем решить ее идеально, то и равномерность распределения %cpu-нагрузки по коллекторам получим автоматом.
Понятно, что, даже если каждый объект генерирует одинаковую нагрузку, со временем какие-то из них могут отмирать, а какие-то возникать новые. Поэтому управлять всей ситуацией надо уметь динамически и поддерживать баланс постоянно.
Динамическая балансировка
Простую задачу (zabbix) мы можем решить достаточно банально:
- вычисляем относительную мощность каждого коллектора в задачах
- делим все задачи между ними пропорционально
- между worker'ами распределяем равномерно
Но что делать в случае сильно неравных объектов, как для коллектора логов?..
Оценка равномерности
Выше мы все время употребляли термин "максимально равномерное распределение", а как вообще можно формально сравнить два распределения, какое из них равномернее?
Для оценки равномерности в математике давно существует такая вещь как среднеквадратичное отклонение. Кому лениво вчитываться:
S[X] = sqrt( sum[ ( x -
avg[X] ) ^ 2 of X ] / count[X] )Поскольку количество worker'ов на каждом из коллекторов у нас тоже может отличаться, то нормировать разброс по нагрузке надо не только между ними, но и между коллекторами в целом.
То есть распределение нагрузки по worker'ам двух коллекторов
[ (10%, 10%, 10%, 10%, 10%, 10%) ; (20%) ] это тоже не
очень хорошо, поскольку на первом получается 10%, а на
втором 20%, что как бы вдвое больше в относительных
величинах.Поэтому введем единую метрику-расстояние для общей оценки равномерности:
d([%wrk], [%col]) = sqrt(
S[%wrk] ^ 2 + S[%col] ^ 2 )Моделирование
Если бы объектов у нас было немного, то мы могли бы полным перебором разложить их между worker'ами так, чтобы метрика оказалась минимальной. Но объектов у нас тысячи, поэтому такой способ не подойдет. Зато мы знаем, что коллектор умеет перемещать объект с одного worker'а на другой давайте этот вариант и смоделируем, используя метод градиентного спуска.
Понятно, что идеальный минимум метрики мы так можем и не найти, но локальный точно. Да и сама нагрузка может изменяться во времени настолько сильно, что искать за бесконечное время идеал абсолютно незачем.
То есть нам осталось всего лишь определить, какой объект и на какой worker эффективнее всего переместить. И сделаем это банальным переборным моделированием:
- для каждой пары (целевой host, worker) моделируем перенос нагрузки
- нагрузку от host внутри исходного worker'а считаем
пропорционально попугаям
В нашем случае за попугая оказалось вполне разумно взять объем получаемого потока логов в байтах. - относительную мощность между коллекторами считаем пропорциональной суммарным попугаям
- вычисляем метрику d для перенесенного состояния
Выстраиваем все пары по возрастанию метрики. В идеале, нам всегда стоит реализовать перенос именно первой пары, как дающий минимальную целевую метрику. К сожалению, в реальности сам процесс переноса стоит ресурсов, поэтому не стоит запускать его для одного и того же объекта чаще определенного интервала охлаждения.
В этом случае мы можем взять вторую, третью, по рангу пару лишь бы целевая метрика уменьшалась относительно текущего значения.
Если же уменьшать некуда вот он локальный минимум!
Пример на картинке:
Запускать итерации до упора при этом вовсе не обязательно. Например, можно делать усредненный анализ нагрузки на интервале 1 мин, и по его завершению делать единственный перенос.
Микро-оптимизации
Понятно, что алгоритм со сложностью
T(целей) x
W(процессов) это не очень хорошо. Но в нем стоит не забыть
применить некоторые более-менее очевидные оптимизации, которые его
могут ускорить в разы.Нулевые попугаи
Если на замеренном интервале объект/задача/хост сгенерировал нагрузку 0 штук, то его не то что перемещать куда-то его даже рассматривать и анализировать не надо.
Самоперенос
При генерации пар нет необходимости оценивать эффективность переноса объекта на тот же самый worker, где он и так находится. Все-таки уже будет
T x (W - 1) мелочь, а
приятно!Неразличимая нагрузка
Поскольку мы моделируем все-таки перенос именно нагрузки, а объект всего лишь инструмент, то пробовать переносить одинаковый %cpu нет смысла значения метрик останутся точно те же, хоть и для другого распределения объектов.
То есть достаточно оценить единственную модель для кортежа (wrkSrc, wrkDst, %cpu). Ну, а одинаковыми вы можете считать, например, значения %cpu, совпадающие до 1 знака после запятой.
Пример реализации на JavaScript
var col = { 'c1' : { 'wrk' : { 'w1' : { 'hst' : { 'h1' : 5 , 'h2' : 1 , 'h3' : 1 } , 'cpu' : 80.0 } , 'w2' : { 'hst' : { 'h4' : 1 , 'h5' : 1 , 'h6' : 1 } , 'cpu' : 20.0 } } }, 'c2' : { 'wrk' : { 'w1' : { 'hst' : { 'h7' : 1 , 'h8' : 2 } , 'cpu' : 100.0 } , 'w2' : { 'hst' : { 'h9' : 1 , 'hA' : 1 , 'hB' : 1 } , 'cpu' : 50.0 } } }};// вычисляем опорные метрики и нормализуем по "мощности"let $iv = (obj, fn) => Object.values(obj).forEach(fn);let $mv = (obj, fn) => Object.values(obj).map(fn);// initial reparsefor (const [cid, c] of Object.entries(col)) { $iv(c.wrk, w => { w.hst = Object.keys(w.hst).reduce((rv, hid) => { if (typeof w.hst[hid] == 'object') { rv[hid] = w.hst[hid]; return rv; } // нулевые значения ничего не решают, поэтому сразу отбрасываем if (w.hst[hid]) { rv[hid] = {'qty' : w.hst[hid]}; } return rv; }, {}); }); c.wrk = Object.keys(c.wrk).reduce((rv, wid) => { // ID воркеров должны быть глобально-уникальны rv[cid + ':' + wid] = c.wrk[wid]; return rv; }, {});}// среднеквадратичное отклонениеlet S = col => { let wsum = 0 , wavg = 0 , wqty = 0 , csum = 0 , cavg = 0 , cqty = 0; $iv(col, c => { $iv(c.wrk, w => { wsum += w.cpu; wqty++; }); csum += c.cpu; cqty++; }); wavg = wsum/wqty; wsum = 0; cavg = csum/cqty; csum = 0; $iv(col, c => { $iv(c.wrk, w => { wsum += (w.cpu - wavg) ** 2; }); csum += (c.cpu - cavg) ** 2; }); return [Math.sqrt(wsum/wqty), Math.sqrt(csum/cqty)];};// метрика-расстояниеlet distS = S => Math.sqrt(S[0] ** 2 + S[1] ** 2);// выбираем оптимальный перенос и моделируем егоlet iterReOrder = col => { let qty = 0 , max = 0; $iv(col, c => { c.qty = 0; c.cpu = 0; $iv(c.wrk, w => { w.qty = 0; $iv(w.hst, h => { w.qty += h.qty; }); w.max = w.qty * (100/w.cpu); c.qty += w.qty; c.cpu += w.cpu; }); c.cpu = c.cpu/Object.keys(c.wrk).length; c.max = c.qty * (100/c.cpu); qty += c.qty; max += c.max; }); $iv(col, c => { c.nrm = c.max/max; $iv(c.wrk, w => { $iv(w.hst, h => { h.cpu = h.qty/w.qty * w.cpu; h.nrm = h.cpu * c.nrm; }); }); }); // "текущее" среднеквадратичное отклонение console.log(S(col), distS(S(col))); // формируем набор хостов и воркеров let wrk = {}; let hst = {}; for (const [cid, c] of Object.entries(col)) { for (const [wid, w] of Object.entries(c.wrk)) { wrk[wid] = { wid , cid , 'wrk' : w , 'col' : c }; for (const [hid, h] of Object.entries(w.hst)) { hst[hid] = { hid , wid , cid , 'hst' : h , 'wrk' : w , 'col' : c }; } } } // реализация переноса нагрузки на целевой worker let move = (col, hid, wid) => { let w = wrk[wid] , h = hst[hid]; let wsrc = col[h.cid].wrk[h.wid] , wdst = col[w.cid].wrk[w.wid]; wsrc.cpu -= h.hst.cpu; wsrc.qty -= h.hst.qty; wdst.qty += h.hst.qty; // перенос на другой коллектор с "процентованием" нагрузки на CPU if (h.cid != w.cid) { let csrc = col[h.cid] , cdst = col[w.cid]; csrc.qty -= h.hst.qty; csrc.cpu -= h.hst.cpu/Object.keys(csrc.wrk).length; wsrc.hst[hid].cpu = h.hst.cpu * csrc.nrm/cdst.nrm; cdst.qty += h.hst.qty; cdst.cpu += h.hst.cpu/Object.keys(cdst.wrk).length; } wdst.cpu += wsrc.hst[hid].cpu; wdst.hst[hid] = wsrc.hst[hid]; delete wsrc.hst[hid]; }; // моделирование и оценка переноса для пары (host, worker) let moveCheck = (orig, hid, wid) => { let w = wrk[wid] , h = hst[hid]; // тот же воркер - ничего не делаем if (h.wid == w.wid) { return; } let col = JSON.parse(JSON.stringify(orig)); move(col, hid, wid); return S(col); }; // хэш уже проверенных переносов (hsrc,hdst,%cpu) let checked = {}; // перебираем все возможные пары (какой хост -> на какой воркер) let moveRanker = col => { let currS = S(col); let order = []; for (hid in hst) { for (wid in wrk) { // нет смысла пробовать повторно перемещать одну и ту же (с точностью до 0.1%) "мощность" между одной парой воркеров let widsrc = hst[hid].wid; let idx = widsrc + '|' + wid + '|' + hst[hid].hst.cpu.toFixed(1); if (idx in checked) { continue; } let _S = moveCheck(col, hid, wid); if (_S === undefined) { _S = currS; } checked[idx] = { hid , wid , S : _S }; order.push(checked[idx]); } } order.sort((x, y) => distS(x.S) - distS(y.S)); return order; }; let currS = S(col); let order = moveRanker(col); let opt = order[0]; console.log('best move', opt); // реализуем перенос if (distS(opt.S) < distS(currS)) { console.log('move!', opt.hid, opt.wid); move(col, opt.hid, opt.wid); console.log('after move', JSON.parse(JSON.stringify(col))); return true; } else { console.log('none!'); } return false;};// пока есть что-куда переноситьwhile(iterReOrder(col));
В результате, нагрузка по нашим коллекторам распределяется практически одинаково в каждый момент времени, оперативно нивелируя возникающие пики:
Категории: 
Обычное состояние
ДЦ 2 отключён
ДЦ 1 и ДЦ 3 не справляются с нагрузкой
Общая схема обработки поискового запроса
Количество обрабатываемых документов без
graceful degradation
Количество обрабатываемых документов при
включении механизма уменьшения нагрузки
Повышение нагрузки при выключении ДЦ.
Линии на верхнем графике показывают загрузку CPU в отдельных ДЦ.
Нагрузка выросла с 82% до 98%. Нижний график показывает процент
срезанных документов.
