Siapa yang butuh linierabilitas?

Saya telah membaca tentang perbedaan antara serializability dan linearizability , yang keduanya merupakan kriteria konsistensi untuk sistem yang direplikasi seperti database yang direplikasi. Namun, saya tidak tahu dalam hal apa linierabilitas akan diperlukan, meskipun itu lebih kuat dari serializability.

Bisakah Anda membuat skenario di mana properti kuat seperti itu sebenarnya diperlukan?

Pertimbangkan desain struktur data concurrent, wait-free (atau lock-free, yang lebih lemah). Dalam skenario ini, linearitas umumnya diperlukan, meskipun dalam beberapa kasus, kinerja dan skalabilitas dapat ditingkatkan dengan memenuhi kondisi ketelitian yang lebih lemah. Apakah suatu implementasi memuaskan kondisi yang lemah seperti itu bermanfaat biasanya tergantung pada aplikasi. Sebaliknya, implementasi linearizable selalu dapat digunakan, karena desainer dapat melihatnya sebagai atom.

Selain itu, linearizability adalah properti non-blocking: operasi total (didefinisikan untuk semua status objek) tidak pernah diperlukan untuk memblokir. Sebaliknya, Serializability bukan properti non-pemblokiran. Oleh karena itu, untuk meningkatkan derajat konkurensi, perancang struktur data konkuren selalu mengandalkan linierabilitas.

Saya telah membaca ulang Herlihy dan Wing berkali-kali selama 15 tahun terakhir. Ini adalah bacaan yang sangat sulit. Dan itu sangat disayangkan, karena sementara ada beberapa seluk-beluk di sekitar tepi ide dasarnya sebenarnya cukup masuk akal.

Singkatnya: linearizability seperti serializability, tetapi dengan persyaratan tambahan bahwa serialisasi menghormati kendala pemesanan tambahan antara transaksi. Tujuannya adalah untuk memungkinkan Anda untuk berpikir secara keras tentang struktur data atom individu daripada harus mempertimbangkan seluruh sistem sekaligus.

Linearizability juga mudah dicapai: cukup kaitkan sebuah mutex dengan objek yang ingin Anda linearkan. Setiap transaksi pada objek itu dimulai dengan mengunci mutex dan selesai dengan membuka kunci mutex.

Berikut adalah definisi yang akan saya gunakan:

Suatu sistem adalah serializabile jika diberikan satu set transaksi atas satu set data, setiap hasil dari mengeksekusi transaksi adalah sama seperti jika transaksi dieksekusi dalam urutan berurutan, dan operasi dalam setiap transaksi terkandung dalam transaksi mereka dalam urutan ditentukan oleh kode transaksi.

Serializability melarang penampilan interleaving operasi antara transaksi yang berbeda, dan mensyaratkan bahwa urutan transaksi yang dipilih memenuhi hubungan sebab akibat (jika transaksi A menulis nilai x, dan transaksi B membaca nilai x yang ditulis A, maka transaksi A harus mendahului transaksi B di urutan serial yang dipilih.) Tapi itu tidak mengatakan apa pun tentang kendala lain pada pemesanan transaksi (khususnya, itu tidak mengatakan apa-apa tentang proses dan urutan di mana proses melihat peristiwa.)

Ada ide terkait lainnya yang menambahkan kendala tentang urutan proses operasi yang dijalankan (tetapi tidak berbicara tentang transaksi, hanya operasi baca / tulis individual):

Suatu sistem konsisten berurutan jika hasil dari setiap eksekusi adalah sama seperti jika operasi dari semua proses dieksekusi dalam urutan berurutan, dan operasi dari setiap proses individu muncul dalam urutan ini dalam urutan yang ditentukan oleh programnya. ( Lamport, "Cara Membuat Komputer Multiprosesor yang Menjalankan Program Multiproses dengan Benar", IEEE T Comp 28: 9 (690-691), 1979 ).

Tersirat dalam definisi konsistensi berurutan adalah bahwa kami hanya menerima pesanan berurutan di mana untuk setiap lokasi memori (objek) urutan operasi berurutan yang dipatuhi mematuhi aturan bahwa nilai yang dikembalikan oleh setiap operasi baca ke lokasi xharus sama dengan nilai yang ditulis oleh operasi penulisan segera sebelumnya ke lokasi xdalam urutan berurutan.

Linearizability memiliki niat baik untuk (a) menggabungkan bersama gagasan transaksi (dari serialisasi) dengan gagasan bahwa proses mengharapkan operasi yang mereka selesaikan agar (dari konsistensi berurutan) dan (b) mempersempit kriteria kebenaran untuk berbicara tentang masing-masing objek dalam isolasi, daripada memaksa Anda untuk alasan tentang sistem secara keseluruhan. (Saya ingin dapat mengatakan bahwa implementasi objek saya benar bahkan dalam sistem di mana ada objek lain yang tidak linierisasi.) Saya percaya Herlihy dan Wing mungkin telah mencoba untuk mendefinisikan monitor secara ketat .

Bagian (a) adalah "mudah": Persyaratan seperti konsistensi sekuensial akan bahwa transaksi pada objek yang dikeluarkan oleh setiap proses muncul dalam urutan yang dihasilkan dalam urutan yang ditentukan oleh program. Persyaratan seperti serialisasi adalah bahwa transaksi pada objek semuanya saling eksklusif (dapat diserialisasi).

Kompleksitas berasal dari tujuan (b) (dapat berbicara tentang setiap objek secara independen dari yang lain).

Dalam suatu sistem dengan banyak objek adalah mungkin bahwa operasi pada objek B menempatkan batasan pada urutan di mana kami percaya operasi dipanggil pada objek A. Jika kita melihat keseluruhan sejarah sistem maka kita akan dibatasi pada urutan berurutan tertentu, dan perlu menolak orang lain. Tetapi kami menginginkan kriteria kebenaran yang dapat kami gunakan secara terpisah (dengan alasan apa yang terjadi pada objek A tanpa menarik sejarah sistem global).

Sebagai contoh: misalkan saya mencoba untuk berdebat tentang kebenaran objek A, yang merupakan antrian, misalkan objek B adalah lokasi memori, dan anggap saya memiliki sejarah eksekusi berikut: Thread 1: A.enqueue (x), A. dequeue () (mengembalikan y). Thread 2: A.enqueue (y), A.dequeue () (mengembalikan x). Apakah ada interleaving peristiwa yang akan memungkinkan implementasi antrian ini menjadi benar? Iya:

Thread 1                           Thread 2
A.enqueue(x)                       ...
...                                A.enqueue(y)
...                                A.dequeue() (returns x)
A.dequeue(y) (returns y)           ...

Tetapi sekarang bagaimana jika sejarah ( termasuk objek B ) adalah: B dimulai dengan nilai 0. Thread 1: A.enqueue (x), A.dequeue () (mengembalikan y), B.write (1). Thread 2: B.read () (pengembalian 1) A.enqueue (y), A.dequeue () (pengembalian x).

Thread 1                           Thread 2
A.enqueue(x)                       ...
A.dequeue() (returns y)            ...                       (uh oh!)
B.write(1)                         ...
...                                B.read() (returns 1)
...                                A.enqueue(y)
...                                A.dequeue() (returns x)

Sekarang kami ingin definisi kami tentang "kebenaran" untuk mengatakan bahwa sejarah ini menunjukkan bahwa implementasi A kami adalah buggy atau implementasi B kami adalah buggy, karena tidak ada serialisasi yang "masuk akal" (baik Thread 2 perlu dibaca nilai dari B yang belum ditulis, atau Thread 1 perlu membagikan nilai dari A yang belum di enqueued.) Jadi, sementara serialisasi asli kami dari transaksi pada A tampak seperti yang wajar, jika implementasi kami memungkinkan riwayat seperti yang kedua, maka jelas salah.

Jadi kendala yang ditambahkan linearisasi cukup masuk akal (dan perlu bahkan untuk struktur data sederhana seperti antrian FIFO). Mereka adalah hal-hal seperti: "implementasi Anda harus melarang dequeue () nilai yang tidak akan enqueued () sampai beberapa waktu di masa depan." Linearizability cukup mudah (dan alami) untuk dicapai: cukup kaitkan sebuah mutex dengan objek Anda, dan setiap transaksi dimulai dengan mengunci dan mengakhiri dengan membuka kunci. Penalaran tentang linearitas mulai menjadi rumit ketika Anda mencoba menerapkan atomicity Anda dengan teknik non-blocking atau lock-free atau wait-free alih-alih mutex sederhana.

Jika Anda tertarik pada beberapa petunjuk pada literatur, saya menemukan yang berikut (walaupun saya pikir diskusi tentang "real-time" adalah salah satu red-herring yang membuat linearizabilty lebih sulit daripada yang seharusnya.) Https: // stackoverflow.com/questions/4179587/difference-between-linearizability-and-serializability

Pertama, linearizability dan serializability tidak dapat dibandingkan secara langsung. Seperti yang ditunjukkan tabel di bawah ini, perbedaan utama adalah bahwa di sisi kiri, semua operasi individu adalah atomik (seperti memiliki java di synchronizedsekitar setiap operasi . Di sisi kanan, unit atomisitas adalah transaksi; operasi individu bukan atomik Itulah sebabnya mengapa Serializability selalu menjadi bagian dari literatur basis data, sementara sisi kiri telah menjadi subjek literatur prosesor-memori (baca / tulis op adalah atomik). Nilai Kunci asli menyimpan (seperti dbm dan memcached) dimulai dari sisi kiri (get / put is atomic), tetapi yang lebih baru semakin mendukung transaksi (seperti spanner Google).

obj. operasi adalah atom | Transaksi bersifat atomik
-------------------------------- + ----------------- ----------------
Kemampuan linierisasi |
Konsistensi Berurutan | Serializability
Konsistensi Kausal |
Konsistensi Cache |

Linearizability mensyaratkan bahwa sistem objek dalam pengaturan konkuren harus berperilaku identik dengan sistem sekuensial yang menangani satu operasi (pasangan permintaan / respons) pada suatu waktu - dalam alam semesta paralel - sedemikian rupa sehingga (a) klien di kedua alam semesta melihat respons yang persis sama (b) keteraturan temporal dipertahankan (lebih lanjut tentang ini di bawah).

Definisi Serializability, seperti Sequential Consistency, hanya memerlukan kriteria pertama.

Pelestarian pesanan temporal berarti ini: jika A: x.op1 () (A adalah klien, x adalah objek, dan op1 adalah operasi) selesai sebelum operasi lain B: y.op2 () dimulai, maka di alam semesta berurutan, permintaan ditangani dalam urutan yang sama. Ini tidak diperlukan dalam Sequential Consistency (SC); objek diizinkan untuk mengantri permintaan klien, menanggapi klien, lalu mengevaluasi nanti. Lebih jauh, objek mungkin menangani permintaan kemudian dari beberapa klien lain secara bergiliran, mengevaluasinya sebelum sampai ke yang pertama.

Non-pelestarian tatanan sementara adalah masalah. Setelah A: x.op1 (), misalkan A mengangkat telepon dan memberi tahu B tentang hal itu, kemudian B memanggil panggilan x.op2 (). Tidak ada cara bagi sistem untuk mengetahui rantai sebab akibat ini, karena langkah kedua melibatkan pesan yang tidak dilacak oleh sistem. Dalam banyak kasus nyata, tidak beralasan bagi A untuk berasumsi bahwa sekali x telah meresponsnya, permohonan B dapat bergantung pada keadaan yang diperbarui. Jika urutan waktu tidak dipertahankan, A dan B akan terkejut. Ini tidak akan terjadi dalam sistem linearizable.

Properti bagus kedua dari pelestarian tatanan temporal adalah lokalitas dan komposisionalitas, bahwa sistem yang dibangun dari objek-objek yang dapat linierisasi itu sendiri dapat liniarizable. Jadi, alih-alih memiliki satu toko kunci-nilai monolitik, Anda dapat membuangnya ke banyak partisi terpisah yang masing-masing dikelola oleh server toko-KV sendiri; jika masing-masing dari mereka adalah linearizable, seluruh basis data berfungsi sebagai satu toko KV monolitik liniarizable, tanpa usaha ekstra.