Коммунальные вычисления: рыночный подход

Коммунальные вычисления (utility computing) — это один из способов приобретения вычислительных ресурсов по требованию. Поскольку спрос на услуги такого рода по природе своей изменчив, авторы считают, что для решения задачи динамического выделения ресурсов уместно использовать концепции и методы, заимствованные из микроэкономики.

Введение

Коммунальные вычисления — это новый подход, открывающий потребителям возможности использования крупных вычислительных ресурсов по требованию путем доступа к ним через высокоскоростные сети. Многие индивидуальные пользователи и предприятия уже арендуют пространство на удаленных, управляемых извне Web-серверах и платят за разнообразные услуги (например, электронную почту), так что сама идея не нова. Новизна заключается в масштабах проникновения коммунальных вычислений и в возможности удовлетворять запросы новых приложений для корпоративных пользователей, требующих огромных ресурсов процессора и памяти.

Как продавать массовые вычислительные ресурсы, такие, как время процессора, объем систем хранения или полосу пропускания канала связи? Проще всего опубликовать прейскурант: большинство предприятий розничной торговли продают товары и услуги именно так. Потребителям и поставщикам удобно ориентироваться в фиксированных ценах (т. е. определять, приемлема ли для них цена), но у этого подхода есть и существенный недостаток — отсутствие гибкости по отношению к покупателям и продавцам. Если установить слишком высокую цену, потребитель не сможет купить товары, а если слишком низкую, то спрос превысит предложение — в любом случае продавец не получит максимальной прибыли. Однако эти эффекты будут минимальны, если существует много разных покупателей и продавцов, а спрос находится в равновесии с предложением.

При большом числе покупателей и продавцов или при большом выборе товаров фиксация цен обеспечивает успешное, даже если не оптимальное, функционирование рыночной экономики. На другом конце спектра по сложности — модель аукциона предметов искусства, на котором продается единственный предмет и в котором участвуют один продавец и несколько покупателей. Поскольку предмет продажи только один, продавец может лишь единожды установить цену товара. При этом правильный выбор начальной цены чрезвычайно важен — от него зависит, сможет ли продавец продать товар и получить прибыль. Аукцион можно назвать процедурой выяснения цены — он позволяет найти тот ценовой уровень, при котором запросы покупателей совпадают с предложениями поставщиков.

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

Коммунальные вычисления

Концепция коммунальных вычислений предполагает, что объемы вычислительных ресурсов, необходимых для нашей деятельности, будут и дальше расти, и для многих предприятий окажутся неоправданными затраты средств и труда специалистов, требуемые для размещения этих ресурсов в рамках собственной инфраструктуры. Уже сегодня компании предпочитают обращаться к сторонним поставщикам ИТ-услуг (аутсорсерам), например, для обслуживания оборудования, а в будущем аусорсинг распространится и на базовые ресурсы — процессоры, каналы связи и хранилища данных. Концепция коммунальных вычислений — это и есть видение мира, где такой аутсорсинг будет безболезненным и прозрачным. Потенциальные поставщики услуг (например, компания HP) прогнозируют будущее, в котором крупные центры обработки данных, способные удовлетворять вычислительные нужды сотен и тысяч потребителей, будут поставлять ИТ-услуги всех видов и сортов: от моделирования динамики жидкостей с интенсивным использованием процессорных ресурсов для аэрокосмических компаний до цифровой обработки мультимедиа и Web-сайтов, где будут храниться домашние фотоальбомы, — и все это с использованием единой базы ресурсов.

Основной аргумент в пользу нового подхода — экономический. За счет своих масштабов крупные центры обработки данных способны сократить затраты на управление и эксплуатацию. По мере того, как компьютерная отрасль становится более зрелой, ИТ проникают во все сферы жизни, и сегодня у многих предприятий очень высока потребность в обработке информации, но при этом они не относят ИТ к своей ключевой деятельности (равно как и строительные работы, организацию питания сотрудников или охрану территории).

Коммунальные вычисления возможны благодаря двум технологическим достижениям: развитию Интернета, что обеспечивает сегодня высокоскоростной доступ по сети к удаленным ресурсам по доступным ценам, и технологиям защиты, достигшим того уровня развития, когда можно начать расширять внутренние ИТ-ресурсы, добавляя к ним динамически выделяемые внешние ресурсы.

Мы полагаем, что на рынке коммунальных вычислений будут действовать три типа игроков. Поставщики ресурсов (Fabric Providers, FP) будут обеспечивать ИТ-ресурсы для массовых вычислений, хранения данных и каналов связи. Поставщики услуг (Service Providers, SP) будут закупать ИТ-ресурсы у их поставщиков, приобретать лицензии у поставщиков приложений (Application Providers) и продавать пакеты информационных услуг пользователям, которые также выступают как оплачивающие эти услуги потребители. Такая схема рынка приведена на рис. 1.

Масштабы приобретения виртуальных ресурсов потребителями потенциально очень велики. Например, рендеринг при съемках голливудского фильма или расшифровка последовательности генома могут потребовать сотен и тысяч процессоров.

Коммунальные вычисления все еще находятся в стадии становления, и существует много бизнес-вопросов, на которые пока нет ответов. Неизвестно, какие секторы рынка будут наиболее важными и какие факторы будут играть роль при выделении отдельных секторов; какие транзакции будут происходить между участниками рынка; какого типа соглашения будут применяться; каковы будут основные временные периоды аренды ресурсов: дни, недели или месяцы.

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

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

Прикладные модели

Для некоторых типов приложений характерны масштабные, изменяющиеся во времени требования к ресурсам. Например, нагрузка на Web-сайты в периоды максимальной и минимальной активности может отличаться десятикратно, и еще более крупные колебания имеют место в особых случаях (спортивные соревнования, важные новости, рекламные акции, сезонные всплески и т. д.)

На рис. 2 показан шаблон трехуровневого Web-приложения, являющий собой абстрактную модель ресурсов для большого класса Web-служб. Пул Web-серверов обеспечивает первую линию интерфейса для потребителей и передает транзакции пулу серверов приложений, который, в свою очередь, обращается к пулу серверов базы данных. Один из способов реагирования на большие перепады нагрузки в такой системе — увеличивать и уменьшать размеры соответствующих пулов, чтобы среднее время обработки транзакции потребителя оставалось неизменным при всех изменениях нагрузки. Таким образом, для типичного трехуровневого сервиса следует указать минимальный базовый размер каждого пула и изменять размеры пулов так, чтобы показатели производительности основных приложений не выходили за рамки приемлемых значений. Ниже. в разделе «Потребитель — поставщик услуг» описана замкнутая циклическая структура, в которой это достигается путем рыночной торговли ресурсами.

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

Роль рынков

Сущность коммунальных вычислений состоит в том, чтобы предоставить пользователям вычислительные ресурсы по запросу как экономическую альтернативу владению ими. Но говоря об этом, не обойтись без рассмотрения структуры данного рынка. Коммунальные вычисления легко спутать с рыночным распределением ресурсов (Market Based Resource Allocation, MBRA). MBRA представляет собой приложение микроэкономической теории к распределению ресурсов и во многих случаях может рассматриваться как изолированный и распределенный механизм управления [3] — иными словами, существуют проблемы управления ресурсами, и один из способов их решения заключается в использовании терминологии и теории микроэкономики. При этом рынок превращается в искусственное образование, используемое для решения проблемы, так же, как множители Лагранжа вводятся для решения задач с ограничениями в прикладной математике.

Важная характеристика рынка — цена pi, уплаченная за товар xi. Цены — это первичные наблюдаемые параметры рынка, которые служат источником информации о нехватке каких-то товаров. Цены также выполняют управляющую функцию путем преобразования доходов в ресурсы. Первая и вторая теоремы Экономики Благосостояния показывают, что при разумных математических условиях существуют «справедливые» равновесные состояния (относительно априорного распределения дохода) — это означает, что каждый игрок рынка получает столько дохода, сколько возможно, и никто не может увеличить свой доход, не поставив в невыгодное положение кого-то другого.

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

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

В данной работе использование «рынков» рассматривается в двух различных контекстах, характеризуемых тем, кто выступает владельцем рынка. Это рынки поставщиков ресурсов для крупных оптовых закупок вычислительных ресурсов (FP) и внутренние рынки поставщиков услуг для эффективного распределения ресурсов между приложениями (SP).

В первом случае мы изучали рыночные механизмы, с помощью которых пользователи могут выразить свои предпочтения при резервировании и покупке ресурсов. Во втором случае использовали чистый MBRA-подход в рамках деятельности поставщика услуг, чтобы максимизировать общее благо, а именно доходы, связанные с пулом его ресурсов.

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

Если цены слишком низки, то покупатели запросят больше ресурсов, нежели готовы предоставить продавцы, поэтому кто-то согласится заплатить немного больше, чтобы не остаться вовсе без ресурсов, а это ведет к повышению цен. Аналогично, если цены слишком высоки, то продавцы пожелают продать больше, чем готовы купить покупатели, и продавцы, неспособные сбыть товар, оказываются перед выбором: снизить цены или совсем лишиться продаж.

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

На потребительских рынках (например, на рынке ПК) цены определяются продавцами, которые на основе некоей информации строят обоснованные предположения касательно спроса на свои товары и соответственно назначают цены. Этот механизм успешно действует, пока спрос и предложение адекватны и изменяются медленно по сравнению с ценами.

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

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

В нашем исследовании в HP Laboratories рассматривались подходящие механизмы для таких аукционов, включая вопросы о том, как будут формироваться пакеты ресурсов для продажи; как потребители будут выражать свои запросы; по каким протоколам будет организована связь между различными участниками; каковы будут вероятные стратегии агентов. Последняя проблема неразрывно связана с предшествующими: поведение покупателей будет меняться в соответствии с рыночными механизмами, а рыночный механизм должен быть адаптирован к поведению агентов.

Оптимизация использования ресурсов

Доход, полученный от сдачи ресурсов в аренду, зависит от времени использования ресурсов и ставки арендной платы. Ключевой показатель здесь — средняя ставка, по которой исчисляется доход от ресурсов.

Например, проблема с организацией общественного транспорта состоит в том, что, с одной стороны, нагрузка на транспортные системы резко увеличивается в часы пик, а с другой — пассажиры требуют предоставить им в это время достаточно мест. Основную же часть дня автобусы и поезда простаивают, поэтому системы общественного транспорта редко приносят прибыль. Если емкость системы в часы пик недостаточна, то вводится управление доступом к услуге; в случае общественного транспорта это означает, что пассажир не может сесть в переполненный автобус или поезд. На практике пассажиры просто сдвигают свои поездки на другие, менее загруженные периоды времени. Таким образом, чем меньше ресурсов выделяется для удовлетворения спроса, тем больше пассажиров вынуждены совершать поездки вне пиковых часов, и в некоторых регионах вечерние часы пик длятся с 15.00 до 20.00 (рис. 3). На рис. 3a объем ресурса/вместимость превышает потребность, и спрос удовлетворяется. На рис. 3b вместимость меньше спроса, и часть спроса смещается на менее удобное время. На рис. 3c вместимость еще меньше, и кривая естественного спроса, показанная на рис. 3a, принимает совсем иную форму.

Такое поведение типично для художников-мультипликаторов, преобразующих свои сцены в изображения. Обычно они предпочитают работать днем, откладывая рендеринг на ночные часы. Если бы ресурсы рендеринга были безграничны, то поведение мультипликаторов соответствовало бы рис. 3a. Но по мере уменьшения ресурса (рис. 3b и c) им приходится выполнять рендеринг в менее удобное для них время.

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

Исследование HP Laboratories

В проведенном компанией Hewlett Packard исследовании рассматривались два сценария, в которых используется управление рыночными методами: их можно назвать кооперативным и конкурентным.

Согласно кооперативному сценарию, все игроки рынка используют один и тот же механизм/структуру для оценки потребностей в ресурсах и честно переводят свои оценки в заявки на ресурсы. Хотя кажется, что участники изолированы друг от друга и децентрализованы, между ними существует неявная связь, поскольку они используют одинаковую структуру оценки и берут на себя обязательство действовать честно ради общего блага. Этот экономический сценарий пригоден для контекста внутренних рынков распределения ресурсов в рамках деятельности поставщика услуг (SP).

Согласно конкурентному сценарию, единственная точка соприкосновения между участниками — аукцион ресурсов, и можно предположить, что все игроки будут самыми разными способами, в меру своей изобретательности, добиваться выгоды для себя. Если в организации рыночного механизма были допущены просчеты, следует предполагать, что они будут использованы. Этот сценарий применим к рынкам крупных поставщиков ресурсов (FP).

Полезны как кооперативный, так и конкурентный сценарии. Кооперативный сценарий использовался в качестве механизма делегированного и распределенного управления, интересный пример этого — система управления центральным отоплением офисного комплекса**. Конкурентный сценарий применяется чаще, так как он в меньшей степени опирается на предположения, но его недостаток — потенциальная сложность рыночных механизмов и трудности теоретического понимания того, как эти рынки функционируют на практике.

Мы применили оба варианта рыночного управления на двух различных уровнях рынка коммунальных вычислений: как средство регулировать использование ресурсов в рамках деятельности одного поставщика услуг и как способ торговли ресурсами между поставщиками услуг и поставщиками ресурсов.

Поставщик услуг располагает пулом ресурсов, приобретенным у поставщиков ресурсов, и распределяет их между потребителями, обеспечивая им заданный уровень обслуживания. Цель поставщика услуг — минимизировать использование ресурсов в соответствии с соглашениями об уровне обслуживания (SLA), которые он заключает с потребителями. Поставщик услуг может реализовать каждое соглашение об уровне обслуживания через агентов (Service Manager), а агенты могут использовать кооперативное рыночное управление, чтобы гарантировать каждому приложению именно тот уровень ресурсов, который ему необходим.

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

Потребитель — поставщик услуг

Предполагается, что контракт между потребителем и поставщиком услуг заключается в форме соглашения об уровне обслуживания (Service Level Agreement, SLA), в котором определяются показатели для конкретного приложения. Согласуется тариф, который зависит от отношения реальной измеренной производительности к эталонным показателям. В большинстве случаев потребитель определяет целевой уровень производительности, а суть SLA заключается в том, что поставщик услуг получает плату за обеспечение этого уровня производительности. При существенном снижении показателей для поставщика услуг можно предусмотреть штраф.

У поставщика услуг нет экономических или обусловленных контрактом причин выделять приложению избыточные ресурсы. Предельная полезность от выделения приложению дополнительных ресурсов на определенном этапе падает до нуля, а затем становится отрицательной, так как затраты на электроэнергию и охлаждение превысят дополнительные доходы (рис. 4). Если поставщик услуг отвечает за выполнение приложений для многих потребителей, то желательно сбалансировать ресурсы для разных приложений таким образом, чтобы максимально увеличить общую эффективность всех ресурсов, — иными словами, чтобы каждый ресурс использовался с наибольшей отдачей.

Рыночное управление обеспечивает простой, элегантный и интуитивно понятный метод балансирования ресурсов между приложениями. Каждому запущенному приложению ставится в соответствие управляющий компонент Service Manager (SM). Service Manager отслеживает показатели производительности приложения и передает их в модуль SLA Manager, который сравнивает текущие показатели с целевым уровнем. Измеренные показатели используются при расчете цены покупателя для ресурса каждого типа, задействованного в приложении.

Service Manager передает информацию о ценах в централизованную систему управления Resource Manager, которая сравнивает предельную полезность, характеризуемую ценой покупателя для ресурса каждого типа в пуле ресурсов, а затем принимает решение о том, как перераспределить ресурсы между приложениями. При необходимости он может запросить дополнительные ресурсы у поставщика или вернуть их — предложенная покупателем цена обеспечивает простой механизм для связи внутреннего предоставления ресурса поставщиком услуг с внешними рынками ресурсов, поэтому существует прямая связь портфеля SLA-соглашений потребителей с динамической торговлей ресурсами за реальные деньги.

Если в результате торговли изменяется набор ресурсов приложения, то диспетчер служб заново развертывает компоненты приложения, и результаты этого сказываются на измеряемых характеристиках производительности. Этот замкнутый цикл управления показан на рис. 5.

Поставщик услуг — поставщик ресурсов

Мы предполагали, что хотя поставщик услуг может иметь стабильный базовый набор ресурсов, арендованных у поставщиков ресурсов на длительный срок (несколько месяцев), существуют и способы динамически расширять и сокращать объем ресурсов, покупая и продавая их на открытом рынке. Товар (good) определяется как «конкретный тип вычислительного ресурса на некий период времени». Как правило, потребителям нужно несколько видов вычислительных ресурсов на какой-то период времени — иными словами, им нужен пакет товаров.

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

В приведенных ниже описаниях предполагается, что единственный поставщик ресурсов продает товары нескольким поставщикам услуг. Этот случай можно обобщить для рынка, на котором торговля идет между многими поставщиками ресурсов и многими поставщиками услуг, но такую ситуацию мы пока не моделировали.

Рынок резервирования

Рынок резервирования позволяет поставщику услуг купить пакет товаров заранее, до того как он будет использован. Доля непроданных ресурсов поставщика ресурсов направляется на аукцион, и у участников есть возможность объявить свой спрос на пакеты товаров в различные периоды времени. Например, типичный запрос на покупку может формулироваться так:

«Я хочу приобрести права на 15 вычислительных единиц начиная с 18.00 в пятницу на 8 часов».

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

Механизмы рынка

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

«45 долл. за любые 50 вычислительных единиц между 17.00 в пятницу и 9.00 в понедельник».

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

Наличный рынок

На наличном рынке товары продаются на короткий срок для немедленного использования. Например, можно ежечасно проводить аукционы с периодом действия два часа. Цель наличного рынка — удовлетворить возникающий внезапно спрос за счет тех ресурсов, которые еще не проданы и так и будут простаивать, если не продать их немедленно. На аукцион выставляются все товары, не используемые в данное время. Как отмечалось выше, товары, купленные на рынке резервирования, можно выставлять на наличный рынок для немедленной продажи и использования.

Для наличного рынка также существует несколько возможных механизмов.

Агенты подачи заявок

Наряду с вопросом об организации самого рынка существует проблема инструментов, с помощью которых участникам было бы удобно объявить свой спрос. Например, на аукционе eBay для этого существуют посредники (proxy bidders), поскольку на практике людям неудобно постоянно отслеживать открытый аукцион, продолжающийся несколько дней; вместо этого участник может назвать посреднику максимальную цену, которую он готов заплатить, и посредник будет подавать заявки от его имени. Мы рассчитываем, что будет разработан механизм вспомогательных агентов, который не только избавит участников от утомительной процедуры подачи заявок, но и поможет принимать стратегические решения в сложных условиях аукциона.

Оптимизация доходов

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

Эта задача оптимизации относится к классу так называемых NP-полных (за исключением особых случаев), и мы полагаем, что будет весьма сложно сформировать аукционные механизмы, легко поддающиеся математической обработке. Однако для решения задач такого типа существуют мощные методы аппроксимации. Они чрезвычайно сложны, и в таких случаях обычно используются коммерческие решения (например, CPLEX). Можно также рассматривать методы аппроксимации с использованием множества агентов подачи заявок.

Арбитраж и спекуляции

Арбитраж — это использование разницы в ценах во времени и пространстве для извлечения прибыли, не связанного с риском; спекуляция — это покупка и продажа в расчете на получение прибыли.

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

Предотвратить арбитраж и спекуляцию почти невозможно; вопрос лишь в том, будут эти явления явными или скрытыми. На финансовых и товарных рынках они поощряются, и один из аспектов узаконивания этой деятельности — возможность ее отслеживать, управлять ею и извлекать из этого прибыль.

План-график

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

План-график считывается системой Resource Manager у поставщика ресурсов, и на его основании динамически выделяются физические ресурсы (рис. 6).

Проблемы

Потребители почти наверняка захотят указать свои предпочтения, касающиеся времени и ресурсов. Предпочтения по времени задают период времени, в течение которого может быть выполнена задача, и могут содержать предельное время ее завершения или максимальную допустимую стоимость. Предпочтения по ресурсам задают состав пакета — минимальный, оптимальный и максимальный набор ресурсов, необходимых для выполнения задачи.

Желательно найти набор пакетов с максимальной доходностью и как можно плотнее их «упаковать» в расписании, избегая при этом конфликтов ресурсов. Таким образом удастся добиться максимального дохода при заданном наборе потребительских предпочтений.

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

Задача планирования не менее сложна и тоже относится к NP-полным. Это означает, что расчет оптимального распределения ресурсов в соответствии с заданным набором потребительских предпочтений времени и ресурсов может оказаться чрезмерно сложным, и приходится прибегать к аппроксимации. В смежных областях для аналогичных задач существует множество целевых аппроксимаций, в которых на общую проблему налагается какое-либо ограничение. В данном исследовании применялись два подхода. Первый — сформулировать задачу для современного коммерческого нелинейного оптимизатора (CPLEX), чтобы выяснить пределы масштабирования этого подхода***. Второй подход — использовать множество параллельных открытых аукционов для приобретения пакетов товаров.

Микрооптимизация

Мы изучили использование рыночных подходов на примере микрооптимизации в центре обработки данных. Один из авторов (Эндрю Байд) исследовал процесс подачи заявок на ресурсы при условии, что их стоимость учитывала факторы местоположения, пропускной способности канала связи и температуры. Это довольно элегантный способ мягкого контроля над распределением ресурсов — например, стоимость ресурсов в стойках с низкой температурой меньше, чем в перегревающихся стойках. Другой автор (Колин Лоу) исследовал бартер между пользователями ресурсов, получив в целом совпадающие результаты.

Grid-вычисления

Распределенные вычисления (grid computing) во многом основаны на тех же принципах, что и коммунальные вычисления, и в будущем у них могут быть общая архитектура на основе стандартов и общие спецификации интерфейса. Однако акценты в этих двух случаях расставлены по-разному. Grid-вычисления — это в первую очередь среда, в которой ученые могут обмениваться ресурсами при решений исключительно сложных задач, и до сих пор это делалось коллегиально. Безусловно, понятно, что на каком-то этапе встанет вопрос платы за ресурсы, но об обязательном требовании получить максимальную отдачу от имеющихся активов речи пока не идет.

Подробный обзор завершенных и текущих исследований в области экономики распределенных вычислений приведен в диссертации Буйа [5].

Заключение

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

Основной целью нашей работы, проведенной в HP Laboratories в Бристоле, было увеличить доходность товаров (в данном случае товаром выступает ресурс, предоставляемый на некий промежуток времени). Мы рассмотрели способы увеличения доходности с точки зрения микроэкономической теории и обнаружили, что если уделять первоочередное внимание получению максимальной экономической отдачи, это будет влиять на принятие любого решения о распределении ресурса. Иными словами, нам не удалось понять природу коммунальных вычислений, не исследовав ее с позиций MBRA.

* Artur Andrzejak, Martin Arlitt, Jerry Rolia. Bounding the Resource Savings of Utility Computing Models. HP Laboratories Technical Report HPL-2002-339.

** Huberman & Clearwater, A Multi-Agent System for Controlling Building Environments, ICMAS 95. Эту работу имеет смысл читать вместе с анализом в статье Ygge & Akkermans, in Decentralized Markets versus Centralized Control: A Comparative Study, Journal of AI Research, 11, 1999.

*** Андерсон, Тенханен и Игге показали, что задачу определения победителя в комбинаторном аукционе можно сформулировать как смешанную задачу целочисленного программирования, и что коммерческое ее решение (CPLEX) способно конкурировать с лучшими специализированными алгоритмами. См. Integer Programming for Combinatorial Auction Winner Determination, Fourth International Conference on Multiagent Systems, Boston, 2000.

Дополнительные источники информации

Введение в микроэкономическую теорию

[1] Varian, H. R. (2002), Intermediate Microeconomics: A Modern Approach, 6th Edition, Norton.

[2] Katz, M. L. and Rosen, H. S. (1998), Microeconomics 3rd Edition, McGraw-Hill.

Применение рыночных методов

[3] Scott H. Clearwater (ed.), Market-Based Control: A Paradigm for Distributed Resource Allocation, World Scientific, Singapore 1995.

Введение в традиционную теорию планирования, в частности, для мелкосерийного производства

[4] Richard W. Conway, William L. Maxwell, Louis W. Miller, Theory of Scheduling, Dover 2003.

Предыдущие работы на тему рыночного планирования и экономики распределенных вычислений в целом

[5] Rajkumar Buyya, Economic-based Distributed Resource Management and Scheduling for Grid Computing, Ph.D Thesis Monash University, Melbourne, Australia April 12, 2002. Документ можно найти по адресу http://www.cs.mu.oz.au/~raj/thesis/.