IAli
Tüm Yazılar
Önbellek İzdihamı ve XFetch Probabilistik Erken Yenileme Algoritması

Önbellek İzdihamı ve XFetch Probabilistik Erken Yenileme Algoritması

Önbellek izdihamı (cache stampede) krizlerini önleyen XFetch olasılıksal erken yenileme algoritması ve tekil uçuş (singleflight) desen analizi.

Yüksek eşzamanlı sistemlerde bir önbellek anahtarının yaşam süresi (TTL) sona erdiği an, sistemin en kırılgan anıdır. Bir e-ticaret platformunun ana sayfa vitrini veya popüler bir ürünün stok bilgisi saniyede binlerce istek alırken bu anahtarın süresi dolarsa, gelen tüm istekler aynı milisaniyede önbelleği ıskalar (cache miss).

Binlerce eşzamanlı iş parçacığı aynı anda arka uç veritabanına hücum eder. Bu duruma Önbellek İzdihamı (Cache Stampede veya Thundering Herd) adı verilir. Veritabanı bağlantı havuzu saniyeler içinde tükenir, CPU kullanımı tavana vurur, yanıt süreleri uzar ve zincirleme bir çöküş dalgası tüm mimariyi felç eder.

Bu felaketi engellemek için geleneksel kilit yaklaşımları denenmiş ancak kendi kilitlenme açmazlarını üretmiştir. Modern mühendislik bu sorunu iki zarif yöntemle çözer: Süreç içi tekil uçuş (singleflight) ve olasılıksal erken yenileme (XFetch) algoritması.

1. İzdiham Anatomisi ve Dağıtık Kilitlerin Eksikleri

Önbellek izdihamı tipik olarak şu adımlarla gelişir:

TEXT
ÖNBELLEK İZDİHAMI (CACHE STAMPEDE):
İstek 1  ---+
İstek 2  ---+---> [Önbellek (TTL Doldu!)] ---> [Veritabanı] (10.000 Sorgu!)
İstek 3  ---+                                        |
İstek N  ---+                                (CPU %100, Havuz Doldu, ÇÖKÜŞ)

Geliştiricilerin ilk çözümü anahtar süresi dolduğunda veritabanına gitmeden önce dağıtık bir kilit (örneğin Redis SETNX) edinmektir:

  • Kilit alan şanslı tek bir iş parçacığı veritabanına gider, veriyi okur ve önbelleği tazeler.
  • Kilit alamayan diğer tüm iş parçacıkları bekler veya döngüye girer.

Kağıt üzerinde mantıklı görünen bu kilit çözümü sahada ciddi arızalar doğurur:

  1. Kilit Çekişmesi: Kilit alamayan binlerce istek CPU harcayarak spin-lock döngüsüne girer ve Redis üzerinde yoğun bir komut yükü yaratır.
  2. Kilit Çöküşü: Veritabanına giden iş parçacığı ağ gecikmesi veya OOM nedeniyle çökerse, kilit zaman aşımına (lease timeout) uğrayana kadar tüm sistem durur.
  3. Kuyruk Şişmesi: Bekleyen tüm HTTP bağlantıları açık kalır, API ağ geçidi (API Gateway) iş parçacıkları tükenir.

Bu sorun Önbellek Mimarisi: Cache-Aside, Write-Through ve Çift Yazma Çıkmazı yazımızda incelediğimiz gecikme dalgalanmalarını katlar.

2. Süreç İçi Tekilleştirme: Go singleflight Deseni

Tek bir uygulama sunucusu içinde aynı anda gelen eşzamanlı istekleri tekilleştirmenin en hafif yolu Go dilindeki singleflight paketidir.

singleflight.Group, aynı anahtar için devam eden (in-flight) bir çağrı varsa, gelen diğer tüm goroutine çağrılarını o ilk çağrının sonucuna bağlar. İlk çağrı tamamlandığında sonuç tüm bekleyenlere aynı anda dağıtılır. Veritabanına o sunucu üzerinden yalnızca tek bir sorgu gider.

Go
package cache

import (
	"context"
	"time"

	"golang.org/x/sync/singleflight"
)

type StampedeShield struct {
	group singleflight.Group
}

func (s *StampedeShield) Fetch(ctx context.Context, key string, queryDB func() (any, error)) (any, error) {
	// 1. Once hizlica onbellegi kontrol et
	if val, ok := getFromCache(key); ok {
		return val, nil
	}

	// 2. Onbellekte yoksa ayni dugumdeki diger istekleri tekil ucus altinda birlestir
	res, err, _ := s.group.Do(key, func() (any, error) {
		// Cift kontrol (Double-check)
		if val, ok := getFromCache(key); ok {
			return val, nil
		}

		// Veritabanina tek bir istek gonderilir
		data, err := queryDB()
		if err != nil {
			return nil, err
		}

		saveToCache(key, data, 5*time.Minute)
		return data, nil
	})

	return res, err
}

Bu mekanizma Go Çalışma Zamanı Goroutine Zamanlayıcı yapısıyla uyumlu çalışarak tek bir düğüm içindeki izdihamı sıfırlar. Ancak 50 düğümlü bir kümede her düğüm yine de veritabanına birer istek atacaktır. Küme genelinde tam koruma için algoritmik bir yaklaşım gerekir.

3. XFetch: Olasılıksal Erken Yenileme Algoritması

VLDB 2015 konferansında Babak Vattani ve ekibi tarafından sunulan Optimal Probabilistic Cache Regeneration (XFetch) algoritması, önbellek izdihamını kökünden çözen matematiksel bir model sunar.

Fikir basittir. Anahtarın süresinin TAMAMEN dolmasını beklemek yerine, anahtarın süresi dolmaya yaklaştıkça artan bir olasılıkla arka planda erken yenileme (early recomputation) tetiklenir. İstek trafiği ne kadar yoğunsa, erken yenilemenin tetiklenme olasılığı o kadar erkene çekilir.

Algoritmanın matematiksel karar formülü şudur:

TEXT
XFETCH FORMÜLÜ:
- (beta * delta * ln(random())) > (expiry - now)

Burada:

  • delta: Veritabanından veriyi hesaplayıp getirmenin geçen seferki süresi (saniye cinsinden).
  • beta: Algoritmanın agresiflik katsayısı (varsayılan değer genellikle 1.0 seçilir, 1.0 üstü değerler daha erken yeniler).
  • random(): 0.0 ile 1.0 arasında düzgün dağılımlı (uniform) rastgele bir sayı.
  • expiry: Anahtarın resmi bitiş zaman damgası.
  • now: Mevcut zaman damgası.
TEXT
XFETCH KARAR MANTIĞI:
[Anahtar Yeni] -----------------> [Erken Pencere] ------> [TTL Bitti]
(random() tetiklenmez)          (Trafik arttıkça        (Asla buraya düşmez!)
                                 yenileme olasılığı %100)

Trafik çok düşükse random() çekilişleri formülü sağlamaz ve anahtar normal TTL süresine kadar bellekte kalır. Trafik saniyede binlerce isteğe çıktığında ise bu matematiksel çekilişlerden biri mutlaka doğru çıkar. Şanslı gelen İLK istek eski veriyi istemciye dönerken arka planda veritabanına gidip önbelleği sessizce yeniler.

Böylece anahtarın süresi resmi olarak HİÇBİR ZAMAN dolmaz. İzdiham daha oluşmadan engellenir.

4. XFetch Algoritmasının Go ile Uygulanması

Aşağıda üretim ortamında kullanılabilecek tam bir XFetch sarmalayıcısı yer almaktadır:

Go
package xfetch

import (
	"context"
	"math"
	"math/rand"
	"time"
)

type CachedItem struct {
	Value     string
	Delta     float64 // Hesaplama suresi (saniye)
	ExpiresAt time.Time
}

func ShouldRefresh(item CachedItem, beta float64) bool {
	now := time.Now()
	// Resmi sure dolmussa zaten yenilenmeli
	if now.After(item.ExpiresAt) {
		return true
	}

	// 0 ile 1 arasinda rastgele sayi
	r := rand.Float64()
	if r <= 0.0 {
		r = 0.0001
	}

	// XFetch olasilik kontrolu
	remainingSeconds := item.ExpiresAt.Sub(now).Seconds()
	threshold := -1.0 * (beta * item.Delta * math.Log(r))

	return threshold > remainingSeconds
}

func GetWithXFetch(ctx context.Context, key string, beta float64, fetchFromDB func() (string, time.Duration, error)) (string, error) {
	item, found := readFromRedis(key)

	if !found || ShouldRefresh(item, beta) {
		// Arka planda veya istek aninda yenile
		start := time.Now()
		val, ttl, err := fetchFromDB()
		if err != nil {
			// Veritabani hatasinda eger eski veri varsa onu donerek sistemi koru
			if found {
				return item.Value, nil
			}
			return "", err
		}
		delta := time.Since(start).Seconds()

		newItem := CachedItem{
			Value:     val,
			Delta:     delta,
			ExpiresAt: time.Now().Add(ttl),
		}
		writeToRedis(key, newItem)
		return val, nil
	}

	return item.Value, nil
}

func readFromRedis(key string) (CachedItem, bool) { return CachedItem{}, false }
func writeToRedis(key string, item CachedItem)    {}

5. Üretim Mimarisi İçin Pratik Kararlar

XFetch algoritmasının başarılı çalışması için delta değerinin doğru ölçülmesi gerekir. Veritabanı sorgusu 200 milisaniye sürüyorsa delta = 0.2 olarak anahtarın yanında saklanmalıdır.

Yüksek hacimli anahtarlar için:

  • beta = 1.0 dengeli bir koruma sağlar.
  • Çok ağır hesaplama gerektiren (örneğin 3 saniye süren) raporlama sorgularında beta = 1.5 yapılarak pencere genişletilebilir.
  • Tekil bir sunucu içinde singleflight, küme seviyesinde ise XFetch bir arada kullanıldığında önbellek izdihamı riski tamamen kontrol altına alınır.

Yazıyı Değerlendir

0 tepki

Fikirlerinizi tek tıkla paylaşarak geri bildirim bırakın.

Bu teknik notu çevrenizle paylaşın

Ali Purtaş

@alipurtas • Hey, This is Ali!

İletişime Geç

Kendi halinde yazılım geliştiren bir öğrenci. Sistemler kuruyor, deniyor, bozuyor ve öğrendiği gerçek çözümleri burada belgeliyor.

Konu Kümesi & Önerilen Yazılar

İç Bağlantılı Mimari
Yorumlar yükleniyor...