Кому нужна математика? Понятная книга о том, как устроен цифровой мир

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

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

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

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

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

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

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

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

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

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