teorema C.A.P

All lectures for ID purposes
Level 1 , Pelajaran 885
Tersedia

4.1 Konsistensi tentang Brewera

Pertama-tama, Eric Brewer bukanlah, dan tidak pernah diklaim sebagai, seorang ahli database. Dia milik komunitas sistem terdistribusi, dan ceramahnya yang terkenal, di mana "teorema" CAP muncul, diberikan pada konferensi "Principles of Distributed Computing". (Ngomong-ngomong, sepuluh tahun kemudian, pada tahun 2010, dia kembali memberikan ceramah undangan di konferensi yang sama, dan dalam ceramah ini dia memberikan, khususnya, sejumlah contoh sistem terdistribusi, yang pengembangannya memperhitungkan " teorema" dari CAP.) Dalam bidang ini istilah-istilah yang digunakan dalam bidang basis data memiliki interpretasi tersendiri.

Secara khusus, istilah "konsistensi langsung" berarti bahwa setelah pengguna menerima pemberitahuan dari sistem tentang keberhasilan penyelesaian beberapa operasi pembaruan data, hasil operasi ini langsung terlihat oleh semua pengamat.

Konsistensi akhir berarti bahwa jika tidak ada operasi pemutakhiran data baru yang memasuki sistem untuk jangka waktu yang cukup lama, maka diharapkan hasil dari semua operasi pemutakhiran data sebelumnya pada akhirnya akan menyebar ke semua node sistem, dan semua data replika akan konsisten (tampaknya, ini harus dipahami sebagai "semua replika akan memiliki status yang sama".

Dengan mempertimbangkan konsistensi ini, "teorema" Brewer dapat dianggap cukup dapat dimengerti dan jelas: dalam sistem terdistribusi mana pun dengan data bersama, hanya dua sifat konsistensi, ketersediaan, dan toleransi partisi dari jaringan yang dapat dipastikan secara bersamaan. Dalam hal ini, Brewer bahkan mengontraskan himpunan properti ACID dengan himpunan properti BASE yang diusulkannya (Pada dasarnya Tersedia, Soft-state, Konsistensi akhir - ketersediaan dalam banyak kasus; status tidak stabil; konsistensi akhir). Tetapi pertentangan ini, menurut saya, tidak dapat dibenarkan, karena dalam kasus pertama kita berbicara tentang karakteristik logis dari transaksi, dan yang kedua - tentang sifat fisik dari sistem terdistribusi.

4.2 Bukti "teorema"

Banyak yang percaya bahwa "teorema" Brewer telah terbukti secara formal. Memang, makalah oleh Seth Gilbert dan Nancy Lynch memperkenalkan beberapa (hampir) definisi formal di mana konteks "teorema" benar-benar menjadi teorema dan dibuktikan. Namun, mari kita lihat bagaimana ketiga properti dari sistem terdistribusi ditentukan, yang menurut "teorema" Brewer, hanya dua properti yang dapat didukung secara bersamaan.

Konsistensi disebut atomik, atau konsistensi yang dapat dilinierkan (atomik, atau konsistensi yang dapat dilinierkan), yang merupakan properti dari sistem, semua objek data individu yang bersifat atomik (dapat dilinierkan). Pada gilirannya, objek atom adalah objek dengan beberapa operasi, sehingga panggilan operasi dan penerimaan data respons terjadi seolah-olah secara instan, yaitu. objek tidak menerima panggilan dari operasi berikutnya sampai operasi sebelumnya selesai sepenuhnya. Urutan di mana operasi diterima harus sedemikian rupa sehingga jika operasi tipe baca tiba setelah beberapa operasi tipe tulis dilakukan, maka operasi baca harus mengembalikan nilai yang ditulis oleh ini atau beberapa operasi tulis kemudian.

Sistem terdistribusi selalu tersedia jika setiap permintaan yang diterima oleh node yang tidak gagal harus dijawab. Ketahanan sistem terhadap partisi jaringan dimodelkan sebagai pelestarian kelangsungan hidup sistem jika terjadi kehilangan sejumlah pesan yang dikirim dari satu node ke node lainnya.

Berdasarkan definisi ini, Hilbert dan Lynch merumuskan teorema berikut (tidak ada jam dalam model jaringan asinkron, dan node harus membuat keputusan hanya berdasarkan pesan yang diterima dan perhitungan lokal):

Dalam model jaringan asinkron, tidak mungkin menerapkan objek data baca/tulis yang menjamin ketersediaan dan properti konsistensi atomik untuk semua eksekusi yang valid (termasuk yang kehilangan pesan).

Teorema ini benar-benar dibuktikan secara formal dengan metode "dengan kontradiksi". Artikel selanjutnya menyimpulkan bahwa:

Dalam model jaringan asinkron, tidak mungkin menerapkan objek data baca/tulis yang menjamin properti aksesibilitas untuk semua eksekusi yang valid dan konsistensi atomik untuk eksekusi yang valid di mana pesan tidak hilang.

Selain itu, kebenaran teorema utama dibuktikan untuk model jaringan yang sinkron sebagian, di mana setiap node memiliki jam, waktu yang ditunjukkan meningkat pada tingkat yang sama, tetapi tidak disinkronkan, yaitu. dapat menunjukkan waktu yang berbeda pada saat nyata yang sama. Ditunjukkan bahwa untuk kasus ini konsekuensi serupa tidak diturunkan, dan, oleh karena itu, untuk jaringan yang sebagian sinkron ada lebih banyak kemungkinan untuk mengatur sistem terdistribusi dengan properti "baik".

Ya, dalam arti tertentu (tidak harus sama dengan yang dimaksudkan Brewer) Gilbert dan Lynch dapat dianggap telah membuktikan bahwa tidak mungkin untuk secara bersamaan memastikan properti konsistensi atomik, ketersediaan, dan toleransi partisi dari suatu jaringan dalam satu sistem terdistribusi. Tapi apa hubungannya dengan transaksi database pada umumnya dan transaksi ACID pada khususnya?

4.3 transaksi ASAM

Inilah yang ditulis Julian Browne tentang ini dalam catatannya tentang pembahasan "teorema" CAP:

Dalam pembuktiannya, Hilbert dan Lynch menggunakan istilah atomisitas alih-alih konsistensi, yang lebih masuk akal dari sudut pandang teknis karena, secara tegas, konsistensi dalam arti ACID mengacu pada properti ideal transaksi basis data dan berarti tidak ada data yang akan hilang. menjadi gigih jika mereka melanggar beberapa batasan yang telah ditetapkan sebelumnya. Tetapi jika kita berasumsi bahwa batasan sistem terdistribusi yang telah ditetapkan sebelumnya adalah larangan adanya beberapa nilai berbeda untuk elemen data yang sama, maka menurut pendapat saya, kekurangan dalam abstraksi konsistensi ini dapat dipertimbangkan. tidak signifikan (selain itu, jika Brewer menggunakan istilah atomisitas, teorema AAP akan muncul, yang namanya akan sangat tidak nyaman untuk diucapkan).

Ini ditulis tidak terlalu serius, tapi jujur. Dan, pada kenyataannya, persyaratan konsistensi atom tidak boleh dicampur dengan persyaratan konsistensi transaksional dalam pengertian ACID. Batasan integritas basis data adalah logis, jika Anda mau, persyaratan bisnis. Mereka berasal dari logika domain aplikasi. Persyaratan konsistensi atom adalah jenis yang sangat berbeda. Ini adalah persyaratan implementasi yang termasuk dalam kategori yang secara tradisional dirujuk dalam industri basis data sebagai konsistensi fisik (misalnya, saat melakukan operasi perubahan indeks, semua blok dari pohon B+ yang sesuai harus berisi nilai yang valid dan dihubungkan dengan referensi yang valid ).

Dan inilah yang ditulis oleh perwakilan komunitas database Daniel Abadi dan Alexander Thomson dengan cukup serius dalam catatan mereka:

... persyaratan untuk ketersediaan sistem transaksional yang dapat diskalakan menjadi semakin kritis, dan ini biasanya dipenuhi melalui replikasi dan pengalihan otomatis permintaan jika terjadi kegagalan salah satu node. Oleh karena itu, pengembang aplikasi berharap bahwa jaminan konsistensi sistem ACID (awalnya terdiri dari dukungan lokal untuk invarian yang ditentukan pengguna) akan diperluas untuk memastikan konsistensi yang kuat (bahwa semua replika dari data yang sama pada waktu tertentu akan menjadi salinan identik, yaitu dalam konsistensi kasus ini tersirat dalam pengertian CAP/PACELC.

Dengan kata lain, konsistensi Brewer tidak ada hubungannya dengan konsistensi dalam arti ASAM, tetapi dalam sistem yang berfokus pada penyediaan ketersediaan tinggi melalui replikasi data yang diinginkan untuk mempertahankan konsistensi replika yang kuat. Ini bukan properti ACID, tetapi fitur teknis (fisik) dari DBMS paralel masif yang memfasilitasi pengembangan aplikasi.

Menurut Michael Stonebreaker, kunci untuk membangun DBMS modern berkualitas tinggi adalah pilihan kompromi teknis yang tepat. Saat memilih solusi teknik tertentu, banyak faktor yang harus diperhitungkan - persyaratan pengguna di masa mendatang, kemungkinan berbagai situasi kegagalan, dll., dan tidak dipandu secara dogmatis oleh pedoman teoretis umum apa pun (termasuk "teorema" CAP).

Stonebreaker percaya bahwa dalam bidang sistem basis data paralel transaksional, mengabaikan konsistensi Brewer demi mendukung ketersediaan tinggi dan toleransi partisi jaringan adalah trade-off yang buruk karena (a) konsistensi replika adalah fitur sistem yang sangat berguna; (b) DBMS paralel masif transaksional tidak memerlukan klaster dengan jumlah node yang sangat besar, sehingga situasi pemisahan jaringan tidak mungkin terjadi; (c) sistem dapat dengan mudah menjadi tidak tersedia, bukan karena partisi jaringan, tetapi, misalnya, karena adanya kesalahan perangkat lunak yang terjadi secara teratur.

Dengan demikian, aktivitas tinggi perwakilan dari kamp NoSQL (baca NoACID), yang sering mengacu pada "teorema" Brewer, tidak terkait dengan ketidakmungkinan teoretis untuk membangun DBMS transaksional paralel besar-besaran yang mendukung transaksi ACID, tetapi dengan fakta bahwa sistem yang disederhanakan yang tidak hanya mendukung transaksi ACID, tetapi juga konsistensi replika, dibuat lebih mudah dan lebih cepat. Karena organisasinya yang sederhana, mereka mampu memproses data dengan sangat cepat, dan untuk beberapa aplikasi ini lebih penting daripada semua kenyamanan yang melekat pada teknologi basis data.

Mari kita lihat bagaimana komunitas database menanggapi tantangan ini.

Komentar
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION