Привет, меня зовут Питер, и я работаю в Badoo в отделе биллинга.
В этой статье я хочу поделиться своим опытом работы над пет-проектом по созданию хранилища фотографий с возможностью поиска дубликатов.
Я расскажу вам, с каким багажом я вошел в этот проект, какая была задача и как я ее решил.
В конце я поделюсь результатами и расскажу, почему я считаю, что это один из лучших проектов, которые я когда-либо делал.
Однажды мои друзья попросили меня сделать им хранилище изображений для их проекта по модерации внешних ресурсов.
Условия: срок хранения до трех лет, фотографии рассылаются неравномерно, средний поток 150 000 снимков в день.
Казалось бы, довольно тривиальная задача.
Если бы не еще одно условие: хорошо бы сравнить фотографии с существующими: найти дубликаты и отметить их.
Позвольте мне начать с того, что существует два класса дубликатов.
Первый — это миниатюры, то есть одно и то же изображение, растянутое или сжатое.
Назовем второй класс полудубликатами.
Это изображения, полученные из оригинала с более серьезными изменениями.
Типичный пример: мы отрезали верхнюю часть с водяным знаком у изображения и добавили свой: 
Нас заинтересовали именно эти полудубликаты: мы хотели сравнить именно этот класс.
Но мне было неясно, как решить эту проблему, пока я не наткнулся на теорию ключевых моментов, которая меня очень увлекла, восприняла как личный вызов и активно ее реализовала.
Я кратко объясню, что представляет собой эта теория и как она позволяет нам сравнивать полудубликаты.
Ключевые моменты
Ключевая точка — это некоторая особенность изображения, где что-то происходит. Например, изменение контрастности, проявляющееся в углах и краях.Существует очень много алгоритмов, которые могут выделить эти ключевые моменты, и все они работают по-разному.
На одном изображении они выдадут разное количество точек и сами точки будут разными.
Но, как правило, все они возвращают массив из структуры из трех параметров x, y и q, где
- х, у — координаты этой самой точки на картинке;
- д — это некий параметр, определяющий качество этой точки, то есть насколько сильным было изменение.
Я взял набор из 10 000 снимков, разделил каждый на области размером 16х16 пикселей и посмотрел, какой процент таких областей включает в себя хотя бы одну ключевую точку: 
Это было необходимо для выбора алгоритма, который лучше всего описывал тестируемые мной изображения.
Если ни одна ключевая точка не попадает в какую-либо область, то сравнение в этой области проводиться не будет. И чем больше таких областей, тем менее точным будет поиск.
В результате я получил большую таблицу, но основные алгоритмы выделялись следующим образом: 
На основании таблицы я выбрал алгоритм AKAZE: он хоть и не имеет самого высокого максимального покрытия, но имеет хорошее среднее значение и приемлемое время обработки.
Стоит обратить внимание: выявление ключевых точек и анализ с помощью этого алгоритма занимает полсекунды, что довольно много для большого объема изображений.
Анализ изменений
Итак, мы нашли на картинке локальную особенность.Теперь это нужно как-то описать, и в качестве примера я приведу принцип работы простейшего алгоритма — BRISK. В качестве входных данных мы передаем алгоритму координаты x и y, и он разбивает область диаметром 30 пикселей вокруг этих координат на множество мелких частей.
Затем алгоритм бинарно сравнивает эти части друг с другом.
Производится 512 вычислений, в результате мы получаем вектор длиной 512 бит, то есть для описания области диаметром 30 пикселей нам понадобится 64 байта.
Этот вектор далее будем называть дескриптором.
Теперь мы можем выбрать ключевые точки на обоих наших изображениях, посчитать дескрипторы и получить их массив для первого и второго изображения.
И, сравнивая эти строки по крупицам, найдите пары.
Если сделать это внимательно и визуализировать, то можно получить такую картину: 
Линии показывают совпадающие ключевые точки.
Красный — это то, с чем мы не смогли сравниться.
Видно, что уникальные части изображения не совпадают. Все алгоритмы достаточно сложны, чтобы нивелировать изменения, в частности ротацию.
Поэтому, если просто перевернуть изображение, ключевые точки тоже совпадут. 
И вроде бы все хорошо, но возникает другая проблема: такое прямое сравнение хорошо работает только в том случае, если изображение было сохранено без потери качества и масштабирования.
В противном случае появляются ошибки и дескрипторы не совпадают. Чтобы исправить это, я использовал интересную функцию.
Расстояние Хэмминга
Ээта функция, которая сообщает нам, сколько позиций у нас есть, где различаются две строки одинаковой длины.
Давайте посмотрим на пример: 
Видно, что две двоичные строки различаются по трем позициям, то есть расстояние Хэмминга между этими двумя строками будет равно трем.
Для простоты далее я буду называть это расстояние ошибкой.
Выбор дескриптора
Теперь, учитывая расстояние Хэмминга, мне нужно было выбрать подходящий алгоритм.К этому времени в базе проекта было собрано множество изображений, и я с помощью скрипта создал различные модификации для 10 000 изображений: обрезал сверху или снизу, назвал размеры, добавил текст. Я сравнил полученные картинки для сравнения очевидно похожие и явно разные Изображений.
Затем я построил графики для каждого алгоритма, где видно, что чем большую ошибку (расстояние Хэмминга) мы допускаем, тем больше положительных, но и ложноположительных сравнений мы получаем: 
Разделив один график на другой, можно получить оптимальное расстояние Хэмминга, которое максимизирует соотношение положительных и ложноположительных сравнений.
Например, для выбранного мной алгоритма получилось 3: 
При выборе алгоритма я также смотрел на время процессора, необходимое для обработки изображения алгоритмом.
А также от длины дескриптора; разные алгоритмы имеют разную длину.
Одно дело 8 байт, другое дело 64 байта на одну ключевую точку, которых будут миллиарды.
Итак, мы смогли сравнить точки и даже устранили некоторую ошибку.
Какие изображения теперь можно считать похожими?
Критерии
Во-первых, я обнаружил, что если на фотографии менее 10 ключевых точек, то это обычно изображение очень низкого качества.Я их просто выбросил, отметив как некачественные.
Во-вторых, картинки можно считать похожими, если пересечений больше 20% от возможных.
Например, одно изображение имеет 100 ключевых точек, другое — 200. Пересекаться может максимум 100 точек, и, соответственно, достаточно 20 совпавших дескрипторов, чтобы признать эти два изображения похожими.
После того, как мы научились сравнивать картинки, осталось только научиться искать одну в большой базе данных.
Как искать похожие изображения
Первой идеей было линейный поиск .Очень просто: берем картинку и сравниваем ее с первой, а затем со второй, третьей и так далее, пока они не закончатся.
Номера соответствующих значений возвращаются как достигнутый результат. Но от линейного поиска вскоре отказались.
При линейном поиске при росте базы в 2 раза время обработки увеличивается в те же 2 раза, что в итоге оказалось слишком много уже для базы в миллион.
Тест скорости:
- загружено 1 миллион изображений;
- Получено около 350 миллионов ключевых точек;
- База данных занимает 10 ГБ (то есть одно изображение в таком индексе занимает примерно 10 КБ).
- Поиск одной ключевой точки занимает 47 секунд, а поиск всего изображения — 4,5 часа.
Напомню, что в исходной постановке задачи в день добавляется около 150 тысяч новых изображений — это либо займет очень много времени, либо понадобится безумное количество серверов (чего не было).
Все, кроме последнего, я реализовал на PHP. Но проблема оказалась не в производительности языка, а в алгоритмической сложности задачи, которую я пытался решить.
И наконец, одна интересная структура помогла мне найти решение.
Дерево префиксов
Это дерево, в котором ключ кодируется не значением в самом узле, а путем к этому узлу.В префиксном дереве есть два типа узлов.
Синим я отметил узлы, которые хранят информацию только о дочерних узлах.
Зелёные — те, которые хранят конечную информацию, это может быть какое-то значение, массив, указатель, что угодно.
Вот пример префиксного дерева, в котором закодированы 6 строк по 3 бита: 
Теперь разберемся, как искать в дереве префиксов с допустимой ошибкой.
Например, нам нужно найти все строки, отличающиеся от 010 на 1 бит. То есть мы допускаем только одно искажение в любом бите:
- Сначала идем от корня, в котором пока накопилась ошибка 0, к узлу и далее по ветке 0. Она совпадает с нашим первым битом, поэтому накопленная ошибка не увеличивается.
- Переходим к следующему 0, а он уже отличается от нашего второго бита, поэтому накопленная ошибка становится 1.
- Оно не превышает максимально допустимого, поэтому продолжаем рассматривать решение и так, следуя по ветке 0, доходим до самого низа.
Если накопленная ошибка остается равной 1, то считаем решение успешным.
- Возвращаемся наверх и следуем по ветке 1. Поскольку она немного отличается от нашей последней, есть две ошибки, то есть данное решение нас не устраивает.
- Затем пробегаем вторую ветку и перемещаемся ко второй половине дерева.
И в итоге нам подойдут три значения: два из них с искажением в 1 бит:
Дело в том, что когда ошибка достигает максимального значения, нет необходимости углубляться в дерево.
Ошибка может только расти, и если она достигла определенного максимального значения, то будет только хуже.
Как результат поиск начинает работать очень быстро , даже если дескриптор имеет 512 уровней.
А по мере увеличения количества элементов в какой-то момент скорость просто превращается в константу и никуда не движется.
Таблица, которую я получил при сравнении дерева при линейном поиске: 
Мы видим, что на той же базе данных из 1 миллиона изображений размер базы внезапно уменьшился на 3 ГБ.
Почему так случилось? Потому что префиксные деревья изначально дедуплицируют данные, и поиск одной ключевой точки вместо 40 секунд теперь занимает всего 3,5 мс.
А поиск одного изображения стал в десять тысяч раз быстрее! Конечно, чтобы обрабатывать 150 тысяч изображений в день, обработка должна происходить за полсекунды.
Но никто не мешает вам искать в дереве префиксов в несколько потоков — и тем самым увеличивать скорость.
Первая версия префиксного дерева была реализована на PHP и работала так быстро благодаря правильно подобранному алгоритму.
На мой взгляд, префиксные деревья — очень недооцененная структура данных в современном мире.
Те же индексы: если у вас есть какое-то значение, закодированное в виде строки, и в данных мало энтропии, префиксные деревья будут занимать гораздо меньше памяти, чем бинарные деревья, которые используются в современных реляционных базах данных.
Когда я использовал деревья префиксов для индексов в Postgres, мне удалось уменьшить размер индекса в среднем вдвое.
Дерево префиксов также может дать интересный эффект, например рекомендации.
Поскольку мы можем искать с некоторой допустимой погрешностью, а у вас, скажем, миллиард товаров или каких-то объектов, качество которых закодировано битами, то вы можете искать и предлагать объект, очень похожий на то, что изначально искал пользователь.
Перейдем от теории к практике.
Реализация проекта
Хранение изображений
В первой итерации я просто помещал файлы на диск.Но когда изображений стало несколько миллионов, оказалось, что такие данные очень сложно бэкапить, передавать и анализировать.
Поэтому в итоге была собрана следующая схема: 
NGINX принимает запрос и пересылает его демону, написанному на ReactPHP. Демон, используя данные, хранящиеся в реляционных базах данных, понимает: что это за образ, на каком сервере он хранится, на каком устройстве, с каким смещением и каким объемом.
Эта информация передается на нужный сервер, который просто считывает необходимое количество байтов с нужным смещением из блочного устройства.
Это дает очень большой прирост производительности, особенно на задачах с большими объемами данных, когда одновременно нужно делать резервные копии, пересчитывать все образы для индекса или передавать их.
Но даже одно чтение может быть в десять раз быстрее.
Это решение пришло ко мне из системы резервного копирования Bacula. В результате я понял, что резервное копирование на ленточных носителях очень удобно, а при современных ценах на жесткие диски это оказалось очень недорого (напомню, проект был личный, многое делалось на энтузиазме, поэтому мы смогли не позволить себе никаких дорогих решений).
Как выглядел кластер
При поиске одной картинки в префиксном дереве для одной ключевой точки происходит примерно 10 тысяч операций чтения памяти, то есть операций чтения из разных случайных блоков.Следовательно, данные должны храниться в памяти; невозможно прочитать такой объем данных с диска.
Но, конечно, рано или поздно память иссякает. Около 30 миллионов, заняв все 128 ГБ ОЗУ, пришлось перейти к шардингу: 
Для данного алгоритма это не проблема, но все ключевые точки одного изображения должны лежать в одном блоке.
После чего данные разбиваются на разные блоки.
Каждый блок может обслуживаться отдельным сервером или группой серверов.
Все это позволяет добиться отказоустойчивости и линейно повысить скорость поиска.
Как работает поиск?
Конвейер поиска выглядит довольно просто.Есть какой-то PHP-демон, который успешно живет месяцами.
Он принимает изображение на вход и отправляет его в кластер, который выбирает его ключевые точки.
Поскольку картинки могут приходить очень большими партиями, их нужно обрабатывать как можно быстрее — поэтому в этом было задействовано несколько узлов.
Затем полученные ключевые точки рассылались по всем блокам, и один из серверов, обслуживающих блок, брал на себя задачу найти id всех похожих изображений и отправить их мастеру.
Который собрал эту информацию: 
Поисковый конвейер Вставка работала примерно так же, но с той лишь разницей: запись происходила через демон ReactPHP и только в один блок, в зависимости от внутренней логики.
Я использовал циклический перебор: 
Вставной конвейер
Результаты
Нам удалось достичь 95-го процентиля поиска (95% изображений) за 8 секунд. Но при большом количестве потоков это работало очень быстро.Кластер спокойно искал по 200 фотографий в день, что позволило с запасом решить наши проблемы.
Всего у нас было 150 миллионов образов на 18 ТБ, и в пике их обслуживали 9 нод. Почему я говорю о пиках? Узнав новое, мы смогли оптимизировать затраты и оборудование.
В итоге у нас получился узел с 768 ГБ оперативной памяти на борту.
Он вмещал почти весь индекс, который составлял 790 ГБ, но его стоимость была сопоставима с топовым игровым компьютером.
Никаких заоблачных цен.
К сожалению, в прошлом году проект закрыли, но я нисколько не жалею, что над ним работал.
Потому что до этого я жил в определенной парадигме, что PHP подходит только для сайтов.
Как только вам нужно что-то серьезное или большое, то вам нужно использовать любой другой язык.
Моя точка зрения изменилась, потому что почти все в этом проекте было написано на PHP. На C был переписан лишь один маленький кусочек — многопоточность для дерева.
Я приобрел большой опыт работы с распределенными вычислениями.
Этот опыт мне до сих пор полезен.
Я активно ищу и помогаю решать проблемы в Badoo, связанные с этим, так как у нас очень большая инфраструктура.
Пока я этим занимался, я много читал о базах данных, и многие из моих решений были почерпнуты из документации Postgres и MySQL. Теперь у меня есть уверенность, что практически любую проблему можно решить, если подходить к ней системно и уделять ей достаточно времени.
Кроме того, я очень интересно провел время, потому что я люблю программировать.
Мне интересно решать очень сложные задачи.
Эта задача была, пожалуй, одной из самых сложных.
И не только технические: нелегко было не сдаваться каждый раз, когда я сталкивался с новыми проблемами и думал, что теперь точно конец, больше ничего нельзя сделать.
Что я хочу сказать напоследок? Хочется пожелать каждому найти свой любимый проект, который, как и я в свое время, увлечет вас на пару лет и поможет улучшить свои навыки.
Конференция PHP Россия 2022 это отличное место, чтобы поделиться своим опытом с сообществом.Теги: #Алгоритмы #Высокая производительность #php #поиск #поисковая оптимизация #алгоритмы поиска #ключевые точки #префиксное дерево #дескрипторы #хамминг #Поисковые технологииОн пройдет 12 и 13 сентября в Москве, в отеле Radisson SAS Славянская.
Фокус: развитие экосистемы (сам PHP, стандарты, фреймворки, библиотеки, OpenSource); опыт крупных компаний по построению сложных проектов на PHP и лучшие практики.
И, конечно же, темы ежедневного развития.
Заявки на выступления принимаются до 25 мая.
Расходы на проезд и проживание спикеров покрываются.
Все подробности на Веб-сайт .
-
Насколько Важны Статьи В Рекламе
19 Oct, 24 -
Баш: Отмечаем Новые Серии На Myshows.ru
19 Oct, 24 -
Ssd Kingston Uv500 – Король Обновлений
19 Oct, 24 -
Перспективный Api Доступен Для Разработчиков
19 Oct, 24
