История разработки фасетного поиска средствами PHP

Как экспериментальный Pet Project дошел до production и на что способны современные версии языка PHP. Немного о проблематике фасетного поиска в части построения агрегатов.

Если ваша первая реакция: «Почему не на Sphinx/ElasticSearch/etc?», не торопитесь с выводами. Воспринимайте изложенное как интересный исследовательский опыт в области возможностей языка и его оптимизаций.

Спойлер: пришлось даже написать порт на GoLang, чтобы лучше понять пути оптимизации кода.

Агрегаты

Прежде чем разбирать решение, немного расскажу про проблематику, для тех кто не сталкивался с фасетами.

Представим, что пользователь нашего интернет-магазина выбрал несколько интересующих его фильтров. Мы должны отобразить не только список товаров, которые соответствуют этим фильтрам, но и обновить сам компонент фильтрации таким образом, чтобы в нем остались только те варианты фильтров, которые присутствуют в найденных результатах.

У каждого значения фильтра необходимо отобразить количество товаров, которое за ним скрывается. Все это пересечения множеств, вычисление которых происходит при помощи агрегатов (по аналогии с ElasticSearch aggregations)

Простой кейс: пользователь в разделе смартфоны выбрал значения фильтров «бренд» и «объем памяти». У фильтра «цвет» доступно 3 варианта значений:  «белый», «синий», «черный». Что произойдет со списком доступных фильтров и их значений, если пользователь выберет вариант «белый» ?

• простой сценарий - ничего особо не меняется, у варианта цвета проставляется «галочка». Это не очень удобно, пользователь видит лишние варианты фильтрации, выбор которых не приводит к изменению результатов;

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

• более редкий, но самый удобный вариант - недоступные фильтры и их значения будут отключены/спрятаны, обновятся данные о количестве товаров за выбранным значением фильтра.

Чтобы реализовать третий вариант, необходимо исключить влияние значения поля фасета на другие значения этого поля при фильтрации в агрегате, условно назову это «Self Filtering». 

Если алгоритм не ограничивает Self Filtering, при этом скрывает недоступные варианты, то в кейсе с телефонами для поля «цвет» останется доступным только значение «белый», так как «синий», «черный» не совместимы с этим выбором. Это неудобно, так как пользователь не сможет изменить выбор цвета. Если мы ограничим Self Filtering, то при выборе одного цвета, остальные варианты цветов останутся доступными для выбора.

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

Более подробно эта проблематика разобрана в статье  “Фасетные фильтры: как готовить и с чем подавать”.

Определить список доступных для фильтрации полей и значений - не самая простая задача. Часто встречал вариант без скрытия / отключения фильтров, обновляется только количество товаров за этим фильтром. Так же часто от пользователя требуется дополнительное действие «Применить фильтры». Просчет агрегатов достаточно дорогой, дополнительное действие используют, чтобы не создавать лишней нагрузки на инфраструктуру. 

Примеры фасетного поиска в известных интернет-магазинах:

На этих примерах видны различные варианты реализации. 

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

Отключение и счетчик товаров проще реализовать на Bitmap или Sphinx. Сложнее обстоят дела, когда наборы свойств заранее не известны.

При должном усердии любое поведение можно реализовать и на Sphinx и на Elastic.

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

Именно этот функционал был реализован в библиотеке на PHP. Он прост в использовании и достаточно быстр, что может конкурировать с «серьезными решениями». Учитывает особенности фильтрации агрегатов, позволяет реализовывать отключение/скрытие лишних опций фильтров. И главное, скрывает сложность всего за парой методов.

Возникновение задачи

На тот момент я работал в компании ПартКом (оптовая продажа автозапчастей), которая на первый взгляд, совершенно не про эксперименты IT и инновации. Большой Enterprise с 80 млн. SKU номенклатуры, логистикой, складами, доставкой и прочими прелестями жизни.

Большая часть проектов в web запускалась как внутренние мини-стартапы со всеми вытекающими. С одной стороны, минимум ресурсов и времени, с другой - свобода выбора инструментов и подходов. Это позволяло очень быстро запускать MVP и экспериментальные сервисы. Запуск нового функционала мог занимать от одного дня до пары недель. 

Внезапно образовался свободный промежуток времени и ресурсы, что позволило взяться за идею запуска MVP каталога автоаксессуаров (щетки, лампочки, коврики, масло и тп), все то, что удобно покупать на основе характеристик. 

Устройство инфраструктуры

Сервис обработки прайс-листов обрабатывал огромные объемы данных и загружал их в БД, в минуту заливались десятки миллионов строк прайс-листов.

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

Из общего объема номенклатуры нас интересовало порядка 300 тыс наименований товаров, которые были в наличии на складах. Эти товары были разбросаны по 100 категориям. В каждой категории дерева каталога могли находиться несколько сущностей «Продукт». 

«Продукт» определял набор допустимых атрибутов и их значений для определенного вида товаров (например: щетки могут иметь тип/размер/применяемость). У каждого продукта был четко определенный и структурированный набор атрибутов. Продукты в одной категории являлись родственными, часть их атрибутов пересекалась. В атрибутах часто встречались длинные перечисления, а также они могли содержать сразу несколько значений из доступного списка (MultiValue).

Товары привязывались к «продуктам» по номенклатуре и так же редактировались в каталоге. Товар содержал фактические значение атибутов, можно представить как объект одного из классов «продукт».

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

Решение

В моем распоряжении было около трех недель и два разработчика - 1 бэк и 1 фронт, которые при этом были загружены на 30% другими задачами.

Первая неделя была потрачена на дополнительные исследования. Провели эксперименты со Sphinx и ElasticSearch, концепцией bitmask + redis/etc, вариант реализации в БД на SQL не рассматривался.

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

Sphinx 

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

У нас уже был подобный сервис с фасетами на Sphinx, который достался по наследству и вызывал много сложностей.

Дополнительный вопрос - как обновлять информацию в реальном времени. При наших объемах, за сутки несколько раз могло обновиться 60 млн строк с информацией о наличии и ценах. 

Из плюсов -  можно было настроить indexer на работу с таблицей цен и остатков.

ElasticSearch

Еще одно отличное решение, но вспоминаем, что нам нужно загружать от 20 млн строк в минуту и это совершенно нетривиальная задача. При разработке сервиса хранения цен и остатков мы экспериментировали с загрузкой в InnoDb, TokuDb, RocksDb, MongoDb, ElasticSearch. На тот момент выбрали InnoDb как самый простой и достаточно быстрый движок MySQL. 

Bitmask 

Концепция хранения битовых масок значений атрибутов отталкивала двумя основными сложностями. 

У нас было много значений-списков и превращать их в битовые маски не очень тривиальная задача, более того размер списков не был прогнозируем (могли быть и по 500 вариантов). В этом случае легко ошибиться с размером битовой маски и выйти за ее пределы. Еще атрибуты могли содержать одновременно несколько значений.

Вторая сложность - это считать агрегаты для фильтров по этим маскам.

Задачу можно было решить с использованием любого из этих инструментов, но это было достаточно сложно, долго и дорого.

Разработать высококлассную архитектуру, развернуть надежную кластерную инфраструктуру ElasticSearch, настроить мониторинги и алерты, выступить с докладом на конференции :-)

Продуктовый подход

Поскольку предпринимаемые усилия были маленьким внутренним стартапом, кроме инженерного взгляда на процесс, есть еще и продуктовый, у которого совершенно свои метрики, правила запуска и тестирование гипотез, ROI, unit-экономика. Спасибо продуктовой и стартап движухе, которую устраивает Аркадий Морейнис, это сильно изменило мои взгляды на разработку, продукты и стартапы.

Мы находились в высококонкурентном сегменте с низкой маржинальностью, где абсолютно отсутствовали гарантии окупаемости «правильного подхода». Закопать тонны ресурсов в проект, который может не полететь бы ло бы очень обидно.

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

Вдохновляли ребята из Badoo и ManyChat, у которых отлично получались делать кастомные решения и они оказывались более эффективными как с точки зрения производительности, так и экономически.

Возникла идея, что PHP на текущий момент достаточно быстрый для попытки реализовать фасетный поиск без использования сторонних решений. При этом, он может быть адаптирован к нашим особенностям и условиям. Поэтому я решил поднять код своего старого PetProject с экспериментами в этой тематике.

На первоначальную доработку библиотеки ушла пара свободных вечеров. После нескольких итераций по оптимизации производительности получился относительно компактный и достаточно быстрый индекс. Код обрабатывал данные 200,000 товарах с 10 атрибутами менее 0,2 c. Размер категории каталога не превышал 20,000 товаров, это давало огромный запас по производительности. После того как я убедился, что библиотека справляется с нужной нагрузкой, взяли ее на вооружение для запуска MVP на рабочем проекте.

Решение на PHP библиотеке и на ElasticSearch крутились параллельно на тестовом сервере. При этом последнее не давало преимуществ в производительности, было сложнее в плане подготовки агрегатов, индексирования данных и поддержке. Имело дополнительный overhead на построение агрегатов.

Решили оставить вариант с PHP библиотекой, на то время, пока она справляется с нагрузкой. Доработали остальные части MVP и выпустили каталог за 3 недели. 

Решение хорошо себя показало на MVP, поэтому я не забросил эту историю, и в свободное время дополнительно оптимизировал индекс.

Как сейчас устроен индекс

Сама концепция структуры данных в индексе очень простая:

<?php
$data = [
    // поля
    'color' => [
        // значения
        'green' => [
          // идентификаторы записей товаров с этим значением
          4, 8, 15, 16, 23, 42
        ],
        'yellow' => [
          // . . .
        ]        
    ],
    'size' => [
        // . . .
    ]    
];

Основная «магия» и усилия оптимизаций были сосредоточены в области эффективного обхода этого индекса.

Предвосхищая вопросы о SplFixedArray и расширениях типа php-ds.

• SplFixedArray - не использовался, так как при индексировании не известен итоговый размер массива, данные индекса нужно прозрачно экспортировать и импортировать, внутри обработки активно используются функции для работы с массивами, которые не поддерживают SplFixedArray.

• Php-ds/etc. - не использовалось, по тем же причинам что и SplFixedArray, дополнительная зависимость для интерпретатора в production.

История оптимизаций

При построении агрегатов требовалось находить много пересечений массивов и тут обнаружился один интересный нюанс.

Представим, что есть два массива - $dataA и $dataB, значения они могут хранить по нашему усмотрению в ключах или в значениях. 

Если элемент содержит значения в ключах, назову его $keysA или $keysB. 

Значений в массивах очень много, но мы точно знаем, что в первом их меньше чем во втором. 

Нам нужно посчитать количество пересекающихся элементов.

Вариант 1

<?php $count = count(array_intersect($dataA, $dataB));

Вариант 2

<?php $count = count(array_intersect_key($keysA, $keysB));

Вариант 3 

<?php
$count = 0;
foreach ($dataA as $v) {
    if (isset($keysB[$v])) {
        $count++;
    }
}

Для тестирования этого примера прогнал каждый вариант по 10 итераций в цикле:

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

Порт на Golang

В какой-то момент идеи по оптимизации кода были исчерпаны, но ощущение, что можно быстрее, осталось.

Решил написать порт библиотеки на Golang, полностью скопировать трюки и оптимизации из PHP, насколько это возможно. Было интересно посмотреть, что будет происходить с Go приложением, изучить данные pprof, пощупать сбор агрегатов в горутинах. Казалось, это может дать значительный прирост. 

Сложно было ожидать, что не имея серьезного опыта в Go, получиться написать очень производительное решение. Тем не менее, язык зарекомендовал себя как очень производительный, с низким порогом входа. Курс Василия Романова позволил быстро разобраться в подходах и особенностях оптимизации приложений на Go.

Первые реализации в 4 раза уступали по производительности варианту на PHP,  даже с многопоточный обработкой агрегатов в горутинах. Стало понятно, что Go не так прост и производительность нужно уметь обеспечивать. С помощью pprof удалось найти места лишних аллокаций памяти, которые были совершенно незаметны на связке XDebug + Cachegrind.

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

В PHP отличная реализация ассоциативных массивов, есть оптимизации с приведением ключа к zend_ulong и упаковка нумерованных списков.

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

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

Большая часть оптимизаций предпринятых в Go легко применялась и давала ускорение на PHP.

Пример оптимизации из Golang

Во время тестов производительности обнаружил странное поведение.

В PHP версии был значительно меньший разброс времени у разных итераций тестирования. В Go был очень сильный разброс.

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

Данные индекса:

<?php
[
    'цвет' => [
            'белый' => [1,2,3,...],  // 1 тыс. элементов
            'черный' => [7,8,9,...], // 10 тыс. элементов,
            // ...

    ],
    'склад' => [
            'N1' => [1,2,3,...],  // 50 тыс. элементов,
            'N2' => [7,8,9,...],  // 70. элементов
    ]
    // ...
]

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

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

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

В Go порядок элементов HashMap не гарантируется, это и вызывало тот странный эффект. При каждом новом тестировании последовательность полей была случайной, из-за этого периодически выдавался максимум элементов на первых итерациях, который кочевал по всем этапам усечения и постепенно уменьшался. Это приводило к колоссальному перерасходу памяти.

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

Эта оптимизация позволила поднять производительность в 2-3 раза и на PHP и на Go.

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

Сам Go вынудил оптимизировать конструкции пересечений таким образом, что через некоторое время стало возможно в некоторых местах перейти от хранения в HashMap к слайсам int64. Поскольку код на PHP следовал этим оптимизациям, в нем так же стал возможен переход к массивам с целочисленными ключами. Изначально это не представлялось возможным, приводило к множеству сортировок и вызовам array_unique.

Решения практически сравнялись по производительности. 

• PHP пока выигрывает в поиске.  

• Go лучше в агрегатах, требует значительно меньше памяти для хранение индекса, на малых и средних объемах это не играет решающей роли. Пока не уверен, что распараллеливание «числодробилки» на все ядра может оказаться лучшим решением при большом количестве запросов.

Тесты производительности

Поиск и агрегаты по 3 фильтрам. (у товаров 10 характеристик)

PHP 8.1.0 + JIT + opcache (без xdebug) v.2.0.0

Порт на Golang 1.17.3 с параллельным подсчетом агрегатов v.0.3.0

RAM -  объем памяти потребляемый индексом

Какие задачи решает подход с PHP библиотекой, а какие нет

Нет

• Подход точно не подойдет если, необходимо Realtime обновление данных в индексе. 

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

• Если у вас всего один тип продукта/документа и сквозной набор характеристик для всей базы данных на миллионы строк.

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

Да

• Если товары/документы у вас поделены по категориям и необходим поиск исключительно в рамках конкретной категории. В категории до 300 тыс. записей. 

Особенно, при большой неопределенности с перспективами проекта, ограниченном времени и ресурсах, а также при отсутствии экспертизы в Sphinx/Elastic. Тут библиотека поможет вам быстро стартовать проект и продержаться какое-то время, возможно очень долгое.

Итоги

Проект за пару недель окупил вложения и начал приносить прибыль. Через три месяца вышел на достойный оборот, поддерживал темпы роста x2 несколько лет подряд. Крутится в production с 2019 года и не вызывает хлопот.

Вся эта история оказалась отличной возможностью посидеть с профайлером и более тонко понять особенности PHP и Golang.

Эксперименты с разными языками позволили шире смотреть на проблематику и помогли генерировать новые идеи.

Новые версии языка, особенно в связке с RoadRunner и Swoole, открывают возможности для реализации вещей, которые ранее казались немыслимыми на PHP.

В рамках стартапа не всегда стоит гнаться за хайповыми технологиями, возможны решения проще и дешевле.

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

GitHub

Update: v3.1.0 PHP 8.2.10 + JIT + opcache