Akar Masalah: Dynamic DAG dan Circular Wait

Eksekusi task graph dinamis (DAG yang simpul atau dependensinya berkembang saat runtime) pada arsitektur worker queue terdistribusi sering mengalami kegagalan circular deadlock. Masalah ini lazim ditemukan pada sistem komputasi modular yang mengekspansi sub-task secara rekursif mirip model ekspansi modular MorphoHDL.

Deadlock terjadi akibat terpenuhinya empat kondisi Coffman, khususnya Circular Wait dan Hold and Wait. Ketika Worker 1 memproses Task A dan mengklaim Resource $R_1$, ia mengekspansi graf dan membutuhkan Resource $R_2$. Pada saat bersamaan, Worker 2 memproses Task B yang memegang lock $R_2$ dan membutuhkan $R_1$. Tanpa koordinasi global terpusat, urutan alokasi lock bergantung pada latensi pengambilan job dari queue (kondisi non-deterministik), yang berujung pada lock order inversion.

Pencegahan Deadlock: Deterministic Ordering & Kahn's Algorithm

Solusi matematis paling efektif untuk memutus circular wait adalah memaksakan hierarki penguncian deterministik secara global. Jika seluruh worker dipaksa mengakuisisi resource dengan urutan terurut secara strictly monotonic ($R_1 < R_2 < ... < R_n$), siklus ketergantungan mustahil terbentuk.

Sebelum sub-graph dinamis didaftarkan ke worker queue, sistem harus melakukan dua validasi:

  1. Runtime Cycle Detection: Memvalidasi struktur dependensi sub-graph baru menggunakan algoritma Kahn (berbasis in-degree counting) atau Depth-First Search (DFS) untuk memastikan tidak ada siklus logis antartask.
  2. Global Resource Canonical Sorting: Saat sebuah task membutuhkan multi-lock pada beberapa resource bersama, ID resource diurutkan secara leksikografis sebelum pemanggilan fungsi akuisisi lock dilakukan.

Verifikasi Siklus Sub-Graph (Algoritma Kahn)

Algoritma Kahn beroperasi dengan menghitung derajat masuk (in-degree) setiap node. Simpul dengan in-degree nol dimasukkan ke dalam antrean. Jika jumlah simpul yang diproses dalam topological sort kurang dari total simpul pada sub-graph, graf tersebut memiliki siklus dan harus ditolak sebelum alokasi lock.

Implementasi: Akuisisi Multi-Lock Deterministik di Go

Kode Go berikut mendemonstrasikan pengurutan kanonikal resource, deteksi siklus sederhana, akuisisi lock berurutan dengan lease timeout (menggunakan simulasi Redis/etcd distributed locker), serta rollback otomatis jika terjadi kegagalan akuisisi.

package main

import (
	"context"
	"errors"
	"fmt"
	"sort"
	"sync"
	"time"
)

type DistributedLockManager interface {
	Acquire(ctx context.Context, resource string, ttl time.Duration) (string, error)
	Release(ctx context.Context, resource string, leaseID string) error
}

type MemoryLockManager struct {
	mu    sync.Mutex
	held  map[string]string
}

func NewMemoryLockManager() *MemoryLockManager {
	return &MemoryLockManager{held: make(map[string]string)}
}

func (m *MemoryLockManager) Acquire(ctx context.Context, resource string, ttl time.Duration) (string, error) {
	m.mu.Lock()
	defer m.mu.Unlock()
	if _, exists := m.held[resource]; exists {
		return "", errors.New("lock contention: resource busy")
	}
	leaseID := fmt.Sprintf("lease-%d", time.Now().UnixNano())
	m.held[resource] = leaseID
	return leaseID, nil
}

func (m *MemoryLockManager) Release(ctx context.Context, resource string, leaseID string) error {
	m.mu.Lock()
	defer m.mu.Unlock()
	if heldID, exists := m.held[resource]; exists && heldID == leaseID {
		delete(m.held, resource)
		return nil
	}
	return errors.New("invalid lease or lock already released")
}

type LockHandle struct {
	Resource string
	LeaseID  string
}

// AcquireLocksDeterministic mengurutkan resource secara kanonikal untuk mencegah circular wait.
func AcquireLocksDeterministic(
	ctx context.Context,
	lm DistributedLockManager,
	resources []string,
	ttl time.Duration,
) ([]LockHandle, error) {
	if len(resources) == 0 {
		return nil, nil
	}

	// 1. Hilangkan duplikasi dan urutkan secara leksikografis (Topological Lock Hierarchy)
	sorted := make([]string, len(resources))
	copy(sorted, resources)
	sort.Strings(sorted)

	unique := make([]string, 0, len(sorted))
	for i, res := range sorted {
		if i == 0 || res != sorted[i-1] {
			unique = append(unique, res)
		}
	}

	acquired := make([]LockHandle, 0, len(unique))

	// 2. Akuisisi berurutan dengan timeout dan rollback cascade
	for _, res := range unique {
		leaseID, err := lm.Acquire(ctx, res, ttl)
		if err != nil {
			// Rollback semua lock yang sudah didapat sebelumnya
			for _, h := range acquired {
				_ = lm.Release(context.Background(), h.Resource, h.LeaseID)
			}
			return nil, fmt.Errorf("failed acquiring lock for %s: %w", res, err)
		}
		acquired = append(acquired, LockHandle{Resource: res, LeaseID: leaseID})
	}

	return acquired, nil
}

Penanganan Failover dan Idempotensi

Worker dapat mengalami crash (OOM, restart node, segment fault) saat berada di tengah proses ekspansi task graph. Kondisi parsial ini berisiko meninggalkan resource terkunci tanpa batas waktu atau menduplikasi sub-task pada queue saat retry otomatis dilakukan.

1. Lock Leases dengan Heartbeat (Fencing Token)

Distributed lock wajib menggunakan TTL (Time-to-Live). Lock manager harus mengembalikan nomor versi monotonik naik (fencing token) setiap kali lock diberikan. Jika worker mengalami network partition atau freeze GC yang melebihi batas TTL, lock akan kedaluwarsa secara otomatis dan resource dapat diklaim worker lain. Saat worker lama bangun, operasi mutasi akan ditolak oleh storage engine karena fencing token-nya telah usang.

2. Idempotent Graph Expansion

Untuk mencegah pembuatan simpul duplikat akibat retry worker, terapkan Idempotency Key deterministik pada setiap edge dan node yang diekspansi. Pola konstruksinya:

IdempotencyKey = SHA256(ParentTaskID + NodeLogicalIndex + SubGraphVersion)

Sebelum worker mengalokasikan lock baru atau meng-insert task ke queue, sistem mengecek state store apakah IdempotencyKey sudah berada pada status COMMITTED. Jika sudah, worker cukup membaca hasil ekspansi sebelumnya dan langsung melanjutkan pipeline.

Metrik Observabilitas Lock Contention

Mendeteksi potensi deadlock dan efisiensi locking membutuhkan instrumentasi metrik spesifik pada distributed lock client dan worker queue:

  • lock_acquisition_duration_seconds (Histogram): Mengukur latensi proses perolehan lock. Lonjakan pada persentil p99 menandakan antrean kontensi tinggi pada resource tertentu.
  • lock_contention_total (Counter): Jumlah kegagalan akuisisi lock karena resource sedang dipegang task lain. Berguna untuk mendeteksi resource bottleneck.
  • lock_lease_expired_before_release_total (Counter): Jumlah peristiwa di mana lock lepas otomatis akibat timeout sebelum task selesai. Jika metrik ini naik, task execution time melebihi konfigurasi TTL atau terjadi worker stall.
  • graph_cycle_detected_total (Counter): Menghitung frekuensi ekspansi dinamis yang digagalkan oleh algoritma validasi siklus (Kahn/DFS) di fase pra-akuisisi.

Kombinasi hierarki lock deterministik, kontrol lease berbasis waktu, dan validasi topologi siklus memastikan worker queue tetap resilien tanpa risiko kebuntuan permanen.