Compare-and-Swap (CAS): атомарные регистры

Идиома из инструкции процессора: «записать новое значение, только если в ячейке лежит ожидаемое старое». Альтернатива блокировкам, основа lock-free алгоритмов и распределённой консистентности.

Что это

CAS — атомарная операция compareExchange(cell, expected, newValue): проверяет что в ячейке expected, и если да — записывает newValue. Возвращает прежнее значение. Если не совпало — ничего не пишется (вызывающий получает текущее, пробует снова или сдаётся).

Идея пришла из CPU-инструкций (CMPXCHG на x86). Экономнее блокировок: транзакции не отменяются на mutex'ах, а просто повторяют попытку, пока чей-то commit не пройдёт.

CAS в Node через Atomics

const sab = new SharedArrayBuffer(4);
const arr = new Int32Array(sab);

// Записать 42, только если там было 0
const old = Atomics.compareExchange(arr, 0, 0, 42);
if (old === 0) {
  // успех: arr[0] стало 42
} else {
  // не получилось: в arr[0] лежит что-то другое, в `old` — реальное значение
}

Lock-free инкремент через CAS:

function casIncrement(arr, i) {
  while (true) {
    const current = Atomics.load(arr, i);
    const prev = Atomics.compareExchange(arr, i, current, current + 1);
    if (prev === current) return current + 1; // выиграли гонку
    // иначе кто-то опередил — пробуем ещё раз
  }
}

CAS-регистр без Atomics (для распределёнки)

Когда «ячейка» — не int32 в RAM, а запись в БД или объект в другом узле, та же идея реализуется как структура:

class CasRegister {
  constructor(initial) { this.value = initial; }
  cas(expected, value) {
    if (this.value === expected) {
      this.value = value;
      return true;
    }
    return false;
  }
}

const r = new CasRegister(100);
r.cas(100, 42); // true  → 42
r.cas(100, 99); // false (там уже 42)
r.cas(42, 77);  // true  → 77

CAS по версии

Для длинных значений сравнивать само значение неэффективно — храним монотонно растущий счётчик версий:

class VersionedRegister {
  constructor(value) { this.value = value; this.version = 0; }
  cas(expectedVersion, newValue) {
    if (this.version !== expectedVersion) return false;
    this.value = newValue;
    this.version++;
    return true;
  }
}
// Так работают etag в HTTP, MVCC в БД, optimistic locking в ORM

CAS по хешу — мост к блокчейну

Идентификация значения через SHA-256. Записать может только тот, кто знает предыдущий хеш:

const crypto = require('node:crypto');

class HashedRecord {
  constructor(initial) {
    this.value = initial;
    this.hash = this._hash(initial);
  }
  _hash(v) {
    return crypto.createHash('sha256').update(JSON.stringify(v)).digest('hex');
  }
  cas(expectedHash, newValue) {
    if (this.hash !== expectedHash) return false;
    this.value = newValue;
    this.hash = this._hash(newValue);
    return true;
  }
}
// Если в record хранить целую JSON-структуру — это уже почти блокчейн:
// каждая запись подписана хешем предыдущего состояния

В браузере хеш считается асинхронно через Web Crypto:

async function sha256(v) {
  const bytes = new TextEncoder.encode(JSON.stringify(v));
  const hash = await crypto.subtle.digest('SHA-256', bytes);
  return Array.from(new Uint8Array(hash))
    .map(b => b.toString(16).padStart(2, '0')).join('');
}

Подводные камни

ABA-проблема: значение прошло цикл A → B → A, CAS думает «не менялось». Решение — версия + значение
Busy-wait в CAS-loop греет CPU; для долгих ожиданий — Atomics.wait или yield
Хеш ради одного числа невыгоден — длинный SHA-256 ради инкремента счётчика. Хеширование оправдано для целых структур
CAS не отменяет необходимость consensus для распределённых систем — между узлами всё равно нужен Paxos/Raft

🎓 Источник: CAS в JavaScript — Compare and Swap

📅 2025-08-08 · YouTube · _S8zcKaj7Fk
Тезисы:
- CAS пришёл из инструкции процессора (CMPXCHG): запись в ячейку памяти, только если там ожидаемое значение
- Альтернатива блокировкам: транзакции не отменяются, а повторяются — экономнее в распределённых системах
- Стратегии консистентности: CRDT или CAS
- В JS: Atomics.compareExchange(arr, i, expected, value) для SharedArrayBuffer
- Atomics.wait с промисами — асинхронное ожидание записи в ячейку другим потоком
- Однопоточный JS линеаризуется в последовательность; мультитрейдинг — НЕ линеаризуешь, нужны атомики
- CAS по версии: храним value + version, инкрементируем version при записи
- CAS по хешу: идентифицируем значение через SHA-256, чтобы записать — знать прежний хеш (близко к блокчейну)
- CompareAndSwapRecord хранит целый JSON, защищается хешем — основа верифицируемых распределённых структур
Цитата:

«Чтобы записать новое значение в этот record, мы должны знать предыдущий хэш. И теперь это уже ближе к блокчейну.»