Quórum de leitura dado o de escrita
A missão
Problema
Um armazenamento chave-valor replicado mantém cada chave em n réplicas. Uma escrita tem sucesso quando w réplicas a confirmam, e uma leitura consulta r réplicas e fica com a versão mais nova que encontrar. Uma leitura só tem a garantia de ver a última escrita bem-sucedida se todo conjunto de leitura possível compartilhar pelo menos uma réplica com todo conjunto de escrita possível. Dados n e w, retorne o menor r com essa propriedade, junto com quantas réplicas podem estar fora do ar enquanto leituras e escritas ainda conseguem ter sucesso.
Exemplos
Input: n = 3, w = 2
Output: (2, 1)
Por quê: quaisquer 2 de 3 se sobrepõem a quaisquer outras 2 de 3, e 1 réplica pode ser perdida
Input: n = 5, w = 3
Output: (3, 2)
Input: n = 3, w = 3
Output: (1, 0)
Por quê: edge case: toda escrita chega a todas as réplicas, então uma réplica basta para ler, mas nenhuma pode falhar
Dicas
0 / 3
Imagine o pior caso: o conjunto de leitura é escolhido para evitar o conjunto de escrita pelo maior tempo possível. Quantas réplicas estão fora do conjunto de escrita?
O conjunto de leitura é obrigado a se sobrepor exatamente quando é maior do que tudo o que está fora do conjunto de escrita, que é o princípio da casa dos pombos: r + w > n.
O menor r é n - w + 1. As leituras precisam de r réplicas no ar e as escritas, de w, então as duas continuam funcionando enquanto no máximo n - max(r, w) réplicas estiverem fora do ar.
- Tempo-alvo
- O(1)
- Espaço-alvo
- O(1)
Solução
Há n - w réplicas que uma escrita específica nunca alcançou, então uma leitura desse número de réplicas pode perder a escrita por completo, enquanto uma réplica a mais força uma sobreposição pelo princípio da casa dos pombos. Isso faz do menor quórum de leitura seguro n - w + 1, a conhecida regra r + w > n. A disponibilidade sai de uma contagem: uma escrita precisa de w réplicas vivas e uma leitura, de r, então o sistema continua atendendo as duas enquanto não houver mais do que n - max(r, w) réplicas fora do ar. Aumentar w compra leituras mais baratas ao custo de tolerar menos falhas, que é o trade-off que os exemplos mostram. O tempo e o espaço são 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)Travou na ideia, e não no código? Consistência e teorema CAP explica isso.