Prompt dan kes penggunaan
Terangkan perbezaan antara linearizability dan sequential consistency, berikan sejarah baca/tulis di mana kedua-duanya berbeza, dan terangkan kompromi antara ketekalan, kependaman, dan ketersediaan dalam sistem teragih. Ini ialah soalan susulan yang berguna untuk peranan reka bentuk sistem, backend, data, dan infrastruktur.
Ini bukan ujian perbendaharaan kata. Penemu duga mahukan satu sejarah yang boleh disahkan yang menggabungkan nilai terkini, susunan masa nyata, susunan bagi setiap klien, dan kelewatan replika.
Perkara yang dinilai oleh penemu duga
- Sama ada anda menyatakan bahawa operasi linearizable kelihatan berkuat kuasa serta-merta antara seruan (invocation) dan respons.
- Sama ada anda menyatakan sequential consistency memerlukan satu susunan global yang mengekalkan susunan program setiap benang (thread), tetapi bukan susunan masa nyata merentasi benang.
- Sama ada anda boleh membuktikan perbezaan tersebut dengan contoh lawan (counterexample) dan bukannya sekadar mengatakan bahawa satu model adalah "lebih kuat".
- Sama ada anda mengaitkan model-model ini dengan mod bacaan dan kos dalam sistem seperti etcd.
Penjelasan sebelum menjawab
Tanya sama ada perbincangan berkenaan dengan satu objek atau satu transaksi, satu klien atau banyak klien, dan sama ada masa seruan dan respons diketahui. Linearizability biasanya menerangkan objek serentak; transaksi pelbagai objek memerlukan jaminan keatoman (atomicity) dan pemencilan (isolation) tambahan.
Jawapan 30 saat
Linearizability memerlukan susunan global yang mematuhi masa nyata: penulisan yang telah selesai mestilah boleh dilihat oleh bacaan yang bermula selepasnya. Sequential consistency hanya mengekalkan susunan program bagi setiap benang, jadi operasi daripada benang yang berbeza boleh disusun semula. Bacaan lapuk selepas penulisan melanggar linearizability; apabila panggilan bertindih, susunan global masih boleh meletakkan bacaan terlebih dahulu dan memenuhi sequential consistency. Model yang lebih kuat memerlukan lebih banyak penyelarasan, yang menelan kos kependaman dan ketersediaan semasa sekatan (partition).
Penjelasan langkah demi langkah
Huraikan sejarah operasi
Rekod masa seruan, masa respons, benang, argumen, dan hasil untuk setiap operasi. Linearizability memilih satu titik antara setiap seruan dan respons supaya semua operasi membentuk pelaksanaan benang tunggal yang sah dan operasi yang selesai mengekalkan susunan masa nyatanya.
Peraturan sequential consistency
Sequential consistency memerlukan satu jujukan global di mana operasi setiap benang muncul dalam susunan programnya sendiri. Operasi daripada benang yang berbeza boleh disusun semula walaupun susunan jam dinding (wall-clock) wujud, asalkan sejarah tersebut tidak mempunyai kekangan masa nyata yang diperlukan.
Garis masa contoh lawan
Benang A: write(x=1) kembali; benang B kemudian menyeru read(x) dan mendapat 0. Untuk objek yang sama, sejarah tersebut tidak boleh dilinearkan (linearized). Jika selang panggilan bertindih, sistem boleh meletakkan bacaan B sebelum penulisan A dalam jujukan global, memenuhi sequential consistency sambil melanggar susunan masa nyata.
~~~text Linearizable: A: write(1) ---- returns B: read() -> 1
Not linearizable: A: write(1) ---- returns B: read() -> 0
Sequentially consistent but not necessarily linearizable: A: write(1) ========= B: read() -> 0 ========= Global order may place B before A when the calls overlap. ~~~
Perbezaan dengan eventual consistency
Eventual consistency menjanjikan penumpuan (convergence) selepas penulisan berhenti dan masa yang mencukupi berlalu. Ia membenarkan bacaan lapuk dan tidak menyediakan read-your-writes atau monotonic reads secara automatik. Linearizability memberikan semantik masa nyata yang lebih kukuh, biasanya dengan menghalakan bacaan dan penulisan melalui ketua (leader) atau korum.
Jawapan model
Saya menerangkan linearizability sebagai ilusi satu salinan masa nyata: setiap operasi mempunyai titik kelinearan antara seruan dan respons, semua operasi membentuk sejarah berjujukan yang sah, dan operasi yang selesai mengekalkan susunan masa nyatanya. Sequential consistency hanya memerlukan sejarah global yang mengekalkan susunan program setiap benang, jadi susunan masa nyata rentas benang mungkin hilang.
Jika A menulis 1 dan kembali sebelum B mula membaca, tindakan B mengembalikan 0 melanggar linearizability. Jika selang panggilan bertindih, bacaan B boleh muncul sebelum penulisan A dalam sejarah global dan masih memenuhi sequential consistency. Pilih model daripada keperluan perniagaan: kunci (locks), pajakan (leases), dan kemas kini bersyarat sering memerlukan linearizability; indeks carian dan replika analitik mungkin menerima semantik yang lebih lemah untuk kependaman yang lebih rendah dan ketersediaan yang lebih tinggi.
Kesilapan lazim
- Memanggil sistem sebagai "ketekalan kuat" (strongly consistent) tanpa menyatakan susunan masa nyata.
- Menerangkan sequential consistency sebagai pengisihan masa pelayan dan bukannya peraturan susunan program bagi setiap benang.
- Mengatakan eventual consistency "akhirnya membaca nilai terkini" tanpa membincangkan read-your-writes atau monotonic reads.
- Menganggap korum secara automatik bermaksud linearizability tanpa menyemak sama ada bacaan menyertai laluan konsensus.
- Menganggap linearizability objek tunggal sebagai pemencilan penuh untuk transaksi pelbagai objek.
Soalan susulan dan respons
Mengapa kos linearizability biasanya lebih tinggi?
Bacaan mungkin memerlukan pengesahan daripada ketua semasa atau korum, menambah perjalanan ulang-alik merentasi rantau. Semasa sekatan rangkaian, sistem mungkin menolak permintaan daripada mengembalikan hasil yang melanggar susunan masa nyata.
Di manakah sequential consistency lebih lemah?
Ia tidak mengekalkan susunan jam dinding merentasi benang. Sebarang jujukan global yang mengekalkan susunan program setiap benang boleh menjadi sah, menjadikan senario "penulisan yang selesai tidak dapat dilihat oleh bacaan kemudian" lebih mudah disembunyikan.
Apakah mod bacaan etcd?
etcd mendokumentasikan jaminan linearizable secara lalai. Bacaan serializable mungkin mengembalikan data lapuk relatif kepada korum, menukar risiko tersebut untuk kependaman yang lebih rendah dan daya pemprosesan (throughput) yang lebih tinggi. Kaitkan mod tersebut dengan risiko perniagaan dan bukannya menamakan konfigurasi secara berasingan.
Bagaimanakah anda menguji linearizability?
Rekod masa seruan dan respons, benang, input, dan hasil, kemudian cari susunan kelinearan yang sah. Suntik kelewatan, jeda proses, dan pertukaran ketua; ujian yang hanya berjalan secara berjujukan tidak dapat mendedahkan kegagalan penting.
Bilakah eventual consistency mencukupi?
Suapan (feeds), indeks carian, dan laporan boleh menerima kelapukan terikat (bounded staleness) apabila produk membuat kompromi tersebut secara eksplisit. Penulisan penting mungkin masih memerlukan read-your-writes, nombor versi, atau laluan muat semula eksplisit.
Bagaimanakah anda mengakhiri jawapan?
Mulakan dengan garis masa, nyatakan kekangan model, dan selesaikan dengan jaminan perniagaan serta kos kependaman dan ketersediaannya. Itu menunjukkan kefahaman yang lebih mendalam daripada sekadar membaca slogan CAP.