Поиск дубликатов в клиентском MDM на миллиард записей
Представьте, что вам нужно объединить две базы данных с информацией о клиентах, каждая из которых содержит несколько миллионов записей. В них есть ФИО, паспортные данные, СНИЛС, даты рождения, адреса и другие данные. Ваша задача — найти все похожие записи и не допустить ошибочных объединений.
Причем данные могут содержать ошибки, опечатки операторов или неверные транскрипции. Для полной сверки каждого с каждым потребуются триллионы операций сравнения. И вишенка на торте — братья-близнецы с редкими, но созвучными именами. Даже оператор может решить, что это дубль, и объединить их записи.
Цена ошибки неверного объединения или дублирования выражается в репутации компании и конкретных суммах на счетах клиентов, к которым могут получить доступ посторонние люди.
В этом посте расскажу о работе нашей системы обработки данных, которую мы применяем и адаптируем под такие сложные случаи.
Откуда берутся дублирование и ошибки: простой пример
Если вы уже знаете, откуда берутся дубли, переходите к разделу «Как можно решить задачу» — там самое «мясо».
Недавно мы адаптировали для заказчика — крупного российского банка — наш «Единый клиент» (систему для управления клиентскими данными). Может показаться, что задача тривиальная — решение ведь уже готовое. Но не все так просто. Например, у любого банка есть:
Автоматизированная банковская система (АБС) — хранит данные по счетам клиентов.
CRM — для работы менеджеров с клиентами.
Процессинг банковских карт — система для обработки платежей и эквайринга, обычно независимая от АБС.
Кредитный конвейер — проверка клиента при оформлении кредита, включая данные из АБС.
А еще есть и аффилированные с банком структуры (те же страховые службы), и отделы со своими БД, например безопасники.
Это так, минимум. Данные клиентов регулярно появляются во всех элементах этой цепочки, с разными уровнями вложенности.
Представим, что человек (пусть зовут его Маша), который ранее не был клиентом банка, оставляет заявку через форму на сайте, чтобы получить кредит. Ее персональные данные сохраняются в базе фронта, а затем проходят через «кредитный конвейер», чтобы выяснить, можно ли выдать запрошенную сумму под желаемый процент. Когда Маша становится клиентом, информация о ней добавляется в АБС вместе с данными о счетах и картах, а также в CRM для управления взаимодействием с клиентом и возможного предложения дополнительных услуг.
Все эти системы должны быть синхронизированы и работать быстро, иначе можно ожидать шквал обращений от клиентов с вопросами: «Ну что там по моему кредиту? Почему так долго отвечаете?» Несмотря на наличие таких идентификаторов, как паспорт, ИНН и СНИЛС, централизованного ID-шника, который связывал бы данные во всех системах, обычно нет, что усложняет задачу связывания информации.
Еще интереснее становится, когда Маша решает поменять какую-то идентифицирующую информацию. Она звонит в call-центр или приходит в офис банка и говорит: «Я вышла замуж, у меня новая фамилия. А еще я переехала, и у меня новый паспорт». В некоторые системы такая информация априори не попадет. Например, если в «кредитном конвейере» заявка уже завершила свой жизненный цикл, то она навсегда останется в том же состоянии, котором была изначально. Но такая информация может быть одновременно обновлена как в CRM, так и в АБС.
Как и любой бизнес, банк не может актуализировать информацию о клиенте самостоятельно. Даже если данные о Маше всплыли из внешних источников, а не она сама пришла, нужно позвонить ей или прислать уведомление из серии: «Уважаемая Мария. Придите в ближайший офис банка и напишите заявление о смене того-то».
В итоге информация о Маше множится в разных системах, как грибы после дождя. Где-то она полнее и актуальнее, а где-то — нет. Скажем, в АБС хранятся ФИО, паспорт, дата рождения, ИНН и СНИЛС. А во фронтальной системе только контакты для коммуникации с клиентом. В которых, кстати, Маша может легко внести ошибку, перепутав одну цифру с другой.
Если помножить все эти записи хотя бы на пару миллионов клиентов (что соответствует среднему по размеру региональному банку), количество записей может превысить число россиян. А потом топ-менеджмент банка спрашивает: «А сколько у нас вообще клиентов? Мы хотим строить BI-аналитику по разным критериям: активность за период, количество транзакций и прочее». Нужно проанализировать разрозненные массивы данных и понять, что условно Маш не десять, а одна — вот в таких-то строчках.
Где в банке могут храниться данные о клиентах
В итоге MDM-система превращается в сложную разветвленную структуру. Но даже настроив и оптимизировав ее под все бизнес-задачи, можно столкнуться с еще большим вызовом.
Как количество записей может превысить население страны: слияние двух банков
Представим ситуацию… В какой-то момент банк А решает расширяться и покупает банк Б. У купленного банка Б есть свои информационные системы, которые хранят миллионы клиентских записей. Банк А хочет перенести эти данные в свою MDM-систему. Но тут возникает проблема:
Информационные системы банка Б разные, и у каждой есть своя отдельная клиентская база.
У банка Б есть свое приложение интернет-банка и CRM.
Часть клиентов банка Б могла параллельно пользоваться услугами банка А.
Если мы просто объединим все системы банка Б с системами банка А, то с высокой вероятностью получим дублирование информации — как внутри банка Б, так и между клиентскими записями банков А и Б. Причем, забегая вперед, пересечение клиентских баз может достигать 10%, а уровень дублирования внутри систем может быть значительно выше.
Теперь представьте, каково будет Маше, когда она узнает, что у нее внезапно появился новый счет в банке А, потому что ее информация из банка Б была интегрирована некорректно? Или как бизнесу будет сложно обслуживать клиента под одним брендом, если информация о нем задвоена в разных частях системы? Не говоря уже о дополнительных проблемах для разработчиков, которым пришлось бы поддерживать несколько систем с дублирующими функциями.
Попутно возникают дополнительные проблемы:
еще пять пунктов
Сроки должны быть как можно более сжатыми. Каждый день клиенты продолжают пользоваться услугами как банка А, так и банка Б. Чем больше процесс будет затягиваться, тем сильнее могут быть репутационные потери бизнеса. Желательно уложиться в три месяца.
Производительность. Представим, что клиент подает заявку на открытие счета или кредита после слияния банков. Тот банк, который быстрее ответит, в итоге и получит клиента. Поэтому нужно буквально в течение секунды проверить, есть ли этот клиент в базе банка А или Б.
Нормализация. Клиенты и менеджеры иногда ошибаются при вводе данных. Например, в одном месте «Иванов», а в другом — «Ванов», хотя это один и тот же человек. Такие ошибки часто возникают при вводе данных клиентами самостоятельно на сайтах, лендингах или в заявках. Даже в офисах при открытии счета, когда клиент проверяет распечатки, возможны ошибки, которые не всегда удается заметить. Кроме того, подобные неточности встречаются и в других сферах, таких как страхование или розничная торговля, где контроль качества ввода может быть ниже, чем в банках. Все эти опечатки нужно отследить и учесть.
А еще бывает, что сотрудники компаний-партнеров при вводе забивают по клиенту телефон (777) 777–77–77 или номер паспорта из единиц. Причем человек реальный, так как у него, например, указан номер страхового полиса на авто. В подобных случаях нужно передать данные по клиенту менеджерам банка, чтобы они вручную разобрались в проблеме. И эти случаи приходится отдельно выявлять.
Избыточная дедупликация — когда схлопываются данные по двум разным людям, у которых многие данные оказались идентичными. В результате они начинают видеть счета друг друга. Об этом мы уже писали на Хабре — как раз по этому кейсу со слиянием банков. Этого также важно избежать.
Критерии сравнения — их по факту может быть много. Как понять, что два человека похожи? Можно сравнить ФИО и даты рождения, взяв их из базы. Но разве этого достаточно? В интернете есть много примеров, как ФАС начисляет долги полным тезкам из разных регионов (еще истории тут и тут). То есть нужно обязательно сравнивать СНИЛС, паспорт, ИНН. А это — еще один вопрос производительности и времени. Как понять достаточность сравнения и установить критерии похожести?
Это только верхнеуровневые проблемы, с которыми мы столкнулись, — по факту их намного больше.
Как можно решить задачу: варианты поиска дубликатов
С причинами появления дублей и ситуацией понятно. Теперь давайте посмотрим, какие у нас были варианты решения, с преимуществами и недостатками. Сразу оговоримся: по факту решений по дедупликации существует не один десяток, но мы рассмотрим только основные, для понимания.
Сравнение в лоб
Мы берем каждую запись из базы банка А и сравниваем с каждой записью в базе банка Б. Но тут возникает проблема: это очень долго, так как сложность растет квадратично. Например, если в каждой базе по миллиону записей, это дает триллион операций сравнения.
Пусть одно сравнение занимает 1 мкс, хотя из-за времени загрузки данных это может длиться дольше. Триллион сравнений — это миллион секунд (почти 12 дней), что слишком долго. Бизнесу на базе в миллион записей нужны не дни, а минуты.
Некоторые подметят, что на хорошем кластере все будет быстрее. Но это вопрос цены. Быстрое выполнение на кластере из сотни серверов обойдется дорого. Плюс передача данных по сети и сбор результатов тоже займут время.
Нечеткое сопоставление строк
Можно попробовать установить, почему записи похожи. Определить некоторую метрику сходства между двумя строковыми записями. Тут есть множество подходов, например:
Расстояние Левенштейна, которое показывает, сколько нужно сделать операций, чтобы схлопнуть одну строку с другой. И тем самым оценивается критерий схожести.
Алгоритм шинглов — когда строка разбивается на цепочки и к каждой применяются хеш-функции для получения единой матрицы сопоставления критериев.
Коэффициент Жаккара — еще более простой метод определения бинарного сходства.
Проблема таких подходов в том, что они не универсальны и плохо масштабируемы. Нужно учитывать специфику данных и их ценность. Например, расстояние Левенштейна между «Маша» и «Миша» равно единице — достаточно одной замены, чтобы получить одно имя из другого, и система может посчитать их похожими. Но если рассматривать «Миша» и «Михаил», они, несмотря на общие корни, похожи гораздо меньше. Более того, если учесть дополнительные параметры, такие как пол человека, ситуация становится еще более сложной.
Другой пример — адреса. Например:
Россия, Ленинградская область, г. Санкт-Петербург, 3-я улица Строителей, дом 25, квартира 11.
РФ, СПБ, 3 Строителей, дом 25, квартира 12.
На первый взгляд адреса кажутся очень похожими. Мера схожести при сопоставлении строк может быть высокой, хотя различие всего в одной цифре квартиры: 11 и 12. Мера схожести при сопоставлении строк может быть высокой, хотя различие всего в одной цифре квартиры: 11 и 12.
Поисковые движки
Есть уже готовые системы поиска вроде Elasticsearch. Подход подразумевает индексацию данных по разным критериям. А данных у нас столько, что эти индексы будут занимать много места и требовать сложное развертывание. Да и вообще, когда мы прикинули масштабы формулировки поисковых запросов, с учетом нечеткого сравнения и взаимосвязей разных документов, стало понятно: на настройку готовой системы мы потратим больше времени, чем если используем самописный подход. Но о нем поговорим ниже.
ML-модели
Очень популярная сейчас тема, которая теоретически может показывать отличные результаты. После обучения модель самостоятельно проверяет строки, нормализует их и решает, можно ли объединить записи. Однако в банковской сфере есть важная проблема — сложно проследить, как модель принимает решения. Это противоречит требованиям прозрачности. Например, если ошибочно объединить счета, клиент может потерять деньги и выяснить причину будет трудно.
Это связано с проблемой объяснимости ИИ (Explainable AI). Важно не только получать результат, но и понимать, как он был достигнут. В банковской сфере, где ошибки недопустимы, это критично.
Мы провели несколько экспериментов с ML-моделями и после нескольких итераций дообучения получили приемлемый результат. Но риск работы с «черным ящиком» остался, и это стало основным сдерживающим фактором.
Комбинированный подход
Стало ясно, что с учетом сроков, масштабируемости подхода и требований к скорости и производительности, проще всего будет реализовать все самим. И для этого подойдет комбинированный подход: в котором мы возьмем все лучшее от других алгоритмов поиска дубликатов, но будем опираться на специфику банковской сферы.
Если кратко: мы присваиваем одному документу (данным по клиенту) несколько индексируемых значений (хешей) — тех самых критериев сравнения. Затем, используя инвертированные индексы, сможем быстро сравнивать один документ с другими.
Как мы ищем дубликаты с комбинированным подходом
Расскажем подробнее про наше решение по этапам: каждый из них закрывает те проблемы, которые описали выше.
Этап 1. Чистка данных
Сначала все данные, которые есть в базах данных, нужно нормализировать — привести к единому базису. Иначе придется сравнивать, условно говоря, теплое с мягким. Миша и Михаил — похожие имена, но не очень. Поэтому из Миши нужно сделать Михаила.
Для этого мы используем парсинг. Нам приходит строкой ФИО. Мы раскладываем ее на компоненты: отдельно фамилия, имя и отчество. При этом сразу определяем опечатки: никаких Мишаилов или Инавовых. Фильтр в том числе основан на групповой распространенности и типовых ошибках. Вплоть до того, что проанализировали расположение клавиатуры: буквы Л и Д расположены рядом, поэтому при наборе легко промахнуться.
То же самое с адресом, который приходит строкой. «Город Москва» мы превращаем в «г. Москва», «Улица ломоносова» — в «ул. Ломоносова», отдельно выделяются корпуса, подъезды и квартиры, если есть. Параллельно обращаем внимание на номера паспортов из единиц или номера телефонов из семерок и при необходимости выводим их в отдельные записи, чтобы передать менеджерам для уточнения.
Пример автоматической нормализации и уточнения данных
Этап 2. Хеширование
Теперь системе нужно объяснить, как сравнивать разные записи. Скажем, Машу с телефоном 1 и Пашу с телефоном 2 сравнивать будет странно. А вот Машу и Пашу с одинаковыми телефонами — имеет смысл. Есть какие-то критерии похожести. Мы придумываем пачку таких критериев и создаем алгоритм, по которым записи группируются — хешируются.
Для хеширования используется стандартная функция hashCode () над строкой в Java, которая основана на алгоритме DJB2, разработанном Даниэлем Дж. Бернстайном.
Сами хеши представляют собой числа, которые занимают намного меньше места, чем исходные записи, благодаря чему операции выполняются гораздо быстрее. Мы избегаем квадратичной сложности, которая возникла бы при сравнении «каждый с каждым». Вместо миллионов сравнений формируются группы из десятка записей, которые затем сравниваются более детально.
Всего есть три вида поиска: полный, инкрементальный и реалтайм, по которым происходит группировка.
Для полного поиска дубликатов. В Lucene есть внутренний числовой идентификатор (innerId), который стабилен и не меняется на момент поиска. А еще есть внешний идентификатор (extId), который берется из самой записи. Принцип поиска следующий:
Запоминается lastFullDate (дата последней полной загрузки данных).
Останавливается очередь применения обновлений.
Выполняется полное перестроение индекса.
Все непримененные обновления из очереди модификации, дата которых меньше lastFullDate, удаляются.
В дескрипторе индекса обновляются даты lastFullDate и lastIncDate.
Возобновляется очередь применения обновлений.
Открывается асинхронный итератор внутренних идентификаторов (в памяти хранится 10 000 идентификаторов) поискового индекса.
Каждый innerId отправляется в поток. Количество потоков (threadCount) и их приоритет задается в запросе SOAP/REST.
Далее для каждого потока:
Загружает свои hasher_N и record по innerId.
Строит и выполняет запрос поиска по индексу, где хотя бы одно значение для одинаковых hasher_N пересекается, и extId не равен текущему. В результате получается коллекция innerId кандидатов, которых нужно проверить.
Отсекаются все найденные innerId, которые меньше текущего, чтобы избежать коммутативных сравнений.
Для каждого найденного innerId загружаются hasher_N и record (в этом шаге hasher_N нужен только для статистики).
Выполняется подсчет статистики.
Загруженные записи отправляются на сравнение компараторами.
Если дубликат найден, то он отправляется в асинхронный сервис сохранения, количество потоков которого равно 10% от threadCount, но не меньше 1.
Для инкрементального поиска дубликатов. Принцип не отличается от полного поиска, кроме того, что итерируются записи, отобранные по index_date. В итоге получается так:
Запоминается lastIncDate (дата последнего инкрементального поиска).
Останавливается очередь применения обновлений.
Принудительно применяются все обновления из очереди до lastIncDate.
Возобновляется очередь применения обновлений.
Выполняет полный поиск дубликатов, но вместо одного итератора по всем внутренним идентификаторам нужно обойти два. А при построении запроса поиска кандидатов index_date должен быть больше даты последнего инкрементального поиска:
— итератор FULL_TO_INC (инкремент к существующим данным) — index_date будет меньше даты последнего инкрементального поиска;
— итератор INC_TO_INC (инкремент внутри самого себя) — index_date будет больше даты последнего инкрементального поиска.В дескрипторе индекса обновляется дата lastIncDate.
Для поиска дубликатов в режиме реального времени. Тут совсем все просто: строит и выполняет запрос, где хотя бы одно значение для одинаковых hasher_N пересекается с текущей записью. Запрос ограничивается количеством найденных кандидатов — по умолчанию 1000. Найденные кандидаты отправляются в компаратор.
Этап 3. Компараторы и правила
В итоге мы получили группы, которые можно сравнивать друг с другом по любым критериям, прописав сценарии. В каждом из сценариев мы дополнительно прописываем коэффициент соответствия от 0 до 100 — он позволяет нам понять, насколько записи похожи и можно ли их считать дублированием. Сразу отметим, что это — экспериментальное значение, не какие-то привязанные к величинам проценты.
Для понимания приведем простейшие сценарии поиска из XML файла:
В итоге заказчик в Confluence видит описание сценария и тот самый коэффициент соответствия — его можно менять по ситуации.
Этап 4. Обновление данных
В итоге мы собрали полный набор данных из всех исходных систем, нормализовали и продедуплицировали их. Что-то схлопнулось автоматически, а остальное передается для ручного подтверждения дублей.
Дальше у нас идет поток изменений в клиентских данных, которые нужно пропускать через наш сервис: обновлять информацию и пересчитывать хеши. И при следующей проверке отслеживать не весь объем записей по клиентам, а только те, по которым были изменения с последней даты. Условно мы работаем не с миллионом записей, а 10 тысячами, которые появились за день.
Мы выполняем полный поиск ночью, а разницу проверяем каждые 10 минут. И дополнительно есть точечный поиск в реалтайме. Через REST API или SOAP приходят данные, введенные клиентом или менеджером в течение дня. Мы сразу можем проверить по данным из АБС или CRM, и если есть совпадение по ID и другим данным, то заводить новую карточку клиента не нужно.
На чем все работает: Apache Lucene с алгоритмом сжатия lz4 и discovery алгоритмом на JGroups
Почему выбрали именно библиотеку Apache Lucene. Это основа для Elasticsearch, которая позволяет добавлять к документу несколько индексируемых значений (хешей) и с помощью инвертированных индексов быстро находить документы (контрагентов) с такими же хешами, как у рассматриваемого.
При этом Lucene поддерживает гибридный режим работы:
Индексы записей хранятся в RAM через MMAP — получаем быстрый поиск, поскольку сами хеши занимают не так много места, как упоминали выше. Не надо выгружать сотни гигабайт данных по клиентам.
Когда нашли идентификаторы похожих записей, обращаемся к общей базе на диске и извлекаем полную информацию о конкретных клиентах. Она уже передается в компараторы для сравнения по разным полям. Конечно, доступ к полной информации на диске немного замедляет процесс, но позволяет оптимизировать использование ресурсов.
То есть такой подход позволил подобрать оптимальные настройки для разных серверов у различных заказчиков. С одной стороны, это не требует слишком дорогих серверов с большим объемом оперативной памяти, а с другой — обеспечивает достаточно быстрый поиск. Сервисы мы реализовали на Java, поэтому интеграция с текущей MDM-системой прошла без проблем. Кроме того, библиотека Lucene тоже написана на Java, что облегчило ее встраивание.
Но дальше, как это часто бывает, возникли сложности.
Проблема 1: алгоритм сжатия
Весь поиск был организован на процессоре Intel Xeon Ice Lake 32 CPU с 64 ГБ RAM и SSD-накопителем. Однако время все равно было большим на текущих объемах базы — иногда до 10 часов, в зависимости от загруженности сервера и прочих факторов. Мы решили поэкспериментировать с алгоритмами сжатия данных.
В Lucene есть стандартный кодек, который по идее должен ускорять работу. По факту же он… замедлял поиск. Мы начали разбираться в вопросе детальнее: провели несколько экспериментов и выявили проблему. Дело в том, что Lucene пережимает весь файл: тратится время как на распаковку, так и на сдвиг курсора чтения к нужной позиции. Возникла идея пережимать не весь файл, а только конкретную запись алгоритмом lz4 — благо в Lucene есть возможность менять способы сжатия данных.
В результате это дало отличный прирост скорости. Метрики при standalone поиске у нас получились такими:
А вот у заказчика на реальных данных — существенный прирост производительности:
Проблема 2: распределенная работа
Первая версия сервиса была реализована на одном сервере. Но стало понятно, что со временем база серьезно разрастается: количество записей приближалось к сотне миллионов, и «выжать» из сервера что-то еще стало проблематично. Доходило до того, что времени полной дедупликации базы не хватало на ночное окно.
Мы решили задействовать дополнительные серверы. Встал вопрос, как сделать это оптимально, используя текущие технологии и не вводя дополнительных тяжеловесных фреймворков? Для этого использовали Java-библиотеку JGroups, которая ищет серверы внутри сети по определенному Discovery алгоритму. Она позволяет настраивать конкретные IP-адреса серверов и автоматически искать наименее загруженные серверы и формировать на них динамические кластеры для распределения нагрузки.
Это дает классные возможности масштабирования: условно берем два сервера и получаем прирост в 1,8–1,9 раза, с учетом ресурсов на сетевое взаимодействие.
При этом весь объем данных мы дробим на небольшие блоки. Условно нам не надо брать все 100 миллионов записей: берем по 1000 записей и ставим их в очередь. Какой именно из серверов возьмет конкретный блок, зависит от его загруженности. Но функционал от этого никак не страдал: любой slave-сервер может брать данные с общего сетевого диска, обрабатывать хеши и возвращать результат в виде найденных дублей обратно на master-сервер. Оттуда уже можно забрать итоговый результат дедупликации.
Блок схема распределения работы между кластерами
Общая архитектура работы сервиса поиска дубликатов в нашей системе «Единый клиент»: с учетом ускорения работы при помощи библиотеки JGroups
Что в итоге: показатели производительности и новые вызовы
В итоге сервис успешно заработал — мы уложились в заданные три месяца. Количество дублей оказалось на уровне 10%. Часть из них передали операторам на ручную обработку. По нашему опыту это можно считать достаточно чистыми данными, с учетом размера клиентской базы банков.
Немного о бенчмарках. Вот как изменяется производительность при полном поиске дубликатов по всей базе на нашем стресс-стенде на одной и двух нод:
С учетом всех оптимизаций на базе в 100 миллионов записей мы можем найти дубли примерно за час. Одиночный запрос в режиме реального времени обрабатывается за 500 мс. Без использования хеширования поиск дубликатов был бы слишком медленным, и мы его даже никогда не проводили.
Важно отметить, что ключевую роль в работе алгоритма играет стандартизация данных. Мы затронули эту тему в этапе 2 данной статьи, где говорили о нормализации данных. Однако это только верхушка айсберга. В одной из следующих статей подробнее расскажем про алгоритмы разбора данных и покажем, как их правильно готовить для успешного дедуплицирования.
