Encontrar duplicados en el MDM del cliente para mil millones de registros / Sudo Null IT News

Imagine que necesita fusionar dos bases de datos de información de clientes, cada una de las cuales contiene varios millones de registros. Contienen nombre completo, datos del pasaporte, SNILS, fechas de nacimiento, direcciones y otros datos. Su tarea es encontrar todos los registros similares y evitar asociaciones erróneas.

Además, los datos pueden contener errores, errores tipográficos del operador o transcripciones incorrectas. Se necesitarían billones de comparaciones para compararlos completamente entre sí. Y la guinda del pastel son los hermanos gemelos con nombres raros pero consonantes. Incluso el camarógrafo puede decidir que se trata de una toma y fusionar sus grabaciones.

El costo de un error de fusión o duplicación incorrecta se expresa en la reputación de la empresa y en montos específicos en las cuentas de los clientes a las que pueden acceder personas no autorizadas.

En este post te hablaré del funcionamiento de nuestro sistema de procesamiento de datos, que utilizamos y adaptamos a casos tan complejos.

De dónde vienen las duplicaciones y los errores: un ejemplo sencillo

Si ya sabes de dónde proceden los duplicados, salta a la sección “¿Cómo puedes resolver el problema?“—Ahí es donde está la “carne”.

Recientemente adaptamos nuestro “Cliente único” (un sistema para gestionar los datos de los clientes) para un cliente: un gran banco ruso. Puede parecer que la tarea es trivial, pero la solución ya está lista. Pero no es tan simple. Por ejemplo, cualquier banco tiene:

1. Sistema bancario automatizado (ABS) — almacena datos sobre las cuentas de los clientes.

2. CRM: para gerentes que trabajan con clientes.

3. El procesamiento de tarjetas bancarias es un sistema para procesar pagos y adquirir, generalmente independiente del sistema bancario central.

4. Canal de crédito: verificación del cliente al solicitar un préstamo, incluidos datos del ABS.

También hay estructuras afiliadas al banco (los mismos servicios de seguros) y departamentos con sus propias bases de datos, por ejemplo, agentes de seguridad.

Eso es todo, al menos. Los datos de los clientes aparecen periódicamente en todos los elementos de esta cadena, con diferentes niveles de anidamiento.

Imaginemos que una persona (llamémosle Masha), que no ha sido cliente del banco anteriormente, deja una solicitud a través de un formulario en la web para conseguir un préstamo. Sus datos personales se almacenan en la base de datos frontal y luego pasan por el “canal de crédito” para averiguar si la cantidad solicitada se puede emitir al tipo de interés deseado. Cuando Masha se convierte en cliente, su información se agrega al sistema bancario central junto con los datos de cuentas y tarjetas, así como al CRM para gestionar la interacción con el cliente y posiblemente ofrecer servicios adicionales.

Todos estos sistemas deben estar sincronizados y funcionar rápidamente; de ​​lo contrario, puede esperar una avalancha de solicitudes de clientes con preguntas: “¿Qué está pasando con mi préstamo? ¿Por qué tardas tanto en responder? A pesar de la presencia de identificadores como pasaporte, INN y SNILS, generalmente no existe una identificación centralizada que vincule los datos en todos los sistemas, lo que complica la tarea de vincular la información.

Se vuelve aún más interesante cuando Masha decide cambiar alguna información de identificación. Llama al call center o viene a la oficina del banco y dice: “Me casé, tengo nuevo apellido. También me mudé y tengo un pasaporte nuevo”. Algunos sistemas no recibirán dicha información a priori. Por ejemplo, si una aplicación en el “canal de crédito” ya ha completado su ciclo de vida, permanecerá para siempre en el mismo estado en el que se encontraba inicialmente. Pero dicha información se puede actualizar simultáneamente tanto en el CRM como en el sistema bancario central.

Como cualquier empresa, un banco no puede actualizar la información de los clientes por sí solo. Incluso si la información sobre Masha surgió de fuentes externas y ella no vino ella misma, debes llamarla o enviarle una notificación de la serie: “Querida María. Ven a la oficina del banco más cercano y escribe una solicitud para cambiar a fulano de tal”.

Como resultado, la información sobre Masha se multiplica en diferentes sistemas, como los hongos después de la lluvia. En algunos lugares es más completo y relevante, pero en otros no. Digamos que ABS almacena su nombre completo, pasaporte, fecha de nacimiento, TIN y SNILS. Y en el sistema frontal solo hay contactos para la comunicación con el cliente. En el que, por cierto, Masha puede cometer un error fácilmente, confundiendo un número con otro.

Si multiplicamos todos estos registros por al menos un par de millones de clientes (lo que corresponde al tamaño medio de un banco regional), el número de registros puede superar el número de rusos. Y entonces la alta dirección del banco pregunta: “¿Cuántos clientes tenemos? Queremos crear análisis de BI basados ​​en varios criterios: actividad durante un período, número de transacciones, etc. Es necesario analizar conjuntos de datos dispersos y comprender que no hay diez Mash, sino uno, en estas líneas.

Como resultado, el sistema MDM se convierte en una estructura ramificada compleja. Pero incluso habiéndolo configurado y optimizado para todas las tareas empresariales, puedes enfrentarte a un desafío aún mayor.

Cómo el número de registros puede superar la población de un país: la fusión de dos bancos

Imaginemos una situación… En algún momento, el banco A decide expandirse y compra el banco B. El banco B comprado tiene sus propios sistemas de información que almacenan millones de registros de clientes. El banco A quiere transferir estos datos a su sistema MDM. Pero aquí viene el problema:

• Los sistemas de información del banco B son diferentes y cada uno tiene su propia base de clientes.

• El Banco B tiene su propia aplicación de banca online y CRM.

• Algunos clientes del Banco B podrían utilizar simultáneamente los servicios del Banco A.

Si simplemente combinamos todos los sistemas del Banco B con los sistemas del Banco A, es muy probable que recibamos información duplicada, tanto dentro del Banco B como entre los registros de clientes de los Bancos A y B. Además, de cara al futuro, el La superposición de bases de clientes puede alcanzar el 10% y el nivel de duplicación dentro de los sistemas puede ser significativamente mayor.

Ahora imagina cómo será para Masha cuando descubra que de repente tiene una nueva cuenta en el banco A porque su información del banco B no se integró correctamente. ¿O qué tan difícil será para una empresa atender a un cliente bajo una misma marca si la información sobre él está duplicada en diferentes partes del sistema? Sin mencionar los dolores de cabeza adicionales para los desarrolladores que tendrían que mantener múltiples sistemas con funcionalidades duplicadas.

En el camino surgen problemas adicionales:

Estos son sólo los problemas de alto nivel que hemos encontrado; de hecho, hay muchos más.

Cómo resolver el problema: opciones para encontrar duplicados

Los motivos de la aparición de duplicados y la situación son claros. Ahora veamos qué opciones de solución teníamos, con ventajas y desventajas. Hagamos una reserva de inmediato: de hecho, existen más de una docena de soluciones para la deduplicación, pero para comprenderlo, consideraremos solo las principales.

Comparación frontal

Tomamos cada registro de la base de datos del banco A y lo comparamos con cada registro de la base de datos del banco B. Pero aquí surge un problema: esto lleva mucho tiempo, ya que la complejidad crece cuadráticamente. Por ejemplo, si cada base de datos tiene un millón de registros, esto da como resultado un billón de operaciones de comparación.

Dejemos que una comparación tarde 1 µs, aunque debido al tiempo de carga de datos puede tardar más. Un billón de comparaciones es un millón de segundos (casi 12 días), lo cual es demasiado. Una empresa con una base de datos de un millón de registros necesita minutos, no días.

Algunos notarán que en un buen clúster todo será más rápido. Pero es una cuestión de precio. Ejecutar rápido en un clúster de cientos de servidores resultará costoso. Además, transmitir datos a través de la red y recopilar resultados también llevará tiempo.

Coincidencia de cadenas difusas

Puede intentar determinar por qué las entradas son similares. Defina alguna métrica de similitud entre dos registros de cadena. Hay muchos enfoques, por ejemplo:

• Distancia de Levenshtein, que muestra cuántas operaciones se necesitan para colapsar una cuerda sobre otra. Y así se evalúa el criterio de similitud.

• Algoritmo de culebrilla – cuando una cadena se divide en cadenas y se aplican funciones hash a cada una para obtener una matriz de comparación de criterio único.

• coeficiente de jaccard es un método aún más simple para determinar la similitud binaria.

El problema con estos enfoques es que no son universales y no se adaptan bien. Es necesario tener en cuenta las particularidades de los datos y su valor. Por ejemplo, la distancia de Levenshtein entre “Masha” y “Misha” es igual a uno: un reemplazo es suficiente para obtener un nombre del otro y el sistema puede considerarlos similares. Pero si consideramos a “Misha” y “Mikhail”, a pesar de sus raíces comunes, son mucho menos similares. Además, cuando se tienen en cuenta parámetros adicionales como el sexo de la persona, la situación se vuelve aún más compleja.

Otro ejemplo son las direcciones. Por ejemplo:

1. Rusia, región de Leningrado, San Petersburgo, calle 3. Stroiteley, edificio 25, apartamento 11.

2. RF, San Petersburgo, 3 Stroiteley, edificio 25, apartamento 12.

A primera vista, las direcciones parecen muy similares. La medida de similitud al comparar cadenas puede ser alta, aunque la diferencia es solo de un dígito apartamento: 11 y 12.

Motores de búsqueda

Existen motores de búsqueda ya preparados como Elasticsearch. El enfoque implica indexar datos según varios criterios. Y tenemos tantos datos que estos índices ocuparán mucho espacio y requerirán una implementación compleja. Y en general, cuando estimamos la escala de formulación de consultas de búsqueda, teniendo en cuenta la comparación y las interrelaciones confusas de diferentes documentos, quedó claro: dedicaríamos más tiempo a configurar un sistema listo para usar que si usáramos uno mismo. -enfoque escrito. Pero hablaremos de ello a continuación.

Modelos ML

Un tema muy popular en este momento, que teóricamente puede mostrar excelentes resultados. Después del entrenamiento, el modelo verifica de forma independiente las filas, las normaliza y decide si los registros se pueden fusionar. Sin embargo, existe un problema importante en el sector bancario: es difícil rastrear cómo el modelo toma decisiones. Esto contradice las exigencias de transparencia. Por ejemplo, si combina cuentas por error, el cliente puede perder dinero y será difícil saber por qué.

Esto se debe a Problema de explicabilidad de la IA (IA explicable). Es importante no sólo obtener el resultado, sino también entender cómo se logró. En el sector bancario, donde no se toleran errores, esto es fundamental.

Realizamos varios experimentos con modelos de ML y después de varias iteraciones de entrenamiento adicional obtuvimos un resultado aceptable. Pero el riesgo de trabajar con una “caja negra” persistía y éste se convirtió en el principal factor limitante.

Enfoque combinado

Quedó claro que, teniendo en cuenta los plazos, la escalabilidad del enfoque y los requisitos de velocidad y rendimiento, la forma más sencilla sería implementar todo nosotros mismos. Y para ello es adecuado un enfoque combinado: en el que tomaremos lo mejor de otros algoritmos de búsqueda duplicada, pero nos basaremos en las particularidades del sector bancario.

En resumen: asignamos a un documento (datos del cliente) varios valores indexados (hashes), los mismos criterios de comparación. Luego, utilizando índices invertidos, podemos comparar rápidamente un documento con otros.

Cómo encontramos duplicados con un enfoque combinado

Te contamos con más detalle nuestra solución por etapas: cada una de ellas resuelve los problemas descritos anteriormente.

Etapa 1. Limpieza de datos

En primer lugar, es necesario normalizar todos los datos que se encuentran en las bases de datos, es decir, llevarlos a una base única. De lo contrario, tendrás que comparar, relativamente hablando, lo cálido con lo suave. Misha y Mikhail son nombres similares, pero no muy similares. Por lo tanto, Misha necesita convertirse en Mikhail.

Para esto utilizamos el análisis. Recibimos la línea del nombre completo. Lo dividimos en componentes: apellido, nombre y patronímico por separado. Al mismo tiempo, identificamos inmediatamente errores tipográficos: no hay Mishails ni Inavovs. El filtro también se basa en la prevalencia del grupo y los errores típicos. Hasta el punto de analizar la distribución del teclado: las letras L y D están ubicadas una al lado de la otra, por lo que es fácil pasarlas por alto al escribir.

Lo mismo ocurre con la dirección que viene como una cadena. Convertimos la “Ciudad de Moscú” en la “Ciudad de Moscú”. Moscú”, “Calle Lomonosov” – en “calle. Lomonosov”, los edificios, las entradas y los apartamentos, si los hay, se resaltan por separado. Al mismo tiempo, prestamos atención a los números de pasaporte de los unos o de los números de teléfono de los siete y, si es necesario, los mostramos en registros separados para transmitirlos a los gerentes para su aclaración.

Etapa 2. Hashing

Ahora el sistema necesita explicar cómo comparar diferentes registros. Digamos que sería extraño comparar a Masha con el teléfono 1 y a Pasha con el teléfono 2. Pero Masha y Pasha con los mismos teléfonos tiene sentido. Hay algunos criterios de similitud. Se nos ocurren varios criterios de este tipo y creamos un algoritmo mediante el cual se agrupan los registros: con hash.

La función estándar se utiliza para hash. código hash() encima de la línea en Java, que se basa en el algoritmo DJB2 desarrollado por Daniel J. Bernstein.

Los hashes en sí son números que ocupan mucho menos espacio que las entradas originales, lo que hace que las operaciones sean mucho más rápidas. Evitamos la complejidad cuadrática que surgiría de una comparación de cada uno con cada uno. En lugar de millones de comparaciones, se forman grupos de decenas de registros, que luego se comparan con más detalle.

Existen tres tipos de búsqueda: completa, incremental y en tiempo real, mediante los cuales se realiza la agrupación.

Para una búsqueda completa de duplicados. Lucene tiene un identificador numérico interno (ID interno), que es estable y no cambia en el momento de la búsqueda. También hay un identificador externo (IDext), que está extraído del propio registro. El principio de búsqueda es el siguiente:

1. Memorable lastFullDate (fecha de la última descarga completa de datos).

2. La cola para aplicar actualizaciones se detiene.

3. Se realiza una reconstrucción completa del índice.

4. Todas las actualizaciones no aplicadas de la cola de modificaciones cuya fecha sea inferior a última fecha completase eliminan.

5. Las fechas se actualizan en el descriptor del índice. última fecha completa y última fecha de inclusión.

6. Se reanuda la cola para aplicar actualizaciones.

7. Se abre un iterador asíncrono de identificadores internos (se almacenan 10.000 identificadores en la memoria) del índice de búsqueda.

8. Cada ID interno entra al arroyo. Número de hilos (recuento de hilos) y su prioridad se especifica en la solicitud SOAP/REST.

Siguiente para cada hilo:

• Carga su hasher_N y registro por ID interno.

• Crea y ejecuta una consulta de búsqueda por índice, donde al menos un valor para el mismo hasher_N se cruza, y IDext no igual al actual. El resultado es una colección. ID interno candidatos a ser evaluados.

  

• Todos los encontrados están cortados. ID internoque son más pequeños que el actual, para evitar comparaciones conmutativas.

• Por cada encontrado ID interno cargando hasher_N y registro (en este paso hasher_N sólo es necesario para estadísticas).

• Se están calculando las estadísticas.

• Los registros descargados se envían para su comparación por parte de comparadores.

• Si se encuentra un duplicado, se envía al servicio de almacenamiento asíncrono, cuyo número de subprocesos es igual al 10% de recuento de hilospero no menos de 1.

Para búsqueda incremental de duplicados. El principio no es diferente de una búsqueda completa, excepto que los registros seleccionados por index_date se iteran. Al final queda así:

1. Memorable lastIncDate (fecha de la última búsqueda incremental).

2. La cola para aplicar actualizaciones se detiene.

3. Fuerza la aplicación de todas las actualizaciones de la cola última fecha de inclusión.

4. Se reanuda la cola para aplicar actualizaciones.

5. Realiza una búsqueda completa de duplicados, pero en lugar de un iterador sobre todos los identificadores internos, necesita atravesar dos. Y al crear una solicitud de búsqueda de candidatos fecha_indice debe ser mayor que la fecha de la última búsqueda incremental:
   – un iterador FULL_TO_INC (incremento a los datos existentes) – fecha_indice voluntad menos fechas de la última búsqueda incremental;
   – un iterador INC_TO_INC (incremento dentro de sí mismo) – fecha_indice voluntad más fechas de la última búsqueda incremental.

6. Se actualiza la fecha en el descriptor de índice. última fecha de inclusión.

Para encontrar duplicados en tiempo real. Aquí todo es bastante simple: crea y ejecuta una consulta donde hay al menos un valor para el mismo hasher_N se cruza con el registro actual. La solicitud está limitada por el número de candidatos encontrados: 1000 por defecto. Los candidatos encontrados se envían al comparador.

Etapa 3. Comparadores y reglas.

Como resultado, obtuvimos grupos que se pueden comparar entre sí según cualquier criterio escribiendo escenarios. En cada uno de los escenarios, especificamos adicionalmente un coeficiente de coincidencia de 0 a 100; esto nos permite comprender qué tan similares son los registros y si pueden considerarse duplicados. Notemos inmediatamente que este es un valor experimental, no un porcentaje adjunto a los valores.

Para mayor comprensión, estos son los escenarios de búsqueda más simples desde un archivo XML:

Como resultado, el cliente ve en Confluence una descripción del escenario y el mismo coeficiente de cumplimiento; se puede cambiar según la situación.

Paso 4: Actualización de datos

Como resultado, recopilamos un conjunto completo de datos de todos los sistemas fuente, los normalizamos y los deduplicamos. Algunas cosas se contraen automáticamente y el resto se pasa para la confirmación manual de las tomas.

A continuación, tenemos un flujo de cambios en los datos del cliente que deben pasar a través de nuestro servicio: actualizar la información y recalcular los hashes. Y en la próxima verificación, no realice un seguimiento de todo el volumen de registros de los clientes, sino solo de aquellos para los que ha habido cambios desde la última fecha. Convencionalmente no trabajamos con un millón de registros, sino con 10 mil que aparecen por día.

Realizamos una búsqueda completa por la noche y comprobamos la diferencia cada 10 minutos. Y además hay una búsqueda de puntos en tiempo real. Los datos introducidos por el cliente o gestor durante el día se reciben vía REST API o SOAP. Podemos verificar inmediatamente utilizando datos del sistema bancario central o CRM, y si hay una coincidencia basada en la identificación y otros datos, entonces no es necesario crear una nueva tarjeta de cliente.

En qué se ejecuta todo: Apache Lucene con algoritmo de compresión lz4 y algoritmo de descubrimiento en JGroups

¿Por qué elegiste la biblioteca Apache Lucene? Esta es la base de Elasticsearch, que permite agregar varios valores indexados (hashes) a un documento y, utilizando índices invertidos, encontrar rápidamente documentos (contrapartes) con los mismos hashes que el en cuestión.

Al mismo tiempo, Lucene admite un modo de funcionamiento híbrido:

• Los índices de registros se almacenan en la RAM a través de MMAP; obtenemos una búsqueda rápida, ya que los hashes en sí no ocupan tanto espacio como se mencionó anteriormente. No es necesario descargar cientos de gigabytes de datos del cliente.

• Cuando encontramos los identificadores de registros similares, recurrimos a la base de datos común en el disco y recuperamos información completa sobre clientes específicos. Ya se transmite a los comparadores para compararlos en diferentes campos. Por supuesto, el acceso a la información completa en el disco ralentiza un poco el proceso, pero permite optimizar el uso de los recursos.

Es decir, este enfoque hizo posible seleccionar la configuración óptima para diferentes servidores de diferentes clientes. Por un lado, esto no requiere servidores muy caros con una gran cantidad de RAM y, por otro lado, proporciona una búsqueda bastante rápida. Implementamos los servicios en Java, por lo que la integración con el sistema MDM actual se realizó sin problemas. Además, la biblioteca Lucene también está escrita en Java, lo que facilita su integración.

Pero luego, como suele suceder, surgieron las dificultades.

Problema 1: algoritmo de compresión

Toda la búsqueda se realizó en una CPU Intel Xeon Ice Lake 32 con 64 GB de RAM y almacenamiento SSD. Sin embargo, el tiempo todavía era largo con los volúmenes de bases de datos actuales: a veces hasta 10 horas, dependiendo de la carga del servidor y otros factores. Decidimos experimentar con algoritmos de compresión de datos.

Lucene tiene un códec estándar que, en teoría, debería acelerar el trabajo. De hecho, él… ralentizó la búsqueda. Comenzamos a comprender el problema con más detalle: realizamos varios experimentos e identificamos el problema. El hecho es que Lucene comprime todo el archivo: se pierde tiempo tanto en desempacar como en mover el cursor de lectura a la posición deseada. Surgió la idea de comprimir no todo el archivo, sino solo un registro específico. algoritmo lz4 — Afortunadamente, Lucene tiene la capacidad de cambiar los métodos de compresión de datos.

Como resultado, esto dio como resultado un excelente aumento de velocidad. Nuestras métricas de búsqueda independientes resultaron ser las siguientes:

Pero el cliente experimentó un aumento significativo en la productividad utilizando datos reales:

Problema 2: trabajo distribuido

La primera versión del servicio se implementó en un servidor. Pero quedó claro que con el tiempo la base de datos estaba creciendo seriamente: el número de registros se acercaba a los cien millones y “exprimir” cualquier otra cosa del servidor se volvió problemático. Llegó al punto en que no había tiempo suficiente para que una deduplicación completa de la base de datos durara toda la noche.

Decidimos utilizar servidores adicionales. Surgió la pregunta: ¿cómo hacer esto de manera óptima, utilizando las tecnologías actuales y sin introducir marcos adicionales pesados? Para esto utilizamos Biblioteca Java JGroupsque busca servidores dentro de la red utilizando un algoritmo de descubrimiento específico. Le permite configurar direcciones IP de servidores específicos y buscar automáticamente los servidores menos cargados y formar clústeres dinámicos en ellos para distribuir la carga.

Esto brinda grandes oportunidades de escalamiento: digamos que tomamos dos servidores y obtenemos un aumento de 1,8 a 1,9 veces, teniendo en cuenta los recursos para la interacción de la red.

Al mismo tiempo, dividimos todo el volumen de datos en pequeños bloques. Convencionalmente, no necesitamos tomar los 100 millones de registros: tomamos 1000 registros cada uno y los ponemos en una cola. El servidor que aceptará un bloque específico depende de su carga. Pero la funcionalidad no se vio afectada de ninguna manera: cualquier servidor esclavo puede tomar datos de una unidad de red compartida, procesar hashes y devolver el resultado en forma de duplicados encontrados al servidor maestro. Desde allí se puede obtener el resultado final de la deduplicación.

Cuál es el resultado: indicadores de desempeño y nuevos desafíos

Como resultado, el servicio se lanzó con éxito: cumplimos el objetivo en tres meses. El número de duplicados resultó ser del 10%. Algunos de ellos fueron entregados a los operadores para su procesamiento manual. Según nuestra experiencia, estos pueden considerarse datos bastante limpios, dado el tamaño de la base de clientes de los bancos.

Un poco sobre los puntos de referencia. Así es como cambia el rendimiento al realizar una búsqueda completa de duplicados en toda la base de datos en nuestro banco de pruebas de estrés en uno y dos nodos:

Teniendo en cuenta todas las optimizaciones en una base de datos de 100 millones de registros, podemos encontrar duplicados en aproximadamente una hora. Una única solicitud en tiempo real se procesa en 500 ms. Sin hash, encontrar duplicados sería demasiado lento y ni siquiera lo hicimos.

Es importante señalar que la estandarización de datos juega un papel clave en el funcionamiento del algoritmo. Tocamos este tema en etapa 2 este artículo, donde hablaron sobre la normalización de datos. Sin embargo, esto es sólo la punta del iceberg. En uno de los siguientes artículos, le brindaremos más información sobre los algoritmos de análisis de datos y le mostraremos cómo prepararlos adecuadamente para una deduplicación exitosa.