Intuisi CAP dan PACELC

Apa yang benar-benar dibatasi teorema CAP dan PACELC pada jaringan yang bisa gagal.

Daftar isi

Topik ini merapikan dua istilah yang sering disalahpahami pada desain sistem terdistribusi, yaitu teorema CAP dan perluasannya PACELC. Pembahasan dimulai dari apa yang sesungguhnya dibatasi teorema CAP, kapan pilihannya harus diambil, dan mengapa keputusan itu hanya muncul saat jaringan terputus. Setelah itu, PACELC dibahas untuk memperlihatkan tradeoff yang tetap ada ketika jaringan berjalan normal. Setelah membaca topik ini, tradeoff pada sistem data nyata dapat dikelompokkan ke dalam kategori PACELC beserta konsekuensi latensi dan konsistensinya.

Apa yang benar-benar dibatasi teorema CAP#

Teorema CAP menyatakan bahwa sebuah sistem data terdistribusi tidak dapat sekaligus menjamin konsistensi linier, ketersediaan penuh, dan partition tolerance ketika partisi jaringan terjadi. Konsistensi yang dimaksud adalah konsistensi linier, yaitu setiap pembacaan melihat tulisan terakhir yang sudah berkomitmen, seolah-olah hanya ada satu salinan data. Ketersediaan berarti setiap permintaan yang tiba pada node yang tidak mati selalu mendapat respons, meskipun isinya mungkin usang. Partition tolerance berarti sistem tetap beroperasi meskipun pesan antarnode dapat hilang atau tertunda tanpa batas waktu.

Kesalahpahaman yang paling umum adalah membaca CAP sebagai pilihan dua dari tiga yang harus diambil sejak awal desain. Pembacaan itu keliru karena partition tolerance bukan sifat yang dapat dilepas, melainkan fakta bahwa jaringan bisa terputus. Teorema hanya mengikat pada saat partisi benar-benar terjadi. Pada kondisi normal, konsistensi linier dan ketersediaan dapat berjalan bersama pada sistem yang sama, dan banyak sistem produksi mengandalkan hal itu setiap hari. Bukti formalnya disusun oleh Gilbert dan Lynch pada model jaringan yang dapat menghilangkan pesan tanpa batas waktu, sehingga klaster yang terbelah tidak pernah dapat memastikan keadaan sisi lainnya.

Pilihan hanya terjadi saat partisi#

Apabila jaringan terputus, dua sisi partisi tidak dapat saling memperbarui salinannya, sehingga sistem harus memilih salah satu dari dua cara. Cara pertama mempertahankan konsistensi: sisi yang tidak dapat mengonfirmasi kepada kuorum mayoritas menolak tulisan dan pembacaan yang mungkin usang, sehingga sebagian permintaan gagal. Cara kedua mempertahankan ketersediaan: setiap sisi menerima tulisan dan melayani pembacaan dari salinannya sendiri, dengan risiko kedua sisi menyimpan nilai yang berbeda. Simulasi berikut memperlihatkan kedua pilihan tersebut pada dua replika yang menyimpan satu penghitung.

python simulasi-partisi.py

# Simulasi partisi jaringan antara dua replika.
# Mode CP: tulisan ditolak di sisi yang terputus dari mayoritas.
# Mode AP: tulisan tetap diterima, dengan risiko nilai yang berbeda.

def simulasikan(mode):
    nilai_a = 10
    nilai_b = 10
    print(f"Mode {mode}")
    print(f"  Sebelum partisi: A = {nilai_a}, B = {nilai_b}")
    print("  Partisi terjadi: A dan B tidak dapat saling berkomunikasi.")

    if mode == "CP":
        print("  Tulisan 'nilai + 5' ke replika A ditolak")
        print("    alasan: A tidak dapat mengonfirmasi ke kuorum mayoritas")
        print(f"  Setelah tulisan: A = {nilai_a}, B = {nilai_b}")
    else:
        nilai_a += 5
        print("  Tulisan 'nilai + 5' ke replika A diterima")
        print(f"  Pembacaan dari replika B: {nilai_b}")
        print(f"  Setelah tulisan: A = {nilai_a}, B = {nilai_b}")
        print("  Nilai kedua replika berbeda selama partisi berlangsung.")

simulasikan("CP")
print()
simulasikan("AP")

text Keluaran

Mode CP
  Sebelum partisi: A = 10, B = 10
  Partisi terjadi: A dan B tidak dapat saling berkomunikasi.
  Tulisan 'nilai + 5' ke replika A ditolak
    alasan: A tidak dapat mengonfirmasi ke kuorum mayoritas
  Setelah tulisan: A = 10, B = 10

Mode AP
  Sebelum partisi: A = 10, B = 10
  Partisi terjadi: A dan B tidak dapat saling berkomunikasi.
  Tulisan 'nilai + 5' ke replika A diterima
  Pembacaan dari replika B: 10
  Setelah tulisan: A = 15, B = 10
  Nilai kedua replika berbeda selama partisi berlangsung.

Pada mode CP, tulisan ditolak karena replika A tidak dapat memastikan dirinya terhubung ke mayoritas, sehingga kedua replika tetap menyimpan nilai yang sama. Pada mode AP, tulisan diterima, tetapi pembacaan dari replika B tetap mengembalikan nilai lama selama partisi berlangsung. Kedua pilihan sama-sama sah, dan sistem nyata sering memilihnya per operasi: tulisan yang kritis dilindungi konsistensi, sedangkan data yang cepat usang dilayani dengan ketersediaan. Hal yang penting adalah keputusan itu dibuat secara eksplisit, bukan dibiarkan sebagai konfigurasi bawaan yang tidak pernah ditinjau ulang.

PACELC menambahkan sisi latensi#

PACELC memperluas CAP dengan menyatakan tradeoff kedua yang berlaku saat jaringan normal. Bunyinya: if Partition, then choose A or C, else choose Latency or Consistency. Bagian else sering luput dari perhatian, padahal inilah keputusan yang dihadapi sistem setiap hari. Untuk mendapatkan konsistensi tanpa partisi, replikasi harus berjalan sinkron, sehingga setiap tulisan menunggu konfirmasi dari node lain. Untuk mendapatkan latensi rendah, replikasi berjalan asinkron, sehingga respons tulisan dikembalikan sebelum salinan lain diperbarui.

Pohon keputusan CAP dan PACELC

Notasi PACELC menuliskan kombinasi itu secara ringkas. Sistem PA/EL menerima tulisan di mana saja dan mereplikasi secara asinkron, misalnya penyimpanan nilai-kunci yang mengutamakan latensi. Sistem PC/EC menuntut kuorum pada tulisan dan pembacaan, sehingga latensinya naik tetapi konsistensinya terjaga. Kombinasi PA/EC dan PC/EL juga mungkin, dan keduanya memperlihatkan bahwa sumbu saat partisi tidak selalu sejajar dengan sumbu saat normal. Sebagai patokan praktis, pertanyaan yang dijawab PACELC bukan tentang pilihan di saat darurat, melainkan tentang biaya harian, karena setiap milidetik tambahan replikasi sinkron dibayar pada setiap tulisan, bukan hanya saat kegagalan.

Kesalahan umum#

Kesalahan pertama adalah menyimpulkan bahwa sistem dengan konsistensi linier pasti sering tidak tersedia. Penyebabnya adalah membaca teorema CAP tanpa prasyarat partisinya, sehingga tradeoff yang hanya berlaku saat jaringan terputus diperlakukan sebagai biaya permanen. Perbaikannya adalah menanyakan terlebih dahulu bagaimana sistem berperilaku saat jaringan normal, karena di sanalah sebagian besar permintaan berada.

Kesalahan kedua adalah menganggap partition tolerance sebagai opsi yang dapat dilepas. Penyebabnya adalah mencampuradukkan keandalan jaringan yang dapat ditingkatkan dengan jaminan perilaku saat jaringan tetap gagal. Perbaikannya adalah merancang seolah-olah partisi pasti terjadi, lalu menentukan pilihan C atau A untuk setiap jenis data.

Kesalahan ketiga adalah memperlakukan CAP atau PACELC sebagai model konsistensi yang lengkap. Penyebabnya adalah menukar slogan tradeoff dengan jaminan yang dapat diuji. Perbaikannya adalah menyebut model konsistensi yang benar-benar diberikan, misalnya konsistensi linier, read-your-writes, atau konsistensi eventual, sebagaimana dibahas pada topik berikutnya.

Ringkasan#

Teorema CAP hanya memaksa pilihan antara konsistensi linier dan ketersediaan saat partisi jaringan terjadi, tidak selalu dan tidak untuk semua keadaan.
Partition tolerance bukan opsi yang dapat dilepas, melainkan fakta bahwa jaringan dapat terputus, sehingga yang dipilih adalah C atau A pada saat itu.
PACELC menambahkan tradeoff latensi versus konsistensi untuk kondisi normal, yang ditentukan oleh replikasi sinkron atau asinkron.

Referensi#

Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services — ACM — Bukti formal teorema CAP oleh Gilbert dan Lynch pada model jaringan yang dapat menghilangkan pesan.
CAP twelve years later: How the “rules” have changed — InfoQ — Rekonseptualisasi CAP oleh Eric Brewer dan pengantar praktik menyerahkan pilihan ke tingkat operasi.