Статьи

Считать треугольники умнее: или, как победить крупных поставщиков данных в их собственной игре

Октябрь 28, 2018

Несколько месяцев назад, я обнаружил Vertica в  « Counting  Треугольники » -Статья  через  призматические . В блоге описан ряд критериев  подсчета  треугольников  в больших сетях.  Треугольник  обнаруживается всякий раз , когда вершина имеет две соседние вершины, которые также прилегают друг к другу. Представьте свою социальную сеть; если двое из ваших друзей также дружат друг с другом, вы трое определяете  треугольник дружбы .  Подсчет  всех  треугольников в большой сети довольно  трудоемкий процесс, В своей наиболее наивной форме алгоритм перебирает все вершины в сети, извлекая смежные вершины из смежных вершин. Если одна из вершин, смежных с последними, идентична исходной вершине, мы идентифицировали треугольник.

В статье Vertica показано, как выполнить оптимизированную реализацию вышеупомянутого алгоритма с помощью Hadoop  и их собственного   продукта базы данных Massive Parallel Processing (MPP) (оба работают на кластере из 4 узлов). Набор данных включает в себя  график социальной сети LiveJournal , содержащий около  86 миллионов взаимосвязей , в результате чего около  285 миллионов идентифицированных  треугольников . Как и следовало ожидать, решение Vertica сияет во всех отношениях ( считая  все  треугольники  за  97 секунд ), опережая решение Hadoop в  40 раз . Через несколько недель парни из Oracle опубликовали аналогичный  пост в блоге.используя   платформу ExaData , опередив результаты Vertica в  7 раз , заработав  14 секунд .

Хотя результаты Vertica и Oracle впечатляют, им требуется значительная аппаратная настройка из 4 узлов, каждый из которых содержит 96 ГБ ОЗУ и 12 ядер. Моя задача: победить поставщиков Big Data в их собственной игре, вычисляя  треугольники с  помощью более  умного  алгоритма  , способного обеспечить аналогичную производительность на  обычном оборудовании  (например, на моем MacBook Pro Retina).

1. Делать это умным способом

Живой журнал сетевой график социального , о 1.3GB в сыром размере, содержит около 86000000 отношений. Каждая строка в этом файле объявляет связь между  исходной  и  целевой вершинами  (где каждая вершина идентифицируется уникальным идентификатором). Предполагается, что отношения являются  двунаправленными : если человек 1 знает человека 2, человек 2 также знает человека 1.

0 1
0 7
0 8
0 9
1 2
1 5
2 0
2 5
2 7489

Давайте начнем с создания  строковой  структуры данных для хранения этих отношений. Ключ  каждой строки является  идентификатором исходной вершины . В строках  значения  является идентификаторами всех  целевых вершин ,  связанных с конкретной исходной вершиной.

 

  0 - 1 7 8 9
 


 

  1 - 2 5
 


 

  2 - 0 5 7479

С этой структурой можно выполнить простой алгоритм, как описано выше. К сожалению, итерация на четырех уровнях приведет к посредственной производительности. Давайте улучшим нашу структуру данных путем  индексации  каждого отношения через его  самый низкий ключ . Таким образом, даже несмотря на то, что файл LiveJournal объявляет отношение как « 2 0 », мы сохраняем отношение, назначая  2- значение  0- стрелке. (Порядок не имеет значения, так как отношения в любом случае двунаправлены.)

 

  0 - 1 2 7 8 9
 


 

  1 - 2 5
 


 

  2 - 5 7479

Вычисление  треугольников  теперь стало намного проще (и быстрее). Если ключ строки является частью  треугольника , его две смежные вершины  должны быть в его списке значений (как по определению, ключ строки является наименьшим идентификатором вершины из трех из них). Следовательно, нам нужно проверить, можем ли мы  найти ребра среди вершин,  содержащихся в каждой строке. Итак, для каждой строки мы перебираем ее список значений. Для каждого из этих значений мы извлекаем связанную строку и проверяем, является ли одно из ее значений частью исходного значения-  источника . Тем самым мы избавляемся от одного дорогого  для -loop. Тем не менее, объем расчетов, которые необходимо выполнить, по-прежнему близок к  2 млрд.!

 

  sourceValues = sourceRow.getValues();
 


 

  for (sourceValue : sourceValues) {
 


 

    targetValues : rows[sourceValue].getValues();
 


 

    for (targetValue : targetValues) {
 


 

      if (sourceValues.contains(targetValue) {
 


 

        triangles++;
 


 

      }
 


 

    }
 


 

  }

2. Сохранение отношений

Структура данных, как описано выше, сохраняется в  специальном хранилище данных,  которое мы разработали в Datablend для питания  similr -engine (поисковой системы химической структуры). Хранилище данных является  полностью постоянным  и оптимизировано для быстрого выполнения  операций на основе множеств  (пересечения, различия, объединения и т. Д.).  На моем MacBook Pro анализ 86 миллионов связей и создание соответствующей структуры данных в памяти занимает около  20 секунд . Дополнительные  4 секунды  требуются для сохранения всей структуры данных в самом хранилище данных. Около 25 секунд в общей сложности для эффективного хранения всех 86 миллионов отношений. Vertica и Oracle отмечают время, необходимое для сохранения набора данных Livejournal в соответствующих базах данных. Тем не менее, я предполагаю, что им также требуется несколько секунд для выполнения этой операции загрузки.

Как насчет  использования диска ? Настраиваемое хранилище данных Datablend занимает  второе место , требуя всего на 37 Мб больше по сравнению с версией Oracle Hybrid Columnar Compression.

 

  1. Oracle HCC Query High:   262 Mb
 


 

  2. Datablend datastore:     296 Mb (+13 %)
 


 

  3. Oracle HCC Query Low:    361 Mb (+38 %)
 


 

  4. Vertica:                 560 Mb (+113 %)

3. Расчет  треугольников

Установка Oracle (в кластере из 4 узлов, каждый с 96 ГБ ОЗУ и 12 ядрами) способна вычислить 265 миллионов  треугольников  за 14 секунд. Описанный выше оптимизированный алгоритм, работающий с пользовательским хранилищем данных Datablend, занимает первое место с тактовой частотой  9 секунд ! На моем MacBook Pro Retina подсчет полностью повторяется, и его пиковое использование составляет всего 2,11 ГБ ОЗУ!

 

  1. Datablend datastore:     9 sec                 (Macbook Pro Retina)
 


 

  2. Oracle:                  14 sec (+55 %)        (4-node cluster)
 


 

  3. Vertica:                 97 sec (+1077 %)      (4-node cluster)

4. Вывод

Пользовательское хранилище данных Datablend — это очень специфическое решение, предназначенное для  определенного диапазона вычислений больших данных . Он ни в коем случае не является настолько универсальным и универсальным, как решения для баз данных MPP, предлагаемые как Vertica, так и Oracle. Тем не менее, в статье делается попытка проиллюстрировать, что для выполнения определенных вычислений больших данных не требуется большой вычислительный кластер. Просто используйте наиболее подходящее / умное решение, чтобы решить проблему элегантно и быстро. Не стесняйтесь  обращаться к нам,  если у вас есть какие-либо вопросы, связанные с  Similr  и / или Datablend.

36
Share: