Cocokkan suplai dan permintaan

Pertanyaan

Bagaimana memisahkan pencarian kandidat dari ranking dan penugasan, dan bagaimana mencegah dua request konkuren menugaskan sumber daya yang sama?

Setelah baca ini, kamu bisa menggambar alur kandidat, ranking, reservasi, dan penugasan, menulis klaim atomik dengan lease, dan menjelaskan apa yang terjadi saat driver menolak atau tidak menjawab.

Prasyarat dan contoh

Kamu sudah bisa menemukan kandidat lewat sel dan menjaga posisi tetap segar (M14.02 sampai M14.04), paham transaksi dan update kondisional (M05), dan antrean serta timeout (M10).

Tiga pelanggan di Blok M memesan dalam rentang 800 ms. Ada dua driver dalam jangkauan. Ketiganya melihat daftar yang sama, dan driver D1 (ETA 2 menit) berada di urutan teratas untuk semua. Kalau masing-masing request membaca "D1 tersedia" lalu menulis "D1 ditugaskan", D1 mendapat tiga penugasan, dan dua pelanggan menunggu driver yang nggak datang.

Mekanisme

1. Pisahkan empat tahap.

1. Kandidat: sel dan filter jarak. Murah, boleh sedikit usang, tidak mengubah status apa pun.
2. Ranking: urutkan berdasarkan ETA, tingkat penerimaan, rating, dan kebijakan bisnis. Ini hanya menghitung dan tidak mengubah status.
3. Reservasi: klaim satu driver untuk satu permintaan dengan batas waktu. Ini titik di mana konkurensi diselesaikan.
4. Penugasan: driver menerima, status menjadi ASSIGNED. Bila menolak atau tidak menjawab, reservasi dilepas dan lanjut ke kandidat berikutnya.

Dua tahap pertama bebas dari efek samping dan bisa diulang, di-cache, dan dijalankan paralel. Semua keputusan konkurensi dipusatkan di tahap 3.

2. Klaim atomik. Jangan baca lalu tulis. Lakukan satu operasi bersyarat:

UPDATE drivers
   SET state = 'RESERVED', request_id = :req, reserved_until = now() + 15 detik
 WHERE id = :driver AND state = 'AVAILABLE'
-- baris terpengaruh = 1 berarti menang, 0 berarti kalah

Di Redis, setara dengan SET driver:D1:lock <request_id> NX PX 15000. Pemenangnya tepat satu, apa pun jumlah request yang datang bersamaan. Yang kalah langsung mencoba kandidat berikutnya tanpa menunggu.

3. Lease, bukan kunci. Reservasi punya reserved_until. Kalau driver tidak menjawab dalam 15 detik, sebuah pekerjaan latar atau pemeriksaan di jalur baca menganggapnya kembali AVAILABLE. Tanpa batas waktu, driver yang kehilangan sinyal selamanya terkunci. Saat driver menerima, jawaban harus menyebut request_id dan diperiksa:

UPDATE drivers SET state = 'ASSIGNED'
 WHERE id = :driver AND state = 'RESERVED' AND request_id = :req

Jawaban terlambat dari tawaran yang sudah kedaluwarsa dan diberikan ke permintaan lain akan gagal di sini, bukan menimpa penugasan baru.

4. Idempotensi. Request pesanan yang diulang (klien retry) harus menghasilkan satu permintaan. Pakai request_id yang dibuat klien dan simpan sebagai kunci unik (M03 dan M05), supaya satu pelanggan tidak memegang dua driver.

5. Kontensi di kandidat teratas. Semua orang menginginkan D1. Bila tiga request bersamaan memilih D1, dua kalah dan mencoba D2, lalu satu kalah lagi. Untuk lalu lintas tinggi, kumpulkan permintaan dalam jendela pendek (misalnya 2 detik) dan selesaikan sebagai satu masalah penugasan, daripada saling berebut satu per satu. Ini kompromi: jendela menambah latensi sampai 2 detik demi penugasan yang lebih baik.

Saat rancangan ini gagal

• Baca lalu tulis. Dua request membaca AVAILABLE, keduanya menulis. Satu driver dengan dua pelanggan, dan hanya terlihat saat salah satu pelanggan marah.
• Reservasi tanpa batas waktu. Driver yang tertutup aplikasinya mengunci diri. Pasokan menyusut tanpa alarm.
• Jawaban terlambat menimpa. Driver menerima setelah 17 detik padahal lease habis di 15 detik dan driver sudah dialokasikan ke orang lain. Tanpa request_id pada kondisi, penugasan ganda.
• Pembatalan tidak melepas. Pelanggan membatalkan pada detik ke 8, tapi driver tetap RESERVED sampai 15 detik. Pembatalan harus melepas lewat kondisi request_id yang sama.
• Hot driver. Semua request mengantre di satu driver top. Throughput klaim satu key terbatas oleh serialisasi satu baris. Sebar lewat pilihan acak di antara beberapa kandidat teratas.

Contoh tandingan: kalau permintaan hanya 3 per menit di satu kota kecil, klaim bersyarat di Postgres sudah cukup. Kamu nggak butuh Redis, jendela batch, atau penjadwal global.

Latihan

Ada 3 permintaan (R1, R2, R3) dan 2 driver (D1 ETA 2 menit, D2 ETA 4 menit) untuk semuanya. Ketiganya tiba bersamaan dan memilih D1 lebih dulu.

1. Apa hasilnya dengan pola baca-lalu-tulis?
2. Apa hasilnya dengan klaim atomik, dan apa yang terjadi pada R3?
3. D1 tidak menjawab dalam 15 detik. Apa yang harus terjadi pada R1?

Lihat pembahasan+

1. Ketiganya membaca D1 AVAILABLE dan menulis ASSIGNED. D1 mendapat tiga penugasan, dan hasil akhir tergantung penulisan terakhir yang menang. Dua pelanggan mendapat janji palsu, D2 menganggur.
2. Misalkan R1 menang atas D1 (baris terpengaruh = 1). R2 dan R3 mendapat 0, lalu keduanya mencoba D2. R2 menang atas D2, R3 kalah lagi. R3 tidak punya kandidat, jadi sistem memperluas radius atau menaruhnya di antrean tunggu dengan batas waktu, bukan menugaskan driver yang sudah terpakai.
3. Pada detik ke 15, reserved_until lewat dan D1 kembali AVAILABLE. R1 mencoba kandidat berikutnya (D2 bila bebas, atau R3 yang menunggu bisa mengambil D1). Jawaban D1 yang datang di detik ke 17 gagal di WHERE request_id = :req AND state = 'RESERVED' bila D1 sudah dialokasikan ke yang lain.

Jawaban yang bagus menyebut bahwa klaim atomik menjamin tidak ada penugasan ganda, bukan bahwa semua orang mendapat driver. Itu masalah pasokan, bukan masalah kebenaran.

Terkait

• Sebelumnya: M14.04 Tangani entitas yang bergerak.
• Lanjut ke M14.06 Tentukan geofence dengan aman.
• M05 (transaksi dan konkurensi) dan M10 (antrean dan timeout) adalah dasar klaim dan lease ini.
• Lab L14 dan rancangan D17 belum tersedia.

Catatan

• Asumsi: satu penyimpanan yang mendukung update bersyarat atomik per driver. Lintas-region atau multi-penyimpanan butuh jaminan tambahan.
• Yang nggak dibahas: algoritma penugasan optimal (Hungarian), harga dinamis, dan penegakan kebijakan pembatalan.
• Penggunaan SET NX PX sebagai kunci tunggal aman untuk satu node Redis, tidak otomatis untuk failover.
• Terakhir ditinjau: 26 Oktober 2026.