Masalah: Bottleneck Telemetri Spatio-Temporal pada Engine RTS

Simulasi game Real-Time Strategy (RTS) mengeksekusi kalkulasi state pada interval tetap (tick rate), umumnya 20 hingga 60 tick per detik. Setiap tick merekam snapshot dari ribuan entity aktif: koordinat 2D (X, Y), hit points (HP), status aksi, dan orientasi. Satu sesi pertandingan multiplayer berdurasi 30 menit dengan 8 pemain dapat menghasilkan puluhan juta baris data telemetri.

Kebutuhan query analitik dan sistem replay mencakup dua hal: rekonsiliasi state per tick dan pencarian entity dalam area tertentu (misalnya, mencari seluruh unit dalam radius efek serangan area/AoE). Struktur skema konvensional dengan indeks B-Tree standar mengalami degradasi performa drastis ketika tabel bertambah besar. Query radius spasial pada tick tertentu memicu sequential scan atau high-cost bitmap heap scan yang membebani I/O disk.

Keterbatasan B-Tree pada Query Multidimensi

Indeks B-Tree didesain untuk data skalar satu dimensi yang memiliki urutan linier mutlak (strictly ordered). Ketika menangani koordinat spasial dua dimensi, developer biasanya membuat indeks komposit seperti (tick, pos_x, pos_y).

Misalkan query mencari seluruh unit pada tick = 1200 dalam bounding box tertentu:

SELECT unit_id, pos_x, pos_y
FROM unit_snapshots
WHERE match_id = 'match-xyz'
  AND tick = 1200
  AND pos_x BETWEEN 100 AND 150
  AND pos_y BETWEEN 200 AND 250;

Mekanisme B-Tree pada skenario ini:

  1. B-Tree melakukan traversal index tree secara efisien untuk menemukan tick = 1200.
  2. B-Tree mempersempit pencarian ke batas range pertama: pos_x BETWEEN 100 AND 150.
  3. Untuk kolom ketiga (pos_y), B-Tree tidak dapat melompati index leaf node secara multidimensi. Nilai pos_y terurut per nilai pos_x yang identik, bukan secara keseluruhan. Database terpaksa memindai semua leaf node di sepanjang range pos_x, lalu menerapkan filter skalar terhadap pos_y di memori.

Karakteristik ini membuat B-Tree tidak optimal untuk evaluasi jarak radius Euclidean ataupun bounding box 2D pada volume data masif.

Solusi: Partisi Tabel dan GiST (Generalized Search Tree)

Untuk menembus batas skalabilitas ini, arsitektur database membutuhkan dua komponen: eliminasi partisi data tidak relevan (partition pruning) dan indeks hierarki spasial (R-Tree via GiST).

1. Partisi Tabel Berbasis Match ID atau Range Tick

Query state game RTS selalu terisolasi pada lingkup satu pertandingan. Menyatukan seluruh data snapshot ke dalam satu tabel datar tunggal menyebabkan index bloat. Strategi terbaik adalah mempartisi tabel secara deklaratif menggunakan LIST atau HASH pada match_id, atau RANGE jika match diarsipkan secara temporal.

2. GiST Indexing dengan Ekstensi btree_gist

GiST memungkinkan pengindeksan data spasial berbasis R-Tree di PostgreSQL. R-Tree mengelompokkan koordinat ke dalam Minimum Bounding Rectangles (MBR) bersarang. Pencarian area hanya menelusuri node MBR yang beririsan dengan target area.

Dengan mengaktifkan modul bawaan btree_gist, PostgreSQL dapat menggabungkan tipe data skalar (seperti integer tick) bersama tipe data geometris (seperti point) dalam satu index tree GiST terpadu.

Implementasi Skema DDL

Aktifkan ekstensi yang diperlukan dan buat skema tabel terpartisi:

-- Aktifkan ekstensi untuk mendukung tipe data skalar di dalam GiST
CREATE EXTENSION IF NOT EXISTS btree_gist;

-- Tabel utama terpartisi berdasarkan match_id
CREATE TABLE unit_snapshots (
    match_id UUID NOT NULL,
    tick INT NOT NULL,
    unit_id INT NOT NULL,
    position POINT NOT NULL,
    hp SMALLINT NOT NULL,
    PRIMARY KEY (match_id, tick, unit_id)
) PARTITION BY HASH (match_id);

-- Buat 4 partisi fisik hash (sesuaikan dengan skala sistem)
CREATE TABLE unit_snapshots_p0 PARTITION OF unit_snapshots
    FOR VALUES WITH (MODULUS 4, REMAINDER 0);
CREATE TABLE unit_snapshots_p1 PARTITION OF unit_snapshots
    FOR VALUES WITH (MODULUS 4, REMAINDER 1);
CREATE TABLE unit_snapshots_p2 PARTITION OF unit_snapshots
    FOR VALUES WITH (MODULUS 4, REMAINDER 2);
CREATE TABLE unit_snapshots_p3 PARTITION OF unit_snapshots
    FOR VALUES WITH (MODULUS 4, REMAINDER 3);

-- Buat GiST index komposit pada tick dan koordinat spasial (point)
CREATE INDEX idx_snapshots_tick_spatial 
ON unit_snapshots USING gist (match_id, tick, position);

Pencarian Unit dalam Radius Area

Untuk mendeteksi unit yang berada dalam radius melingkar dari suatu titik ledakan (AoE) pada tick tertentu, gunakan operator containment <@ pada tipe circle:

SELECT 
    unit_id, 
    position[0] AS x, 
    position[1] AS y, 
    hp
FROM unit_snapshots
WHERE match_id = 'a6b32dc8-b4b3-4f91-93bf-ec0cfcb38d61'
  AND tick = 2450
  AND position <@ circle(point(120.0, 350.0), 15.0);

Ekspresi circle(point(X, Y), Radius) membentuk geometri lingkaran target. Operator <@ memerintahkan planner untuk menggunakan GiST index tree guna mengambil entitas yang posisinya berada di dalam radius 15 unit dari titik (120.0, 350.0).

Evaluasi Rencana Eksekusi: B-Tree vs GiST

Sebelum: Eksekusi Menggunakan B-Tree Index (tick, x, y)

Bitmap Heap Scan on unit_snapshots (cost=412.30..8450.12 rows=18 width=24) (actual time=14.231..82.115 rows=12 loops=1)
  Recheck Cond: ((tick = 2450) AND (pos_x >= 105.0) AND (pos_x <= 135.0))
  Filter: ((pos_y >= 335.0) AND (pos_y <= 365.0) AND (point(pos_x, pos_y) <@ '<(120,350),15>'::circle))
  Rows Removed by Filter: 1420
  ->  Bitmap Index Scan on idx_btree_tick_xy (cost=0.00..412.25 rows=1450 width=0) (actual time=13.804..13.804 rows=1432 loops=1)
        Index Cond: ((tick = 2450) AND (pos_x >= 105.0) AND (pos_x <= 135.0))
Planning Time: 0.215 ms
Execution Time: 82.201 ms

Sesudah: Eksekusi Menggunakan GiST Index (match_id, tick, position)

Index Scan using unit_snapshots_p1_match_id_tick_position_idx on unit_snapshots_p1 (cost=0.28..8.31 rows=12 width=24) (actual time=0.045..0.068 rows=12 loops=1)
  Index Cond: ((match_id = 'a6b32dc8-b4b3-4f91-93bf-ec0cfcb38d61'::uuid) AND (tick = 2450) AND (position <@ '<(120,350),15>'::circle))
Planning Time: 0.180 ms
Execution Time: 0.091 ms

Analisis: GiST mengeliminasi fase penyaringan intermediate rows di memori. Engine langsung menavigasi sub-tree spatial bounding box yang sesuai, menurunkan execution time dari 82.2 ms ke 0.09 ms pada tabel berskala 10 juta baris.

Streaming Replay Match: Keyset Pagination

Saat client game memutar ulang rekaman pertandingan (replay spectator), backend streaming state secara berkala per batch data tick. Penggunaan OFFSET dilarang karena kompleksitasnya $O(N)$ terhadap baris yang dilewati.

Gunakan keyset pagination (seek method) pada indeks deterministik (match_id, tick, unit_id):

-- Indeks deterministik khusus pipeline streaming replay
CREATE INDEX idx_replay_stream 
ON unit_snapshots (match_id, tick ASC, unit_id ASC);

-- Batch pertama:
SELECT tick, unit_id, position, hp
FROM unit_snapshots
WHERE match_id = 'a6b32dc8-b4b3-4f91-93bf-ec0cfcb38d61'
ORDER BY tick ASC, unit_id ASC
LIMIT 500;

-- Batch berikutnya: Gunakan komposit nilai terakhir dari batch sebelumnya
-- Asumsikan record terakhir yang diterima: tick = 150, unit_id = 42
SELECT tick, unit_id, position, hp
FROM unit_snapshots
WHERE match_id = 'a6b32dc8-b4b3-4f91-93bf-ec0cfcb38d61'
  AND (tick, unit_id) > (150, 42)
ORDER BY tick ASC, unit_id ASC
LIMIT 500;

Komparasi tuple (tick, unit_id) > (:last_tick, :last_unit_id) memanfaatkan traversal B-Tree secara konstan $O(\log N + M)$ di mana $M$ adalah ukuran LIMIT, menjamin transmisi state game tetap stabil pada throughput tinggi tanpa jitter latency.

Trade-off dan Limitasi Teknis

  • Biaya Penulisan (Write Amplification): Pembangunan tree GiST membutuhkan siklus CPU lebih tinggi daripada B-Tree murni saat evaluasi split leaf node R-Tree. Jika backend menulis snapshot langsung secara real-time batching, pastikan throughput disk (IOPS) mencukupi, atau masukkan data melalui message queue/staging table terlebih dahulu.
  • Index Bloat: Update data in-place pada GiST dapat menyebabkan penurunan kerapatan bounding box. Karena state RTS umumnya bersifat append-only (immutable event snapshots), bloat akibat update terminimalisir secara alami. Jalankan pembersihan berkala melalui partisi: drop partisi usang secara instan tanpa perlu menjalankan operasi VACUUM FULL.