Algoritma / masalah bacaan apa yang Anda rekomendasikan untuk menyelesaikan transaksi / kunci baca-tulis?

10

Transaksi basis data klasik yang disederhanakan dapat dilihat sebagai:

  • membaca item M.
  • melakukan beberapa perhitungan berdasarkan bacaan tersebut
  • menulis beberapa hasil N berdasarkan perhitungan ini, yang dapat mencakup unsur-unsur yang awalnya dibaca.

Saat melakukan transaksi ini (secara bersamaan) properti ACID perlu dipertahankan.

Persis persyaratan yang sama (pembaruan N berdasarkan M membaca secara transaksi) ada di sistem bersamaan non-DBMS lainnya.

Saya tertarik untuk mencari tahu apa algoritma yang ada untuk melakukan / menyelesaikan transaksi ini, dan apa kekuatan dan kelemahan relatif dari algoritma ini. Bisakah Anda merekomendasikan beberapa bacaan? Ini bisa berupa buku atau referensi / tutorial online.

Klarifikasi:

Jadi misalnya, algoritma naif mungkin setiap transaksi mengambil kunci global tunggal, yang berlaku memaksa threading tunggal dan menghapus konkurensi. Algoritma yang sedikit lebih rumit adalah kunci baca / tulis item individual, dengan urutan untuk menghindari kebuntuan). Dll, dll. Apakah ada sumber yang bagus yang mendokumentasikan berbagai algoritma untuk memecahkan masalah ini. Bahkan jawaban yang hanya menunjuk pada satu algoritma dengan kekuatan dan kelemahannya akan berguna.

Nick Fortescue
sumber
3
Pertanyaan ini tentu saja termasuk dalam ruang lingkup situs ini. Saya akan merekomendasikan menulis lebih banyak tentang konteks di mana Anda bekerja. Saat ini agak umum dan terbuka.
Dave Clarke
Apakah Anda pikir itu layak diulangi sehingga justru pertanyaan database? Yaitu sesuatu seperti "Saya memiliki database yang dapat dibaca dan ditulis, dan saya ingin dapat membaca dan menulis secara transaksi dengan properti ACID. Algoritma apa yang ada untuk memastikan properti ini"
Nick Fortescue
Mengulangi pertanyaan dapat menghasilkan jawaban yang lebih dekat dengan apa yang Anda cari, seperti memberikan lebih banyak detail dari masalah yang Anda coba selesaikan; saat ini Anda hanya memberikan petunjuk. Dalam hal apa pun, sepertinya Anda meminta algoritma transaksi basis data klasik.
Dave Clarke
@Dave - terima kasih, saya sudah mengedit. Lebih baik?
Nick Fortescue
1
Apakah Anda sudah terbiasa dengan buku teks DBMS seperti yang oleh Ramakrishnan dan Gehrke? Dan jika Anda tidak bertanya tentang internal DBMS, dapatkah Anda mengklarifikasi pertanyaan untuk memberi tahu kami perbedaan antara DBMS dan apa yang Anda minati?
Maverick Woo

Jawaban:

10

Buku Sistem Informasi Transaksional oleh Weikum dan Vossen mencakup cukup banyak bidang, baik secara teoritis maupun praktis, dari perspektif yang berbeda, bukan hanya transaksi. Panjangnya sekitar 1000 halaman, jadi akan membuat Anda sibuk selama satu atau dua akhir pekan. Di sisi lain, sudah hampir 10 tahun, jadi mungkin ada sesuatu yang lebih up-to-date. Buku-buku lain di baris ini termasuk Kontrol Konkurensi dan Pemulihan dalam Sistem Basis Data oleh Bernstein, P., Hadzilacos, V., dan Goodman, N, Addison-Wesley, 1987, Pemrosesan Transaksi: Konsep dan Teknik oleh Jim Gray dan Andreas Reuter, dan Prinsip Pemrosesan Transaksioleh Philip A. Bernstein dan Eric Newcomer, 2009. Saya belum melihat yang terakhir, tetapi menjadi yang paling baru bisa menjadi tempat yang baik untuk memulai, meskipun solusi Anda mungkin dapat ditemukan dalam teks yang lebih lama. Perjalanan ke perpustakaan mungkin bermanfaat.

Teks monumental di bidang ini adalah Transaksi Atom oleh Nancy Lynch et al. Ini menyajikan akun formal dan bukti dari sejumlah jenis algoritma yang Anda minati. Agak formal, dan membosankan, jadi mungkin tidak sesuai dengan selera Anda.

Banyak pekerjaan baru-baru ini dikhususkan untuk Memori Transaksional Perangkat Lunak , yang menerapkan gagasan transaksi untuk aplikasi multi-utas. Ada puluhan publikasi tentang topik ini setiap tahun: halaman wikipedia menyediakan banyak referensi.

Dave Clarke
sumber
1
terima kasih dave, terutama untuk frasa "Memori transaksional perangkat lunak", saya belum menemukan nama ini
Nick Fortescue
1
STM adalah topik yang sangat panas dalam penelitian bahasa pemrograman hari ini. Ada perlombaan untuk melihat apakah model pemrograman STM atau Aktor akan menjadi dasar bahasa pemrograman konkuren (= semua) di masa depan.
Dave Clarke
1
Selain STM, satu kata kunci tertentu untuk dicari di dalam referensi ini adalah MVCC. Ini digunakan di sebagian besar DBMS modern: en.wikipedia.org/wiki/Multiversion_concurrency_control
Maverick Woo
@supercooldave Saya tidak yakin ini sebuah perlombaan: Saya pikir bahasa di masa depan harus mendukung sedikit dari tingkat tertentu.
Marc Hamann
@Marc Harmann: berbicara secara metaforis.
Dave Clarke