CAP dan Model Konsistensi

Model konsistensi mendefinisikan jaminan apa yang diberikan oleh sistem tereplikasi mengenai nilai yang dikembalikan oleh pembacaan, dan teorema CAP membatasi jaminan mana yang dapat hidup berdampingan dengan ketersediaan di bawah partisi jaringan.

Definition

Model konsistensi adalah kontrak antara penyimpanan data tereplikasi dan kliennya yang menentukan hasil yang diizinkan dari pembacaan dan penulisan bersamaan; teorema CAP menyatakan bahwa dengan adanya partisi jaringan, penyimpanan data terdistribusi tidak dapat menyediakan konsistensi linearizable dan ketersediaan.

Scope

Topik ini mencakup model konsistensi formal—linearizabilitas, konsistensi sekuensial, konsistensi kausal, dan konsistensi eventual—serta pengurutannya berdasarkan kekuatan; teorema CAP dan pernyataan serta buktinya yang tepat; dan penyempurnaan seperti PACELC yang juga memperhitungkan pertukaran latensi-konsistensi tanpa adanya partisi. Ini menyediakan kosakata untuk menentukan dan membandingkan jaminan sistem tereplikasi.

Core questions

• Bagaimana linearizabilitas, konsistensi sekuensial, kausal, dan eventual berbeda dalam kekuatannya?
• Apa sebenarnya yang dilarang oleh teorema CAP, dan apa yang diizinkannya?
• Bagaimana pertimbangan latensi menyempurnakan pertukaran konsistensi ketika tidak ada partisi?

Key theories

Linearizabilitas dan konsistensi sekuensial

Linearizabilitas mensyaratkan setiap operasi untuk tampak berlaku secara atomik pada suatu instan antara pemanggilan dan responsnya, konsisten dengan waktu nyata; konsistensi sekuensial menghilangkan persyaratan waktu nyata, hanya menuntut satu interleave legal yang menghormati urutan setiap proses.

Teorema CAP

Gilbert dan Lynch membuktikan bahwa tidak ada penyimpanan data tereplikasi yang dapat menjamin konsistensi linearizable dan ketersediaan ketika jaringan dapat menjatuhkan pesan antar replika, memaksa pilihan selama partisi.

Penyempurnaan PACELC

PACELC memperluas CAP dengan mencatat bahwa bahkan tanpa partisi, sistem menukar latensi dengan konsistensi, sehingga desain dicirikan oleh perilakunya baik selama partisi maupun dalam operasi normal.

Clinical relevance

Setiap basis data terdistribusi dan layanan penyimpanan harus menyatakan model konsistensi, dan pertukaran CAP dan PACELC menjelaskan mengapa beberapa sistem memprioritaskan ketersediaan sementara yang lain memprioritaskan konsistensi; memahami hal tersebut sangat penting untuk memilih dan mengoperasikan infrastruktur data.

History

Lamport mendefinisikan konsistensi sekuensial pada tahun 1979 dan Herlihy serta Wing memformalkan linearizabilitas pada tahun 1990; Brewer menduga pertukaran CAP pada tahun 2000, Gilbert dan Lynch membuktikannya pada tahun 2002, dan pembingkaian ulang PACELC oleh Abadi pada tahun 2012 mengklarifikasi bahwa latensi, bukan hanya partisi, mendorong pilihan konsistensi.

Debates

Apakah CAP sering disalahartikan?

CAP sering diringkas sebagai 'pilih dua dari tiga,' tetapi hasil yang tepat hanya memaksa pilihan konsistensi-ketersediaan selama partisi; kritikus berpendapat bahwa penyederhanaan berlebihan ini mengaburkan pertukaran latensi-konsistensi sehari-hari yang lebih relevan yang ditangkap oleh PACELC.

Key figures

• Eric Brewer
• Seth Gilbert
• Nancy Lynch
• Maurice Herlihy
• Jeannette Wing
• Leslie Lamport

Seminal works

• gilbert2002
• herlihy1990
• lamport1979

Frequently asked questions

Apakah CAP berarti sistem hanya dapat memiliki dua dari konsistensi, ketersediaan, dan toleransi partisi?

Tidak sepenuhnya. Partisi adalah fakta jaringan, bukan pilihan desain, jadi keputusan sebenarnya adalah apa yang harus dilakukan selama partisi: mengorbankan konsistensi yang kuat untuk tetap tersedia, atau mengorbankan ketersediaan untuk tetap konsisten. Ketika tidak ada partisi, sistem dapat menjadi konsisten dan tersedia.