Median real-time di worker queue bukan sekadar implementasi dua heap seperti di soal interview. Di sistem produksi, median harus tetap benar ketika event datang terlambat, job di-retry, worker crash di tengah update, cache kedaluwarsa, dan beberapa worker memproses stream yang sama secara paralel.

Jika kebutuhan Anda adalah median yang selalu tersedia untuk dibaca cepat, pendekatan yang dipilih biasanya jatuh ke salah satu dari tiga model: exact incremental dengan dua heap, batched recomputation, atau pendekatan hibrida. Pilihan terbaik ditentukan oleh tiga hal: akurasi yang dibutuhkan, throughput event, dan kompleksitas operasional yang sanggup Anda tanggung.

Artikel ini memakai ide klasik computing the median sebagai pintu masuk ke masalah backend yang lebih nyata: bagaimana menyimpan dan memperbarui median dari event yang diproses lewat queue dengan tetap menjaga konsistensi state.

Masalah yang sebenarnya: median bukan hanya algoritma, tetapi state terdistribusi

Secara algoritmik, median dari stream angka bisa dijaga dengan dua heap:

  • Max-heap untuk separuh nilai bawah
  • Min-heap untuk separuh nilai atas

Aturannya sederhana:

  • Ukuran kedua heap berbeda paling banyak satu
  • Semua elemen di max-heap harus lebih kecil atau sama dengan elemen di min-heap
  • Median diambil dari puncak heap, atau rata-rata dua puncak untuk jumlah data genap

Di memory lokal satu proses, ini elegan dan efisien. Namun pada worker queue, Anda hampir selalu menghadapi pertanyaan tambahan:

  • Apakah ada satu stream global atau banyak stream terpisah per tenant, user, campaign, atau product?
  • Apakah event bisa datang out of order?
  • Apakah queue menjamin at least once delivery, sehingga duplicate job mungkin terjadi?
  • Apakah median harus exact untuk setiap event, atau cukup akurat dalam jendela waktu tertentu?
  • Di mana state heap disimpan: memory worker, Redis, atau database?
  • Bagaimana jika worker mati setelah menulis ke heap tapi sebelum menandai job selesai?

Begitu median menjadi shared mutable state, fokus utamanya bergeser dari kompleksitas O(log n) ke atomicity, idempotensi, ordering, dan recovery.

Kapan dua heap tepat dipakai

Cocok untuk stream yang butuh hasil exact dan latensi rendah

Pendekatan dua heap masuk akal bila:

  • Anda butuh median exact, bukan perkiraan
  • Setiap event harus segera tercermin di hasil baca
  • Jumlah stream tidak terlalu besar, atau setiap stream masih bisa dikelola sebagai state terpisah
  • Anda bisa menerima biaya sinkronisasi state

Contoh yang cukup masuk akal:

  • Median waktu proses per satu antrian premium
  • Median nominal transaksi per merchant tertentu dengan volume moderat
  • Median skor atau latency untuk dashboard operasional yang sensitif terhadap outlier

Tidak cocok jika cardinality atau throughput terlalu tinggi

Dua heap menjadi mahal saat:

  • Anda punya jutaan stream aktif, karena tiap stream membutuhkan state sendiri
  • Volume event sangat tinggi sehingga lock contention naik
  • Anda butuh koreksi terhadap event terlambat atau penghapusan event, yang sulit pada struktur dua heap sederhana

Masalah praktisnya bukan hanya kapasitas memory, tetapi juga biaya memelihara state exact yang bisa dimutasi dari banyak worker.

Arsitektur dasar: queue, worker, Redis/cache, dan database

Untuk median real-time, arsitektur yang umum terlihat seperti ini:

  1. Producer mengirim event ke queue
  2. Worker mengambil job
  3. Worker melakukan deduplikasi/idempotency check
  4. Worker mengambil atau mengunci state median untuk stream terkait
  5. Worker memperbarui state di Redis atau penyimpanan cepat lain
  6. Worker menyimpan ringkasan atau snapshot ke database
  7. API read path mengambil median dari cache cepat, lalu fallback ke database jika perlu

Representasi state per stream bisa berupa:

  • Heap bawah
  • Heap atas
  • Jumlah elemen
  • Versi state atau sequence terakhir yang sudah diterapkan
  • Metadata seperti updated_at dan checksum ringan

Redis sering dipilih untuk state aktif karena cepat dan mudah dipakai sebagai cache sekaligus mekanisme lock. Database relasional atau document store lebih cocok untuk durability, audit, dan re-build state.

Catatan: Jangan menyimpan state dua heap hanya di memory worker jika lebih dari satu worker bisa memproses stream yang sama. Hasilnya akan benar hanya secara lokal, tetapi salah secara global.

Implementasi exact incremental dengan dua heap

Aturan update state

Saat event baru datang dengan nilai x:

  1. Masukkan x ke heap bawah jika lebih kecil atau sama dengan puncak heap bawah, selain itu ke heap atas
  2. Lakukan rebalance sampai selisih ukuran maksimal satu
  3. Simpan state baru secara atomik

Secara logika, pseudocode-nya seperti ini:

function applyValue(state, x) {
  if (state.lower.isEmpty() || x <= state.lower.peek()) {
    state.lower.push(x)   // max-heap
  } else {
    state.upper.push(x)   // min-heap
  }

  if (state.lower.size() > state.upper.size() + 1) {
    state.upper.push(state.lower.pop())
  } else if (state.upper.size() > state.lower.size()) {
    state.lower.push(state.upper.pop())
  }

  state.count += 1
  return state
}

function median(state) {
  if (state.count === 0) return null
  if (state.lower.size() === state.upper.size()) {
    return (state.lower.peek() + state.upper.peek()) / 2
  }
  return state.lower.peek()
}

Masalahnya, di sistem nyata, fungsi applyValue tidak boleh berdiri sendiri. Ia harus dibungkus oleh mekanisme konsistensi.

Kenapa update harus atomik

Bayangkan dua worker memproses stream yang sama pada saat bersamaan:

  • Worker A membaca state lama
  • Worker B membaca state lama yang sama
  • A menambah nilai 10 dan menyimpan
  • B menambah nilai 100 dan menyimpan

Jika tidak ada lock atau kontrol versi, salah satu update akan hilang. Median menjadi salah walaupun algoritma heap Anda benar.

Pola lock yang paling sederhana

Untuk satu stream, satu update state sebaiknya dieksekusi secara serial. Biasanya ada dua pendekatan:

  • Distributed lock per stream key, misalnya median:lock:{stream_id}
  • Optimistic concurrency dengan version check, lalu retry jika konflik

Lock lebih mudah dipahami, tetapi dapat menurunkan throughput bila banyak event menumpuk pada stream yang sama. Optimistic concurrency lebih efisien pada konflik rendah, tetapi implementasinya lebih rumit karena perlu loop baca-modifikasi-tulis dengan deteksi konflik.

Contoh alur dengan lock:

job(event):
  key = "median:state:" + event.stream_id
  lockKey = "median:lock:" + event.stream_id
  dedupeKey = "median:event:" + event.event_id

  if redis.exists(dedupeKey):
    ack job
    return

  acquire lock(lockKey, ttl=short)
  try:
    state = redis.get(key) or emptyState()
    state = applyValue(state, event.value)
    redis.set(key, state)
    redis.set(dedupeKey, 1, ttl=long_enough)
    persistSnapshotAsync(event.stream_id, state.summary)
    ack job
  finally:
    release lock(lockKey)

Contoh ini sengaja generik. Detail atomiknya tergantung tool yang dipakai. Intinya, dedupe, update state, dan penandaan progress harus dipikirkan sebagai satu rangkaian konsistensi.

Out-of-order event, retry, dan duplicate job

Out-of-order tidak selalu merusak median, tetapi bisa merusak aturan bisnis

Jika median dihitung atas seluruh himpunan nilai tanpa memedulikan urutan waktu, maka event yang datang terlambat sebenarnya tidak masalah secara matematis. Median dari kumpulan nilai yang sama tetap sama walaupun urutan masuk berbeda.

Tetapi banyak sistem tidak sesederhana itu. Misalnya:

  • Median dihitung per jendela waktu 5 menit
  • Median hanya untuk event dengan status tertentu
  • Median harus mencerminkan urutan sequence bisnis tertentu

Dalam kasus seperti ini, event terlambat bisa masuk ke bucket yang salah atau memaksa koreksi state lama. Dua heap incremental menjadi kurang nyaman, karena ia bagus untuk append-only exact update, bukan untuk mutasi historis.

Retry dan duplicate job adalah default, bukan edge case

Pada banyak queue, pengiriman bersifat at least once. Artinya job yang sama bisa dieksekusi lebih dari sekali. Penyebabnya antara lain:

  • Worker berhasil memproses tapi gagal mengirim ACK
  • Worker timeout padahal update state sudah sempat ditulis
  • Queue melakukan redelivery setelah crash

Jika job tidak idempoten, median akan bergeser setiap kali retry terjadi.

Idempotensi yang praktis

Paling tidak, setiap event perlu identifier unik yang stabil, misalnya event_id. Worker menyimpan bukti bahwa event tersebut sudah diterapkan. Strateginya bisa:

  • Menyimpan event_id di Redis dengan TTL yang cukup panjang
  • Menyimpan progress per stream berdasarkan sequence number terakhir, jika urutan terjamin
  • Menyimpan ledger di database untuk audit dan reprocessing

Trade-off-nya:

  • Dedupe by event_id lebih aman untuk out-of-order, tetapi butuh storage lebih banyak
  • Dedupe by last_sequence lebih hemat, tetapi hanya valid jika sequence monoton dan tidak lompat secara ambigu

Kesalahan umum adalah memberi TTL dedupe terlalu pendek. Sistem terlihat benar pada traffic normal, lalu saat ada backlog dan retry terlambat, event lama diproses ulang karena jejak dedupenya sudah hilang.

Kapan batching lebih masuk akal daripada dua heap

Tidak semua masalah median perlu dijawab dengan update exact per event. Batching sering lebih sehat jika salah satu kondisi berikut terjadi:

  • Event rate sangat tinggi
  • Banyak event datang terlambat
  • Median dibutuhkan per interval, bukan per event
  • Anda perlu koreksi dan re-build state dengan mudah

Model batching yang umum

Alih-alih memperbarui dua heap di setiap job, worker hanya menulis event mentah atau agregasi ringan ke storage tahan lama. Lalu proses periodik menghitung median untuk bucket tertentu, misalnya per menit atau per 5 menit.

Keuntungan batching:

  • Lebih tahan terhadap out-of-order event
  • Lebih mudah direkalkulasi jika ada bug
  • Lock contention jauh berkurang
  • Recovery lebih sederhana karena sumber kebenaran tetap event mentah

Kekurangannya:

  • Median tidak benar-benar real-time per event
  • Read path perlu menerima keterlambatan pembaruan
  • Biaya komputasi batch bisa besar pada bucket besar

Aturan praktis memilih exact vs batch

  • Pilih dua heap exact jika median harus segera tersedia dan jumlah stream aktif masih terkendali
  • Pilih batching jika throughput lebih penting daripada presisi per detik
  • Pilih hibrida jika butuh dashboard cepat namun tetap ingin sumber data yang bisa direbuild

Pola hibrida yang sering berhasil: simpan event mentah ke database atau log, update median sementara di Redis untuk kebutuhan baca cepat, lalu lakukan rekonsiliasi periodik ke snapshot yang lebih tahan lama.

Trade-off akurasi, throughput, dan kompleksitas operasional

Akurasi exact menaikkan biaya koordinasi

Median exact incremental memberi hasil paling presisi, tetapi memerlukan:

  • Koordinasi antar worker
  • State yang konsisten
  • Deduplikasi andal
  • Strategi recovery saat drift

Jika Anda hanya butuh indikator operasional, biaya ini bisa terlalu tinggi dibanding nilainya.

Throughput tinggi sering menuntut kompromi

Semakin banyak event per stream, semakin besar kemungkinan:

  • Lock menjadi bottleneck
  • Queue backlog meningkat
  • TTL lock yang terlalu pendek memicu overlap
  • Retry storm memperparah duplicate update

Di titik tertentu, batching atau partisi stream menjadi keharusan, bukan optimasi opsional.

Kompleksitas operasional sering diremehkan

Dua heap di whiteboard terlihat simpel. Menjalankan state exact di cluster worker jauh lebih mahal secara operasional. Anda harus memikirkan:

  • Rebuild state
  • Migrasi format state
  • Monitoring drift
  • Poison message
  • Redis eviction
  • Race condition saat failover

Kalau tim Anda kecil, desain yang sedikit kurang real-time tetapi mudah dioperasikan sering lebih baik daripada desain exact yang rapuh.

Cache invalidation dan read path

Median biasanya dibaca jauh lebih sering daripada dihitung ulang. Karena itu, hasil median sering disimpan di cache atau Redis. Tetapi cache invalidation di sini bukan sekadar menghapus key saat ada update.

Masalah umum pada cache median

  • State heap sudah berubah, tetapi nilai median turunan belum diperbarui
  • Snapshot database tertinggal dari Redis, lalu API membaca fallback yang stale
  • Cache hilang karena eviction, lalu service membangun ulang dari snapshot yang belum sinkron

Pola yang lebih aman adalah menyimpan state kanonik dan nilai median turunan bersama versi yang sama. Jadi pembaca bisa tahu apakah hasil baca konsisten dengan state terakhir.

Contoh metadata yang berguna:

  • version
  • count
  • median_value
  • last_event_id atau last_applied_sequence
  • updated_at

Jika API menemukan versi median turunan tidak cocok dengan versi state, ia bisa menolak hasil itu, menghitung ulang cepat, atau fallback ke snapshot yang lebih baru.

Distributed lock: perlu, tetapi jangan dianggap obat semua masalah

Kegunaan lock

Distributed lock berguna untuk memastikan hanya satu worker yang memutasi state stream tertentu pada satu waktu. Ini mengurangi race condition yang paling jelas.

Keterbatasan lock

Lock tidak otomatis menyelesaikan semua masalah berikut:

  • Worker memegang lock lalu crash setelah menulis sebagian state
  • TTL lock habis sebelum proses selesai, lalu worker lain masuk
  • Job yang sama diproses ulang setelah lock dilepas
  • State Redis berhasil ditulis, tetapi snapshot database gagal

Artinya, lock harus dipadukan dengan:

  • Idempotensi
  • Write ordering yang jelas
  • Snapshot atau ledger untuk recovery
  • Timeout dan retry policy yang masuk akal

Kesalahan umum adalah menganggap lock cukup, lalu melupakan duplicate processing. Hasilnya, tidak ada race antar worker, tetapi event yang sama tetap masuk dua kali.

Gejala bug yang sering muncul

1. Median sesekali melonjak lalu kembali normal

Biasanya terkait duplicate job yang masuk sekali-sekali, atau event terlambat yang salah bucket. Gejala ini sering muncul sebagai spike yang sulit direproduksi.

2. Count tidak cocok dengan jumlah event unik

Ini sinyal kuat bahwa idempotensi bocor. Jika count di state lebih besar dari jumlah event unik yang tercatat, duplicate apply hampir pasti terjadi.

3. API read kadang melihat median lama

Sering disebabkan read path mengambil snapshot database yang stale, atau cache median turunan tidak diperbarui bersama state utama.

4. Median salah hanya pada stream dengan traffic tinggi

Ini mengarah ke contention, lock expiry, atau optimistic update conflict yang tidak ditangani baik. Stream sepi tampak normal, stream ramai rusak.

5. Drift muncul setelah deploy atau restart Redis

Kemungkinan ada state aktif yang belum dipersist dengan baik, format state berubah tanpa migrasi, atau rebuild fallback tidak setara dengan logika incremental saat ini.

Checklist observabilitas yang wajib ada

Jika Anda serius menjalankan median real-time di worker queue, observabilitas bukan pelengkap.

Metrics

  • Queue lag per stream atau per partition
  • Jumlah retry dan dead-letter
  • Duplicate job rate
  • Lock acquisition latency
  • Lock timeout atau contention rate
  • State update failure rate
  • Median recomputation/reconciliation count
  • Selisih antara count state dan count event unik dari sumber kebenaran

Logs terstruktur

  • event_id
  • stream_id
  • job_id
  • attempt
  • state_version_before dan state_version_after
  • dedupe_hit
  • lock_wait_ms

Tanpa field-field ini, investigasi drift akan sangat lambat.

Tracing

Jika stack Anda mendukung tracing, hubungkan jejak dari producer ke queue, worker, Redis, dan database. Ini membantu menemukan apakah masalah terjadi saat enqueue, saat apply state, atau saat snapshot persistence.

Invariant checks

Tambahkan validasi berkala terhadap invariant dua heap:

  • Selisih ukuran heap maksimal satu
  • Semua elemen heap bawah tidak lebih besar dari heap atas
  • Median turunan sesuai dengan puncak heap

Jika invariant gagal, tandai stream tersebut untuk recovery otomatis sebelum hasil salah menyebar ke pengguna.

Strategi recovery saat state median drift

State drift berarti median atau struktur internalnya tidak lagi merepresentasikan event yang seharusnya. Ini bisa terjadi karena duplicate apply, write setengah jalan, bug deploy, atau event ordering yang salah.

1. Punya sumber kebenaran yang bisa diputar ulang

Recovery paling aman adalah rebuild dari event source, bukan mencoba menebak selisih dari state yang sudah korup. Karena itu, simpan event mentah atau setidaknya log yang cukup untuk replay.

2. Pisahkan rebuild dari jalur produksi

Jangan rebuild state besar langsung pada key yang sedang dibaca traffic produksi. Gunakan pola:

  1. Baca event untuk stream atau bucket tertentu
  2. Bangun state baru di key sementara
  3. Validasi invariant dan count
  4. Swap pointer atau versi secara atomik

Dengan begitu, pembaca tidak melihat state setengah jadi.

3. Rekonsiliasi periodik

Untuk sistem exact incremental, jadwalkan rekonsiliasi berkala:

  • Pilih sampel stream aktif atau stream kritis
  • Hitung ulang median dari source of truth
  • Bandingkan dengan state Redis
  • Tandai dan perbaiki stream yang melenceng

Ini penting karena beberapa bug tidak langsung terlihat di dashboard.

4. Quarantine untuk stream bermasalah

Jika invariant heap gagal atau drift terdeteksi, lebih baik stream tersebut masuk mode degraded:

  • Tahan update incremental sementara
  • Sajikan status stale dengan penanda yang jelas, atau fallback ke snapshot terakhir yang valid
  • Jalankan rebuild asinkron

Lebih baik memberi hasil sedikit terlambat daripada hasil salah yang tampak meyakinkan.

Desain yang sering berhasil di praktik

Jika kebutuhan Anda berada di tengah-tengah—ingin cepat, tetapi tidak ingin operasional terlalu rapuh—desain berikut sering menjadi kompromi sehat:

  1. Semua event masuk ke queue dan juga ditulis ke storage tahan lama
  2. Worker melakukan dedupe berbasis event_id
  3. State median aktif per stream disimpan di Redis
  4. Update state per stream dilindungi lock singkat atau optimistic concurrency
  5. Snapshot ringkas disimpan berkala ke database
  6. Job rekonsiliasi periodik membandingkan state aktif dengan source of truth
  7. API membaca dari Redis, lalu fallback ke snapshot yang tervalidasi

Dengan pola ini, Anda mendapat:

  • Latensi baca rendah
  • State aktif yang cukup real-time
  • Jalur recovery yang jelas saat drift

Kekurangannya tetap ada: lebih banyak komponen, lebih banyak failure mode, dan kebutuhan observabilitas yang lebih tinggi.

Panduan keputusan singkat

  • Gunakan dua heap exact jika median harus akurat per event, jumlah stream terbatas, dan tim siap mengelola lock, dedupe, dan recovery
  • Gunakan batching jika event besar, out-of-order sering terjadi, atau median cukup diperbarui periodik
  • Gunakan hibrida jika Anda butuh hasil cepat untuk read path tetapi tetap ingin kemampuan replay dan rekonsiliasi

Pertanyaan yang paling membantu bukan “bagaimana menghitung median secepat mungkin”, tetapi “apa definisi benar untuk median di sistem saya, dan berapa biaya menjaga definisi itu saat data diproses secara asinkron?”

Begitu pertanyaannya bergeser seperti itu, keputusan soal heap, lock, cache, dan konsistensi biasanya menjadi jauh lebih jelas.