İçeriğe atla

Key-Value Store Sistem Tasarımı: Bölümleme, Replikasyon ve Quorum

Dynamo tarzı bir key-value store tasarlayın: hash ring, replikasyon, R + W > N quorum, çakışma çözümü, hinted handoff, gossip ve LSM motoru.

· Kurucu ve geliştirici

Yayımlandı:

A'dan F'ye altı sunucu bir ring üzerinde; k anahtarı A'dan hemen önce hash'lenir. Sepet servisi A'ya put(k, ctx, v) gönderir, A da B'ye (ack) ve C'ye (kapalı) replike eder. Kesikli hinted write D'ye gider, D sonra C'ye verir. Paneller: N = 3, W = 2, R = 2 ve LSM yazma yolu.

Sepet servisiniz her tıklamada yazma yapıyor ve Aralık ayında tek bir sepete ekleme isteğini bile reddedemez. Yoğun dönemde bir disk bozulacak, bir rack switch'i kararsız çalışacak, belki bir veri merkezi ağdan düşecek. Tek bir birincil veritabanı bunların her birini kesintiye çevirir.

Amazon'un 2007 tarihli Dynamo makalesi, tüm bunlar yaşanırken bile yazma kabul etmeyi sürdüren bir store'u anlattı; Cassandra ve Riak KV kümeleme fikirlerinin çoğunu ondan aldı. Bu yazı Dynamo tarzı bir store'u API'den depolama motoruna kadar tasarlıyor, gerçek sistemleri karşılaştırıyor ve sonucu çiziyor.

Gereksinimler ve API

Dynamo'nun arayüzü iki işlemden oluşur:

get(key)                 -> [value, ...], context
put(key, context, value) -> ok

get çakışan sürümleri ve opak bir context döndürebilir; sonraki put bu context'i geri göndererek hangi sürümleri değiştirdiğini belirtir. Gereksinimler:

  • Her zaman yazılabilir, düğümler veya bağlantılar kapalı olsa bile.
  • Öngörülebilir kuyruk gecikmesi. Makalenin örnek SLA'sı, saniyede 500 isteklik tepe yükte isteklerin %99,9'u için 300 ms'dir.
  • Küçük değerler, tek anahtarlar: nesneler genellikle 1 MB'ın altındadır, birden çok anahtarı kapsayan işlem yoktur.
  • Artımlı ölçekleme, her seferinde bir düğüm.

Boyutlandırma, 1 KB'lık değerler ve compaction için boş alan payı bırakan yarı dolu diskler varsayımıyla: 1 milyar anahtar 1 TB eder, üç kopyayla 3 TB; yani diyagramdaki ring gibi altı adet 1 TB'lık düğüm gerekir. Saniyede 30.000 yazmada üç kopya 90.000 replika yazması, yani düğüm başına 15.000 yazma demektir.

CAP ve PACELC kısaca

CAP, ağ bölünmesi sırasında bir store'un bazı istekleri reddetmesi veya bayat okuma riskini göze alması gerektiğini söyler; Dynamo erişilebilir kalır. Daniel Abadi'nin PACELC'i (2012) bölünme yokken bile gecikme ile tutarlılık arasında bir takas yaptığınızı ekler; Abadi, Dynamo, Cassandra ve Riak'ın varsayılan yapılandırmalarını PA/EL olarak sınıflandırır.

Hash ring ve sanal düğümlerle bölümleme

Dynamo her anahtarı MD5 ile ring üzerinde 128 bitlik bir konuma hash'ler ve anahtar saat yönündeki ilk düğüme aittir. Bir düğüm katıldığında veya ayrıldığında, hash(key) % N yaklaşımındaki gibi neredeyse tüm anahtarlar yerine yalnızca komşu aralıklar taşınır; consistent hashing diyagramı bunu gösterir.

Düğüm başına tek konum veriyi dengesiz dağıtır, bu yüzden her düğüm sanal düğüm veya token denen çok sayıda konum alır. Cassandra 5.0 düğüm başına 16 token ile gelir; Riak'ın ring'i varsayılan olarak 64 partition içerir. Aralık taramalarından vazgeçersiniz: komşu anahtarlar farklı düğümlere düşer, veritabanı sharding diyagramı bunu açıklar.

Replikasyon ve tercih listeleri

Her anahtar N düğümde yaşar: koordinatör (saat yönündeki ilk düğüm) ve sonraki N − 1 farklı fiziksel düğüm. Anahtarın tercih listesi bunların ötesinde de devam eder, böylece bir replika kapalıyken yedek düğümler vardır. Replikaları hata alanlarına yayın: Dynamo her listeyi veri merkezlerine yaydı, Cassandra'nın NetworkTopologyStrategy'si ise rack'lere yayar. Veritabanı replikasyonu diyagramındaki lider tabanlı kurulumların aksine, her replika yazma kabul eder.

Quorum: R + W > N

Koordinatör her yazmayı N replikanın hepsine gönderir ve W onaydan sonra yanıt verir; bir okuma R yanıttan sonra yanıt verir. R + W > N ise, herhangi bir okuma kümesi ve onaylanmış herhangi bir yazma kümesi en az bir düğümü paylaşır.

N, R, W R + W > N Ne elde edersiniz Neye mal olur
3, 2, 2 Evet Okumalar onaylanmış son yazmayı görür; bir replika arızalanabilir Her istek en hızlı ikinci yanıtı bekler
3, 1, 3 Evet Herhangi bir replikadan hızlı okuma Yazmalar üçünü de bekler
3, 1, 1 Hayır En düşük gecikme, en yüksek erişilebilirlik Okumalar bayat olabilir
5, 3, 3 Evet İki replika arızalanabilir Her değerin beş kopyası

Dynamo makalesinin yaygın yapılandırması (3, 2, 2) idi; ürün kataloğu gibi okuma ağırlıklı servisler R = 1, W = N kullandı. Cassandra istek başına, ONE'dan ALL'a kadar bir consistency level belirler; okuma ve yazmada QUORUM kullanmak R + W > N sağlar.

Örtüşme linearizability değildir. Tek bir replikaya ulaşıp sonra başarısız olan bir yazma bir okumada görünüp sonrakinde kaybolabilir; Cassandra'nın varsayılan bloklayan read repair'i quorum okumalarında bunu önler. Compare-and-set konsensüs ister: Cassandra'nın lightweight transaction'larında veya Raft tabanlı bir store'da olduğu gibi.

Çakışmalar: last write wins, vector clock veya CRDT

Farklı replikalardan gelen eşzamanlı yazmalar iki sürüm bırakır. Üç çıkış yolu var:

Strateji Nasıl çözer Güncelleme kaybedebilir mi? Kullananlar
Last write wins En yüksek zaman damgası kazanır Evet, sessizce; kazananı saat sapması seçer Cassandra, DynamoDB global tables, yapılandırılırsa Riak
Vector clock Eşzamanlı sürümleri tutar; istemci birleştirir Hayır, ama her istemci birleştirmek zorunda Dynamo, Riak (dotted version vectors)
CRDT Birleştirmeleri her zaman yakınsayan veri tipleri Hayır, desteklenen tipler için Riak counter'ları, set'leri ve map'leri

Vector clock, (düğüm, sayaç) çiftlerinden oluşan bir listedir. Tüm sayaçları diğerinin sayaçlarından küçük veya eşit olan sürüm atadır ve silinebilir; aksi halde ikisi de tutulur. Sepet servisi çakışan sepetleri birleştirdi, bu yüzden eklenen ürünler asla kaybolmadı, ancak silinenler geri gelebildi. Çakışmalar nadirdi: 24 saat boyunca sepet isteklerinin %99,94'ü tam olarak tek bir sürüm gördü. CRDT'ler birleştirmeyi veri tipinin kendisine taşır; CRDT tabanlı ortak düzenleme editörleri aynı fikri paylaşılan metne uygular.

Hata yönetimi: hinted handoff, repair ve gossip

Sloppy quorum ve hinted handoff. Dynamo, tercih listesindeki ilk N sağlıklı düğümü kullanır: C kapalıysa D, C'nin kopyasını bir ipucuyla alır ve C düzeldiğinde geri verir. Yazmalar çalışmaya devam eder, ancak B ve düzelmiş C'den yapılan bir okuma, yalnızca A ve D'nin onayladığı bir yazmayı kaçırabilir. Cassandra quorum'ları katı tutar: hint'ler yalnızca ANY seviyesinde consistency level'a sayılır ve bir düğüm 3 saat kapalı kaldıktan sonra durur (max_hint_window).

Read repair ve anti-entropy. Yanıtlar çeliştiğinde koordinatör en yeni sürümü bayat replikalara geri yazar. Soğuk veri için replikalar her anahtar aralığının Merkle ağaçlarını karşılaştırır ve yalnızca farklı olan aralıkları senkronlar. Cassandra'nın dokümanları her düğümde en az 7 günde bir nodetool repair çalıştırmayı önerir: tombstone'lar gc_grace_seconds sonra (varsayılan 10 gün) temizlenir ve onarılmamış bir replika silinmiş veriyi geri getirebilir.

Gossip ve hata tespiti. Her düğüm saniyede bir, rastgele bir eşle üyelik ve token durumunu değiş tokuş eder; herkesin bildiği seed düğümler ring'in bölünmesini önler. Cassandra'nın phi accrual dedektörü, şüphe phi_convict_threshold değerini (varsayılan 8) aştığında bir eşi kapalı işaretler.

Yazma yolu: commit log, memtable, SSTable'lar

Cassandra'nın depolama motoru yazma için optimize edilmiş bir log-structured merge (LSM) tree'dir:

  1. Yazmayı commit log'a ekleyin. Varsayılan olarak (periodic) Cassandra hemen onaylar ve her 10 saniyede bir senkronlar; bu yüzden bir çökme o pencereyi kaybettirebilir.
  2. Yazmayı, bellekte sıralı bir yapı olan memtable'a ekleyin.
  3. Dolan bir memtable'ı diskte değiştirilemez, sıralı bir SSTable'a flush edin.
  4. SSTable'ları arka planda compact edin; en yeni sürümleri tutun, süresi dolmuş tombstone'ları atın.

Okumalar önce memtable'a, sonra SSTable'lara bakar; her SSTable için bir Bloom filter, anahtarı içeremeyecek dosyaları atlar: anahtar başına 10 bit ve 7 hash fonksiyonuyla yanlış pozitif oranı (1 − e^(−0,7))^7, yani yaklaşık %0,8'dir. Size-tiered compaction varsayılandır; Cassandra 5.0 yeni iş yükleri için unified stratejisini önerir.

Gerçek sistemler ve makale

Dynamo (2007) Amazon DynamoDB Cassandra 5.0 Riak KV
Bölümleme MD5 ring, eşit partition'lar Boyuta veya trafiğe göre bölünen aralıklar Murmur3 ring, düğüm başına 16 token 160 bitlik ring, 64 partition
Replikasyon Lidersiz, anahtar başına N AZ'lere yayılmış 3 replika, Multi-Paxos lideri Lidersiz, veri merkezi başına Lidersiz, n_val 3
Tutarlılık Sloppy quorum Varsayılan olarak eventual; güçlü okumalar liderden İstek başına consistency level Sloppy quorum, pr ve pw
Çakışmalar Vector clock'lar Lider yazmaları sıralar; Region'lar arasında son yazan kazanır Last write wins Sibling'ler veya CRDT'ler
Depolama Berkeley DB, MySQL B-tree artı write-ahead log LSM tree Bitcask, LevelDB

DynamoDB adı paylaşır, tasarımı değil: 2022 USENIX makalesine göre partition lideri, üç replikadan ikisi yazmayı log'ladığında yazmayı onaylar. Global tables varsayılan olarak Region'lar arasında last writer wins kullanır; yazının hazırlandığı sırada (Kasım 2026) tam olarak üç Region'da çok Region'lı güçlü tutarlılık de sunarlar.

Dynamo tarzı key-value store diyagramı

A'dan F'ye altı sunucu bir ring üzerinde; k anahtarı A'dan hemen önce hash'lenir. Sepet servisi A'ya put(k, ctx, v) gönderir, A da B'ye (ack) ve C'ye (kapalı) replike eder. Kesikli hinted write D'ye gider, D sonra C'ye verir. Paneller: N = 3, W = 2, R = 2 ve LSM yazma yolu.

21 bileşen · 8 bağlantı

Archboard'da aç
Diyagram içeriği
  • Node B
  • Node A
  • Node C
  • Node F
  • Node D
  • Node E
  • Cart service
  • Inside every node: LSM write path
  • Commit log
  • Memtable
  • SSTables
  • put(k, ctx, v)
  • replica 2: ack
  • replica 3: no reply
  • hinted write for C: ack
  • hand off when C recovers
  • then insert
  • flush when full
  • gossip
k anahtarı altı düğümlü ring üzerinde bir noktaya hash'lenir. Node A put işlemini koordine eder ve B ile C'ye replike eder. C kapalıdır, bu yüzden D ipuçlu bir kopya tutar ve sonra geri verir. Yan paneller N, R, W değerlerini ve her düğümdeki yazma yolunu listeler.

Nasıl okunur:

  • Ring. Nokta olan hash(k)'den saat yönünde yürümek, A'dan F'ye tercih listesini verir.
  • Yazma. Sepet servisi put(k, ctx, v) isteğini koordinatör A'ya gönderir, A da B ve C'ye replike eder.
  • Hata. C kapalıdır, bu yüzden D, C'nin kopyasını bir ipucuyla alır (kesikli kehribar rengi) ve sonra geri verir. W = 2 olduğundan put, A ve B'de olduğunda döner.
  • Gossip (noktalı) rastgele düğüm çiftleri arasında çalışır.
  • Paneller N, R, W değerlerini ve her düğümün yazma yolunu listeler.

Key-value store diyagramlarını net çizmek

  • Tek bir anahtarı takip edin. Hash'ini işaretleyin, tercih listesini yazın ve yanına N, R ve W değerlerini koyun; anahtarsız bir ring hiçbir şey açıklamaz.
  • Hatayı çizin. Kırmızı bir node ve kesikli bir yedek bağlantı, sloppy quorum'u düz metinden daha hızlı açıklar.
  • Hata alanlarını gösterin: replikaları rack veya zone'a göre renklendirin, böylece gözden geçirenler hiçbir iki kopyanın aynı alanı paylaşmadığını kontrol edebilir.
  • Düğüm iç yapısını tek bir ek kutuya bırakın. Önce küme gelir.

Sık yapılan bir hata: istemciden her replikaya oklar çizip koordinatör göstermemek; bu, bir yazmanın başarılı olduğuna kimin karar verdiğini gizler. Adım adım sistem tasarımı yöntemi yerleşimi ve sayıları ele alır.

Archboard'da oluşturun

  1. Google veya GitHub ile giriş yapın ve bir diyagram oluşturun.
  2. Token ring'i için Temel pack'inden büyük gri bir Elips ekleyin.
  3. Ring üzerine Ağ pack'inden altı Sunucu node'u yerleştirin, saat yönünde Node A'dan Node F'ye. A ve B'yi yeşil, C'yi kırmızı, D'yi kehribar renginde boyayın ve rollerini Temel Metin notlarıyla etiketleyin.
  4. Ring üzerinde Node A'dan hemen önce, hash(k) için küçük bir Elips ekleyin ve bir Metin etiketi koyun.
  5. Sepet servisi için C4 Modeli pack'inden bir Container ekleyin ve Node A'ya put(k, ctx, v) bağlantısı çizin.
  6. Bağlantıları çizin: A'dan B'ye düz yeşil, A'dan C'ye çarpı ok uçlu kesikli kırmızı, A'dan D'ye ve D'den C'ye kesikli kehribar (hinted write, sonra handoff) ve F ile E arasına bir Metin notuyla noktalı gossip bağlantısı.
  7. Temel pack'inden N, R, W değerlerini ve senaryoyu içeren bir Markdown bloğu ekleyin.
  8. Temel pack'inden bir Çerçeve ekleyin; içine C4 Modeli pack'inden üç Component node'u koyun: Commit log, Memtable ve SSTables, yukarıdan aşağıya bağlı, ayrıca Bloom filter'lar için bir Metin notu.

Örnek 14 diagram node kullanıyor ve Free planın sınırları içinde kalıyor.

SSS

Dağıtık bir key-value store nasıl tasarlanır? Consistent hashing ile bölümleyin, her anahtarı N düğüme replike edin, R ve W değerlerini ayarlayın, bir çakışma stratejisi seçin, hinted handoff ve anti-entropy repair ekleyin ve her düğümde bir LSM tree çalıştırın.

R + W > N ne demek? N replikadan, bir yazma W tanesini, bir okuma R tanesini bekler. R + W, N'yi aşarsa her okuma, onaylanmış son yazmayı tutan en az bir replikaya ulaşır.

DynamoDB, Dynamo makalesine mi dayanıyor? Yalnızca kısmen: her partition'ın üç replikası, bir Multi-Paxos lideri ve B-tree depolaması vardır; sloppy quorum ve vector clock'lar yoktur.

Hinted handoff nedir? Başka bir düğüm, erişilemeyen bir replikanın yazmasını bir ipucuyla saklar ve replika döndüğünde teslim eder. Cassandra varsayılan olarak 3 saatlik kesintiden sonra bir düğüm için hint saklamayı bırakır.

Last write wins mi, vector clock mı kullanmalıyım? Last write wins, eşzamanlı bir güncellemenin kaybı kabul edilebilir olan veriler için uygundur; örneğin oturumlar. Sepetler ve sayaçlar gibi her güncelleme önemliyse vector clock veya CRDT kullanın.

Ücretsiz başlayın — tek kullanıcı, kredi kartı gerekmez.

İlgili yazılar

← Blog'a dön

Bir dakikada canvas açın

Google veya GitHub ile giriş yapın. Tek koltuk ücretsiz; ekip katılınca planı yükseltin.