Кто придумал и обосновал метод выбора из двух

 

Впервые метод выбора из двух предложили ученые‑информатики Дерек Игер, Эдвард Лазовска и Джон Захорджан в 1986 году {14} именно в контексте разделения вычислительной работы между ресурсами. Это практически та же ситуация, что и наш пример с веб‑сервером. Ученые заметили, насколько сильно влияет на систему небольшое количество информации, и обратили внимание на то, что именно выбор из двух (а не из трех или четырех) особенно эффективен.

Казалось бы, открытие сделано? Но, как всегда в науке, это было только начало. Дело в том, что все результаты в статье Игера и соавторов основывались исключительно на так называемом имитационном моделировании.

Что такое имитационное моделирование и в чем его сила и недостатки, понять совсем нетрудно. Многие, наверное, играли в компьютерные игры, где надо, скажем, управлять автомобилем. Конечно, никакого автомобиля нет. Но вы проедете по виртуальной дороге за виртуальным рулем, и вам покажут всю статистику: скорость, время, качество вождения и другие показатели. Аналогично можно виртуально изобразить работу серверов и посмотреть, как они будут функционировать при использовании разных методов распределения нагрузки. Это дает представление о результатах без необходимости что‑то менять на реальном сервере, что бывает трудно, а порой и невозможно по техническим причинам и чревато немалым количеством ошибок. Точно так же как для большинства из нас Формулу‑1 на скорости 250 км/ч лучше проходить виртуально, по крайней мере для начала.

Имитационное моделирование – мощный способ получить информацию о сложной системе. С первого взгляда можно даже подумать, что формулы вообще не нужны и имитационного моделирования достаточно. Но у этого подхода есть ограничения. Во‑первых, при изменении параметров системы (например, изменилось количество поступающих сообщений в минуту) все надо пересчитывать заново. Если бы была формула, то новое значение параметра можно было бы просто в нее подставить. Во‑вторых, имитационное моделирование не дает ответа на вопрос, почему метод так хорошо работает, а из математического доказательства обычно сразу видно, какие факторы оказали решающее влияние.

Мы никогда не смогли бы просто так взять и за пару минут посчитать результаты, приведенные в табл. 5.1, и никогда бы точно не оценили эффективность выбора из двух, если бы не вклад математиков. Всплеск их интереса к этой теме произошел во второй половине 1990‑х, и именно тогда были получены основные результаты.

В 1996 году российские математики Никита Дмитриевна Введенская, Роланд Львович Добрушин и Фридрих Израилевич Карпелевич опубликовали статью «Система обслуживания с выбором наименьшей из двух очередей – асимптотический подход» в журнале «Проблемы передачи информации» {15}. Система обслуживания – это наши несколько серверов, которые должны отправить (обслужить) веб‑страницы. Выбор наименьшей из двух очередей мы уже обсудили – это и есть метод выбора из двух.

На самом деле об асимптотическом подходе мы уже несколько раз упоминали, просто не пользовались математической терминологией. Дело в том, что система выбора из двух не поддается точному математическому анализу. Об этом авторы пишут на первой же странице. Проблема в том, что серверов несколько, и это делает математические уравнения такими громоздкими, что их невозможно решить ни на бумаге, ни даже на компьютере. Проблема сильно упрощается, есть предположить, что серверов очень много, бесконечное количество. Тогда самые запутанные части в уравнении настолько уменьшаются, что ими можно пренебречь. А то, что остается, поддается анализу. И хотя он по‑прежнему далеко не тривиальный, но уже выполнимый! Это и есть асимптотический анализ, от слова асимптота – предел, которого нельзя достигнуть. Асимптотические результаты всегда приблизительные. Никто никогда не даст вам бесконечное количество серверов! Но когда серверов много, асимптотические результаты очень точные, а главное они позволяют нам понять, как работает система. Именно такой асимптотический анализ и сделали авторы статьи. Результаты, приведенные в табл. 5.1, взяты прямо из статьи, мы только подставили числа. При этом отдали должное асимптотическому подходу и оговорились, что результаты применимы, когда серверов много.

Практически одновременно с российскими математиками похожие результаты опубликовал Михаел Митценмахер из Гарвардского университета. Вскоре появилось еще несколько статей, в которых рассматривались разные особенности системы (например, длина очереди на самом загруженном сервере) и предлагались разные подходы к решению. Видимо, это был именно тот случай, когда идеи витали в воздухе!

В 2001 году Михаел Митценмахер с коллегами опубликовал серьезную обзорную статью на эту тему {16}, которой мы воспользовались при написании этой главы. Уже на тот момент перечень литературы о выборе из двух и других похожих моделях стал достаточно обширным и продолжает расширяться до сих пор.