Operaciones atómicas y objetos inmutables en JavaScript

Problema

Un cerrojo para un solo +1

Una venta relámpago: 100 auriculares a mitad de precio, a las 10:00. La página del producto se abre miles de veces por segundo, y cada apertura incrementa el contador de visitas. De la lección sobre bloqueo sabes cómo no perder incrementos: un cerrojo alrededor de views++.

Eso es correcto. Pero cada hilo hace cola delante del cerrojo para un único +1. Un hilo que no consigue el cerrojo suele ser puesto a dormir y despertado más tarde por el sistema operativo. Eso cuesta mucho más que la suma misma.

El segundo problema es peor. El último artículo se compra con «si hay uno, disminuir en 1». Son dos pasos, y entre ellos otro hilo puede llevarse el mismo artículo.

La idea

Un paso indivisible

El procesador tiene instrucciones que leen, cambian y escriben una celda de memoria en un paso indivisible. Ningún otro hilo puede meterse en medio. Esto es una operación atómica. No hay cerrojo, nadie hace cola y nadie duerme.

En JavaScript las operaciones atómicas están en Atomics y trabajan sobre un Int32Array (u otro arreglo de enteros) encima de un SharedArrayBuffer: la memoria que ven varios Workers. Atomics.add(array, index, 1) es el +1 atómico. Lo viste en la lección sobre hilos. En el código async normal de un solo hilo no necesitas nada: allí nadie puede interrumpir views++.

Míralo

El contador de visitas

Cuatro hilos, cada uno con 100 000 visitas:

import { Worker, isMainThread, workerData } from "node:worker_threads";
import { once } from "node:events";

if (isMainThread) {
  const views = new Int32Array(new SharedArrayBuffer(4));
  const workers = [1, 2, 3, 4].map(
    () => new Worker(new URL(import.meta.url), { workerData: views }),
  );
  await Promise.all(workers.map((worker) => once(worker, "exit")));
  console.log(`Vistas: ${views[0]}`);
} else {
  for (let i = 0; i < 100_000; i++) {
    Atomics.add(workerData, 0, 1);
  }
}

Vistas: 400000

400 000 en cada ejecución. Sin el +1 atómico sería menos y distinto cada vez, como en la lección sobre condiciones de carrera.

Más precisamente, para curiosos

Atomics solo funciona con arreglos de enteros sobre un SharedArrayBuffer. Los objetos, arreglos y números normales no se comparten entre Workers: postMessage los copia. Así que en JavaScript el estado compartido existe solo donde lo has pedido explícitamente.

¿Cuánto más rápido que un cerrojo es? Depende de la máquina y de cuántos hilos peleen por una celda. Sin pelea, un +1 atómico son unos pocos nanosegundos. Un cerrojo sin pelea se acerca. La diferencia llega con muchos hilos: entonces el cerrojo pone hilos a dormir, mientras que la operación atómica solo repite.

La idea

Comprobar y cambiar: compare-and-set

Comprar no es solo −1. Es «si hay al menos uno, disminuir en 1». La comprobación y el cambio deben ser un solo paso.

Para esto hay una operación atómica más general: compare-and-set (CAS). Le das dos números: lo que crees que hay y lo que quieres que haya. Cambia el valor solo si sigue siendo lo que crees, y te dice si lo consiguió. Si otro hilo lo ha cambiado entretanto, CAS no toca nada y responde «no».

Entonces comprar es un bucle:

leer las existencias;
si es 0, rechazar;
CAS: «si sigue siendo tanto, déjalo en uno menos»;
si CAS falla, alguien ha comprado entretanto: volver a 1.

En JavaScript esto es Atomics.compareExchange(array, index, expected, new). Devuelve el valor que encontró. Si es el esperado, el cambio se ha hecho.

Míralo

Los últimos tres auriculares

// cells: Int32Array sobre un SharedArrayBuffer
const STOCK = 0, SOLD = 1, REFUSED = 2;

function tryBuy(cells) {
  while (true) {
    const left = Atomics.load(cells, STOCK);
    if (left === 0) return false; // agotado
    const was = Atomics.compareExchange(
      cells, STOCK, left, left - 1);
    if (was === left) return true;
    // alguien cambió stock: leer otra vez
  }
}

Paso a paso, en palabras

Los últimos 3 auriculares: las existencias son 3. Los Workers A y B llaman a tryBuy() al mismo tiempo.
A lee las existencias: left = 3.
B las lee antes de que A haya cambiado nada: también 3.
B: compareExchange(…, 3, 2). «Si todavía es 3, ponlo en 2.» Todavía es 3, así que se escribe 2. B compró.
A prueba lo mismo: «si todavía es 3…». Ahora es 2, así que no se escribe nada y la respuesta es false. No se pierde nada.
A no espera ni se rinde: el bucle da otra vuelta y A lee de nuevo: 2. Ningún Worker ha dormido.
A: «si todavía es 2, ponlo en 1». Todavía es 2: se escribe 1. A también compró.
Dos compradores, dos vendidos, existencias 1. No hay cerrojo: el procesador comprueba y escribe en un solo paso, y el que pierde solo repite el bucle.

Nadie espera: el hilo que perdió solo repite dos líneas. Esto se llama lock-free. Cien artículos para 160 intentos:

if (isMainThread) {
  const cells = new Int32Array(new SharedArrayBuffer(12));
  cells[STOCK] = 100;
  const workers = [1, 2, 3, 4].map(
    () => new Worker(new URL(import.meta.url), { workerData: cells }),
  );
  await Promise.all(workers.map((worker) => once(worker, "exit")));
  console.log(`Vendidos: ${cells[SOLD]}`);
  console.log(`Rechazados: ${cells[REFUSED]}`);
  console.log(`Existencias: ${cells[STOCK]}`);
} else {
  for (let i = 0; i < 40; i++) {
    if (tryBuy(workerData)) Atomics.add(workerData, SOLD, 1);
    else Atomics.add(workerData, REFUSED, 1);
  }
}

Vendidos: 100
Rechazados: 60
Existencias: 0

Cuántas veces dio vueltas el bucle es distinto en cada ejecución, por eso el programa no lo imprime. Los totales son siempre los mismos: 100 vendidos, 60 rechazados, 0 en existencias.

Pruébalo

Predice la salida

Aquí los dos «hilos» están escritos uno tras otro en un solo hilo, para que el orden sea el mismo que en la escena en cada ejecución. ¿Qué imprime?

const stock = new Int32Array(new SharedArrayBuffer(4));
stock[0] = 3;
let seenByA = Atomics.load(stock, 0);
const seenByB = Atomics.load(stock, 0);
const b = Atomics.compareExchange(stock, 0, seenByB, seenByB - 1) === seenByB;
console.log(`B: ${b}`);
let a = Atomics.compareExchange(stock, 0, seenByA, seenByA - 1) === seenByA;
console.log(`A: ${a}`);
seenByA = Atomics.load(stock, 0);
a = Atomics.compareExchange(stock, 0, seenByA, seenByA - 1) === seenByA;
console.log(`A otra vez: ${a}`);
console.log(`Existencias: ${Atomics.load(stock, 0)}`);

Respuesta

B: true
A: true
A otra vez: true
Existencias: 0

B: true
A: false
A otra vez: true
Existencias: 1

B: true
A: true
A otra vez: false
Existencias: 1

Pruébalo

Completa

¿Con qué compara el CAS al comprar?

const was = Atomics.compareExchange(
  cells, STOCK, , left - 1);

Pruébalo

Encuentra el error

Un colega ha simplificado la compra. Cada línea por sí sola es segura, y aun así en la venta se venden 103 auriculares de 100. ¿En qué línea está el error?

Elige la línea con el error.

Problema

La lista de precios que cambia a la mitad

A las 10:00 el administrador empieza la promoción: auriculares de 60 a 48 €, funda de 15 a 12 €, cable de 5 a 4 €. Al mismo tiempo las cajas calculan carritos. Si los precios están en un diccionario compartido y cambian uno por uno, una caja puede leer el precio nuevo de los auriculares y el viejo de la funda:

// el administrador
prices.headphones = 48;
await saveToLog(); // una pausa entre dos cambios
prices.case = 12;
prices.cable = 4;

// el cobro, durante la pausa
const total = cart.reduce((sum, item) => sum + prices[item], 0);

El carrito sale en 68 €: un total que no fue correcto en ningún momento. Ni con los precios viejos (80 €), ni con los nuevos (64 €). En JavaScript hay un solo hilo, pero un await en medio del cambio deja que otro código lea el objeto a medio cambiar.

La idea

No lo cambies, reemplázalo entero

La lista de precios se lee muchas veces y se cambia pocas. Entonces no la cambies nunca. Hazla un objeto inmutable: una vez creada, se queda igual. Para la promoción el administrador hace una lista de precios nueva y cambia una referencia: «la lista de precios actual es esta».

Un objeto que nadie cambia puede ser leído por tantos hilos como quieras, sin ninguna protección.
Lo único compartido es la referencia, y cambiarla es un paso atómico.
La caja toma la referencia una vez, al empezar el carrito, y calcula todo el carrito con ella. Ve la lista de precios vieja entera o la nueva entera, nunca una mezcla.

Entre Workers no se comparten objetos en absoluto. postMessage envía una copia, así que «publicar» una lista de precios nueva es un mensaje a cada caja. En un solo hilo, Object.freeze protege contra cambiarla por error. Intentar cambiar un objeto congelado en un módulo lanza un TypeError.

function priceList(version, prices) {
  return Object.freeze({ version, prices: Object.freeze({ ...prices }) });
}

function total(list, cart) {
  return cart.reduce((sum, item) => sum + list.prices[item], 0);
}

import { Worker, isMainThread, parentPort } from "node:worker_threads";
import { once } from "node:events";

const cart = ["headphones", "case", "cable"];

if (isMainThread) {
  const regular = { headphones: 60, case: 15, cable: 5 };
  const promo = { headphones: 48, case: 12, cable: 4 };
  const checkout = new Worker(new URL(import.meta.url));
  for (let v = 1; v <= 3; v++) {
    checkout.postMessage(priceList(v, v % 2 === 0 ? promo : regular));
    const [line] = await once(checkout, "message");
    console.log(line);
  }
  checkout.postMessage(null);
  await once(checkout, "exit");
  const last = priceList(3, regular);
  try {
    last.prices.headphones = 1;
  } catch (error) {
    console.log(`Congelado: ${error.constructor.name}`);
  }
} else {
  parentPort.on("message", (list) => {
    if (list === null) return parentPort.close();
    parentPort.postMessage(`Versión ${list.version}: ${total(list, cart)} €`);
  });
}

Versión 1: 80 €
Versión 2: 64 €
Versión 3: 80 €
Congelado: TypeError

Cada caja recibe su propia copia y calcula con ella. Nadie más puede cambiar esa copia, así que no puede haber totales mezclados.

Más precisamente, para curiosos

Así funcionan también las colecciones «copy on write»: CopyOnWriteArrayList en Java, ImmutableList en C#. Cada cambio hace una copia nueva, y leer no necesita cerrojo. Compensa cuando hay muchas lecturas y pocas escrituras. Si las escrituras son frecuentes, copiar sale caro.

La inmutabilidad es honesta solo si llega hasta el fondo. Un objeto con un campo final que apunta a una lista modificable no es inmutable: la lista se puede cambiar desde fuera. Por eso Object.freeze está también sobre el objeto anidado prices: freeze solo llega a un nivel.

Cómo es en los otros lenguajes: record y Map.copyOf con AtomicReference en Java; record con ImmutableDictionary y Volatile o Interlocked.Exchange en C#; una dataclass frozen, una tuple o MappingProxyType y asignación en Python; Object.freeze y mensajes entre Workers en JavaScript.

La idea

Cuando lo atómico no basta

Una reserva mueve un artículo de las existencias a la cuenta de reservados. La regla es que los dos juntos suman siempre 10 000. Dos variables atómicas no la mantienen:

function reserve(cells) {
  Atomics.sub(cells, STOCK, 1);    // cada línea es atómica,
  Atomics.add(cells, RESERVED, 1); // las dos juntas no
}

Entre las dos líneas el auditor ve 9999 en total. Lo atómico protege un valor. Cuando la regla trata de varios valores juntos, necesitas un cerrojo alrededor de todos los cambios y de la comprobación:

// cells: [cerrojo, existencias, reservados] en un SharedArrayBuffer
const LOCK = 0, STOCK = 1, RESERVED = 2;

function lock(cells) {
  while (Atomics.compareExchange(cells, LOCK, 0, 1) !== 0) {
    Atomics.wait(cells, LOCK, 1);
  }
}

function unlock(cells) {
  Atomics.store(cells, LOCK, 0);
  Atomics.notify(cells, LOCK, 1);
}

function reserve(cells) {
  lock(cells); // las dos o ninguna
  try {
    if (cells[STOCK] === 0) return false;
    cells[STOCK]--;
    cells[RESERVED]++;
    return true;
  } finally {
    unlock(cells);
  }
}

function audit(cells) {
  lock(cells);
  try {
    return cells[STOCK] + cells[RESERVED];
  } finally {
    unlock(cells);
  }
}

if (isMainThread) {
  const cells = new Int32Array(new SharedArrayBuffer(12));
  cells[STOCK] = 10_000;
  const roles = ["reserver", "reserver", "auditor"];
  const workers = roles.map(
    (role) => new Worker(new URL(import.meta.url), { workerData: { cells, role } }),
  );
  const report = once(workers[2], "message");
  await Promise.all(workers.map((worker) => once(worker, "exit")));
  const [broken] = await report;
  console.log(`Existencias: ${cells[STOCK]}, reservados: ${cells[RESERVED]}`);
  console.log(`Comprobaciones rotas: ${broken}`);
} else if (workerData.role === "reserver") {
  while (reserve(workerData.cells)) {}
} else {
  let broken = 0;
  for (let i = 0; i < 50_000; i++) {
    if (audit(workerData.cells) !== 10_000) broken++;
  }
  parentPort.postMessage(broken);
}

Existencias: 0, reservados: 10000
Comprobaciones rotas: 0

JavaScript no tiene cerrojos, así que aquí uno está escrito con Atomics: compareExchange toma el cerrojo (0 → 1), y Atomics.wait duerme mientras está tomado. Eso es lo que hace lock en los otros lenguajes.

Más precisamente, para curiosos

Otra manera sin cerrojo: los dos valores en un objeto inmutable (existencias, reservados), y el cambio con un CAS sobre la referencia. Un objeto nuevo con los dos valores nuevos reemplaza al viejo de golpe. Eso combina las dos ideas de esta lección, pero el cerrojo suele ser más claro.

Qué usar cuándo:

un valor, un contador o una bandera: una operación atómica;
comprobar y cambiar un valor: un bucle CAS;
datos que se leen mucho y se cambian poco: un objeto inmutable y un cambio de referencia;
varios valores relacionados: un cerrojo.

Ejercicio

Un vale con usos limitados

Resuelve la tarea en tu editor.

El vale «SPRING20» se puede usar 50 veces. Ocho hilos, cada uno con 10 clientes, intentan usarlo al mismo tiempo. Escribe tryUse(cells) de modo que el vale nunca se use más de 50 veces. Sin cerrojo: con un bucle de compare-and-set. Imprime cuántas veces se usó, cuántos rechazos hubo y cuántos usos quedan:

Usados: 50
Rechazados: 30
Quedan: 0

Más tareas

El máximo. Guarda el pedido más grande del día mientras muchos hilos añaden pedidos. Pista: un bucle CAS que escribe solo si el nuevo es mayor.
Dos promociones. Dale una versión a la lista de precios y haz que dos administradores publiquen al mismo tiempo. ¿Cómo evitas que se pierda la promoción de uno? (Pista: cambia la referencia con CAS solo si la versión sigue siendo la que leíste.)
El auditor sin cerrojo. Pon las existencias y la cuenta de reservados en un objeto inmutable y cámbialo con CAS. Comprueba que el auditor sigue viendo siempre 10 000.

Test

Ponte a prueba

1. Las existencias son 6. Un hilo llama a CAS «si es 5, ponlo en 4». ¿Qué pasa?El hilo duerme hasta que el valor sea 5Se escribe 4No se escribe nada y la respuesta es «falló»: el hilo tiene que leer otra vez

2. tryBuy tiene «si las existencias son > 0» y luego «disminuir en 1». Las dos líneas son atómicas. ¿Por qué aun así vende más de lo que hay?No puede: si cada línea es atómica, todo el método es seguroPorque las operaciones atómicas a veces pierden incrementosEntre la comprobación y la disminución otro hilo puede llevarse el último artículo: cada paso es indivisible, pero los dos juntos no

3. Las cajas leen la lista de precios miles de veces por segundo, y cambia una vez al día. ¿Cuál es la mejor manera de compartirla?Un objeto inmutable: el administrador hace una lista de precios nueva y cambia una referencia; cada caja lee la lista vieja entera o la nueva enteraUn cerrojo alrededor de cada lectura de un precioUn diccionario compartido en el que el administrador cambia los precios uno por uno

4. Reservas un artículo: las existencias bajan 1 y la cuenta de reservados sube 1. El auditor comprueba que la suma sea siempre 10 000. ¿Qué necesitas?Nada: la suma se calcula al finalUn cerrojo alrededor de los dos cambios y de la comprobaciónDos variables atómicas

Operaciones atómicas y objetos inmutables

Cookies