WhyПесочница

Закон Литтла

ПроблемаИнтенсивность входного потока и время пребывания заявки есть в любом мониторинге. Третья величина — сколько заявок находится в системе — получается из этих двух умножением, но её обычно оценивают отдельно и приблизительно. Отсюда пулы, рассчитанные по числу пользователей, и пороги на глубину очереди, которые ничего не говорят о времени ожидания.

  1. Шаг 1 из 8

    Три величины и одно равенство

    Закон Литтла связывает три величины: L — сколько заявок в среднем находится в системе, λ — с какой интенсивностью они в неё поступают, W — сколько времени каждая в ней проводит. По любым двум вычисляется третья.

    В 1954 году соотношение уже использовали как очевидное: у Кобхема оно приведено без доказательства. Доказательство предложил Джон Литтл в 1961 году; более простые позже дали Джуэлл, Эйлон и Стидем.

  2. Шаг 2 из 8

    L = λ × W

    Формулировка: долгосрочное среднее количество заявок L в стационарной системе равно долгосрочной средней интенсивности входного потока λ, умноженной на среднее время пребывания заявки в системе W.

    Десять заявок в секунду, каждая проводит в системе тридцать секунд — в системе в среднем триста заявок. Размерность сходится: заявок в секунду, умноженное на секунды, даёт заявки.

    Связь не зависит ни от распределения поступления, ни от распределения обслуживания, ни от порядка обслуживания. Заявки приходят равномерно или залпами, обслуживаются по очереди, с конца или по приоритету — равенство выполняется одинаково. Числа обслуживающих приборов в нём тоже нет.

    Этим закон отличается от остального аппарата теории массового обслуживания. Там, чтобы что-то посчитать, распределения нужно знать. Здесь достаточно двух измеренных средних.

    little.ts
    // L = lambda * W
const inSystem = arrivalsPerSecond * secondsInSystem;

    Вывод

    10 /s × 30 s = 300 in the system at any moment
no assumption about arrival pattern, service order or server count

  3. Шаг 3 из 8

    Любая из трёх по двум другим

    Калькулятор справа. λ и W входят в произведение симметрично: удвоение интенсивности и удвоение времени пребывания дают один результат.

    Само W ползунком не задаётся — оно складывается из ожидания и обслуживания. Поэтому сокращение времени обслуживания уменьшает и W, и L, и число обслуживающих приборов: λS падает вместе с S. Внешний сервис, наоборот, стал отвечать втрое дольше — выросли и W, и L, и счёт за инфраструктуру, хотя ни одна величина на нашей стороне не менялась.

    Ожидание при этом остаётся входной величиной, и это не упрощение. Насколько сократится очередь оттого, что обслуживание ускорилось, закон Литтла не говорит — у него в условиях нет ни распределений, ни загрузки. Это предмет теории массового обслуживания, и на шаге про ограничения об этом сказано отдельно.

    Исходные величины

    Что из них следует

    Время пребывания W
    30 с
    Заявок в системе L
    300 шт.
    На обслуживании λS
    100 шт.
    В очереди λWq
    200 шт.
    Обслуживающих приборов
    100 шт.

    W = 20 + 10 = 30 с, и тогда L = λW = 300 заявок

    Тот же закон на обслуживании: λS = 10 × 10 = 100. В очереди остальные 200.

    Ожидающих больше, чем обслуживаемых: основная часть W приходится на ожидание, и сокращать нужно его.

  4. Шаг 4 из 8

    Длина очереди как разность

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

    Применяем его дважды. Ко всей системе: λW, все заявки внутри. К обслуживанию: λS, где S — время обслуживания без ожидания. Разность — длина очереди.

    Десять заявок в секунду, тридцать секунд пребывания, из них десять — обслуживание. В системе триста, на обслуживании сто, ожидают двести.

    Отсюда правило для размера пула: считать по λS. Ожидающая заявка занимает место в очереди, а не обслуживающий прибор. Расчёт по λW даёт втрое больше машин, чем нужно работе.

    У Брайана Гетца в «Java Concurrency in Practice» это записано как число потоков = ядра × целевая загрузка × (1 + время ожидания / время работы). Дробь в скобках — то же отношение ожидания к обслуживанию, из-за которого потоков требуется больше, чем ядер.

    little.ts
    // The same law on a smaller box: service only.
const inService = arrivalsPerSecond * serviceSeconds;
const waiting = inSystem - inService; 

// The pool is sized by service: waiting items do not hold a worker.
const workers = Math.ceil(inService / itemsPerWorker);

    Вывод

    10 /s × 10 s = 100 being served, 200 waiting in the queue
100 / 1 item per worker = 100 workers

  5. Шаг 5 из 8

    Обратная подстановка: W = L / λ

    Равенство, решённое относительно времени пребывания.

    Так читают графики очереди. Число «сорок тысяч сообщений» само по себе не интерпретируется: это может быть рабочим состоянием, а может быть аварией. Разделив на интенсивность разбора — двести в секунду, — получаем двести секунд. Порог «глубина больше сорока тысяч» означает «заявка ждёт больше трёх минут».

    Отсюда и практика настраивать алерт по возрасту самой старой заявки, а не по глубине очереди. Возраст — это W, та самая величина, о которой даётся обещание пользователю. Глубина без λ не интерпретируется: тысяча сообщений при интенсивности разбора десять тысяч в секунду — это одна десятая секунды, а сто сообщений при интенсивности одно в секунду — сто секунд.

    little.ts
    // W = L / lambda — the same equality, solved for time.
const secondsToDrain = queueDepth / drainedPerSecond;

    Вывод

    40 000 messages / 200 per second = 200 s before the queue is empty
alert threshold "depth > 40 000" == "the oldest message is 200 s old"

  6. Шаг 6 из 8

    Условия применимости

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

    Стационарность на практике проверяют так: на достаточно длинном окне из системы выходит столько же заявок, сколько в неё вошло. Если интенсивность входного потока выше пропускной способности, стационарности нет. Очередь растёт, W растёт вместе с ней, и среднего значения у него не существует. Равенство при этом не нарушается — оно показывает, что L растёт, — но предсказывать им нечего: считать надо разность между λ и пропускной способностью.

    Пропускная способность выводится из тех же величин: число обслуживающих приборов, делённое на время обслуживания. Сто приборов по десять секунд дают ровно десять заявок в секунду. При λ = 10 загрузка стопроцентная, и любое отклонение даёт очередь, которая уже не рассасывается.

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

  7. Шаг 7 из 8

    Чего закон не даёт

    Все три величины — средние, причём долгосрочные. Из этого следуют три ограничения, и про все три регулярно забывают.

    Из L = 300 не следует, что в системе всегда триста заявок. Это могут быть ровные триста, а могут — ноль половину суток и три тысячи в час пик. Пул, рассчитанный по среднему, пик не выдержит; поэтому в оценках появляется отдельный коэффициент неравномерности.

    О разбросе закон тоже молчит. Среднее W в двадцать секунд совместимо с тем, что один процент заявок ждёт десять минут. Поэтому обещания пользователю формулируют в процентилях, а не в средних.

    И он не отвечает, что станет с W при росте λ. Пропускная способность в десять заявок в секунду не означает, что девять — рабочий режим: с приближением загрузки к единице очередь растёт нелинейно. Это уже предмет теории массового обслуживания, и там без распределений не обойтись. Литтл даёт L при известном W; как изменится W при росте λ, он не говорит.

  8. Шаг 8 из 8

    Где он применяется

    Три подстановки в одно равенство:

    • число обслуживающих приборов — λS, делённое на то, сколько заявок держит один;
    • длина очереди — λW − λS;
    • время ожидания — L / λ.

    За пределами теории массового обслуживания то же равенство известно под другими именами. В канбане оно записано как «время цикла = WIP / пропускная способность», а лимиты на незавершённую работу — способ удерживать L, чтобы не росло W.

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

Листать шаги можно стрелками ← и →.

Проверь себя

Поток джоб не изменился, но целевой API стал отвечать вдвое медленнее. Что произойдёт с числом джоб, находящихся в работе одновременно?

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

Внутри системы в среднем триста единиц: сто обслуживаются, двести ждут. Сколько обслуживающих приборов нужно, если один держит одну единицу?

Отвечено 0 из 3