?

Log in

No account? Create an account

Previous Entry | Next Entry

Adam Silberstein, Jeff Terrace, Brian F. Cooper, Raghu Ramakrishnan

http://www.google.com/search?q=pdf+selectively+materializing+user%27s+event+feeds

Feeding Frenzy: Selectively Materializing Users’ Event Feeds


Народ из Yahoo! Research и Princeton University разбирает проблему глобальной оптимизации расходования машинных ресурсов для поддержки передачи реал-таймовых фидов.

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

Теперь проблема: если есть быстрые поставщики фидов и огромное количество не очень часто посещающих свои фиды потребителей, то материализация фидов для такой толпы становится накладной операцией. Например, в твиттере есть такой пользователь «Ashton Kutcher», каждое сообщение которого расходится по «френдлентам» почти пяти миллионов подписчиков. То есть, каждое сообщение от него должно повлиять на миллионы материализованных представлений.

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

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

Авторы вводят понятие k,t-diversity. Неформально это можно понимать так: если приходит событие от Боба в последние t квантов времени, тогда мы не показываем более k событий от Алисы, ежели мы не показываем в это же время событие от Боба.

Рассматриваются две модели когерентности: per-producer и global (эта деталь неважна сейчасlionet). В модели per-producer, стоимость события для конкретного потребителя зависит от частоты актов потребления (рефреша страницы френдленты) и событий поставщика. В глобальной модели когерентности, стоимость события зависит от частоты актов потребления и суммы частоты событий от всех поставщиков событий для данного потребителя.

Что такое стоимость — это выраженная в CPU или в disk IO операциях сложность обслуживания события для системы.

Адаптивный алгоритм, который они предлагают ("правильный" knapsack алгоритм — NP-hard) выглядит примерно так:

We simply sort the pull edges by descending, and shift some number of top-ranked edges to push. Then, if our latency is higher than the SLA, we incrementally shift the top-ranked pull edges to push. If our latency is lower than the SLA, we incrementally shift the lowest-ranked push edges back to pull (note that we never shift edges to pull if they are assigned to push).


От себя:

В этой области всё интуитивно понятно было как оптимизировать и без статьи, но хорошо, что кто-то пошёл и чуть более формально отнёсся к проблеме. Опять же, экспериментальная проверка добавляет уровня доверия результатам статьи. Для эховцев будет небезынтересно поверхностно ознакомиться с параграфами начиная с 4.1 Architecture, в которых рассказывается, как конкретно делается система материализованных представлений на яховской PNUTS.

Tags:

Comments

( 3 comments — Leave a comment )
gliv
Apr. 28th, 2010 01:09 pm (UTC)
Где ты берешь ссылки на такие статьи?
Kirill A. Korinskiy [catap.ru]
Apr. 28th, 2010 08:29 pm (UTC)
Я лично читаю следующие фиды:

http://research.yahoo.com/publication/rss.xml
http://research.google.com/pubs/atom.xml
http://research.microsoft.com/rss/publications.xml
http://www.research.microsoft.com/rss/news.xml
http://www.hpl.hp.com/rss/techreports/techreport.xml
http://domino.research.ibm.com/library/cyberdig.nsf/rss
(Deleted comment)
( 3 comments — Leave a comment )

Profile

lionet
Lev Walkin
Website

Latest Month

December 2016
S M T W T F S
    123
45678910
11121314151617
18192021222324
25262728293031
Powered by LiveJournal.com
Designed by yoksel