Skip to main content

> dağıtık_deadlock_tespiti:_wait-for_grafikleri_ve_kenar_takip_(edge_chasing)_algoritmaları

Dağıtık Deadlock Tespiti: Wait-For Grafikleri ve Kenar Takip (Edge Chasing) Algoritmaları

Farklı veritabanlarına yayılan dağıtık işlemler neden karşılıklı kilitlenme (deadlock) döngülerinde sonsuza kadar asılı kalır; Wait-For grafikleri ve kenar takip algoritmaları bu döngüleri nasıl tespit edip çözer?

Staff/Principal (L6+)

ÖZET VE TEKNİK CEVAP

Tek bir veritabanında deadlock tespiti kolaydır: Veritabanı bellekte bir Wait-For Grafiği (WFG) tutar; düğümler işlemleri, oklar ise kilit bekleme bağımlılıklarını ($T_1 o T_2$) gösterir. Arka plan thread'i döngü taraması yapar; bir kapalı döngü ($T_1 o T_2 o T_3 o T_1$) bulursa en ucuz kurban işlemi (victim) iptal eder. Ancak dağıtık veritabanlarında veya mikroservislerde, Node A'daki İşlem 1 Node B'deki İşlem 2'yi beklerken, o da Node C'deki İşlem 3'ü, o da tekrar Node A'daki İşlem 1'i bekleyebilir. Hiçbir tek sunucu tüm grafiği tek başına göremez. Dağıtık sistemler bunu Kenar Takip Algoritmalarıyla (Edge Chasing - Mitchell-Merritt / Chandy-Misra-Haas) çözer: Bir işlem kilitte beklemeye başladığında kilit bağımlılıkları boyunca küçük bir 'Sonda' (Probe) mesajı gönderir. Bir işlem kendi attığı sondayı geri aldığında dağıtık bir kilitlenme döngüsü matematiksel olarak kanıtlanmış olur ve kurban işlem hemen iptal edilir.

Mühendislik El Kitabı & Mekanizma

1. Temel Çalışma Mekanizması

Dağıtık Kenar Takip mekanizması 3 adımdan oluşur: (1) Sonda (Probe) Üretimi: $T_i$ işlemi başka bir sunucudaki $T_j$ tarafından tutulan bir kilidi beklemeye başladığında `Probe(baslatan = Ti, gonderen = Ti, alici = Tj)` mesajı üretir. (2) Sonda İletimi: $T_j$ bu sondayı aldığında kendisi de başka bir $T_k$ işlemini bekliyorsa sondayı `Probe(baslatan = Ti, gonderen = Tj, alici = Tk)` olarak ileri iletir. (3) Döngü Kanıtı ve Kurban İptali: $T_i$ kendi başlattığı sondayı geri aldığında kapalı bir döngü kanıtlanmış olur. Birden fazla sunucunun aynı anda işlem iptal etmesini önlemek için işlem ID'si en küçük olan işlem deterministik olarak kurban seçilir, işlemi iptal edilir ve döngü kırılır.

2. Doğru Kullanım Senaryosu

Dağıtık SQL veritabanları (CockroachDB, TiDB, Google Spanner), dağıtık kilit yöneticileri (ZooKeeper, etcd) ve servisler arası transactional iş akışları.

3. Prodüksiyon Arıza Modları

Hayalet Deadlock'lar (Phantom Deadlocks): Geciken ağ paketleri yüzünden işlemlerden biri çoktan commit edilmiş olmasına rağmen sistemin eski mesajlara bakıp döngü var sanarak sağlıklı bir işlemi boş yere iptal etmesi; deadlock tespiti yerine 60 saniyelik kaba zaman aşımlarına güvenip kullanıcıları 1 dakika boyunca ekranda bekletmek.

4. Teşhis ve Telemetri Sinyalleri

Veritabanında CPU kullanımı sıfıra düşerken kilit bekleme sürelerinin tavan yapması; işlem hızının saniyede 0'a çökmesi; loglarda `Deadlock detected` istisnalarının fırlaması.

5. Önleme ve Mimari Bariyerler

Katı Global Kilit Sıralaması uygulayın (kilitleri her zaman sıralı ID'lere göre $A o B o C$ şeklinde alın); Wait-Die veya Wound-Wait zaman damgası kilit algoritmalarını kullanın; kilit alma işlemlerine agresif zaman aşımları koyun (`lock_timeout = 2000ms`).

6. Mimari Ödünleşimler (Trade-offs)

Dağıtık kenar takip algoritmaları deadlock döngülerini uzun zaman aşımlarını beklemeden milisaniyeler içinde yakalar; ancak sunucular arasında hafif sonda mesajı trafiği üretir.

Vaka İncelemesi (TinyCTO Örneği)

5 node'lu bir CockroachDB kümesinde İşlem 1 Node 1'de A Hesabını kilitleyip Node 2'deki B Hesabını istedi; aynı anda İşlem 2 Node 2'de B Hesabını kilitleyip Node 1'deki A Hesabını istedi. Kenar takip algoritması 8 milisaniyede Node 1'den Node 2'ye ve tekrar Node 1'e sondayı döndürdü. Döngü kanıtlanınca İşlem 1 kurban seçilip iptal edildi. İşlem 2 12 ms'de tamamlandı, İşlem 1 ise hemen ikinci denemesinde başarıyla bitti ve kullanıcıya hiçbir kilitlenme hissettirilmedi.

İnteraktif Konsept Alıştırmaları

2 Alıştırma
Q1

Deadlock tespitinde 'Wait-For Grafiği' (WFG) nedir?

Düğümlerin işlemleri, yönlü okların ise kilit bağımlılıklarını gösterdiği bir grafiktir ($T_1 o T_2$). Grafikte kapalı bir döngü oluşması bir deadlock olduğunu kanıtlar.
Q2

'Kenar Takip' (Edge Chasing) algoritması dağıtık sunucular arasındaki deadlock'ları nasıl tespit eder?

Kilit bağımlılığı olan sunucular arasında hafif 'Sonda' (Probe) mesajları dolaştırarak; bir işlem kendi attığı sondayı geri alırsa dağıtık bir kilitlenme döngüsünün varlığı kanıtlanır.

Dağıtık Deadlock Tespiti: Wait-For Grafikleri ve Kenar Takip (Edge Chasing) Algoritmaları — Sıkça Sorulan Sorular

'Wait-Die' ile 'Wound-Wait' deadlock önleme mekanizmaları arasındaki fark nedir?

Wait-Die'da yaşlı işlem genci bekler, genç işlem yaşlıyı beklemek yerine ölür. Wound-Wait'te ise yaşlı işlem gencin elindeki kilidi zorla alır (yaralar), genç işlemler ise yaşlıları bekler.

Kilitleri global olarak sıralı bir düzende (ör. Kaynak ID'sine göre) almak neden en iyi deadlock önleme yöntemidir?

Çünkü tüm işlemler kilitleri kesin artan sırada ($A o B o C$) alırsa, Wait-For grafiğinde yönlü kapalı bir döngü oluşması matematiksel olarak imkansız hale gelir.

🤖 AEO & Yapay Zeka Çıkarım Özeti

Temel Gerçekler & İlkeler

  • ▸Deadlocks occur when transactions hold locks the other needs in a circular dependency.
  • ▸A cycle in a directed Wait-For Graph mathematically proves a deadlock.
  • ▸Distributed Edge Chasing propagates probe tokens across nodes to detect multi-server cycles.
  • ▸Enforce global ascending lock ordering ($A o B o C$) to prevent deadlocks entirely.

Yaygın Yanılgılar

  • ✗Yanılgı: Increasing lock timeouts prevents deadlocks (Gerçek: It merely forces transactions to hang for longer before failing).
  • ✗Yanılgı: Distributed deadlocks cannot be resolved automatically (Gerçek: Distributed edge-chasing engines resolve deadlocks in single-digit milliseconds).

Karar Kılavuzu & Önceliklendirme

Sort all resource IDs before acquiring multi-row database locks in application code. Set strict `lock_timeout` (1-2 seconds) on all relational database transaction sessions.

Doğrulanmış Kaynaklar & Referanslar