Bottleneck Ekstraksi AST pada Pipeline Git

Mengekstrak graph entitas semantik (semantic code graph) langsung dari commit Git—seperti pada arsitektur Sem—adalah operasi komputasi intensif. Parser seperti Tree-sitter atau parser bawaan bahasa membutuhkan siklus CPU signifikan untuk membangun Abstract Syntax Tree (AST), melakukan resolusi simbol, dan merekonstruksi relasi dependensi.

Masalah performa muncul ketika setiap event git push memicu worker queue untuk mem-parsing ulang ribuan file pada satu commit snapshot. Kondisi ini menyebabkan:

  • CPU Spike 100%: Concurrency worker mengeksekusi parser secara paralel pada file yang sama berulang kali.
  • Queue Backpressure: Antrean memanjang karena pengerjaan merge commit berukuran besar menahan pengerjaan commit kecil berikutnya.
  • Redundant I/O: Membaca objek blob yang identik dari disk atau storage berkali-kali.

Content-Addressable Cache Berbasis Git OID

Git adalah Content-Addressable Storage (CAS). Setiap file direpresentasikan sebagai objek Blob, dan setiap direktori direpresentasikan sebagai objek Tree. Identifier uniknya adalah Object ID (OID), yang merupakan hash cryptographic (SHA-1 atau SHA-256) dari konten objek beserta header tipenya.

Sifat deterministik Git OID memberikan jaminan fundamental: Jika Blob OID tidak berubah, AST dan representasi entitas semantik file tersebut dijamin identik 100%.

Alih-alih mem-parse seluruh snapshot workspace pada commit target, pipeline worker hanya perlu mengekstrak AST untuk Blob OID baru. Hasil ekstraksi disimpan ke key-value store (seperti Redis atau Valkey) menggunakan key format ast:blob:<oid>.

Optimasi Traversal di Level Tree OID

Optimasi tidak berhenti pada file individual. Jika sebuah subdirektori tidak mengalami perubahan antar-commit, Git Tree OID direktori tersebut tetap sama. Pipeline diff dapat melakukan skip rekursi pada subtree yang memiliki Tree OID identik, memangkas jutaan komparasi file pada monorepo.

// Perbandingan tree OID antar commit (pseudo-logic)
if parentTreeOID == currentTreeOID {
    // Subtree identik: skip seluruh file di bawah direktori ini
    return
}

Arsitektur Worker dan Pipeline Diff

Pipeline efisien membagi pekerjaan menjadi dua fase:

  1. Fase Ingestion & Diffing: Worker mengeksekusi Git plumbing command git diff-tree -r --raw <parent_commit> <current_commit> untuk mendapatkan daftar Blob OID yang ditambah (A) atau diubah (M). File yang dihapus (D) langsung ditandai pada database semantic graph tanpa parsing.
  2. Fase Parsing & Cache Resolution: Worker memeriksa eksistensi OID pada cache. Hanya OID berstatus miss yang dikirim ke engine AST parser.

Queue Job Deduplication

Jika pengembang mem-push beberapa branch yang memiliki basis commit identik secara bersamaan, antrean worker berpotensi menerima ribuan blob task duplikat. Solusinya adalah deduplikasi pada broker antrean menggunakan message ID berbasis Blob OID:

// Format task ID unik untuk broker antrean
task_id = fmt.Sprintf("parse-blob-%s", blobOID)

Jika task dengan ID tersebut masih berstatus pending atau processing, broker mengabaikan penambahan task baru.

Implementasi Worker Ekstraksi AST (Go)

Contoh implementasi worker Go yang memanfaatkan cache OID, library parser, dan mekanisme fallback.

package main

import (
	"context"
	"crypto/sha256"
	"encoding/json"
	"errors"
	"fmt"
	"time"

	"github.com/redis/go-redis/v9"
)

type ASTEntity struct {
	Name      string   `json:"name"`
	Kind      string   `json:"kind"` // function, struct, interface
	Signature string   `json:"signature"`
	Imports   []string `json:"imports"`
}

type ExtractorWorker struct {
	rdb *redis.Client
}

func NewExtractorWorker(rdb *redis.Client) *ExtractorWorker {
	return &ExtractorWorker{rdb: rdb}
}

// ProcessBlob mengekstrak AST berdasarkan Git Blob OID
func (w *ExtractorWorker) ProcessBlob(ctx context.Context, blobOID string, rawContent []byte) ([]ASTEntity, error) {
	cacheKey := fmt.Sprintf("ast:blob:%s", blobOID)

	// 1. Cek cache
	cachedData, err := w.rdb.Get(ctx, cacheKey).Bytes()
	if err == nil {
		var entities []ASTEntity
		if err := json.Unmarshal(cachedData, &entities); err == nil {
			return entities, nil // Cache hit
		}
	} else if !errors.Is(err, redis.Nil) {
		return nil, fmt.Errorf("redis error: %w", err)
	}

	// 2. Cache miss: Parse AST (Simulasi ekstraksi semantik)
	entities, err := parseSourceCode(rawContent)
	if err != nil {
		return nil, fmt.Errorf("failed to parse AST: %w", err)
	}

	// 3. Simpan ke cache secara permanen (OID bersifat immutable)
	payload, err := json.Marshal(entities)
	if err == nil {
		// TTL panjang atau no-TTL karena blob OID bersifat konstan
		w.rdb.Set(ctx, cacheKey, payload, 30*24*time.Hour)
	}

	return entities, nil
}

func parseSourceCode(content []byte) ([]ASTEntity, error) {
	// Integrasikan dengan tree-sitter atau native parser (go/parser, babel, dll.)
	// Dummy extraction:
	return []ASTEntity{
		{Name: "CalculateMetrics", Kind: "function", Signature: "func(int) bool"},
	}, nil
}

Mitigasi Cache Stampede pada Merge Commit

Saat merge commit besar masuk (misal penggabungan release branch yang berisi 5.000 file baru), ratusan worker paralel berpotensi menerima instruksi parsing untuk sekumpulan OID yang sama. Ini memicu cache stampede atau thundering herd problem.

1. Distributed Lock Menggunakan Redis SETNX

Sebelum menjalankan komputasi AST berat pada OID yang belum ada di cache, worker harus mengakuisisi distributed lock untuk OID tersebut. Worker lain yang gagal mengakuisisi lock harus menunggu hingga hasil parsing tersedia di cache daripada mengeksekusi parser sendiri.

func (w *ExtractorWorker) ProcessBlobWithLock(ctx context.Context, blobOID string, rawContent []byte) ([]ASTEntity, error) {
	cacheKey := fmt.Sprintf("ast:blob:%s", blobOID)
	lockKey := fmt.Sprintf("lock:blob:%s", blobOID)

	// Cek cache awal
	cached, err := w.rdb.Get(ctx, cacheKey).Bytes()
	if err == nil {
		var entities []ASTEntity
		_ = json.Unmarshal(cached, &entities)
		return entities, nil
	}

	// Coba acquire lock (TTL 10 detik untuk antisipasi crash)
	locked, err := w.rdb.SetNX(ctx, lockKey, "1", 10*time.Second).Result()
	if err != nil {
		return nil, err
	}

	if !locked {
		// Gagal dapat lock: Worker lain sedang memproses OID ini.
		// Polling singkat untuk menunggu cache terisi.
		for i := 0; i < 20; i++ {
			time.Sleep(100 * time.Millisecond)
			cached, err := w.rdb.Get(ctx, cacheKey).Bytes()
			if err == nil {
				var entities []ASTEntity
				_ = json.Unmarshal(cached, &entities)
				return entities, nil
			}
		}
		return nil, errors.New("timeout waiting for concurrent parser")
	}

	defer w.rdb.Del(ctx, lockKey)

	// Eksekusi parsing
	entities, err := parseSourceCode(rawContent)
	if err != nil {
		return nil, err
	}

	payload, _ := json.Marshal(entities)
	w.rdb.Set(ctx, cacheKey, payload, 30*24*time.Hour)

	return entities, nil
}

Catatan: Jika worker berjalan dalam single-instance multi-threaded, gunakan golang.org/x/sync/singleflight untuk menekan duplicate execution lokal tanpa overhead jaringan Redis.

Batasan dan Trade-Offs

  • Cross-File Type Resolution: Caching per-Blob OID sangat efektif untuk isolated syntactic analysis (AST lokal, nama fungsi, signature). Namun, untuk resolusi relasi antar-file (seperti type-checking lintas modul), perubahan pada satu interface file dapat membatalkan tipe di file lain meskipun OID file kedua tidak berubah. Pisahkan ekstraksi menjadi dua tahap: Ekstraksi AST per-blob (cached by OID) dan Graph Resolution per-commit (inkremental).
  • Penyimpanan Cache: Repositori masif dapat memproduksi jutaan blob unik seiring waktu. Terapkan Redis eviction policy berupa allkeys-lru atau simpan persistent payload di object store (S3/MinIO) dengan Redis hanya sebagai OID index pointer.