- Two-Phase Locking(2PL), yang diperkenalkan pada 1976, menyediakan Opacity yang lebih kuat daripada serializability, tetapi sekitar 50 tahun kemudian masih menyisakan keterbatasan dalam skalabilitas baca dan jaminan progres
- Dengan aturan sederhana untuk memperoleh dan melepas lock, 2PL menangani transaksi multi-record sekaligus menyediakan tingkat isolasi yang kuat, sehingga masih banyak digunakan di DB transaksional komersial dan struktur data konkuren
- 2PL tradisional dapat membuat operasi baca saling bertabrakan karena mutual exclusion lock; bahkan saat memakai reader-writer lock, kontensi read-indicator muncul pada titik yang dipadati pembacaan, seperti root pada binary search tree
- 2PLSF menyebarkan penanda per reader ke cache line untuk mengurangi kontensi saat memperoleh read lock, dan menerapkan fetch_and_add() pada penghitung atomik pusat hanya untuk transaksi yang mengalami konflik
- Varian 2PL seperti No-Wait, Deadlock-detection, dan Wait-Or-Die masih menyisakan masalah live-lock atau skalabilitas, sementara 2PLSF adalah peningkatan yang menargetkan skalabilitas baca sekaligus transaksi starvation-free
Mengapa 2PL Masih Penting
- Two-Phase Locking(2PL) adalah salah satu kontrol konkurensi serbaguna pertama yang menyediakan serializability, dan dalam praktiknya menyediakan tingkat isolasi yang lebih kuat, yaitu Opacity
- 2PL diperkenalkan pada 1976 melalui makalah Jim Gray dan koleganya, dan karena idenya sendiri kemungkinan sudah ada sebelumnya, teknik ini diperlakukan sebagai teknik yang hampir berusia 50 tahun
- Kontrol konkurensi serbaguna berarti algoritme yang memungkinkan transaksi dengan semantik all-or-nothing atas item data seperti beberapa objek, record, atau tuple
- Kelebihan 2PL terletak pada kesederhanaan dan isolasi yang kuat
- Sebelum membaca atau menulis record, transaksi terlebih dahulu memperoleh lock yang melindungi record tersebut
- Lock yang sudah diperoleh dipertahankan sampai transaksi selesai, sehingga dapat membentuk sudut pandang yang konsisten
Isolasi yang Dibentuk oleh Aturan Sederhana
- Dalam 2PL, lock diperoleh pada setiap akses selama transaksi, lalu semua lock dilepas pada akhir transaksi ketika diketahui tidak ada akses lagi
- Pada titik akhir, semua lock atas data yang diakses sudah dipegang, sehingga terbentuk linearization point untuk transaksi tersebut
- Lima puluh tahun lalu, banyak peneliti database menganggap lock boleh langsung dilepas setelah akses record selesai, tetapi kontrol konkurensi seperti itu tidak serializable
- Database transaksional komersial yang dikenal menggunakan 2PL atau kombinasi dengan T/O dan MVCC
- Di bidang struktur data konkuren, linearizability hampir menjadi standar, dan untuk menulis secara konsisten ke beberapa node biasanya diperlukan pendekatan seperti 2PL untuk akses tulis
- Pengecualiannya adalah struktur data lock-free, tetapi ditekankan bahwa implementasi lock-free yang benar itu sulit
Bottleneck 2PL: Skalabilitas Baca dan Live-lock
- Kelemahan besar 2PL adalah kurangnya skalabilitas baca dan jaminan progres live-lock
- 2PL klasik dirancang berdasarkan mutual exclusion lock, sehingga meskipun dua thread hanya membaca record yang sama, keduanya dapat bertabrakan dan salah satu atau keduanya dapat abort lalu dimulai ulang
- Jika diganti dengan reader-writer lock, konflik antar pembacaan berkurang, tetapi biaya lock dan penggunaan memori meningkat
- Mutual exclusion lock dapat diimplementasikan dengan 1 bit yang menunjukkan status terkunci/tidak terkunci
- Reader-writer lock membutuhkan counter untuk menghitung jumlah reader yang saat ini memegang lock dalam mode baca, selain bit tersebut
- Misalnya, counter 7-bit dapat merepresentasikan hingga 128 thread, dan setiap lock dapat memakan 1 byte
- Jika database memiliki miliaran record, lock saja dapat membutuhkan miliaran byte
- Masalah yang lebih besar adalah kontensi counter
- Pada workload read-non-disjoint, banyak pembacaan terpusat pada data yang sama
- Root node pada binary search tree adalah contoh representatif karena semua operasi harus membacanya sebelum turun ke node bawah
- Dalam 2PL, setiap akses ke root perlu memperoleh lock, dan meskipun memakai reader-writer lock, terjadi kontensi berat pada lock root node
Pendekatan yang Ada dan Read-indicator yang Skalabel
- TLRW adalah pendekatan yang diajukan Dave Dice dan Nir Shavit di SPAA 2010; pendekatan ini meningkatkan performa dibanding mutual exclusion lock dengan memakai reader-writer lock, tetapi tidak secepat optimistic concurrency control
- Jika implementasi yang mirip TLRW, di mana setiap akses baca berkontensi pada satu variabel reader-writer lock, diterapkan ke Rank-based Relaxed AVL binary search tree, skalabilitas akan mendatar baik untuk sebagian besar transaksi tulis maupun transaksi baca
- Kontensi read-indicator dapat diredakan dengan read-indicator yang skalabel
- Cara yang disukai adalah reader-writer lock di mana setiap reader menandai kedatangan dan kepergiannya pada cache line terpisah
- Perolehan read lock menjadi bebas kontensi
- Thread yang ingin memperoleh write lock harus memindai semua cache line untuk memeriksa apakah diizinkan, sehingga biaya memperoleh write lock meningkat
- NUMA Aware reader-writer locks membahas algoritme reader-writer lock yang menggunakan teknik ini
- Dari tiga algoritme reader-writer lock, dua memiliki skalabilitas tinggi tetapi tidak starvation-free
Desain Reader-writer Lock pada 2PLSF
- Two-Phase Locking Starvation-Free(2PLSF) adalah kontrol konkurensi yang diimplementasikan dengan reader-writer lock yang memiliki skalabilitas baik saat memperoleh read lock dan memiliki sifat tambahan
- Reader-writer lock 2PLSF mencadangkan 1 bit per thread untuk read-lock
- Bit-bit ini ditempatkan pada cache line tersendiri
- Ditempatkan bersama bit read-indicator dari lock yang berdekatan
- Seperti dalam makalah NUMA-aware reader-writer lock, biayanya dipindahkan ke perolehan write lock
- Write lock harus memindai beberapa cache line
- Ini bukan solusi ajaib, melainkan trade-off
- Alasan trade-off ini berguna adalah karena kebanyakan workload cenderung read-heavy, dan workload write-intensive pun menghabiskan waktu yang cukup besar pada akses baca, seperti tahap lookup record
- Dengan reader-writer lock yang ditingkatkan, 2PL dapat diskalakan bahkan pada workload read-non-disjoint, tetapi masalah live-lock harus diselesaikan secara terpisah
Masalah Jaminan Progres yang Tersisa pada Varian 2PL
- 2PL klasik memiliki varian representatif seperti No-Wait, Deadlock-detection, dan Wait-Or-Die, tergantung cara menangani kontensi
-
No-Wait
- Ketika terjadi konflik, transaksi sendiri atau transaksi lawan di-abort lalu dicoba lagi
- Percobaan ulang dapat dilakukan segera atau nanti dengan exponential backoff
- Jika transaksi yang ingin memodifikasi A lalu B dan transaksi yang ingin memodifikasi B lalu A terus bertabrakan, keduanya dapat berulang kali abort-restart tanpa berhasil commit, sehingga memiliki live-lock progress
-
Deadlock-detection
- Mempertahankan daftar thread yang menunggu pada lock dan mendeteksi siklus, yaitu deadlock
- Pada reader-writer lock, setiap reader harus memiliki daftarnya sendiri, dan mutual exclusion lock juga diperlukan untuk melindungi tiap daftar
- Saat mengambil lock dalam mode read-lock, semua daftar reader harus dipindai, sehingga biayanya besar
- Secara teoretis starvation-free mungkin bisa dicapai, tetapi ini bertentangan dengan tujuan karena memerlukan starvation-free lock dan tidak ada reader-writer lock bereskalabilitas tinggi yang starvation-free yang tersedia secara publik
- Jika setiap reader memiliki daftar, penggunaan memori juga dapat meningkat
-
Wait-Or-Die
- Semua transaksi diberi urutan, dan saat terjadi konflik lock, keputusan untuk menunggu atau abort dibuat dengan membandingkan timestamp transaksi dan timestamp pemilik lock
- Pada mutual exclusion lock, ini bekerja dengan baik karena pemilik dapat disimpan di dalam lock sebagai identifier thread unik
- Untuk memakai cara yang sama pada reader-writer lock, diperlukan thread-id untuk setiap reader
- Untuk mendukung 256 thread, diperlukan 8 bit × 256 = 256 byte per reader-writer lock
Bottleneck Penghitung Atomik Pusat dan Perbedaan 2PLSF
- Hambatan yang lebih besar pada Wait-Or-Die adalah semua transaksi harus memiliki ID transaksi unik
- Misalnya, urutan dapat dibuat dengan mengambil nomor dari variabel atomik pusat melalui fetch_and_add()
- Pada sebagian besar CPU modern, sulit melakukan lebih dari 40 juta fetch_and_add() per detik terhadap variabel atomik yang berkontensi
- Angka ini mungkin tampak besar jika dibandingkan dengan sekitar 660 juta transaksi harian Visa
- Namun untuk in-memory DBMS atau struktur data konkuren, angka itu mungkin belum cukup besar
- Pada satu mesin uji, sulit melampaui 20 juta fetch_and_add() per detik
- Fakta bahwa fetch_and_add() ini diperlukan untuk semua transaksi, termasuk transaksi baca, bukan hanya transaksi tulis, membatasi skalabilitas
- TL2 menjalankan pembacaan optimistis tanpa transaksi baca melakukan fetch_and_add() atomik
- Dari sisi transaksi baca, ini dapat diskalakan hingga ratusan juta tps
- Sebaliknya, 2PL berbasis Wait-Or-Die tidak dapat melampaui 40M tps/sec
- 2PLSF hanya memberi urutan pada transaksi yang masuk konflik
- Jumlah transaksi yang melakukan fetch_and_add() pada variabel atomik pusat berkurang
- Transaksi tanpa konflik tidak terikat pada plateau 40M tps
- Sebagai contoh, 200M tps dapat berjalan tanpa konflik, sementara hanya 40M tps yang sedang berkonflik yang terikat pada batas fetch_and_add()
- Algoritme ini menyediakan starvation-freedom
Materi dan Penilaian Akhir
- Algoritme 2PLSF sendiri tidak dibahas secara mendetail, tetapi dinilai cukup sederhana untuk algoritme yang starvation-free
- Sebagai materi rujukan, tersedia makalah dan source code
- Makalah: https://zenodo.org/record/7886718
- Source code: https://github.com/pramalhe/2PLSF/blob/main/stms/2PLSF.hpp
- 2PLSF juga terhubung ke makalah ACM, dan dirangkum sebagai algoritme yang dibuat oleh Pedro Ramalhete, Andreia, dan Pascal Felber
- Tujuan 2PLSF mendekati sifat yang semestinya dimiliki 2PL sejak awal
- Dapat diskalakan dengan baik bahkan dalam situasi read-non-disjoint ketika pembacaan saling tumpang tindih
- Menyediakan transaksi starvation-free, bentuk tertinggi dari blocking progress
- Dapat memiliki skalabilitas bahkan dalam sebagian situasi konflik
- 2PLSF tidak sempurna, tetapi dinilai lebih baik daripada TL2 dari sisi penyelesaian konflik, dan perbedaannya dengan 2PL lama dianalogikan seperti perbedaan antara beliung dan jackhammer
1 komentar
Pendapat Hacker News
Saya penasaran apa praktik terbaik industri untuk menyinkronkan atau menjaga beberapa penyimpanan data tetap “konsisten” dalam arsitektur microservices terdistribusi
Beberapa hari lalu saya mencoba memecahkan masalah inkonsistensi dengan “settled timestamp”; ini mirip pendekatan multiversion yang menganggap penyimpanan/commit valid jika waktu berlalu tanpa laporan error. Dalam two-phase commit, fase keduanya adalah waktu
Caranya adalah memantau clock server lain, dan jika tidak diperbarui, tidak memercayai settled timestamp server itu. Tujuannya memperluas konsistensi ke banyak server karena tidak perlu menunggu respons pada setiap update, cukup menunggu rentang timestamp berikutnya
Saya membuat kode Python multithread dan multiprocessing yang menguji nondeterminisme dengan 10 thread yang saling mengirim update acak: https://replit.com/@Chronological/InconsistencySimulation#ma...
Dalam simulasi ini, pembacaan adalah nilai minimum dari seluruh timestamp yang dilaporkan semua server, dan ketika tiap thread ditanya nilai counternya setelah 10 detik, kadang semuanya memberi nilai yang sama, tetapi cukup sering menjadi kondisi split-brain
Saya tahu bahwa wall clock timestamp tidak cocok untuk penentuan urutan dalam sistem terdistribusi, dan harus menggunakan logical clock atau vector clock
Akan bagus jika pada titik mana pun simulasi bisa dibuat melaporkan angka yang sama semuanya. Bloomlang mencoba menyelesaikan masalah pada eventual consistency ketika nilai yang datang terlambat memengaruhi hasil sehingga tidak linearizable
Saya terutama tertarik pada cara melakukan scaling sambil menjaga konsistensi, tetapi ini tampaknya masalah yang cukup sulit
Beberapa sistem menulis secara berurutan ke jurnal terpusat, dan jurnal menerima request seperti key-value store. Jurnal itu direplikasi ke semua node, lalu node membaca jurnal dan menjalankan logika kompleks yang diminta
Karena Kubernetes menggunakan etcd, ia cukup baik diskalakan sebagai key-value store dengan konsistensi kuat
Karena Anda menyebut “beberapa penyimpanan data”, saya berasumsi datanya heterogen dan opsi seperti CockroachDB bukan pilihan
Jika Anda pemula, membuat sendiri itu berbahaya. https://aphyr.com/ adalah semacam tolok ukur untuk pengujian dan juga sangat bagus untuk edukasi. Anda bisa menguji sistem terdistribusi dengan Jepsen, tetapi lebih baik memakai penyimpanan data yang sudah ditunjukkan Kyle sebagai kokoh
Saya tidak terlalu familier dengan teknologi-teknologi ini, tetapi ketika belajar database, SSI diperkenalkan sebagai 2PL yang “lebih baik” untuk masa depan. Saya penasaran apa bedanya SSI dengan 2PLSF, dan mengapa tidak disebutkan di sini
Namun untuk efek terdistribusi, locking, transaksi dua fase, dan sebagainya masih diperlukan. Secara pribadi saya melihatnya lebih sebagai fitur yang saling melengkapi daripada pengganti
Untuk struktur data dalam memori, itu wajar, tetapi jika menangani database eksternal atau resource eksternal bersama lainnya, mungkin ada cara yang lebih baik
Sering kali request bisa diproses secara batch sehingga resource eksternal diakses dengan concurrency lebih rendah dan payload lebih besar. Jika resource itu menangani batch dengan baik, concurrency dan locking yang diperlukan akan jauh berkurang
Misalnya jika menggunakan Postgres, jumlah koneksi berkurang, dan Anda mungkin tidak perlu menambahkan PgBouncer yang meningkatkan kompleksitas
Namun batching request kurang cocok dengan sebagian besar bahasa pemrograman. Bahasa yang dioptimalkan untuk concurrency tinggi seperti channel di Go atau process di Elixir bisa melakukannya dengan baik, tetapi dalam bahasa yang memproses semuanya dengan thread, ini bisa menyakitkan
Situs yang tidak bisa di-upgrade ke HTTPS akan menampilkan peringatan, dan situs yang mendukung keduanya akan langsung dialihkan ke versi HTTPS
Dan kalau tautan HTTP itu tentang algoritma concurrency yang bagus, saya tetap akan membacanya
fetch_and_adduntuk mendapatkan transaction ID? Saya juga mempertanyakan apakah transaction ID memang diperlukan sejak awalTujuannya terdengar seperti menetapkan urutan yang arbitrer tetapi konsisten di antara transaksi aktif, agar saat terjadi konflik mereka bisa sama-sama menyepakati siapa yang menunggu dan siapa yang mati. Kalau begitu, tidak bisakah memakai ID thread?
Angka acak juga mungkin bisa. Jika seri diperlakukan sebagai “mati”, dalam kasus terburuk kedua transaksi hanya akan dibatalkan tanpa perlu lalu dicoba lagi dengan angka acak baru
Meski tidak disebutkan, sepertinya tujuannya adalah memprioritaskan transaksi yang lebih lama agar transaksi yang berjalan lama tidak kelaparan oleh transaksi pendek. Misalnya, jika satu transaksi panjang rata-rata berkonflik dengan tiga transaksi pendek, dan pada setiap konflik pemenangnya pada dasarnya acak, peluang transaksi panjang itu menang ketiganya dan commit hanya 1/8
Namun untuk mencegah starvation, tidak perlu selalu memprioritaskan transaksi yang lebih lama setiap kali; cukup pada sebagian besar kasus. Terutama jika selisih usianya hanya sangat sedikit
Jadi, meskipun ada selisih jam antar-thread atau ketidakakuratan lain, sesuatu seperti timestamp atau cycle counter bisa bekerja dengan baik. Seri bisa dipecahkan dengan ID thread, atau lagi-lagi membuat kedua pihak dibatalkan
Cocok untuk kasus seperti ini dan banyak kasus lain
Two-phase commit adalah sesuatu yang layak dibandingkan dengan Paxos, dan keduanya masuk kategori protokol konsensus
Two-phase locking adalah mekanisme kontrol konkurensi
Ketika pesan lock pertama hilang, masalahnya adalah bagaimana Anda tahu bahwa yang hilang bukan pesan respons
Untuk kasus sederhana, seperti GitHub atau Dropbox, Anda bisa saja lanjut lalu menangani konflik belakangan. Kalau database, semoga beruntung; kalau bank, apalagi
Pada transaksi read-only, TL2 cukup mengambil sampel versi global, lalu untuk semua read memeriksa apakah versi lokal tidak lebih besar dari versi yang disampel
Kalau begitu, sulit memahami mengapa grafiknya sublinear, dan mengapa TL2 tidak secepat implementasi STM lain
Misalnya, katakan ada 1000 tugas biasa dan 10–100 thread hardware
Buat satu daftar terurut berisi 1000 tugas, buat salinannya untuk tiap thread, lalu acak urutan salinan itu setiap kali
Lalu tiap thread cukup membaca daftarnya sendiri dan menjalankan tugas, kemudian berlangganan ke satu daftar yang diimplementasikan sebagai antrean multi-thread non-blocking
Dalam kasus terburuk, beberapa thread bisa mengerjakan tugas tertentu berulang kali
Dengan cara ini, operasi atomik bisa diskalakan hingga 1000 kali lipat