Quórum de lectura según el de escritura
La misión
Problema
Un almacén clave-valor replicado guarda cada clave en n réplicas. Una escritura tiene éxito cuando w réplicas la confirman, y una lectura consulta r réplicas y se queda con la versión más nueva que ve. Una lectura tiene garantizado ver la última escritura exitosa solo si todo conjunto de lectura posible comparte al menos una réplica con todo conjunto de escritura posible. Dados n y w, devuelve el menor r que cumple eso, junto con cuántas réplicas pueden estar caídas sin que dejen de funcionar las lecturas ni las escrituras.
Ejemplos
Input: n = 3, w = 2
Output: (2, 1)
Por qué: dos réplicas cualesquiera de 3 se cruzan con otras dos cualesquiera, y se puede perder 1 réplica
Input: n = 5, w = 3
Output: (3, 2)
Input: n = 3, w = 3
Output: (1, 0)
Por qué: caso límite: cada escritura llega a todas, así que basta una réplica para leer, pero ninguna puede fallar
Pistas
0 / 3
Imagina el peor caso: el conjunto de lectura se elige para evitar el conjunto de escritura todo lo posible. ¿Cuántas réplicas quedan fuera del conjunto de escritura?
El conjunto de lectura está obligado a superponerse exactamente cuando es más grande que todo lo que queda fuera del conjunto de escritura, que es el principio del palomar: r + w > n.
El menor r es n - w + 1. Las lecturas necesitan r réplicas activas y las escrituras necesitan w, así que ambas siguen funcionando mientras haya como máximo n - max(r, w) réplicas caídas.
- Tiempo objetivo
- O(1)
- Espacio objetivo
- O(1)
Solución
Hay n - w réplicas a las que una escritura dada nunca llegó, así que una lectura de esa cantidad de réplicas puede no ver la escritura en absoluto, mientras que una réplica más obliga a una superposición por el principio del palomar. Eso hace que el menor quórum de lectura seguro sea n - w + 1, la conocida regla r + w > n. La disponibilidad sale después de contar: una escritura necesita w réplicas vivas y una lectura necesita r, así que el sistema sigue atendiendo ambas mientras no haya más de n - max(r, w) réplicas caídas. Subir w compra lecturas más baratas a costa de tolerar menos fallos, que es el trade-off (compromiso) que muestran los ejemplos. El tiempo y el espacio son 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)¿Lo que te frena es la idea y no el código? Consistencia y CAP lo explica.