Анализ данных о посещаемости Web-сайтов
Администраторы Web-сайтов часто используют журналы регистрации посещений Web-страниц, чтобы понимать поведение своих пользователей. Это позволяет изменять структуру Web-сайта с тем, чтобы улучшить его показатели. Например, Web-рекламодателям часто требуется знать среднее число кликов, выполяемых пользователями от входа на начальную страницу конкретного Web-сайта до попадания на страницу с рекламой. Web-издателям может быть интересно среднее число статей, прочитываемых посетителями, которые начинают свою сессию с посещения раздела "Политика" и попадают, в конце концов, в раздел "Развлечения".
Если имеется отношение Clicks(user_id int, page_id int, category_id int, ts timestamp), в котором сохраняется информация о пользователе, идентификатор страницы, на которую перешел этот пользователь, и время, когда он это сделал, то каково среднее число страниц, посещенных пользователем в промежутке времени между посещением некоторой страницы категории X и некоторой страницы категории Y? Мы называем клик, приведший на страницу категории X, начальным кликом, а клик, приведший на страницу категории Y, – конечным кликом. Мы сгенерировали искусственный набор данных кликов с использованием SQL/MR-функции над строками, которой задается некоторая таблица пользователей, и из каждой строки этой таблицы получается набор строк кликов соответствующего пользователя. Для каждого пользователя генерировалась 1000 кликов со случайными значениями столбцов ts, category_id и page_id (во всех случаях использовалось равномерное распределение). На каждый узел пришлось пятьдесят миллионов строк.
Рис. 9. Запрос на чистом SQL, обеспечивающий ответ на вопрос о характере посещений Web-сайта.
Для ответа на сформулированый выше вопрос мы сначала написали показанный на рис. 9 запрос на чистом SQL. В этом запросе сначала соединяются каждый клик категории X с каждым кликом категории Y одного и того же пользователя, если клик категории Y был произведен позже клика категории X. Над результатом этого подзапроса выполняется SELECT DISTINCT, в результате которого остаются только те конечные клики, которые были произведены в самое близкое время после начальных кликов.
Далее производится проекция этого результата на временные метки начального и конечного кликов и подсчитывается число кликов того же пользователя за этот промежуток времени. Наконец, это число усредняется для всех отобранных ранее пар начального и конечного кликов.
Рис. 10. SQL/MR-запрос, обеспечивающий ответ на вопрос о характере посещений Web-сайта.
После этого мы написали SQL/MR-функцию, обеспечивающую ответ на тот же вопрос. Запрос с вызовом этой функции показан на рис. 10. Мы разделяем входные данные по значениям столбца user_id и упорядочиваем каждый раздел по значениям ts. Кроме того, у функции имеются разделы аргументов, в которых указываются категория начальной страницы, категория конечной страницы и показатель, значения которого требуется вычислить (в данном случае, длина – length). После разделения и сортировки входных данных эта функция производит один проход по данным о посещениях сайта. Каждый раз, когда функция встречает строку с данными о посещении страницы начальной категории, она запоминает позицию этой строки, а когда ей встречается строка с данными о посещении страницы конечной категории, функция производит строку, содержащую разность между позицией конечной страницы и позицией начальной страницы.
Рис. 11. Горизонтальная масштабируемость SQL/MR на аппаратном кластере и на кластере, размещенном в Amazon EC2.
Оба описанные выше запроса выполнялись в СУБД nCluster на "физическом" кластере с 2, 5, 10 и 20 узлами, а также на кластере, размещенном в Amazon EC2, с 2, 4, 8, 16 и 32 узлами. Объем данных в каждом узле оставался неизменным. На рис. 11 показана линейная горизонтальная масштабируемость SQL/MR. При росте размера кластера, пропорциональном росту объема данных, время обработки запроса остается неизменным. Поскольку почти все вычисления в данном случае могут выталкиваться на рабочие узлы, такое поведение было вполне предсказуемым.
Рис. 12. Сравнение структур времени выполнения аналитических запросов данных о посещении Web-сайта, представленных на чистом SQL и с использованием SQL/MR.
Мы также сравнивали время выполнения SQL/MR-запроса с временем выполнения запроса, представленного на чистом SQL. SQL/MR-запрос выдал требуемые данные почти в девять раз быстрее SQL-запроса. На рис. 12 показана структура временных затрат на выполнение обоих запросов. Заметим, что время выполнения SQL/MR-запроса в равных долях тратится на сортировку входных данных (в соответствии с аргументами разделов PARTITION BY и ORDER BY) и на реальную обработку данных. При выполнении запроса на чистом SQL основное время тратится на выполнение соединения таблицы с самой собой и на локальное удаление дубликатов (local DISTINCT), а остальное время уходит на глобальное устранение дубликатов (global DISTINCT) и заключительное соединение.
