Jeden z mechanismů koordinace v distrbuovaných systémech
Proces potřebuje souhlas podmnožiny (quora) procesů, ne všech. Klíčem je průniková vlastnost: libovolná dvě quora se musí překrývat alespoň v jednom uzlu.
Klíčová myšlenka:
Nepotřebuješ všechny. Stačí ti “dost” procesů, ale tak, aby se žádná dvě quora nepřekrývala. Překryv = koordinace.
Pro hlasovací množiny $V_1, V_2, \ldots, V_n$ musí platit:
\[V_i \cap V_j \neq \emptyset \quad (\forall i, j)\]Proč? Pokud se dvě quora překrývají, alespoň jeden proces je v obou → ten zajistí koordinaci (nemůže dát hlas dvěma různým žadatelům současně).
Existuje trade-off mezi velikostí quora a počtem zpráv:
| Typ quora | Velikost | Použití |
|---|---|---|
| Majority (většina) | $\lceil \frac{N+1}{2} \rceil$ | Paxos, Raft, Dynamo |
| Grid-based (√N) | $2\sqrt{N} - 1$ | Maekawa algorithm |
| Read/Write quora | $R + W > N, W > \frac{N}{2}$ | Replicated databases |
| Weighted quorum | $\sum w_i > \frac{W}{2}$ | Uzly s různými vahami |
REQUEST(timestamp) jen členům $V_i$ (ne všem!)VOTERELEASEVOTE od všech členů svého quora $V_i$RELEASE členům $V_i$VOTE dalšímu čekajícímuDefinice: $Q = {$ libovolná podmnožina s $> \frac{N}{2}$ uzly $}$
Důkaz průniku:
| Quorum 1: $ | Q_1 | > \frac{N}{2}$ |
| Quorum 2: $ | Q_2 | > \frac{N}{2}$ |
| $ | Q_1 | + | Q_2 | > N$ → musí se překrývat! ✓ |
Vlastnosti:
Použití:
Definice: Uspořádej N uzlů do $\sqrt{N} \times \sqrt{N}$ matice.
Příklad (9 uzlů):
C1 C2 C3
R1 [ 1][ 2][ 3]
R2 [ 4][ 5][ 6]
R3 [ 7][ 8][ 9]
P5 má quorum: {4, 5, 6, 2, 5, 8} = {2, 4, 5, 6, 8}
Důkaz průniku:
Vlastnosti:
Použití:
Definice:
Příklad:
Vlastnosti:
Použití:
Definice: Uzlům přiřadíme váhy $w_1, w_2, \ldots, w_N$
Příklad:
Node 1: w=3 (silný server)
Node 2: w=3 (silný server)
Node 3: w=1 (slabý server)
Node 4: w=1 (slabý server)
W = 8 celkem
Validní quora:
{1, 2} → 6 > 4 ✓
{1, 3, 4} → 5 > 4 ✓
{2, 3, 4} → 5 > 4 ✓
Použití:
1. Menší počet zpráv než permission-based
2. Vysoká odolnost vůči výpadkům
3. Flexibilita
4. Paralelismus
1. Složitá konstrukce quor
2. Stále potřebuješ celé quorum
3. Riziko deadlocku (Maekawa)
4. Složitější reasoning o korektnosti
class MaekawaProcess:
def request_CS(self):
self.timestamp = lamport_clock.tick()
# Pošli REQUEST jen svému quoru
for node in my_voting_set:
send(node, REQUEST(self.id, self.timestamp))
# Čekej na VOTE od všech v quoru
wait_for_votes(len(my_voting_set))
enter_critical_section()
def on_receive_request(self, sender, timestamp):
if not self.voted_for:
# Nemám aktivní VOTE → dám hlas
self.voted_for = sender
send(sender, VOTE(self.id))
else:
# Už jsem dal hlas → zařaď do fronty
self.request_queue.append((sender, timestamp))
# Deadlock prevention: INQUIRE
if timestamp < self.my_timestamp:
send(self.voted_for, INQUIRE())
def release_CS(self):
for node in my_voting_set:
send(node, RELEASE(self.id))
def on_receive_release(self, sender):
self.voted_for = None
# Dej hlas prvnímu ve frontě
if self.request_queue:
next_requester = self.request_queue.pop(0)
self.voted_for = next_requester
send(next_requester, VOTE(self.id))
Phase 1: Prepare
def propose(value):
proposal_number = generate_unique_number()
# Pošli PREPARE majority quoru
for node in majority_quorum():
send(node, PREPARE(proposal_number))
# Čekej na PROMISE od majority
promises = wait_for_majority_promises()
# Vyber hodnotu (nejnovější nebo svou)
final_value = choose_value(promises, value)
Phase 2: Accept
# Pošli ACCEPT majority quoru
for node in majority_quorum():
send(node, ACCEPT(proposal_number, final_value))
# Čekej na ACCEPTED od majority
if received_majority_accepts():
return CHOSEN(final_value)
Write (W=3 z N=5):
def put(key, value):
# Najdi preference list pro klíč
replicas = consistent_hash.get_replicas(key, N=5)
# Piš na všech 5, čekej na 3
version = vector_clock.increment()
for replica in replicas:
async_write(replica, key, value, version)
# Čekej na W=3 potvrzení
wait_for_acks(W=3)
return SUCCESS
Read (R=2 z N=5):
def get(key):
replicas = consistent_hash.get_replicas(key, N=5)
# Čti z R=2 replik
responses = []
for replica in replicas[:R]:
responses.append(read(replica, key))
# Vyber nejnovější verzi (vector clock)
return resolve_conflicts(responses)
Problém: Jak sestavit quora pro grid, pokud $N \neq k^2$?
Řešení 1: Padding
N = 10 → nejbližší čtverec = 16
Přidej 6 "dummy" uzlů
Řešení 2: Asymetrické quora
N = 10 → 3×4 grid (nemusí být čtvercové)
Některá quora jsou větší než jiná
Řešení 3: Projective planes (pokročilé)
Problém: Co když se N mění (uzly přibývají/ubývají)?
Řešení v Paxos/Raft:
| Vlastnost | Quorum | permission-based koordinace | token-based koordinace | ||
|---|---|---|---|---|---|
| Počet zpráv | O(√N) - O(N/2) 🟡 | O(N) ❌ | O(1) ✅ | ||
| Odolnost vůči výpadkům | ✅ Vysoká (majority) | 🟡 Nízká | ❌ Velmi nízká | ||
| Latence | 🟡 Střední (čeká na quorum) | ❌ Vysoká (čeká na všechny) | 🟡 Závisí | ||
| Složitost | ❌ Vysoká | 🟡 Střední | ✅ Nízká | ||
| Férové uspořádání | ✅ Ano (timestamp) | ✅ Ano | 🟡 Závisí | ||
| Flexibilita | ✅ Velmi vysoká | ❌ Nízká | ❌ Nízká |
Výhody:
Nevýhody:
Výhody:
Nevýhody:
Vyvážený trade-off:
Dobré pro:
Nepoužívej pro:
1. Amazon Dynamo:
2. Apache Cassandra:
4. etcd/Consul: