Большие данные
Вы, наверное, слышали о понятии большие данные. Существуют самые разные определения, но, по сути, термин «большие данные» означает, что нам ничего не стоит получить огромное количество разной информации. И сразу возникает вопрос, как ее обработать. Например, банковские платежи совершаются через интернет или по электронным картам. Современный банк может без особых усилий собрать и сохранить данные о каждой трансакции.
Казалось бы, теперь мы можем ответить на любые вопросы. Какие продукты наращивают популярность? Насколько широко используются наши услуги, карты, банкоматы? Но, оказывается, разобраться в миллионах электронных записей не так уж просто, даже при наличии самых мощных компьютеров. Особенно если ответы нужны прямо сейчас!
Большие данные сами по себе не дают ответа на все наши вопросы. Их анализ влечет за собой множество проблем.
В этой главе мы расскажем только об одной такой проблеме. Звучит она совершенно элементарно, но для ее решения понадобилась новая и далеко не тривиальная математическая теория. Почему? Потому что, как и во многих других задачах с большими данными, ее наивное решение приводит к абсолютно невыполнимым требованиям к компьютерной памяти.
Чтобы было понятно, мы расскажем о самой проблеме чуть позже, в разделе . А сначала вкратце объясним, как устроена компьютерная память и почему, несмотря на ее мощь и колоссальный объем, она все-таки не всесильна.
Компьютерная память
Мы уже рассказали в , что вся информация в компьютере записывается в виде нулей и единиц. Каждый ноль и единица физически занимают крошечную ячейку памяти. Чтобы сохранить одну цветную фотографию на 3 мегабайта, понадобится
3×8×2 20 =25 165 824,
то есть больше 25 миллионов таких ячеек.
Обычно память работает на полупроводниках. Но мы будем просто считать (для нашего рассказа этого достаточно), что компьютерная память – это физическое устройство, где каждый символ (0 или 1) занимает место. Такие устройства могут быть самыми разными, например CD, DVD или флешка. В любом компьютере информация записывается на жесткий диск. Качество устройств памяти непрерывно улучшается. На жестком диске современных ноутбуков может умещаться, скажем, 320, а то и больше гигабайтов. Этого хватит, чтобы сохранить более ста тысяч цветных фотографий!
Если вам нужно еще больше памяти, можно хранить данные на удаленном сервере. Многие компании, в том числе Google и Amazon, предлагают подобные услуги. Это очень популярный сервис. Возможно, вы тоже что-то храните «в облаке».
У таких информационных гигантов, как Google и «Яндекс», есть свои дата-центры. Если вы хотите получить представление о том, как выглядят дата-центры «Яндекса», можете зайти, например, на сайт . Фактически дата-центры – это целые комплексы, которые занимают большие территории, где каждое строение либо заполнено серверами, либо предназначено для их энергоснабжения, охлаждения и обслуживания.
Компьютерная память сама по себе пока еще не является ограниченным ресурсом. Дисков и серверов мы можем построить достаточно. Вопрос в том, как воспользоваться всей этой информацией. И вот здесь возникают проблемы, потому что диск не в состоянии «сообразить» или «вспомнить». Чтобы извлечь информацию, компьютер должен найти нужную ячейку памяти.
На доступ к информации на жестком диске или сервере уходит какое-то время. Это можно представить себе примерно так. Предположим, вы читаете дома книгу на английском языке со словарем. Только словарь лежит в библиотеке! И вы бегаете в библиотеку и обратно за каждым словом, причем каждый раз аккуратно ставите словарь обратно на полку и в следующий раз заново ищете его по каталогу. Конечно, компьютер найдет информацию на диске быстрее, чем вы добежите до библиотеки. Но и операций он выполняет гораздо больше, поэтому сравнение вполне уместное.
Без сомнения, намного удобнее, когда словарь лежит рядом с вами на диване. Для этого у компьютера есть так называемая оперативная память. Информация считывается с диска, обрабатывается в оперативной памяти, после чего результаты снова сохраняются на диске, а оперативная память освобождается для следующей задачи.
Доступ к оперативной памяти происходит очень быстро, несравнимо с жестким диском. Но именно поэтому ее объем существенно ограничен. На вашем диване не поместится полбиблиотеки. Обычный ноутбук может предложить, например, 2 гигабайта оперативной памяти. Кстати, как раз из-за этого компьютер начинает «тормозить», если у вас открыто слишком много программ и документов.
Получается, что могущество компьютерной памяти сильно ограничено. У памяти на диске или сервере практически бесконечный объем, зато ограничена скорость доступа. А у оперативной памяти скорость феноменальная, зато объем очень маленький.
Какие последствия все это имеет для обработки больших данных? Оказывается, это фундаментальная и серьезная проблема даже для самых незамысловатых операций.
Раз, два, три, четыре, пять…
Рассмотрим небольшой пример. Допустим, банк выпустил пятьдесят кредитных карт с номерами 01, 02… 50. Всего было проведено 30 трансакций по картам с номерами:
Спрашивается: сколько клиентов воспользовалось кредитными картами?
Попробуйте сами ответить на этот вопрос. Каковы ваши действия? Поначалу все просто: 15 – это раз, 48 – два, 32 – три, 31 – четыре. Дальше снова 48, но эта та же карточка, поэтому мы ее не считаем. 27 – пять. В первом ряду всего 8 разных номеров. А вот во втором ряду уже начинаются затруднения. Попадался нам номер 02 до этого или нет? А 29? Или 45? Наша память не в состоянии это удержать! В результате до конца третьего ряда можно добраться только одним способом – сравнивать каждый номер со всеми предыдущими и ставить пометку, если он раньше не встречался. Ответ: 22 карты. Ниже мы выделили разные номера жирным шрифтом.
Теперь представьте, что эту задачу выполняет компьютер. Каким образом можно сравнить номер каждой карты со всеми предыдущими? Особенно если трансакций не тридцать, а три миллиона? И вот тут возникает проблема с памятью. Считывать все номера заново с жесткого диска – непозволительно долго. А оперативная память переполнится гораздо раньше, чем мы дойдем до середины.
Что же получается? При наличии полных данных и самых мощных компьютеров мы не в состоянии подсчитать, сколько человек воспользовалось кредитными картами?! В принципе да, не в состоянии. И конечно, кредитные карты – это всего лишь пример. На самом деле мы вообще не в состоянии ничего посчитать!
У вас на сайте есть счетчик уникальных посещений? Скорее всего, он считает приблизительно.
Это и есть принципиальный подход к решению задачи о подсчете. Если точный ответ нам физически недоступен, нужно найти как можно более точный приблизительный ответ, который при этом использует минимальное количество памяти.
Общее количество заходов на сайт, кстати, можно сосчитать и точно, потому что в этом случае не нужно запоминать каждое посещение, достаточно помнить, сколько их было. Число друзей на «Фейсбуке» тоже подсчитывается точно, потому что они не повторяются. Приблизительное решение понадобится для подсчета количества разных объектов, когда один и тот же объект может появиться несколько раз.
Оговоримся, что в примере с кредитными картами проблему можно решить и по-другому, с абсолютной точностью. Например, если выстроить все номера в порядке возрастания, то сосчитать разные номера будет гораздо проще. Очевидный недостаток состоит в том, что обычно к нам поступают неупорядоченные данные и их сортировка представляет собой отдельную, непростую задачу, которой посвящена масса математической литературы.
Еще можно заранее создать такую структуру данных, где на каждого клиента было бы заведено электронное досье. Тогда совсем нетрудно пройтись по всем досье и посчитать, сколько из них содержит трансакции по кредитным картам. К каждому досье понадобится обратиться всего раз, и это много времени не займет. Но данный способ тоже работает не всегда. Например, как посчитать количество магазинов, в которых клиенты воспользовались кредитной картой? Наверняка у банка нет досье на каждый магазин.
Проблема подсчета очень актуальна, особенно в контексте больших данных. Сколько посетителей заходит на наш сайт из разных регионов России? Сколько школьников в этом году подали заявления в вузы? Сколько людей обсуждают в социальных сетях нашу партию? Сотрудники Google в своей статье пишут, что в их систему хранения и обработки данных поступает свыше пяти миллионов подобных запросов в день! Регулярно встречаются запросы, предполагающие подсчет более миллиарда объектов. В этой статье также приводится цифра: в среднем около ста таких запросов в день. Из-за ограничений памяти получить точный ответ на подобный запрос абсолютно нереально.
Как найти хорошее приближение, практически ничего не запоминая? У задачи подсчета есть несколько решений. Сходу такое решение нельзя придумать, но понять основные идеи не так уж сложно.
Как решается задача подсчета
Мы воспользуемся блестящим блогом и начнем с метода К-Minimum Values [K-минимальные величины]. Идея очень проста. Допустим, значения, которые надо посчитать, равномерно разбросаны в каком-то интервале. В нашем примере с номерами карточек от 01 до 50 и их непредсказуемым использованием это предположение вполне разумно. Теперь давайте не будем запоминать все увиденные значения, а запомним лишь несколько самых маленьких.
Возьмем снова пример с кредитными картами, где трансакций было 30, а разных карт – 22. Мы можем запомнить, скажем, всего пять самых маленьких значений. В данном случае это номера 01, 02, 05, 08 и 10. Пять значений в интервале от 1 до 10. Значит, сколько разных значений мы встретим в интервале от 1 до 50? Интервал в пять раз длиннее, значения разбросаны равномерно. Стало быть, всего значений будет
5 (значений) × 5 (интервалов) = 25 (значений)
примерно двадцать пять. Поскольку число 10 находится на самой границе интервала, делается коррекция. Для большей точности в данном случае пользуются формулой
Это, конечно, не равняется точному ответу 22, но достаточно близко к нему. При этом нам пришлось запомнить только 5 значений, а не 22.
Хранить в оперативной памяти всего несколько самых маленьких значений уже вполне реально, но по-прежнему не идеально. Чем больше значений мы сохраняем, тем выше точность, и для действительно высокой точности значений нужно хранить довольно много.
Можно ли сделать лучше? Оказывается, можно. Настоящую революцию в мире счетчиков совершил французский математик Филипп Флажоле. Его результаты были опубликованы в 2007 году в статье, а сейчас широко применяются в системах обработки данных, в том числе BigQuery Google и Redis компании Amazon.
HyperLogLog-счетчики
Филипп Флажоле и соавторы предложили новый метод подсчета под названием HyperLogLog.
LogLog означает, что по сравнению с числом объектов нам нужно очень маленькое количество оперативной памяти. Под LogLog здесь понимают двойной логарифм по основанию 2, и это на самом деле очень маленькое число. Например, при миллиарде объектов двойной логарифм будет
log 2 (log 2 (1000 000 000)) ≈ 4,9,
то есть порядка 5 битов памяти – всего пять нулей и единиц!
Приставка Hyper использована тоже не просто так. Идею подобного метода Флажоле предлагал и раньше, но предыдущие версии давали слишком грубые результаты.
Метод HyperLogLog сильно улучшил точность, что позволило применить его на практике.
Как и в методе К-Minimum Values, Флажоле исходил из предположения, что записи в базе данных можно представить в виде разбросанных случайным образом чисел. На практике это действительно так, потому что каждой записи, будь то число, имя, адрес или название, присваивается так называемое хеш-значение. Это последовательность из нулей и единиц одинаковой небольшой длины. Если две записи совпадают (например, одно и то же название повторяется два раза), то и их хеш-значения совпадают. Например, хеш-значения длины 8 для разных веб-магазинов могут выглядеть примерно как в табл. 7.1. Мы выделили жирным шрифтом название, которое повторяется два раза:
Таблица 7.1. Фиктивный пример хеш-значений веб-магазинов
На практике обычно применяют хеш-значения длины 32 или 64. Хеш-значения генерируются с помощью специальных программ, так называемых хеш-функций, весьма нетривиальным образом. Усмотреть связь между изначальной записью и ее хеш-значением фактически невозможно. Поэтому можно считать, что хеш-значения присваиваются случайным образом. И метод К-Minimum Values, и метод Флажоле пользуются не самими записями, а их хеш-значениями.
Напомним, что по методу К-Minimum Values нужно запомнить несколько самых маленьких хеш-значений. Флажоле пошел еще дальше, предложив запоминать только число нулей в начале хеш-значения.
Для примера опять возьмем хеш-значения длины 8. Допустим, нам попалось хеш-значение
00001011
Последовательности, у которых в начале ровно четыре нуля, встречаются не очень часто, в среднем одна на 32. Если мы наткнулись на такую последовательность, то можно предположить, что в среднем мы видели 32 разных хеш-значения, то есть число объектов – примерно 32. Что, если мы видели еще больше нулей, скажем пять?
00000101
Такие последовательности еще более редки, одна на 64, то есть объектов примерно 64! Разве не гениально?
Идея очень простая. Чем больше нулей, тем реже встречаются такие хеш-значения. Если какому-то объекту случайно досталось очень редкое хеш-значение, значит, объектов было много.
Запомнить при этом нужно только одно число – самое большое количество нулей, которое мы видели, например 4. Для этого достаточно минимального объема памяти. Если нам попалось хеш-значение, у которого нулей больше, например 5, мы выкидываем из памяти 4 и запоминаем 5.
Очевидно, что этот метод очень приблизительный. Например, хеш-значение с четырьмя нулями нам могло встретиться и в самом начале. Столь грубые оценки для практики не годятся.
В HyperLogLog для улучшения точности добавлено много хитрых приемов. Хеш-значения разбиваются на регистры, оценка считается в каждом регистре отдельно, а потом усредняется специальным образом. Кроме этого, учитывается коррекция, когда объектов очень мало или, наоборот, очень много. Подробно об этом можно прочитать в блоге. Там можно даже запустить программу и посмотреть, как метод работает.
На практике стараются достичь еще более высокой точности. Собственно, об этом статья сотрудников Google, о которой мы упоминали выше. Она так и называется «HyperLogLog на практике». Например, авторы уделили особое внимание коррекции при маленьком числе объектов. Грубо говоря, если клиент в состоянии посчитать объекты вручную, то и компьютер должен давать абсолютно правильный ответ.
Так грубая, почти нахальная оценка Флажоле привела к решению задачи подсчета, решению с оптимальным балансом между эффективностью и точностью.
Четыре виртуальных рукопожатия
Помимо того что задача подсчета важна сама по себе, она находит и другие, совершенно неожиданные применения.
Все мы знаем, что мир тесен. Знакомишься с человеком, и тут же находятся общие знакомые или хотя бы знакомые знакомых. Многих исследователей интересовал вопрос, насколько тесен виртуальный мир социальных сетей.
Вопросы подобного рода имеют длинную историю. В конце 1960-х годов социолог Стэнли Милграм провел свой знаменитый эксперимент. Он раздал случайным людям в штатах Небраска и Канзас письма, адресованные брокеру из Бостона. Географически и по роду занятий эти люди были достаточно далеки от адресата. По правилам эксперимента, участники могли переслать письма только своим знакомым, которые должны были передать их дальше, своим знакомым, и так далее, пока они в конце концов не достигнут адресата. Из 296 писем большинство затерялось в дороге, но 64 письма дошли-таки по назначению. При этом оказалось, что цепочка, связывающая совершенно незнакомых людей, на удивление короткая. В среднем отправителя и адресата разделяло всего 5 человек! На рис. 7.1 мы схематически изобразили, как письмо пересылалось всего шесть раз, через пять промежуточных человек.
Рис. 7.1. Схематическое изображение эксперимента Стэнли Милграма. Участники могли переслать письмо только своим знакомым. Письмо от отправителя до адресата пересылалось 6 раз, через 5 разных человек
Так родилось понятие «шести рукопожатий». Если вы пожмете руку всем своим знакомым, ваши знакомые пожмут руку своим знакомым и так далее, то понадобится всего шесть рукопожатий, чтобы соединить вас с любым человеком на Земле!
Эксперимент Милграма не идеален, неслучайно столько писем затерялось в дороге. Но в то время просто не было другого способа выяснить, кто, с кем и через кого знаком. Зато сейчас таких данных сколько угодно.
Чтобы провести подобный эксперимент в «Фейсбуке», не нужно даже беспокоить участников. На сервере сети хранится полная информация, кто с кем дружит. Остается только вычислить количество «виртуальных рукопожатий», отделяющих одного пользователя от другого. Можем ли мы это сделать? Именно такой вопрос задали научные сотрудники «Фейсбука» профессору Миланского университета Себастьяно Винье.
И Себастьяно, и сотрудники социальной сети понимали, что это колоссальная задача. Неслучайно она не была решена раньше. У «Фейсбука» свыше 700 миллионов активных пользователей, то есть более
пар пользователей. И нужно вычислить длину цепочки для каждой пары! Но дело не только в этом. Ключевая проблема – опять же в количестве оперативной памяти, и возникает она потому, что между двумя пользователями не одна, а несколько цепочек разной длины. Для примера посмотрим на маленькую социальную сеть на рис. 7.2. А отделяет от В одно рукопожатие или два – через Г. Разных цепочек очень много, потому что друзья друзей зачастую наши друзья. В социальных сетях это известный, проверенный и доказанный феномен. При этом нас интересует самая короткая цепочка.
Рис. 7.2. Социальная мини-сеть. Кружками с буквами обозначены пользователи, линия между двумя пользователями означает, что они друзья. Мы обозначили пользователя А светло-серым цветом, а его друзей – серым. Темно-серым цветом обозначены пользователи, которых от А отделяют два рукопожатия
Компьютеру совсем нетрудно считать с диска всех «друзей друзей» пользователя А. Но только некоторых из них отделяет от А одно рукопожатие, а некоторых – два. Например, на рис. 7.2 и В, и Ж – это друзья друзей А. Но В друг А, а Ж – нет. Как определить, что Ж на расстоянии двух рукопожатий? Только одним способом – запомнить всех друзей А. Именно так работает самый распространенный метод под названием поиск в ширину.
Если теперь добавить всех «друзей друзей друзей», а потом их друзей и так далее, то нужно запоминать всех, кого мы видели на расстоянии один, два, три… После пяти-шести шагов мы уже видели практически всех пользователей сети. Держать в оперативной памяти 700 миллионов имен, или разных чисел, – ну просто абсолютно нереально!
Сотрудники «Фейсбука» поверили в успех, потому что Себастьяно Винья и его коллеги придумали абсолютно иной способ подсчета числа рукопожатий. Они заметили, что самая главная проблема – необходимость запоминать увиденных пользователей – совершенно аналогична задаче о подсчете. А последнюю можно решить методом HyperLogLog.
Для интересующихся читателей ниже во врезках мы объясняем основные идеи с помощью примера на рис. 7.2. Этот текст не требует математической подготовки, но, если вы не хотите вдаваться в подробности, можете его пропустить.
Применение HyperLogLog -счетчика для подсчета числа рукопожатий
Хорошая новость: можно очень легко вычислить всех друзей любого пользователя.
Присваиваем хеш-значение каждому пользователю. Запускаем счетчик HyperLogLog и просматриваем пользователей начиная с А. На каждом шаге HyperLogLog будет сообщать, сколько всего разных пользователей мы видели. Оказывается, это все, что нам нужно.
Начнем с пользователя А. Это один пользователь, на расстоянии ноль рукопожатий от самого себя. Теперь посмотрим на его друзей:
Б В Г Д Е,
HyperLogLog сообщит нам, что всего с момента запуска мы видели 6 пользователей. Минус А, получаем 5 пользователей на расстоянии одного рукопожатия. Теперь к А и его друзьям добавляем всех тех, кто дружит с друзьями А:
друзья Б: А, Ж,
друзья В: А, Г, Ж, З
друзья Г: А, В, И
друзья Д: А, Е
друзья Е: А, Д.
После этого HyperLogLog сообщит, что всего с момента запуска мы видели 9 разных пользователей. Вычитаем А и число его друзей, получается
9 − 1 − 5 = 3
пользователя на расстоянии двух рукопожатий от А. Заметьте, что нам не нужно запоминать самих друзей А, а только их количество!
В данном случае больше пользователей у нас нет. В реальности процесс продолжается. На третьем шаге мы добавляем всех «друзей друзей друзей». После этого HyperLogLog опять сообщает, сколько разных пользователей мы видели до сих пор. Вычитаем из этого числа количество пользователей на расстоянии ноль, один и два и получаем число пользователей, которых от А отделяют ровно три рукопожатия. И так далее.
Процесс будет завершен, когда мы увидим всех пользователей сети. Как вы помните, HyperLogLog держит в памяти лишь максимальное число нулей в хеш-значении. В дополнение к этому надо запомнить только число пользователей на расстоянии одного, двух, трех и так далее рукопожатий. Это тоже занимает очень скромный объем оперативной памяти.
HyperLogLog требует так мало памяти, что процесс можно запустить для всех пользователей одновременно и в результате получить общее число пар на расстоянии одного, двух, трех рукопожатий и так далее. Конечно, результаты приблизительные, но их точность очень высокая.
Оказалось, что двух пользователей «Фейсбука» в среднем разделяет не шесть, а всего 4,74 рукопожатия! Статья Себастьяно Виньи и соавторов быстро обрела известность в научном мире и за его пределами. О ней писали ВВС и New York Times. Результаты уже сейчас попали в популярную литературу и специальные учебники. Виртуальный мир оказался еще теснее, чем реальный – тот, в котором мы живем!
Филипп Флажоле
Филипп Флажоле умер в 2011 году, когда работа над внедрением HyperLogLog была в самом разгаре. Блог под названием «HyperLogLog – краеугольный камень инфраструктуры больших данных» {26} был написан в 2012 году. Статья {27} о 4,74 виртуальных рукопожатий в «Фейсбуке» вышла в том же 2012 году, а статья сотрудников Google {28} – в 2013-м. Система Redis внедрила HyperLogLog в 2014 году. В честь Филиппа Флажоле команды HyperLogLog начинаются с его инициалов PF.
Нам неизвестно, успел ли Флажоле узнать, что его результаты уже стояли на пороге широкого внедрения. Мы закончим последними фразами из блога {29} , где автор подробно и с большим энтузиазмом объясняет HyperLogLog широкой технической публике:
…Мне очень жаль, что я не был знаком с ним лично. Я уверен, что его труды будут жить дальше, но наука и индустрия, безусловно, потеряли выдающийся интеллект. Продолжай считать, Филипп, мы на тебя рассчитываем!