Балансировка нагрузки: префиксные суммы, общая очередь и кража работы

Если ты знаешь, как делить задачи известного размера префиксными суммами, как устроена кража работы и почему вор берёт с другого конца очереди, листай до «Теперь сам».

Как думаешь, кто закончит последним

Две тысячи задач, большинство на секунды, а пара процентов - в сто раз длиннее. Восемь рабочих, каждому дали по 250 задач подряд. Насколько последний рабочий закончит позже идеала - если бы работа была поделена ровно?

Ответ зависит от того, куда легли длинные задачи; в опыте разбора - на 43%: в его кусок попало больше длинных задач. Разбор покажет, что даже при известных размерах помогает не «поровну по числу», а «поровну по весу», а при неизвестных - только динамика.

На что это похоже

Бригада на складе разгружает фуры. Можно заранее раздать по фуре на человека - но фуры разные, и кто-то уйдёт домой в обед, а кто-то останется до ночи. Можно посадить бригадира, у которого все берут следующую коробку, - но у бригадира очередь. А можно так: каждый разгружает свою фуру, а освободившийся подходит к случайному коллеге и забирает у него из глубины кузова половину оставшегося. Бригадир не нужен, и все заканчивают почти одновременно.

Механизм: три способа

Префиксные суммы - для задач известного размера t₁, …, tₘ. Считаем префиксные суммы Sᵢ - вес всех задач перед i (их можно считать параллельно - сканом из главы о примитивах) и отдаём задачу i рабочему ⌊Sᵢ · p / W⌋. Каждый рабочий получает непрерывный кусок весом примерно W / p: нагрузка каждого отличается от W / p не больше чем на самую крупную задачу. Сандерс оценивает время как O(α log p + max куска).

Общая очередь - рабочие берут следующую задачу у мастера. Подходит для неизвестных размеров, но каждый запрос - сообщение мастеру, и при тысячах рабочих и мелких задачах он не успевает отвечать.

Кража работы (Блюмофе и Лейзерсон, 1999). У каждого рабочего дек - очередь с двумя концами. Новые подзадачи кладутся в его конец, и берёт он оттуда же - самую свежую, как обход в глубину: так меньше памяти и лучше кеш. Освободившийся рабочий выбирает случайную жертву и забирает задачу из начала её дека - самую старую, а в рекурсии «разделяй и властвуй» самая старая задача ближе всех к корню и обычно одна из самых крупных. Ожидаемое время T₁ / p + O(T∞), ожидаемое число краж - O(p · T∞): красть приходится редко, пока работы много.

Правило

Задачи известного размера делят префиксными суммами: граница куска k - там, где сумма весов доходит до k · W / p, и нагрузка каждого отличается от W / p не больше чем на самую крупную задачу. Задачи неизвестного размера балансируют динамически: общая очередь проста, но имеет узкое место; кража работы - свой дек у каждого, владелец берёт с конца, вор - с начала у случайной жертвы, ожидаемое время T₁ / p + O(T∞).

Разбор: поровну по числу против поровну по весу

Две тысячи задач с тяжёлым хвостом: 98% размером 1-10, 2% - 500-1000. Восемь рабочих. Сравним «по 250 задач подряд» и разбиение по префиксным суммам весов.

import random

def po_chislu(razmery, p):
    # каждому по n / p задач подряд
    n = len(razmery)
    nagruzka = []
    for k in range(p):
        nagruzka.append(sum(razmery[k * n // p:(k + 1) * n // p]))
    return max(nagruzka)

def po_prefiksam(razmery, p):
    # граница куска k - там, где префиксная сумма доходит до k * W / p
    W = sum(razmery)
    nagruzka = [0] * p
    pref = 0
    for r in razmery:
        k = min(p - 1, pref * p // W)
        nagruzka[k] = nagruzka[k] + r
        pref = pref + r
    return max(nagruzka)

random.seed(2)
razmery = []
for i in range(2000):
    # большинство задач мелкие, изредка - в сто раз крупнее
    if random.random() < 0.02:
        razmery.append(random.randint(500, 1000))
    else:
        razmery.append(random.randint(1, 10))
p = 8
print("идеал", sum(razmery) // p)
print("поровну по числу задач", po_chislu(razmery, p))
print("по префиксным суммам", po_prefiksam(razmery, p))
print("самая крупная задача", max(razmery))

идеал 6413
поровну по числу задач 9147
по префиксным суммам 6705
самая крупная задача 982

Идеал - 6413. «Поровну по числу» - 9147, на 43% хуже: в один кусок попало больше длинных задач. Префиксные суммы - 6705, на 4,5% хуже идеала; лишнее - меньше одной самой крупной задачи (982). Но для этого нужно было знать размеры заранее. В деревьях рекурсии, обходе графов и запросах с фильтрами размер работы выясняется только по ходу.

Разбор: кража работы на рекурсии

Работа - рекурсия «разделяй и властвуй»: задача размера больше 8 за один шаг делится на две в случайной пропорции, маленькая выполняется за свой размер. Восемь корней разного размера. Сначала каждому рабочему по корню и никакой кражи, потом то же с кражей.

import random

def shag(s, dek):
    # задача размера s > 8 делится на две в случайной пропорции за 1 шаг,
    # задача поменьше - лист, s шагов работы. Возвращает, сколько шагов
    # остаётся доделать после этого.
    if s > 8:
        a = random.randint(1, s - 1)
        dek.append(a)
        dek.append(s - a)
        return 0
    return s - 1

def zapusk(p, korni, krast, seed):
    # у каждого рабочего дек; своё берут с конца, вор - с начала
    random.seed(seed)
    dek = []
    for k in range(p):
        dek.append([])
    for k in range(len(korni)):
        dek[k % p].append(korni[k])
    ostalos = [0] * p
    vremya = 0
    rabota = 0
    krazh = 0
    while True:
        kto_rabotal = 0
        for k in range(p):
            if ostalos[k] > 0:
                ostalos[k] = ostalos[k] - 1
                kto_rabotal = kto_rabotal + 1
            elif len(dek[k]) > 0:
                ostalos[k] = shag(dek[k].pop(), dek[k])
                kto_rabotal = kto_rabotal + 1
            elif krast:
                zhertva = random.randint(0, p - 1)
                if len(dek[zhertva]) > 0:
                    dek[k].append(dek[zhertva].pop(0))
                    krazh = krazh + 1
        pusto = True
        for k in range(p):
            if len(dek[k]) > 0:
                pusto = False
        # конец - никто не работал и украденного тоже не осталось
        if kto_rabotal == 0 and pusto:
            return [vremya, rabota, krazh]
        vremya = vremya + 1
        rabota = rabota + kto_rabotal

p = 8
korni = [900, 300, 300, 200, 200, 200, 150, 150]
t, w, k = zapusk(p, korni, False, 1)
print("по корню на рабочего, без кражи: время", t, "работа", w)
t, w, k = zapusk(p, korni, True, 1)
print("то же с кражей: время", t, "работа", w, "краж", k)
print("нижняя граница работа / p:", -(-w // p))

по корню на рабочего, без кражи: время 1101 работа 2941
то же с кражей: время 383 работа 2943 краж 51
нижняя граница работа / p: 368

Без кражи - 1101 шаг: всё время определяет рабочий с корнем 900, остальные давно стоят. С кражей - 383 шага при нижней границе 368 (работа / p, округлённая вверх): на 4% хуже идеала. Краж понадобилась 51 - меньше одной на каждые пятьдесят выполненных шагов работы. Это и обещает оценка O(p · T∞): при параллелизме много больше p краж мало по сравнению с работой - в опыте 51 кража на 2943 шага. Работа в двух запусках различается на две единицы: кражи тоже тянут случайные числа, и рекурсия разбивается чуть иначе, - на сравнение времени это не влияет.

Что ломается без этого

Разбиение по числу при тяжёлом хвосте. Пакет из тысячи запросов делят поровну между серверами, и сервер с двумя тяжёлыми запросами отвечает вдвое дольше остальных. Средняя загрузка - 60%, а время ответа - по худшему.

Вор берёт свежую задачу. Если красть с того же конца, что берёт владелец, вор уносит крохотную подзадачу, быстро её делает и снова идёт красть: краж становится столько же, сколько задач, и каждая - синхронизация на одном конце дека.

Слишком мелкие задачи. Даже при краже порождение задачи стоит десятки операций - порог из первой главы раздела никуда не девается.

Зачем это в работе

Кража работы - стандартный планировщик: Cilk, ForkJoinPool в Java (на нём параллельные стримы), Rayon в Rust, планировщик горутин в Go, Tokio, TBB. Префиксные суммы делят данные в распределённых системах: Spark и Hadoop режут входные файлы по размеру байтов, а не по числу файлов, - из-за того же тяжёлого хвоста.

Теперь сам

1. Размеры задач 5, 1, 1, 8, 3, 2, двое рабочих. Раздели префиксными суммами: кому какие задачи и какой итог у каждого?
2. Почему вор крадёт у СЛУЧАЙНОЙ жертвы, а не у самой загруженной?
3. Чем кража работы лучше общей очереди при десяти тысячах рабочих?