Как избежать “биений” и “затопления” системы запросами

Решение этой проблемы возникло во время моей работы над игрой Soldiers: Heroes of World War II (“В тылу врага”), для которой я разрабатывал систему движения для танков и другой техники.

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

Танки!

Чтобы справиться с этим багом, сначала я добавил повторный запуск приказа через фиксированное время. На первый взгляд, это было логичное решение. Но в итоге оно привело к тому, что все застрявшие танки начинали одновременно пытаться объехать препятствие. Это приводило к всплеску нагрузки на подсистему поиска пути и ощутимому “подвисанию” игры. Возникал так называемый эффект биения.

Также возникал эффект одновременного решения конфликтов, когда оба танка пытались объехать друг друга одновременно и мешали друг другу. Как если бы на узком тротуаре два человека, пытаясь уступить другу другу дорогу, шагали бы одновременно в одну и ту же сторону.

Это решение не сработало. Тогда я попытался ввести повторение действия через случайный интервал в заданном временном диапазоне. Мне удалось устранить “биения” и “бесконечные циклы” в решении конфликтов.

Но в этом изящном решении есть одна проблема. Чем больше времени проходит, тем меньше вероятность, что ситуация изменится на благоприятную.  Поэтому нет смысла нагружать излишне систему постоянными проверками.

Так родилось третье решение, которое учитывало эту вероятность путем умножения времени ожидания на фиксированную величину после каждой попытки.

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

В итоге получился алгоритм перезапуска неудавшихся операций, который выглядит вот так:

время ожидания / номер попытки

Параметры:

  • T0 — минимальное время ожидания
  • Chigh — количество попыток, при которых растёт время ожидания
    • 1 < Chigh <= Cmax
  • Cmax — максимальное количество попыток
    • Cmax >= 1
  • D — максимальный разброс времени при первой попытке
    • должен быть > 0
  • S — коэффициент увеличения ожидания на каждом последующем шаге
    • должен быть > 1

Алгоритм:

  1. изначально счётчик попыток C ←  0
  2. выполняем операцию
  3. если операция успешна, то
    1. выходим с успехом
  4. счётчик попыток C ←  C + 1
  5. если счётчик попыток C >= Сmax, то
    1. выход с ошибкой
  6. если счётчик попыток C = 1, то
    1. время ожидания T ← Tmin+  D * (случайная величина от 0 до 1)
  7. иначе
    1. X ← min(Chigh, C) — 2
    2. время ожидания T ← Tmin +  D * (SX + (случайная величина от 0 до 1) *  (SX+1 — SX)
  8. ожидаем время T
  9. переходим на пункт 2

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

  • для определения разумного времени переподключений клиента к серверу
  • в компьютерных играх, чтобы ИИ не выглядел бездумным болванчиком
  • разрешения коллизий в сети
  • перезапуске программ после слёта

Этот же алгоритм был использован позже уже при разработке InvariMatch, чтобы перезапускать сбойные операции. Он позволил нам обеспечить стабильность работы системы, избегать перегрузок сервера из-за повтора сбойных запросов и добавить автоматическое восстановление системы после локальных и глобальных сбоев.

Метки: ,
Категории: ,