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

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

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

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

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

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

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

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

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

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

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