Авторы: C. Canali, M. Cjlajanni, R. Lancellotti
Перевод: Е.А. Филонова
Источник: C. Canali, Adaptive algorithms for efficient content management
in social network services / C. Canali, M. Cjlajanni, R. Lancellotti // University of Modena and Reggio Emilia http://weblab.ing.unimo.it/papers/cit10.pdf
Идентификация набора ресурсов, которые, как ожидают, примут большинство запросов в ближайшем будущем, а именно, горячем наборе,лежит в основании большинства стратегий управления контентом любой Веб-службы. Здесь мы рассматриваем службы социальной сети, которые открывают интересные новые проблемы для горячей идентификации набора. Действительно, социальные связи между пользователями и переменными шаблонами доступа пользователя с непрерывными операциями загрузки ресурса / скачивания определяют очень разный и динамический контекст для сохранения ресурсов. Мы предлагаем адаптивные алгоритмы, которые комбинируют прогнозирующую и социальную информацию, и динамично корректируют их параметры согласно непрерывному изменению характеристик рабочей нагрузки. Большой набор результатов эксперимента показывает, что адаптивные алгоритмы могут достигнуть производительности близко к теоретическим идеальным алгоритмам и, еще более важнее, они гарантируют стабильные результаты для широкого диапазона сценариев рабочей нагрузки.
Социальные сети представляют новый класс Веб-служб, которые поддерживают взаимодействие, обмен знаниями и разделение ресурсов среди сообществ онлайновых пользователей. Эти службы характеризуются новыми образцами доступа, где пользовательские операции не ограничены навигацией и загрузкой, но также и загрузкой ресурсов, можно вставлять короткие комментарии, создавать ссылки с другими пользователями. Эти новые образцы требуют модернизации традиционных стратегий эффективного управления контентом, таких как репликация, кэширование, упреждающая выборка и предварительная генерация ресурсов. Все эти стратегии должны определить подмножество ресурсов, которые, как ожидают, получат больше запросов в ближайшем будущем (так называемый горячий набор). Работа просто или главным образом на горячем наборе, а не на всем рабочем наборе позволяет провайдеру контента ограничивать число дорогих операций управления контентом на уровень сети,и хранение вычислительной мощности.
Большинство алгоритмов для горячей идентификации набора было предложено в так называемой сети 1.0 периода, и они в основном полагаются на информацию о прошлых доступах ресурсов. Они могут достигнуть хороших результатов в традиционных Веб-службах, где популярность ресурса медленно изменяется согласно известным образцам. С другой стороны, эти алгоритмы неподходящие, чтобы предсказать горячий набор в социальной сети службы, где присутствие пользователя генерировало социальные соединения среди пользователей, и приводят к довольно новым схемам доступа к ресурсам, таким образом вызывая частые и быстрые изменения в популярности ресурса. Предыдущее исследование от тех же авторов демонстрирует, что точность горячей идентификации набора в службах социальной сети может быть улучшена относительно традиционных решений, принимая во внимание прогнозирующие модели и характеристики пользователя в социальных соединениях. Тем не менее, остается открытым вопросом как объединить эффективно в состав неоднородной информации, такой как прогноз о будущих обращениях и социально связанных данных, характеризуемых различными временными зависимостями и распределениями вероятностей. Комбинация многократной информации должна улучшить точность горячей идентификации набора, и, еще более важно то, что должна гарантировать устойчивую производительность даже в очень переменном сценарии служб социальной сети. Основной вклад данной работы — предложение нового класса алгоритмов для горячей идентификации набора, которые используют адаптивные методы, чтобы автоматически настроить процесс слияния прогнозирующей и социально-обоснованной информации согласно характеристикам рабочей нагрузки с плавной регулировкой. Предложенные адаптивные алгоритмы оценены, чтобы проанализировать точность их горячей идентификации набора и устойчивость достигнутой производительности для большого набора параметров рабочей нагрузки. Наши эксперименты демонстрируют, что адаптивные методы - фундаментальный элемент для точной и стабильной работы в очень переменном контексте служб социальной сети. Предложенные алгоритмы могут достигнуть точности для горячей идентификации набора, которая является близко к идеальному теоретическому алгоритму и, еще более важна, достигнутая производительность, они нечувствительны к широкому диапазону параметров рабочей нагрузки. С другой стороны, мы показываем, что любая статическая комбинация прогнозирующих и социальных метрик может привести к результатам, которые неприемлемо нестабильны.
Остальная часть работы организована следующим образом. Раздел 2 описывает основные проблемы в идентификации ресурса горячий набор для служб социальной сети. Раздел 3 представляет предлагаемые алгоритмы. Раздел 4 описывает экспериментальные результаты. Раздел 5 обсуждает соответсвующую работу. Раздел 6 завершает работу с некоторыми заключительными комментариями.
Идентификация горячего набора представляет ключевую задачу для эффективных стратегий управления контентом. Его значение является производным от характеристик популярности ресурса с веб-интерфейсом и в службах социальной сети. Есть хорошая литература, демонстрирующая, что размерность, популярность и частота веб-ресурсов следуют за некоторым распределением закона о питании, особенно некоторым подобным Zipf распределением. Эти результаты, охватывающие 15 лет веб-характеристики подтвердили, что много пользовательских запросов относятся к ограниченному подмножеству популярных ресурсов. Горячая идентификация набора стремится выбирать ресурсы, которые, вероятно, получат большинство доступов в ближайшем будущем. Из-за изменений популярности мы можем полагать, что горячая идентификация набора - периодическая задача с периодом t. Идентификация горячего набора находится в базе типовых стратегий управления контентом, таких как преадаптация содержания, репликация, упреждающая выборка и доставка CDN.
Преадаптация содержания в службах социальной сети представляет необходимую задачу, которая получит еще больше важности в недалеком будущем. Увеличивающаяся диффузия поддерживающих мобильный Интернет устройств с маленьким дисплеем и ограниченной связью требует, чтобы адаптировали службы социальной сети и ресурсы к возможностям устройства. В вычислительном отношении дорогие операции, участвующие в адаптации содержания , как правило, осуществляется в автономном режиме на подмножества ресурсов и ограничивают непрерывную адаптацию только к менее популярным ресурсам, когда о них спросят. В этом контексте идентификация лучшего горячего набора играет фундаментальную роль потому что это может ограничить весомые задачи преадаптации самыми популярными ресурсами рабочего набора.
Стратегии репликации содержания широко используются в контексте географически распределенных инфраструктур. Тиражирование ресурсов от некоторого центрального сервера (ов) до узлов распределенной инфраструктуры улучшает масштабируемость, ограничивает риск узких мест и уменьшает связанные задержки сети. Горячая идентификация набора представляет основной элемент, чтобы определить, какие ресурсы должны быть тиражированы, чтобы максимизировать число запросов, которые могут быть удовлетворены, не получая доступ к центральному серверу при ограничении издержек для непротиворечивости копии.
Упреждающая выборка хорошо знают, что используется для уменьшения восприятия пользователем времени отклика в веб-контекстах. В основном этот метод состоит в продвижении ресурсов в кэш сервера и обратных прокси, чтобы уменьшить задержку в обслуживании следующих Веб-запросов. Ограничение работы упреждающей выборки к ресурсам, которые получат больше запросов в недалеком будущем, является необходимой задачей, чтобы избежать траты пропускной способности и пространства памяти в серверах и обратных прокси.
Доставка CDN позволяет провайдеру контента присваивать часть своих ресурсов к сторонней сети доставки контента для масштабируемой и высокоэффективной доставки. Инфраструктуры CDN поставляют популярные статические и мультимедийные ресурсы и были недавно применены к службам социальной сети, таким как YouTube. Привлечение этих сторонних инфраструктур обеспечивает весь рабочий набор, но не удобно из-за понесенной высокой стоимости, когда трафик направлен к CDN. Идентификация горячего набора может ограничить доставку CDN только с самыми популярными ресурсами. Несмотря на то, что горячий набор - основной принцип для нескольких стратегий управления контентом, новые схемы доступа и тенденции рабочей нагрузки, характеризующие службы социальной сети, уменьшают эффективность существующих решений для горячей идентификации набора. В 5 разделе мы демонстрируем преимущество слияния прогнозирующих методов и социальной информации для эффективной горячей идентификации набора. Однако определение лучшего подхода к прогнозирующему объединению и социальные метрики представляет нерешенный вопрос по следующим причинам:
Мы предлагаем различные методы, чтобы объединить predictiveand социальные метрики, и мы оцениваем интеграцию адаптивного управления, которое автоматически настраивает процесс комбинации, чтобы достигнуть устойчивой производительности в очень переменном контексте служб социальной сети.