Saltearse al contenido
NamiDB NamiDB

LSM sobre object storage

NamiDB usa un LSM tree (log-structured merge) montado sobre un object store. Los bloques clásicos del LSM — memtable, WAL, SSTs inmutables, compaction leveled — todos se mapean naturalmente sobre el modelo de object storage.

Las capas

┌──────────────────────────────────────────────┐
│  Memtable                                    │  in RAM, write side
│  (concurrent skip-list, latest per key)      │
├──────────────────────────────────────────────┤
│  WAL                                         │  in the bucket
│  (append-only segments, durable on commit)   │
├──────────────────────────────────────────────┤
│  L0 SSTs   ← memtable flushes                │  in the bucket
│  L1 SSTs   ← compaction of L0                │  in the bucket
└──────────────────────────────────────────────┘

El motor shippea con dos niveles persistentes — L0 (rangos solapados, producidos por flush) y L1 (no solapados, producidos por compaction). Niveles más profundos son roadmap.

Camino de escritura

  1. La mutación de Cypher parsea, planea y ejecuta contra el snapshot actual.
  2. Append al WAL — cada registro se appendea al segmento de WAL actual y se hace flush antes de que la llamada retorne. Esto es lo que da durabilidad en commit_batch.
  3. Insert en la memtable — el registro aterriza en la memtable in-RAM para que las lecturas siguientes lo vean.
  4. CAS del manifest — el LSN watermark avanza. Se publica una nueva versión del manifest.

Cuando la memtable crece más allá de un umbral (o el intervalo de flush tickea), se convierte en un SST L0 — un archivo Parquet (nodos) o de formato custom (aristas), subido al bucket, y después referenciado desde la siguiente versión del manifest. Los segmentos de WAL que contribuyeron a ese flush se vuelven elegibles para truncación.

Camino de lectura

  1. Abrir un snapshot en la versión actual del manifest.
  2. Planear la query (optimizador basado en costos, predicate pushdown, factorización).
  3. Para cada node-pattern: sondear la memtable, después L0, después L1, …, mergeando las versiones visibles por LSN.
  4. Para cada edge-pattern: caminar la CSR adjacency (cache in-memory keyado por SST id), leyendo los streams de propiedades de aristas on demand.
  5. Aplicar filtros, proyecciones, joins. Devolver filas.

Compaction

La compaction es leveled:

  • Los SSTs de L0 pueden solaparse en rango de claves.
  • Los SSTs de L1 tienen rangos de claves no solapados.
  • Cuando L0 acumula demasiados archivos, NamiDB los mergea a L1, descartando tombstones y versiones superseded. Los sidecars persistentes de SST (por ejemplo, los índices de propiedad única) se re-emiten sobre las salidas mergeadas para que el camino rápido sobreviva a la compaction.

Las salidas de compaction se suben como objetos nuevos, después se swapean atómicamente al manifest vía CAS. Los archivos viejos siguen siendo legibles hasta que ningún snapshot los referencie — entonces el GC los reclama.

Qué es distinto de un LSM disk-resident

  • No hay fsync sobre el archivo — la primitiva de durabilidad es “el PUT devolvió 200 OK”. El object store maneja la durabilidad física.
  • No hay write amplification en los appends chicos al WAL — cada append al WAL es un PUT (o un upload streaming para batches grandes).
  • Las lecturas son GETs, no lecturas del file system. Los ranged reads con headers Range: nos dejan traer solo los row groups, solo las columnas de propiedades, solo las páginas de bloom filter que necesitamos (RFC-003).
  • Los flushes grandes usan PUT multipart. Los cuerpos de SST ≥ 4 MiB se suben como partes de 5 MiB con concurrencia 8-way in-flight (object_store::buffered::BufWriter); los cuerpos chicos conservan el PUT único + la protección de colisión vía PutMode::Create (desde v0.4.0).

Ver también