Gejala Insiden: Lonjakan CPU 100% dan Thread Starvation

Sebuah layanan backend microservice pemrosesan aturan filter mengalami kegagalan saat menerima payload ekspresi kompleks. Metrik sistem menunjukkan utilisasi CPU menyentuh 100% pada semua core secara konstan, diikuti oleh lonjakan request latency dari sub-milidetik menjadi puluhan detik hingga mencapai ambang batas HTTP timeout (504 Gateway Timeout).

Dampaknya adalah thread starvation: worker pool WSGI/ASGI kehabisan thread aktif untuk melayani request baru karena seluruh thread terperangkap dalam loop komputasi parser. Analisis awal memastikan tidak ada kendala I/O atau network lock; masalah murni berakar pada CPU-bound parsing.

Root Cause: State Explosion pada Naive Recursive Backtracking

Parser aturan filter ini awalnya diimplementasikan menggunakan kombinasi regular expression dan recursive descent parser naif. Ketika input tidak cocok pada cabang grammar bersarang (seperti nested grouping atau repeated optional clauses), engine mencoba setiap kemungkinan permutasi secara rekursif.

Misalkan terdapat token parsing aturan seperti ((a|b)*)*c atau sub-parser kondisional dengan banyak cabang bercabang. Ketika string masukan berformat aaaa...aX (diakhiri karakter yang menggagalkan kecocokan), engine melakukan catastrophic backtracking. Kompleksitas komputasi meledak dari O(n) menjadi eksponensial O(2n).

# Implementasi Naif: Rekursi tanpa batasan state (Eksponensial)
def naive_match(pattern_tree, text, idx=0):
    if not pattern_tree:
        return idx == len(text), idx
    op, children = pattern_tree[0], pattern_tree[1:]
    if op == 'LITERAL':
        char = children[0]
        if idx < len(text) and text[idx] == char:
            return naive_match(pattern_tree[1], text, idx + 1)
        return False, idx
    if op == 'OR':
        # Mencoba cabang kiri lalu kanan secara rekursif tak berbatas
        for branch in children:
            matched, end_idx = naive_match([branch], text, idx)
            if matched:
                sub_matched, final_idx = naive_match(pattern_tree[1], text, end_idx)
                if sub_matched:
                    return True, final_idx
        return False, idx
    return False, idx

Rekursi tak terbatas ini mengakibatkan alokasi stack frame masif dan eksplorasi lintasan komputasi redundan yang berulang kali gagal pada titik yang sama.

Solusi: Mengadopsi Evaluasi Goal-Directed ala Bahasa Icon

Bahasa pemrograman Icon (Griswold, 1983) memperkenalkan paradigma goal-directed evaluation. Dalam konsep ini, setiap ekspresi berfungsi sebagai generator: menghasilkan nilai jika berhasil (success), menghasilkan alternatif berikutnya jika operasi downstream gagal (backtracking internal), atau memicu failure tanpa melempar runtime exception.

Evaluasi goal-directed menyelesaikan masalah memory exhaustion dan state explosion dengan dua aturan inti:

  • Suspension and Resumption: Generator hanya mengevaluasi satu state alternatif pada satu waktu, menangguhkan eksekusi, lalu melanjutkan pencarian hanya jika ekspresi induk menolaknya.
  • Pruning / Bounded Choice: Jika batas traversal atau kriteria kecocokan parsial tercapai, jalur backtracking langsung dipotong (serupa operator cut pada Prolog atau atomic grouping pada modern regex).

Implementasi Parser Generator Deterministik

Menggunakan generator Python (yield), kita dapat mereplikasi evaluasi goal-directed Icon untuk string matching tanpa mengalokasikan memori eksplisit untuk seluruh pohon state:

def match_literal(expected, text, pos):
    if pos < len(text) and text[pos] == expected:
        yield pos + 1  # Sukses menghasilkan posisi berikutnya, lalu suspend

def match_or(generator_funcs, text, pos):
    # Mencoba alternatif secara lazy
    for func in generator_funcs:
        for next_pos in func(text, pos):
            yield next_pos

def match_seq(g1, g2, text, pos):
    # Goal-directed evaluation: g2 gagal memicu evaluasi alternatif dari g1
    for p1 in g1(text, pos):
        for p2 in g2(text, p1):
            yield p2

# Bounded traversal: Menghentikan evaluasi berulang yang tidak menghasilkan kemajuan
def parse_expression(text):
    # ponytail: naive generator pipeline, upgrade to DFA for complex grammars
    def grammar(t, pos):
        branch_a = lambda t, p: match_seq(
            lambda t, p: match_literal('a', t, p),
            lambda t, p: match_literal('b', t, p),
            t, p
        )
        branch_b = lambda t, p: match_literal('a', t, p)
        return match_or([branch_a, branch_b], t, pos)

    # Eksekusi goal-directed: Cari solusi pertama yang valid
    for final_pos in grammar(text, 0):
        if final_pos == len(text):
            return True
    return False

Verifikasi dan Uji Latensi

Pengujian dilakukan terhadap payload non-matching bersarang "a" * 25 + "!". Hasil perbandingan menunjukkan degradasi terkendali:

  • Parser Naif: Membutuhkan waktu > 12.4 detik, pemakaian CPU core penuh (100%), dan thread terkunci.
  • Goal-Directed Generator: Berhenti dalam 0.003 milidetik segera setelah jalur alternatif gagal divalidasi oleh consumer, penggunaan memori flat O(d) di mana d adalah kedalaman grammar.

Unit Test Verifikasi

import time

def test_catastrophic_backtracking_mitigation():
    bad_payload = "a" * 28 + "!"
    
    start_time = time.perf_counter()
    result = parse_expression(bad_payload)
    duration = time.perf_counter() - start_time
    
    assert result is False, "Payload tidak valid harus menghasilkan False"
    assert duration < 0.05, f"Parsing memakan waktu terlalu lama: {duration} detik"

if __name__ == '__main__':
    test_catastrophic_backtracking_mitigation()
    print("Test passed: backtracking aman dan bounded.")

Trade-off dan Alternatif

Meskipun generator evaluasi goal-directed menyelesaikan lonjakan memori dan mudah diintegrasikan ke kode prosedural backend, solusi ini memiliki batas toleransi:

  • Kapan Menggunakan Evaluasi Goal-Directed: Sangat baik untuk domain-specific languages (DSL) sederhana, query builders, atau filter payload dinamis yang membutuhkan backtracking terkontrol tanpa menulis state machine manual yang rumit.
  • Kapan Memilih Deterministik Lexing/Parsing (DFA/Packrat): Jika grammar berukuran besar dan berulang, konversi langsung grammar ke Deterministic Finite Automaton (DFA) via parser combinator atau lexer berbasis ragel/lex menjamin batas run-time O(n) murni, meniadakan backtracking sama sekali dengan trade-off kompleksitas struktur kode.