- Зачем всё это надо?
- Кажется, кто-то уже это делал?
- Генерация отпечатка аудиозаписи
- Сравнение отпечатков аудиозаписей
- Архитектура генерации отпечатков и индексирования/поиска в архитектуре ВКонтакте
- Что получилось?
- Есть вопросы по архитектуре и алгоритмам индексации аудиозаписей ВКонтакте?
Зачем всё это надо?
В социальной сети ВКонтакте действительно очень много музыки. Очень много — это больше 400 миллионов треков, которые весят примерно 4 ПБ. Если загрузить всю музыку из ВКонтакте на 64 ГБ айфоны, и положить их друг на друга, получится башня выше Эйфелевой. Каждый день в эту стопку нужно добавлять еще 25 айфонов — или 150 тысяч новых аудиозаписей объёмом 1.5 ТБ.
Конечно, далеко не все эти файлы во ВКонтакте уникальны. У каждого аудио ВКонтакте есть данные об исполнителе и названии (опционально — текст и жанр), которые пользователь заполняет при загрузке песни к себе в профиль. Премодерации нет. В результате получаются дубли песен с разными названиями, ремиксы, концертные и студийные записи одних и тех же композиций, и, конечно, совсем неверно названные треки.
Если научиться достаточно точно находить одинаковые (или очень похожие) аудиозаписи, можно применять это с пользой, например:
- не дублировать в поиске ВКонтакте один трек под разными названиями;
- предлагать прослушать любимую композицию ВКонтакте в более высоком качестве;
- добавлять обложки и текст ко всем вариантам песни ВКонтакте;
- усовершенствовать механизм рекомендаций ВКонтакте;
- улучшить работу ВКонтакте с жалобами владельцев контента.
Пожалуй, первое, что приходит в голову — это ID3-теги. У каждого mp3-файла ВКонтакте есть набор метаданных, и можно принимать во внимание эту информацию как более приоритетную, чем то, что пользователь указал в интерфейсе сайта при загрузке трека. Это самое простое решение. И оно не слишком хорошее — теги можно редактировать вручную, и они совсем не обязательно соответствуют содержимому.
Итак, вся ассоциированная с файлом информация, которая у нас есть, человекозависима и может быть недостоверной. Значит, нужно приниматься за сам файл.
Разработчики ВКонтакте поставили перед собой задачу определять треки, которые одинаковы или очень похожи на слух, анализируя при этом только содержимое файла.
Кажется, кто-то уже это делал?
Поиск похожих аудио — довольно популярная история. Ставшее уже классическим решение используется всеми подряд, от Shazam’а до биологов, изучающих вой волков. Оно основано на акустических отпечатках.
Акустический отпечаток — это представление аудиосигнала в виде набора значений, описывающих его физические свойства.
Проще говоря, отпечаток содержит в себе некую информацию о звуке, причем эта информация компактна — её объём сильно меньше, чем у исходного файла. Композиции ВКонтакте, похожие на слух, будут иметь одинаковые отпечатки, и наоборот, у отличных по звучанию песен отпечатки не будут совпадать.
Разработчики ВКонтакте начали с попытки использовать одно из готовых решений на C++ для генерации акустических отпечатков. Прикрутили к нему свой поиск, протестировали на реальных файлах и поняли, что для значительной части выборки результаты плохие. Один и тот же трек успешно «маскируется» эквалайзером, добавлением фонового шума или джинглов, склейкой с фрагментом другого трека.
Вот как это выглядит (в сравнении с исходным треком):
Лайв-исполнение
Эхо
Ремикс
Во всех этих случаях человек легко поймёт, что это одна и та же композиция. А во ВКонтакте много файлов с подобными искажениями, и важно уметь получать хороший результат и на них. Стало ясно, что нужна другая реализация генератора отпечатков.
Генерация отпечатка аудиозаписи
Что же, имеем: есть аудиозапись в виде mp3-файла. Как превратить его в компактный отпечаток?
Нужно начать с декодирования аудиосигнала, который в этот файл упакован. MP3 представляет собой цепочку фреймов (блоков), в которых содержатся закодированные данные об аудио в формате PCM (pulse code modulation) — это несжатый цифровой звук.
Чтобы получить PCM из MP3, используется библиотека libmad на С и обертку для неё на Go. Позднее сделали выбор в пользу прямого использования ffmpeg.
Так или иначе, в результате получаем аудиосигнал в виде массива значений, описывающих зависимость амплитуды от времени. Можно представить его в виде такого графика:
Аудиосигнал раскодированного mp3 трека:
Это тот звук, который слышит наше ухо. Человек может воспринимать его как одно целое, но на самом деле звуковая волна представляет собой комбинацию множества элементарных волн разной частоты. Что-то вроде аккорда, состоящего из нескольких нот.
Теперь нужно узнать, какие частоты есть в этом сигнале, а особенно — какие из них наиболее «характерны» для него. Для этого можно использовать давно открытый способ получения таких данных — быстрое преобразование Фурье (FFT).
Подробное описание математического аппарата выходит за рамки этой статьи. Узнать больше о применении преобразования Фурье в области цифровой обработки сигналов Вы можете, например, в этой публикации.
В реализации ВКонтакте для этого используется пакет GO-DSP (Digital Signal Processing), а именно github.com/mjibson/go-dsp/fft — собственно FFT и github.com/mjibson/go-dsp/window — для оконной функции Ханна.
На выходе получаем набор комплексных чисел, которые, будучи перенесенными на плоскость, называются спектрограммой.
Спектрограмма — это визуальное представление всех трёх акустических измерений: времени, частоты и амплитуды сигнала. Она выражает значение амплитуды для определённого значения частоты в определённый момент времени.
Пример получаемой спектограммы mp3 трека эталонной дорожки ВКонтакте:
По оси X отсчитывается время, ось Y представляет частоту, а значение амплитуды обозначается интенсивностью цвета пикселя. На иллюстрации приведена спектрограмма для «эталонного» сигнала с равномерно повышающейся частотой. Для обычной песни спектрограмма выглядит, например так:
Спектрограмма обычной дорожки mp3 трека ВКонтакте:
Это довольно подробный «портрет» аудиодорожки ВКонтакте, из которого можно (с определённой аппроксимацией) восстановить исходный трек. С точки зрения ресурсов, хранить такой «портрет» полностью невыгодно. В нашем случае это потребовало бы 10 ПБ памяти — в два с половиной раза больше, чем весят сами аудиозаписи.
Поэтому для уменьшения объёма хранения информации выбираются ключевые точки (пики) на спектрограмме, основываясь на интенсивности спектра, чтобы сохранять только самые характерные для этого трека значения. В результате объём данных сокращается примерно в 200 раз.
Ключевые значения на спектрограмме mp3 трека ВКонтакте:
Осталось собрать эти данные в удобную форму. Каждый пик однозначно определяется двумя числами — значениями частоты и времени. Добавив все пики для трека в один массив, получим искомый акустический отпечаток.
Сравнение отпечатков аудиозаписей mp3 трека ВКонтакте
Допустим, всё вышеописанное сделано для двух условных треков, и теперь есть их отпечатки. Вернёмся к исходной задаче — сравнить эти треки с помощью отпечатков и выяснить, похожи (одинаковы) они или нет.
Каждый отпечаток mp3 трека ВКонтакте — это массив значений. Попробуем сравнивать их поэлементно, сдвигая треки по временной шкале относительно друг друга (сдвиг нужен, например, чтобы учесть тишину в начале или в конце трека). На одних смещениях совпадений в отпечатках будет больше, на других — меньше. Выглядит это примерно так:
Треки с общим фрагментом и разные треки ВКонтакте
Вроде похоже на правду. Для треков ВКонтакте с общим фрагментом этот фрагмент нашелся и выглядит как всплеск числа совпадений на определённом временном смещении. Результат сравнения — «коэффициент сходства», который зависит от числа совпадений с учетом смещения.
Программная реализация Go библиотеки для генерации и сравнения отпечатков доступна на GitHub. Вы можете увидеть графики и результаты для собственных примеров.
Теперь надо встроить всё это в инфраструктуру ВКонтакте и посмотреть, что получится.
Архитектура генерации отпечатков и индексирования/поиска в архитектуре ВКонтакте
Движки генерации отпечатков и индексирования/поиска в архитектуре ВКонтакте
Движок для генерации отпечатков работает на каждом сервере ВКонтакте для загрузки аудио (их сейчас около 1000). Он принимает на вход mp3-файл, обрабатывает его (декодирование, FFT, выделение пиков спектра) и выдаёт акустический отпечаток этого аудио.
Нагрузка распараллеливается на уровне файлов — каждый трек обрабатывается в отдельной горутине. Для средней аудиозаписи ВКонтакте длительностью 5-7 минут обработка занимает 2-4 секунды. Время обработки линейно растет с увеличением длительности аудио.
Акустические отпечатки всех треков ВКонтакте, хоть и с некоторой потерей точности, займут около 20 ТБ памяти. Весь этот объём данных нужно где-то хранить и уметь быстро к нему обращаться, чтобы что-нибудь в нём найти. Эту задачу решает отдельный движок индексирования и поиска ВКонтакте.
Он хранит данные об отпечатках в виде обратных (инвертированных) индексов:
Обратный индекс отпечатков mp3 треков ВКонтакте
Чтобы добиться быстродействия и сэкономить на памяти, ВКонтакте используют преимущества структуры самого отпечатка. Отпечаток — это массив, и можно рассматривать отдельные его элементы (хэши), которые, как Вы помните, соответствуют пикам спектра.
Вместо того, чтобы хранить соответствие «трек» → «отпечаток», мы разбиваем каждый отпечаток на хэши и храним соответствие «хэш» → «список треков, в отпечатках которых он есть». Индекс прореженный, и 20 ТБ отпечатков в виде индекса займут около 100 ГБ.
Как это работает на практике? В движок поиска ВКонтакте приходит запрос с аудиозаписью. Нужно найти похожие на неё треки. Из хранилища скачивается отпечаток для этого аудио. В индексе выбираются строчки, содержащие хэши этого отпечатка. Из соответствующих строк выбираются часто встречающиеся треки, для них скачиваются отпечатки из хранилища ВКонтакте. Эти отпечатки сравниваются с отпечатком исходного файла. В результате возвращаются самые похожие треки с соответствующими совпавшими фрагментами и условным «коэффициентом сходства» для этих фрагментов.
Движок индексирования и поиска работает на 32 машинах ВКонтакте, написан на чистом Go. Здесь по максимуму используются горутины, пулы внутренних воркеров, параллелится работа с сетью и глобальным индексом.
Итак, вся логика готова. Давайте соберем отпечатки всей музыки ВКонтакте, проиндексируем и начнём с ними работать. Кстати, сколько времени это займёт?
Разработчики ВКонтакте запустили индексацию, подождали пару дней и оценили сроки. Как оказалось, результат будет примерно через год. Такой срок неприемлем — нужно что-то менять.
Внедрение sync.Pool везде, где только можно, выкроило 2 месяца. Новый срок: 10 месяцев. Это всё ещё слишком долго. Надо лучше.
Оптимизируем тип данных — выбор треков по индексу был реализован слиянием массива. Использование container/heap вместо массива обещает сэкономить половину времени. Получаем 6 месяцев выполнения. Может, можно ещё лучше?
Затачиваем container/heap под использование нашего типа данных вместо стандартных интерфейсов, и выигрываем ещё месяц времени. Но нам и этого мало (то есть много).
Правим stdlib, сделав собственную реализацию ВКонтакте для container/heap — ещё минус 2 месяца, итого остаётся 3. В четыре раза меньше первых оценок!
И, наконец, обновление версии Go с 1.5 на 1.6.2 привело нас к финальному результату. 2.5 месяца потребовалось в итоге на создание индекса всей музыки ВКонтакте.
Что получилось?
Продакшн-тестирование выявило несколько кейсов, которые не были утены изначально. Например, копия трека с немного изменённой скоростью воспроизведения:
Ускоренная дорожка mp3 трека ВКонтакте
Для слушателя аудиозаписи ВКонтакте это практически одно и то же, небольшое ускорение не воспринимается как существенное отличие. К сожалению, наш алгоритм сравнения отпечатков считал такие треки совсем разными.
Чтобы это исправить, было добавлено немного преобработки. Заключается она в поиске наибольшей общей подпоследовательности (Longest Common Subsequence) в двух отпечатках. Ведь амплитуда и частота не меняются, меняется в этом случае только соответствующее значение времени, а общий порядок следования точек друг за другом сохраняется.
LCS mp3 трека ВКонтакте
Нахождение LCS позволяет определить коэффициент «сжатия» или «растяжения» сигнала по шкале времени. Дальше дело за малым — сравниваем отпечатки как обычно, применив к одному из них найденный коэффициент.
Применение алгоритма поиска LCS значительно улучшило результаты — многие треки ВКонтакте, которые прежде не находились по отпечатку, стали успешно обрабатываться.
Еще один интересный случай — совпадение по фрагментам. Например, минус какой-то популярной песни с записанным поверх него любительским вокалом.
Совпадения фрагментов mp3 треков ВКонтакте
Раскладываем результат сравнения по времени и смотрим на число совпадений для каждой секунды трека ВКонтакте. На картинке выше как раз пример любительской записи поверх минуса в сравнении с исходным треком этого минуса. Интервалы с отсутствием совпадений — вокал, пики совпадений — молчание (т.е. чистый минус, который аналогичен исходной дорожке). В такой ситуации считаем число фрагментов с совпадениями и вычисляем условный «коэффициент сходства» по числу самих совпадений.
После кластеризации похожих треков отдельные кластеры оказались значительно больше остальных. Что там? Там — интересные ситуации, в которых не очень понятно, чем их правильно считать. Например, всем известная Happy Birthday to You. У нас есть несколько десятков вариантов этой песни, которые отличаются только именем поздравляемого. Считать их разными или нет? То же касается и версий трека на разных языках. Эти искажения и их сочетания стали серьёзной проблемой на этапе запуска.
Разработчика ВКонтакте пришлось изрядно доработать механизм с учётом этих и других не вполне обычных ситуаций. Сейчас система работает должным образом в том числе и на таких сложных кластерах, и продолжается работа по её усовершенстванию, при встречах с новыми неординарными преобразованиями. Алгоритм ВКонтакте умеет находить песни под вымышленными названиями, ускоренные, с врезками джинглов и без вокала. Поставленная задача была выполнена, и, несомненно, ещё не раз пригодится в дальнейшей работе по развитию сервиса рекомендаций, поиска по музыке и аудиораздела ВКонтакте в целом.
Есть вопросы по архитектуре и алгоритмам индексации аудиозаписей ВКонтакте?
Вопросы автору статьи можно задать в официальном сообществе технического блога ВКонтакте.
По материалам:
https://vk.com/blog/arhitektura-i-algoritmy-indeksatsii-audiozapisey
Заберите ссылку на статью к себе, чтобы потом легко её найти!
Раз уж досюда дочитали, то может может есть желание рассказать об этом месте своим друзьям, знакомым и просто мимо проходящим?
Не надо себя сдерживать! ;)
