İçeriğe geç

Yazma quorum'una göre okuma quorum'u

Kolay#quorum#pigeonhole~10 dk

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

Hedef zaman
O(1)
Hedef alan
O(1)

Kodda değil de fikirde mi takıldın? Tutarlılık ve CAP bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case