hkucuk

Chandy-Lamport Algoritması: Dağıtık Sistemlerde Küresel Durum Nasıl Görüntülenir?

23 Şubat 2025 • ☕️☕️ 10 dk okuma • 🏷 bilgisayar, yazılım, algoritma

Yazar tarafından şu dillere çevrildi: English


Dağıtık sistemler, birden fazla bağımsız sürecin veya düğümün (node) ortak bir amaç doğrultusunda işbirliği yaptığı sistemlerdir. Modern teknoloji dünyasında mikroservis mimarilerinden, bulut (cloud) altyapılarına kadar pek çok alanda yaygın bir şekilde kullanılmaktadırlar.

  • Küresel durum (global state), bir dağıtık sistemi oluşturan tüm süreçlerin ve bu süreçler arasındaki iletişim kanallarının o andaki durumlarının birleşimidir.
  • Dağıtık bir sistemde küresel durumun belirlenmesi; hata tespiti, checkpointing, hata toleransı ve işlem koordinasyonu gibi konularda kritik bir rol oynar.

Fakat burada büyük bir sorun vardır: Dağıtık sistemlerde, tek bir küresel saat (global clock) veya tüm düğümleri aynı anda “donduran” bir mekanizma bulunmadığından, “O an” kavramı her düğüm için farklı olabilir. Bu durum tutarlı bir küresel durumun yakalanmasını zorlaştırır. Chandy-Lamport Algoritması bu sorunu çözmek için geliştirilmiş klasik bir metottur.

Chandy-Lamport Algoritması

Dağıtık Sistemlerde Küresel Durum Kavramı

Dağıtık bir sistemde:

  1. Süreçler (Processes): Her biri bağımsız çalışan genellikle bir işlemci, bir çekirdek veya bir program parçası.
  2. İletişim Kanalları (Channels): Süreçler arasındaki mesaj iletim yolları. Bu kanalların kendine özgü gecikmeleri veya sıralama sorunları olabilir.

Bir süreç yerel durum (local state) olarak adlandırılan kendi belleği, kaydedilmiş değişkenleri, veri yapılarını vs. saklar. Küresel durum tüm süreçlerin yerel durumlarının ve süreçler arası kanallarda bulunan mesajların birleşiminden oluşur.

Chandy-Lamport Algoritması’nın Tarihçesi ve Önemi

Chandy-Lamport Algoritması, K. Mani Chandy ve Leslie Lamport tarafından 1985 yılında yayımlanan “Distributed Snapshots: Determining Global States of Distributed Systems” başlıklı makalede tanıtılmıştır. Bu makale dağıtık sistemlerde tutarlı snapshot (anlık görüntü) alma problemine getirdiği çözüm ile literatürde çığır açmıştır.

Algoritma, o zamandan bu yana:

  • Checkpointing: Dağıtık sistemin o andaki durumunu kaydedip, bir hata sonrası bu duruma geri dönme.
  • Hata tespiti: Örneğin “hangi süreçler çalışıyor, hangileri çalışmıyor” gibi durumların gözlemlenmesi.
  • Deadlock tespiti ve analizi: Bazı süreçler kaynak bekleyerek sıkıştığında küresel durumun analizi gerekir.

gibi birçok alanda temel bir çerçeve sunmuştur.

Algoritmanın Temel İlkeleri

Chandy-Lamport Algoritması şu basit ama etkili fikre dayanır:

  1. Marker (İşaretleyici) Kullanımı: Bir süreç anlık görüntü (snapshot) başlatmaya karar verdiğinde, kendi durumunu kaydeder ve diğer süreçlere özel bir marker mesajı gönderir.
  2. Koordinasyon: Marker mesajı alan süreçler, eğer bu marker’ı ilk kez görüyorsa, kendi durumlarını da kaydedip marker’ı başkalarına yollar.
  3. Kanal Durumu Kaydı: Her süreç marker mesajından önce ve sonra gelen mesajları takip ederek kanal durumunu tutarlı şekilde belirler.

Bu sayede tüm süreçler zamansal olarak ayrık ancak mantıksal olarak tutarlı bir snapshot elde edebilirler.

Algoritmanın Adımları

Chandy-Lamport Algoritması üç temel aşamadan oluşur:

  1. Snapshot (Anlık Görüntü) Başlatma

    • Bir süreç (örneğin P_1), kendi yerel durumunu kaydeder.
    • Tüm komşu süreçlere birer marker mesajı gönderir.

  2. Marker Mesajının Alınması

    • Başka bir süreç (ör. P_2), eğer bu algoritmayı ilk kez başlatıyorsa:

      • Kendi yerel durumunu kaydeder.
      • Tüm komşularına marker mesajı gönderir.
      • Marker mesajı gelmeden önce alınan mesajları ilgili kanalın parçası olarak kaydeder.
    • Eğer süreç zaten bir snapshot başlatmışsa ve marker mesajını ikinci kez görüyorsa, bu marker sadece kanal durumunu tamamlamak için kullanılır.

  3. Kanal Durumunu Kaydetme

    • Bir kanalın durumu, marker mesajı geldiği andan itibaren veya marker’ı gönderdikten hemen sonraki mesaj trafiği ile ilişkilendirilir.
    • Böylece, kanalın o anki içeriği (gelen ama henüz işlenmemiş mesajlar) kaydedilmiş olur.

Kanal (Channel) Durumlarının Kaydedilmesi

Kanal durumu bir sürecin marker mesajını gönderdikten (veya aldıktan) sonra kanal üzerinden geçen mesajlarla ilişkilendirilir. Daha kesin olmak gerekirse:

  • Bir süreç marker’ı kaydedip gönderene kadar kanal durumu kendi içinde “tamamlanmamış” kabul edilir.
  • Marker mesajı alındıktan sonra başka bir süreç, bu kanaldan gelen mesajları biriktirmeye başlar. O mesajlar snapshot’ın parçası haline gelir.

Özellikle marker mesajı almadan önce gelen mesajlar, kanal durumunun kaydedilmesine dahil olmaz. Çünkü o mesajlar zaten o kanalın önceki snapshot ile ilişkilendirilmiş ya da sürecin yerel durumuna dahil edilmiştir.

Ayrıntılı Bir Örnek Senaryo

Üç süreçten oluşan (P_1, P_2, P_3) bir dağıtık sistem düşünelim. Her bir sürecin birbiriyle etkileşimi şu şekilde olsun:

  • P_1 ↔ P_2
  • P_2 ↔ P_3
  • P_1 ↔ P_3

Yani, tam bağlı (fully connected) bir topolojiye sahibiz.

  1. Snapshot Başlatma (P_1)

    • P_1 kendi durumunu kaydeder. Diyelim ki P_1’in “belleğindeki değer: x=10”, “işlem sayısı: 3” olsun.
    • P_1, P_2 ve P_3‘e marker mesajları gönderir.

  2. Marker Mesajını P_2 Alır

    • Eğer P_2 daha önce marker mesajı almadıysa (ilk defa alıyor):
    • P_2 kendi durumunu kaydeder. (Örneğin: y=20, işlemler=5)
    • P_2, hem P_1 hem P_3‘e marker mesajı gönderir. (Aslında P_1’e de gönderir ancak P_1 marker’a sahip olduğu için sadece kanal durumunu tamamlar.)

  3. Marker Mesajını P_3 Alır

    • Aynı mantıkla, P_3 kendi durumunu kaydeder. (z=15, işlemler=7)
    • P_3, diğer iki sürece marker gönderir.

  4. Kanal Durumlarının Kaydedilmesi

    • P_2, P_3’ten marker gelmeden önce P_3’e bazı mesajlar göndermiş olabilir. Eğer bu mesajlar marker’dan önce çıktı ve marker’dan sonra teslim alındıysa, bu mesajlar “giden ama henüz işlenmemiş” bir duruma düşebilir. Dolayısıyla kanal durumuna dahil edilir.

Bu adımların tamamlanmasıyla üç sürecin de yerel durumları ve aralarındaki kanallarda “bekleyen” mesajlar kaydedilerek tam, tutarlı bir snapshot oluşturulur.

GoLang ile Kod Örneği

Aşağıda Chandy-Lamport algoritmasının basitleştirilmiş bir simülasyonunu kodlamaya çalışacağız. Örnek üç süreç (goroutine) arasında mesaj alışverişini ve bir marker mesajını nasıl işlediklerini göstermektedir.

Lütfen dikkat: Aşağıdaki kod tam bir üretim kodu değildir, daha çok eğitici bir amaç taşır. Dağıtık sistemlerde gerçek mesajlaşma genellikle ağ üzerinden gerçekleşir; burada, Go’nun chan (channel) mekanizması ile bir benzetim (simulation) yapıyoruz.

package main

import (
    "fmt"
    "sync"
    "time"
)

// We will define a simple structure to hold the state of each process
type Process struct {
    id            int
    localState    int
    hasRecorded   bool
    markerChannel chan bool
    messageChan   chan int
    wg            *sync.WaitGroup
}

// Global wait group for all processes
var wg sync.WaitGroup

func main() {
    // Create 3 processes
    process1 := Process{
        id:            1,
        localState:    10,
        hasRecorded:   false,
        markerChannel: make(chan bool, 1),
        messageChan:   make(chan int, 10),
        wg:            &wg,
    }
    process2 := Process{
        id:            2,
        localState:    20,
        hasRecorded:   false,
        markerChannel: make(chan bool, 1),
        messageChan:   make(chan int, 10),
        wg:            &wg,
    }
    process3 := Process{
        id:            3,
        localState:    30,
        hasRecorded:   false,
        markerChannel: make(chan bool, 1),
        messageChan:   make(chan int, 10),
        wg:            &wg,
    }

    // We will use one channel to simulate message passing between each pair
    // But for clarity, let's just consider processes sending messages to each other in a ring or fully connected scenario
    // Here, we simulate a fully connected pattern in a simplistic manner

    wg.Add(3)
    go process1.run(&process2, &process3)
    go process2.run(&process1, &process3)
    go process3.run(&process1, &process2)

    // Start the system for a bit, then initiate a snapshot from process1
    time.Sleep(2 * time.Second)

    fmt.Println("=== Starting Snapshot from Process 1 ===")
    process1.markerChannel <- true // send a marker to process1

    // Wait for all processes to finish
    wg.Wait()
}

// run is the main loop for each process
func (p *Process) run(p2, p3 *Process) {
    defer p.wg.Done()

    // Start a ticker that sends a message to p2 and p3 every 500ms
    ticker := time.NewTicker(500 * time.Millisecond)

    for {
        select {
        case <-ticker.C:
            // Send a random message (here, just localState) to p2 and p3
            p2.messageChan <- p.localState
            p3.messageChan <- p.localState
            fmt.Printf("Process %d sends message with content %d\n", p.id, p.localState)

        case marker := <-p.markerChannel:
            // If marker is received, handle the snapshot logic
            if marker {
                if !p.hasRecorded {
                    p.takeSnapshot()
                    // Send marker to other processes
                    p2.markerChannel <- true
                    p3.markerChannel <- true
                } else {
                    // If already recorded, do nothing special
                    // except acknowledging we received a marker
                    fmt.Printf("Process %d already recorded a snapshot\n", p.id)
                }
            }

        case msg := <-p.messageChan:
            // We receive a normal message
            fmt.Printf("Process %d receives message with content %d\n", p.id, msg)
            // If we haven't recorded yet, this message belongs to the channel state
            if !p.hasRecorded {
                fmt.Printf("Process %d: This message is stored as part of the channel state for snapshot.\n", p.id)
            }

        // We add a timeout or some condition to exit
        case <-time.After(5 * time.Second):
            fmt.Printf("Process %d shutting down.\n", p.id)
            return
        }
    }
}

// takeSnapshot simulates recording the local state
func (p *Process) takeSnapshot() {
    p.hasRecorded = true
    fmt.Printf("Process %d is recording local state: %d\n", p.id, p.localState)
    // In a real scenario, we would also store the channel states here
}

Program çalıştırıldığında çıktısı aşağıdaki gibi olacaktır.

Process 2 sends message with content 20
Process 1 receives message with content 20
Process 1: This message is stored as part of the channel state for snapshot.
Process 1 sends message with content 10
Process 3 receives message with content 20
Process 3: This message is stored as part of the channel state for snapshot.
Process 3 sends message with content 30
Process 3 receives message with content 10
Process 3: This message is stored as part of the channel state for snapshot.
Process 2 receives message with content 10
Process 2: This message is stored as part of the channel state for snapshot.
Process 2 receives message with content 30
Process 2: This message is stored as part of the channel state for snapshot.
Process 1 receives message with content 30
Process 1: This message is stored as part of the channel state for snapshot.
Process 1 sends message with content 10
Process 1 receives message with content 30
Process 1: This message is stored as part of the channel state for snapshot.
Process 1 receives message with content 20
Process 3 sends message with content 30
Process 3 receives message with content 10
Process 3: This message is stored as part of the channel state for snapshot.
Process 3 receives message with content 20
Process 3: This message is stored as part of the channel state for snapshot.
Process 1: This message is stored as part of the channel state for snapshot.
Process 2 sends message with content 20
Process 2 receives message with content 10
..........

Programın çalışır haline şuradan erişilebilir.

Bu örnek tüm Chandy-Lamport sürecinin basitleştirilmiş bir versiyonudur. Gerçek dünyada ağ gecikmeleri, yeniden iletim, hata durumları gibi karmaşık konular eklenir ve ele alınır.

Gerçek Dünya Uygulamaları

  1. Dağıtık Veritabanlarında Checkpointing

    • Önemli veritabanları zaman zaman anlık görüntüler alarak veri bütünlüğünü korurlar. Böylece bir hata olması durumunda sistem bu kayda geri dönebilir.

  2. Hata Tespiti ve Kurtarma

    • Dağıtık sistemler sürekli çevrimiçi olmayı hedeflediğinden, belirli zamanlarda alınan snapshot’lar sayesinde hangi süreçlerin çalıştığı, hangi kanallarda mesajların takılıp kaldığı gibi durumlar kolayca tespit edilir.

  3. Dağıtık Sistemlerde Tutarlılık Kontrolü

    • Örneğin blockchain gibi çoğaltılmış defter (ledger) yapıları, dönemsel olarak küresel durum bilgisine ihtiyaç duyarlar.

  4. IoT ve Mikroservis Mimarisi

    • Sensör verilerinin toplanması veya çok sayıda mikroservisin iletişimi sırasında, sistemin belirli bir anlık durumunu analiz etmek için snapshot’lar alınır.

Sık Karşılaşılan Sorular ve Yanıtları

Soru 1: Algoritma eşzamanlı (synchronous) veya eşzamanlı olmayan (asynchronous) ağlarda çalışır mı? Yanıt: Chandy-Lamport Algoritması, eşzamanlı olmayan (asynchronous) sistemlerde de çalışabilir. Hatta bu algoritmanın güzelliği iletişim gecikmelerinin belirsiz olduğu ortamlarda bile tutarlı snapshot alınmasını garanti etmesidir.

Soru 2: Marker mesajının kendisi bir durumu nasıl temsil ediyor? Yanıt: Marker mesajı “Bu kanalda snapshot başlıyor” anlamını taşır. Her süreç marker mesajını aldığında (eğer ilk kez görüyorsa) kendi yerel durumunu kaydeder ve süreci başlatır.

Soru 3: Tüm süreçler snapshot’ı tamamlayana kadar sistemi durdurmamız gerekir mi? Yanıt: Hayır. Chandy-Lamport Algoritması dağıtık çalışır ve süreçlerin normal çalışmasını engellemez. Süreçler snapshot alırken mesaj göndermeye ve almaya devam edebilir.

Soru 4: Diğer snapshot algoritmalarıyla farkı nedir? Yanıt: Chandy-Lamport marker kullanımıyla basit, genişletilebilir ve tutarlı snapshot alır. Başka algoritmalar da vardır (örneğin Mattern’ın renkli marker algoritması) ancak çoğu Chandy-Lamport fikrinden esinlenmiştir.

Chandy-Lamport Algoritması dağıtık sistemlerdeki küresel durum (global state) problemini ustalıkla çözen, marker-passing (işaretleyici iletme) temelli bir yöntemdir. Esas başarısı herhangi bir merkezi denetleyici kullanmadan, süreçlerin birbirlerini bloke etmeden, tutarlı bir snapshot yaratmaya olanak sağlamasıdır.

Kaynaklar