Очереди, которых мы не видим

Всем нам хорошо знакомы самые разные очереди. Очередь в кассу супермаркета, очередь в приемной врача, очередь у лифта в большом здании, толкотня перед входом в метро и непереносимые очереди из машин – автомобильные пробки. Но кроме всех этих «живых» очередей, мы, сами того не замечая, стоим в огромном количестве «компьютерных» очередей. Например, это происходит практически каждый раз, когда мы подключаемся к интернету.

Допустим, вы хотите посмотреть какую-то веб-страницу, скажем главную страницу Московского физико-технического института (МФТИ), где работает Андрей. Вы вводите веб-адрес в своем браузере (например, Internet Explorer, Fire Fox или Google Chrome). Что же дальше?

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

Отправка цифровой информации сравнима с отправкой обычной почты или грузов. Запрос с вашего браузера поступает на так называемый веб-сервер под именем , веб-сервер МФТИ. Веб-сервер – это специально выделенный компьютер, который отвечает за поиск нужного файла и его отправку в браузер пользователя. У каждого сайта, или домена – , , и других, – свой веб-сервер, и часто не один.

Получив ваш запрос, веб-сервер МФТИ отправляет в ваш браузер файл с содержанием главной страницы. Дальше вы начинаете ее читать, кликаете на ссылки, загружаете документы. И каждый раз веб-сервер МФТИ отправляет вам новые странички, фотографии, тексты и все остальное. Кроме вас на сайт заходят другие пользователи, с другими запросами. У веб-сервера работы хватает! И когда ее слишком много, ваши запросы должны дожидаться своей очереди.

И это еще не все. Как и почтовая пересылка, информация попадает с одного компьютера на другой не напрямую, а через несколько промежуточных узлов. Каждый узел – это тоже серверы, и там тоже могут образоваться очереди на доставку и отправку. Это происходит при отправке любой цифровой информации, будь то имейл, фотографии на «Фейсбуке» или ваш голос по скайпу.

Насколько длинной будет очередь? Можно ли организовать сервис, например отправку веб-страниц или передачу голоса и видео, так, чтобы задержки были как можно меньше? Этими вопросами занимается специальная область математики под названием теория очередей, или теория массового обслуживания. Среди ее основателей крупные российские математики – Александр Яковлевич Хинчин и Борис Владимирович Гнеденко.

Теория очередей возникла из практики в начале XX века, когда датский математик Агнер Эрланг решил проанализировать работу телефонной станции. С появлением современных телекоммуникаций эта теория получила новое необъятное поле приложений и мощный толчок к развитию. В этой главе мы расскажем только об одной задаче, так называемой балансировке нагрузки, и об одном ее относительно недавнем и необыкновенно элегантном решении.

 

Параллельные серверы

Как вы уже поняли, запросов на веб-сервер поступает множество. Поэтому часто используется не один, а сразу несколько серверов, которые могут обрабатывать запросы одновременно. Серверов может быть очень много. Например, современные поисковые системы, такие как «Яндекс» и Google, получают миллиарды запросов в день. Поэтому они оснащены огромным количеством мощных серверов, занимающих внушительные территории.

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

Схематически мы изобразили параллельные серверы на рис. 5.1. Запросы на рисунке разной величины, потому что все они разного объема. Кому-то нужна страница с коротеньким текстом, а кому-то – годовой отчет на 100 страниц с графиками и фотографиями. Если информации больше, то и времени на ее отправку понадобится больше.

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

Поскольку серверов много, возникает проблема: на какой сервер отправить ваш запрос? Вопрос распределения заданий между параллельными серверами далеко не тривиален. Например, нельзя допустить, чтобы один сервер был перегружен, а другой простаивал. Желательно распределить нагрузку на них равномерно и свести очереди к минимуму. Как это сделать? В общих чертах это и есть задача о балансировании нагрузки.

Эта задача возникает не только при отправке и пересылке информации. Другой распространенный и очень похожий пример – вычисления на удаленном компьютере. Например, когда в научных вычислениях одним супермощным компьютером пользуется несколько исследовательских групп или когда мы что-то храним или вычисляем на «облаке». Проблемы возникают, если запросов на вычисления много, вычисления объемные и их невозможно выполнить одновременно.

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

 

Какой сервер выбрать?

Возможно, одни серверы в данный момент простаивают, а другие сильно загружены. Например, на сервер 5 загружен больше всех. Совершенно очевидно, что лучше всего отправить запрос на второй сервер – тот, у которого самая короткая очередь (в данном случае очереди просто нет). Однако такая стратегия не всегда оптимальна. Может оказаться, что в очереди всего один запрос, зато очень объемный, в то время как в другой очереди пять коротеньких запросов, которые будут выполнены моментально. Все мы наблюдали похожую ситуацию в обычном супермаркете. Лучше встать в очередь из трех человек с маленькими корзиночками, чем оказаться позади одной большой тележки! Иногда супермаркеты даже открывают специальную кассу для тех, у кого мало покупок. И в этой очереди, даже если она длиннее, вас практически всегда обслужат быстрее.

В контексте примера с супермаркетом понятно, что лучше всего выбрать сервер, у которого меньше всего работы, то есть тот, что освободится раньше всех. Математически это тоже нетрудно доказать. Однако есть существенная разница с супермаркетом. В супермаркете мы видим, у кого сколько покупок, и примерно представляем, какая очередь пойдет быстрее. Чтобы применить такую же тактику на веб-сервере, сервер должен «знать», сколько времени займет обработка каждого запроса в очереди.

Мы привыкли, что компьютеры умные. Тем не менее важно понять, что компьютер не человек, он не может взглянуть и оценить. Он не умеет думать. Все, что он может, – это использовать имеющуюся информацию и включить ее в протокол, то есть заранее установленный порядок действий. Это означает: оценить объем каждого запроса при входе, сохранить эту информацию и удалить после выполнения запроса. На это уходит время, тратится память, работа сервера замедляется. Если нам неизвестен объем заданий в очереди, то лучшее, что мы можем сделать, – выбрать самую короткую очередь. Такая стратегия тоже хорошо изучена математиками. Она очень эффективна, почти оптимальна. Итак, отправляем запрос в самую короткую очередь? Но вы, наверное, уже догадались, что в реальности возникают проблемы. Откуда система «знает» длину очереди каждого сервера на данный момент?

Каким образом получить информацию о загрузке, скажем, 1000 серверов? Можно послать серверам запрос. Но на обмен информацией уйдет какое-то время, и полученные данные будут хоть немножко, но устаревшими. Информация сразу со всех серверов загрузит канал, который нам нужен для обработки запроса. Кроме этого, полученную информацию необходимо где-то сохранить, скорректировать на задержку, просчитать решение. Да, все это происходит быстро. Но в итоге, может быть, выгоднее отправить запрос на любой сервер наугад, зато сразу? В редких случаях вам не повезет и запрос застрянет в очереди. Зато система будет работать быстро, и каналы передачи не будут загружены лишней информацией.

В разных случаях в зависимости от ситуации задача решается разными способами. Один из самых известных и простых называется Power of two choices – сила выбора из двух.

 

Сила выбора из двух

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

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

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

Чтобы воочию убедиться в эффективности выбора из двух, давайте предположим, что серверов много и система загружена на 90 %. Это означает, что каждый сервер простаивает примерно 10 % времени, что вполне разумно. Если загрузка больше, то из-за неравномерности поступления работы и разного времени обработки запросов очереди будут непозволительно большими. При загрузке 90 % и выборе сервера наудачу в среднем на нем будет девять сообщений. А если применить выбор из двух, то средняя очередь составит примерно 2,35 – очередь уменьшилась почти в четыре раза!

Еще интереснее подробный анализ. Сколько процентов серверов пустуют? Какая длина очереди наиболее типична? В табл. 5.1 мы привели результаты расчетов и сравнили процент серверов с очередью 0, 1, 2, 3, 4, 5, 6, 7 и больше при выборе сервера наугад и применении метода выбора из двух. Загрузка по-прежнему равна 90 %. Результаты довольно точные, когда серверов много.

Таблица 5.1. Процент серверов с очередью 1–7 и больше. Загрузка системы – 90 %

Давайте посмотрим, что означают эти числа. Начнем с того, что и в том и в другом случае 10 % серверов пустуют. Это естественно, потому что система загружена на 90 %. Зато дальше разница совершенно очевидна. При методе выбора из двух нагрузка распределяется равномерно. Больше чем у половины серверов очередь два или три, а очередь семь или больше почти не встречается. По сравнению с этим картина при случайном выборе сервера довольно печальная. Почти у половины серверов очередь семь и больше!

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

 

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

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

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

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

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

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

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

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

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

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

 

Где используется метод выбора из двух

В статье Митценмахера и другой литературе говорится о нескольких применениях метода выбора из двух. Одно приложение мы уже рассмотрели подробно – балансировка нагрузки, когда есть несколько обслуживающих приборов. В нашем примере это были веб-серверы, и мы упомянули пересылку информации через интернет и удаленные вычисления. Но подобная ситуация возникает и во множестве других контекстов. Неслучайно одно из названий модели – модель супермаркета. В следующий раз не обходите все кассы, окиньте взглядом две наугад и выбирайте самую короткую очередь из двух!

Есть и другие приложения – мы коротко опишем два из них, – тоже связанные с компьютерными технологиями. Первое – хеш-таблицы. Они используются для того, чтобы извлечь нужную информацию из памяти компьютера, который ищет ее по «ключу» – коротенькому коду. Когда информации немного, ключей достаточно. Но иногда происходят «коллизии»: несколько элементов, хранящихся в памяти, пользуются одним и тем же ключом. В этом случае компьютеру надо проверить всю эту группу (которая называется цепочкой), чтобы найти то, что нужно. Желательно, конечно, чтобы коллизий было поменьше, а цепочки покороче. Для этого часто пользуются методами типа выбора из двух.

Еще одно применение тоже связано с эффективным использованием памяти компьютера, и этот случай немного похож на наш пример с серверами. Компьютерные вычисления требуют большого объема памяти. Легче всего, когда ее необходимое количество доступно в одном месте. Но это не всегда возможно. В реальности распространены так называемые системы с распределенной памятью, где ею можно воспользоваться на нескольких разных машинах. Методы типа выбора из двух актуальны в нескольких разных вариантах при координации работы систем с распределенной памятью.

 

В чем секрет силы выбора из двух

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

Давайте вернемся к . У сервера 5 самая длинная очередь. Если выбрать сервер наудачу, наши шансы наткнуться на сервер 5 будут 1:5. Это 20 % случаев! При этом шансы попасть на самый лучший сервер, сервер 2, точно такие же.

Теперь представьте, что мы сначала выбираем два сервера, а потом наименьшую очередь из двух. Во-первых, в этом случае на сервер 5 мы в принципе не попадаем никогда. В худшем случае мы попадем на сервер 4. Но для этого мы должны наудачу вытянуть сервер 4 и сервер 5. Два сервера из пяти можно выбрать десятью способами: 1 и 2, 1 и 3, 1 и 4, 1 и 5, 2 и 3, 2 и 4, 2 и 5, 3 и 4, 3 и 5, 4 и 5. Все эти пары равновероятны. Шансы, что из десяти возможных пар мы вытянем именно самую неудачную, 4 и 5, всего 1:10. При этом свободный сервер 2 входит в четыре из десяти пар. Выбрав пару, в которую входит этот сервер, мы непременно на него попадем. Значит, наши шансы попасть на сервер 2 равны 4:10; это уже не 20 %, а 40 %.

Итак, у нас набралось три причины, по которым выбор из двух выгоднее выбора наугад:

1) мы никогда не попадаем в самую длинную очередь;

2) маловероятно, что мы выберем сразу два сервера с длинной очередью;

3) увеличиваются шансы попасть на пустой сервер.

Какая из этих причин самая значительная? Из математических уравнений следует, что причина 2. Представьте, что серверов много и у 20 % серверов длинная очередь. Тогда шансы наткнуться на два таких сервера всего 0,2×0,2×100 %=4 %.

Именно это перемножение вероятностей 0,2×0,2 и приводит к совершенно другому решению уравнения, согласно которому длинные очереди становятся практически невероятными.

Так получилось, что Нелли, будучи аспиранткой, присутствовала на одном из первых докладов Никиты Введенской о силе выбора из двух на конференции в Израиле в 1996 году. Когда Никита Дмитриевна объяснила решение, оно оказалось таким красивым и простым, что создавалось впечатление, что каждый мог догадаться! В перерыве Никита Дмитриевна сказала: «На самом деле это так просто, что можно объяснять студентам!» Это был блестящий пример математической работы – красивой и полезной!

Спустя почти 20 лет, на конференции в Стамбуле в 2015 году, пленарный доклад делала Кавита Раманан из университета Брауна в США. Кавита – блестящий математик с огромным количеством фундаментальных работ и профессиональных наград. На одном из первых слайдов она сослалась на работу Введенской, Добрушина и Карпелевича. Доклад Кавиты тоже был о методе выбора из двух. Но на данный момент эти исследования уже перешли на иной уровень обобщения и абстракции. Кавита занимается очень сложными асимптотическими процессами, ее доклад выходит за рамки нашей книги. Проблема развивается и ставит перед математиками новые задачи, еще красивее, еще сложнее и, кто знает, возможно, еще полезнее.