Dağıtık cache ve key-value store

Problem

"Şirketteki onlarca servisin kullanacağı, Memcached veya Redis Cluster benzeri dağıtık bir bellek içi cache tasarla: get, set (TTL ile), delete. Yatayda ölçeklenmeli, bir node düşünce servis vermeye devam etmeli. Sonrasında aynı tasarımı kalıcı bir key-value store'a (Dynamo benzeri) nasıl genişleteceğini tartışalım."

Bu soru iki katmanlıdır. Birinci katman dağıtık sistemin iskeleti: veriyi node'lara nasıl bölersin (consistent hashing), node eklenince ne taşınır, istemci doğru node'u nasıl bulur, replikasyon ve failover. İkinci katman cache'e özgü zorluklar: bellek dolunca ne silinir, popüler bir anahtarın süresi dolunca veritabanına binlerce istek gitmesi (stampede), sıcak anahtar ve cache ile veritabanı arasındaki tutarsızlık. Mülakatçı adayın bu iki katmanı birbirinden ayırıp ayırmadığına ve "cache" ile "veri deposu" arasındaki farkı (kayıp kabul edilir mi?) netleştirip netleştirmediğine bakar.

Kitap Bölüm 11'de cache-aside, TTL, eviction, invalidation ve stampede'in temelleri anlatıldı. Bu case o temelleri bir sistem olarak birleştirir.

Netleştirme soruları ve varsayımlar

Kapasite tahmini

Bellek:
  sıcak veri 2 TB (anahtar + değer + öğe başına ~50-100 B yönetim yükü dahil)
  node: 64 GB RAM, veri için kullanılabilir ~45 GB
        (parçalanma, replikasyon tamponları, fork/snapshot ve büyüme payı için ~%30 boşluk)
  2.000 GB / 45 GB ≈ 45 primary
  1 replika ile                 ≈ 90 node

İşlem:
  (2.000.000 + 200.000) / 45    ≈ 49.000 işlem/s/primary   -> tek thread'li bir motor için rahat
Bant genişliği:
  okuma 2.000.000 x 1 KB        ≈ 2 GB/s toplam, node başına ≈ 44 MB/s ≈ 350 Mbit/s

Sıcak anahtar örneği:
  tek bir kampanya anahtarı toplam okumanın %5'ini alırsa = 100.000 okuma/s tek node'a
  -> o node ortalamanın ~3 katı yük alır (49.000'e ek 100.000)

Teşhis:

• Node sayısını bellek belirler, işlem hızı değil. 45 primary işlem açısından fazlasıyla yeterli; bu yüzden bellek verimliliği (değer sıkıştırma, gereksiz alanları cache'lememek, doğru eviction) doğrudan maliyettir.
• Ortalama yük sorun değil; çarpıklık sorun. Tek bir sıcak anahtar bir node'u ortalamanın katlarına çıkarır. Tasarımın büyük bir kısmı hot key ve stampede gibi çarpıklık problemleriyle ilgilidir.

API

get(key)                         -> value | MISS
mget(keys[])                     -> map
set(key, value, ttlSeconds)      -> OK
set(key, value, ttl, NX | XX)    -> OK | NOT_STORED      (yoksa yaz / varsa yaz)
cas(key, value, expectedVersion) -> OK | CONFLICT        (compare-and-set)
delete(key)                      -> OK
incr(key, delta)                 -> newValue

• Anahtarlar kiracı önekiyle isim alanına ayrılır: catalog:product:v3:123. Önekteki v3 şema versiyonudur; nesnenin biçimi değişince eski ve yeni pod'lar aynı anahtarda çakışmaz.
• NX ve cas, stampede koruması ve kilitler için gereken atomik ilkelerdir.
• mget aynı node'daki anahtarları tek çağrıda toplar; farklı node'lara düşenleri istemci paralel çağırır.

Veri modeli

Bir node içinde her öğe:

key        : byte dizisi (en fazla birkaç yüz byte)
value      : byte dizisi (tavsiye edilen üst sınır ~100 KB; büyük değerler parçalanır veya cache'lenmez)
expires_at : mutlak süre sonu
version    : cas için artan sayı
lru/lfu    : eviction için erişim bilgisi (birkaç bit)

Küme seviyesinde:

topology:
  slot (0..16383) -> shard id
  shard id        -> { primary: node-a, replicas: [node-b] }
  epoch           : topoloji her değiştiğinde artar

Topoloji küçüktür ve nadiren değişir; bir yapılandırma servisinde (ya da Redis Cluster'daki gibi node'ların gossip ile paylaştığı durumda) tutulur, istemciler kendi kopyasını taşır.

Yüksek seviye tasarım

flowchart LR
    S1[Servis A ve akıllı istemci] --> N1[Shard 1 primary]
    S1 --> N2[Shard 2 primary]
    S2[Servis B ve akıllı istemci] --> N2
    S2 --> N3[Shard 3 primary]
    N1 -->|asenkron replikasyon| R1[Shard 1 replika]
    N2 -->|asenkron replikasyon| R2[Shard 2 replika]
    N3 -->|asenkron replikasyon| R3[Shard 3 replika]
    CFG[Topoloji ve failover koordinatörü] --> N1
    CFG --> N2
    CFG --> N3
    CFG -->|topoloji güncellemesi| S1
    CFG -->|topoloji güncellemesi| S2
    S1 -.->|MISS| DB[(Doğruluk kaynağı veritabanı)]

• Akıllı istemci: Anahtarın slot'unu kendisi hesaplar ve doğrudan doğru primary'ye gider; ara bir proxy yoktur, gecikme tek gidiş-dönüştür. Topoloji eskiyse node "bu slot artık şurada" diye yönlendirme cevabı döner (Redis Cluster'da MOVED/ASK), istemci topolojisini yeniler.
• Alternatif, proxy katmanı: İstemciler bir proxy'ye (mcrouter, Envoy, twemproxy benzeri) konuşur. Dil bağımsızlık, bağlantı sayısını azaltma ve merkezi yönlendirme kuralları kazandırır; bedeli ek bir gidiş-dönüş ve ek bir katman.
• Failover koordinatörü: Primary'lerin sağlığını izler, düşeni replikayla değiştirir ve epoch'u artırır. Bölünmüş beyin (split brain) riskine karşı karar çoğunluk oyuyla verilir.

Derinlemesine

Veriyi bölmek: modulo, consistent hashing, sabit slot

Modulo (hash(key) % N): Basit, ama node sayısı değişince neredeyse her anahtarın yeri değişir. 200.000 anahtarlık bir simülasyonda 10 node'dan 11'e çıkınca anahtarların %90,7'sinin node'u değişti. Cache için bu, ölçekleme anında isabet oranının neredeyse sıfıra düşmesi ve bütün yükün veritabanına binmesi demektir.

Consistent hashing: Node'lar ve anahtarlar aynı hash halkasına yerleşir; anahtar, halkada saat yönünde karşılaştığı ilk node'a aittir. Node eklenince sadece yeni node'un "önündeki" aralık taşınır. Aynı simülasyonda 10 node'dan 11'e çıkınca anahtarların %8,2'si taşındı (ideal 1/11 ≈ %9,1).

Her node'u halkaya tek nokta olarak koymak yükü çok dengesiz dağıtır; çözüm sanal node'lar: her fiziksel node halkada yüzlerce noktaya sahip olur. Simülasyon (10 node, 200.000 anahtar):

Sanal node'ların ikinci faydası: bir node düştüğünde onun aralıkları tek bir komşuya değil, halkadaki birçok node'a dağılır; yük tek bir node'a yığılmaz. Farklı kapasiteli makinelere farklı sayıda sanal node vererek ağırlıklandırma da yapılabilir.

Sabit sayıda slot: Redis Cluster aynı problemi farklı çözer: anahtar uzayı 16.384 hash slot'a bölünür (CRC16(key) mod 16384), slot'lar node'lara atanır. Node eklemek, bazı slot'ları yeni node'a taşımaktır. Avantajı açık ve yönetilebilir bir eşlemedir (hangi slot nerede, tek tabloda). Couchbase'in vBucket'ları da aynı fikirdir. Ayrıca hash tag: anahtarda {...} varsa sadece parantez içi hash'lenir, böylece ilgili anahtarlar aynı slot'a düşer ve çok anahtarlı atomik işlemler mümkün olur.

Mülakatta söylenecek cümle: "Node sayısı değiştiğinde taşınan veriyi 1/N ile sınırlamak için ya consistent hashing ve sanal node'lar, ya da sabit sayıda mantıksal parça kullanırım; işletimi kolay olduğu için ikincisini tercih ederim."

Yeniden dengeleme sırasında ne olur?

Bir slot taşınırken anahtarlar iki node arasında bölünmüş durumdadır. Redis Cluster'da kaynak node, taşınmış bir anahtar için ASK yönlendirmesi döner; istemci o tek isteği hedef node'a yollar ama topolojisini henüz değiştirmez. Taşıma bitince MOVED kalıcı yönlendirmedir. Cache için daha basit bir yaklaşım da mümkündür: slot'u taşımak yerine yeni node'u boş başlatmak ve ıskalamaların veritabanından dolmasına izin vermek. Bunun bedeli geçici bir isabet düşüşüdür; bu yüzden node ekleme yoğun saatlerde değil, kademeli yapılır.

Replikasyon ve failover

Her shard'ın bir primary'si ve bir (ya da daha fazla) replikası vardır. Yazmalar primary'ye gider ve replikaya asenkron aktarılır; senkron replikasyon her yazmaya bir gidiş-dönüş ekler ve bir cache için genelde değmez.

Sonuçları bilinçli kabul edilir:

• Failover'da kayıp: Primary bir yazmayı onaylayıp replikaya iletmeden ölürse replika terfi ettiğinde o yazma kaybolur. Redis Cluster spesifikasyonu bunu açıkça gerçek bir arıza modu olarak tanımlar ve onaylanmış yazmaların kaybolmayacağını garanti etmez. Cache için sonuç bir sonraki okumada ıskalama ya da eski değerdir; kaynak veritabanı olduğu sürece kabul edilebilir.
• Bölünme: Ağ bölünmesinde azınlık tarafındaki primary, çoğunlukla belirli bir süre (node timeout) iletişim kuramazsa yazma kabul etmeyi bırakır; bu, kayıp penceresini sınırlar.
• Replikadan okuma: Okuma yükünü dağıtır ama replika geride olabilir; "yazdıktan hemen sonra oku" gereken çağrılar primary'den okur.

Bellek dolunca: eviction ve TTL

• TTL: Süresi dolan anahtarlar hem erişildiğinde (lazy) hem de arka planda periyodik örneklemeyle silinir. TTL, invalidation kaçırıldığında bile bayatlığın üst sınırıdır; cache'teki her anahtarın bir TTL'i olmalıdır.
• Eviction politikası: Bellek sınırına gelince ne silinecek? Redis'te noeviction yazma komutlarını hataya düşürür; bir cache için doğru seçim genelde allkeys-lru veya allkeys-lfu'dur. volatile-* politikaları sadece TTL'li anahtarları siler ve TTL'li anahtar yoksa noeviction gibi davranır.
• Yaklaşık LRU: Kesin LRU her erişimde bir bağlı liste güncellemesi gerektirir. Redis bunun yerine rastgele birkaç anahtar örnekleyip en uzun süredir erişilmeyeni siler (maxmemory-samples, varsayılan 5) ve bir aday havuzu tutar; sonuç gerçek LRU'ya çok yakındır. LFU ise birkaç bitlik olasılıksal bir sayaçla erişim sıklığını tutar ve zamanla azaltır; tek seferlik taramaların (bir batch iş bütün anahtarları bir kez okur) sıcak veriyi cache'ten atmasına karşı LRU'dan dayanıklıdır.
• Kiracı izolasyonu: Tek bir servisin büyük değerleri herkesin sıcak verisini dışarı itebilir. Çözüm: kiracılara ayrı kümeler ya da en azından ayrı bellek kotaları; ve aynı Redis'te hem cache hem de silinmemesi gereken veri (oturum, sepet) tutulmaz, çünkü eviction politikası ikisini ayırt etmez.

Cache stampede: popüler anahtarın süresi dolunca

Saniyede 100.000 kez okunan bir anahtarın TTL'i dolduğu an, aynı milisaniyelerde yüzlerce istek ıskalar ve hepsi veritabanına gider. Önlemler, birbirini tamamlar:

1. Tek yükleyici (single-flight): Aynı pod içinde aynı anahtar için tek bir yükleme yapılır, diğer thread'ler onun sonucunu bekler (Caffeine get(key, loader) bunu sağlar). Pod'lar arası için kısa ömürlü bir kilit: SET lock:{key} <token> NX PX 3000; kilidi alan yükler, diğerleri kısa bekleyip tekrar cache'e bakar ya da eski değeri döner.
2. Bayat değeri sunarken yenilemek (stale-while-revalidate): Değer, gerçek TTL'den önce dolan bir "taze kalma" süresiyle saklanır. Taze süre geçince ilk okuyan arka planda yenilemeyi tetikler, herkes bu arada eski değeri alır.
3. Olasılıksal erken yenileme: Her okuma, süre sonuna yaklaştıkça artan bir olasılıkla değeri erkenden yeniler; yenilemeler zamana yayılır ve tek bir "son saniye" oluşmaz.
4. TTL jitter: Deploy sonrası aynı anda yüklenmiş binlerce anahtarın aynı anda dolmaması için TTL'e rastgele sapma eklenir (cache avalanche).
5. Lease (kira): Facebook'un memcache çalışmasında anlatılan yaklaşım: ıskalayan istemciye kısa ömürlü bir kira belirteci verilir, değeri sadece kira sahibi yazabilir ve kira belirli bir sıklıkla verilir. Bu hem stampede'i hem de "eski değerin geç yazılması" (stale set) problemini hedefler.

Cache ile veritabanı arasındaki tutarsızlık

Cache ve veritabanı arasında transaction yoktur. Varsayılan kurallar (Kitap Bölüm 11): güncellemede cache'i yeni değerle güncelleme, sil; ve silmeyi veritabanı commit'inden sonra yap. Kalan yarış: okuyucu A ıskalar ve eski değeri veritabanından okur; yazıcı B güncelleyip cache'i siler; A eski değeri cache'e yazar ve değer TTL dolana kadar bayat kalır. Hafifletmeler:

• Versiyonlu yazma: Değer bir versiyonla saklanır; cas ile sadece daha yeni versiyon yazılabilir.
• Lease: Silme işlemi bekleyen kirayı geçersiz kılar; A'nın kirası iptal olduğu için eski değeri yazamaz.
• CDC tabanlı invalidation: Veritabanının değişiklik akışını (Debezium gibi) dinleyen bir tüketici ilgili anahtarları siler; uygulamadaki her yazma yolunu hatırlamak gerekmez ve commit sırası garanti olur.
• Kısa TTL: Hepsine rağmen son sigorta.

Hangi verinin cache'lenmeyeceği de bir karardır: stok ve fiyat gibi kararı etkileyen değerler karar anında kaynaktan doğrulanır; listeleme ekranında birkaç saniyelik bayatlık kabul edilir.

Sıcak anahtar

Tek bir anahtar tek bir slot'a, tek bir node'a düşer; o node'un CPU'su ve ağı tavan yapar. Önlemler, ucuzdan pahalıya:

1. İstemci içi L1 cache: Uygulama pod'unda birkaç saniyelik TTL ile yerel kopya. 100.000 okuma/s, 200 pod'a dağılmış ve her pod saniyede bir kez yenilediğinde node'a saniyede 200 istek gider.
2. Replikadan okuma: Sıcak shard'ın okumaları replikalara yayılır.
3. Anahtarı çoğaltmak: hot:key#0..7 gibi N kopya yazılır (hash tag olmadan; {key} kullanılırsa bütün kopyalar aynı slot'a düşer), okuma rastgele bir kopyadan yapılır; yazma N kopyayı günceller.
4. Tespit: Hangi anahtarların sıcak olduğunu bilmeden bunlar uygulanamaz. LFU sayaçları, istemci tarafı örneklenmiş metrikler veya node'da en çok erişilen anahtar istatistikleri izlenir.

Cache'ten kalıcı key-value store'a

Gereksinim "veri kaybı kabul değil" olunca aynı iskelete şunlar eklenir (Dynamo makalesinde anlatılan ve Cassandra gibi sistemlere ilham veren teknikler):

• Kalıcılık: Her yazma önce bir commit log'a (WAL) eklenir, sonra bellekte bir yapıya (memtable); periyodik olarak diske sıralı dosyalar (SSTable) olarak boşaltılır ve arka planda birleştirilir (LSM ağacı).
• Replikasyon faktörü ve quorum: Her anahtar N node'da tutulur. Yazma W node'dan, okuma R node'dan onay bekler. R + W > N ise okuma ve yazma kümeleri en az bir node'da kesişir ve okuma en son onaylanmış yazmayı görür (sıkı quorum). Tipik seçim N=3, R=2, W=2. W=1 yazmayı hızlandırır ama tutarlılığı zayıflatır; bu ayar istek başına da yapılabilir (tunable consistency).
• Geçici arızalar: Asıl replikalardan biri erişilemezse yazma geçici olarak başka bir node'a yazılır ve asıl node dönünce ona iletilir (hinted handoff); bu erişilebilirliği artırır ama sıkı quorum garantisini gevşetir (sloppy quorum).
• Ayrışan replikaları onarmak: Okuma sırasında farklı cevap veren replikalar güncellenir (read repair); arka planda Merkle ağaçlarıyla replikalar karşılaştırılıp farklı aralıklar eşitlenir (anti-entropy).
• Çakışan yazmalar: Aynı anahtara iki replika üzerinden eşzamanlı yazma yapılırsa hangisi kazanır? En basit çözüm son yazan kazanır (last-write-wins, zaman damgasıyla; saat kayması veri kaybettirebilir). Daha güçlüsü sürüm vektörleri (vector clock) ile çakışmayı tespit edip uygulamaya bırakmaktır.
• Üyelik ve arıza tespiti: Node'lar gossip protokolüyle birbirinin durumunu yayar; merkezi bir koordinatör gerekmez.

Bu noktada CAP/PACELC tartışması doğal olarak gelir (Kitap Bölüm 11): bölünme sırasında bu tasarım erişilebilirliği seçer; bölünme yokken de gecikme ile tutarlılık arasında R ve W ayarıyla seçim yapılır.

Darboğazlar, hatalar ve trade-off'lar

Trade-off'lar:

• Asenkron replikasyon: Düşük gecikme karşılığında failover'da veri kaybı (cache için kabul).
• Akıllı istemci ve proxy: Tek gidiş-dönüş karşılığında istemci kütüphanesi karmaşıklığı; proxy ile ek gecikme karşılığında merkezi kontrol.
• LRU ve LFU: LRU yakın zamanı, LFU sıklığı korur; tarama ağırlıklı iş yüklerinde LFU daha dayanıklıdır.
• Quorum ayarı: R ve W büyüdükçe tutarlılık artar, gecikme ve arıza toleransı azalır.

Üç seviyede cevap

Soru: "Cache'e yeni node eklediğimizde ne olur? Veriyi nasıl dağıtırsın?"

Soru: "Popüler bir ürünün cache anahtarının süresi doldu ve veritabanı çöktü. Ne oldu, nasıl önlersin?"

Soru: "Bu cache'i kalıcı bir key-value store'a çevirmek istesek neler değişir?"

Mülakatçı için

Takip soruları:

• Büyük değerler (5 MB'lık JSON) için cache'i nasıl tasarlarsın, yoksa cache'lemez misin?
• Çok bölgeli bir kurulumda cache invalidation nasıl yayılır?
• Cache isabet oranı %95'ten %80'e düştü. Nereden başlarsın?
• LRU'yu O(1) ile tek bir JVM'de nasıl implement edersin? (Kitap Bölüm 19.)

Seviye beklentisi: Mid seviyede consistent hashing, replikasyon, eviction ve stampede'in temel çözümü beklenir. Senior'dan dağıtım ve yeniden dengelemenin sayısal etkisi, replikasyon kaybının bilinçli kabulü, katmanlı stampede çözümü, sıcak anahtar ve KV store'a genişlemede quorum, onarım ve çakışma çözümü beklenir.

Hızlı tekrar

Kaynaklar

• Alex Xu, System Design Interview: An Insider's Guide (Cilt 1): "Design Consistent Hashing" ve "Design a Key-Value Store" bölümleri.
• Martin Kleppmann, Designing Data-Intensive Applications: Bölüm 3 (LSM ağaçları), Bölüm 5 (replikasyon, quorum, sloppy quorum), Bölüm 6 (partitioning).
• DeCandia ve diğerleri, "Dynamo: Amazon's Highly Available Key-value Store", SOSP 2007.
• Nishtala ve diğerleri, "Scaling Memcache at Facebook", NSDI 2013.
• Redis Cluster specification: 16.384 slot, CRC16, hash tag'ler ve asenkron replikasyonda yazma güvenliği.
• Redis: Key eviction: Eviction politikaları, yaklaşık LRU ve LFU parametreleri.