Tangani entitas yang bergerak

Pertanyaan

Bagaimana menjaga indeks lokasi tetap cukup segar untuk dipakai, tanpa menulis ulang indeks tiap kali satu driver bergerak satu meter?

Setelah baca ini, kamu bisa menghitung beban pembaruan lokasi, memisahkan lokasi terbaru dari keanggotaan sel, menetapkan TTL berdasarkan kecepatan, dan menjelaskan kenapa pembaruan yang datang terlambat harus ditolak.

Prasyarat dan contoh

Kamu sudah paham sel grid dan pencarian tetangga (M14.02 dan M14.03), antrean dan pesan yang bisa datang ulang atau terlambat (M10), dan koneksi klien yang putus-nyambung (M13).

Ada 50.000 driver online. Tiap driver mengirim lokasi setiap 4 detik. Itu 12.500 tulisan per detik rata-rata, dan sekitar 25.000 saat jam sibuk dengan pengali 2. Kalau tiap tulisan memperbarui indeks (hapus dari sel lama, masukkan ke sel baru), kamu sedang membayar biaya indeks untuk perpindahan yang 99% nggak mengubah sel.

Mekanisme

1. Pisahkan dua hal yang berubah dengan laju berbeda.

• Posisi terbaru driver: berubah tiap 4 detik. Simpan sebagai satu record per driver (driver_id → lat, lon, accuracy_m, recorded_at, seq) di penyimpanan cepat, misalnya hash di memori dengan TTL.
• Keanggotaan sel: berubah hanya saat driver melintas batas sel. Simpan sebagai himpunan per sel (cell_id → {driver_id}).

Pada 8,3 m/s (30 km/jam) dan sel 1,2 km, sebuah garis lurus melewati batas sel kira-kira tiap 145 detik. Itu 0,007 pembaruan indeks per driver per detik, atau sekitar 345 per detik untuk 50.000 driver. Tulisan indeks turun sekitar 36 kali, dari 12.500 ke ~345 per detik.

2. Urutan lebih penting dari kecepatan. Pembaruan bisa datang terbalik: lokasi 12:00:08 tiba sebelum 12:00:04 karena retry atau jaringan. Beri tiap pembaruan seq (atau recorded_at dari klien yang sudah dikoreksi) dan tulis hanya bila lebih baru:

jika update.seq > tersimpan.seq maka tulis
jika tidak maka buang

Tanpa ini, driver "melompat mundur" dan bisa tercatat berada di sel lama, sementara himpunan sel baru masih memuatnya. Hasilnya driver ganda di dua sel.

3. Kedaluwarsa. Driver yang menutup aplikasi, kehilangan sinyal, atau masuk terowongan berhenti mengirim. Tanpa kedaluwarsa dia tetap muncul sebagai kandidat. Beri TTL pada posisi terbaru, misalnya 15 detik (tiga heartbeat terlewat). Saat TTL habis, driver dianggap tidak tersedia dan dihapus dari himpunan sel lewat tugas pembersihan, bukan lewat jalur baca.

Umur posisi punya biaya yang bisa dihitung:

galat posisi ≈ kecepatan × umur
8,3 m/s × 12 detik ≈ 100 m

Posisi berumur 12 detik bisa jadi 100 m dari tempat driver sebenarnya. Kalau fitur kamu memutuskan "driver ini 80 m dari pelanggan", angka itu sudah dalam kisaran galat.

4. Filter kasar dan presisi. Hasil pencarian sel hanyalah kandidat. Filter presisi di jalur baca mengecek:

1. jarak sebenarnya ke posisi terbaru,
2. umur posisi (now - recorded_at < batas),
3. status ketersediaan driver,
4. akurasi pembacaan (accuracy_m terlalu besar berarti buang atau turunkan peringkat).

Keanggotaan sel boleh sedikit usang karena filter presisi memperbaiki akhirnya. Prinsip ini yang membuat indeks bisa murah.

Saat rancangan ini gagal

• Menulis ke indeks tiap ping. 25.000 tulisan indeks per detik membebani penyimpanan untuk perubahan yang hampir seluruhnya sepele.
• Tidak ada kedaluwarsa. Driver hantu: aplikasi sudah ditutup 10 menit lalu tapi masih ditawarkan ke pelanggan, tawaran kedaluwarsa, dan konversi turun.
• Pembaruan keluar urutan. Sel lama dan sel baru sama-sama memuat driver. Filter jarak menyembunyikan bug itu sampai ada dua tawaran untuk satu driver.
• Thundering herd saat reconnect. Jaringan mati 30 detik lalu 50.000 klien menyambung dan mengirim sekaligus. Batasi laju per klien dan beri jitter pada interval kirim ulang.
• Menurunkan frekuensi ping demi hemat. Ping tiap 30 detik menghemat tulisan tapi galat posisi menjadi 250 m pada 8,3 m/s. Hemat itu nyata, galatnya juga.

Contoh tandingan: untuk motor yang diam di pangkalan, ping tiap 4 detik nggak berguna. Kirim lebih jarang saat posisi nggak berubah lebih dari akurasi (misalnya 15 m), dan tetap kirim heartbeat tiap 10 detik supaya TTL nggak habis.

Latihan

200.000 driver online, ping tiap 5 detik, kecepatan rata-rata 20 km/jam, sel panjang 6 (lebar sekitar 1,2 km). TTL posisi 15 detik.

1. Berapa tulisan posisi per detik?
2. Perkirakan berapa pembaruan keanggotaan sel per detik (anggap garis lurus melintasi sel lebar).
3. Berapa galat posisi terburuk saat posisi tepat di batas TTL?

1. 200.000 / 5 = 40.000 tulisan posisi/detik
2. 20 km/jam = 5,56 m/s. Satu lintasan sel lebar 1.200 m butuh 1.200 / 5,56 ≈ 216 detik.
   Laju per driver ≈ 1 / 216 = 0,0046/detik
   200.000 × 0,0046 ≈ 926 pembaruan keanggotaan/detik
3. 5,56 m/s × 15 detik ≈ 83 m

Terkait

• Sebelumnya: M14.03 Pilih grid spasial.
• Lanjut ke M14.05 Cocokkan suplai dan permintaan.
• M13 (real-time) membahas penyambungan ulang dan klien lambat, yang memengaruhi pembaruan ini.
• Lab L14 dan rancangan D17 belum tersedia.

Catatan

• Asumsi: gerak garis lurus dengan kecepatan konstan, jam klien sudah dikoreksi atau memakai seq.
• Yang nggak dibahas: penghematan baterai klien, dead reckoning, dan peta yang dicocokkan ke jalan.
• Angka kecepatan dan interval adalah contoh, bukan data pengukuran.
• Terakhir ditinjau: 26 Oktober 2026.