Semana 10 — Replicación

Objetivos

  • Explicar para qué se replica (disponibilidad, lecturas, cercanía) y describir la replicación con un líder, síncrona y asíncrona, con lo que cada una garantiza cuando el líder falla.
  • Reconocer las anomalías del retraso de replicación (no leer lo que uno escribió, lecturas que retroceden) y elegir una garantía para cada caso de uso.
  • Describir un failover y sus riesgos: detectar mal la falla, perder escrituras confirmadas y split brain.
  • Comparar la replicación con un líder, con varios líderes y sin líder, y calcular con quórums qué combinaciones de lecturas y escrituras se solapan.

Sesión A — Replicación con un líder: síncrona y asíncrona, retraso y failover

Lecturas:

  • Kleppmann y Riccomini, Designing Data-Intensive Applications (2.ª ed.), cap. 6 Replication: la introducción, Single-Leader Replication y la sección sobre los problemas del retraso de replicación.
  • Lectura libre: Martin Kleppmann, apuntes de sistemas distribuidos de Cambridge, sección 5, Replication.

Lecturas complementarias:

Temas:

  • Replicar es mantener la misma información en varias máquinas. Tres razones, tres escenarios: seguir funcionando si una máquina falla (disponibilidad), atender más lecturas (rendimiento) y tener los datos cerca de quien los usa (latencia). Si los datos no cambiaran, sería trivial; toda la dificultad está en propagar los cambios.
  • Replicación con un líder: un nodo, el líder, acepta las escrituras y las envía en orden a los seguidores, que las aplican en el mismo orden. Las lecturas pueden ir a cualquiera. Es lo que hacen PostgreSQL, MySQL y la mayoría de las bases de datos relacionales.
  • Cómo viaja el cambio: el log de escritura anticipada (WAL) del líder, enviado en continuo. En PostgreSQL, replicación por streaming: el seguidor es una copia física que solo acepta lecturas.
  • Síncrona: el líder espera a que el seguidor confirme antes de responder. Ninguna escritura confirmada se pierde si el líder muere; a cambio, cada escritura paga la latencia del seguidor, y si el seguidor no responde, las escrituras se detienen. Asíncrona: el líder responde sin esperar; es rápida y sigue funcionando sin seguidores, y lo confirmado en los últimos instantes puede perderse. En la práctica: semisíncrona, con un seguidor síncrono y los demás asíncronos.
  • Retraso de replicación: el tiempo entre que el líder confirma y el seguidor lo aplica. Normalmente son milisegundos; bajo carga, o con un seguidor lento, pueden ser segundos o minutos. Mientras dure, leer de un seguidor es leer el pasado. A eso se le llama consistencia eventual: si se deja de escribir, los seguidores terminan por alcanzar al líder, sin decir cuándo.
  • Anomalías que ve el usuario y la garantía que las evita. No leer lo que uno acaba de escribir (compra y no ve su compra): read-your-writes, leyendo del líder lo que el propio usuario pudo modificar, o durante unos segundos después de escribir, o esperando a que el seguidor alcance la posición de la escritura. Lecturas que retroceden en el tiempo (un comentario aparece y luego desaparece al cambiar de seguidor): lecturas monótonas, fijando cada usuario a un seguidor. Efectos antes que sus causas: lecturas con prefijo consistente.
  • Agregar un seguidor nuevo sin detener al líder: una copia consistente (un snapshot) más el log desde ese punto. Es lo que hace pg_basebackup.
  • Failover: promover a un seguidor cuando el líder falla. Tres pasos y un riesgo en cada uno. Detectar la falla: un timeout, que si es corto produce failovers innecesarios y si es largo alarga la caída. Elegir al nuevo líder: el más actualizado, lo que requiere acuerdo. Redirigir a los clientes. Riesgos: con replicación asíncrona, el nuevo líder no tiene las últimas escrituras del anterior, que ya se confirmaron; y si el líder anterior vuelve creyendo que sigue siéndolo, hay dos líderes aceptando escrituras (split brain).
  • En Tinkuy (P3): las lecturas del catálogo y el reporte pueden ir a una réplica; la confirmación de una compra no. La decisión de qué lectura va a dónde es por caso de uso, y se escribe.
  • Error común: enviar todas las lecturas a la réplica “para descargar al principal” y descubrir en producción que el usuario no ve lo que acaba de hacer.
  • Error común: creer que una réplica es un respaldo. Un DELETE equivocado se replica en milisegundos.

Sesión B — Varios líderes y sin líder: conflictos y quórums · ✂️ Dynamo

Lecturas:

Lecturas complementarias:

  • Unmesh Joshi, Majority Quorum.
  • Apuntes de Cambridge, sección 5.2, sobre quórums.

Temas:

  • Varios líderes: más de un nodo acepta escrituras y cada uno las replica a los demás. Para qué: varios centros de datos (cada región escribe en el suyo), aplicaciones que funcionan sin conexión (cada dispositivo es un líder) y edición colaborativa. El precio: dos escrituras concurrentes sobre el mismo dato en líderes distintos producen un conflicto que nadie detectó al escribir.
  • Qué hacer con un conflicto. Evitarlo: que todas las escrituras de un mismo dato pasen por el mismo líder. Resolverlo con una regla: la última escritura gana, que es simple y pierde datos en silencio. Conservar las dos versiones y que la aplicación o el usuario decida. Tipos de datos diseñados para converger (CRDT). No hay una resolución correcta en general: depende de qué significa el dato.
  • Sin líder: el cliente (o un coordinador) envía cada escritura a varias réplicas y lee de varias. Si una réplica estaba caída, se pone al día después: al leer (read repair) o con un proceso de fondo (anti-entropía).
  • Quórums: con n réplicas, una escritura se confirma con w y una lectura consulta r. Si w + r > n, el conjunto que se lee y el que se escribió se solapan en al menos una réplica, así que alguna respuesta trae el valor más reciente. Con n = 3: w = 2, r = 2 tolera una réplica caída para leer y para escribir. Se puede mover el punto: w = 3, r = 1 lee rápido y no escribe si falta una; w = 1, r = 3 al revés.
  • Lo que los quórums no garantizan: con escrituras concurrentes, con una escritura que falló en algunas réplicas, o si una réplica se restaura con datos viejos, se puede leer un valor antiguo. Para decidir cuál es el más reciente hacen falta versiones (vectores de versiones), no relojes de pared.
  • Borrar en un sistema sin líder: si se borra el dato de dos réplicas y la tercera estaba caída, al volver lo “repara” y el dato resucita. Por eso se escribe una marca de borrado, un tombstone, que se replica como cualquier otro valor.
  • ✂️ Dynamo: los requisitos (un carrito de compras que siempre acepta escrituras, aunque haya fallas) llevaron al diseño (sin líder, quórums ajustables, versiones en conflicto que la aplicación fusiona). Es el ejemplo clásico de una arquitectura derivada de un escenario de disponibilidad.
  • Cómo se elige: un líder cuando hace falta un orden único de las escrituras y se tolera un failover; varios líderes cuando hay que escribir en varios lugares aunque se desconecten, y los conflictos son raros o tienen una resolución natural; sin líder cuando la disponibilidad de escritura importa más que leer siempre lo último.
  • En Tinkuy: los asientos necesitan un orden único (no se puede “fusionar” dos ventas del mismo asiento), así que un líder. Un contador de visitas de un evento podría tolerar cualquiera de los otros.
  • Error común: “la última escritura gana” usando el reloj de cada máquina. Los relojes difieren, y la escritura que gana puede ser la que ocurrió antes.

Laboratorio — Una réplica de PostgreSQL: retraso, read-your-writes y failover

Referencias: documentación de PostgreSQL 18, Log-Shipping Standby Servers; labs/README.md (el comando pg-replica). Material: code/week-10/. En parejas.

  1. Con el principal corriendo, crear la réplica: pg-replica create. Conectarse a cada uno (psql y psql -p 5433) y comprobar quién es quién con SELECT pg_is_in_recovery(). Intentar un INSERT en la réplica y leer el error.
  2. Escribir en el principal y leer en la réplica. Ver el estado con pg-replica lag (pg_stat_replication): posición enviada, posición aplicada y retraso.
  3. Provocar retraso: con el script de code/week-10/ que escribe en ráfaga mientras la réplica aplica con demora (recovery_min_apply_delay), medir cuánto tarda una fila en aparecer en la réplica.
  4. La anomalía: el programa read-your-writes.ts crea una orden en el principal y la busca enseguida en la réplica. Correrlo cien veces y contar cuántas no la encuentra.
  5. Corregirla de dos maneras y comparar: (a) leer del principal durante unos segundos después de una escritura del mismo usuario; (b) guardar la posición del WAL después de confirmar la escritura (pg_current_wal_lsn(), en una sentencia aparte y después del COMMIT: leída dentro del mismo INSERT queda antes del registro de confirmación) y esperar a que la réplica la haya aplicado (pg_last_wal_replay_lsn()). ¿Qué cuesta cada una?
  6. Síncrona: configurar el principal con synchronous_standby_names y repetir la escritura en ráfaga. Medir la latencia de escritura antes y después. Detener la réplica (pg-replica stop) y escribir: ¿qué pasa con la escritura, y cómo se sale de ahí desde otra sesión? Volver a asíncrona.
  7. Failover: con el script de carga escribiendo órdenes numeradas, matar el principal (svc kill postgres) y promover la réplica (pg-replica promote). Comparar la última orden que el cliente recibió como confirmada con la última que existe en el nuevo principal. Con los dos servidores en la misma máquina el retraso es tan pequeño que casi nunca se pierde nada: repetirlo con el enlace cortado un segundo antes de la caída (make link-cut en la carpeta de la semana). ¿Cuántas se perdieron ahora? ¿Con replicación síncrona habría pasado?
  8. Volver a levantar el principal antiguo (svc start postgres). Ahora hay dos servidores que aceptan escrituras: escribir una fila distinta en cada uno. ¿Cómo se llama esta situación y qué tendría que haberla impedido? Al terminar, pg-replica destroy.

Entregas

Sin entregas esta semana. P3 se entrega en la semana 11.

Preguntas de repaso

  1. Con replicación asíncrona, el líder confirma una escritura y falla un instante después. ¿Qué ve el usuario tras el failover? ¿Qué atributo se intercambió por cuál al elegir asíncrona?
  2. Un usuario cambia su foto de perfil, recarga la página y ve la anterior. Nombren la anomalía y den dos formas de evitarla.
  3. ¿Por qué un timeout corto para detectar la caída del líder es peligroso? ¿Y uno largo?
  4. Con n = 5, ¿qué valores de w y r toleran dos réplicas caídas para leer y para escribir? ¿Qué garantiza w + r > n y qué no?
  5. Dos usuarios editan el mismo dato en dos líderes distintos mientras están desconectados. Den dos estrategias de resolución y un tipo de dato para el que cada una es aceptable.
  6. ¿Por qué una réplica no reemplaza a un respaldo?

Código de la semana

Compilar y probar dentro del contenedor del curso con make y make test.

Ejemplos (16)Errores (1)Pruebas (4)Laboratorio (3)Compilación (3)

Ejemplos

Los programas que usan los apuntes y la clase.

read-your-writes.tsDescargar read-your-writes.ts
// La anomalía de la semana: crear una orden en el principal y buscarla
// enseguida en la réplica, como haría una aplicación que manda todas las
// lecturas a la réplica "para descargar al principal".
//
//   node read-your-writes.ts          cien compras
//   RUNS=20 node read-your-writes.ts  veinte
//
// Cuenta en cuántas el comprador no encuentra la orden que acaba de crear.
import { createOrder, orderExists, primaryPool, replicaPool, sleep } from './shared/db.ts';
import { elapsedMs, ms, percentile } from './shared/stats.ts';

const RUNS = Number(process.env.RUNS ?? 100);

const primary = primaryPool();
const replica = replicaPool();
try {
  // Una consulta de calentamiento en cada servidor: abrir la conexión tarda
  // más que el retraso que queremos ver, y lo escondería en la primera vuelta.
  await primary.query('SELECT 1');
  await replica.query('SELECT 1');

  let missing = 0;
  const appearedAfter: number[] = [];
  for (let run = 1; run <= RUNS; run++) {
    const id = await createOrder(primary, `comprador-${run}@correo.pe`, `A-${run}`);
    const confirmed = process.hrtime.bigint();
    if (await orderExists(replica, id)) continue;

    missing++;
    // No estaba. ¿Cuánto tarda en aparecer?
    while (!(await orderExists(replica, id))) await sleep(1);
    appearedAfter.push(elapsedMs(confirmed));
  }

  console.log(`${RUNS} órdenes creadas en el principal y leídas enseguida en la réplica`);
  console.log(`no encontradas en la primera lectura: ${missing} de ${RUNS}`);
  if (appearedAfter.length > 0) {
    console.log(
      `las que faltaban aparecieron después de: p50 ${ms(percentile(appearedAfter, 50))}, ` +
        `máximo ${ms(Math.max(...appearedAfter))}`,
    );
  }
} finally {
  await primary.end();
  await replica.end();
}
db/schema.sqlDescargar db/schema.sql
-- Semana 10: el esquema más pequeño que alcanza para ver la replicación.
-- Se carga en el principal; la réplica lo recibe por el WAL, como todo lo demás.

-- Una orden de compra de una entrada. Es el dato que el comprador quiere
-- volver a ver apenas termina de comprar.
CREATE TABLE orders (
    id         bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    buyer      text        NOT NULL,
    seat       text        NOT NULL,
    created_at timestamptz NOT NULL DEFAULT now()
);

-- Escrituras numeradas por quien escribe: 1, 2, 3... Sirven para el failover,
-- porque basta mirar el número más alto para saber cuáles llegaron.
CREATE TABLE numbered_writes (
    n          integer     PRIMARY KEY,
    written_at timestamptz NOT NULL DEFAULT now()
);

-- Una fila por servidor que aceptó escrituras después del failover.
CREATE TABLE notes (
    id         bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    written_on text        NOT NULL,
    body       text        NOT NULL
);
failover/compare.tsDescargar failover/compare.ts
// Después del failover: compara lo que el cliente recibió como confirmado
// (build/last-confirmed.txt, que dejó failover/writer.ts) con lo que existe
// en el nuevo principal (la réplica promovida, puerto 5433).
//
//   node failover/compare.ts       (make compare-failover)
import { readFileSync } from 'node:fs';
import pg from 'pg';
import { DATABASE, REPLICA_PORT } from '../shared/db.ts';

const confirmed = Number(readFileSync('build/last-confirmed.txt', 'utf8').trim());
const client = new pg.Client({ database: DATABASE, port: REPLICA_PORT });
await client.connect();
try {
  const result = await client.query<{ last: number | null; total: string }>(
    'SELECT max(n) AS last, count(*) AS total FROM numbered_writes',
  );
  const last = result.rows[0]!.last ?? 0;
  console.log(`confirmadas al cliente:        1..${confirmed}`);
  console.log(`existen en el nuevo principal: 1..${last} (${result.rows[0]!.total} filas)`);
  if (last < confirmed) {
    const which = confirmed - last === 1 ? `la ${confirmed}` : `de la ${last + 1} a la ${confirmed}`;
    console.log(`confirmadas que se PERDIERON:  ${confirmed - last} (${which})`);
  } else if (last > confirmed) {
    console.log(`ninguna confirmada se perdió; además llegó la ${last}, que el cliente nunca supo si se guardó`);
  } else {
    console.log('ninguna confirmada se perdió');
  }
} finally {
  await client.end();
}
failover/kill-primary.shDescargar failover/kill-primary.sh
#!/usr/bin/env bash
# Mata el principal sin aviso, como una caída real, y deja viva a la réplica.
#
# Hace lo mismo que `svc kill postgres`, paso a paso: no se puede matar "todo
# lo que se llame postgres", porque los procesos de la réplica también se
# llaman así. Se matan solo el proceso principal del servidor del puerto 5432
# y sus hijos.
set -euo pipefail

PIDFILE="$PGDATA/postmaster.pid"
[ -f "$PIDFILE" ] || { echo "El principal no está corriendo." >&2; exit 1; }
PID="$(head -1 "$PIDFILE")"
CHILDREN="$(pgrep -P "$PID" || true)"

# Primero el padre: si se matara antes a un hijo, el padre reiniciaría el servidor.
kill -KILL "$PID"
[ -n "$CHILDREN" ] && kill -KILL $CHILDREN 2>/dev/null || true
echo "Principal muerto (kill -9 al proceso $PID y a sus hijos). La réplica sigue en el puerto 5433."
failover/link.shDescargar failover/link.sh
failover/writer.tsDescargar failover/writer.ts
// Escribe órdenes numeradas en el principal, una tras otra: 1, 2, 3...
// Cada número se cuenta como confirmado solo cuando PostgreSQL respondió al
// INSERT. Cuando el principal deja de responder, se detiene y guarda en
// build/last-confirmed.txt el último número que le confirmaron.
//
//   node failover/writer.ts        (make writer)
//
// En otra terminal: make kill-primary, pg-replica promote y make compare-failover.
import { mkdirSync, writeFileSync } from 'node:fs';
import pg from 'pg';
import { DATABASE, PRIMARY_PORT } from '../shared/db.ts';

const client = new pg.Client({ database: DATABASE, port: PRIMARY_PORT });
// Si el servidor muere entre dos escrituras, pg avisa con un evento 'error';
// sin alguien que lo escuche, el proceso terminaría sin guardar el resultado.
client.on('error', () => {});
await client.connect();
await client.query('TRUNCATE numbered_writes');

let confirmed = 0;
let attempted = 0;
let failure = '';
console.log('Escribiendo órdenes numeradas en el principal (puerto 5432)...');
for (;;) {
  attempted = confirmed + 1;
  try {
    await client.query('INSERT INTO numbered_writes (n) VALUES ($1)', [attempted]);
  } catch (error) {
    failure = error instanceof Error ? error.message : String(error);
    break;
  }
  confirmed = attempted;
  if (confirmed % 1000 === 0) console.log(`  confirmadas: ${confirmed}`);
}

mkdirSync('build', { recursive: true });
writeFileSync('build/last-confirmed.txt', `${confirmed}\n`);
console.log(`El principal dejó de responder: ${failure}`);
console.log(`Última escritura confirmada al cliente: ${confirmed}`);
console.log(`Escritura sin respuesta (no se sabe si llegó): ${attempted}`);
await client.end().catch(() => {});
quorum/cluster.tsDescargar quorum/cluster.ts
// Un almacén clave-valor replicado sin líder, con quórums: n réplicas, una
// escritura se confirma con w respuestas y una lectura consulta r.
//
// Es un simulador determinista: no hay red, ni hilos, ni azar. Quien lo usa
// dice a qué réplicas llega cada petición (`to`, `from`), y así una prueba
// puede recorrer todos los casos en vez de esperar a que alguno ocurra.
//
// Una simplificación a propósito: las versiones salen de un solo contador,
// como si hubiera un único cliente que escribe una cosa después de otra. Así
// el simulador aísla la pregunta de los quórums (¿la lectura ve la última
// escritura?) de la del orden entre escrituras concurrentes, que es otro
// problema (ver lww.ts y version-vector.ts).
import { Replica } from './replica.ts';
import type { Versioned } from './replica.ts';

export type Config = {
  n: number;
  w: number;
  r: number;
  /** Al leer, copiar el valor más nuevo a las réplicas consultadas que estaban atrasadas. Por omisión, sí. */
  readRepair?: boolean;
  /** Borrar escribiendo un tombstone (true, por omisión) o quitando la clave (false). */
  tombstones?: boolean;
};

export type WriteResult = {
  /** true si confirmaron al menos w réplicas. */
  ok: boolean;
  version: number;
  /** Las réplicas que guardaron el valor. Si ok es false, lo conservan igual: nadie lo deshace. */
  acks: number[];
};

export type ReadResult = {
  /** true si respondieron al menos r réplicas. */
  ok: boolean;
  /** El valor de la versión más alta entre las respuestas; undefined si no existe o está borrado. */
  value: string | undefined;
  /** La versión más alta vista; 0 si ninguna réplica consultada conocía la clave. */
  version: number;
  /** Las réplicas cuyas respuestas se usaron. */
  asked: number[];
  /** Las réplicas que read repair puso al día. */
  repaired: number[];
};

export class Cluster {
  readonly config: Required<Config>;
  readonly replicas: Replica[];
  private lastVersion = 0;

  constructor(config: Config) {
    const { n, w, r } = config;
    if (!(Number.isInteger(n) && n >= 1)) throw new RangeError('n debe ser un entero positivo');
    if (!(Number.isInteger(w) && w >= 1 && w <= n)) throw new RangeError('w debe estar entre 1 y n');
    if (!(Number.isInteger(r) && r >= 1 && r <= n)) throw new RangeError('r debe estar entre 1 y n');
    this.config = { readRepair: true, tombstones: true, ...config };
    this.replicas = Array.from({ length: n }, (_, i) => new Replica(i + 1));
  }

  replica(id: number): Replica {
    const found = this.replicas[id - 1];
    if (found === undefined) throw new RangeError(`No existe la réplica ${id}`);
    return found;
  }

  private all(): number[] {
    return this.replicas.map((replica) => replica.id);
  }

  /** De las réplicas pedidas, las que están arriba. */
  private reachable(ids: number[]): Replica[] {
    return ids.map((id) => this.replica(id)).filter((replica) => replica.up);
  }

  /**
   * Escribe `value` en la clave. La petición llega a las réplicas de `to`
   * (por omisión, a todas); las caídas no la reciben. Se confirma si la
   * guardaron al menos w.
   */
  write(key: string, value: string, to: number[] = this.all()): WriteResult {
    return this.store(key, value, to);
  }

  /**
   * Borra la clave. Con tombstones, es una escritura más: guarda la marca de
   * borrado con una versión nueva. Sin tombstones, quita la clave de las
   * réplicas a las que llega.
   */
  delete(key: string, to: number[] = this.all()): WriteResult {
    if (this.config.tombstones) return this.store(key, null, to);
    const version = ++this.lastVersion;
    const reached = this.reachable(to);
    for (const replica of reached) replica.remove(key);
    return { ok: reached.length >= this.config.w, version, acks: reached.map((replica) => replica.id) };
  }

  private store(key: string, value: string | null, to: number[]): WriteResult {
    const version = ++this.lastVersion;
    const reached = this.reachable(to);
    for (const replica of reached) replica.put(key, { version, value });
    return { ok: reached.length >= this.config.w, version, acks: reached.map((replica) => replica.id) };
  }

  /**
   * Lee la clave. Pregunta a las réplicas de `from` (por omisión, a todas) y
   * usa las primeras r que respondan, en el orden dado. Devuelve el valor de
   * la versión más alta.
   */
  read(key: string, from: number[] = this.all()): ReadResult {
    const responders = this.reachable(from).slice(0, this.config.r);
    const asked = responders.map((replica) => replica.id);
    if (responders.length < this.config.r) {
      return { ok: false, value: undefined, version: 0, asked, repaired: [] };
    }

    let newest: Versioned | undefined;
    for (const replica of responders) {
      const entry = replica.get(key);
      if (entry !== undefined && (newest === undefined || entry.version > newest.version)) newest = entry;
    }

    const repaired: number[] = [];
    if (newest !== undefined && this.config.readRepair) {
      for (const replica of responders) {
        const entry = replica.get(key);
        if (entry === undefined || entry.version < newest.version) {
          replica.put(key, newest);
          repaired.push(replica.id);
        }
      }
    }

    return {
      ok: true,
      value: newest?.value ?? undefined,
      version: newest?.version ?? 0,
      asked,
      repaired,
    };
  }

  /**
   * Anti-entropía: un proceso de fondo que compara las réplicas que están
   * arriba y deja en todas la versión más alta de cada clave. No depende de
   * que alguien lea.
   */
  antiEntropy(): void {
    const alive = this.replicas.filter((replica) => replica.up);
    const keys = new Set(alive.flatMap((replica) => replica.keys()));
    for (const key of keys) {
      let newest: Versioned | undefined;
      for (const replica of alive) {
        const entry = replica.get(key);
        if (entry !== undefined && (newest === undefined || entry.version > newest.version)) newest = entry;
      }
      if (newest !== undefined) for (const replica of alive) replica.put(key, newest);
    }
  }

  /**
   * Quita los tombstones de las réplicas que están arriba, para recuperar
   * espacio. Solo es seguro cuando todas las réplicas ya los tienen.
   */
  purgeTombstones(): void {
    for (const replica of this.replicas) {
      if (!replica.up) continue;
      for (const key of replica.keys()) {
        if (replica.get(key)?.value === null) replica.remove(key);
      }
    }
  }

  /** El contenido de cada réplica para una clave, en una línea, para imprimir. */
  describe(key: string): string {
    return this.replicas
      .map((replica) => {
        const entry = replica.get(key);
        const state = replica.up ? '' : ' (caída)';
        if (entry === undefined) return `r${replica.id}${state}: -`;
        return `r${replica.id}${state}: ${entry.value === null ? 'tombstone' : entry.value} v${entry.version}`;
      })
      .join(' | ');
  }
}

/** Todos los subconjuntos de tamaño k de {1..n}, en orden lexicográfico. */
export function subsets(n: number, k: number): number[][] {
  const result: number[][] = [];
  const build = (start: number, chosen: number[]): void => {
    if (chosen.length === k) {
      result.push([...chosen]);
      return;
    }
    for (let id = start; id <= n; id++) build(id + 1, [...chosen, id]);
  };
  build(1, []);
  return result;
}

/** Cuántas réplicas caídas tolera una configuración para escribir y para leer. */
export function tolerance(n: number, w: number, r: number): { writes: number; reads: number; overlap: boolean } {
  return { writes: n - w, reads: n - r, overlap: w + r > n };
}
quorum/demo.tsDescargar quorum/demo.ts
// Recorre a la vista los casos de la Sesión B con el simulador.
//
//   node quorum/demo.ts       (make quorum)
import { Cluster, subsets, tolerance } from './cluster.ts';
import { LwwNode } from './lww.ts';

const title = (text: string): void => console.log(`\n== ${text}`);

title('n = 3, w = 2, r = 2: la escritura llega a dos réplicas y se lee de otras dos');
{
  const cluster = new Cluster({ n: 3, w: 2, r: 2, readRepair: false });
  cluster.write('asiento-A1', 'libre');
  cluster.write('asiento-A1', 'vendido', [1, 2]);
  console.log(cluster.describe('asiento-A1'));
  for (const readSet of subsets(3, 2)) {
    const read = cluster.read('asiento-A1', readSet);
    console.log(`  leer de {${readSet.join(', ')}} -> ${read.value} (v${read.version})`);
  }
}

title('n = 3, w = 1, r = 1: w + r <= n, y la lectura depende de a quién le toque');
{
  const cluster = new Cluster({ n: 3, w: 1, r: 1, readRepair: false });
  cluster.write('asiento-A1', 'libre');
  const write = cluster.write('asiento-A1', 'vendido', [1]);
  console.log(`escritura confirmada: ${write.ok ? 'sí' : 'no'} (con ${write.acks.length} réplica)`);
  console.log(cluster.describe('asiento-A1'));
  for (const readSet of subsets(3, 1)) {
    const read = cluster.read('asiento-A1', readSet);
    console.log(`  leer de {${readSet.join(', ')}} -> ${read.value} (v${read.version})`);
  }
}

title('Cuántas réplicas caídas tolera cada configuración con n = 3');
for (const [w, r] of [[2, 2], [3, 1], [1, 3], [1, 1]] as const) {
  const t = tolerance(3, w, r);
  console.log(
    `  w = ${w}, r = ${r}: escribe con ${t.writes} caída(s), lee con ${t.reads} caída(s), ` +
      `${t.overlap ? 'se solapan' : 'NO se solapan'}`,
  );
}

title('Read repair: la réplica 3 estuvo caída durante una escritura');
{
  const cluster = new Cluster({ n: 3, w: 2, r: 2 });
  cluster.write('asiento-A1', 'libre');
  cluster.replica(3).up = false;
  cluster.write('asiento-A1', 'vendido');
  cluster.replica(3).up = true;
  console.log(`antes:   ${cluster.describe('asiento-A1')}`);
  const read = cluster.read('asiento-A1', [2, 3]);
  console.log(`leer de {2, 3} -> ${read.value}; reparadas: {${read.repaired.join(', ')}}`);
  console.log(`después: ${cluster.describe('asiento-A1')}`);
}

for (const tombstones of [false, true]) {
  title(`Borrar con la réplica 3 caída, ${tombstones ? 'con' : 'sin'} tombstones`);
  const cluster = new Cluster({ n: 3, w: 2, r: 2, tombstones });
  cluster.write('carrito', 'entrada VIP');
  cluster.replica(3).up = false;
  const deleted = cluster.delete('carrito');
  console.log(`borrado confirmado: ${deleted.ok ? 'sí' : 'no'}`);
  console.log(`  ${cluster.describe('carrito')}`);
  cluster.replica(3).up = true;
  const read = cluster.read('carrito', [2, 3]);
  console.log(`vuelve la réplica 3; leer de {2, 3} -> ${read.value ?? 'no existe'}; reparadas: {${read.repaired.join(', ')}}`);
  console.log(`  ${cluster.describe('carrito')}`);
}

title('La última escritura gana, con el reloj de Lima adelantado 500 ms');
{
  const lima = new LwwNode('lima', 500);
  const cusco = new LwwNode('cusco', 0);
  const first = lima.write('Rosa Quispe', 1000);
  const second = cusco.write('Rosa Quispe Mamani', 1200);
  console.log(`t = 1000 ms, en lima:  "${first.value}" con sello ${first.timestamp}`);
  console.log(`t = 1200 ms, en cusco: "${second.value}" con sello ${second.timestamp}`);
  lima.receive(second);
  cusco.receive(first);
  console.log(`después de replicar: lima = "${lima.value}", cusco = "${cusco.value}"`);
}
quorum/lww.tsDescargar quorum/lww.ts
// "La última escritura gana" (last write wins, LWW) con el reloj de cada nodo.
// Cada nodo sella sus escrituras con la hora que marca su propio reloj, y al
// juntar dos versiones se queda con la del sello más alto. Si los relojes
// difieren, el sello más alto no es el de la escritura que ocurrió después.

export type Stamped = {
  value: string;
  /** La hora que marcaba el reloj del nodo que aceptó la escritura. */
  timestamp: number;
  node: string;
};

export class LwwNode {
  readonly name: string;
  /** Cuánto adelanta (positivo) o atrasa (negativo) el reloj de este nodo, en ms. */
  readonly skewMs: number;
  private current: Stamped | undefined;

  constructor(name: string, skewMs: number) {
    this.name = name;
    this.skewMs = skewMs;
  }

  /** Lo que marca el reloj de este nodo cuando la hora verdadera es `trueTime`. */
  clock(trueTime: number): number {
    return trueTime + this.skewMs;
  }

  /** Un cliente escribe aquí cuando la hora verdadera es `trueTime`. */
  write(value: string, trueTime: number): Stamped {
    const stamped = { value, timestamp: this.clock(trueTime), node: this.name };
    this.receive(stamped);
    return stamped;
  }

  /** Llega una escritura replicada desde otro nodo: se queda la del sello más alto. */
  receive(incoming: Stamped): void {
    if (this.current === undefined || wins(incoming, this.current)) this.current = incoming;
  }

  get value(): string | undefined {
    return this.current?.value;
  }
}

/** ¿`a` le gana a `b`? Sello más alto; si empatan, desempata el nombre del nodo. */
export function wins(a: Stamped, b: Stamped): boolean {
  if (a.timestamp !== b.timestamp) return a.timestamp > b.timestamp;
  return a.node > b.node;
}
quorum/replica.tsDescargar quorum/replica.ts
// Una réplica de un almacén clave-valor sin líder: un mapa en memoria.
// Cada valor lleva un número de versión; gana siempre la versión más alta.

/** Un valor con su versión. `value: null` es un tombstone: la marca de que la clave se borró. */
export type Versioned = {
  version: number;
  value: string | null;
};

export class Replica {
  readonly id: number;
  /** Una réplica caída no recibe escrituras ni responde lecturas, pero conserva lo que tenía. */
  up = true;
  private data = new Map<string, Versioned>();

  constructor(id: number) {
    this.id = id;
  }

  get(key: string): Versioned | undefined {
    return this.data.get(key);
  }

  /** Guarda el valor solo si es más nuevo que el que tiene: aplicar dos veces lo mismo no cambia nada. */
  put(key: string, incoming: Versioned): void {
    const current = this.data.get(key);
    if (current === undefined || incoming.version > current.version) {
      this.data.set(key, { ...incoming });
    }
  }

  /** Borrado físico: la clave desaparece y no queda rastro de que existió. */
  remove(key: string): void {
    this.data.delete(key);
  }

  keys(): string[] {
    return [...this.data.keys()];
  }

  /** Una copia de todo lo que tiene, como un respaldo. */
  snapshot(): Map<string, Versioned> {
    return new Map([...this.data].map(([key, entry]) => [key, { ...entry }]));
  }

  /** Reemplaza todo lo que tiene por un respaldo (posiblemente viejo). */
  restore(snapshot: Map<string, Versioned>): void {
    this.data = new Map([...snapshot].map(([key, entry]) => [key, { ...entry }]));
  }
}
quorum/version-vector.tsDescargar quorum/version-vector.ts
// Vectores de versiones: un contador por nodo. Permiten decir, sin relojes,
// si una versión de un dato reemplaza a otra o si las dos son concurrentes
// (ninguna conocía a la otra), que es justo lo que LWW no puede distinguir.

export type VersionVector = Readonly<Record<string, number>>;

export type Order = 'equal' | 'before' | 'after' | 'concurrent';

/** Compara a con b: 'before' si b ya incluye todo lo de a; 'concurrent' si ninguna incluye a la otra. */
export function compare(a: VersionVector, b: VersionVector): Order {
  let aAhead = false;
  let bAhead = false;
  for (const node of new Set([...Object.keys(a), ...Object.keys(b)])) {
    const inA = a[node] ?? 0;
    const inB = b[node] ?? 0;
    if (inA > inB) aAhead = true;
    if (inB > inA) bAhead = true;
  }
  if (aAhead && bAhead) return 'concurrent';
  if (aAhead) return 'after';
  if (bAhead) return 'before';
  return 'equal';
}

/** El vector de una escritura nueva aceptada por `node`, hecha por quien había visto `seen`. */
export function increment(seen: VersionVector, node: string): VersionVector {
  return { ...seen, [node]: (seen[node] ?? 0) + 1 };
}

/** El máximo de cada contador: lo que conoce quien vio las dos versiones. */
export function merge(a: VersionVector, b: VersionVector): VersionVector {
  const result: Record<string, number> = { ...a };
  for (const [node, counter] of Object.entries(b)) result[node] = Math.max(result[node] ?? 0, counter);
  return result;
}

export type Version = { value: string; vector: VersionVector };

/**
 * Las versiones que un nodo conserva de una clave. Al llegar una nueva,
 * descarta las que la nueva reemplaza y la ignora si alguna ya la incluye;
 * si es concurrente con las que hay, se queda con todas (siblings) para que
 * la aplicación decida.
 */
export function addVersion(existing: readonly Version[], incoming: Version): Version[] {
  const kept: Version[] = [];
  for (const version of existing) {
    const order = compare(incoming.vector, version.vector);
    if (order === 'before' || order === 'equal') return [...existing];
    if (order === 'concurrent') kept.push(version);
  }
  return [...kept, incoming];
}
replication/burst.tsDescargar replication/burst.ts
// Una ráfaga de escrituras en el principal, medida desde quien escribe.
//
//   node replication/burst.ts                 2000 órdenes con 4 conexiones
//   WRITES=5000 CLIENTS=8 node replication/burst.ts
//
// Imprime la latencia de cada escritura (p50, p95, p99), cuánto WAL llegó a
// tener pendiente la réplica durante la ráfaga y cuánto tardó la última orden
// en aparecer en la réplica después de confirmada. Sirve para los pasos 3 y 6
// del laboratorio: la misma ráfaga con y sin demora, asíncrona y síncrona.
import { createOrder, orderExists, primaryPool, replicaPool, sleep } from '../shared/db.ts';
import { elapsedMs, ms, percentile } from '../shared/stats.ts';

const WRITES = Number(process.env.WRITES ?? 2000);
const CLIENTS = Number(process.env.CLIENTS ?? 4);

const primary = primaryPool(CLIENTS + 1);
const replica = replicaPool(1);
try {
  await primary.query('SELECT 1');
  await replica.query('SELECT 1');
  const mode = await primary.query<{ sync_state: string }>('SELECT sync_state FROM pg_stat_replication');
  console.log(`réplica: ${mode.rows[0]?.sync_state ?? 'no conectada'}`);

  // Mientras se escribe, otra conexión mira cuánto WAL le falta aplicar a la réplica.
  let writing = true;
  let maxPendingBytes = 0;
  const watcher = (async () => {
    while (writing) {
      const result = await primary.query<{ pending: string | null }>(
        'SELECT pg_wal_lsn_diff(pg_current_wal_lsn(), replay_lsn) AS pending FROM pg_stat_replication',
      );
      maxPendingBytes = Math.max(maxPendingBytes, Number(result.rows[0]?.pending ?? 0));
      await sleep(20);
    }
  })();

  const latencies: number[] = [];
  let next = 0;
  let lastId = 0;
  let lastConfirmed = process.hrtime.bigint();
  const start = process.hrtime.bigint();
  const writer = async (): Promise<void> => {
    while (next < WRITES) {
      const n = ++next;
      const before = process.hrtime.bigint();
      const id = await createOrder(primary, `rafaga-${n}@correo.pe`, `R-${n}`);
      latencies.push(elapsedMs(before));
      if (id > lastId) {
        lastId = id;
        lastConfirmed = process.hrtime.bigint();
      }
    }
  };
  await Promise.all(Array.from({ length: CLIENTS }, writer));
  const total = elapsedMs(start);

  while (!(await orderExists(replica, lastId))) await sleep(1);
  const appeared = elapsedMs(lastConfirmed);
  writing = false;
  await watcher;

  console.log(`${WRITES} escrituras con ${CLIENTS} ${CLIENTS === 1 ? 'conexión' : 'conexiones'} en ${ms(total)}`);
  console.log(
    `latencia de escritura: p50 ${ms(percentile(latencies, 50))}, ` +
      `p95 ${ms(percentile(latencies, 95))}, p99 ${ms(percentile(latencies, 99))}`,
  );
  console.log(`WAL pendiente de aplicar en la réplica, máximo visto: ${maxPendingBytes} bytes`);
  console.log(`la última orden apareció en la réplica ${ms(appeared)} después de confirmada`);
} finally {
  await primary.end();
  await replica.end();
}
replication/monotonic-reads.tsDescargar replication/monotonic-reads.ts
// Lecturas que retroceden en el tiempo. Un load balancer reparte las lecturas
// de un mismo usuario entre dos servidores que no van igual de adelantados;
// aquí son el principal y la réplica, pero pasa igual con dos réplicas.
//
//   node replication/monotonic-reads.ts
//
// El usuario cuenta las órdenes del asiento tres veces seguidas. Cada
// respuesta es correcta para el servidor que la dio; la secuencia no lo es.
import { createOrder, primaryPool, replicaPool } from '../shared/db.ts';
import type pg from 'pg';

async function countOrders(server: pg.Pool, seat: string): Promise<number> {
  const result = await server.query<{ total: string }>('SELECT count(*) AS total FROM orders WHERE seat = $1', [seat]);
  return Number(result.rows[0]!.total);
}

const primary = primaryPool();
const replica = replicaPool();
try {
  const seat = `M-${Date.now()}`;
  await replica.query('SELECT 1');
  await createOrder(primary, 'rosa.quispe@correo.pe', seat);

  // Round-robin: la primera lectura cae en el servidor adelantado, la segunda en el atrasado.
  const servers = [
    { name: 'principal', pool: primary },
    { name: 'réplica', pool: replica },
    { name: 'principal', pool: primary },
  ];
  let previous = 0;
  for (const [i, server] of servers.entries()) {
    const total = await countOrders(server.pool, seat);
    const note = total < previous ? '   <- retrocedió' : '';
    console.log(`lectura ${i + 1} (${server.name}): ${total} orden(es) del asiento ${seat}${note}`);
    previous = total;
  }
} finally {
  await primary.end();
  await replica.end();
}
shared/cluster.tsDescargar shared/cluster.ts
// Cambios de configuración de los dos servidores, para las pruebas. Son los
// mismos que hacen a mano `make delay`, `make sync-on` y `make sync-off`.
import pg from 'pg';
import { PRIMARY_PORT, REPLICA_PORT, sleep } from './db.ts';

async function admin<T>(port: number, fn: (client: pg.Client) => Promise<T>): Promise<T> {
  const client = new pg.Client({ database: 'postgres', port });
  await client.connect();
  try {
    return await fn(client);
  } finally {
    await client.end();
  }
}

/** La réplica espera `milliseconds` antes de aplicar cada transacción que recibe. */
export async function setApplyDelay(milliseconds: number): Promise<void> {
  const value = Math.trunc(milliseconds);
  await admin(REPLICA_PORT, async (client) => {
    // ALTER SYSTEM no admite parámetros; el valor es un entero, no texto de nadie.
    await client.query(`ALTER SYSTEM SET recovery_min_apply_delay = '${value}ms'`);
    await client.query('SELECT pg_reload_conf()');
    for (;;) {
      const result = await client.query<{ setting: string }>(
        "SELECT setting FROM pg_settings WHERE name = 'recovery_min_apply_delay'",
      );
      if (Number(result.rows[0]!.setting) === value) return;
      await sleep(20);
    }
  });
}

/** Activa o desactiva la replicación síncrona y espera a que el principal la vea así. */
export async function setSynchronous(enabled: boolean): Promise<void> {
  await admin(PRIMARY_PORT, async (client) => {
    // 'walreceiver' es el application_name con el que se conecta la réplica de pg-replica.
    await client.query(
      enabled ? "ALTER SYSTEM SET synchronous_standby_names = 'walreceiver'" : 'ALTER SYSTEM RESET synchronous_standby_names',
    );
    await client.query('SELECT pg_reload_conf()');
    const expected = enabled ? 'sync' : 'async';
    for (;;) {
      const result = await client.query<{ sync_state: string }>('SELECT sync_state FROM pg_stat_replication');
      if (result.rows[0]?.sync_state === expected) return;
      await sleep(20);
    }
  });
}

/** La posición actual del WAL del principal. */
export async function primaryLsn(primary: pg.Pool): Promise<string> {
  const result = await primary.query<{ lsn: string }>('SELECT pg_current_wal_lsn() AS lsn');
  return result.rows[0]!.lsn;
}

/** ¿La réplica ya aplicó el WAL hasta `lsn`? */
export async function hasReplayed(replica: pg.Pool, lsn: string): Promise<boolean> {
  const result = await replica.query<{ reached: boolean }>(
    'SELECT pg_last_wal_replay_lsn() >= $1::pg_lsn AS reached',
    [lsn],
  );
  return result.rows[0]!.reached;
}

/** Espera a que la réplica haya aplicado todo lo que el principal tiene confirmado ahora. */
export async function waitUntilCaughtUp(primary: pg.Pool, replica: pg.Pool): Promise<void> {
  const lsn = await primaryLsn(primary);
  while (!(await hasReplayed(replica, lsn))) await sleep(10);
}
shared/db.tsDescargar shared/db.ts
import pg from 'pg';

// El principal escucha en el puerto 5432 y la réplica en el 5433 (pg-replica).
// El host y el usuario salen de PGHOST y PGUSER, que el contenedor ya define.
export const DATABASE = process.env.W10_DB ?? 'arq_w10';
export const PRIMARY_PORT = 5432;
export const REPLICA_PORT = 5433;

/** Un pool contra el principal: el único servidor que acepta escrituras. */
export function primaryPool(max = 4): pg.Pool {
  return new pg.Pool({ database: DATABASE, port: PRIMARY_PORT, max });
}

/** Un pool contra la réplica: solo lecturas, y con retraso. */
export function replicaPool(max = 4): pg.Pool {
  return new pg.Pool({ database: DATABASE, port: REPLICA_PORT, max });
}

/** Crea una orden en el principal y devuelve su id. La escritura ya está confirmada al volver. */
export async function createOrder(primary: pg.Pool, buyer: string, seat: string): Promise<number> {
  const result = await primary.query<{ id: string }>(
    'INSERT INTO orders (buyer, seat) VALUES ($1, $2) RETURNING id',
    [buyer, seat],
  );
  return Number(result.rows[0]!.id);
}

/** Busca una orden en el servidor que le pasen. Devuelve si la encontró. */
export async function orderExists(server: pg.Pool, id: number): Promise<boolean> {
  const result = await server.query('SELECT 1 FROM orders WHERE id = $1', [id]);
  return result.rowCount === 1;
}

export function sleep(ms: number): Promise<void> {
  return new Promise((resolve) => setTimeout(resolve, ms));
}
shared/stats.tsDescargar shared/stats.ts
// Percentiles por rango más cercano (nearest rank), como en la semana 2:
// el percentil p de n muestras ordenadas es la que ocupa la posición ceil(p/100 · n).
export function percentile(samples: number[], p: number): number {
  if (samples.length === 0) throw new Error('No hay muestras');
  const sorted = [...samples].sort((a, b) => a - b);
  const rank = Math.max(1, Math.ceil((p / 100) * sorted.length));
  return sorted[rank - 1]!;
}

/** Milisegundos con dos decimales y coma decimal, para imprimir. */
export function ms(value: number): string {
  return `${value.toFixed(2).replace('.', ',')} ms`;
}

/** Milisegundos transcurridos desde `start` (process.hrtime.bigint()). */
export function elapsedMs(start: bigint): number {
  return Number(process.hrtime.bigint() - start) / 1e6;
}

Errores

Ejemplos con errores a propósito: no compilan, fallan o dan un resultado incorrecto. Los apuntes explican cada uno.

errors/lsn-before-commit.tsDescargar errors/lsn-before-commit.ts
// Un error fácil de cometer al esperar a la réplica: pedir la posición del WAL
// dentro de la misma sentencia que escribe. En ese momento el registro de
// COMMIT todavía no existe, así que la posición queda antes del commit. La
// réplica puede haber aplicado hasta ahí y, sin embargo, no mostrar la fila:
// una fila es visible recién cuando se aplica el commit de su transacción.
//
//   node errors/lsn-before-commit.ts      (con demora en la réplica: make delay MS=2000)
//
// Compara las dos formas: la posición tomada dentro del INSERT y la tomada
// en una consulta aparte, después de que el INSERT ya se confirmó.
import { orderExists, primaryPool, replicaPool, sleep } from '../shared/db.ts';
import type pg from 'pg';

async function replayed(replica: pg.Pool, lsn: string): Promise<boolean> {
  const result = await replica.query<{ reached: boolean }>(
    'SELECT pg_last_wal_replay_lsn() >= $1::pg_lsn AS reached',
    [lsn],
  );
  return result.rows[0]!.reached;
}

async function waitFor(replica: pg.Pool, lsn: string): Promise<void> {
  while (!(await replayed(replica, lsn))) await sleep(5);
}

const primary = primaryPool();
const replica = replicaPool();
try {
  // Se parte con la réplica al día, para que lo único pendiente sea lo de este programa.
  const start = await primary.query<{ lsn: string }>('SELECT pg_current_wal_lsn() AS lsn');
  await waitFor(replica, start.rows[0]!.lsn);

  // Mal: la posición se pide en la misma sentencia, antes del commit.
  const wrong = await primary.query<{ id: string; lsn: string }>(
    `INSERT INTO orders (buyer, seat) VALUES ('error@correo.pe', 'E-1')
     RETURNING id, pg_current_wal_insert_lsn() AS lsn`,
  );
  await waitFor(replica, wrong.rows[0]!.lsn);
  const foundWrong = await orderExists(replica, Number(wrong.rows[0]!.id));
  console.log(`posición tomada dentro del INSERT (${wrong.rows[0]!.lsn}): la réplica llegó ahí;`);
  console.log(`  ¿ve la orden? ${foundWrong ? 'sí' : 'no'}`);

  // Bien: primero se confirma la escritura; después se pregunta la posición.
  const right = await primary.query<{ id: string }>(
    `INSERT INTO orders (buyer, seat) VALUES ('error@correo.pe', 'E-2') RETURNING id`,
  );
  const after = await primary.query<{ lsn: string }>('SELECT pg_current_wal_lsn() AS lsn');
  await waitFor(replica, after.rows[0]!.lsn);
  const foundRight = await orderExists(replica, Number(right.rows[0]!.id));
  console.log(`posición tomada después del commit (${after.rows[0]!.lsn}): la réplica llegó ahí;`);
  console.log(`  ¿ve la orden? ${foundRight ? 'sí' : 'no'}`);
} finally {
  await primary.end();
  await replica.end();
}

Pruebas

Comprueban lo que afirman los apuntes; se ejecutan con make test.

test/lww.test.tsDescargar test/lww.test.ts
// "La última escritura gana" con relojes de pared, y lo que cambia con vectores de versiones.
import assert from 'node:assert/strict';
import { test } from 'node:test';
import { LwwNode } from '../quorum/lww.ts';
import { addVersion, compare, increment, merge } from '../quorum/version-vector.ts';
import type { Version } from '../quorum/version-vector.ts';

test('con relojes iguales, LWW se queda con la escritura posterior', () => {
  const lima = new LwwNode('lima', 0);
  const cusco = new LwwNode('cusco', 0);
  const first = lima.write('Rosa Quispe', 1000);
  const second = cusco.write('Rosa Quispe Mamani', 1200);
  lima.receive(second);
  cusco.receive(first);
  assert.equal(lima.value, 'Rosa Quispe Mamani');
  assert.equal(cusco.value, 'Rosa Quispe Mamani');
});

test('con un reloj adelantado, LWW descarta la escritura posterior, en silencio y en los dos nodos', () => {
  const lima = new LwwNode('lima', 500); // su reloj adelanta medio segundo
  const cusco = new LwwNode('cusco', 0);
  const first = lima.write('Rosa Quispe', 1000); // sello 1500
  const second = cusco.write('Rosa Quispe Mamani', 1200); // ocurre 200 ms después; sello 1200
  assert.ok(first.timestamp > second.timestamp);

  lima.receive(second);
  cusco.receive(first);
  // Los nodos convergen, pero al valor equivocado: ganó la escritura que ocurrió antes.
  assert.equal(lima.value, 'Rosa Quispe');
  assert.equal(cusco.value, 'Rosa Quispe');
});

test('LWW pierde la escritura posterior incluso si quien la hizo había leído la anterior', () => {
  const lima = new LwwNode('lima', 500);
  const cusco = new LwwNode('cusco', 0);
  const first = lima.write('2 entradas', 1000);
  cusco.receive(first); // cusco ya tiene la primera: no hay concurrencia alguna
  assert.equal(cusco.value, '2 entradas');
  cusco.write('3 entradas', 1200); // sello 1200 < 1500: el propio nodo la descarta
  assert.equal(cusco.value, '2 entradas');
});

test('un vector de versiones ordena dos escrituras cuando una conocía a la otra, sin mirar relojes', () => {
  const first = increment({}, 'lima'); // { lima: 1 }
  const second = increment(first, 'cusco'); // hecha por quien leyó la primera
  assert.equal(compare(first, second), 'before');
  assert.equal(compare(second, first), 'after');

  let versions: Version[] = [];
  versions = addVersion(versions, { value: '3 entradas', vector: second });
  versions = addVersion(versions, { value: '2 entradas', vector: first }); // llega tarde: se ignora
  assert.deepEqual(versions.map((version) => version.value), ['3 entradas']);
});

test('dos escrituras que no se conocían son concurrentes: se conservan las dos, no se elige una', () => {
  const inLima = increment({}, 'lima');
  const inCusco = increment({}, 'cusco');
  assert.equal(compare(inLima, inCusco), 'concurrent');

  let versions: Version[] = [];
  versions = addVersion(versions, { value: 'Rosa Quispe', vector: inLima });
  versions = addVersion(versions, { value: 'Rosa Quispe Mamani', vector: inCusco });
  assert.equal(versions.length, 2);

  // Quien lee las dos y decide escribe una versión que las reemplaza a ambas.
  const resolved = increment(merge(inLima, inCusco), 'lima');
  versions = addVersion(versions, { value: 'Rosa Quispe Mamani', vector: resolved });
  assert.deepEqual(versions.map((version) => version.value), ['Rosa Quispe Mamani']);
  assert.equal(compare(inLima, resolved), 'before');
  assert.equal(compare(inCusco, resolved), 'before');
});

test('compare: iguales, y vectores con nodos distintos', () => {
  assert.equal(compare({ a: 1 }, { a: 1 }), 'equal');
  assert.equal(compare({}, { a: 1 }), 'before');
  assert.equal(compare({ a: 2, b: 1 }, { a: 1, b: 2 }), 'concurrent');
  assert.equal(compare({ a: 2, b: 2 }, { a: 1, b: 2 }), 'after');
});
test/quorum.test.tsDescargar test/quorum.test.ts
// Lo que los apuntes afirman sobre los quórums, comprobado caso por caso.
import assert from 'node:assert/strict';
import { test } from 'node:test';
import { Cluster, subsets, tolerance } from '../quorum/cluster.ts';

const intersects = (a: number[], b: number[]): boolean => a.some((id) => b.includes(id));

test('w + r > n equivale a que todo quórum de lectura se cruce con todo quórum de escritura', () => {
  for (let n = 1; n <= 7; n++) {
    for (let w = 1; w <= n; w++) {
      for (let r = 1; r <= n; r++) {
        const alwaysIntersect = subsets(n, w).every((ws) => subsets(n, r).every((rs) => intersects(ws, rs)));
        assert.equal(alwaysIntersect, w + r > n, `n=${n} w=${w} r=${r}`);
      }
    }
  }
});

test('con w + r > n, la lectura devuelve la última escritura confirmada, sea cual sea el reparto', () => {
  for (const [n, w, r] of [[3, 2, 2], [3, 3, 1], [3, 1, 3], [5, 3, 3], [5, 4, 2]] as const) {
    for (const writeSet of subsets(n, w)) {
      for (const readSet of subsets(n, r)) {
        const cluster = new Cluster({ n, w, r });
        assert.ok(cluster.write('asiento', 'libre').ok);
        // La segunda escritura llega solo a w réplicas: las demás siguen con el valor viejo.
        assert.ok(cluster.write('asiento', 'vendido', writeSet).ok);
        const read = cluster.read('asiento', readSet);
        assert.ok(read.ok);
        assert.equal(read.value, 'vendido', `n=${n} w=${w} r=${r} W={${writeSet}} R={${readSet}}`);
      }
    }
  }
});

test('con w + r <= n hay repartos en los que la lectura devuelve un valor viejo', () => {
  for (const [n, w, r] of [[3, 1, 1], [3, 2, 1], [3, 1, 2], [5, 2, 3], [5, 3, 2]] as const) {
    let stale = 0;
    let fresh = 0;
    for (const writeSet of subsets(n, w)) {
      for (const readSet of subsets(n, r)) {
        const cluster = new Cluster({ n, w, r });
        cluster.write('asiento', 'libre');
        assert.ok(cluster.write('asiento', 'vendido', writeSet).ok, 'la escritura se confirmó');
        const read = cluster.read('asiento', readSet);
        assert.ok(read.ok);
        // Es viejo exactamente cuando los dos conjuntos no comparten ninguna réplica.
        assert.equal(read.value === 'libre', !intersects(writeSet, readSet));
        if (read.value === 'libre') stale++;
        else fresh++;
      }
    }
    assert.ok(stale > 0, `n=${n} w=${w} r=${r}: debería existir una lectura vieja`);
    assert.ok(fresh > 0, 'y también lecturas que sí ven el valor nuevo: por eso el error pasa las pruebas');
  }
});

test('n = 3, w = 2, r = 2 tolera una réplica caída para leer y para escribir, y no dos', () => {
  assert.deepEqual(tolerance(3, 2, 2), { writes: 1, reads: 1, overlap: true });
  const cluster = new Cluster({ n: 3, w: 2, r: 2 });
  cluster.replica(3).up = false;
  assert.ok(cluster.write('k', 'a').ok);
  assert.equal(cluster.read('k').value, 'a');

  cluster.replica(2).up = false;
  assert.equal(cluster.write('k', 'b').ok, false);
  assert.equal(cluster.read('k').ok, false);
});

test('mover el punto: w = 3, r = 1 no escribe si falta una; w = 1, r = 3 no lee si falta una', () => {
  const fastReads = new Cluster({ n: 3, w: 3, r: 1 });
  fastReads.replica(1).up = false;
  assert.equal(fastReads.write('k', 'a').ok, false);
  assert.equal(fastReads.read('k').ok, true);

  const fastWrites = new Cluster({ n: 3, w: 1, r: 3 });
  fastWrites.replica(1).up = false;
  assert.equal(fastWrites.write('k', 'a').ok, true);
  assert.equal(fastWrites.read('k').ok, false);
});

test('con n = 5, solo w = 3 y r = 3 toleran dos caídas en lecturas y escrituras con solapamiento', () => {
  const valid: string[] = [];
  for (let w = 1; w <= 5; w++) {
    for (let r = 1; r <= 5; r++) {
      const t = tolerance(5, w, r);
      if (t.overlap && t.writes >= 2 && t.reads >= 2) valid.push(`w=${w} r=${r}`);
    }
  }
  assert.deepEqual(valid, ['w=3 r=3']);
});

test('read repair pone al día a la réplica atrasada que participó en la lectura', () => {
  const cluster = new Cluster({ n: 3, w: 2, r: 2 });
  cluster.write('k', 'viejo');
  cluster.replica(3).up = false;
  cluster.write('k', 'nuevo');
  cluster.replica(3).up = true;
  assert.equal(cluster.replica(3).get('k')?.value, 'viejo');

  const read = cluster.read('k', [2, 3]);
  assert.equal(read.value, 'nuevo');
  assert.deepEqual(read.repaired, [3]);
  assert.equal(cluster.replica(3).get('k')?.value, 'nuevo');
});

test('sin lecturas no hay read repair: hace falta anti-entropía para las claves que nadie lee', () => {
  const cluster = new Cluster({ n: 3, w: 2, r: 2 });
  cluster.write('k', 'viejo');
  cluster.replica(3).up = false;
  cluster.write('k', 'nuevo');
  cluster.replica(3).up = true;
  assert.equal(cluster.replica(3).get('k')?.value, 'viejo');
  cluster.antiEntropy();
  assert.equal(cluster.replica(3).get('k')?.value, 'nuevo');
});

test('una escritura que no alcanzó el quórum no se deshace: una lectura posterior puede devolverla', () => {
  const cluster = new Cluster({ n: 3, w: 2, r: 2 });
  cluster.write('k', 'a');
  // Solo llega a la réplica 1: al cliente se le responde que falló.
  const failed = cluster.write('k', 'b', [1]);
  assert.equal(failed.ok, false);
  assert.deepEqual(failed.acks, [1]);

  // Según a quién se pregunte, el valor "fallido" aparece o no.
  assert.equal(cluster.read('k', [2, 3]).value, 'a');
  assert.equal(cluster.read('k', [1, 2]).value, 'b');
  // Y read repair lo acaba de propagar: ahora lo ve cualquier quórum que incluya a la 2.
  assert.equal(cluster.read('k', [2, 3]).value, 'b');
});

test('una réplica restaurada de un respaldo viejo rompe la garantía aunque w + r > n', () => {
  const cluster = new Cluster({ n: 3, w: 2, r: 2 });
  cluster.write('k', 'viejo');
  const backup = cluster.replica(1).snapshot();
  // La escritura nueva se confirma con las réplicas 1 y 2; la 3 no la recibió.
  assert.ok(cluster.write('k', 'nuevo', [1, 2]).ok);
  // La réplica 1 pierde su disco y se restaura con el respaldo.
  cluster.replica(1).restore(backup);
  // Ahora solo la réplica 2 tiene el valor nuevo: un quórum de lectura sin ella lee lo viejo.
  assert.equal(cluster.read('k', [1, 3]).value, 'viejo');
});
test/replica.test.tsDescargar test/replica.test.ts
// Lo que los apuntes afirman sobre la réplica de PostgreSQL, comprobado contra
// los dos servidores del contenedor. Necesita la réplica creada (make replica).
// Las anomalías se vuelven deterministas con una demora de aplicación en la
// réplica: durante DELAY_MS, lo confirmado en el principal no está en ella.
import assert from 'node:assert/strict';
import { after, before, test } from 'node:test';
import pg from 'pg';
import { createOrder, orderExists, primaryPool, replicaPool } from '../shared/db.ts';
import { hasReplayed, primaryLsn, setApplyDelay, setSynchronous, waitUntilCaughtUp } from '../shared/cluster.ts';

const DELAY_MS = 1500;
let primary: pg.Pool;
let replica: pg.Pool;

before(async () => {
  primary = primaryPool();
  replica = replicaPool();
  await setSynchronous(false);
  await setApplyDelay(0);
});

after(async () => {
  await setSynchronous(false);
  await setApplyDelay(0);
  await primary.end();
  await replica.end();
});

test('el principal no está en recuperación; la réplica sí', async () => {
  const onPrimary = await primary.query<{ r: boolean }>('SELECT pg_is_in_recovery() AS r');
  const onReplica = await replica.query<{ r: boolean }>('SELECT pg_is_in_recovery() AS r');
  assert.equal(onPrimary.rows[0]!.r, false);
  assert.equal(onReplica.rows[0]!.r, true);
});

test('la réplica rechaza las escrituras', async () => {
  await assert.rejects(
    replica.query("INSERT INTO orders (buyer, seat) VALUES ('x@correo.pe', 'X-1')"),
    (error: unknown) => {
      assert.ok(error instanceof Error);
      assert.equal((error as Error & { code?: string }).code, '25006'); // read_only_sql_transaction
      assert.match(error.message, /cannot execute INSERT in a read-only transaction/);
      return true;
    },
  );
});

test('lo que se escribe en el principal termina en la réplica (consistencia eventual)', async () => {
  const id = await createOrder(primary, 'rosa.quispe@correo.pe', 'T-1');
  await waitUntilCaughtUp(primary, replica);
  assert.equal(await orderExists(replica, id), true);
});

test('un DELETE también se replica: la réplica no es un respaldo', async () => {
  const id = await createOrder(primary, 'rosa.quispe@correo.pe', 'T-2');
  await waitUntilCaughtUp(primary, replica);
  assert.equal(await orderExists(replica, id), true);
  await primary.query('DELETE FROM orders WHERE id = $1', [id]);
  await waitUntilCaughtUp(primary, replica);
  assert.equal(await orderExists(replica, id), false);
});

test('con retraso, quien escribe en el principal no encuentra su orden en la réplica', async () => {
  await waitUntilCaughtUp(primary, replica);
  await setApplyDelay(DELAY_MS);
  const id = await createOrder(primary, 'rosa.quispe@correo.pe', 'T-3');
  assert.equal(await orderExists(replica, id), false, 'la réplica todavía muestra el pasado');
  assert.equal(await orderExists(primary, id), true, 'el principal sí la tiene');
});

test('con retraso, alternar entre servidores hace que una lectura retroceda', async () => {
  await waitUntilCaughtUp(primary, replica);
  const id = await createOrder(primary, 'rosa.quispe@correo.pe', 'T-4');
  const sequence = [await orderExists(primary, id), await orderExists(replica, id)];
  assert.deepEqual(sequence, [true, false]);
});

test('esperar la posición tomada después del commit garantiza que la réplica tiene la orden', async () => {
  await waitUntilCaughtUp(primary, replica);
  const id = await createOrder(primary, 'rosa.quispe@correo.pe', 'T-5');
  const lsn = await primaryLsn(primary);
  assert.equal(await hasReplayed(replica, lsn), false);
  await waitUntilCaughtUp(primary, replica);
  assert.equal(await hasReplayed(replica, lsn), true);
  assert.equal(await orderExists(replica, id), true);
});

test('la posición tomada dentro del INSERT queda antes del commit: la réplica llega ahí sin mostrar la orden', async () => {
  await waitUntilCaughtUp(primary, replica);
  const result = await primary.query<{ id: string; lsn: string }>(
    `INSERT INTO orders (buyer, seat) VALUES ('rosa.quispe@correo.pe', 'T-6')
     RETURNING id, pg_current_wal_insert_lsn() AS lsn`,
  );
  const { id, lsn } = result.rows[0]!;
  // La réplica aplica enseguida los registros anteriores al commit...
  const deadline = Date.now() + DELAY_MS / 2;
  while (!(await hasReplayed(replica, lsn)) && Date.now() < deadline) { /* enseguida */ }
  assert.equal(await hasReplayed(replica, lsn), true);
  // ...pero la fila no es visible hasta que aplique el commit.
  assert.equal(await orderExists(replica, Number(id)), false);
});

test('síncrona: al confirmar, el WAL de la escritura ya está guardado en la réplica', async () => {
  await setApplyDelay(0);
  await waitUntilCaughtUp(primary, replica);
  await setSynchronous(true);
  const result = await primary.query<{ lsn: string }>(
    `INSERT INTO orders (buyer, seat) VALUES ('rosa.quispe@correo.pe', 'T-7')
     RETURNING pg_current_wal_insert_lsn() AS lsn`,
  );
  // Sin esperar nada: lo que la réplica dice tener en disco ya pasó la posición de la escritura.
  const state = await primary.query<{ sync_state: string; flushed: boolean }>(
    'SELECT sync_state, flush_lsn >= $1::pg_lsn AS flushed FROM pg_stat_replication',
    [result.rows[0]!.lsn],
  );
  assert.equal(state.rows[0]!.sync_state, 'sync');
  assert.equal(state.rows[0]!.flushed, true);
});

test('síncrona no es read-your-writes: confirma cuando la réplica guardó el WAL, no cuando lo aplicó', async () => {
  await waitUntilCaughtUp(primary, replica);
  await setApplyDelay(DELAY_MS);
  const id = await createOrder(primary, 'rosa.quispe@correo.pe', 'T-8');
  assert.equal(await orderExists(replica, id), false);
});

test('con synchronous_commit = remote_apply, la escritura espera a que la réplica la aplique', async () => {
  await waitUntilCaughtUp(primary, replica);
  const client = await primary.connect();
  try {
    await client.query('SET synchronous_commit = remote_apply');
    const start = Date.now();
    const result = await client.query<{ id: string }>(
      "INSERT INTO orders (buyer, seat) VALUES ('rosa.quispe@correo.pe', 'T-9') RETURNING id",
    );
    const waited = Date.now() - start;
    assert.equal(await orderExists(replica, Number(result.rows[0]!.id)), true);
    assert.ok(waited >= DELAY_MS * 0.8, `la escritura pagó el retraso de la réplica (esperó ${waited} ms)`);
  } finally {
    await client.query('RESET synchronous_commit');
    client.release();
  }
});
test/tombstone.test.tsDescargar test/tombstone.test.ts
// Borrar en un sistema sin líder: por qué hace falta un tombstone.
import assert from 'node:assert/strict';
import { test } from 'node:test';
import { Cluster } from '../quorum/cluster.ts';

/** La réplica 3 está caída durante el borrado y después vuelve. */
function deleteWhileOneIsDown(tombstones: boolean): Cluster {
  const cluster = new Cluster({ n: 3, w: 2, r: 2, tombstones });
  cluster.write('carrito', 'entrada VIP');
  cluster.replica(3).up = false;
  assert.ok(cluster.delete('carrito').ok, 'el borrado se confirma con dos réplicas');
  cluster.replica(3).up = true;
  return cluster;
}

test('sin tombstones, el dato borrado resucita cuando vuelve la réplica que no vio el borrado', () => {
  const cluster = deleteWhileOneIsDown(false);
  // Un quórum de lectura que incluye a la réplica 3: ella tiene el valor y la otra, nada.
  const read = cluster.read('carrito', [2, 3]);
  assert.equal(read.value, 'entrada VIP');
  // Y read repair "arregla" a la réplica que había borrado bien.
  assert.deepEqual(read.repaired, [2]);
  assert.equal(cluster.replica(2).get('carrito')?.value, 'entrada VIP');
});

test('sin tombstones, la anti-entropía también lo resucita, sin que nadie lea', () => {
  const cluster = deleteWhileOneIsDown(false);
  cluster.antiEntropy();
  for (const id of [1, 2, 3]) assert.equal(cluster.replica(id).get('carrito')?.value, 'entrada VIP');
});

test('con tombstones, el borrado gana porque es una versión más nueva, y se propaga', () => {
  const cluster = deleteWhileOneIsDown(true);
  const read = cluster.read('carrito', [2, 3]);
  assert.equal(read.value, undefined);
  assert.deepEqual(read.repaired, [3]);
  assert.equal(cluster.replica(3).get('carrito')?.value, null);
  for (const readSet of [[1, 2], [1, 3], [2, 3]]) assert.equal(cluster.read('carrito', readSet).value, undefined);
});

test('un tombstone purgado antes de que todas las réplicas lo tengan deja resucitar el dato', () => {
  const cluster = new Cluster({ n: 3, w: 2, r: 2, tombstones: true });
  cluster.write('carrito', 'entrada VIP');
  cluster.replica(3).up = false;
  cluster.delete('carrito');
  cluster.purgeTombstones();
  cluster.replica(3).up = true;
  assert.equal(cluster.read('carrito', [2, 3]).value, 'entrada VIP');
});

test('si la purga espera a que todas lo tengan, el dato sigue borrado', () => {
  const cluster = new Cluster({ n: 3, w: 2, r: 2, tombstones: true });
  cluster.write('carrito', 'entrada VIP');
  cluster.replica(3).up = false;
  cluster.delete('carrito');
  cluster.replica(3).up = true;
  cluster.antiEntropy();
  cluster.purgeTombstones();
  for (const readSet of [[1, 2], [1, 3], [2, 3]]) assert.equal(cluster.read('carrito', readSet).value, undefined);
});

Laboratorio

Archivos de partida del laboratorio de la semana.

lab/compare.tsDescargar lab/compare.ts
// Laboratorio, paso 5: compara tres formas de leer una orden recién creada.
//
//   node lab/compare.ts              usa lab/routing.ts (lo que ustedes completan)
//   RUNS=50 WINDOW_MS=1000 node lab/compare.ts
//   THINK_MS=150 WINDOW_MS=100 node lab/compare.ts   el comprador tarda 150 ms en pedir la lectura
//
//   ninguna    siempre de la réplica (la anomalía del paso 4)
//   (a)        del principal si el comprador escribió hace menos de WINDOW_MS
//   (b)        de la réplica, después de esperar a que aplique la posición de la escritura
//
// Para cada una imprime cuántas veces no encontró la orden, cuántas lecturas
// fueron al principal y cuánto tardó la lectura.
import { createOrder, orderExists, primaryPool, replicaPool, sleep } from '../shared/db.ts';
import { elapsedMs, ms, percentile } from '../shared/stats.ts';
import type { Session } from './routing.ts';

const RUNS = Number(process.env.RUNS ?? 100);
const WINDOW_MS = Number(process.env.WINDOW_MS ?? 5000);
const TIMEOUT_MS = Number(process.env.TIMEOUT_MS ?? 10000);
// Cuánto pasa entre que el comprador escribe y pide la lectura.
const THINK_MS = Number(process.env.THINK_MS ?? 0);
// Con W10_ROUTING=solution se compara la solución de referencia, si está en la carpeta.
const routing: typeof import('./routing.ts') = await import(
  process.env.W10_ROUTING === 'solution' ? '../solution/routing.ts' : './routing.ts'
);

type Strategy = 'ninguna' | '(a) principal un rato' | '(b) esperar a la réplica';
const strategies: Strategy[] = ['ninguna', '(a) principal un rato', '(b) esperar a la réplica'];

const primary = primaryPool();
const replica = replicaPool();
try {
  await primary.query('SELECT 1');
  await replica.query('SELECT 1');
  console.log(`${RUNS} compras por estrategia; ventana de (a): ${WINDOW_MS} ms; pausa antes de leer: ${THINK_MS} ms`);

  for (const strategy of strategies) {
    let missing = 0;
    let fromPrimary = 0;
    const readLatencies: number[] = [];

    for (let run = 1; run <= RUNS; run++) {
      // Cada vuelta es un comprador distinto: escribe y enseguida quiere ver su orden.
      const session: Session = { lastWriteAt: null, lastWriteLsn: null };
      const id = await createOrder(primary, `comprador-${run}@correo.pe`, `C-${run}`);
      session.lastWriteAt = Date.now();
      if (strategy === '(b) esperar a la réplica') session.lastWriteLsn = await routing.currentLsn(primary);

      if (THINK_MS > 0) await sleep(THINK_MS);
      const before = process.hrtime.bigint();
      let server = replica;
      if (strategy === '(a) principal un rato') {
        if (routing.chooseServer(session, Date.now(), WINDOW_MS) === 'primary') server = primary;
      } else if (strategy === '(b) esperar a la réplica') {
        // Si la réplica no llega a tiempo, se lee del principal.
        const reached = await routing.waitForReplay(replica, session.lastWriteLsn!, TIMEOUT_MS);
        if (!reached) server = primary;
      }
      if (server === primary) fromPrimary++;
      const found = await orderExists(server, id);
      readLatencies.push(elapsedMs(before));
      if (!found) missing++;
    }

    console.log(
      `${strategy.padEnd(25)} no encontradas: ${String(missing).padStart(3)}   ` +
        `lecturas en el principal: ${String(fromPrimary).padStart(3)}   ` +
        `lectura p50 ${ms(percentile(readLatencies, 50))}, p95 ${ms(percentile(readLatencies, 95))}`,
    );
  }
} finally {
  await primary.end();
  await replica.end();
}
lab/routing.test.tsDescargar lab/routing.test.ts
// Pruebas del paso 5 del laboratorio. Corren contra lab/routing.ts
// (make test-lab) y fallan hasta que completen las dos funciones.
// Necesitan la réplica creada (make replica); ellas mismas ponen y quitan la demora.
import assert from 'node:assert/strict';
import { after, before, test } from 'node:test';
import pg from 'pg';
import { setApplyDelay, waitUntilCaughtUp } from '../shared/cluster.ts';
import { createOrder, orderExists, primaryPool, replicaPool } from '../shared/db.ts';

const routing: typeof import('./routing.ts') = await import(
  process.env.W10_ROUTING === 'solution' ? '../solution/routing.ts' : './routing.ts'
);

const DELAY_MS = 1500;
let primary: pg.Pool;
let replica: pg.Pool;

before(async () => {
  primary = primaryPool();
  replica = replicaPool();
  await waitUntilCaughtUp(primary, replica);
  await setApplyDelay(DELAY_MS);
});

after(async () => {
  await setApplyDelay(0);
  await primary.end();
  await replica.end();
});

test('(a) quien nunca escribió lee de la réplica', () => {
  assert.equal(routing.chooseServer({ lastWriteAt: null, lastWriteLsn: null }, 10_000, 5000), 'replica');
});

test('(a) dentro de la ventana se lee del principal; después, de la réplica', () => {
  const session = { lastWriteAt: 10_000, lastWriteLsn: null };
  assert.equal(routing.chooseServer(session, 10_001, 5000), 'primary');
  assert.equal(routing.chooseServer(session, 14_999, 5000), 'primary');
  assert.equal(routing.chooseServer(session, 15_000, 5000), 'replica');
  assert.equal(routing.chooseServer(session, 60_000, 5000), 'replica');
});

test('(b) después de esperar la posición de la escritura, la réplica tiene la orden', async () => {
  await waitUntilCaughtUp(primary, replica);
  const id = await createOrder(primary, 'lab@correo.pe', 'L-1');
  const lsn = await routing.currentLsn(primary);
  // Con la demora puesta, enseguida no está.
  assert.equal(await orderExists(replica, id), false);
  assert.equal(await routing.waitForReplay(replica, lsn, 10_000), true);
  assert.equal(await orderExists(replica, id), true);
});

test('(b) si la réplica no llega a tiempo, devuelve false en vez de esperar para siempre', async () => {
  const id = await createOrder(primary, 'lab@correo.pe', 'L-2');
  const lsn = await routing.currentLsn(primary);
  const start = Date.now();
  assert.equal(await routing.waitForReplay(replica, lsn, 200), false);
  assert.ok(Date.now() - start < DELAY_MS, 'no debe esperar más que el timeout pedido');
  assert.equal(await orderExists(replica, id), false);
});
lab/routing.tsDescargar lab/routing.ts
// Laboratorio, paso 5: dos formas de garantizar read-your-writes.
//
// Este archivo es el punto de partida. Tal como está, las dos estrategias se
// comportan igual que no hacer nada: `chooseServer` manda todo a la réplica y
// `waitForReplay` no espera. Complétenlas y comparen con `make compare`.
// Las pruebas de lab/routing.test.ts (make test-lab) dicen cuándo están bien.
import type pg from 'pg';

/** Lo que la aplicación recuerda de cada comprador entre una petición y la siguiente. */
export type Session = {
  /** Cuándo escribió por última vez (milisegundos, como Date.now()); null si nunca. */
  lastWriteAt: number | null;
  /** La posición del WAL del principal justo después de su última escritura; null si nunca. */
  lastWriteLsn: string | null;
};

export type Server = 'primary' | 'replica';

/**
 * Estrategia (a): leer del principal durante `windowMs` después de una
 * escritura del mismo comprador, y de la réplica el resto del tiempo.
 */
export function chooseServer(session: Session, now: number, windowMs: number): Server {
  // TODO: decidir con session.lastWriteAt, now y windowMs.
  void session;
  void now;
  void windowMs;
  return 'replica';
}

/**
 * Para la estrategia (b): la posición del WAL del principal en este momento.
 * Se llama después de que la escritura se confirmó, en una consulta aparte
 * (ver errors/lsn-before-commit.ts para lo que pasa si no).
 */
export async function currentLsn(primary: pg.Pool): Promise<string> {
  const result = await primary.query<{ lsn: string }>('SELECT pg_current_wal_lsn() AS lsn');
  return result.rows[0]!.lsn;
}

/**
 * Estrategia (b): esperar a que la réplica haya aplicado el WAL hasta `lsn`.
 * Devuelve true si llegó, o false si pasaron `timeoutMs` sin que llegara
 * (quien llama decide entonces qué hacer: leer del principal, o responder
 * que todavía no).
 */
export async function waitForReplay(replica: pg.Pool, lsn: string, timeoutMs: number): Promise<boolean> {
  // TODO: preguntarle a la réplica por pg_last_wal_replay_lsn() hasta que
  // alcance `lsn`, con una pausa corta entre preguntas, sin pasar de timeoutMs.
  void replica;
  void lsn;
  void timeoutMs;
  return true;
}

Compilación

Cómo se compilan y ejecutan los ejemplos.

MakefileDescargar Makefile
# Semana 10: replicación. Una réplica de PostgreSQL dentro del contenedor (el
# principal en el puerto 5432, la réplica en el 5433) y un simulador de
# quórums para lo que PostgreSQL no hace. Se usa dentro del contenedor del curso.
#
#   make                 crea la base de datos arq_w10 y la réplica (pg-replica create)
#   make lag             el estado de la réplica según el principal (pg-replica lag)
#   make delay MS=2000   la réplica aplica cada transacción 2 s tarde (MS=0 lo quita)
#   make anomaly         read-your-writes.ts: cien compras leídas enseguida en la réplica
#   make burst           una ráfaga de escrituras: latencia y retraso (WRITES=2000 CLIENTS=4)
#   make monotonic       una lectura que retrocede al cambiar de servidor
#   make wrong-lsn       errors/lsn-before-commit.ts (necesita make delay MS=2000)
#   make compare         laboratorio, paso 5: las dos correcciones de lab/routing.ts
#   make test-lab        las pruebas de lab/routing.ts
#   make sync-on         replicación síncrona (synchronous_standby_names)
#   make sync-off        vuelve a asíncrona
#   make writer          failover: escribe órdenes numeradas hasta que el principal muera
#   make link-cut        failover: la réplica deja de recibir WAL (make link-restore lo repone)
#   make kill-primary    failover: mata solo al principal, sin aviso
#   make compare-failover  failover: lo confirmado al cliente contra lo que tiene el nuevo principal
#   make quorum          el simulador de quórums, caso por caso (quorum/demo.ts)
#   make test            revisa los tipos (tsc) y corre las pruebas (test/*.test.ts)
#   make clean           borra las bases de datos, la réplica y build/
#
# Después de un failover (pg-replica promote) la réplica ya no sigue al
# principal: para volver a empezar, svc start postgres, pg-replica destroy y make.

MS ?= 2000
REPLICA_DIR = /var/lib/postgresql/replica
# psql no avisa cuando la base de datos que se va a borrar todavía no existe.
PGOPTIONS = --client-min-messages=warning
export PGOPTIONS

.PHONY: all db replica lag delay anomaly burst monotonic wrong-lsn compare test-lab sync-on sync-off \
        writer link-cut link-restore kill-primary compare-failover quorum test clean

all: db replica

db:
	@psql -X -q -d postgres -c "DROP DATABASE IF EXISTS arq_w10 WITH (FORCE)" -c "CREATE DATABASE arq_w10"
	@psql -X -q -d arq_w10 -v ON_ERROR_STOP=1 -f db/schema.sql
	@echo "Base de datos arq_w10 recién creada en el principal."

# Crea la réplica si no existe y la inicia si estaba detenida. Si quedó
# promovida de un failover anterior, avisa: ya no es una réplica.
replica:
	@if [ ! -e $(REPLICA_DIR) ]; then pg-replica create; \
	 elif ! pg_isready -q -p 5433; then pg-replica start; fi
	@[ "$$(psql -X -At -p 5433 -c 'SELECT pg_is_in_recovery()')" = t ] || { \
	  echo "El servidor del puerto 5433 fue promovido y ya no sigue al principal:"; \
	  echo "  svc start postgres && pg-replica destroy && make"; exit 1; }

lag:
	@pg-replica lag

delay:
	@psql -X -q -p 5433 -c "ALTER SYSTEM SET recovery_min_apply_delay = '$(MS)ms'" -c "SELECT pg_reload_conf()" >/dev/null
	@sleep 0.3
	@echo "La réplica aplica cada transacción con una demora de: $$(psql -X -At -p 5433 -c 'SHOW recovery_min_apply_delay')"

anomaly:
	@node read-your-writes.ts

burst:
	@node replication/burst.ts

monotonic:
	@node replication/monotonic-reads.ts

wrong-lsn:
	@node errors/lsn-before-commit.ts

compare:
	@node lab/compare.ts

test-lab: replica
	node --test lab/routing.test.ts

# 'walreceiver' es el application_name con el que se presenta la réplica.
sync-on:
	@psql -X -q -c "ALTER SYSTEM SET synchronous_standby_names = 'walreceiver'" -c "SELECT pg_reload_conf()" >/dev/null
	@sleep 0.3
	@pg-replica lag

sync-off:
	@psql -X -q -c "ALTER SYSTEM RESET synchronous_standby_names" -c "SELECT pg_reload_conf()" >/dev/null
	@sleep 0.3
	@pg-replica lag

writer:
	@node failover/writer.ts

link-cut:
	@bash failover/link.sh cut

link-restore:
	@bash failover/link.sh restore

kill-primary:
	@bash failover/kill-primary.sh

compare-failover:
	@node failover/compare.ts

quorum:
	@node quorum/demo.ts

# Las pruebas usan su propia base de datos (arq_w10_test) y dejan la réplica
# como la encontraron: asíncrona y sin demora. La solución del laboratorio se
# prueba solo si está en la carpeta.
test: replica
	tsc -p .
	@psql -X -q -c "ALTER SYSTEM RESET synchronous_standby_names" -c "SELECT pg_reload_conf()" >/dev/null
	@psql -X -q -p 5433 -c "ALTER SYSTEM RESET recovery_min_apply_delay" -c "SELECT pg_reload_conf()" >/dev/null
	@psql -X -q -d postgres -c "DROP DATABASE IF EXISTS arq_w10_test WITH (FORCE)" -c "CREATE DATABASE arq_w10_test"
	@psql -X -q -d arq_w10_test -v ON_ERROR_STOP=1 -f db/schema.sql
	@until psql -X -q -p 5433 -d arq_w10_test -c "SELECT 1 FROM notes LIMIT 1" >/dev/null 2>&1; do sleep 0.2; done
	W10_DB=arq_w10_test node --test --test-concurrency=1 "test/*.test.ts"
	@if [ -f solution/routing.ts ]; then \
	  echo "W10_ROUTING=solution node --test lab/routing.test.ts"; \
	  W10_DB=arq_w10_test W10_ROUTING=solution node --test lab/routing.test.ts; fi

clean:
	@if pg_isready -q; then \
	  psql -X -q -c "ALTER SYSTEM RESET synchronous_standby_names" -c "SELECT pg_reload_conf()" >/dev/null; \
	  psql -X -q -d postgres -c "DROP DATABASE IF EXISTS arq_w10 WITH (FORCE)" -c "DROP DATABASE IF EXISTS arq_w10_test WITH (FORCE)"; fi
	@if [ -e $(REPLICA_DIR) ]; then pg-replica destroy; fi
	rm -rf build
package.jsonDescargar package.json
{
  "name": "week-10",
  "private": true,
  "type": "module"
}
tsconfig.jsonDescargar tsconfig.json
{
  "compilerOptions": {
    "target": "es2024",
    "lib": ["es2024"],
    "module": "nodenext",
    "moduleResolution": "nodenext",
    "types": ["node"],
    "strict": true,
    "noEmit": true,
    "allowImportingTsExtensions": true,
    "erasableSyntaxOnly": true,
    "verbatimModuleSyntax": true,
    "skipLibCheck": true
  },
  "include": ["*.ts", "shared", "replication", "failover", "quorum", "errors", "lab", "solution", "test"]
}