Qual è il ragionamento alla base del teorema PAC?

Question

http://en.wikipedia.org/wiki/CAP_theorem

http://www.cs.berkeley.edu/~brewer/cs262b -2004 / PODC-keynote.pdf

penso che non è molto semplice motivo per cui solo due di

1. Coerenza
2. Disponibilità
3. Tolleranza Partizione

può contenere per ogni dato sistema di database distribuito. Questa congettura è stato dimostrato, ma c'è un modo più semplice per capire perché probabilmente questo potrebbe contenere?

Io non sono alla ricerca di una prova, solo un buon modo per capire il motivo per cui questo teorema potrebbe avere un senso. Qual è il ragionamento?

Answer 1

Ok, immaginate di avere un database distribuito. Diciamo che si dispone di un nodo in Oregon e uno in California. La teoria PAC dice che si incorrere in problemi quando si imposta questo tipo di database.

Ad esempio, se si query di dati da un database, esso deve essere lo stesso che i dati nella altro database. Ciò assicura che tutto ciò che valore hanno in un unico database è garantito per essere nell'altro ( Coerenza della teoria PAC). In questo modo consente di aggiornare i dati in un database e di query da un altro, ottenendo gli stessi risultati.

Quando aggiorniamo i dati nel nodo Oregon, i dati vengono inviati al nodo della California in modo che i database sono coerenti. Al fine di mantenere la consistenza veramente, dobbiamo assicurare che entrambi i database ottenere l'aggiornamento prima o sono autorizzati a veramente salvare i dati (commit a due fasi usando le transazioni distribuite). In altre parole, se il database della California non può salvare i dati per qualche motivo (ad esempio guasto del disco rigido), quindi il database in Oregon non salverà i dati e fallirà la transazione.

Il problema con le transazioni distribuite, come quello di cui sopra arriva quando vogliamo avere alta disponibilità. In questo scenario di cui sopra, il processo di cercare di ottenere entrambi i database in sincronia è un processo molto, molto lento. (Immaginate, dobbiamo inviare i dati dall'Oregon alla California, assicurarsi che arriva, assicurarsi che entrambi i database hanno serrature sui dati, etc.) Questo fa sì che i principali problemi quando vogliamo un sistema che è veloce e reattivo anche durante periodi di forte domanda. (Questo è il Disponibilità del teorema PAC).

Di solito, ciò che facciamo al fine di assicurare l'alta disponibilità è usiamo replica invece di transazioni distribuite. Così, invece di garantire che la California può accettare i dati, dobbiamo solo andare avanti e lo immagazzinano nel nodo Oregon e quindi inviare i dati in California quando arriviamo intorno ad esso. Questo garantisce che possiamo sempre memorizzare i dati, indipendentemente dal fatto che la California è pronto per memorizzare i dati oppure no.

Questo migliora disponibilità, ma a costo di coerenza. Vedi, se qualcuno aggiorna i dati in Oregon e poi qualcuno (allo stesso tempo), legge i dati in California, non stanno ottenendo i nuovi dati - i database non sono più coerenti. In realtà, essi non saranno coerenti fino Oregon invia i dati in California!

Quindi, questa è la disponibilità -confrontarli- Coerenza trade-off.

Partizione Tolleranza è il terzo aspetto della teoria della PAC. Il partizionamento è, in questo contesto, l'idea che un database (o altro sistema distribuito) possono rompere in sezioni separate e ancora funzionare correttamente.

La questione diventa, che cosa accade quando entrambi i database sono in esecuzione in modo corretto, ma il link dall'Oregon alla California è reciso?

Se si aggiorna il database in Oregon, abbiamo bisogno di ottenere i dati in California un modo o nell'altro (transazione distribuita o di replica). Tuttavia, se il collegamento tra i due è reciso, allora il sistema è diventato partizionato e le banche dati non sono più collegati tra loro.

Quando questo accade, le scelte devono smettere di consentire gli aggiornamenti (per mantenere la coerenza) al costo di disponibilità o per consentire gli aggiornamenti (per mantenere la disponibilità) al costo di coerenza.

Come si può vedere, la tolleranza partizione crea compromessi diretti tra coerenza e di disponibilità.

---

Non c'è ovviamente più ad esso che quello, ma questi sono un paio di esempi su come questi tre aspetti principali dei sistemi distribuiti lavorano per e uno contro l'altro. href="http://www.julianbrowne.com/article/viewer/brewers-cap-theorem" rel="nofollow noreferrer"> Julian Browne della teoria PAC è un luogo eccellente per imparare di più.