Вероятностные алгоритмы: Вероятно, это работает (ЧАСТЬ 1)

rtb-98-rutarget-23-638Вероятностные алгоритмы (probabilistic algorithm) предназначены для решения задач, точное решение которых является невозможным или нерациональным (слишком дорогим, требующим слишком много времени и т.п.). В идеальном мире нам бы никогда не понадобились вероятностные алгоритмы. Для программистов, не знакомых с подобными алгоритмами, вероятностная концепция может показаться сомнительной: «Будет ли этот алгоритм действительно работать? Что если он по каким-то причинам будет работать неправильно? Как я смогу его отладить? Возможно, лучше просто отказаться от решения этой задачи или купить побольше серверов…»

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

Окружающий нас мир является вероятностным. По крайней мере, он слишком сложен, чтобы мы могли смоделировать его со 100% точностью. Сети, в особенности Интернет, также являются вероятностными системами. Мы не можем точно знать, будет ли конкретный пакет доставлен по назначению или нет. Еще менее определенно можно судить о пути, который пройдет пакет, перемещаясь из одной части мира в другую. Системы, работающие с асинхронными сетями или с сетями, где имеют место потери, неизбежно являются вероятностными. Нравится нам это или нет, вероятность повсюду вокруг нас.

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

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

Существует также и третий тип вероятностных алгоритмов. Алгоритмы этого типа ориентированы на работу с данными, которые являются случайными по своей природе. К сфере их применения относятся: GPS-мониторинг, беспилотные автомобили, сенсорные сети, системы самонаведения ракет. Например, сенсорные сети обычно пытаются предоставить информацию о сети в целом, несмотря на наличие только части данных. В случае беспилотных автомобилей и систем самонаведения данные представляют собой непрерывный поток. К тому моменту, когда программа завершает обработку данных, текущее состояние уже изменилось, и это необходимо учитывать. В этой статье мы не будем рассматривать алгоритмы данного типа, но вы можете подробнее узнать о них, прочитав материалы о фильтре Калмана (Kalman filter), а также об алгоритмах оценки (estimation algorithm) в целом.

Подсчет количества уникальных элементов

Широко распространена задача подсчета количества уникальных элементов (count-distinct problem) в потоке, который может содержать повторяющиеся элементы. К ней сводятся многие другие задачи. Например, сколько уникальных IP-адресов подключалось к серверу за последний час? Сколько различных слов в большом корпусе текстов? Какое количество уникальных посетителей побывало на популярном сайте за день? Сколько уникальных URL было запрошено через прокси-сервер?

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

... 
def count_distinct(stream): 
  seen = set() 
  for item in stream: 
     seen.add(item) 
  return len(seen) 
...

Как и во многих других случаях, трудности возникают при увеличении масштаба. С минимальными затратами можно подсчитать тысячу или даже миллион уникальных посетителей, IP-адресов, URL или слов. А как насчет 100 миллионов? Тоже приемлемо. А что если речь идет о 100 миллионах уникальных элементов на один сервер при наличии тысяч серверов? Теперь это уже становится интересным.

Теперь наша задача преобразуется к следующему виду: необходимо сформировать множества уникальных элементов для каждого из 1000 серверов, каждое из которых может содержать около 100 миллионов уникальных элементов, а затем подсчитать количество уникальных элементов в объединении этих множеств. Другими словами, мы имеем дело с распределенным вариантом задачи подсчета уникальных элементов. Рассмотрим наивное решение.

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

... 
def combined_cardinality(seen_sets): 
  combined = set() 
  for seen in seen_sets: 
     combined |= seen 
  return len(combined) 
...

Хотя наше наивное решение является вполне логичным, на практике этот подход обойдется высокой ценой. Для примера возьмем URL, средняя длина которого составляет 76 символов. В нашем случае один сервер обслуживает около 100 миллионов уникальных URL, следовательно, размер файла с их перечнем составит около 7,6 ГБ. Даже если каждый URL преобразовать в 64-битный хеш, размер файла составит 800 МБ. Это намного лучше, но не забывайте, что речь идет о 1000 серверов. Каждый сервер отправляет файл с перечнем уникальных URL на центральный сервер, следовательно, при наличии 1000 серверов функция combined_cardinality должна обработать 800 ГБ данных.

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

Представляем вам алгоритм HyperLogLog. Этот алгоритм реализует вероятностный подход к задаче подсчета уникальных элементов и базируется на двух следующих положениях: (1) вероятность того, что любой данный бит двоичного представления случайного числа равен единице, составляет 50%; (2) вероятность того, что совместно произойдут два независимых случайных события A и B, вычисляется по формуле P(A)*P(B). Таким образом, если вероятность равенства единице одного любого бита случайного числа составляет 50%, тогда вероятность равенства единице двух любых битов составляет 25%, трех – 12,5% и т.д.

Вспомним еще одно базовое положение теории вероятностей, согласно которому ожидаемое количество испытаний, необходимое для наступления события, вычисляется по формуле 1/P(событие). Следовательно, если P(один бит равен единице) = 50%, то ожидаемое количество испытаний равно 2. Для двух битов – 4, для трех битов – 8 и т.д.

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

Рассмотрим алгоритм подробно. Вначале необходимо хешировать все элементы исследуемого набора. Затем нужно подсчитать количество последовательных начальных битов, равных единице, в двоичном представлении каждого хеша и определить максимальное значение этого количества среди всех хешей. Если максимальное количество единиц обозначить n, тогда количество уникальных элементов в наборе можно оценить, как 2n. То есть, если максимум один начальный бит равен единице, тогда количество уникальных элементов, в среднем, равно 2; если максимум три начальных бита равны единице, в среднем, мы можем ожидать 8 уникальных элементов и т.д.

Подход, направленный на повышение точности оценки и являющийся одной из ключевых идей HyperLogLog, заключается в следующем: разделяем хеши на подгруппы на основании их конечных битов, определяем максимальное количество начальных единиц в каждой подгруппе, а затем находим среднее. Этот подход позволяет получить намного более точную оценку общего количества уникальных элементов. Если мы имеем m подгрупп и n уникальных элементов, тогда, в среднем, в каждой подгруппе будет n / m уникальных элементов. Таким образом, нахождение среднего по всем подгруппам дает достаточно точную оценку величины log2(n/m), а отсюда легко можно получить необходимое нам значение.

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

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

Вспомним теперь наше наивное решение. Мы имеем 1000 серверов и 100 миллионов уникальных URL на каждый сервер, следовательно, центральный сервер должен обрабатывать 800 ГБ данных при каждом выполнении нашего алгоритма. Это также означает, что 800 ГБ данных каждый раз необходимо передавать по сети. HyperLogLog меняет ситуацию кардинально.

Согласно анализу, проведенному авторами оригинальной публикации, HyperLogLog обеспечивает точность около 98% при использовании всего 1,5 КБ памяти. Каждый сервер формирует соответствующий файл размером 1,5 КБ, а затем отправляет его на центральный сервер. При наличии 1000 серверов, центральный сервер обрабатывает всего 1,5 МБ данных при каждом выполнении алгоритма. Другими словами, обрабатывается лишь 0,0002% данных по сравнению с наивным решением.

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

Продолжение следует…

Добавить комментарий

Ваш e-mail не будет опубликован.

закрыть

Поделиться

Отправить на почту
закрыть

Вход

закрыть

Регистрация

+ =