Каким образом получить информацию о загрузке, скажем, 1000 серверов? Можно послать серверам запрос. Но на обмен информацией уйдет какое-то время, и полученные данные будут хоть немножко, но устаревшими. Информация сразу со всех серверов загрузит канал, который нам нужен для обработки запроса. Кроме этого, полученную информацию необходимо где-то сохранить, скорректировать на задержку, просчитать решение. Да, все это происходит быстро. Но в итоге, может быть, выгоднее отправить запрос на любой сервер наугад, зато сразу? В редких случаях вам не повезет и запрос застрянет в очереди. Зато система будет работать быстро, и каналы передачи не будут загружены лишней информацией.
В разных случаях в зависимости от ситуации задача решается разными способами. Один из самых известных и простых называется Power of two choices – сила выбора из двух.
Давайте еще раз проанализируем два крайних случая. Собирать информацию от всех серверов неудобно, и это занимает много времени. Отправлять запрос наугад, при полном отсутствии информации, тоже плохо, потому что так мы рискуем попасть на самый загруженный сервер. Если крайние случаи нас не устраивают, то, скорее всего, самое лучшее решение лежит где-то посередине. И часто уже первый шаг в этом направлении ведет к серьезным улучшениям.
Что, если мы затребуем информацию о длине очереди не на всех серверах, а только на двух, выбранных наугад, а дальше посмотрим, на каком из них очередь меньше, и именно туда отправим запрос. Ответ от двух серверов придет быстро, и на загрузку системы это практически не повлияет. У этого простого метода есть несколько названий: парадигма двух выборов, метод двух случайных выборов, метод выбора из двух. А иногда его называют моделью супермаркета.
Понятно, что выбирать самую короткую очередь из двух случайных серверов лучше, чем выбирать сервер вслепую. Но насколько лучше? Оказывается, результаты просто несравнимы!
Чтобы воочию убедиться в эффективности выбора из двух, давайте предположим, что серверов много и система загружена на 90 %. Это означает, что каждый сервер простаивает примерно 10 % времени, что вполне разумно. Если загрузка больше, то из-за неравномерности поступления работы и разного времени обработки запросов очереди будут непозволительно большими. При загрузке 90 % и выборе сервера наудачу в среднем на нем будет девять сообщений. А если применить выбор из двух, то средняя очередь составит примерно 2,35 – очередь уменьшилась почти в четыре раза!
Еще интереснее подробный анализ. Сколько процентов серверов пустуют? Какая длина очереди наиболее типична? В табл. 5.1 мы привели результаты расчетов и сравнили процент серверов с очередью 0, 1, 2, 3, 4, 5, 6, 7 и больше при выборе сервера наугад и применении метода выбора из двух. Загрузка по-прежнему равна 90 %. Результаты довольно точные, когда серверов много.