Pemrosesan data kompetitif heterogen real-time secara ketat satu kali

Anotasi

Memproses data secara real time tepat sekali ( tepat sekali ) adalah tugas yang sangat tidak sepele dan membutuhkan pendekatan yang serius dan bijaksana di seluruh rantai perhitungan. Beberapa bahkan percaya bahwa tugas seperti itu tidak mungkin . Pada kenyataannya, saya ingin memiliki pendekatan yang menyediakan pemrosesan yang toleran terhadap kesalahan tanpa penundaan sama sekali dan penggunaan berbagai penyimpanan data, yang mengedepankan persyaratan baru yang bahkan lebih ketat untuk sistem: bersamaan tepat sekali dan heterogenitas lapisan persisten. Sampai saat ini, persyaratan seperti itu tidak mendukung sistem yang ada.

Pendekatan yang diusulkan akan secara konsisten mengungkapkan bahan-bahan rahasia dan konsep-konsep yang diperlukan yang membuatnya relatif mudah untuk mengimplementasikan proses heterogen secara bersamaan tepat satu kali secara harfiah dari dua komponen.

Pendahuluan

Pengembang sistem terdistribusi melalui beberapa tahap:

Tahap 1: Algoritma . Berikut adalah studi tentang algoritma dasar, struktur data, pendekatan pemrograman seperti OOP, dll. Kode secara eksklusif single-threaded. Tahap awal memasuki profesi. Namun, ini cukup rumit dan bisa bertahan bertahun-tahun.

Tahap 2: Multithreading . Selanjutnya, muncul pertanyaan tentang mengekstraksi efisiensi maksimum dari besi, ada multithreading, asynchrony, balap, debugging, strace, malam tanpa tidur ... Banyak yang terjebak pada tahap ini dan bahkan mulai merasakan sensasi yang tidak dapat dijelaskan di beberapa titik. Tetapi hanya sedikit yang memahami arsitektur memori virtual dan model memori, algoritma bebas kunci / tunggu-bebas, dan berbagai model asinkron. Dan hampir tidak ada yang pernah - verifikasi kode multi-threaded.

Tahap 3: Distribusi . Di sini sampah seperti itu terjadi yang tidak ada dalam dongeng atau pena untuk menggambarkan.

Tampaknya sesuatu yang rumit. Kami melakukan transformasi: banyak utas -> banyak proses -> banyak server. Tetapi setiap langkah transformasi membawa perubahan kualitatif, dan semuanya jatuh pada sistem, menghancurkannya dan mengubahnya menjadi debu.

Dan intinya di sini adalah untuk mengubah domain penanganan kesalahan dan ketersediaan memori bersama. Jika sebelumnya selalu ada sepotong memori yang tersedia di setiap utas, dan jika diinginkan, dalam setiap proses, sekarang tidak ada bagian seperti itu dan tidak bisa. Masing-masing untuk dirinya sendiri, mandiri dan bangga.

Jika sebelumnya kegagalan dalam aliran mengubur aliran dan proses pada saat yang sama, dan ini bagus, karena tidak menyebabkan kegagalan parsial, sekarang kegagalan parsial menjadi norma dan setiap kali sebelum setiap tindakan Anda berpikir: "bagaimana jika?". Ini sangat menjengkelkan dan mengalihkan perhatian dari menulis, pada kenyataannya, tindakan itu sendiri bahwa kode karena ini tumbuh tidak pada waktu, tetapi dengan perintah besarnya. Semuanya berubah menjadi mie penanganan kesalahan, pergantian status dan pelestarian konteks, pemulihan karena kegagalan satu komponen, komponen lain, tidak dapat diaksesnya beberapa layanan, dll. dll. Setelah mengacaukan pemantauan untuk semua hal ini, Anda dapat tidur nyenyak di laptop favorit Anda.

Apakah itu masalah multithreading: Saya mengambil mutex dan pergi untuk menghancurkan memori bersama untuk kesenangan. Cantik!

Sebagai hasilnya, kami memiliki bahwa kunci dan pola yang diuji pertempuran diambil, dan yang baru, untuk menggantikannya, untuk beberapa alasan tidak disampaikan, dan ternyata seperti dalam lelucon tentang bagaimana peri melambaikan tongkatnya dan menara jatuh dari tangki.

Namun, sistem terdistribusi memiliki serangkaian praktik yang terbukti dan algoritma yang terbukti. Namun, setiap programmer yang menghargai diri sendiri menganggap tugasnya untuk menolak prestasi terkenal dan mengayuh kebaikannya sendiri, terlepas dari pengalaman yang didapat, sejumlah besar artikel ilmiah dan penelitian akademis. Lagi pula, jika Anda bisa ke dalam algoritma dan multithreading, bagaimana Anda bisa menjadi berantakan dengan distribusi? Tidak ada dua pendapat di sini!

Akibatnya, sistem buggy, data menyimpang dan memburuk, layanan secara berkala menjadi tidak tersedia untuk ditulis, atau bahkan sama sekali tidak tersedia, karena tiba-tiba sebuah node crash, jaringan turun, Java mengkonsumsi banyak memori dan GC membosankan, dan ada banyak alasan lain yang dapat menunda akhirnya kepada pihak berwenang.

Namun, bahkan dengan pendekatan yang terkenal dan terbukti, hidup tidak menjadi lebih mudah, karena primitif andalan terdistribusi adalah kelas berat dengan persyaratan serius untuk logika kode yang dapat dieksekusi. Oleh karena itu, sudutnya terputus sedapat mungkin. Dan, seperti yang sering terjadi, dengan sudut yang tergesa-gesa, kesederhanaan dan skalabilitas relatif muncul, tetapi keandalan, ketersediaan, dan konsistensi sistem terdistribusi menghilang.

Idealnya, saya ingin tidak berpikir sama sekali bahwa sistem kami didistribusikan dan multithreaded, yaitu bekerja pada tahap 1 (algoritma), tanpa memikirkan ke-2 (multithreading + asynchrony) dan ke-3 (distribusi). Cara isolasi abstraksi ini akan secara signifikan meningkatkan kesederhanaan, keandalan, dan kecepatan penulisan kode. Sayangnya, saat ini hanya mungkin dalam mimpi.

Namun, abstraksi individual memungkinkan isolasi relatif. Salah satu contoh khasnya adalah penggunaan coroutine , di mana alih-alih kode asinkron kita menjadi sinkron, mis. kami beralih dari tahap 2 ke tahap 1, yang memungkinkan kami menyederhanakan penulisan dan pemeliharaan kode secara signifikan.

Artikel ini secara berturut-turut mengungkapkan penggunaan algoritma bebas-kunci untuk membangun sistem waktu-nyata yang dapat didistribusikan secara konsisten dan konsisten, mis. bagaimana pencapaian bebas-kunci dari tahap 2 membantu dalam penerapan tahap ke-3, mengurangi tugas menjadi algoritma single-threaded dari tahap 1.

Pernyataan masalah

Tugas ini hanya menggambarkan beberapa pendekatan penting dan disajikan sebagai contoh untuk memasukkan masalah ke dalam konteks. Ini dapat dengan mudah digeneralisasikan ke kasus yang lebih kompleks, yang akan dilakukan di masa depan.

Tugas: pemrosesan data streaming real-time .

Ada dua aliran angka. Pawang membaca data dari aliran input ini dan memilih angka terakhir untuk periode tertentu. Angka-angka ini dirata-rata selama interval waktu ini, yaitu di jendela data geser untuk waktu tertentu. Nilai rata-rata yang diperoleh harus ditulis ke antrian output untuk diproses selanjutnya. Selain itu, jika jumlah angka di jendela melebihi ambang tertentu, kemudian naikkan satu penghitung di basis data transaksional eksternal.

Kami mencatat beberapa fitur dari masalah ini.

1. Non-determinisme . Ada dua sumber perilaku non-deterministik: ini adalah bacaan dari dua aliran, serta jendela waktu. Jelas bahwa membaca dapat dilakukan dengan cara yang berbeda, dan hasil akhir akan tergantung pada urutan data yang akan diekstraksi. Jendela waktu juga mengubah hasil dari awal ke awal, sebagai jumlah data di jendela akan tergantung pada kecepatan pekerjaan.
2. Keadaan pawang . Ada keadaan pawang dalam bentuk serangkaian angka di jendela, di mana hasil saat ini dan selanjutnya dari pekerjaan tergantung. Yaitu kami memiliki penangan yang tegas.
3. Interaksi dengan penyimpanan eksternal . Penting untuk memperbarui nilai penghitung di database eksternal. Poin penting adalah bahwa jenis penyimpanan eksternal berbeda dari penyimpanan keadaan prosesor dan utas.

Semua ini, seperti yang akan ditunjukkan di bawah ini, secara serius mempengaruhi alat yang digunakan dan metode implementasi yang mungkin.

Tetap menambahkan sentuhan kecil pada tugas, yang segera mentransfer tugas dari area yang sangat rumit ke yang tidak mungkin: jaminan secara bersamaan-sekali diperlukan.

Tepat sekali

Tepat-sekali sering ditafsirkan secara luas, yang mengebiri istilah itu sendiri, dan tidak lagi memenuhi persyaratan asli dari tugas tersebut. Jika kita berbicara tentang sistem yang berjalan secara lokal di satu komputer - maka semuanya sederhana: ambil lebih banyak, lanjutkan. Tetapi dalam kasus ini kita berbicara tentang sistem terdistribusi di mana:

1. Jumlah penangan bisa besar: setiap penangan bekerja dengan bagian datanya sendiri. Selain itu, hasilnya dapat ditambahkan ke berbagai tempat, misalnya, database eksternal, bahkan mungkin diacak.
2. Setiap pawang tiba-tiba dapat berhenti memproses. Sistem toleran kesalahan menyiratkan operasi yang berkelanjutan bahkan dalam hal kegagalan bagian-bagian individu dari sistem.

Dengan demikian, kita harus siap dengan kenyataan bahwa pawang bisa jatuh, dan pawang lain harus mengambil pekerjaan yang sudah dilakukan dan melanjutkan pemrosesan.

Pertanyaan segera muncul: apa yang akan berarti sekali jika pawang non-deterministik bekerja? Lagi pula, setiap kali kita memulai ulang, kita akan menerima, secara umum, keadaan yang berbeda. Jawabannya di sini sederhana: dengan tepat-sekali, ada eksekusi sistem di mana setiap nilai input diproses tepat sekali, memberikan hasil keluaran yang sesuai. Selain itu, eksekusi ini tidak harus secara fisik berada pada simpul yang sama. Tetapi hasilnya harus seolah-olah semuanya diproses pada satu node logis tanpa crash .

Bersamaan tepat-sekali

Untuk memperparah persyaratan, kami memperkenalkan konsep baru: bersamaan tepat sekali . Perbedaan mendasar dari sederhana persis-sekali adalah tidak adanya jeda selama pemrosesan, seolah-olah semuanya diproses pada node yang sama tanpa tetes dan tanpa jeda . Dalam tugas kami, kami akan membutuhkan tepat bersamaan satu kali , untuk kesederhanaan presentasi, agar tidak mempertimbangkan perbandingan dengan sistem yang ada yang tidak tersedia saat ini.

Konsekuensi dari memiliki persyaratan seperti itu akan dibahas di bawah ini.

Transaksional

Agar pembaca semakin diilhami oleh kompleksitas yang telah muncul, mari kita lihat berbagai skenario buruk yang harus dipertimbangkan ketika mengembangkan sistem seperti itu. Kami juga akan mencoba menggunakan pendekatan umum yang akan memungkinkan kami untuk menyelesaikan masalah di atas dengan mempertimbangkan persyaratan kami.

Hal pertama yang terlintas dalam pikiran adalah kebutuhan untuk mencatat keadaan pawang dan aliran input dan output. Keadaan aliran keluaran dijelaskan oleh antrian angka yang sederhana, dan keadaan aliran input oleh posisi di dalamnya. Intinya, stream adalah antrian tanpa batas, dan posisi dalam antrian secara unik menentukan lokasi.

Implementasi penangan naif berikut muncul dengan menggunakan semacam gudang data. Pada tahap ini, sifat penyimpanan khusus tidak akan penting bagi kami. Kami akan menggunakan bahasa Pseco untuk menggambarkan ide (Pseco: = kode semu):

handle(input_queues, output_queues, state): #    input_indexes = storage.get_input_indexes() #      while true: #         items, new_input_indexes = input_queues.get_from(input_indexes) #    state.queue.push(items) #     duration state.queue.trim_time_window(duration) avg = state.queue.avg() need_update_counter = state.queue.size() > size_boundary # (A)      output_queues[0].push(avg) if need_update_counter: # (B)      db.increment_counter() # (C)     storage.save_state(state) # (D)    storage.save_queue_indexes(new_input_indexes) # (E)    input_indexes = new_input_indexes 

Berikut adalah algoritma single-threaded sederhana yang membaca data dari input stream dan menulis nilai yang diinginkan sesuai dengan tugas yang dijelaskan di atas.

Mari kita lihat apa yang terjadi jika sebuah node jatuh pada titik yang berubah-ubah dalam waktu, dan juga setelah melanjutkan pekerjaan. Jelas bahwa jika terjadi penurunan pada titik (A) dan (E) semuanya akan baik-baik saja: baik data belum direkam di mana pun dan kami hanya mengembalikan keadaan dan melanjutkan pada simpul lain, atau semua data yang diperlukan telah direkam dan lanjutkan langkah berikutnya.

Namun, jika terjadi kejatuhan di semua titik lain, masalah tak terduga menunggu kita. Jika penurunan terjadi pada titik (B) , maka ketika pawang restart, kami akan mengembalikan keadaan dan merekam ulang nilai rata-rata dalam kisaran kisaran yang sama. Dalam kasus jatuh pada titik (C) selain duplikat rata-rata, duplikat akan terjadi dalam kenaikan nilai. Dan jika terjadi penurunan (D) kita akan mendapatkan status handler yang tidak konsisten: state berhubungan dengan momen baru dalam waktu, dan kita akan membaca nilai dari input yang lama.

Pada saat yang sama, tidak ada yang akan berubah secara fundamental ketika menata ulang operasi perekaman: inkonsistensi dan duplikat akan tetap demikian. Dengan demikian, kita sampai pada kesimpulan bahwa semua tindakan untuk mengubah keadaan penangan dalam repositori, antrian output dan basis data harus dilakukan secara transaksi, yaitu. semuanya atom pada saat bersamaan.

Oleh karena itu, perlu untuk mengembangkan suatu mekanisme sehingga penyimpanan yang berbeda dapat mengubah keadaannya secara transaksi, dan tidak di dalam masing-masing secara independen, tetapi secara transaksial antara semua penyimpanan secara bersamaan. Tentu saja, Anda dapat menempatkan penyimpanan kami di dalam basis data eksternal, namun, tugas tersebut mengasumsikan bahwa mesin basis data dan mesin untuk kerangka kerja pemrosesan data streaming terpisah dan bekerja secara independen satu sama lain. Di sini saya ingin mempertimbangkan kasus yang paling sulit, karena kasus-kasus sederhana tidak menarik untuk dipertimbangkan.

Daya Respons Kompetitif

Pertimbangkan eksekusi kompetitif tepat sekali dengan lebih detail. Dalam kasus sistem toleransi kesalahan, kami membutuhkan kelanjutan pekerjaan dari beberapa titik. Jelas bahwa poin ini akan menjadi poin di masa lalu, karena Untuk mempertahankan kinerja, tidak mungkin untuk menyimpan semua momen perubahan kondisi di masa sekarang dan di masa depan: baik hasil terakhir dari operasi atau sekelompok nilai untuk meningkatkan throughput disimpan. Perilaku ini segera membawa kita pada fakta bahwa setelah pemulihan keadaan prosesor, akan ada beberapa keterlambatan dalam hasil, itu akan meningkat dengan meningkatnya ukuran kelompok nilai dan ukuran negara.

Selain keterlambatan ini, ada juga keterlambatan dalam sistem yang terkait dengan memuat negara ke node lain. Selain itu, pendeteksian simpul masalah juga membutuhkan waktu, dan seringkali banyak. Hal ini disebabkan, pertama-tama, oleh kenyataan bahwa jika kita menetapkan waktu deteksi yang pendek, maka kemungkinan positif palsu adalah mungkin, yang akan mengarah pada semua jenis efek khusus yang tidak menyenangkan.

Selain itu, dengan bertambahnya jumlah prosesor paralel, tiba-tiba ternyata tidak semuanya bekerja dengan baik meskipun tidak ada kegagalan. Terkadang tumpul terjadi, yang juga menyebabkan keterlambatan dalam pemrosesan. Alasan tumpul tersebut dapat bervariasi:

1. Perangkat lunak : Jeda GC, fragmentasi memori, jeda pengalokasi, gangguan kernel dan penjadwalan tugas, masalah dengan driver perangkat yang menyebabkan perlambatan.
2. Perangkat keras : disk tinggi atau beban jaringan, pelambatan CPU karena masalah pendinginan, kelebihan beban, dll., Perlambatan disk karena masalah teknis.

Dan ini sama sekali bukan daftar masalah yang bisa memperlambat penangan.

Karenanya, melambat adalah pemberian yang dengannya seseorang harus hidup. Terkadang ini bukan masalah serius, dan kadang-kadang sangat penting untuk mempertahankan kecepatan pemrosesan yang tinggi meskipun mengalami kegagalan atau perlambatan.

Segera muncul ide duplikasi sistem: mari kita jalankan untuk satu dan aliran data yang sama bukan hanya satu tapi dua prosesor sekaligus, atau bahkan tiga. Masalahnya di sini adalah bahwa dalam kasus ini, duplikat dan perilaku sistem yang tidak konsisten dapat dengan mudah terjadi. Biasanya, kerangka kerja tidak dirancang untuk perilaku ini dan menyarankan bahwa jumlah penangan pada waktu tertentu tidak melebihi satu. Sistem yang memungkinkan duplikasi eksekusi dijelaskan disebut bersamaan tepat sekali .

Arsitektur ini memungkinkan Anda untuk memecahkan beberapa masalah sekaligus:

1. Perilaku gagal: jika salah satu node jatuh, yang lain terus bekerja seolah-olah tidak ada yang terjadi. Tidak perlu koordinasi tambahan, karena pawang kedua dieksekusi terlepas dari kondisi yang pertama.
2. Menghapus tumpul: siapa pun yang pertama kali memberikan hasil itu baik untuknya. Yang lain hanya perlu mengambil negara baru dan melanjutkan dari saat ini.

Pendekatan ini, khususnya, memungkinkan Anda untuk menyelesaikan perhitungan panjang yang sulit, sulit untuk waktu yang lebih mudah diprediksi, karena kemungkinan keduanya akan bodoh dan jatuh jauh lebih sedikit.

Penilaian probabilitas

Mari kita coba mengevaluasi manfaat dari duplikasi kinerja. Misalkan sesuatu terjadi rata-rata setiap hari dengan pawang: baik GC telah tumpul, atau simpul berbohong, atau wadah telah menjadi kanker. Misalkan kita menyiapkan paket data dalam 10 detik.

Maka probabilitas bahwa sesuatu akan terjadi selama pembuatan paket adalah 10 / (24 · 3600) ≃ 1e-4 .

Jika Anda menjalankan dua penangan secara paralel, maka kemungkinan keduanya terbang adalah ≃ 1e-8 . Jadi acara ini akan datang dalam 23 tahun! Ya, sistem tidak hidup banyak, yang berarti ini tidak akan pernah terjadi!

Selain itu, jika waktu persiapan paket akan lebih pendek dan / atau tumpul akan terjadi lebih jarang, maka angka ini hanya akan meningkat.

Dengan demikian, kami menyimpulkan bahwa pendekatan yang dipertimbangkan secara signifikan meningkatkan keandalan seluruh sistem kami. Tetap hanya untuk memecahkan pertanyaan kecil seperti ini: di mana membaca tentang bagaimana membuat sistem konkuren sekali saja . Dan jawabannya sederhana: Anda harus membaca di sini.

Setengah transaksi

Untuk diskusi lebih lanjut, kita perlu konsep setengah transaksi . Cara termudah untuk menjelaskannya adalah dengan sebuah contoh.

Pertimbangkan untuk mentransfer dana dari satu rekening bank ke rekening bank lain. Pendekatan tradisional menggunakan transaksi dalam bahasa Pseco dapat digambarkan sebagai berikut:

 transfer(from, to, amount): tx = db.begin_transaction() amount_from = tx.get(from) if amount_from < amount: return error.insufficient_funds tx.set(from, amount_from - amount) tx.set(to, tx.get(to) + amount) tx.commit() return ok 

Namun, bagaimana jika transaksi ini tidak tersedia untuk kita? Menggunakan kunci, ini bisa dilakukan sebagai berikut:

 transfer(from, to, amount): #         lock_from = db.lock(from) lock_to = db.lock(to) amount_from = db.get(from) if amount_from < amount: return error.insufficient_funds db.set(from, amount_from - amount) db.set(to, db.get(to) + amount) return ok 

Pendekatan ini dapat menyebabkan kebuntuan, seperti kunci dapat diambil dalam urutan berbeda secara paralel. Untuk memperbaiki perilaku ini, cukup dengan memperkenalkan fungsi yang secara bersamaan mengambil beberapa kunci dalam urutan deterministik (misalnya, mengurutkan berdasarkan kunci), yang sepenuhnya menghilangkan kemungkinan deadlock.

Namun, implementasinya dapat disederhanakan:

 transfer(from, to, amount): lock_from = db.lock(from) amount_from = db.get(from) if amount_from < amount: return error.insufficient_funds db.set(from, amount_from - amount) lock_from.release() #   , # .. db.set(db.get...)     lock_to = db.lock(to) db.set(to, db.get(to) + amount) return ok 

Pendekatan ini juga membuat keadaan akhir konsisten, melestarikan invarian dengan jenis mencegah pengeluaran dana yang berlebihan. Perbedaan utama dari pendekatan sebelumnya adalah bahwa dalam implementasi seperti itu kami memiliki periode waktu tertentu di mana akun berada dalam keadaan tidak konsisten. Yaitu, operasi seperti itu menyiratkan bahwa keadaan total dana dalam akun tidak berubah. Dalam kasus ini, ada kesenjangan waktu antara lock_from.release() dan db.lock(to) , di mana database dapat mengembalikan nilai yang tidak konsisten: jumlah total mungkin berbeda dari yang benar ke bawah.

Bahkan, kami membagi satu transaksi untuk mentransfer uang menjadi dua setengah transaksi:

1. Setengah transaksi pertama membuat cek dan mengurangi jumlah yang diperlukan dari akun.
2. Transaksi paruh kedua menulis jumlah yang ditarik ke akun lain.

Jelas bahwa membagi transaksi menjadi yang lebih kecil, secara umum, melanggar perilaku transaksional. Dan contoh di atas tidak terkecuali. Namun, jika semua setengah transaksi dalam rantai terpenuhi sepenuhnya, maka hasilnya akan konsisten dengan semua invarian dipertahankan. Inilah tepatnya yang merupakan properti penting dari rantai setengah transaksi.

Untuk sementara kehilangan beberapa konsistensi, namun demikian kami memperoleh fitur bermanfaat lainnya: kemandirian operasi, dan, sebagai hasilnya, skalabilitas yang lebih baik. Kemandirian dimanifestasikan dalam kenyataan bahwa setengah transaksi setiap kali bekerja hanya dengan satu baris, membaca, memeriksa dan mengubah datanya, tanpa berkomunikasi dengan data lain. Dengan demikian, Anda dapat mengocok basis data yang transaksinya bekerja hanya dengan satu pecahan. Selain itu, pendekatan ini dapat digunakan dalam kasus repositori heterogen, yaitu setengah transaksi dapat dimulai pada satu jenis penyimpanan, dan berakhir pada yang lain. Ini adalah properti yang sangat berguna yang akan digunakan di masa depan.

Muncul pertanyaan yang sah: bagaimana menerapkan setengah trans dalam sistem terdistribusi dan tidak menyapu? Untuk mengatasi masalah ini, Anda perlu mempertimbangkan pendekatan bebas kunci.

Bebas kunci

Seperti yang Anda ketahui, pendekatan bebas-kunci terkadang meningkatkan kinerja sistem multi-utas, khususnya dalam hal akses kompetitif ke sumber daya. Namun, sama sekali tidak jelas bahwa pendekatan semacam itu dapat digunakan dalam sistem terdistribusi. Mari kita menggali lebih dalam dan mempertimbangkan apa yang bebas kunci dan mengapa properti ini akan berguna dalam menyelesaikan masalah kita.

Beberapa pengembang terkadang tidak begitu mengerti apa itu bebas kunci. Pandangan picik menunjukkan bahwa ini adalah sesuatu yang terkait dengan instruksi prosesor atom. Penting untuk dipahami di sini bahwa penguncian bebas berarti penggunaan "atom", sebaliknya tidak benar, yaitu, tidak semua "atom" memberikan perilaku bebas kunci.

Properti penting dari algoritma bebas kunci adalah setidaknya satu utas membuat kemajuan dalam sistem. Tetapi karena beberapa alasan, banyak atribut properti ini sebagai definisi (itu adalah definisi yang tumpul yang dapat ditemukan, misalnya, di Wikipedia ). Di sini perlu menambahkan satu nuansa penting: kemajuan dibuat bahkan dalam kasus tumpul satu atau lebih utas. Ini adalah poin yang sangat kritis yang sering diabaikan dan memiliki implikasi serius bagi sistem terdistribusi.

Mengapa tidak adanya kondisi kemajuan setidaknya satu utas meniadakan konsep algoritma bebas kunci? Faktanya adalah bahwa dalam kasus ini spinlock biasa juga akan bebas kunci. Memang, orang yang mengambil kunci akan membuat kemajuan. Apakah ada utas dengan progres => bebas kunci?

Jelas, tanpa kunci berarti tanpa kunci, sementara spinlock dengan namanya menunjukkan bahwa ini adalah kunci yang sebenarnya. Itulah sebabnya penting untuk menambahkan kondisi pada kemajuan, bahkan dalam kasus tumpul. Lagi pula, penundaan ini bisa bertahan tanpa batas waktu, karena definisi tidak mengatakan apa-apa tentang garis waktu atas. Dan jika demikian, maka penundaan tersebut akan setara dalam arti dengan mematikan arus. Dalam hal ini, algoritma bebas kunci akan menghasilkan kemajuan dalam kasus ini.

Tetapi siapa yang mengatakan pendekatan bebas kunci berlaku secara eksklusif untuk sistem multi-utas? Mengganti thread dalam proses yang sama pada node yang sama dengan proses pada node yang berbeda, dan memori bersama dari thread dengan penyimpanan terdistribusi bersama, kami mendapatkan algoritma terdistribusi bebas kunci.

Penurunan node dalam sistem seperti itu sama dengan penundaan dalam pelaksanaan utas untuk beberapa waktu, karena saatnya memulihkan pekerjaan. Pada saat yang sama, pendekatan bebas-kunci memungkinkan peserta lain dalam sistem terdistribusi untuk terus bekerja. Selain itu, algoritma bebas kunci khusus dapat dijalankan secara paralel satu sama lain, mendeteksi perubahan kompetitif, dan memotong duplikat.

Pendekatan Tepat sekali menyiratkan adanya penyimpanan terdistribusi yang konsisten. Penyimpanan seperti itu sebagai aturan mewakili tabel nilai kunci yang persisten besar. Kemungkinan operasi: set , get , del . Namun, operasi yang lebih rumit diperlukan untuk pendekatan bebas kunci: CAS atau compare-and-swap. Mari kita pertimbangkan lebih rinci operasi ini, kemungkinan penggunaannya, serta hasil apa yang diberikannya.

Cas

CAS atau compare-and-swap adalah primitif sinkronisasi utama dan penting untuk algoritma bebas kunci dan tunggu. Esensinya dapat diilustrasikan oleh Pseco berikut:

 CAS(var, expected, new): # ,   atomic,   atomic: if var.get() != expected: return false var.set(new) return true 

Kadang-kadang, untuk optimasi, mereka mengembalikan tidak true atau false , tetapi nilai sebelumnya, karena sangat sering operasi seperti itu dilakukan dalam satu lingkaran, dan untuk mendapatkan nilai yang expected , Anda harus terlebih dahulu membacanya:

 CAS_optimized(var, expected, new): # ,   atomic,   atomic: current = var.get() if current == expected: var.set(new) return current #  CAS   CAS_optimized CAS(var, expected, new): return var.CAS_optimized(expected, new) == expected 

Pendekatan ini dapat menghemat satu bacaan. Sebagai bagian dari tinjauan kami, kami akan menggunakan bentuk CAS sederhana, karena jika diinginkan, optimasi tersebut dapat dilakukan secara independen.

Dalam hal sistem terdistribusi, setiap perubahan diversi. Yaitu pertama-tama kita membaca nilai dari toko, mendapatkan versi data saat ini. Dan kemudian kami mencoba menulis, berharap bahwa versi data tidak berubah. Dalam hal ini, versi bertambah setiap kali data diperbarui:

 CAS_versioned(var, expected_version, new): atomic: if var.get_version() != expected_version: return false var.set(new, expected_version + 1) return true 

Pendekatan ini memungkinkan Anda untuk lebih akurat mengontrol pembaruan nilai, menghindari masalah ABA . Khususnya, versi didukung oleh Etcd dan Zookeeper.

Perhatikan properti penting yang CAS_versioned operasi CAS_versioned . Faktanya adalah bahwa operasi seperti itu dapat diulang tanpa mengurangi logika superior. Dalam pemrograman multi-utas, properti ini tidak memiliki nilai khusus, karena di sana, jika operasi gagal, maka kita tahu pasti bahwa itu tidak berlaku. Dalam kasus sistem terdistribusi, invarian ini dilanggar, karena permintaan dapat mencapai penerima, tetapi respons yang berhasil tidak ada lagi. Oleh karena itu, penting untuk dapat mengirim ulang permintaan tanpa takut melanggar invarian logika tingkat tinggi.

Properti inilah yang CAS_versioned operasi CAS_versioned . Bahkan, operasi ini dapat diulang tanpa henti hingga respons nyata dari penerima dikembalikan. Yang, pada gilirannya, melempar seluruh kelas kesalahan yang terkait dengan interaksi jaringan.

Contoh

Mari kita lihat bagaimana, berdasarkan CAS_versioned dan setengah transaksi, untuk mentransfer dari satu akun ke akun lain, yang termasuk, misalnya, ke salinan Etcd yang berbeda. Di sini, saya berasumsi bahwa fungsi CAS_versioned sudah diterapkan berdasarkan pada API yang disediakan.

 withdraw(from, amount): # CAS- while true: #     version_from, amount_from = from.get_versioned() if amount_from < amount: return error.insufficient_funds if from.CAS_versioned(version_from, amount_from - amount): break return ok deposit(to, amount): # CAS- while true: version_to, amount_to = to.get_versioned() if to.CAS_versioned(version_to, amount_to + amount): break return ok transfer(from, to, amount): #   if withdraw(from, amount) is ok: #     , #    deposit(to, amount) 

Di sini kami membagi operasi kami menjadi setengah transaksi, dan kami melakukan setiap setengah transaksi melalui operasi CAS_versioned . Pendekatan ini memungkinkan Anda untuk bekerja secara independen dengan masing-masing akun, memungkinkan penggunaan penyimpanan heterogen yang tidak terhubung satu sama lain. Satu-satunya masalah yang menunggu kita di sini adalah hilangnya uang jika terjadi penurunan proses saat ini dalam interval antara setengah transaksi.

Antrian

Untuk melanjutkan, Anda perlu mengimplementasikan antrian acara. Idenya adalah agar penangan berkomunikasi satu sama lain, Anda harus memiliki antrian pesan yang dipesan di mana data tidak hilang atau digandakan. Dengan demikian, semua interaksi dalam rantai penangan akan dibangun di atas primitif ini. Ini juga merupakan alat yang berguna untuk menganalisis dan mengaudit aliran data yang masuk dan keluar. Selain itu, mutasi dari keadaan penangan juga dapat dilakukan melalui antrian.

Antrean akan terdiri dari sepasang operasi:

1. Tambahkan pesan ke akhir antrian.
2. Menerima pesan dari antrian di indeks yang ditentukan.

Dalam konteks ini, saya tidak mempertimbangkan menghapus pesan dari antrian karena beberapa alasan:

1. Beberapa prosesor dapat membaca dari antrian yang sama. Menghapus sinkronisasi akan menjadi tugas yang tidak sepele, meskipun bukan tidak mungkin.
2. Berguna untuk menjaga antrian untuk interval yang relatif panjang (hari atau minggu) untuk debugging dan audit. Kegunaan properti ini sulit ditaksir terlalu tinggi.
3. Anda dapat menghapus item lama baik sesuai jadwal atau dengan mengatur TTL pada item antrian. Penting untuk memastikan bahwa prosesor mengelola untuk memproses data sebelum sapu tiba dan membersihkan semuanya. Jika waktu pemrosesan adalah urutan detik, dan TTL urutan hari, maka tidak ada yang terjadi.

Untuk menyimpan elemen dan mengimplementasikan penambahan secara efektif, kita perlu:

1. Nilai dengan indeks saat ini. Indeks ini menunjuk ke akhir antrian untuk menambahkan item.
2. , .

lock-free

: . :

1. CAS .
2. .

, , .

1. lock-free . , , . Lock-free? ! , 2 : . lock-free, — ! , , , . . , .. , .
2. . , . .

, lock-free .

Lock-free

, , : , .. , :

 push(queue, value): #      index = queue.get_current_index() while true: #  ,    #    var = queue.at(index) #  = 0   , ..   # ,         if var.CAS_versioned(0, value): #   ,    queue.update_index(index + 1) break #   , .   index = max(queue.get_current_index(), index + 1) update_index(queue, index): while true: #     cur_index, version = queue.get_current_index_versioned() #      , #  , .   if cur_index >= index: # -     , #        break if queue.current_index_var().CAS_versioned(version, index): #      ,   break # -  . # ,      ,   

. , ( — , , ). lock-free . ?

, push , ! , , .

. : . , - , - . , , .. . . ? , .. , , .

, , . .. . , , . , .

, . , . , , . , .

, , , .

. .

, :

1. , .. stateless.
2. , — .

, , concurrent exactly-once .

:

 handle(input, output): index = 0 while true: value = input.get(index) output.push(value) index += 1 

. :

 handle(input, output, state): #   index = state.get() while true: value = input.get(index) output.push(value) index += 1 #   state.set(index) 

exactly-once . , , , .

exactly-once , , . .., , , , , — :

 #       get_next_index(queue): index = queue.get_index() #     while queue.has(index): #    queue.push index = max(index + 1, queue.get_index()) return index #      . #  true    push_at(queue, value, index): var = queue.at(index) if var.CAS_versioned(0, value): #   queue.update_index(index + 1) return true return false handle(input, output, state): #   #    {PREPARING, 0} fsm_state = state.get() while true: switch fsm_state: case {PREPARING, input_index}: #   :   , #        output_index = output.get_next_index() fsm_state = {WRITING, input_index, output_index} case {WRITING, input_index, output_index}: value = input.get(input_index) if output.push_at(value, output_index): #  ,     input_index += 1 #    ,  push_at  false, #        fsm_state = {PREPARING, input_index} state.set(fsm_state) 

push_at ? , . , , , . , . . - , lock-free .

, :

1. : .
2. , : .

: concurrent exactly-once .

? :

1. , , push_at false. .
2. , . , , .

concurrent exactly-once ? , , . , . .

:

 #     ,  ,     # ..       true, #      true. #       false push_at_idempotent(queue, value, index): return queue.push_at(value, index) or queue.get(index) == value handle(input, output, state): version, fsm_state = state.get_versioned() while true: switch fsm_state: case {PREPARING, input_index}: #   ,   , #        output_index = output.get_next_index() fsm_state = {WRITING, input_index, output_index} case {WRITING, input_index, output_index}: value = input.get(input_index) #   , #       if output.push_at_idempotent(value, output_index): input_index += 1 fsm_state = {PREPARING, input_index} #     if state.CAS_versioned(version, fsm_state): version += 1 else: #   ,    version, fsm_state = state.get_versioned() 

:

, . , .

kernel panic, , .. . . : , . , .

, , .

: .

: , , , , :

 #  : # - input_queues -   # - output_queues -   # - state -    # - handler -    : state, inputs -> state, outputs handle(input_queues, output_queues, state, handler): #        version, fsm_state = state.get_versioned() while true: switch fsm_state: # input_indexes       case {HANDLING, user_state, input_indexes}: #       inputs = [queue.get(index) for queue, index in zip(input_queues, input_indexes)] #   ,    next_indexes = next(inputs, input_indexes) #    #     user_state, outputs = handler(user_state, inputs) #      , #     fsm_state = {PREPARING, user_state, next_indexes, outputs, 0} case {PREPARING, user_state, input_indexes, outputs, output_pos}: #  ,      #    output_index = output_queues[output_pos].get_next_index() #     fsm_state = { WRITING, user_state, input_indexes, outputs, output_pos, output_index } case { WRITING, user_state, input_indexes, outputs, output_pos, output_index }: value = outputs[output_pos] #       if output_queues[output_pos].push_at_idempotent( value, output_index ): #  ,      output_pos += 1 #    ,      PREPARING. #     #     fsm_state = if output_pos == len(outputs): #   , #       {HANDLING, user_state, input_indexes} else: #       #   , #         {PREPARING, user_state, input_indexes, outputs, output_pos} if state.CAS_versioned(version, fsm_state): version += 1 else: #   ,    version, fsm_state = state.get_versioned() 

:

: HANDLING . , .., , . , . , PREPARING WRITING , . , HANDLING .

, , , . , . , .

. . .

:

 my_handler(state, inputs): #      state.queue.push(inputs) #    duration state.queue.trim_time_window(duration) #   avg = state.queue.avg() need_update_counter = state.queue.size() > size_boundary return state, [ avg, if need_update_counter: true else: # none      none ] 

, , concurrent exactly-once handle .

:

 handle_db(input_queue, db): while true: #      tx = db.begin_transaction() #     . #      , #      index = tx.get_current_index() #    tx.write_current_index(index + 1) #      value = intput_queue.get(index) if value: #    tx.increment_counter() tx.commit() #   ,      , #           

. Karena , , , , concurrent exactly-once . .

— . , , .

, , . , , .

. , . Karena , . . .

— . , , . , - , , . , .. , , .

. , , . , , .

. , . : , . , .

, , :

1. , . .
2. . , .
3. . , . , , . .. . : .

, , -, , -, .

, . :

 transfer(from, to, amount): #   if withdraw(from, amount) is ok: #     , #    deposit(to, amount) 

withdraw , , deposit : ? deposit - (, , ), . , , , , ? , , - , .

, , , . , , , . , . , , . Karena , , . , : , — .

, .

: , , , , . , - :

• . , , , , .
• . .

, , .

, , .. , , . , .

: lock-free , . , .. , .

CAS . , :

 #     ,    handle(input, output, state): # ... while true: switch fsm_state: case {HANDLING, ...}: #      fsm_state = {PREPARING, ...} case {PREPARING, input_index}: #   ... output_index = ...get_next_index() fsm_state = {WRITING, output_index, ...} case {WRITING, output_index, ...}: #  ,  output_index 

, . . :

1. PREPARING . , .
2. WRITING . . , PREPARING .

, . , , — . :

1. . , , .. , .
2. , .. . , .

, lock-free , , .

, . , Stale Read , . — CAS: . :

• Distributed single register — (, etcd Zookeeper):
  
  1. Linearizability
  2. Sequential consistency
• Transactional — (, MySQL, PostgreSQL ..):
  
  1. Serializability
  2. Snapshot Isolation
  3. Repeatable Read
  4. Read Committed
• Distributed Transactional — NewSQL :
  
  1. Strict Consistency

: ? , , . , , CAS . , , Read My Writes .

Kesimpulan

exactly-once . , .. , , , . , , , , .. , .

lock-free .

:

1. : .
2. : .
3. : : exactly-once .
4. Concurrent : .
5. Real-time : .
6. Lock-free : , .
7. Deadlock free : , .
8. Race condition free : .
9. Hot-hot : .
10. Hard stop : .
11. No failover : .
12. No downtime : .
13. : , .
14. : .
15. : .
16. : .

, . Tapi itu cerita lain.

:

1. Concurrent exactly-once.
2. Semi-transactions .
3. Lock-free two-phase commit, .

1. .
2. lock-free .
3. .

Sastra

[1] Wikipedia: Masalah ABA.
[2] Blog: Anda Tidak Bisa Memiliki Pengiriman Tepat-Sekali
[3] Habr: Keterjangkauan dari batas bawah pada waktu pelaksanaan komit dari transaksi gagal-aman terdistribusi.
[4] Habr: Asynchrony 3: model subjektif.
[5] Wikipedia: Sinkronisasi non-pemblokiran.