La gestión eficiente de datos relacionales a escala de "hyperscaler" para casos de uso transaccionales (OLTP) presenta un desafío fundamental en la computación distribuida: cómo ofrecer alta disponibilidad y baja latencia para consultas complejas (traversals) sobre grafos masivos, sin incurrir en la sobrecarga de sistemas de grafos OLAP tradicionales. Este problema se agrava cuando se requiere consistencia eventual en entornos multi-región y la capacidad de evolucionar el esquema del grafo.

La Abstracción de Grafo de Netflix aborda esto mediante la construcción de una capa semántica sobre primitivas de almacenamiento distribuido existentes (Key-Value y TimeSeries), optimizando la estructura de los índices para traversals y aplicando estrategias de caching y consistencia eventual. La clave reside en el desacoplamiento de los enlaces de los bordes de sus propiedades y el uso de índices forward/reverse, junto con un sistema de esquemas que permite optimizaciones en tiempo de consulta y asegura la calidad de los datos.

Arquitectura del Sistema

La Abstracción de Grafo de Netflix se asienta sobre la Abstracción Key-Value (KV) para la vista en tiempo real y, opcionalmente, la Abstracción TimeSeries (TS) para datos históricos. EVCache se utiliza para el caching de baja latencia. El Data Gateway Control Plane gestiona los esquemas del grafo y automatiza el aprovisionamiento de datasets.

El modelo de datos es un Property Graph con nodos y bordes fuertemente tipados, cada uno con propiedades. Los datos se organizan en 'namespaces', cada uno asociado a una tabla KV subyacente. Los nodos se almacenan en namespaces KV dedicados, permitiendo lecturas eficientes de todas las propiedades de un nodo en una única búsqueda de partición. Los bordes utilizan dos índices distintos: uno para los enlaces (adjacency list) y otro para las propiedades de los bordes. Esta separación permite upserts eficientes de propiedades y evita 'wide rows' en bases de datos como Cassandra. Se mantienen índices 'forward' y 'reverse' para soportar traversals bidireccionales, utilizando un identificador lexicográfico para las propiedades de los bordes para garantizar el acceso en una única llamada a la base de datos.

Las estrategias de caching incluyen 'write-aside caching' para enlaces de bordes (reduciendo la amplificación de escritura) y 'read-aside caching' con EVCache para propiedades (reduciendo la amplificación de lectura). La consistencia es eventual, con mecanismos de 'entropy repair' basados en Kafka para reintentos y resolución de conflictos Last-Write-Wins (LWW). Las eliminaciones de nodos son asíncronas para evitar latencias inaceptables. La replicación global entre regiones es asíncrona, contribuyendo a la consistencia eventual del sistema.

Flujo de Escritura de Borde con Caching

  1. 1 Servicio de Abstracción Recibe solicitud de escritura de borde.
  2. 2 Cache Write-Aside Verifica si el enlace de borde ya existe para evitar escritura redundante.
  3. 3 KV Abstraction (Enlaces) Persiste enlaces de borde en índices forward y reverse.
  4. 4 KV Abstraction (Propiedades) Persiste propiedades de borde usando ID lexicográfico.
  5. 5 Kafka (Entropy Repair) Mecanismo de reintento para garantizar consistencia eventual.
  6. 6 EVCache (Invalidación) Invalida entradas de cache de propiedades (si aplica).

Flujo de Traversal de Grafo (1-hop)

  1. 1 Cliente gRPC Envía TraversalRequest con nodo de inicio y filtros.
  2. 2 Servicio de Abstracción Carga esquema del grafo en memoria.
  3. 3 Planificador de Consulta Usa esquema para construir rutas de traversal posibles y optimizadas.
  4. 4 EVCache (Read-Aside) Intenta obtener datos de propiedades de nodos/bordes desde cache.
  5. 5 KV Abstraction (Enlaces) Realiza Range Read en índice forward/reverse para obtener enlaces.
  6. 6 KV Abstraction (Propiedades) Realiza Point Read en índice de propiedades para enlaces coincidentes.
  7. 7 Servicio de Abstracción Aplica filtros, ordenación y límites; devuelve resultados.
CapaTecnologíaJustificación
storage Key-Value (KV) Abstraction Almacenamiento primario para la vista en tiempo real de nodos y bordes. Proporciona particionamiento de datos e idempotencia con Last-Write-Wins.
storage TimeSeries (TS) Abstraction Almacenamiento opcional para la vista histórica de la evolución del grafo.
cache EVCache Capa de caching para lograr latencias de milisegundos, integrada con la Abstracción KV. Soporta caching a nivel de registro e ítem.
orchestration Data Gateway Control Plane Gestiona esquemas de grafo, automatiza el aprovisionamiento, eliminación y configuración de datasets en KV y TS.
messaging Kafka Utilizado en el mecanismo de reintento para 'entropy repair' y garantizar la consistencia eventual en escrituras paralelas.
networking gRPC API de traversal personalizada, inspirada en Gremlin, para la exploración del grafo distribuido.

Trade-offs

Ganancias
  • ▲ Eficiencia de upserts de propiedades
  • ▲ Prevención de 'wide rows' en bases de datos
  • ▲ Reducción de amplificación de escritura
  • ▲ Reducción de amplificación de lectura
Costes
  • ▲ Escrituras no atómicas para bordes (múltiples namespaces)
  • ▲ Consistencia eventual (no estricta) en escrituras y eliminaciones
  • △ Mayor consumo de memoria con caching write-through (WIP) 
{
"edgeConfig": {
"edgeMappings": [
{
"edgeMappingKey": {
"fromNodeType": "account",
"edgeType": "owns",
"toNodeType": "profile"
},
"directionType": "UNIDIRECTIONAL"
},
{
"edgeMappingKey": {
"fromNodeType": "profile",
"edgeType": "linked_to",
"toNodeType": "device"
},
"directionType": "BIDIRECTIONAL"
}
]
}
}
Ejemplo de cómo se define un esquema de grafo, especificando mappings de bordes entre tipos de nodos y sus propiedades.
TraversalRequest.newBuilder()
.setNamespace("<graph-namespace>")
.setTraversalQuery(
TraversalQuery.newBuilder()
.setStartNode(node("device", "my-device-id"))
.setTraversal(
Traversal.newBuilder()
.setEdgeLimit(5)
.setDirectionTraversal(
DirectionTraversal.newBuilder()
.setDirection(IN)
.addNodePropertiesSelections(propSelection("account", "created_at"))
.addNodePropertiesSelections(propSelection("profile", "last_active"))
.setDirectionFilter(
DirectionFilter.newBuilder()
.setTypeMatchingStrategy(EXCLUDE_NON_TARGETED)
.addAllNodeFilters(typeFilters("account", "profile")))))
.addNextTraversals(
Traversal.newBuilder()
.setOrder(LATEST)
.setEdgeLimit(200)
.setDirectionTraversal(
DirectionTraversal.newBuilder()
.setDirection(OUT)
.addEdgePropertiesSelections(propSelection("watched", "view_time"))
.addEdgePropertiesSelections(propSelection("has_plan", "active"))
.setDirectionFilter(
DirectionFilter.newBuilder()
.setTypeMatchingStrategy(EXCLUDE_NON_TARGETED)
.addAllNodeFilters(typeFilters("title", "plan")))))))
.build();
Ejemplo de cómo se construye una solicitud de traversal utilizando la API gRPC personalizada, encadenando traversals y aplicando filtros.

Fundamentos Teóricos

El diseño de sistemas de grafos distribuidos a gran escala se basa en principios fundamentales de la teoría de grafos y las bases de datos distribuidas. La elección del modelo de Property Graph es un estándar de facto en la industria, con raíces en la representación de datos relacionales y semánticos. La gestión de la consistencia eventual en un sistema distribuido multi-región se alinea con los teoremas de CAP y PACELC, donde se prioriza la disponibilidad y la tolerancia a particiones sobre la consistencia estricta, un compromiso común en sistemas a escala de hyperscaler. La estrategia de índices forward/reverse para bordes es una aplicación directa de las listas de adyacencia, una estructura de datos clásica para representar grafos, optimizada para búsquedas direccionales. La resolución de conflictos Last-Write-Wins (LWW) es un patrón bien establecido en sistemas distribuidos para manejar actualizaciones concurrentes en un modelo de consistencia eventual, a menudo visto en sistemas como DynamoDB o Cassandra, que se remonta a conceptos de CRDTs (Conflict-free Replicated Data Types) aunque no se menciona explícitamente.