Подбираем нужные автозапчасти: миллиарды комбинаций за 12 минут

Привет! Меня зовут Кирилл Егоров, я технический лидер двух юнитов Авито: «Запчасти» и «Строительство и ремонт». В этой статье рассказываю о том, как мы определяем, к каким автомобилям подходят запчасти из объявлений, как нам с помощью Golang удается перебрать миллиарды вариантов и какие трудности пришлось решить при реализации этого решения.

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

Мы знаем про:

•  >40 000 модификаций авто;

•  >40 млн уникальных запчастей и это без учета жидкостей и аксессуаров;

•  >300 млн кроссов: связок аналогов и заменителей запчастей;

•  >120 млн оригинальных совместимостей: связок «деталь → авто»;

•  >8 000 брендов с несколькими вариантами написания для каждого;

•  >100 связок родственных брендов.

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

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

Метрики

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

Важные метрики, за которыми мы следим в этом кейсе:

• покрытие запчастей совместимостями — для какого объема запчастей мы знаем подходящие авто;

• качество покрытия — процент ошибок в справочных данных;

• покрытие объявлений — для какого объема объявлений мы знаем подходящие авто.

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

Логика определения совместимости

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

Подробнее по шагам:

1. Получаем идентификатор запчасти по бренду и артикулу: так определяется уникальный SKU в мире запчастей. Артикул предварительно нормализуется — удаляются пробелы, незначимые символы.

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

3. Для найденных запчастей получаем список аналогов и оригинальных замен — кроссов. Находим все связки part1→part2, где с любой стороны присутствует исходная запчасть. Это кроссы первого уровня.

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

   Кроссы имеют свою условную классификацию: например, кроссы на оригинал, деталь в сборе на элемент и наоборот, оригинальные замены. У разных источников — разное качество данных и уровень доверия, все это мы учитываем. 

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

   Аналогично пункту 2, в этом случае для каждой детали нужно определить детали родственных брендов. Это делается перебором вариантов.

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

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

Ключевая сложность кейса

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

Для обработки запроса пользователя нужно заранее определить, к каким автомобилям подходит запчасть из объявления и передать эту информацию в поисковую систему на индексацию. При этом объявления могут заливаться фидами c десятками тысяч SKU — пересчитывать совместимости для каждого накладно.

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

Проверенные варианты решения: 

• построчный расчет «в лоб». Получаем каждую запчасть по очереди и рассчитываем список авто, к которым она подходит. Занимает от 8 часов, при этом вызывает интенсивную нагрузку на БД в виде сотен миллионов запросов; 

• реализация на чистом SQL в postgresql. Обрабатывает данные более 20 часов, при этом съедает CPU и IO. Все потому, что логика расчетов сложная, требует пересечений многомиллионных таблиц и итерирования по ним, создания временных представлений. На нагруженной продуктовой базе такие расчеты проводить невозможно, а держать копию дорого по ресурсам;

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

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

Решение

Можно было бы нарисовать красивую сложную схему с несколькими вариантами обработки, включая DWH, колоночные БД, графовые алгоритмы и ML. Или потребовать шардированный кластер на N десятков серверов и уйти на полгода в разработку с десятком инженеров. Но мы продуктовая команда, это не наш подход.

А что, если мы сможем просчитать все варианты за условные 10 минут? Да еще и на небольшом стандартном инстансе без дополнительного железа? Звучит фантастически, но у нас это получилось. 

Выбранная конфигурация — 4 ядра CPU и 15 GB оперативной памяти (размер небольшого сервера). Такие лимиты — это серьезный челлендж рубрики «мастер оптимизаций». Пора расчехлять Golang и pprof!

План действий такой: 

1. вычитать все необходимые данные в память приложения; 

2. построить эффективные индексы, учитывающие специфику задачи; 

3. перебрать все комбинации;

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

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

Этап первый: вычитываем данные

Прежде, чем заняться расположением данных в памяти, необходимо научиться их быстро вычитывать из БД. Здесь скрыто немало подводных камней. Самый эффективный метод «вычитки»:

(псевдокод):

SELECT id, number, vendor FROM myTable WHERE id > $x  ORDER BY id ASC LIMIT $y

Где «x» — последний вычитанный идентификатор, «у» — лимит вычитки, который подбирается под настройки БД. Вычитываем все строки из БД порциями, по Primary Key. Cлишком большой «y» (лимит) может привести к израсходованию work_mem запроса (postgres), что приведет к созданию временного файла на диске и повышенному IO write со всеми вытекающими последствиями, нам это не нужно. Подбираем правильный «y», в нашем случае это несколько сотен тысяч записей.

Начал читать данные в большом объеме и поймал жесточайшие пики потребления оперативной памяти приложением. После вычитки 450 млн строк из БД получил словари размером 10 Gb и пиковое потребление процессом порядка 18 Gb RAM.

Вооружившись профайлером, обнаружил, что основная «утечка» происходит в нескольких местах на уровне драйвера БД. Например, получение и конвертация данных текстовых колонок (scan) происходит через создание слайса байт, который убегает в heap. В разных реализациях и версиях драйверов похожая картина, где-то больше дополнительных аллокаций, где-то меньше.

При этом было наивное ожидание, что GC придет и все почистит, но нет, GC все не приходил… 

Дело в том, что по умолчанию Go стартует с настройкой триггера срабатывания по памяти в 100% от текущего используемого объема. 

Collection is triggered when the ratio of freshly allocated data to live data remaining after the previous collection reaches this percentage.

Если в приложении аллоцировано 5 Gb данных, триггер запуска GC по памяти сработает при аллокации дополнительных 5 Gb. При малых объемах данных внутри приложения такое поведение совершенно незаметно, на объемах в десятки гигабайт — ощутимо и критично.

Спасла установка debug.SetGCPercent(5) со срабатыванием при достижении 5% от аллоцированной памяти. Озарение пришло не сразу, первое время проблема решалась принудительным вызовом runtime.GC(), что было не так эффективно. 

Теперь GC срабатывал намного чаще и освобождал память, что и требовалось. Поскольку воркер не обрабатывает realtime-запросы, это не имело негативных эффектов.

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

Индекс кроссов

Кросс — связка деталей аналогов  part1→part2, в БД она хранится в двух колонках int64. Для оптимального поиска всех аналогов на конкретную запчасть необходимо подготовить данные так, чтобы по id запчасти получать весь список аналогов без необходимости прохода по всем данным. В этом случае подошел вариант с Map вида:

part1 → [part2, part3] part2 → [part1]           part3 → [part1]       

Такая карта заняла около 10 Gb оперативной памяти, при этом около половины связок при просчете не приводило к нахождению совместимостей (детали кросса не имели прямой связи с авто). Нужно было оптимизировать хранение.

Оптимизация #1

Было принято решение перенести загрузку справочника кроссов на самый последний этап, когда остальные данные собраны и можно понять, есть ли совместимость для детали кросса. Добавлен этап проверки целесообразности хранения кросса в памяти. Перед тем как записать детали из кросса в Map, производится поиск всех родственных деталей для пары part1→part2, далее проверяется наличие хотя бы одной совместимости с авто для них. Если совместимость не находится – нет смысла заносить в карту.

Такая оптимизация сократила размер индекса на ~25%.

Оптимизация #2

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

Пример:

27310-3N420 Hyundai partId: 1, brandId: 1    27310-3N420 Kia     partId: 2, brandId: 2   27310-3N420 Mobis   partId: 3, brandId: 3  заменяется на   27310-3N420 Hyundai partId: 1, brandId: 1

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

Удалось сократить размер индекса кроссов c 20 Gb (в БД) до 1.8 Gb (в приложении).

Индекс запчастей – это Map c десятками миллионов элементов.

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

Тут подошел трюк с получением CRC32 хэша от строки артикула. Хэш использовался в качестве ключа Map, что уменьшило размер потребляемой памяти (около 3Gb) и облегчило жизнь GC.

index[unit32][]entity.Part

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

Почему CRC32:

Были эксперименты с xxHash, на этом кейсе они дали совсем незначительный прирост производительности. Проверял еще несколько алгоритмов с реализацией на Go из списка  https://github.com/rurban/smhasher, все они не давали особого преимущества. Само вычисление хэша не было узким местом.

Для быстрого перебора комбинаций требовалось два варианта доступа к данным: 

• по идентификатору (partId), для работы с кроссами;

• по хэшу артикула, для поиска запчастей родственных брендов.

Пришлось хранить дополнительный индекс:

part[int64]entity.Part

Это увеличило объем потребления памяти на ~1Gb, но значительно ускорило обработку данных. В отличии от индекса БД, хранились еще и данные, что тоже влияет на потребляемый объем.

Индекс совместимостей

Данные о том, к какому авто подходит запчасть в БД лежат в виде строк partId — carId. Эти данные используются как основа для дальнейших расчетов совместимости.

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

 compatibility[int64][]int64

Почему сразу не хранить «сырые данные» в таком виде в БД? Мы интенсивно собираем информацию из различных источников, при этом нам необходимо уметь их независимо обновлять, при такой структуре хранения воркеры сбора данных будут конфликтовать за строки при обновлении и вызывать блокировки.

Сравнение размеров индексов

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

Просчитываем варианты

• проходим по индексу запчастей и добавляем их в буферизованный канал обработки; 

• канал обработки читают воркеры (8 горутин);

• воркер получает на вход part id, на выходе формирует ByteBuffer согласованного формата и отправляет его в буферизованный канал записи;

• канал записи читает одна горутина, которая занимается фактической записью в файл;

• файл отправляется на дальнейшую обработку в систему поиска.

На выходе получаем около 1 млрд комбинаций. Файл с таким количеством строк был бы очень больших размеров — придумываем метод «схлопывания» строк с логическим сжатием данных. Его можно представить в виде csv-файла с нестандартной структурой: данные о детали и json массив со списком идентификаторов авто в конце.

В файле до 50 млн строк — уже намного лучше, но все еще много.

Разбиваем данные на несколько файлов и добавляем потоковое сжатие.

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

В ходе разработки было добавлено множество мелких оптимизаций: 

• отказ от sync.Pool в пользу FreeList;

• повсеместное использование локальных буферов по мотивам статьи Debugging performance issues in Go programs от Dmitry Vyukov в блоге Intel Developer Zone;

• передача буферов в качестве аргументов;

• замена map на slice где это возможно;

• правка мельчайших аллокаций, вплоть до использования strconv.AppendInt для более оптимальной записи int в []byte .

Хотелось бы раскрыть вопрос оптимизации и профилирования более подробно, но это требует написания отдельной статьи, ещё большей по объему. 

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

Итоги

Пример тестового запуска:

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

Система работает в production два года, с нагрузкой справляется.

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

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

Спасибо вам за уделенное статье время! Задавайте вопросы в комментариях, с удовольствием отвечу на них и обсужу накопленный опыт. До встречи!

Подписывайтесь на канал AvitoTech в Telegram, там мы рассказываем больше о профессиональном опыте наших инженеров, проектах и работе в Авито, а также анонсируем митапы и статьи.