caching - open - ¿De qué manera los sitios como LinkedIn muestran de manera eficiente la relación de 1 °, 2 ° y 3 ° nivel junto al nombre de cada persona?

linkedin register

Question

Hace poco fallé una entrevista de trabajo al responder mal una pregunta directa: ¿cómo muestran sitios como LinkedIn de manera eficiente la distancia de relación (1ª / 2ª / 3ª) entre usted y cada persona que aparece en una página (por ejemplo, en resultados de búsqueda de personas, lista de personas que trabajan en una empresa, etc.)?

<EDIT> Obtuve el "truco" esencial de la solución: encontrar una "distancia de mí" es una operación común (por ejemplo, 20x + en una sola página, 100 por sesión de inicio de sesión), para que pueda hacer parte de la "distancia de mí" X ", almacenarlo en caché y luego reutilizar ese resultado parcial en caché muchas veces para hacer que otras operaciones sean mucho más económicas. También adiviné que el resultado parcial probablemente serían mis conexiones de segundo nivel, porque "almacenar en caché todas las conexiones de tercer nivel" sería demasiado costoso en RAM y CPU. </ EDIT>

Pero cuando intenté convertir esta idea en una solución, se me ocurrió una respuesta torpe que involucraba crear cachés persistentes de conexiones de segundo nivel de todos en el sitio (lo que hubiera sido extremadamente costoso en el rendimiento y complejo de mantener), y tomé un desvío inexplicable en el uso de Bloom Filters de una manera que tenía poco sentido técnico. ¡No me hubiera contratado después de una respuesta como esa!

Más tarde, al pensar en el problema sin la presión de una entrevista que colgaba sobre mi cabeza, obtuve una respuesta más razonable.

• Cree una forma muy rápida de obtener las conexiones de primer nivel para cada lote de ID de usuario (tamaño de lote de hasta ~ 1000?). Esto probablemente signifique un clúster dedicado de servidores con muchas RAM que pueden almacenar en caché las conexiones de primer nivel de la red en la memoria. Afortunadamente, 50 millones de miembros x promedio. 100 conexiones por miembro x 4 bytes por ID de miembro = <25 GB para almacenar en caché en la RAM, lo cual es factible con hardware a un precio razonable. Y el número de cambios por día va a ser inferior al 1%, por lo que mantener el caché actualizado no es demasiado difícil. (Tenga en cuenta que una base de datos relacional probablemente sería una mala elección para implementar esta memoria caché porque el patrón de acceso de "muchas E / S aleatorias" mata el rendimiento de la base de datos relacional).

• cuando un usuario inicia sesión, almacena en caché sus conexiones de segundo nivel obteniendo conexiones de primer nivel de cada conexión de primer nivel, y pega una tabla hash (clave = ID de segundo nivel, valor = matriz de conexiones de primer nivel que lo conectan) . Guarde también sus conexiones de primer nivel en la memoria caché para que pueda recuperar el primer y el segundo nivel mediante una sola llamada a su servidor de caché remota. Los ID de usuario son fácilmente particionables, por lo que un caché distribuido como memcached puede funcionar bien para esto.

• para cualquier ID de usuario, para saber si está en su "red" y qué relación tiene para usted (1 °, 2 °, 3 °), haga lo siguiente:

  1. si la ID está en tus conexiones de primer nivel, detente.
  2. intente buscar la ID en su hashtable de conexiones de segundo nivel en caché. Si lo encuentra, devuelva la matriz de conexiones que lo conectan.
  3. busque las conexiones de primer nivel de la ID y repita el paso 2 para cada una de ellas. Agregue todos los resultados en una única matriz y devuélvalos.
  4. <EDIT> refactorizar en una implementación por lotes ("distancia de búsqueda entre N y N usuarios diferentes") para que pueda obtener todos los resultados remotos del paso 3 sin tener que hacer hasta N llamadas remotas. </ EDIT>

Pero estoy seguro de que hay mejores respuestas para esto. ¿Lo que es tuyo? Si desea un desafío adicional, intente simular una situación de inteview (no se pueden buscar soluciones en la Web).

Tenga en cuenta que la pregunta era acerca de una solución óptima, independientemente de cómo LinkedIn realmente lo hace hoy , que busqué después de que escribí mi propia respuesta anterior.

Answer 1

¿Los datos de LinkedIn no están representados como un gran gráfico gigante? y cuando una persona inicie sesión, el sistema habría manejado a su nodo, y luego haciendo un primer cruce ancho para 3 niveles, el sistema mantendría estos nodos como un conjunto (junto con la información de nivel), y cuando una persona aparece en la página web , el sistema realiza una búsqueda en este conjunto de nodos y muestra la distancia de relación.

Esta es mi suposición. Por favor, siéntase libre de señalar, lo que lo hace impráctico.

Answer 2

Curiosamente, la tecnología de 1970 haría un buen trabajo modelando esto. El modelo de base de datos de red maneja eficientemente este tipo de relación.

No es eficiente en términos de consultas ad hoc o mantenimiento del modelo de datos, por lo que cayó en desgracia con el aumento de los modelos de datos relacionales.

Answer 3

Es posible que pueda aprovechar los axiomas sobre redes de redes pequeñas para optimizar este tipo de recorrido.

Las pequeñas redes mundiales se caracterizan por "centros" que representan interconexiones muy densas de otros nodos. La mayoría de los nodos en la red generalmente se conectan a unos pocos saltos a un nodo topológico cercano (1-4 saltos de distancia) o se enrutarán a través de uno o más de tales concentradores. Esta es una de las principales razones por las que las redes mundiales pequeñas se comportan de la manera en que lo hacen.

Answer 4

No estoy seguro de la estructura de la tabla, o la complejidad del sistema, pero aquí hay un ejemplo simple de SQL Server usando un CTE recursivo:

DECLARE @People table (PersonID int, Name varchar(10))
DECLARE @Network table (PersonID int, NetworkedPersonID int)
INSERT INTO @People VALUES (1,''AAA'')
INSERT INTO @People VALUES (2,''BBB'')
INSERT INTO @People VALUES (3,''CCC'')
INSERT INTO @People VALUES (4,''DDD'')
INSERT INTO @People VALUES (5,''EEE'')
INSERT INTO @People VALUES (6,''FFF'')
INSERT INTO @People VALUES (7,''GGG'')
INSERT INTO @People VALUES (8,''HHH'')
INSERT INTO @Network VALUES (1,2)
INSERT INTO @Network VALUES (1,3)
INSERT INTO @Network VALUES (2,5)
INSERT INTO @Network VALUES (2,7)
INSERT INTO @Network VALUES (4,8)
INSERT INTO @Network VALUES (7,8)
INSERT INTO @Network VALUES (7,3)
INSERT INTO @Network VALUES (8,9)
DECLARE @TargetPersonID  int
SET @TargetPersonID=1

;WITH NetworkLevels AS
(   SELECT
        NetworkedPersonID,1 AS NetworkLevel
        FROM @Network
        WHERE PersonID=@TargetPersonID
    UNION ALL
    SELECT
        n.NetworkedPersonID, l.NetworkLevel+1
        FROM @Network                n
            INNER JOIN NetworkLevels l ON n.PersonID=l.NetworkedPersonID
    WHERE l.NetworkLevel<=2
)
SELECT * FROM NetworkLevels

SALIDA:

NetworkedPersonID NetworkLevel
----------------- ------------
2                 1
3                 1
5                 2
7                 2
8                 3
3                 3

(6 row(s) affected)

Answer 5

Para implementar

DistanceCategory(A,B): { 1, 2, 3+}

Use el hecho de que las conexiones son bidireccionales.

Almacene las conexiones de primer nivel como una lista ordenada en algún dolor de KV:

Key: [UserFromId,UserToId].
Value: UserToId

Pseudocódigo:

DistanceCategory(A,B)
{
    if ( exists([A,B]) )
        return 1;
    if ( firstCommonElement(getAll([A,B]), getAll([A,B])) != null )
        return 2;
    return 3;
}

Complejidad: O (C1 + C2). C1, C2 - número de conexión de ambos usuarios.

Answer 6

Si lo piensas bien, hacer esto en SQL podría ser muy intensivo en el uso del procesador.

Teniendo en cuenta eso y el hecho de que finalmente se usará en todas partes, y ese espacio es relativamente barato ... Sugeriría crear un índice usando Lucene (o Lucene.NET) dependiendo de su preferencia de idioma. Podrías hacer un par de cosas de esta manera.

Puede crear una estructura de datos de tipo árbol y rastrear recursivamente su índice buscando todos los nodos principales o nodos secundarios y sus nodos principales o secundarios según sus necesidades en ese momento.

O podría escribir todas las relaciones a medida que se crean (el espacio es un concepto barato). Este sería un proceso de escritura única (que no se actualizaría de todas las maneras). Cuando se crea o se revoca una relación, debe poner en cola una actualización de su índice (cola porque no desea abrir para escribir para solicitudes individuales ... lote las actualizaciones de índice). Luego, podría leer esta estructura realmente plana para obtener los ID en cuestión.

Con los ID en la mano (de cualquier tipo de búsqueda que realice), puede ir al DB para obtener la información requerida de alrededor. Luego, almacene en caché su salida para minimizar aún más lo que sería una búsqueda muy rápida, consulta de DB, creación de datos ... pero aún más rápido si solo proviene de la memoria caché.

Use algo como Velocity, MemCached o MemCached Win32 para el almacenamiento en caché centralizado en una granja de servidores web.