Yazma quorum'una göre okuma quorum'u
Görev tanımı
Problem
Replike edilmiş bir key-value store her anahtarı n replikada tutuyor. Bir yazma w replika onu onayladığında başarılı olur, bir okuma da r replikaya sorar ve gördüğü en yeni sürümü tutar. Bir okuma ancak olası her okuma kümesi (set) olası her yazma kümesiyle en az bir replikayı paylaşıyorsa son başarılı yazmayı görmesi garanti olur. n ve w verildiğinde böyle en küçük r'yi, okumalar da yazmalar da hâlâ başarılı olabilirken kaç replikanın çökmüş olabileceğiyle birlikte döndür.
Örnekler
Input: n = 3, w = 2
Output: (2, 1)
Neden: 3'ün herhangi 2'si 3'ün diğer herhangi 2'siyle örtüşür ve 1 replika kaybedilebilir
Input: n = 5, w = 3
Output: (3, 2)
Input: n = 3, w = 3
Output: (1, 0)
Neden: edge case: her yazma herkese ulaşır, bu yüzden okumak için bir replika yeter, ama hiçbiri çökemez
İpuçları
0 / 3
En kötü durumu düşün: okuma kümesi yazma kümesinden olabildiğince uzun süre kaçınacak şekilde seçiliyor. Yazma kümesinin dışında kaç replika var?
Okuma kümesi tam olarak yazma kümesinin dışındaki her şeyden büyük olduğunda örtüşmeye zorlanır; bu güvercin yuvası ilkesi: r + w > n.
En küçük r, n - w + 1. Okumalar r, yazmalar w replikanın ayakta olmasına ihtiyaç duyar; bu yüzden en fazla n - max(r, w) replika çökükken ikisi de çalışmaya devam eder.
- Hedef zaman
- O(1)
- Hedef alan
- O(1)
Çözüm
Belirli bir yazmanın hiç ulaşmadığı n - w replika vardır; bu yüzden o kadar replikanın okunması yazmayı tamamen kaçırabilir, bir fazlası ise güvercin yuvası ilkesiyle bir örtüşmeyi zorunlu kılar. Bu, en küçük güvenli okuma quorum'unu n - w + 1 yapar; bilinen r + w > n kuralı. Erişilebilirlik (availability) de saymaktan çıkar: bir yazma w canlı replikaya, bir okuma r'ye ihtiyaç duyar; bu yüzden sistem n - max(r, w)'den fazla replika çökmediği sürece ikisine de hizmet etmeye devam eder. w'yi artırmak daha az tolere edilen hata pahasına daha ucuz okumalar alır; örneklerin gösterdiği trade-off da bu. Zaman ve alan O(1).
def quorum_plan(n, w):
r = n - w + 1 # smallest read set that must meet every write set
tolerate = n - max(r, w) # replicas that can be down with both still working
return r, tolerate
print(quorum_plan(3, 2)) # -> (2, 1)
print(quorum_plan(5, 3)) # -> (3, 2)
print(quorum_plan(3, 3)) # -> (1, 0)Kodda değil de fikirde mi takıldın? Tutarlılık ve CAP bunu anlatıyor.