Penguncian diedarkan menggunakan Redis

Hai Habr!

Hari ini kami membawa kepada perhatian anda terjemahan artikel yang kompleks tentang pelaksanaan penguncian yang diedarkan menggunakan Redis dan menjemput anda untuk bercakap tentang prospek Redis sebagai topik. Analisis algoritma Redlock yang dipersoalkan dari Martin Kleppmann, pengarang buku "Aplikasi Beban Tinggi", diberikan di sini.

Penguncian teragih ialah primitif yang sangat berguna yang digunakan dalam banyak persekitaran di mana proses yang berbeza mesti berfungsi pada sumber yang dikongsi dengan cara yang saling eksklusif.

Terdapat beberapa perpustakaan dan siaran di luar sana yang menerangkan cara melaksanakan DLM (Pengurus Kunci Teragih) menggunakan Redis, tetapi setiap perpustakaan mengambil pendekatan yang berbeza dan jaminan yang mereka berikan agak lemah berbanding dengan apa yang boleh dicapai dengan reka bentuk yang lebih canggih sedikit.

Dalam artikel ini kami akan cuba menerangkan algoritma kanonik bersyarat yang menunjukkan cara melaksanakan penguncian teragih menggunakan Redis. Kami akan bercakap tentang algoritma yang dipanggil Redlock, ia melaksanakan pengurus kunci teragih dan, pada pendapat kami, algoritma ini lebih selamat daripada pendekatan satu contoh biasa. Kami berharap komuniti akan menganalisisnya, memberikan maklum balas dan menggunakannya sebagai titik permulaan untuk projek yang lebih kompleks atau alternatif.

Perlaksanaan

Sebelum beralih kepada perihalan algoritma, kami menyediakan beberapa pautan ke pelaksanaan siap sedia. Mereka boleh digunakan untuk rujukan.

• Redlock-rb (pelaksanaan untuk Ruby). Terdapat juga garpu Redlock-rb, yang menambah pakej (permata) untuk memudahkan pengedaran, dan bukan sahaja untuk itu.
• Redlock-py (Pelaksanaan Python).
• Airedlock (pelaksanaan untuk Asyncio Python).
• Redlock-php (pelaksanaan untuk PHP).
• PHPRedisMutex (pelaksanaan lain untuk PHP)
• cheprasov/php-redis-lock (Perpustakaan PHP untuk kunci)
• Redsync (pelaksanaan untuk Go).
• Redisson (pelaksanaan untuk Java).
• Redis::DistLock (pelaksanaan untuk Perl).
• Redlock-cpp (pelaksanaan untuk C++).
• Redlock-cs (pelaksanaan untuk C#/.NET).
• RedLock.net (pelaksanaan untuk C#/.NET). Dengan sokongan untuk sambungan tak segerak dan kunci.
• ScarletLock (pelaksanaan untuk C# .NET dengan stor data boleh dikonfigurasikan)
• Redlock4Net (pelaksanaan untuk C# .NET)
• nod-redlock (pelaksanaan untuk NodeJS). Termasuk sokongan untuk memanjangkan kunci.

Jaminan Keselamatan dan Ketersediaan

Kami akan memodelkan reka bentuk kami dengan hanya tiga sifat yang kami fikir memberikan jaminan minimum yang diperlukan untuk menggunakan penguncian teragih dengan berkesan.

1. Harta keselamatan: Pengecualian bersama. Pada bila-bila masa, hanya seorang pelanggan boleh memegang kunci.
2. Ketersediaan Harta A: Tiada kebuntuan. Ia sentiasa mungkin untuk memperoleh kunci, walaupun pelanggan yang mengunci sumber gagal atau mendarat pada segmen cakera yang berbeza.
3. Ketersediaan Harta B: Toleransi Kesalahan. Selagi majoriti nod Redis sedang berjalan, pelanggan dapat memperoleh dan melepaskan kunci.

Mengapa pelaksanaan berdasarkan pemulihan kegagalan tidak mencukupi dalam kes ini
Untuk memahami perkara yang akan kami perbaiki, mari kita analisa keadaan semasa dengan kebanyakan perpustakaan kunci yang diedarkan berdasarkan Redis.

Cara paling mudah untuk mengunci sumber menggunakan Redis ialah mencipta kunci dalam contoh itu. Biasanya, kunci dicipta dengan jangka hayat terhad, ini dicapai menggunakan ciri tamat tempoh yang disediakan dalam Redis, jadi lambat laun kunci ini dikeluarkan (harta 2 dalam senarai kami). Apabila pelanggan perlu melepaskan sumber, ia memadamkan kunci.

Pada pandangan pertama, penyelesaian ini berfungsi dengan baik, tetapi terdapat masalah: seni bina kami mencipta satu titik kegagalan. Apakah yang berlaku jika contoh Redis hos gagal? Jom tambah budak! Dan kami akan menggunakannya jika penyampai tidak tersedia. Malangnya, pilihan ini tidak berdaya maju. Dengan melakukan ini, kami tidak akan dapat melaksanakan dengan betul sifat pengecualian bersama yang kami perlukan untuk memastikan keselamatan, kerana replikasi dalam Redis adalah tak segerak.

Jelas sekali, dalam model sedemikian keadaan perlumbaan berlaku:

1. Pelanggan A memperoleh kunci pada induk.
2. Tuan gagal sebelum entri kunci dipindahkan kepada hamba.
3. Pengikut dinaikkan pangkat menjadi ketua.
4. Pelanggan B memperoleh kunci pada sumber yang sama yang telah dikunci oleh A. PELANGGARAN KESELAMATAN!

Kadang-kadang adalah perkara biasa bahawa dalam keadaan khas, seperti kegagalan, ramai pelanggan boleh memegang kunci pada masa yang sama. Dalam kes sedemikian, penyelesaian berasaskan replikasi boleh digunakan. Jika tidak, kami mengesyorkan penyelesaian yang diterangkan dalam artikel ini.

Pelaksanaan yang betul dengan satu contoh

Sebelum cuba mengatasi kelemahan konfigurasi satu contoh yang diterangkan di atas, mari kita fahami cara mengendalikan kes mudah ini dengan betul, kerana penyelesaian ini sebenarnya sah dalam aplikasi di mana keadaan perlumbaan boleh diterima dari semasa ke semasa, dan juga kerana menyekat pada contoh tunggal berfungsi sebagai asas yang digunakan dalam algoritma teragih yang diterangkan di sini.

Untuk mendapatkan kunci, lakukan ini:

SET resource_name my_random_value NX PX 30000

Perintah ini memasang kunci hanya jika ia belum wujud (pilihan NX), dengan tempoh sah 30000 milisaat (pilihan PX). Kunci ditetapkan kepada "myrandomvalue" Nilai ini mestilah unik merentas semua pelanggan dan semua permintaan kunci.
Pada asasnya, nilai rawak digunakan untuk melepaskan kunci dengan selamat, dengan skrip memberitahu Redis: hanya keluarkan kunci jika ia wujud dan nilai yang disimpan di dalamnya adalah tepat seperti yang diharapkan. Ini dicapai menggunakan skrip Lua berikut:

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

Ini penting untuk mengelakkan kunci yang dipegang oleh pelanggan lain daripada ditanggalkan. Sebagai contoh, pelanggan mungkin memperoleh kunci, kemudian menjadi terkunci dalam beberapa operasi yang bertahan lebih lama daripada kunci pertama (supaya kunci mempunyai masa untuk tamat tempoh), dan kemudian mengeluarkan kunci yang telah diletakkan oleh pelanggan lain.
Menggunakan DEL mudah adalah tidak selamat kerana pelanggan boleh mengeluarkan kunci yang dipegang oleh pelanggan lain. Sebaliknya, apabila menggunakan skrip di atas, setiap kunci "ditandatangani" dengan rentetan rawak, jadi hanya pelanggan yang meletakkannya sebelum ini boleh mengeluarkannya.

Apakah rentetan rawak ini? Saya rasa ia sepatutnya 20 bait daripada /dev/urandom, tetapi anda boleh mencari cara yang lebih murah untuk menjadikan rentetan cukup unik untuk tujuan anda. Sebagai contoh, adalah baik untuk menyemai RC4 dengan /dev/urandom dan kemudian menjana aliran pseudo-rawak daripadanya. Penyelesaian yang lebih mudah melibatkan gabungan masa unix dalam resolusi mikrosaat ditambah dengan ID pelanggan; ia tidak begitu selamat, tetapi ia mungkin terpulang kepada tugas dalam kebanyakan konteks.

Masa yang kita gunakan sebagai ukuran jangka hayat kunci dipanggil "seumur hidup kunci". Nilai ini ialah kedua-dua jumlah masa sebelum kunci dilepaskan secara automatik dan jumlah masa pelanggan perlu menyelesaikan operasi sebelum pelanggan lain boleh mengunci sumber itu, tanpa benar-benar melanggar jaminan pengecualian bersama. Jaminan ini terhad hanya pada tetingkap masa tertentu, yang bermula dari saat kunci dibeli.

Oleh itu, kami telah membincangkan cara yang baik untuk memperoleh dan melepaskan kunci. Sistem (jika kita bercakap tentang sistem tidak teragih yang terdiri daripada satu contoh dan sentiasa tersedia) adalah selamat. Mari kita lanjutkan konsep ini kepada sistem teragih, di mana kita tidak mempunyai jaminan sedemikian.

Algoritma kunci merah

Versi algoritma yang diedarkan mengandaikan bahawa kami mempunyai master N Redis. Nod ini bebas sepenuhnya antara satu sama lain, jadi kami tidak menggunakan replikasi atau sistem koordinasi tersirat yang lain. Kami telah membincangkan cara memperoleh dan melepaskan kunci dengan selamat pada satu kejadian. Kami mengambil mudah bahawa algoritma, apabila bekerja dengan satu contoh, akan menggunakan kaedah ini dengan tepat. Dalam contoh kami, kami menetapkan N kepada 5, yang merupakan nilai yang munasabah. Oleh itu, kita perlu menggunakan 5 induk Redis pada komputer atau mesin maya yang berbeza untuk memastikan bahawa mereka bertindak secara bebas antara satu sama lain.

Untuk memperoleh kunci, pelanggan melakukan operasi berikut:

1. Mendapat masa semasa dalam milisaat.
2. Secara berurutan cuba mendapatkan kunci pada semua kejadian N, menggunakan nama kunci yang sama dan nilai rawak dalam semua kes. Dalam Peringkat 2, apabila pelanggan menyediakan kunci pada asas setiap kejadian, pelanggan menggunakan kelewatan untuk memperolehnya yang cukup singkat berbanding dengan masa selepas itu kunci dilepaskan secara automatik. Sebagai contoh, jika tempoh penyekatan ialah 10 saat, maka kelewatan boleh berada dalam julat ~5-50 milisaat. Ini menghapuskan situasi di mana pelanggan boleh kekal disekat untuk masa yang lama cuba mencapai nod Redis yang gagal: jika contoh tidak tersedia, maka kami cuba menyambung ke contoh lain secepat mungkin.
3. Untuk mengambil kunci, pelanggan mengira berapa banyak masa telah berlalu; Untuk melakukan ini, ia menolak daripada nilai masa sebenar cap masa yang diperolehi dalam langkah 1. Jika dan hanya jika pelanggan dapat mendapatkan kunci pada majoriti kejadian (sekurang-kurangnya 3), dan jumlah masa yang diambil untuk mendapatkan kunci, kurang daripada tempoh kunci, kunci dianggap telah diperolehi.
4. Jika kunci telah diperoleh, tempoh kunci diambil sebagai tempoh kunci asal tolak masa berlalu yang dikira dalam langkah 3.
5. Jika pelanggan gagal mendapatkan kunci atas sebab tertentu (sama ada ia tidak dapat mengunci kejadian N/2+1 atau tempoh kunci adalah negatif), maka ia akan cuba membuka kunci semua kejadian (walaupun yang difikirkannya tidak dapat disekat ).

Adakah algoritma tidak segerak?

Algoritma ini berdasarkan andaian bahawa, walaupun tidak ada jam yang disegerakkan di mana semua proses akan berfungsi, waktu tempatan dalam setiap proses masih mengalir pada kadar yang lebih kurang sama, dan ralat adalah kecil berbanding dengan jumlah masa selepas kunci itu dikeluarkan secara automatik. Andaian ini sangat serupa dengan situasi biasa untuk komputer biasa: setiap komputer mempunyai jam tempatan, dan kita biasanya boleh bergantung pada fakta bahawa perbezaan masa antara komputer yang berbeza adalah kecil.

Pada ketika ini, kita mesti lebih berhati-hati merumuskan peraturan pengecualian bersama kami: pengecualian bersama dijamin hanya jika pelanggan yang memegang kunci keluar semasa kunci itu sah (nilai ini diperoleh dalam langkah 3), tolak beberapa masa lagi (jumlah beberapa milisaat untuk mengimbangi perbezaan masa antara proses).

Artikel menarik berikut memberitahu lebih lanjut tentang sistem sedemikian yang memerlukan penyelarasan selang masa: Pajakan: mekanisme toleransi kesalahan yang cekap untuk ketekalan cache fail yang diedarkan.

Cuba semula pada kegagalan

Apabila pelanggan gagal memperoleh kunci, ia mesti mencuba lagi selepas kelewatan rawak; ini dilakukan untuk menyahsegerakkan berbilang pelanggan yang cuba mendapatkan kunci pada sumber yang sama pada masa yang sama (yang boleh membawa kepada situasi "otak berpecah" di mana tiada pemenang). Selain itu, lebih pantas pelanggan cuba mendapatkan kunci pada kebanyakan contoh Redis, lebih sempit tetingkap di mana situasi otak berpecah boleh berlaku (dan semakin kurang keperluan untuk mencuba semula). Oleh itu, sebaik-baiknya, pelanggan harus cuba menghantar arahan SET kepada keadaan N secara serentak menggunakan pemultipleksan.

Perlu ditekankan di sini betapa pentingnya pelanggan yang gagal memperoleh majoriti kunci untuk melepaskan kunci (sebahagian) yang diperoleh, supaya mereka tidak perlu menunggu kunci tamat tempoh sebelum kunci pada sumber boleh diperoleh semula (walaupun jika pemecahan rangkaian berlaku, dan pelanggan terputus hubungan dengan contoh Redis, maka anda perlu membayar penalti ketersediaan sementara menunggu kunci tamat tempoh).

Lepaskan kunci

Melepaskan kunci ialah operasi mudah yang hanya memerlukan membuka kunci semua kejadian, tidak kira sama ada pelanggan nampaknya telah berjaya mengunci kejadian tertentu.

Pertimbangan Keselamatan

Adakah algoritma selamat? Mari cuba bayangkan apa yang berlaku dalam senario yang berbeza.

Sebagai permulaan, mari kita anggap bahawa pelanggan dapat memperoleh kunci pada kebanyakan keadaan. Setiap kejadian akan mengandungi kunci dengan jangka hayat yang sama untuk semua. Walau bagaimanapun, setiap kunci ini telah dipasang pada masa yang berbeza, jadi ia akan tamat tempoh pada masa yang berbeza. Tetapi, jika kunci pertama dipasang pada masa yang tidak lebih teruk daripada T1 (masa yang kami pilih sebelum menghubungi pelayan pertama), dan kunci terakhir dipasang pada masa tidak lebih teruk daripada T2 (masa respons diterima dari pelayan terakhir), maka kami yakin bahawa kunci pertama dalam set yang tamat tempoh akan bertahan sekurang-kurangnya MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Semua kunci lain akan tamat tempoh kemudian, jadi kami boleh memastikan bahawa semua kunci akan sah serentak untuk sekurang-kurangnya kali ini.

Semasa kebanyakan kunci kekal sah, pelanggan lain tidak akan dapat memperoleh kunci itu, kerana operasi N/2+1 SET NX tidak boleh berjaya jika kekunci N/2+1 sudah wujud. Oleh itu, sebaik sahaja kunci telah diperoleh, adalah mustahil untuk memperolehnya semula pada masa yang sama (ini akan melanggar harta pengecualian bersama).
Walau bagaimanapun, kami ingin memastikan bahawa berbilang pelanggan yang cuba mendapatkan kunci pada masa yang sama tidak boleh berjaya pada masa yang sama.

Jika pelanggan telah mengunci majoriti kejadian selama lebih kurang atau lebih daripada tempoh kunci maksimum, ia akan menganggap kunci itu tidak sah dan membuka kunci kejadian. Oleh itu, kami hanya perlu mengambil kira kes di mana pelanggan berjaya menyekat majoriti kejadian dalam masa kurang daripada tarikh tamat tempoh. Dalam kes ini, mengenai hujah di atas, semasa MIN_VALIDITY tiada pelanggan sepatutnya boleh mendapatkan semula kunci itu. Oleh itu, ramai pelanggan akan dapat mengunci tika N/2+1 dalam masa yang sama (yang berakhir pada penghujung peringkat 2) hanya apabila masa untuk mengunci majoriti lebih besar daripada masa TTL, yang menjadikan kunci tidak sah.

Bolehkah anda memberikan bukti rasmi keselamatan, menunjukkan algoritma serupa yang sedia ada, atau mencari pepijat di atas?

Pertimbangan Kebolehcapaian

Ketersediaan sistem bergantung pada tiga ciri utama:

1. Lepaskan kunci secara automatik (apabila kekunci tamat tempoh): Kekunci akhirnya akan tersedia semula untuk digunakan untuk kunci.
2. Hakikat bahawa pelanggan biasanya membantu antara satu sama lain dengan mengeluarkan kunci apabila kunci yang diingini belum diperoleh, atau telah diperoleh dan kerja telah selesai; jadi kemungkinan besar kita tidak perlu menunggu sehingga kunci tamat tempoh untuk mendapatkan semula kunci itu.
3. Hakikat bahawa apabila pelanggan perlu mencuba semula untuk mendapatkan kunci, ia menunggu masa yang agak lama berbanding tempoh yang diperlukan untuk memperoleh kebanyakan kunci. Ini mengurangkan kemungkinan situasi otak berpecah yang timbul apabila bersaing untuk mendapatkan sumber.

Walau bagaimanapun, terdapat penalti ketersediaan yang sama dengan TTL segmen rangkaian, jadi jika terdapat segmen bersebelahan, penalti mungkin tidak ditentukan. Ini berlaku apabila pelanggan memperoleh kunci dan kemudian merobek ke segmen lain sebelum ia boleh melepaskannya.

Pada dasarnya, memandangkan segmen rangkaian bersebelahan yang tidak terhingga, sistem boleh kekal tidak tersedia untuk tempoh masa yang tidak terhingga.

Prestasi, failover dan fsync

Ramai orang menggunakan Redis kerana mereka memerlukan prestasi pelayan kunci yang tinggi dari segi kependaman yang diperlukan untuk memperoleh dan melepaskan kunci, dan bilangan pemerolehan/pelepasan yang boleh diselesaikan sesaat. Untuk memenuhi keperluan ini, terdapat strategi untuk berkomunikasi dengan pelayan N Redis untuk mengurangkan kependaman. Ini ialah strategi pemultipleksan (atau "pemultipleksan lelaki miskin", di mana soket diletakkan dalam mod tidak menyekat, menghantar semua arahan dan membaca arahan kemudian, dengan mengandaikan bahawa masa pergi balik antara klien dan setiap contoh adalah serupa) .

Walau bagaimanapun, kami juga perlu mengambil kira pertimbangan yang berkaitan dengan penyimpanan data jangka panjang jika kami berusaha untuk mencipta model dengan pemulihan yang boleh dipercayai daripada kegagalan.

Pada asasnya, untuk menjelaskan isu ini, mari kita anggap bahawa kita mengkonfigurasi Redis tanpa storan data jangka panjang sama sekali. Pelanggan berjaya menyekat 3 daripada 5 kejadian. Salah satu kejadian yang berjaya disekat oleh pelanggan dimulakan semula, dan pada masa ini terdapat 3 kejadian sekali lagi untuk sumber yang sama, yang boleh kami sekat, dan pelanggan lain boleh, seterusnya, menyekat contoh yang dimulakan semula, melanggar sifat keselamatan yang menganggap eksklusif kunci.

Jika anda mendayakan data hadapan (AOF), keadaan akan bertambah baik sedikit. Sebagai contoh, anda boleh mempromosikan pelayan dengan menghantar arahan SHUTDOWN dan memulakannya semula. Memandangkan operasi tamat tempoh dalam Redis dilaksanakan secara semantik sedemikian rupa sehingga masa terus mengalir walaupun pelayan dimatikan, semua keperluan kami adalah baik. Ini adalah perkara biasa selagi penutupan biasa dipastikan. Apa yang perlu dilakukan sekiranya bekalan elektrik terputus? Jika Redis dikonfigurasikan secara lalai, dengan fsync menyegerak pada cakera setiap saat, maka ada kemungkinan bahawa selepas dimulakan semula kita tidak akan mempunyai kunci kami. Secara teorinya, jika kami ingin menjamin keselamatan kunci semasa sebarang kejadian dimulakan semula, kami harus mendayakan fsync=always dalam tetapan untuk penyimpanan data jangka panjang. Ini akan mematikan prestasi sepenuhnya, sehingga ke tahap sistem CP yang secara tradisinya digunakan untuk melaksanakan kunci teragih dengan selamat.

Tetapi keadaannya lebih baik daripada yang kelihatan pada pandangan pertama. Pada dasarnya, keselamatan algoritma dipelihara kerana apabila contoh dimulakan semula selepas kegagalan, ia tidak lagi mengambil bahagian dalam mana-mana kunci yang sedang aktif.

Untuk memastikan ini, kami hanya perlu memastikan bahawa selepas kegagalan, contoh itu kekal tidak tersedia untuk tempoh masa yang sedikit melebihi TTL maksimum yang kami gunakan. Dengan cara ini kita akan menunggu sehingga tarikh tamat tempoh dan keluaran automatik semua kunci yang aktif pada masa kegagalan.

Menggunakan permulaan semula yang tertunda, pada dasarnya adalah mungkin untuk mencapai keselamatan walaupun tanpa adanya sebarang kegigihan jangka panjang dalam Redis. Walau bagaimanapun, ambil perhatian bahawa ini boleh mengakibatkan denda kerana melanggar kebolehaksesan. Contohnya, jika kebanyakan kejadian gagal, sistem akan menjadi tidak tersedia secara global untuk TTL (dan tiada sumber boleh disekat pada masa ini).

Kami meningkatkan ketersediaan algoritma: kami melanjutkan penyekatan

Jika kerja yang dilakukan oleh pelanggan terdiri daripada langkah-langkah kecil, adalah mungkin untuk mengurangkan tempoh kunci lalai dan melaksanakan mekanisme untuk melanjutkan kunci. Pada dasarnya, jika pelanggan sibuk mengira dan nilai tamat tempoh kunci adalah rendah, anda boleh menghantar skrip Lua kepada semua kejadian yang memanjangkan TTL kunci jika kunci masih wujud dan nilainya masih merupakan nilai rawak yang diperoleh apabila kunci telah diperolehi.

Pelanggan hanya perlu mempertimbangkan kunci untuk diperoleh semula jika ia telah berjaya mengunci majoriti kejadian dalam tempoh sah.

Benar, secara teknikal algoritma tidak berubah, jadi bilangan maksimum percubaan berulang untuk memperoleh kunci mesti dihadkan, jika tidak, sifat kebolehaksesan akan dilanggar.

Sumber: www.habr.com