Сравнение массивов 5М+ значений?

Question

[キム ファイブプラス]

Столкнулся с проблемой «нехватки» памяти при попытке выполнить array_diff для двух многомиллонных массивов. Кушается порядка 1200Мб при такой операции. Про время выполнения вообще молчу.
Один массив набирается из БД, второй массив приходит с удаленного сервера.
Подскажите кто как решил бы данный вопрос.
Запись в файл получается крайне громоздкая и затем достаточно геморно получить обратно разницу в нужном формате.

UPD 14/01/2017
В общем пока что решил вопрос редисом.
Если приходящий массив новый, записываю его сразу же листом в редиску, без сортировки.
Он будет являться эталонным.
При обновлении создаю еще один ключ с постпфиксом "_new".
Сравниваю поочередно два ключа через sDiff. В итоге в пых возвращаются два массива Delete, New.
Соответственно значения массива New добавляю в эталонный список, значения Delete удаляю из этого же списка.
Дропаю ключ "_new", в мускул произвожу те же самые записи, только в разные таблицы, для вывода юзеру.
Теперь осталось выяснить нагрузку на HDD от редиски :) Но пока что все летает.
Как появится возможность, буду переписывать нафиг все на пайтон.
Всем спасибо за помощь.

Comments

[Максим]

Массивы отсортированные?

[キム ファイブプラス]

Максим: Приходящий сырой, при записи сортирую.
В базе скажем под id1 => 12345, а этот же 12345 в пришедшем может быть с ключом id5940.

[galeev_roman]

Правильно я понимаю, что в каждом массиве значения идут без повторов?
Если да, то можно воспользоваться тем, что массивы в php - это скоро hash map.
Код по ссылке sandbox.onlinephpfunctions.com/code/72b044628c969c... работает весьма шустро, хоть и потребляет в пике гигабайт памяти.
Для проверки придётся записать его в скрипт локально, так как php sandbox ограничивает память 128 Мб.

Answer 1

[Евгений]

Запишите оба массива в бд и сделайте joinом

Comments

[キム ファイブプラス]

А не жирно будет хранить два состояния одних и тех же данных?
Таблица то не одна такая, их сотня. Все нужно сравнивать периодически.

[d-stream]

SalatProduction: ну для БД десятки гигабайт - нормально, а вот 2Gb для операций в памяти - черевато...

кстати truncate после сравнения - тоже панацея

[キム ファイブプラス]

d-stream: Truncate чего? Текущей таблицы?! Чтобы ее еще раз записать заново?)
Такое было в «бета» решении, тогда мускул загибает намертво. Пишется только разница.
Старые DELETE, новые INSERT.

[d-stream]

Я имею в виду лить пришедшие извне данные в таблицу и уже дальше сливать-сравнивать средствами sql. Ну а подразумевая то, что изменения прилетают каждый раз "одноразовыми", то втянул - обработал - удалил

У меня в подобной конструкции (правда mssql) полмиллиона записей втягиваются булком из csv секунд за 5-7, а перед этим сек 20 конверт из mdb в csv (по ряду причин такая двухфазка), подопытный с 18 миллионами строк временно пропал. Вот дальнейшие действия (обновление-добавление позиций прайса) - пришлось оптимизировать, т.к. "в лоб" это занимало часы.

[キム ファイブプラス]

d-stream: Эта баржа первоначально в пустую таблицу только записывается секунд 15 (если идти по пути truncate затем insert).
Потом ее нужно получить обратно вместе с оригинальным списком.
Да, мы выигрываем по памяти, но конкретно проигрываем по времени выполнения.
Я уже так пробовал.
Еще раз повторюсь, данная задача выполняется через воркер с сотней подобных таблиц.
То есть это не единоразовый цикл. Берет одну таблицу с удаленного, сравнивает, записывает разницу. Берет следующую и так далее.
Сейчас время выполнения максимально-оптимальное и все таблицы (не все они 5 миллионов, какие то поменьше, где то 800к, где то 1М) успевает пройти в среднем за 20-30 минут, как раз до необходимого дедлайна по актуальной выдаче, но память...текёт...текёт...

[d-stream]

SalatProduction: у меня немного не до конца вырисовывается в голове полная картина, но с единовременными операциями в памяти пугают пороги в 2Gb, 4Gb и прочим (это я предположил что архитектура процессора x86|64)

[Евгений]

Можно еще через редис попробовать
https://redis.io/commands/sdiff

[キム ファイブプラス]

Евгений: Так это лишняя прослойка получается. Из БД нужно получить в массив, записать его в редиску.. Что мы от этого выиграем?

[Евгений]

SalatProduction: так может от бд отказаться можно и писать всё в редис, в любом случаи стоит попробовать, возможно там diff быстрее будет в разы.

[キム ファイブプラス]

Евгений: Может стоит и отказаться. Пока не знаю. Пробовать буду все предложенное, потому что свои идеи зашли в тупик уже.

Answer 2

[Александр Аксентьев]

Для этого есть всякие распределнные вычисления типа mapreduce на hadoop или аналогичных платформах.

Но 5млн строк это всё-таки не бигдата .
Делайте нормальный скрипт для проверки постепенной, а не 5 милионов сразу в функцию зах*уячить и ждать что всё будет прекрасно.
Можно еще очередь(amqp) поставить и воркеров запустить, и вкидывать туда задания. Но тоже это все аккуратно и постепенно.

Comments

[キム ファイブプラス]

Вопрос так сказать возник на боевом сервере и какое то временное решение нужно принять прямо сейчас. А так спасибо, чекну обязательно инфу.

[Александр Аксентьев]

SalatProduction: ну решение сейчас это как раз адекватный скрипт накидать, который постепенно пройдёт все значения, а не всю базу сразу.

Пускай висит 1-2-3 часа, но рабочий вариант зато.

[キム ファイブプラス]

Александр Аксентьев: Обнова каждые 20 минут должна происходить (в вакууме...)

[Александр Аксентьев]

SalatProduction: ну это уже зависит от того что проверить и как проверить.
Если размер данных не очень большой, то вполне можно успеть.

Судя по тому что вы смогли это всё загрузить в скрипт, там немного и влезло в раму.
Так что дальше зависит от того что это и как написать.

Из советов могу сказать что чем больше данных входных собрать, тем быстрее всё выполнится.
Т.е. во время цикла/циклов проверки данных стараться делать минимум запросов в базу/апи/кешам и т.д.
Чисто вычисления - тогда будет летать.
Т.е. до того как сравнивать как раз вытаскиваете из базы все что по ходу понадобится.
В данном случае один большой запрос вначале гораздо эффективне чем куча простых точечных селектов к базе например.

[キム ファイブプラス]

Александр Аксентьев: Ну с запросами проблем нет, потому что селект происходит только один, когда забирается из базы в массив все 5 лимонов)
Обратно запись также. Собирается массив diff и записывается через prepare mysqli единоразово. А вот с памятью беда.

[キム ファイブプラス]

Я понял про разделение, но как раз таки не знаю, как это провернуть из за того, что приходящие данные уже находятся в готовом массиве. Их все равно нужно декодить за один проход.

[Александр Аксентьев]

SalatProduction: трудно что-то подсказать, данные вы не показываете, и что сравнивается.

Ну как вариант почему бы не разбить первоначальные данные по 1 миллиону хотя бы.
Уже сократит потребление памяти в 5 раз, только цикл надо будет сделать на 5 повторов.

Ну это из разряда бреда совет, без понимая что у вас там происходит :)

[キム ファイブプラス]

Александр Аксентьев: Два поля в таблице id -> autoincrement и data -> integer.
И от удаленного тоже самое, только id в них постоянно меняется местами. Все.
Я даже не знаю что тут можно показать.

Про разбить я уже ответил, не вижу возможности (по крайне мере я) взять часть из БД и часть из удаленного, тк я не знаю, под каким ключом будет в следующий раз id из взятого куска БД.
«В базе скажем под id1 => 12345, а этот же 12345 в пришедшем может быть с ключом id5940»

[Stalker_RED]

SalatProduction: Т.е. ключи вообще смысловой нагрузки не несут, и сравнивать нужно только значения? Отсортируйте тогда их, разбейте на какие-то диапазоны и сравнивайте.

[キム ファイブプラス]

Stalker_RED: Уже попробовал. Время выполнения увеличивается в 2 раза. Это очень критично.

Answer 3

[private_tm]

На линуксе в терминале
diff 1.txt 2.txt > diff.txt

Comments

[キム ファイブプラス]

То есть вы предлагаете декодить приходящий json в список txt, затем также записывать данные из БД, затем их сравнивать, конвертировать строки обратно в массив и записывать опять в БД...? Я тогда пожалуй лучше не пожалею оперативы)

[private_tm]

SalatProduction: можете и json сразу сравнить с json выводом из бд.

[private_tm]

SalatProduction: на самом деле проблемы больших фалов давно и очень просто решаются порциями. Если я не ошибаюсь в php для таких случаев используют yield и генераторы(для чтения больших фалов порциями).

Answer 4

[Дмитрий Евграфович]

Вообще это не для php задача, если перепишете на том же питоне с тем же самым алгоритмом, памяти уйдет раз в 10 примерно меньше (https://habrahabr.ru/post/141093/#comment_4719302 - почти пруф. Сам одно время интересовался, нужно было сравнивать массивы пользователей из вк, сейчас бы попробовал go наверное, с ним потребление памяти не изучал, но оно будет явно меньше, чем у php). Также как вариант записать данные со стороннего сервера себе и брать порциями, используя генераторы (yield), они как раз и созданы, чтобы экономить память, но лучше мне кажется все-таки использовать другой язык программирования на такие объемы.

Comments

[Максим]

только пруф почти обратный - там 32 млн записей укладываются в 30 Мб :)
PHP в жертву удобства кушает больше, но это не значит, что нельзя немного поиграть в "бигдату" на нем. Только надо понимать как это сделать правильно.

[Дмитрий Евграфович]

Максим: эээ, на питоне 3 мегабайта, на php 21 метр. разница в 7 раз в пользу питона при использовании одинаковых массивов данных (причем неизвестно, какие пакеты и какой тип массивов применяет автор комментария), почему он обратный?

[AlikDex]

Дмитрий Евграфович: Вот тоже первое что пришло в голову, так это использовать другой яп. Какая разница в принципе кто будет считать и обрабатывать массивы, если задача судя по всему работает по крону и данные к самому пхп никак не привязаны (берутся из базы\базы другого сервера). Питон, жава, го, си тот же. Всяко быстрее и менее ресурсоемко будет.

[キム ファイブプラス]

Я все больше начинаю склоняться к пайтону, может подскажите какие то проверенные временем классы для работы с мускулом?

[Дмитрий Евграфович]

SalatProduction: боюсь, это не ко мне вопрос.

[Максим]

Дмитрий Евграфович: в том смысле что 32млн записей запросто умещаются в 30 мб. А у автора не влезает 5млн в 1.2Гб. Т.е. тут больше проблема не самих размеров массива, а проблема с дальнейшей их судьбой.

[Максим]

Дмитрий Евграфович: И да, я не спорю, что в си или питоне будет быстрей. Но обработать можно и в пхп :)

[Дмитрий Евграфович]

Максим: в статье в записи обычное число от 1 до 32 миллионов, а у автора куча данных.

Answer 5

[Максим]

Если сортируется быстро, то можно отсортировать массивы, затем пройтись по одному и найти все вхождения в другом, ограничивая перебор брейком, т.е. что-то в духе:

sort($arr1);
sort($arr2);
$lv = 0;
$m = count($arr2);
foreach ($arr1 as $k1) {
    for ($i=$lv ;$i < $m; $i++) {
        if($k1 == $arr2[$i]) {
            // do smth
            $lv = i;
            break;
       }
       if ($k1 < $arr2[$i]) {
           break;
       }
   }
}

но это не готовое решение

Comments

[キム ファイブプラス]

Сейчас тоже самое и используется. array_udiff с callback.

array_udiff($array2, $array1, function ($a, $b) {
    return ($a['ID'] <=> $b['ID']);	
})

[キム ファイブプラス]

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

[Максим]

SalatProduction: нет и нет. Вариант что я написал по идее должен быть быстрее, т.к. он не делает лишних проходов и ему не нужно больше памяти. Т.е. по идее сложность алгоритма должна быть O(N+M). А В array_diff происходит сравнение каждого с каждым, т.е. O(N*M). Вроде бы так.

Далее, если массивы у Вас есть и ошибка происходит в момент array_diff, то нехватка в функции. Тогда замена может помочь. Если же ошибка возникает до вызова array_diff, то тогда да, надо решать проблему, причем основательно, начиная с того как избежать эти 5млн.

[Максим]

SalatProduction: забыл в коде про сортировку.

[キム ファイブプラス]

Максим: Такс щас буду тестить.
Не, ошибки никакой нету, у меня на серваке 4Гб оперативы. Но нужно цифру уменьшать. Появляются новые аккаунты, увеличивается количество таблиц, соответственно, нужно уменьшать время выполнения, увеличивая нагрузку и хватая сразу по 2-3 массива в обработку.
Итого 2-3 5М будут забивать 3,5Гб в лучшем случае за один проход.

[Максим]

SalatProduction: по хорошему менять архитектуру надо, чтобы не доводить до такого.

Добавил еще одно условие в цикл, чтобы просто выкидывало, когда ключ пройден

[キム ファイブプラス]

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

Answer 6

[Philipp]

Сложите данные во вторую таблицу и потом через SQL все сделайте.

Answer 7

[ReenExe]

А что если попробовать через разницу ключей?

$start = microtime(true);

$exists = array_fill(2e7, 7e7, true);
$stored = array_fill(3e7, 8e7, true);
shuffle($exists);
shuffle($stored);

echo microtime(true) - $start;
echo PHP_EOL;

$start = microtime(true);;

$diff = array_diff($stored, $exists);

echo microtime(true) - $start;
echo PHP_EOL;

$start = microtime(true);

$diff = array_keys(array_diff_key(array_fill_keys($stored, true), array_fill_keys($exists, true)));

echo microtime(true) - $start;
echo PHP_EOL;

// initialize:      11.500846147537
// array_diff:      4.1464519500732
// array_diff_key:  3.2659499645233

Решение с Redis возможно более правильное
Но вместо Python - PHP мигрируют на Golang

Comments

[キム ファイブプラス]

Не, голанг не нравится. У пайтона более минималистичный синтаксис. Меньше кода - легче читать.