Part 059 — Lock-Free and Wait-Free Thinking for Browser Workers

Part 057 memberi primitive: SharedArrayBuffer dan Atomics. Part 058 memberi syarat deployment: cross-origin isolation. Sekarang kita bahas cara berpikirnya: kapan shared memory pantas dipakai, apa arti lock-free, dan bagaimana tidak menipu diri sendiri dengan concurrency yang kelihatannya cepat tetapi rapuh.

Di browser, default concurrency model yang sehat adalah message passing:

main thread  --postMessage-->  worker
main thread  <--postMessage--  worker

Shared memory mengubah model menjadi:

main thread  --reads/writes same memory-->  worker

Itu lebih cepat untuk beberapa workload karena tidak perlu clone/copy payload. Tetapi ia juga membawa kelas bug yang biasanya tidak muncul di JavaScript UI biasa:

• data race,
• lost update,
• stale read,
• livelock,
• starvation,
• spin loop yang membakar CPU,
• memory layout corruption,
• subtle off-by-one pada ring buffer,
• dead worker yang meninggalkan state setengah jadi,
• bug yang sulit direproduksi karena bergantung timing.

Jadi aturan pertama:

Jangan memakai shared memory karena terlihat advanced. Pakai karena bottleneck data movement atau latency memang sudah terbukti dan message passing sudah tidak cukup.

1. The Real Goal

Tujuan lock-free/wait-free thinking di browser bukan supaya semua code menjadi “lock-free”. Tujuannya adalah memilih coordination strategy yang memiliki progress guarantee jelas.

Pertanyaan yang benar:

Ketika dua atau lebih execution context berebut resource,
apakah sistem tetap bergerak maju?
Kalau iya, siapa yang dijamin maju?
Dalam batas waktu apa?
Dengan biaya CPU/memory berapa?

Contoh resource:

• slot ring buffer,
• sequence number,
• job descriptor,
• shared byte buffer,
• queue head/tail,
• cancel flag,
• ready flag,
• telemetry counter,
• worker lifecycle generation.

Kalau tidak ada jawaban, implementasi Anda hanya “race condition with confidence”.

2. Vocabulary: Blocking, Non-Blocking, Lock-Free, Wait-Free

Istilah ini sering dipakai sembarangan. Kita buat definisi operasional yang cukup untuk engineering browser.

Perhatikan bedanya:

lock-free  = someone makes progress
wait-free  = everyone makes progress within bound

Di browser, banyak desain yang cukup baik adalah single-producer/single-consumer bounded queue. Kita tidak harus langsung membuat MPMC wait-free queue.

3. Browser Reality: Main Thread Cannot Block Like a Worker

Atomics.wait() membuat agent tidur sampai dibangunkan oleh Atomics.notify() atau timeout. Tetapi dalam browser, blocking main thread adalah ide buruk karena main thread mengurus input, rendering, layout, dan event dispatch.

Mental model:

Worker boleh menunggu secara blocking dalam beberapa kasus.
Main thread sebaiknya tidak pernah block.
Main thread harus poll ringan, schedule, atau memakai waitAsync/fallback message.

Pattern aman:

• worker boleh memakai Atomics.wait() untuk menunggu data,
• main thread memakai non-blocking check + requestAnimationFrame, setTimeout, atau Atomics.waitAsync() bila tersedia dan cocok,
• control-plane tetap via postMessage,
• data-plane via SharedArrayBuffer.

MDN menjelaskan Atomics.wait() memeriksa nilai pada shared memory lalu sleep sampai wake-up/timeout; operasi ini hanya bekerja dengan Int32Array atau BigInt64Array view. Atomics.waitAsync() adalah alternatif async yang segera mengembalikan object dengan value string atau Promise.

4. Locks Are Not Evil; Unbounded Blocking Is

Di browser orchestration, lock kadang justru primitive paling sederhana dan paling benar. Contohnya:

• Web Locks untuk leader election,
• IndexedDB transaction untuk atomic state update,
• mutex kecil di worker-local runtime,
• queue ownership lock.

Yang berbahaya bukan “lock”. Yang berbahaya:

• lock tanpa timeout,
• lock tanpa owner identity,
• lock tanpa fencing token,
• lock tanpa cancellation,
• lock yang dipegang selama network call panjang,
• lock yang block UI thread,
• lock yang tidak punya recovery ketika owner crash.

Lock-free juga bukan otomatis lebih aman. Lock-free code bisa lebih sulit diuji dan lebih mudah salah.

Prinsip:

Prefer simple locking when contention is low and failure recovery is clear.
Prefer lock-free data plane only when the hot path really needs it.

5. Control Plane vs Data Plane

Ini invariant terbesar dari desain shared memory browser.

Jangan taruh semua hal di shared memory. Shared memory bagus untuk data yang layout-nya stabil dan sering bergerak. Ia buruk untuk object graph dinamis.

Bad design:

All events, commands, responses, errors, and payloads encoded manually in one SAB.

Better design:

postMessage: INIT { protocolVersion, sab, layout, capabilities }
SAB:        ring buffer frames
postMessage: RESET / ERROR / METRICS / SHUTDOWN

6. Memory Layout Is an API

Begitu Anda memakai SharedArrayBuffer, memory layout menjadi public contract antar agents.

Contoh layout sederhana:

SharedArrayBuffer

[ header Int32 area ]
  0: state
  1: capacity
  2: head
  3: tail
  4: generation
  5: cancelFlag
  6: droppedCount
  7: errorCode

[ payload byte area ]
  fixed-size slots or variable-size frames

Layout harus versioned.

type SharedLayoutV1 = {
  magic: 0x574f524b; // WORK
  version: 1;
  headerBytes: 64;
  capacity: number;
  slotBytes: number;
};

Tanpa magic/version/header size, rolling deployment bisa membuat main thread versi baru membaca buffer yang ditulis worker versi lama dengan asumsi offset berbeda.

7. Atomic Operations Are Coordination Points

Operasi non-atomic biasa pada SharedArrayBuffer dapat terlihat berbeda antar agents. Gunakan Atomics untuk field koordinasi.

Biasanya:

• payload bytes ditulis dengan typed array biasa,
• metadata coordination ditulis dengan Atomics.store,
• ownership/state dibaca dengan Atomics.load,
• claim slot memakai Atomics.compareExchange,
• worker tidur dengan Atomics.wait,
• producer membangunkan consumer dengan Atomics.notify.

Contoh flag:

const STATE_EMPTY = 0;
const STATE_WRITING = 1;
const STATE_READY = 2;
const STATE_READING = 3;

function publishSlot(header: Int32Array, slotStateIndex: number) {
  Atomics.store(header, slotStateIndex, STATE_READY);
  Atomics.notify(header, slotStateIndex, 1);
}

Ingat: Atomics.notify() hanya membangunkan agents yang menunggu pada address tersebut. Ia bukan broadcast event high-level.

8. The CAS Loop Mental Model

Atomics.compareExchange() adalah primitive utama untuk banyak algorithm lock-free.

Artinya:

Jika memory[index] masih expected,
ganti menjadi replacement secara atomic.
Kalau tidak, jangan ubah apa-apa.
Return nilai lama.

Pattern:

function tryClaimSlot(header: Int32Array, index: number): boolean {
  const prev = Atomics.compareExchange(header, index, STATE_EMPTY, STATE_WRITING);
  return prev === STATE_EMPTY;
}

CAS loop:

function incrementAtomic(view: Int32Array, index: number): number {
  while (true) {
    const current = Atomics.load(view, index);
    const next = current + 1;
    const previous = Atomics.compareExchange(view, index, current, next);
    if (previous === current) return next;
  }
}

Tetapi jangan asal membuat infinite CAS loop di main thread. Under contention, loop ini bisa membakar frame budget.

Browser rule:

On main thread: bounded attempts + yield.
On worker: CAS loop acceptable only with backoff/deadline.

9. ABA Problem

ABA terjadi ketika sebuah value berubah dari A ke B lalu kembali ke A. CAS melihat “masih A”, padahal dunia sudah berubah.

Contoh:

Consumer reads head = 7
Other actor consumes slot 7, advances, wraps, reuses slot 7
Consumer CAS sees head = 7 again
Consumer thinks nothing changed

Solusi umum:

• sequence number per slot,
• generation counter,
• monotonically increasing ticket,
• jangan memakai boolean ownership untuk resource yang bisa reuse.

Slot state yang buruk:

slotState = EMPTY | FULL

Slot state yang lebih kuat:

slot.sequence = monotonically increasing integer
slot.state    = EMPTY | WRITING | READY | READING

Untuk bounded ring buffer, sequence number adalah fencing token lokal.

10. Spin, Sleep, Backoff, Yield

Concurrency bug sering bukan correctness saja, tetapi resource usage.

Empat mode menunggu:

Anti-pattern:

while (Atomics.load(header, READY) === 0) {
  // busy wait on main thread: terrible
}

Better worker-side:

while (true) {
  const ready = Atomics.load(header, READY);
  if (ready === 1) break;
  Atomics.wait(header, READY, 0, 100);
}

Better main-thread side:

async function waitReadyNonBlocking(header: Int32Array) {
  while (Atomics.load(header, READY) === 0) {
    await new Promise((r) => setTimeout(r, 4));
  }
}

If available and appropriate:

async function waitReadyAsync(header: Int32Array) {
  while (Atomics.load(header, READY) === 0) {
    const result = Atomics.waitAsync(header, READY, 0, 100);
    const value = typeof result.value === "string" ? result.value : await result.value;
    if (value === "ok" || value === "not-equal") return;
  }
}

11. Boundedness Is the Difference Between Engineering and Hope

A shared-memory queue must have explicit bounds:

• capacity in slots,
• max frame bytes,
• max pending frames,
• max spin attempts,
• max wait timeout,
• max dropped frames,
• max replay after reset,
• max time before declaring peer dead.

Unbounded design:

If queue is full, keep trying forever.

Production design:

If queue is full:
  1. drop low-priority frame, or
  2. return backpressure to caller, or
  3. switch to slower postMessage path, or
  4. terminate/recreate channel if peer is dead.

12. Progress Guarantees by Pattern

Most browser apps that need SAB should start with SPSC, not MPMC.

13. SPSC Before MPSC Before MPMC

Single-producer/single-consumer is much easier because ownership of indexes is clean:

producer owns tail writes
consumer owns head writes
both read the other index

For SPSC:

• producer writes payload,
• producer publishes tail/state atomically,
• consumer reads state,
• consumer reads payload,
• consumer advances head atomically.

For MPSC/MPMC:

• many actors compete on head/tail,
• CAS contention increases,
• ABA risk grows,
• fairness becomes harder,
• debugging gets painful.

Browser guidance:

Use one SAB ring per producer/consumer pair.
Aggregate via worker hub if needed.
Avoid premature global shared queue.

14. Lifecycle Reset Must Be First-Class

Shared memory has a nasty failure mode: one side dies while the other side keeps reading the same memory.

Always include:

• generation id,
• state flag,
• cancel flag,
• owner id,
• heartbeat timestamp/counter,
• reset protocol,
• magic/version validation.

Example:

const OFF_STATE = 0;
const OFF_GENERATION = 1;
const OFF_HEARTBEAT = 2;
const OFF_CANCEL = 3;

const CHANNEL_OPEN = 1;
const CHANNEL_CLOSING = 2;
const CHANNEL_CLOSED = 3;
const CHANNEL_RESET = 4;

Reader invariant:

Never consume payload if generation does not match the generation negotiated during INIT.

This prevents stale worker writes from contaminating a new channel.

15. A Practical Lock-Free Design Checklist

Before writing the algorithm, answer these:

1. Who owns each memory field?
2. Which fields require atomic reads/writes?
3. Which field is the publish point?
4. What is the consumer visibility rule?
5. What is the capacity bound?
6. What happens when full?
7. What happens when empty?
8. What happens when peer crashes?
9. What prevents ABA?
10. What prevents stale generation writes?
11. Which side is allowed to block?
12. How do we reset safely?
13. How do we observe dropped frames, wait time, and contention?
14. How do we test wraparound?
15. What is the fallback when SharedArrayBuffer is unavailable?

If these are not written down, do not ship the shared-memory path.

16. Minimal Shared Flag Example

This is not a queue yet. It is the smallest useful pattern: producer writes value, publishes ready flag, notifies consumer.

const OFF_READY = 0;
const OFF_VALUE = 1;

const sab = new SharedArrayBuffer(Int32Array.BYTES_PER_ELEMENT * 2);
const i32 = new Int32Array(sab);

// Producer
function publish(value: number) {
  Atomics.store(i32, OFF_VALUE, value);
  Atomics.store(i32, OFF_READY, 1);
  Atomics.notify(i32, OFF_READY, 1);
}

// Consumer, usually worker-side
function consumeBlocking(): number {
  while (Atomics.load(i32, OFF_READY) === 0) {
    Atomics.wait(i32, OFF_READY, 0, 1000);
  }

  const value = Atomics.load(i32, OFF_VALUE);
  Atomics.store(i32, OFF_READY, 0);
  return value;
}

Important invariant:

Producer stores payload before ready flag.
Consumer reads ready flag before payload.

The ready flag is the publish point.

17. Non-Blocking Main Thread Poll Example

For UI code:

async function consumeFromMainThread(i32: Int32Array): Promise<number> {
  const deadline = performance.now() + 200;

  while (performance.now() < deadline) {
    if (Atomics.load(i32, OFF_READY) === 1) {
      const value = Atomics.load(i32, OFF_VALUE);
      Atomics.store(i32, OFF_READY, 0);
      return value;
    }

    await new Promise((resolve) => setTimeout(resolve, 0));
  }

  throw new Error("Timed out waiting for shared value");
}

This is slower than blocking wait, but preserves UI responsiveness.

18. Failure Matrix

19. Testing Strategy

You cannot test lock-free code only with happy-path unit tests.

Test cases:

• capacity 1,
• capacity 2,
• wraparound after many writes,
• producer faster than consumer,
• consumer faster than producer,
• worker killed mid-frame,
• reset while producer is writing,
• duplicate INIT,
• stale generation frame,
• random cancellation,
• randomized frame sizes,
• max payload boundary,
• queue full policy,
• queue empty wait timeout,
• unsupported SAB fallback.

Add a stress harness:

for (let round = 0; round < 10_000; round++) {
  // random write/read/cancel/reset schedule
  // assert monotonic sequence, no duplicates, no missing committed frames
}

Your invariant is not “no exception”. Your invariant is:

No committed frame is corrupted.
No frame is consumed twice.
No stale generation frame is accepted.
The system recovers after peer death.

20. Production Observability

Expose these metrics:

Keep this data coarse. Do not log payload bytes or security-sensitive state.

21. Decision Rule

Use shared-memory lock-free-ish design when all are true:

• payload is binary/numeric and large/frequent,
• copy/clone cost is measured and significant,
• producer/consumer topology is simple,
• you can bound capacity,
• you can define reset semantics,
• you have fallback path,
• you can test wraparound and crash recovery.

Do not use it when:

• workload is low-frequency command/response,
• object graph is complex,
• protocol changes frequently,
• team cannot maintain low-level concurrency code,
• browser support/isolation headers cannot be guaranteed,
• correctness depends on “probably no race”.

22. Mental Model Summary

Message passing is the default safe path.
Shared memory is an optimization boundary.
Atomics are coordination points, not business protocol.
Memory layout is an API.
Generation token prevents stale peer corruption.
Boundedness prevents resource collapse.
Testing must attack wraparound, reset, and crash.

The best browser concurrency systems are not the ones with the cleverest lock-free algorithm. They are the ones where the hot path is small, bounded, observable, and replaceable.

References

• MDN — SharedArrayBuffer: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/SharedArrayBuffer
• MDN — Atomics.wait(): https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Atomics/wait
• MDN — Atomics.notify(): https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Atomics/notify
• MDN — Atomics.waitAsync(): https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Atomics/waitAsync