ProHoster > blog > administrasi > Penguncian terdistribusi menggunakan Redis

Penguncian terdistribusi menggunakan Redis

Hei Habr!

Hari ini kami menyampaikan kepada Anda terjemahan artikel kompleks tentang penerapan penguncian terdistribusi menggunakan Redis dan mengundang Anda untuk membicarakan prospek Redis sebagai sebuah topik. Analisis algoritma Redlock yang dimaksud dari Martin Kleppmann, penulis buku "Aplikasi Beban Tinggi", diberikan di sini.

Penguncian 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 perpustakaan dan postingan di luar sana yang menjelaskan cara mengimplementasikan DLM (Distributed Lock Manager) menggunakan Redis, namun setiap perpustakaan menggunakan pendekatan yang berbeda dan jaminan yang mereka berikan cukup lemah dibandingkan dengan apa yang dapat dicapai dengan desain yang sedikit lebih canggih.

Pada artikel ini, kami akan mencoba menjelaskan algoritma kanonik bersyarat yang menunjukkan cara mengimplementasikan penguncian terdistribusi menggunakan Redis. Kita akan berbicara tentang algoritma yang disebut kunci merah, ini mengimplementasikan pengelola kunci terdistribusi dan, menurut pendapat kami, algoritme ini lebih aman daripada pendekatan instans tunggal biasa. Kami berharap masyarakat akan menganalisanya, memberikan masukan, dan menggunakannya sebagai titik awal untuk proyek yang lebih kompleks atau alternatif.

Penerapan

Sebelum melanjutkan ke deskripsi algoritme, kami menyediakan beberapa tautan ke implementasi yang sudah jadi. Mereka dapat digunakan sebagai referensi.

Jaminan Keamanan dan Ketersediaan

Kami akan memodelkan desain kami hanya dengan tiga properti yang menurut kami memberikan jaminan minimum yang diperlukan untuk menggunakan penguncian terdistribusi secara efektif.

  1. Properti keamanan: Pengecualian bersama. Pada waktu tertentu, hanya satu klien yang dapat memegang kunci tersebut.
  2. Properti Ketersediaan A: Tidak ada kebuntuan. Selalu ada kemungkinan untuk mendapatkan kunci pada akhirnya, bahkan jika klien yang mengunci sumber daya gagal atau mendarat di segmen disk yang berbeda.
  3. Properti Ketersediaan B: Toleransi Kesalahan. Selama sebagian besar node Redis berjalan, klien dapat memperoleh dan melepaskan kunci.

Mengapa implementasi berdasarkan pemulihan kegagalan saja tidak cukup dalam kasus ini
Untuk memahami apa yang akan kami tingkatkan, mari kita menganalisis keadaan saat ini dengan sebagian besar perpustakaan penguncian terdistribusi berdasarkan Redis.

Cara paling sederhana untuk mengunci sumber daya menggunakan Redis adalah dengan membuat kunci di instance. Biasanya, kunci dibuat dengan masa pakai terbatas, hal ini dicapai dengan menggunakan fitur kedaluwarsa yang disediakan di Redis, sehingga cepat atau lambat kunci ini akan dirilis (properti 2 dalam daftar kami). Ketika klien perlu melepaskan sumber daya, klien akan menghapus kuncinya.

Pada pandangan pertama, solusi ini bekerja cukup baik, namun ada masalah: arsitektur kami menciptakan satu titik kegagalan. Apa yang terjadi jika instans host Redis gagal? Ayo tambahkan budaknya! Dan kami akan menggunakannya jika presenter tidak tersedia. Sayangnya, opsi ini tidak dapat dijalankan. Dengan melakukan ini, kita tidak akan dapat mengimplementasikan dengan benar properti saling pengecualian yang kita perlukan untuk memastikan keamanan, karena replikasi di Redis bersifat asinkron.

Jelasnya, dalam model seperti itu terjadi kondisi balapan:

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

Terkadang merupakan hal yang normal jika dalam keadaan khusus, seperti kegagalan, banyak klien dapat menahan kunci pada saat yang bersamaan. Dalam kasus seperti ini, solusi berbasis replikasi dapat diterapkan. Jika tidak, kami merekomendasikan solusi yang dijelaskan dalam artikel ini.

Implementasi yang benar dengan satu contoh

Sebelum mencoba mengatasi kekurangan konfigurasi instance tunggal yang dijelaskan di atas, mari kita pahami cara menangani kasus sederhana ini dengan benar, karena solusi ini sebenarnya valid dalam aplikasi di mana kondisi balapan dapat diterima dari waktu ke waktu, dan juga karena pemblokiran pada a contoh tunggal berfungsi sebagai dasar yang digunakan dalam algoritma terdistribusi yang dijelaskan di sini.

Untuk mendapatkan kunci, lakukan ini:

SET resource_name my_random_value NX PX 30000

Perintah ini menginstal kunci hanya jika belum ada (opsi NX), dengan masa berlaku 30000 milidetik (opsi PX). Kuncinya disetel ke “myrandomvalue" Nilai ini harus unik di semua klien dan semua permintaan kunci.
Pada dasarnya, nilai acak digunakan untuk melepaskan kunci dengan aman, dengan skrip yang memberi tahu Redis: hanya hapus kunci jika ada dan nilai yang disimpan di dalamnya persis seperti yang diharapkan. Hal ini dicapai dengan menggunakan skrip Lua berikut:

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

Hal ini penting untuk mencegah kunci yang dipegang oleh klien lain dihapus. Misalnya, klien mungkin memperoleh kunci, kemudian terkunci dalam beberapa operasi yang berlangsung lebih lama dari kunci pertama (sehingga kunci tersebut memiliki waktu untuk kedaluwarsa), dan kemudian menghapus kunci yang telah dipasang oleh klien lain.
Menggunakan DEL sederhana tidak aman karena klien dapat menghapus kunci yang dipegang oleh klien lain. Sebaliknya, saat menggunakan skrip di atas, setiap kunci “ditandatangani” dengan string acak, sehingga hanya klien yang menempatkannya sebelumnya yang dapat menghapusnya.

Apa yang seharusnya menjadi string acak ini? Saya kira itu harus 20 byte dari /dev/urandom, tetapi Anda dapat menemukan cara yang lebih murah untuk membuat string tersebut cukup unik untuk keperluan Anda. Misalnya saja, akan baik-baik saja untuk melakukan seed RC4 dengan /dev/urandom dan kemudian menghasilkan aliran pseudo-acak darinya. Solusi yang lebih sederhana melibatkan kombinasi waktu unix dalam resolusi mikrodetik ditambah ID klien; ini tidak seaman itu, tapi mungkin sesuai dengan tugas di sebagian besar konteks.

Waktu yang kita gunakan sebagai ukuran masa pakai kunci disebut "masa kunci". Nilai ini adalah jumlah waktu sebelum kunci dilepaskan secara otomatis dan jumlah waktu yang dimiliki klien untuk menyelesaikan operasi sebelum klien lain dapat mengunci sumber daya tersebut, tanpa benar-benar melanggar jaminan pengecualian bersama. Jaminan ini terbatas hanya pada jangka waktu tertentu, yang dimulai sejak kunci dibeli.

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

Algoritma kunci ulang

Versi algoritma terdistribusi mengasumsikan bahwa kita memiliki master N Redis. Node-node ini sepenuhnya independen satu sama lain, jadi kami tidak menggunakan replikasi atau sistem koordinasi implisit lainnya. Kami telah membahas cara memperoleh dan melepaskan kunci dengan aman pada satu instance. Kami berasumsi bahwa algoritme, ketika bekerja dengan satu instance, akan menggunakan metode ini. Dalam contoh kita, kita 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 bertindak secara independen satu sama lain.

Untuk mendapatkan kunci, klien melakukan operasi berikut:

  1. Mendapatkan waktu saat ini dalam milidetik.
  2. Secara berurutan mencoba untuk mendapatkan kunci pada semua N instance, menggunakan nama kunci yang sama dan nilai acak dalam semua kasus. Di Tahap 2, ketika klien menyiapkan kunci per instans, klien menggunakan penundaan untuk mendapatkannya yang cukup singkat dibandingkan dengan waktu setelah kunci dilepaskan secara otomatis. Misalnya, jika durasi pemblokiran adalah 10 detik, maka penundaannya bisa berkisar antara ~5-50 milidetik. Hal ini menghilangkan situasi di mana klien dapat tetap diblokir dalam waktu lama saat mencoba menjangkau node Redis yang gagal: jika instance tidak tersedia, kami mencoba menyambung ke instance lain sesegera mungkin.
  3. Untuk mengambil kunci, klien menghitung berapa lama waktu yang telah berlalu; Untuk melakukan hal ini, ia mengurangi stempel waktu yang diperoleh pada langkah 1 dari nilai waktu sebenarnya. Jika dan hanya jika klien dapat memperoleh kunci pada sebagian besar instans (setidaknya 3), dan total waktu yang diperlukan untuk memperoleh kunci, kurang dari durasi penguncian, kunci dianggap telah diperoleh.
  4. Jika kunci telah diperoleh, durasi kunci dianggap sebagai durasi kunci asli dikurangi waktu yang telah berlalu yang dihitung pada langkah 3.
  5. Jika klien gagal mendapatkan kunci karena alasan tertentu (tidak dapat mengunci N/2+1 instance, atau durasi kunci negatif), maka klien akan mencoba membuka semua instance (bahkan yang dianggap tidak dapat diblokir ).

Apakah algoritmanya asinkron?

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

Pada titik ini, kita harus merumuskan aturan pengecualian bersama dengan lebih hati-hati: pengecualian bersama dijamin hanya jika klien yang memegang kunci keluar selama waktu kunci tersebut valid (nilai ini diperoleh pada langkah 3), dikurangi beberapa waktu lagi (total beberapa milidetik untuk mengkompensasi perbedaan waktu antar proses).

Artikel menarik berikut ini menceritakan lebih banyak tentang sistem yang memerlukan koordinasi interval waktu: Sewa: mekanisme toleransi kesalahan yang efisien untuk konsistensi cache file terdistribusi.

Coba lagi jika gagal

Ketika klien gagal mendapatkan kunci, klien harus mencoba lagi setelah penundaan acak; ini dilakukan untuk membatalkan sinkronisasi beberapa klien yang mencoba mendapatkan kunci pada sumber daya yang sama pada saat yang sama (yang dapat menyebabkan situasi "otak terpecah" di mana tidak ada pemenang). Selain itu, semakin cepat klien mencoba mendapatkan kunci pada sebagian besar instans Redis, semakin sempit jendela terjadinya situasi split-brain (dan semakin kecil kebutuhan untuk mencoba ulang). Oleh karena itu, idealnya, klien harus mencoba mengirim perintah SET ke N instance secara bersamaan menggunakan multiplexing.

Perlu ditekankan di sini betapa pentingnya bagi klien yang gagal memperoleh sebagian besar kunci untuk melepaskan (sebagian) kunci yang diperoleh, sehingga mereka tidak perlu menunggu kunci tersebut kedaluwarsa sebelum kunci pada sumber daya dapat diperoleh kembali. (walaupun jika terjadi fragmentasi jaringan, dan klien kehilangan kontak dengan instans Redis, Anda harus membayar penalti ketersediaan sambil menunggu kunci kedaluwarsa).

Lepaskan kuncinya

Melepaskan kunci adalah operasi sederhana yang hanya memerlukan pembukaan kunci semua instance, terlepas dari apakah klien tampaknya berhasil mengunci instance tertentu.

Pertimbangan Keamanan

Apakah algoritmanya aman? Mari kita coba membayangkan apa yang terjadi dalam berbagai skenario.

Untuk memulainya, mari kita asumsikan bahwa klien dapat memperoleh kunci pada sebagian besar kasus. Setiap instance akan berisi kunci dengan masa hidup yang sama untuk semua instance. Namun, masing-masing kunci ini dipasang pada waktu yang berbeda, sehingga masa berlakunya akan berbeda-beda. Namun, 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 saat respons diterima dari server terakhir), maka kami yakin bahwa kunci pertama dalam set yang kedaluwarsa setidaknya akan bertahan MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Semua kunci lainnya akan habis masa berlakunya nanti, jadi kami dapat yakin bahwa semua kunci akan valid secara bersamaan setidaknya untuk saat ini.

Selama sebagian besar kunci tetap valid, klien lain tidak akan dapat memperoleh kunci tersebut, karena operasi N/2+1 SET NX tidak dapat berhasil jika kunci N/2+1 sudah ada. Oleh karena itu, setelah kunci diperoleh, tidak mungkin untuk memperolehnya lagi pada saat yang sama (hal ini akan melanggar properti saling pengecualian).
Namun, kami ingin memastikan bahwa beberapa klien yang mencoba mendapatkan kunci pada saat yang sama tidak dapat berhasil pada saat yang bersamaan.

Jika klien telah mengunci sebagian besar instance selama sekitar atau lebih dari durasi penguncian maksimum, klien akan menganggap kunci tersebut tidak valid dan membuka kunci instance. Oleh karena itu, kami hanya perlu memperhitungkan kasus di mana klien berhasil memblokir sebagian besar instance dalam waktu kurang dari tanggal kedaluwarsa. Dalam hal ini, mengenai argumen di atas, selama ini MIN_VALIDITY tidak ada klien yang dapat memperoleh kembali kunci tersebut. Oleh karena itu, banyak klien akan dapat mengunci instans N/2+1 dalam waktu yang sama (yang berakhir pada akhir tahap 2) hanya ketika waktu untuk mengunci mayoritas lebih besar dari waktu TTL, yang menjadikan kunci tersebut tidak valid.

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

Pertimbangan Aksesibilitas

Ketersediaan sistem bergantung pada tiga karakteristik utama:

  1. Melepaskan kunci secara otomatis (saat kunci habis masa berlakunya): Kunci pada akhirnya akan tersedia kembali untuk digunakan sebagai kunci.
  2. Fakta bahwa klien biasanya membantu satu sama lain dengan melepas kunci ketika kunci yang diinginkan belum diperoleh, atau telah diperoleh dan pekerjaan telah selesai; jadi kemungkinan besar kita tidak perlu menunggu kuncinya habis masa berlakunya untuk mendapatkan kembali kunci tersebut.
  3. Fakta bahwa ketika klien perlu mencoba lagi untuk mendapatkan kunci, ia menunggu dalam waktu yang relatif lebih lama daripada periode yang diperlukan untuk mendapatkan sebagian besar kunci. Hal ini mengurangi kemungkinan terjadinya situasi perpecahan otak ketika bersaing untuk mendapatkan sumber daya.

Namun, terdapat penalti ketersediaan yang sama dengan TTL segmen jaringan, jadi jika terdapat segmen yang berdekatan, penalti tersebut mungkin tidak terbatas. Hal ini terjadi setiap kali klien memperoleh kunci dan kemudian meretas ke segmen lain sebelum dapat melepaskannya.

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

Performa, failover, dan fsync

Banyak orang menggunakan Redis karena mereka memerlukan kinerja server kunci yang tinggi dalam hal latensi yang diperlukan untuk memperoleh dan melepaskan kunci, dan jumlah akuisisi/rilis yang dapat diselesaikan per detik. Untuk memenuhi persyaratan ini, terdapat strategi untuk berkomunikasi dengan server N Redis untuk mengurangi latensi. Ini adalah strategi multiplexing (atau "multiplexing orang miskin", di mana soket ditempatkan pada mode non-pemblokiran, mengirimkan semua perintah, dan membaca perintah nanti, dengan asumsi bahwa waktu bolak-balik antara klien dan setiap instance serupa) .

Namun, kami juga harus mempertimbangkan pertimbangan terkait penyimpanan data jangka panjang jika kami berusaha membuat model dengan pemulihan kegagalan yang andal.

Pada dasarnya, untuk memperjelas masalah ini, mari kita asumsikan kita mengonfigurasi Redis tanpa penyimpanan data jangka panjang sama sekali. Klien berhasil memblokir 3 dari 5 contoh. Salah satu instance yang berhasil diblokir oleh klien di-restart, dan saat ini ada 3 instance lagi untuk sumber daya yang sama, yang dapat kita blokir, dan klien lain, pada gilirannya, dapat memblokir instance yang di-restart, melanggar properti keamanan yang mengasumsikan eksklusivitas kunci.

Jika Anda mengaktifkan data ke depan (AOF), situasinya akan sedikit membaik. Misalnya, Anda dapat mempromosikan server dengan mengirimkan perintah SHUTDOWN dan memulai ulang. Karena operasi kedaluwarsa di Redis diimplementasikan secara semantik sedemikian rupa sehingga waktu terus mengalir bahkan ketika server dimatikan, semua persyaratan kami baik-baik saja. Hal ini normal selama pematian normal dipastikan. Apa yang harus dilakukan jika listrik padam? Jika Redis dikonfigurasikan secara default, dengan sinkronisasi fsync pada disk setiap detik, maka ada kemungkinan bahwa setelah restart kita tidak akan memiliki kunci kita. Secara teoritis, jika kita ingin menjamin keamanan kunci selama restart, kita harus mengaktifkannya fsync=always dalam pengaturan untuk penyimpanan data jangka panjang. Hal ini akan mematikan kinerja sepenuhnya, hingga ke tingkat sistem CP yang biasanya digunakan untuk menerapkan kunci terdistribusi dengan aman.

Namun situasinya lebih baik daripada yang terlihat pada pandangan pertama. Pada prinsipnya, keamanan algoritma tetap terjaga karena ketika instance dimulai ulang setelah terjadi kegagalan, instance tersebut tidak lagi berpartisipasi dalam kunci apa pun yang sedang aktif.

Untuk memastikan hal ini, kita hanya perlu memastikan bahwa setelah kegagalan, instance tetap tidak tersedia untuk jangka waktu yang sedikit melebihi TTL maksimum yang kita gunakan. Dengan cara ini kita akan menunggu hingga tanggal kedaluwarsa dan pelepasan otomatis semua kunci yang aktif pada saat kegagalan.

Dengan menggunakan restart yang tertunda, pada prinsipnya keamanan dapat dicapai bahkan tanpa adanya persistensi jangka panjang di Redis. Namun perlu diingat bahwa hal ini dapat mengakibatkan denda karena melanggar aksesibilitas. Misalnya, jika sebagian besar instance gagal, sistem akan menjadi tidak tersedia secara global untuk TTL (dan tidak ada sumber daya yang dapat diblokir selama waktu tersebut).

Kami meningkatkan ketersediaan algoritme: kami memperluas pemblokiran

Jika pekerjaan yang dilakukan oleh klien terdiri dari langkah-langkah kecil, dimungkinkan untuk mengurangi durasi penguncian default dan menerapkan mekanisme untuk memperpanjang penguncian. Pada prinsipnya, jika klien sibuk melakukan komputasi dan nilai kedaluwarsa kunci sangat rendah, Anda dapat mengirimkan skrip Lua ke semua instance yang memperluas TTL kunci jika kunci masih ada dan nilainya masih merupakan nilai acak yang diperoleh saat kunci diperoleh.

Klien hanya boleh mempertimbangkan kunci untuk diperoleh kembali jika klien telah berhasil mengunci sebagian besar instance dalam masa validitas.

Benar, secara teknis algoritme tidak berubah, sehingga jumlah maksimum upaya berulang untuk mendapatkan kunci harus dibatasi, jika tidak, properti aksesibilitas akan dilanggar.

Sumber: www.habr.com

Tambah komentar