HighLoad++ 2016 завершён. До встречи в 2017!

Профессиональная конференция разработчиков высоконагруженных систем

Москва, СКОЛКОВО,
7 и 8 ноября
Архив
2015
года
Конференция прошла в этом году уже в десятый раз и собрала 2500 участников. Мероприятие направлено на обмен знаниями о технологиях, позволяющих одновременно обслуживать многие тысячи и миллионы пользователей.

Хочу знать, сколько уникальных посетителей было на моём сайте за произвольный интервал времени в прошлом
BigData и машинное обучение

Доклад принят в Программу конференции
Qrator Labs

Выпускник МГТУ им. Баумана и Высшей Школы Экономики.
Инженер-разработчик в отделе исследований Qrator Labs.
@podshumok

Тезисы

Что нужно хранить для того, чтобы была возможность ответить на этот вопрос?

Для точного ответа нужно через равные интервалы времени сохранять множество посетителей сайта (пусть это для простоты будут IP-адреса), которых мы за прошедший интервал увидели. Понятное дело, что такой объём информации хранить нереально, а даже, если получится, придётся объединять большое количество множеств и считать элементы в том множестве, которое получилось в итоге. Это очень долго. Не спасает ситуацию даже переход от точных алгоритмов к приблизительным: гарантировать точность либо не получится, либо придётся использовать объём памяти и вычислительные ресурсы, сопоставимые с точным алгоритмом.

В 80-х годах появились первые вероятностные алгоритмы для приблизительной оценки количества элементов в множестве. При большом количестве уникальных элементов эти алгоритмы дают приблизительную оценку, которая отличается от истинного значения в (1±e), e<1 раз с вероятностью p>0.5. То есть они могут вернуть оценку, которая сильно отличается от истинного значения с некоторой вероятностью (1-p). Чем больше требуется точность, и чем меньше нужна вероятность ошибки, тем больше ресурсов требуют алгоритмы. Сохраняя внутреннее состояние одного из таких алгоритмов через равные промежутки времени в базе данных, мы можем оценить приблизительное количество уникальных посетителей не только за произвольный интервал времени, но и за произвольное объединение любых интервалов времени, например, мы можем посчитать общее количество уникальных IP, которых мы наблюдали в промежутке времени с 17:00 до 18:00 в течение последней недели.

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

Первый такой алгоритм был предложен в 2010 году. О нём-то мы и поговорим.

Бронирование билетов
Вы можете забронировать себе билеты уже сейчас — чем раньше Вы это сделаете, тем лучше, ведь цена на билеты постоянно растёт. Бронь вас ни к чему не обязывает, после бронирования у Вас будет пара недель на принятие решения об оплате.
ЗАБРОНИРОВАТЬ БИЛЕТЫ
Остались вопросы?
Спроси по телефону у контактного центра: +7 (495) 646-0768
Или напиши письмо в службу поддержки: support@ontico.ru
Rambler's Top100