Clever Geek Handbook

Kunci yang didistribusikan menggunakan Redis

Halo, Habr!



Hari ini kami menyampaikan kepada Anda terjemahan dari artikel kompleks tentang penerapan kunci terdistribusi menggunakan Redis dan mengusulkan untuk membicarakan tentang perspektif Redis sebagai topik. Analisis algoritme Redlock yang dianggap dari Martin Kleppman, penulis buku " Aplikasi Beban Tinggi ", diberikan di sini .





Kunci terdistribusi adalah primitif yang sangat berguna yang digunakan di banyak lingkungan di mana proses yang berbeda harus bekerja pada sumber daya bersama dengan cara yang saling eksklusif.



Ada sejumlah pustaka dan postingan di luar sana yang menjelaskan cara mengimplementasikan DLM (Distributed Locking Manager) dengan Redis, tetapi setiap pustaka mengambil pendekatan yang berbeda dan jaminan yang diberikan agak lemah dibandingkan dengan apa yang dapat dicapai dengan desain yang sedikit lebih kompleks.



Dalam artikel ini, kami akan mencoba menjelaskan algoritme kanonis bersyarat yang mendemonstrasikan cara menerapkan kunci terdistribusi dengan Redis. Kami akan berbicara tentang algoritma yang disebut Redlock, ini menerapkan manajer penguncian terdistribusi dan, menurut pendapat kami, algoritme ini lebih aman daripada pendekatan instans tunggal konvensional. Kami berharap masyarakat dapat menganalisanya, memberikan masukan dan menggunakannya sebagai titik awal untuk implementasi proyek yang lebih kompleks atau alternatif.



Implementasi



Sebelum melanjutkan ke deskripsi algoritma, berikut adalah beberapa link ke implementasi yang sudah jadi. Mereka dapat digunakan sebagai referensi.







Jaminan Keamanan dan Ketersediaan



Kami akan mensimulasikan desain kami hanya dengan tiga properti yang kami yakini memberikan jaminan minimum yang diperlukan untuk menggunakan kunci terdistribusi secara efektif.



  1. Properti keamanan: Pengecualian bersama. Hanya satu klien yang dapat menahan kunci dalam satu waktu.
  2. Properti Aksesibilitas A: Tidak ada jalan buntu. Pada akhirnya, Anda selalu bisa mendapatkan kunci, bahkan jika klien yang mengunci sumber daya gagal atau berakhir di segmen disk lain.
  3. Properti Aksesibilitas B: Toleransi Kesalahan. Saat sebagian besar node Redis berjalan, klien dapat memperoleh dan melepaskan kunci.




Mengapa implementasi berbasis failover tidak cukup dalam kasus ini

Untuk memahami apa yang akan kami tingkatkan, mari menganalisis keadaan saat ini dengan sebagian besar pustaka penguncian terdistribusi berdasarkan Redis.



Cara termudah untuk mengunci sumber daya menggunakan Redis adalah dengan membuat kunci pada sebuah instance. Biasanya kunci dibuat dengan masa pakai terbatas, ini dicapai menggunakan fitur kedaluwarsa yang disediakan di Redis, jadi cepat atau lambat kunci ini dilepaskan (properti 2 di daftar kami). Saat klien perlu membebaskan sumber daya, kunci tersebut dihapus.



Sekilas, solusi ini berfungsi dengan baik, tetapi ada masalah: ada satu titik kegagalan dalam arsitektur kami. Apa yang terjadi jika instance master Redis gagal? Ayo tambahkan pengikut! Dan kami akan menggunakannya jika host tidak tersedia. Sayangnya, opsi ini tidak dapat dijalankan. Dengan melakukan ini, kami tidak akan dapat menerapkan properti pengecualian bersama dengan benar yang kami perlukan untuk memastikan keamanan, karena replikasi di Redis bersifat asinkron.



Jelas, kondisi balapan terjadi dalam model seperti itu:

  1. Klien A memperoleh kunci pada master.
  2. Master gagal sebelum penulisan ke kunci ditransfer ke budak.
  3. Pengikut dipromosikan menjadi pemimpin.
  4. Klien B memperoleh kunci pada sumber daya yang sama yang telah dikunci oleh A. PELANGGARAN KEAMANAN!




Terkadang sangatlah normal bahwa dalam keadaan khusus, seperti kegagalan, banyak klien dapat menahan kunci pada saat yang bersamaan. Dalam kasus seperti itu, Anda dapat menerapkan solusi berbasis replikasi. Jika tidak, kami merekomendasikan solusi yang dijelaskan dalam artikel ini.



Penerapan Mesin Instans Tunggal yang Benar



Sebelum kita mencoba untuk mengatasi kekurangan konfigurasi instans tunggal yang dijelaskan di atas, mari kita cari tahu cara menangani kasus sederhana ini, karena ini sebenarnya dapat diterima dalam aplikasi di mana kondisi balapan terkadang dapat diterima, dan juga karena penguncian pada satu instance berfungsi sebagai dasar untuk algoritme terdistribusi yang dijelaskan di sini.



Untuk mendapatkan kunci, mari lakukan hal berikut:



SET resource_name my_random_value NX PX 30000



Perintah ini menginstal kunci hanya jika belum ada (opsi NX), dengan tanggal kedaluwarsa 30.000 milidetik (opsi PX). Kuncinya disetel ke " myrandomvalue". Nilai ini harus unik di semua klien dan di semua permintaan kunci.

Pada dasarnya, nilai acak digunakan untuk melepaskan kunci dengan aman, menggunakan skrip yang memberi tahu Redis untuk menghapus kunci hanya jika ada dan nilai yang disimpan di dalamnya persis seperti yang diharapkan. Ini dicapai dengan 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 mencegah pelepasan kunci oleh klien lain. Misalnya, klien mungkin memperoleh kunci, lalu memblokir dalam operasi yang berlangsung lebih lama dari kunci pertama (sehingga kunci memiliki waktu untuk kedaluwarsa), dan kemudian menghapus kunci yang ditempatkan beberapa klien lain.

Tidak aman menggunakan DEL sederhana karena klien mungkin menghapus kunci yang dipegang oleh klien lain. Sebaliknya, saat menggunakan script di atas, setiap kunci "ditandatangani" dengan string acak, jadi hanya klien yang sebelumnya menempatkannya yang dapat menghapusnya.



Apa seharusnya string acak ini? Saya kira itu harus 20 byte dari / dev / urandom, tetapi Anda dapat menemukan cara yang lebih murah untuk membuat string cukup unik untuk tujuan yang ingin Anda capai. Misalnya, tidak masalah untuk menyemai RC4 dengan / dev / urandom dan kemudian menghasilkan aliran pseudo-acak berdasarkan itu. Solusi yang lebih sederhana melibatkan penggabungan waktu unix mikrodetik ditambah ID klien; ini tidak cukup aman, tetapi mungkin pada level tantangan di sebagian besar konteks.



Waktu yang kami gunakan sebagai ukuran masa pakai kunci disebut "waktu kedaluwarsa kunci". Nilai ini adalah waktu setelah kunci akan dilepaskan secara otomatis dan waktu klien harus menyelesaikan operasi sebelum klien lain pada gilirannya dapat mengunci sumber daya tanpa benar-benar melanggar jaminan pengecualian bersama. Jaminan semacam itu hanya terbatas pada jangka waktu tertentu, yang dimulai dari saat mendapatkan kunci.



Jadi, kami telah membahas cara yang baik untuk memperoleh dan membuka kunci. Sistem (jika kita berbicara tentang sistem yang tidak terisi yang terdiri dari satu instance yang selalu tersedia) aman. Mari kita kembangkan konsep ini ke sistem terdistribusi di mana kami tidak memiliki jaminan seperti itu.



Redlock Algorithm



Versi algoritme yang didistribusikan mengasumsikan bahwa kami memiliki N yang memimpin Redis. Node ini sepenuhnya independen satu sama lain, jadi kami tidak menggunakan replikasi atau sistem koordinasi implisit lainnya. Kami telah membahas cara mendapatkan dan melepaskan kunci dengan aman pada satu instance. Kami menerima begitu saja bahwa algoritme akan menggunakan metode ini saat bekerja dengan satu instance. Dalam contoh kami, kami menetapkan N ke 5, yang merupakan nilai yang masuk akal. Oleh karena itu, kita perlu menggunakan 5 master Redis di komputer atau mesin virtual yang berbeda untuk memastikan bahwa mereka beroperasi secara independen satu sama lain.



Untuk mendapatkan kunci, klien melakukan operasi berikut:



  1. Mendapat waktu saat ini dalam milidetik.
  2. N , . 2, , , , , , . , 10 , ~ 5-50 . , , Redis: , .
  3. , , ; , 1. , ( 3), , , , , , .
  4. , , 3.
  5. - ( N/2+1 , ), ( , , , ).




Apakah algoritmanya tidak sinkron?



Algoritme ini didasarkan pada asumsi bahwa, meskipun tidak ada jam tersinkronisasi di mana semua proses akan bekerja, waktu lokal di setiap proses masih mengalir pada kecepatan yang kira-kira sama, dan kesalahannya kecil dibandingkan dengan total waktu setelah kunci dilepaskan secara otomatis. Asumsi ini sangat mirip dengan situasi yang khas untuk komputer biasa: setiap komputer memiliki jam lokal, dan biasanya kita dapat mengandalkan fakta bahwa perbedaan waktu pada komputer yang berbeda kecil.



Pada tahap ini, kita harus lebih berhati-hati dalam merumuskan aturan pengecualian timbal balik kami: pengecualian bersama dijamin hanya jika klien yang memegang kunci selesai dalam waktu selama kunci tersebut valid (nilai ini diperoleh pada langkah 3), dikurangi beberapa waktu lagi (total beberapa milidetik untuk mengimbangi perbedaan waktu antar proses).



Artikel menarik berikut ini menjelaskan lebih lanjut tentang sistem yang memerlukan jeda waktu: Sewa: mekanisme toleransi kesalahan yang efisien untuk konsistensi cache file terdistribusi .



Coba lagi jika gagal



Ketika klien gagal mendapatkan kunci, ia harus mencoba melakukannya lagi, dengan penundaan acak; hal ini dilakukan untuk membatalkan sinkronisasi banyak klien secara bersamaan yang mencoba mendapatkan kunci pada sumber daya yang sama (yang dapat menyebabkan situasi otak terbelah di mana tidak ada pemenang). Selain itu, semakin cepat klien mencoba mendapatkan kunci pada sebagian besar instance Redis, semakin sempit jendela tempat situasi otak terbelah dapat terjadi (dan semakin sedikit percobaan ulang yang diperlukan). Oleh karena itu, idealnya, klien harus mencoba mengirim perintah SET ke instans N pada saat yang sama menggunakan multiplexing.



Perlu ditekankan di sini betapa pentingnya bagi klien yang belum dapat memperoleh sebagian besar kunci untuk melepaskan (sebagian) kunci yang diperoleh sehingga mereka tidak perlu menunggu tanggal kedaluwarsa kunci sebelum kunci pada sumber daya dapat diperoleh lagi (meskipun jika terjadi fragmentasi jaringan dan klien kehilangan kontak dengan instance Redis, Anda harus membayar penalti pelanggaran akses sementara kuncinya diperkirakan akan kedaluwarsa).



Melepaskan Kunci



Melepaskan kunci adalah operasi sederhana yang hanya memerlukan membuka kunci semua instans, terlepas dari apakah pelanggan mengira mereka berhasil mengunci instans tertentu.



Pertimbangan keamanan



Apakah algoritme aman? Mari kita coba membayangkan apa yang terjadi dalam skenario yang berbeda.



Pertama, mari kita asumsikan bahwa klien dapat memperoleh kunci pada sebagian besar contoh. Setiap instance akan berisi kunci dengan masa pakai yang sama untuk semua orang. Namun, masing-masing kunci ini dipasang pada waktunya sendiri, sehingga akan kedaluwarsa pada waktu yang berbeda. Tapi, jika kunci pertama dipasang pada waktu yang tidak lebih buruk dari T1 (waktu yang kita pilih sebelum menghubungi server pertama), dan kunci terakhir dipasang pada waktu yang tidak lebih buruk dari T2 (waktu di mana tanggapan diterima dari server terakhir), maka kita yakin bahwa kunci pertama dalam rangkaian yang akan kedaluwarsa akan bertahan setidaknyaMIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT... Semua kunci lainnya akan kedaluwarsa nanti, jadi kami dapat memastikan bahwa semua kunci akan valid secara bersamaan setidaknya untuk saat ini.



Selama sebagian besar kunci tetap valid, klien lain tidak akan dapat memperoleh kunci, karena operasi N / 2 + 1 SET NX tidak dapat berhasil jika kunci N / 2 + 1 sudah ada. Oleh karena itu, jika kunci diperoleh, maka tidak mungkin untuk memperolehnya kembali pada saat yang sama (ini akan melanggar properti pengecualian bersama).

Namun, kami ingin memastikan bahwa banyak klien yang secara bersamaan mencoba mendapatkan kunci tidak dapat berhasil pada saat yang bersamaan.



Jika klien telah mengunci sebagian besar instans, menghabiskan sekitar atau lebih dari durasi penguncian maksimum untuk saat ini, ini akan membatalkan penguncian dan membuka blokir instans. Oleh karena itu, kami hanya perlu mempertimbangkan kasus di mana pelanggan dapat memblokir sebagian besar instance dalam waktu kurang dari tanggal kedaluwarsa. Dalam kasus ini, sehubungan dengan argumen di atas, MIN_VALIDITYtidak ada klien yang dapat memperoleh kembali kunci tepat waktu. Oleh karena itu, beberapa klien akan dapat mengunci instans N / 2 + 1 dalam jumlah waktu yang sama (yang berakhir pada akhir tahap 2) hanya ketika waktu untuk mengunci mayoritas lebih besar dari waktu TTL, yang membatalkan penguncian.



Dapatkah Anda memberikan bukti keamanan formal, menunjukkan algoritme serupa yang ada, atau menemukan bug di atas?



Pertimbangan



Ketersediaan Ketersediaan sistem bergantung pada tiga karakteristik utama:



  1. Pelepasan kunci secara otomatis (saat kunci kedaluwarsa): Pada akhirnya kunci akan tersedia lagi untuk digunakan sebagai kunci.
  2. Fakta bahwa klien biasanya saling membantu dengan melepas kunci ketika kunci yang diinginkan tidak diperoleh, atau diperoleh, dan pekerjaan selesai; oleh karena itu, sepertinya kita tidak perlu menunggu kunci kedaluwarsa untuk mendapatkan kembali kunci tersebut.
  3. Fakta bahwa ketika pelanggan perlu mencoba kembali untuk mendapatkan kunci, ia menunggu waktu yang relatif lebih lama daripada yang dibutuhkan untuk memperoleh sebagian besar kunci. Ini mengurangi kemungkinan situasi otak terbelah ketika bersaing untuk mendapatkan sumber daya.




Namun, Anda harus membayar penalti untuk ketersediaan yang berkurang sama dengan waktu TTL di segmen jaringan, jadi jika ada segmen yang berdekatan, maka penalti ini dapat menjadi ukuran yang tidak ditentukan. Ini terjadi setiap kali klien memperoleh kunci dan kemudian menjepit ke segmen lain sebelum dapat melepaskannya.



Pada prinsipnya, mengingat segmen jaringan berdekatan yang tak terbatas, sistem dapat tetap tidak tersedia untuk jangka waktu yang tidak terbatas.



Performa, failover, dan fsync



Banyak orang menggunakan Redis karena mereka perlu memberikan kinerja tinggi dari server kunci, pada tingkat latensi yang diperlukan untuk memperoleh dan melepaskan kunci, serta jumlah operasi akuisisi / pelepasan yang dapat dilakukan per detik. Untuk memenuhi kebutuhan tersebut, terdapat strategi komunikasi dengan server N Redis untuk mengurangi latensi. Ini adalah strategi multiplexing (atau multiplexing orang malang, yang menempatkan soket dalam mode non-pemblokiran, mengirim semua perintah, dan membaca perintah nanti, dengan asumsi waktu pulang-pergi antara klien dan setiap instance serupa).



Benar, ada juga pertimbangan penyimpanan data jangka panjang yang perlu dipertimbangkan jika kita ingin membuat model dengan pemulihan yang andal setelah kegagalan.



Pada dasarnya, untuk memperjelas masalah, mari kita asumsikan bahwa kita mengonfigurasi Redis tanpa penyimpanan data jangka panjang sama sekali. Klien berhasil memblokir 3 dari 5 contoh. Salah satu contoh yang berhasil diblokir klien dimulai ulang, dan saat ini 3 contoh muncul lagi untuk sumber daya yang sama, yang dapat kita blokir, dan klien lain dapat, pada gilirannya, memblokir contoh yang direstart, melanggar properti keamanan yang menyiratkan eksklusivitas kunci.



Jika Anda mengaktifkan Data Advance (AOF), situasinya akan sedikit membaik. Misalnya, Anda dapat mempromosikan server dengan mengirimkan perintah SHUTDOWN dan kemudian memulai ulang. Karena operasi kedaluwarsa di Redis diterapkan secara semantik sedemikian rupa sehingga waktu terus mengalir bahkan saat server dimatikan, semuanya baik-baik saja dengan semua persyaratan kami. Normal selama shutdown normal terjamin. Apa yang harus dilakukan jika listrik padam? Jika Redis dikonfigurasi secara default, dengan fsync melakukan sinkronisasi pada disk setiap detik, maka ada kemungkinan bahwa setelah restart kita akan kehilangan kunci kita. Secara teori, jika kami ingin menjamin keamanan kunci pada setiap memulai ulang instans, kami harus mengaktifkanfsync=alwaysdalam pengaturan untuk penyimpanan data jangka panjang. Ini benar-benar akan mematikan kinerja, ke tingkat sistem CP yang biasanya digunakan untuk mengimplementasikan kunci terdistribusi dengan aman.



Tapi situasinya lebih baik daripada yang terlihat. Pada prinsipnya, algoritme tetap aman karena ketika sebuah instance dimulai ulang setelah terjadi kegagalan, itu tidak lagi berpartisipasi dalam kunci yang sedang aktif.



Untuk menjamin ini, kami hanya perlu memastikan bahwa setelah kegagalan, instans tetap tidak tersedia untuk periode waktu yang sedikit melebihi TTL maksimum yang kami gunakan. Jadi kami akan menunggu kedaluwarsa dan rilis otomatis semua kunci yang aktif pada saat penolakan.



Dengan menggunakan mulai ulang yang ditangguhkan, pada prinsipnya mungkin untuk mencapai keamanan tanpa persistensi jangka panjang di Redis. Namun, perhatikan bahwa ini dapat mengakibatkan penalti aksesibilitas. Misalnya, jika sebagian besar instance gagal, sistem akan menjadi tidak tersedia secara global untuk waktu TTL (dan tidak ada sumber daya yang dapat diblokir saat ini).



Meningkatkan ketersediaan algoritme: memperpanjang kunci



Jika pekerjaan yang dilakukan oleh klien terdiri dari langkah-langkah kecil, maka dimungkinkan untuk mempersingkat waktu kedaluwarsa kunci default dan menerapkan mekanisme perpanjangan kunci. Pada dasarnya, jika klien sibuk dengan penghitungan dan nilai kedaluwarsa kunci sangat rendah, Anda dapat mengirim semua contoh skrip di Lua untuk memperluas TTL kunci, jika kunci masih ada, dan nilainya masih acak yang diperoleh saat kunci diperoleh.



Seorang pelanggan harus mempertimbangkan kunci sebagai diperoleh kembali hanya jika telah berhasil mengunci sebagian besar instans selama periode validitas.



Namun, secara teknis, algoritme tidak berubah dalam kasus ini, jadi jumlah maksimum upaya berulang untuk mendapatkan kunci harus dibatasi, jika tidak, properti aksesibilitas akan dilanggar.


More articles:


All Articles