Halo semuanya!
Hari ini kami ingin sekali lagi menyinggung topik eksekusi simultan dan berurutan dalam berbagai program, terutama dalam sistem terdistribusi. Kembali pada bulan September, kami menerbitkan artikel "
Sinkronisasi adalah mitos " pada topik ini, dan sekarang kami menerbitkan terjemahan studi yang lebih serius, yang, kami harap, akan membantu Anda menavigasi lebih baik dengan sistem terdistribusi.
Hanya ada satu masalah nyata dalam ilmu komputer: untuk mengakui bahwa kesalahan validasi cache tidak disebutkan dengan benar. Ini hanya kesalahan unit yang terkait dengan penggunaan waktu.
- Penulis tidak dikenal
Waktu adalah hal yang aneh.
Waktu ini sangat aneh, karena kami benar-benar ingin percaya bahwa itu sepenuhnya efisien. Tampaknya bagi kita bahwa peristiwa apa pun pada pukul 15.00 terjadi (seperti yang akan kita katakan) sebelum peristiwa apa pun pada pukul 16.00 - tanpa pengecualian, argumen, atau kompromi.
Namun, ilmu komputer tahu banyak contoh ketika perlu untuk mendekati persyaratan ini tidak begitu ketat. Ini memanifestasikan dirinya di tingkat prosesor, kompiler, node jaringan. Berkali-kali dalam perhitungan, pada tingkat tumpukan yang berbeda, kita menemukan diri kita dalam situasi di mana kita dihadapkan dengan dua peristiwa, dan kita tidak tahu dalam urutan apa mereka terjadi. Waktu jelas tidak total; dia terfragmentasi.
Mengapa Faktanya adalah bahwa kita tidak mengetahui hal ini, karena tingkat abstraksi yang kita miliki tidak memberikan jawaban untuk pertanyaan ini. Apakah itu kebetulan atau tidak, abstraksi komputasi kami tidak memberikan jaminan mengenai prosedur ini. Kebebasan untuk menyusun ulang acara sering kali memungkinkan Anda membuat sistem yang jauh lebih produktif dan terjangkau.
Prosesor mungkin memiliki
model pemesanan memori ; itu mencerminkan jaminan apa yang prosesor tidak ingin memberi Anda jaminan pada tahap perakitan - misalnya, instruksi mana yang dieksekusi sebelumnya dan yang kemudian. Prosesor memutuskan dengan tepat bagaimana menyampaikan instruksi dan mengeksekusi mereka keluar dari urutan - yaitu, menggunakan chip lebih efisien daripada yang saya kira.
Suatu bahasa mungkin memiliki
model pencocokan memori ("model memori" singkatnya); itu mencerminkan jaminan apa yang tidak diberikan oleh bahasa itu saat membuat perakitan, misalnya, ketika mendistribusikan instruksi di banyak utas. Penataan ulang seperti itu secara inheren melekat dalam model perangkat keras memori dan untuk sebagian besar menjelaskan mengapa konsep waktu "lemah" disediakan dalam kompiler. Hal ini dalam kerangka model memori yang diterapkan dalam bahasa yang Anda program ketika Anda menulis kode non-blocking.
Contoh terkenal dari model memori yang diimplementasikan pada tingkat bahasa adalah
model memori yang kuat dan lemah dalam standar C ++ 11. Secara default, C ++ menyediakan operasi atom dengan sinkronisasi, tetapi juga dapat melemahkan model akses memori untuk meningkatkan kinerja. Perilaku yang disediakan dengan cara ini dimaksudkan untuk berfungsi sebagai abstraksi atas arsitektur prosesor utama yang digunakan saat ini (x86, POWER, dan ARM).
Akhirnya, sistem terdistribusi mungkin memiliki model konsistensi sendiri; itu mencerminkan jaminan apa yang sistem tidak akan berikan kepada Anda mengenai urutan kejadian pada klien dan replika di jaringan komputer global. Perekam ulang yang berhubungan langsung dengan latensi komunikasi atau kurangnya sinkronisasi terutama menjelaskan mengapa dalam sistem terdistribusi Anda tidak dapat melakukannya tanpa model waktu yang lemah tersebut. Model konsistensi inilah yang Anda program ketika Anda menulis aplikasi terdistribusi.
Dalam praktiknya, ada banyak sekali model konsistensi yang dapat Anda gunakan saat memprogram sistem terdistribusi. Dalam semua situasi seperti itu, model-model ini menggambarkan perilaku (yang diinginkan) dari sistem yang diamati dari luar sistem itu. Jika saya - klien tertentu atau aliran tertentu - menulis nilai, kemudian segera membacanya, apakah dijamin bahwa saya pasti akan melihat catatan yang tidak lebih lama dari milik saya? Jika waktu tidak terfragmentasi, jika kita selalu memiliki ide yang jelas dalam urutan apa operasi dalam sistem kita berlangsung - tentu saja, jawaban untuk pertanyaan ini adalah di afirmatif. Akan aneh untuk bertanya seperti itu sama sekali.
Tetapi waktu itu terpisah-pisah - karena itu, perlu untuk mengajukan pertanyaan seperti itu.
Model Konsistensi - Maksud saya, model memori
Berbicara tentang keteraturan yang terfragmentasi seperti ini seringkali sulit dan selalu tidak menyenangkan. Kami ingin memulai dari fakta bahwa di semua tingkat tumpukan, waktu selalu mutlak absolut - baik dengan transaksi ACID atau operasi / kunci atom. Semakin ketat jaminan, semakin mudah diprogram dengan mereka!
Tapi kita semua berusaha untuk kecepatan. Apakah itu tentang sistem terdistribusi di mana pengorbanan konsistensi yang ketat demi aksesibilitas harus dikorbankan, atau tentang pemrograman non-blocking, di mana model memori yang lemah digunakan untuk menghindari biaya sinkronisasi, biasanya disarankan bagi seorang programmer yang bekerja dengan tingkat tumpukan apa saja untuk masuk ke argumen kompleks ini. .
Konsistensi model memori bersama dan konsistensi model memori terdistribusi keduanya
abstrak . Mereka menggambarkan pemrogram bekerja dengan sistem, antarmuka sistem ini. Mereka memungkinkan untuk memahami tipe perilaku mana yang sesuai dengan model memori yang lemah, mengingat sekarang bahwa sifat umum dari urutan peristiwa dalam sistem, yang kita terima begitu saja, tidak lagi bertindak di dalamnya. Tampaknya kedua model memori ini serupa, namun kedua komunitas telah mengembangkan wacana mereka sendiri untuk diskusi. Nilai yang digunakan di dalamnya berbeda, meskipun tumpang tindih.
Kita sudah membayangkan betapa bingungnya hal ini. Apa yang harus dilakukan
Deskripsi waktu sebagai entitas, menyiratkan suatu tempat dari dua hingga delapan jenis urutan parsial
Dalam
bukunya 2014, Sebastian Burkhardt berusaha untuk memberikan deskripsi lengkap tentang banyak pilihan untuk model konsistensi. Dengan karakteristik ini, bersama dengan struktur matematika lainnya, dua varian dari urutan logis peristiwa digunakan: "visibilitas" dan "arbitrasi", yang sebelumnya juga disebutkan dalam karya-karya lain Burkhardt et al, lihat, misalnya,
artikel tentang menunjuk dan memeriksa tipe data yang direplikasi (2014).
"Visibilitas" adalah urutan parsial yang melekat dalam pengondisian potensial. Hal ini memungkinkan Anda untuk melacak peristiwa mana (mungkin dalam replika lain) yang terlihat dengan peristiwa lainnya. Tidak ada persyaratan untuk visibilitas selain asiklisitas; peristiwa dalam suatu objek dapat terlihat oleh peristiwa di objek lain, dan operasi membaca atau menulis suatu peristiwa tidak mempengaruhi visibilitasnya untuk peristiwa lain.
"Arbitrase" adalah urutan umum yang memungkinkan Anda melacak bagaimana sistem terdistribusi di mana situasi pilihan muncul akan menilai peristiwa mana yang terjadi lebih awal dan yang kemudian.
Karena model konsistensi terdistribusi mirip dengan model memori, ternyata fenomena visibilitas dan keacakan seperti itu juga dapat berguna ketika membahas model memori. Secara khusus,
dalam lampiran artikelnya 2014, Burkhardt menunjukkan "seberapa dekat" model memori lemah dari C ++ 11 dengan konsistensi kausal berbasis objek, tetapi dengan beberapa penyimpangan yang menarik. Ini akan dibahas di sisa posting.
Untuk mulai dengan, mari kita menyempurnakan visibilitas dan keacakan, dengan mempertimbangkan "membaca" dan "urutan perubahan". Ketika "membaca", visibilitas antara dua objek akan diperhitungkan hanya dalam situasi di mana membaca dan menulis menyentuh objek yang sama, dan ketika membaca hanya satu catatan (atau lebih dari satu) dapat terlihat.
Ini sesuai dengan situasi di mana prosesor dengan memori bersama pada waktu tertentu dapat merekam informasi hanya dalam satu sel memori untuk objek tertentu, bahkan jika utas yang berbeda dapat mengaksesnya pada momen sebab dan akibat yang berbeda (di sisi lain, dalam sistem terdistribusi, logis suatu objek dapat direkam segera dalam banyak replika terpisah).
"Modifikasi pesanan" sesuai dengan tahap yang sama ketika mengkonkretkan kesewenang-wenangan, itu objektif dan hanya memungkinkan rekaman. Sekali lagi, spesialisasi ini didasarkan pada kenyataan bahwa, dengan spesifikasi memori yang lemah, jaminan kategoris hanya diberikan pada tingkat satu objek.
Selanjutnya, mari kita bahas aksioma konsistensi yang dirumuskan oleh Burkhardt et al. Dan lihat bagaimana mereka berlaku untuk model memori yang lemah. Harap dicatat: meskipun ada kata "aksioma", ini hanyalah properti yang mungkin atau mungkin tidak disediakan dalam berbagai model memori. Artikel Burkhardt berfokus pada sifat-sifat yang menentukan kausalitas objek-silang.
Koherensi akhirnya
Untuk peristiwa tertentu, tidak mungkin ada banyak peristiwa tanpa batas yang tidak dapat melihatnya. Artinya, setiap peristiwa
pada akhirnya dapat dilihat oleh sistem.
Secara logis membangun kondisi seperti itu dalam sistem dengan model memori yang lemah harus agak lebih sulit: harus diperdebatkan bahwa untuk
catatan tertentu tidak boleh ada jumlah tak terbatas operasi baca yang tidak akan membaca catatan ini atau catatan sebelumnya (dalam urutan modifikasi).
Dalam spesifikasi C ++ 11, kepatuhan terhadap aksioma ini tidak dijamin, meskipun dalam praktiknya sulit untuk menemukan contoh tandingan.
Konsistensi Ethereal
Saat melacak "kondisionalitas potensial" pada tingkat arus / operasi klien dan terkait dengan visibilitas / keterbacaan, Anda perlu memahami bahwa tidak ada waktu pengembalian. Itu sebabnya diperlukan bahwa penutupan ketika memesan aliran menyiratkan membaca asiklik. Sebagai aturan, tidak ada keraguan bahwa properti ini akan diamati dalam sistem terdistribusi, namun properti inilah yang tidak memungkinkan visibilitas pengguna dalam beberapa versi spekulatif jika sistem memiliki model memori yang lemah.
Burkhardt et al. Menunjukkan bahwa aksioma ini "tidak dikonfirmasi" dalam spesifikasi C ++ 11, dan tidak jelas "tidak memvalidasi" apakah "siklus yang memuaskan" dapat
diamati dalam praktek .
Aksioma Kondisionalitas
Untuk menentukan secara pasti apa yang terkait dengan fenomena kondisionalitas di bawah model memori yang lemah, kita harus secara tepat menentukan peristiwa mana yang dapat mempengaruhi hasil peristiwa lainnya. Untuk memulai, pertimbangkan aksioma sebab-akibat standar kami:
jaminan sesi . Ini adalah empat kualitas yang saling terkait yang mencerminkan sifat koherensi operasi baca dan tulis yang terjadi dalam aliran yang berbeda, apalagi, mereka harus ditentukan pada tingkat setiap objek (lihat
Burkhardt et al .,
Gbr. 23 ).
- RYW (Baca catatan Anda): operasi baca setelah operasi tulis dilakukan dalam sel yang sama, dalam aliran / replika / sesi yang sama, itu harus membaca data yang tidak kalah relevan dari catatan. Varian dari properti ini untuk sistem terdistribusi ditentukan secara khusus dalam hal visibilitas, sedangkan varian untuk model memori yang lemah harus didasarkan pada urutan membaca dan urutan perubahan.
- MR (bacaan monolitik): bacaan selanjutnya (dalam aliran yang sama, dalam sel yang sama) juga harus melihat data yang tidak kurang relevan di masa depan.
- WFR (baca pertama, lalu tulis): jika menulis mengikuti pembacaan di dalam aliran, dalam sel yang sama, maka dalam urutan perubahan harus lebih lambat dari operasi baca.
- MW (Catatan Monolitik): catatan yang lebih baru (di dalam aliran, dalam sel yang sama) harus masuk kemudian dalam urutan modifikasi.
Versi asli WFR dan MW ada dalam dua versi, untuk keacakan dan visibilitas; tetapi ini hanya penting ketika bekerja dengan sel data yang lebih kompleks daripada dengan register untuk integer.
Sifat-sifat ini mencerminkan pengertian kondisionalitas, konsisten dengan akal sehat kita; Namun, mereka melewatkan yang paling menarik. Khususnya, ketika menganalisis dalam model memori yang lemah, fenomena kondisionalitas seperti itu dibatasi oleh batas-batas aliran / replika / sesi dan sel / objek spesifik tempat entri dibuat:
dalam sebuah artikel oleh Burkhardt et al . dalam hal ini dikatakan tentang "visibilitas kondisional objek-oleh-kondisional" dan "kesewenang-wenangan objek-demi-kondisional", juga lihat gambar. 23. Fenomena ini tidak sepenuhnya membatasi perilaku sistem ketika aliran yang berbeda menulis informasi ke sel yang berbeda.
Kemudian aksioma pengkondisian objek-silang menggambarkan efek hubungan sebab-akibat pada level berbagai objek / sel memori.
- COCV (Cross-Object Conditional Visibility): kasus yang sama dengan RYW, tetapi tanpa syarat pembacaan akhir harus dilakukan semua dalam utas / replika / sesi yang sama. Pembacaan dari suatu objek yang secara obyektif lebih lambat dari catatan dalam objek ini harus mengambil data yang tidak kurang relevan dari yang dimasukkan selama perekaman.
Spesifikasi C ++ 11 mencerminkan properti ini. Harap dicatat: mereka didefinisikan sedemikian rupa sehingga pembatasan pencatatan visibilitas dan kesewenang-wenangan dari urutan modifikasi tidak terlalu mencerminkan definisi ini.
Tetapi ini tidak berlaku untuk properti yang terakhir.
- COCA (Cross-Object Conditional Arbitrary): mirip dengan catatan monolitik, tetapi berlaku untuk aliran yang berbeda, mirip dengan COCV - itu adalah RYW untuk aliran yang berbeda. Namun, karena urutan modifikasi hanya mempengaruhi rekaman dalam satu objek, formulasi untuk model memori yang lemah memungkinkan sistem untuk memiliki distribusi yang tidak konsisten dari peristiwa perekaman di objek yang berbeda, dan catatan mungkin tidak sesuai dengan bacaan atau urutan dalam aliran.
Secara khusus, COCA dalam model memori yang lemah adalah properti yang jauh lebih lemah. Itulah sebabnya dengan model memori yang lemah, kode berikut dapat mengembalikan
{x ≡ 0, y ≡ 0} .
Thread A: y := 0; x := 1; return x
Thread B: x := 0; y := 1; return yUrutan dalam setiap aliran mungkin tidak konsisten dengan urutan objek-oleh-pesanan dan urutan modifikasi. Harap dicatat: dengan RYW tidak ada
x := 0 → x := 1 dalam urutan modifikasi dan untuk
y sama; dengan demikian, urutan modifikasi harus mengandung
x := 1 → x := 0 dan
y := 1 → y := 0 . Jadi, urutan modifikasi jelas membentuk siklus dalam urutan arus.
Perulangan semacam itu diizinkan dalam COCA dengan model memori yang lemah. Bukan berarti urutan aliran / membaca bertentangan dengan urutan modifikasi, tetapi bahwa setiap aliran melihat riwayat catatan yang konsisten. Kisah-kisah ini konsisten dengan kisah-kisah aliran lain hanya jika kita secara objektif membatasi ruang lingkup penerapannya.
Apa artinya semua ini?
Waktu terfragmentasi.
Meskipun bagi kami tampaknya waktu mengalir dengan tertib, mempelajari sistem terdistribusi dan model memori yang lemah jelas menunjukkan kepada Anda bahwa ini tidak benar. Itulah sebabnya dalam kedua situasi ini, perkiraan standar kami yang berlebihan, yang sesuai dengan waktu total, membatasi kinerja - yang tidak dapat kami mampu.
Kemudian, mengakui bahwa waktu benar-benar terfragmentasi, kami menemukan banyak perbedaan kecil namun penting antara varietas keberpihakan seperti itu. Bahkan dua bidang yang disebutkan di atas, yang tampak sangat mirip pada pandangan pertama, dalam banyak nuansa halus memungkinkan untuk membedakan jenis peristiwa tertentu yang dianggap saling mempengaruhi.
Hal ini diperlukan untuk memahami secara lebih rinci rincian teknis dari berbagai properti yang sudah ada setelah seseorang dapat mengekspresikan properti dari satu bidang dalam bahasa yang lain.
Waktu terfragmentasi. Mungkin kita hanya perlu membiasakan diri dengannya.