Представим задачу: хотим определить, какие пользователи чаще всего лайкали на стене заданного сообщества. Т.е. нужно сначала получить список постов на стене через wall.get, а потом для каждого поста вызывать likes.getList, последовательно получая список id людей.

И, получив этот список, нужен ответ в виде соответствий id ↔ count, отсортированный по count. Count будет обозначать количество лайков. Например:

input: 283, 42, 9001, 9001, 42, 854, 42, 130, 854
criteria: countMin = 2, countMax = Inf

result: 42 ↔ 3, 9001 ↔ 2, 854 ↔ 2

Другой пример: есть список групп, и мы хотим определить, какие люди состоят в наибольшем числе из них. Т.е. для каждой нужно вызывать groups.getMembers, аналогично скачивая список id, и запустить тот же самый алгоритм. Только count будет обозначать, в скольких сообществах состоит человек.

Итак, имея (последовательно скачивая) id пользователей, нужно возвратить список id ↔ count с сортировкой по count.

Сложность — в объемах. Количество просмотренных id может быть миллионы, десятки миллионов. Они скачиваются сотнями запросов к VK API в течение нескольких минут, а в качестве результата нужно получить только N самых топовых.

При разработке на Node.js первым в голову приходит такой вариант реализации:

var ids_counts = {}

// строим гистограммы (bin'ы)
function increment( id ) {
    if( id in ids_counts )
        ids_counts[id]++
    else 
        ids_counts[id] = 1
}

// упорядочиваем объект "{ id: count, ... }" по count
function toSortedCounts() {
    var arr = []
    for( var id in ids_counts )
        arr.push( { id: id, count: ids_counts[id] } )
    arr.sort( (a, b) => b.count - a.count )
    return arr
}

Т.к. object — структура без отношения порядка, а нам нужна сортировка по count, то для этой сортировки приходится делать массив [ {id, count} ], каждый элемент которого опять же js-объект.

Данное решение плохо тем, что хранит все id в памяти, причем 2 раза; в итоге при обработке 10 миллионов id потребляется больше 1 ГБайт памяти со временем работы около 40 секунд.

Замена js object на Map невозможна, т.к. в V8 ограничение на размер Map в 16 млн элементов, а нужно больше.

Попытка написать аналог с тем же подходом, но на C++ контейнерах map / unordered_map успеха не приносит. Чуть быстрее, чуть меньше памяти, но качественно — то же самое. Непригодно в production для обработки больших данных.

Плюс к этому, заранее не известно, сколько id придет на вход, т.е. невозможно предсказать, сколько памяти займет процесс во время работы. А т.к. все id хранятся в памяти в течение нескольких минут (пока скачиваются из VK и сортируются), то, запустив несколько ресурсоемких операций на одном сервере, каждая из них будет съедать все больше и больше памяти, что приведет либо к уходу в своп, либо к остановке процесса.

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

Ниже предлагается алгоритм, который был разработан специально для решения задачи сортировки гистограмм, реализован на C++ отдельно от Node.js и успешно используется в рабочей версии проекта.

• в сервеном javascript вообще не хранится хеш id ↔ count (объект ids_counts в коде выше)

• вместо этого id последовательно сохраняются в файл по мере их поступления (он автоматически удалится при завершении работы Docker-контейнера с worker’ом)

• причем сохраняются они в бинарном little endian формате с синхронной записью, используя один кольцевой буфер

• после формирования этого файла запускается C++ бинарник sort-mapcount, который:

• читает этот файл напрямую в память по int* – без дополнительных преобразований получается непрерывный набор чисел

• сортирует эти числа в несколько потоков через openmp

• первым последовательным проходом определяет количество уникальных элементов size (т.к. массив сортированный, это делается без хеш-таблиц)

• выделяет память size × 8 байт

• вторым последовательным проходом заполняет этот массив: старшие 4 байта – это count, младшие – id

• сортирует этот массив как 8-байтные числа, что эквивалентно сортировке по count

• последовательным проходом по уже отсортированному по старшим 4-м байтам массиву определяет индексы start и end для выполнения условия countMin ≤ count ≤ countMax

• последовательно генерирует выходные данные json или tsv: просто записывая туда младшие и старшие 4 байта каждого элемента этого массива

• в итоге tsv-файл можно отправить в базу через COPY, а json-файл импортировать обратно в Node.js

Код на C++ для данной задачи работает действительно быстро и потребляет чуть больше, чем 4 * Ntotal + 8 * Nuniq байт. Например, на файл из 100 миллионов id, где примерно 10 миллионов уникальных — обрабатывается за 5.2 секунды (вместе с сортировкой и генерацией выходного json) и резервирует 500 МБайт памяти, в то время как javascript-вариант потребляет 2.5 ГБайт памяти и работает больше минуты.

Таким образом, потребление памяти хоть и есть, но оно пиковое, в течение нескольких секунд работы C++ программы, а не на всём протяжении исполнения процесса, поэтому при балансировке процессов его можно не учитывать.

На самом деле, все чуть сложнее. Нужно не просто соответствие id ↔ count, а множественное соответствие: id ↔ count1, count2, count3, с сортировкой по сумме count'ов.

Пример: мы анализируем лайки, репосты и комментарии. И хотим отсортировать все просмотренные id по сумме активностей, но тем не менее разделив лайки, репосты и комментарии на отдельные числа.

Именно эта задача и решается приведенным кодом.

Для этого:

• при скачивании id через VK API создается и заполняется не один bin-файл, а несколько (по числу колонок)
• разделяются два понятия:
  • гистограмма — массив 8-байтных чисел, отсортированный по id (младшим четырем байтам);
  • mapcount — тот же массив, но отсортированный по count (старшим четырем байтам) или по sum при более чем одной колонке;
• из каждого bin-файла создается в памяти одна гистограмма
• общее количество size уникальных id последовательным проходом по всем ним одновременно
• отсортированные по id гистограммы сливаем в массив из size элементов вида id ↔ count1, ..., count_k−1, sum
• получившуюся гистограмму переводим в mapcount сортировкой по sum
• как и в предыдущем пункте, обрезаем по условию диапазона и формируем tsv/json файлы с нужным количеством колонок

• sort-mapcount.cpp — входная точка; парсит аргументы командной строки и в зависимости от количества входных bin-файлов выбирает дальнейшую ветку
• для 1, 2, 3 и 4-х колоночных гистограмм реализованы отдельные алгоритмы слияния (результат более качественный и быстрый, чем если для произвольного N) (см. mc-items.hpp и mc-merging.hpp)
• при компиляции флаг -fopenmp (см. Makefile) определяет, что будет использоваться параллельная сортировка гистограмм __gnu_parallel::sort вместо обычной std::sort
• mc-output.hpp — вывод результирующего mapcount в json/tsv; для вывода используется std::ofstream (почему-то с ними работает быстрее, чем с fwrite с собственными строковыми буферами)