ProHoster > Blog > Ma'muriyat > Redis yordamida taqsimlangan qulflash

Redis yordamida taqsimlangan qulflash

Hey Xabr!

Bugun biz sizga Redis-dan foydalangan holda taqsimlangan qulflarni amalga oshirish haqidagi murakkab maqolaning tarjimasini taklif qilamiz va Redis-ning potentsialini mavzu sifatida muhokama qilamiz. Ko'rib chiqilayotgan Redlock algoritmining tahlili kitob muallifi Martin Kleppman tomonidan taqdim etilgan "Yuqori yuklangan ilovalar", berilgan shu yerda.

Taqsimlangan qulflar turli jarayonlar umumiy resurslarda o'zaro eksklyuziv tarzda ishlashi kerak bo'lgan ko'plab muhitlarda qo'llaniladigan juda foydali primitivdir.

Redis-dan foydalangan holda DLM (Distributed Lock Manager) ni qanday amalga oshirishni tavsiflovchi bir qator kutubxonalar va postlar mavjud, ammo har bir kutubxona o'ziga xos yondashuvni qo'llaydi va ular taqdim etadigan kafolatlar biroz murakkabroq dizayn bilan erishish mumkin bo'lgan narsalarga nisbatan ancha zaifdir.

Ushbu maqolada biz Redis yordamida taqsimlangan qulflashni qanday amalga oshirishni ko'rsatadigan kanonik algoritmni tasvirlashga harakat qilamiz. deb nomlangan algoritmni muhokama qilamiz RedlockU taqsimlangan blokirovka boshqaruvchisini qo'llaydi va biz bu algoritm an'anaviy bir nusxali yondashuvga qaraganda xavfsizroq deb hisoblaymiz. Umid qilamizki, hamjamiyat buni tahlil qiladi, fikr-mulohazalarini bildiradi va undan murakkabroq yoki muqobil loyihalar uchun boshlang‘ich nuqta sifatida foydalanadi.

Amalga oshirish

Algoritmni tasvirlashdan oldin biz mavjud ilovalarga bir nechta havolalarni taqdim etamiz. Bulardan ma'lumot uchun foydalanish mumkin.

Xavfsizlik va mavjudlik kafolatlari

Biz dizaynimizni faqat uchta xususiyat bilan modellashtirmoqchimiz, biz ishonamizki, taqsimlangan qulflardan samarali foydalanish uchun zarur bo'lgan minimal kafolatlar beradi.

  1. Xavfsizlik xususiyati: O'zaro istisno. Faqat bitta mijoz istalgan vaqtda qulfni ushlab turishi mumkin.
  2. Mavjudlik xususiyati A: Tugallanish yo'q. Resursni bloklagan mijoz ishlamay qolsa yoki boshqa disk segmentiga ko'chirilgan bo'lsa ham, har doim qulfni olish mumkin.
  3. Mavjudlik xususiyati B: xatoga chidamlilik. Redis tugunlarining aksariyati ishlayotgan ekan, mijozlar qulflarni olishlari va ochishlari mumkin.

Nima uchun bu holatda muvaffaqiyatsizlikka asoslangan dastur etarli emas
Biz nimani yaxshilamoqchi ekanligimizni tushunish uchun, keling, Redis-ga asoslangan taqsimlangan blokirovkalash kutubxonalarining ko'pchiligining hozirgi holatini tahlil qilaylik.

Redis yordamida resursni blokirovka qilishning eng oddiy usuli misolda kalit yaratishdir. Odatda, kalit cheklangan xizmat muddati bilan yaratiladi, Redis-ning amal qilish muddati tugashi xususiyati yordamida erishiladi, shuning uchun kalit oxir-oqibat chiqariladi (bizning ro'yxatdagi 2-xususiyat). Mijoz resursni chiqarishi kerak bo'lganda, u kalitni o'chiradi.

Bir qarashda, bu yechim ishlayotgandek tuyuladi, ammo muammo bor: bizning arxitekturamiz bitta xato nuqtasini taqdim etadi. Asosiy Redis misoli muvaffaqiyatsiz bo'lsa nima bo'ladi? Keling, bir qul qo'shamiz! Va agar usta mavjud bo'lmasa, undan foydalaning. Afsuski, bu maqbul variant emas. Bu bizga xavfsizlik uchun zarur bo'lgan o'zaro istisno xususiyatini to'g'ri amalga oshirishimizga to'sqinlik qiladi, chunki Redis-da replikatsiya asinxrondir.

Shubhasiz, bunday modelda poyga sharti paydo bo'ladi:

  1. A mijozi masterda qulf oladi.
  2. Kalit yozuvi qulga uzatilgunga qadar master muvaffaqiyatsiz bo'ladi.
  3. Izdoshi yetakchiga ko‘tariladi.
  4. B mijozi A tomonidan allaqachon qulflangan bir xil resursda qulfni oladi. XAVFSIZLIKNI BUZISH!

Ba'zan, bir nechta mijozlar maxsus holatlarda, masalan, nosozlik paytida qulfni bir vaqtning o'zida ushlab turishi mutlaqo normaldir. Bunday hollarda replikatsiyaga asoslangan yechimdan foydalanish mumkin. Aks holda, biz ushbu maqolada tasvirlangan yechimni tavsiya qilamiz.

Bitta misol bilan to'g'ri amalga oshirish

Yuqorida tavsiflangan bir nusxali konfiguratsiyaning kamchiliklarini bartaraf etishga harakat qilishdan oldin, keling, ushbu oddiy ishni qanday qilib to'g'ri hal qilishni ko'rib chiqaylik, chunki bunday yechim poyga shartlari vaqti-vaqti bilan maqbul bo'lgan ilovalarda maqbuldir, shuningdek, bu erda tasvirlangan taqsimlangan algoritmda ishlatiladigan asos bo'lgan yagona instantsiya blokirovkasi.

Qulfni sotib olish uchun quyidagi amallarni bajaring:

SET resource_name my_random_value NX PX 30000

Bu buyruq kalitni faqat u mavjud bo'lmagan taqdirdagina o'rnatadi (option NX), amal qilish muddati 30000 millisekund (PX varianti). Kalit qiymatga o'rnatiladi "myrandomvalue”. Bu qiymat barcha mijozlar va barcha blokirovka so‘rovlari uchun yagona bo‘lishi kerak.
Asosan, tasodifiy qiymatdan qulfni xavfsiz bo'shatish uchun foydalaniladi, bunda Redisga kalit mavjud bo'lsa va unda saqlangan qiymat kutilgandek bo'lsagina uni o'chirishni aytadigan skript yordamida ishlatiladi. Bunga quyidagi Lua skripti bilan erishiladi:

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

Bu boshqa mijoz tomonidan boshqa mijoz tomonidan o'rnatilgan qulfni olib tashlashning oldini olish uchun muhimdir. Misol uchun, mijoz qulfni sotib olishi mumkin, so'ngra dastlabki qulfdan uzoqroq davom etadigan operatsiya davomida bloklanadi (kalitning amal qilish muddati tugashi mumkin) va keyin boshqa mijoz tomonidan o'rnatilgan qulfni olib tashlashi mumkin.
Oddiy DEL-dan foydalanish xavflidir, chunki mijoz boshqa mijoz tomonidan ilgari saqlangan qulfni o'chirib tashlashi mumkin. Yuqoridagi skriptdan farqli o'laroq, har bir qulf tasodifiy satr bilan "imzolangan", shuning uchun uni faqat ilgari ushlab turgan mijoz o'chirib tashlashi mumkin.

Bu tasodifiy qator nima bo'lishi kerak? O'ylaymanki, bu /dev/urandom dan 20 bayt bo'lishi kerak, lekin stringni maqsadlaringiz uchun etarlicha noyob qilishning arzonroq usullari mavjud. Misol uchun, RC4 ni /dev/urandom bilan ekish va undan so'ng tasodifiy oqim hosil qilish yaxshi bo'lar edi. Oddiyroq yechim Unix vaqtini mikrosoniyali ruxsat va mijoz identifikatori bilan birlashtirishni o'z ichiga oladi; u unchalik xavfsiz emas, lekin u ko'pchilik kontekstlar uchun etarli bo'lishi mumkin.

Kalitning ishlash muddatini o'lchash uchun foydalanadigan vaqt "qulf muddati" deb ataladi. Bu qiymat ham blokirovka avtomatik ravishda chiqarilgandan so‘ng, ham mijoz boshqa mijoz o‘z navbatida resursni o‘zaro istisno qilish kafolatini buzmasdan bloklashi mumkin bo‘lgunga qadar operatsiyani bajarishi kerak bo‘lgan vaqtdir. Ushbu kafolat ma'lum bir vaqt oynasi bilan cheklangan bo'lib, u qulfni sotib olgandan keyin boshlanadi.

Shunday qilib, biz qulfni olish va ochishning yaxshi usulini muhokama qildik. Tizim (agar biz yagona, har doim mavjud bo'lgan misoldan iborat taqsimlanmagan tizim haqida gapiradigan bo'lsak) xavfsiz. Keling, ushbu kontseptsiyani taqsimlangan tizimga kengaytiraylik, bu erda bizda bunday kafolatlar yo'q.

Redlock algoritmi

Algoritmning taqsimlangan versiyasi bizda N Redis ustasi borligini taxmin qiladi. Bu tugunlar bir-biridan mutlaqo mustaqil, shuning uchun biz replikatsiya yoki boshqa yashirin muvofiqlashtirish tizimidan foydalanmaymiz. Biz allaqachon bitta misolda qulfni qanday xavfsiz olish va chiqarishni tasvirlab berdik. Biz algoritm bitta misol bilan ishlashda ushbu usuldan foydalanadi deb taxmin qilamiz. Bizning misollarimizda biz N ni 5 ga qo'ydik, bu o'rtacha qiymatdir. Shuning uchun, bir-biridan mustaqil ishlashini ta'minlash uchun turli xil kompyuterlar yoki virtual mashinalarda beshta Redis ustasidan foydalanishimiz kerak bo'ladi.

Qulfni sotib olish uchun mijoz quyidagi amallarni bajaradi:

  1. Joriy vaqtni millisekundlarda oladi.
  2. Barcha holatlarda bir xil kalit nomi va tasodifiy qiymatlardan foydalanib, ketma-ket barcha N misollarda qulfni olishga harakat qiladi. 2-bosqichda, har bir misol uchun qulfni sotib olayotganda, mijoz uni sotib olish uchun kechikishdan foydalanadi, bu qulf avtomatik ravishda chiqarilgan vaqtga nisbatan ancha qisqa. Misol uchun, agar blokirovkaning davomiyligi 10 soniya bo'lsa, kechikish ~ 5-50 millisekund oralig'ida bo'lishi mumkin. Bu, mijozning muvaffaqiyatsiz Redis tuguniga kirishga urinayotganda uzoq vaqt bloklangan holatda qolishi mumkin bo'lgan vaziyatni oldini oladi: agar namuna mavjud bo'lmasa, biz imkon qadar tezroq boshqa namunaga ulanishga harakat qilamiz.
  3. Qulfni olish uchun mijoz joriy vaqtdan 1-bosqichda olingan vaqt tamg'asini ayirib, qancha vaqt o'tganligini hisoblab chiqadi. Agar mijoz ko'p hollarda (kamida 3 ta) qulfni sotib olishi mumkin bo'lsa va qulfni olish uchun zarur bo'lgan umumiy vaqt qulfning amal qilish muddatidan kamroq bo'lsa, qulf sotib olingan hisoblanadi.
  4. Agar qulf olingan bo'lsa, uning davomiyligi 3-bosqichda hisoblangan o'tgan vaqtni ayirib tashlagan holda asl qulflash davomiyligi sifatida qabul qilinadi.
  5. Agar mijoz biron sababga ko'ra qulfni ololmasa (yoki u N/2+1 nusxalarini bloklay olmasa yoki qulfning amal qilish muddati salbiy bo'lsa), u barcha misollarni (hatto qulflay olmaydi deb o'ylaganlarni ham) qulfdan chiqarishga harakat qiladi.

Algoritm asinxronmi?

Ushbu algoritm barcha jarayonlarda sinxronlashtirilgan soat bo'lmasa-da, har bir jarayonda mahalliy vaqt hali ham taxminan bir xil tezlikda oqadi va blokirovka avtomatik ravishda chiqariladigan umumiy vaqtga nisbatan xato kichik bo'ladi, degan taxminga asoslanadi. Bu taxmin oddiy kompyuterlar uchun odatiy holatga juda o'xshaydi: har bir kompyuterda mahalliy soat mavjud va biz odatda turli kompyuterlar orasidagi vaqt farqiga ishonishimiz mumkin.

Shu nuqtada, biz o'zaro istisno qoidamizni yanada ehtiyotkorlik bilan shakllantirishimiz kerak: o'zaro istisno faqat qulfni ushlab turgan mijoz qulfning amal qilish muddati (3-bosqichda olingan qiymat) ichida tugatilgan taqdirdagina kafolatlanadi, qo'shimcha vaqtni (jarayonlar orasidagi vaqt oralig'ini qoplash uchun atigi bir necha millisekundlar) chiqarib tashlaydi.

Quyidagi qiziqarli maqola vaqt o'zgaruvchan muvofiqlashtirishni talab qiladigan shunga o'xshash tizimlar haqida batafsil ma'lumot beradi: Lizinglar: taqsimlangan fayl keshining mustahkamligi uchun samarali nosozliklarga chidamli mexanizm.

Muvaffaqiyatsiz qayta urinib ko'ring

Mijoz qulfni qo'lga kirita olmasa, tasodifiy kechikishdan keyin qayta urinib ko'rishi kerak. Bu bir vaqtning o'zida bir nechta mijozlarning bir xil resursda blokirovka qilishga urinishini oldini olish uchun amalga oshiriladi (bu g'oliblar bo'lmagan "miyaning bo'linishi" holatiga olib kelishi mumkin). Bundan tashqari, mijoz Redis misollarining aksariyatida qulfni qanchalik tez qo'lga kiritishga harakat qilsa, miyaning bo'linishi bilan bog'liq vaziyat yuzaga kelishi mumkin bo'lgan oyna shunchalik torroq bo'ladi (va qayta urinishlar kamroq talab qilinadi). Shuning uchun, ideal holda, mijoz bir vaqtning o'zida SET buyruqlarini multiplekslash yordamida N nusxaga yuborishga harakat qilishi kerak.

Shu o‘rinda shuni ta’kidlab o‘tish joizki, o‘z qulflarining ko‘p qismini qo‘lga kirita olmagan mijozlar o‘zlari qo‘lga kiritgan qulflarni (qisman) bo‘shatishlari qanchalik muhimligini, shunda ular resursda qulfni qayta qo‘lga kiritishdan oldin kalitning amal qilish muddati tugashini kutishlariga to‘g‘ri kelmaydi (garchi tarmoq bo‘linishi sodir bo‘lsa va mijoz kutish vaqtida ulanishni yo‘qotsa ham. kalitning amal qilish muddati tugashi uchun).

Qulfni ochish

Qulfni bo'shatish oddiy operatsiya bo'lib, mijoz ma'lum bir nusxani muvaffaqiyatli bloklay olganiga ishonadimi yoki yo'qligidan qat'i nazar, barcha misollarni qulfdan chiqarishni talab qiladi.

Xavfsizlik masalalari

Algoritm xavfsizmi? Keling, turli stsenariylarda nima sodir bo'lishini tasavvur qilishga harakat qilaylik.

Boshlash uchun, mijoz ko'p hollarda qulfni qo'lga kirita oldi deb faraz qilaylik. Har bir misol barcha misollarda bir xil umrga ega kalitni o'z ichiga oladi. Biroq, bu kalitlarning har biri boshqa vaqtda o'rnatilgan, shuning uchun ularning amal qilish muddati turli vaqtlarda tugaydi. Biroq, agar birinchi kalit T1 dan yomon bo'lmagan vaqtda o'rnatilgan bo'lsa (birinchi server bilan bog'lanishdan oldin biz tanlagan vaqt) va oxirgi kalit T2 dan yomon bo'lmagan vaqtda o'rnatilgan bo'lsa (oxirgi serverdan javob olingan vaqt), unda biz to'plamdagi birinchi kalitning amal qilish muddati kamida mavjud bo'lishiga aminmiz. MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFTBoshqa barcha kalitlarning amal qilish muddati keyinroq tugaydi, shuning uchun barcha kalitlar bir vaqtning o'zida kamida shuncha vaqt davomida amal qilishiga amin bo'lishimiz mumkin.

Aksariyat kalitlar amalda bo'lgan vaqt davomida boshqa mijoz qulfni qo'lga kirita olmaydi, chunki N/2+1 SET NX operatsiyalari N/2+1 tugmalari allaqachon mavjud bo'lsa, muvaffaqiyatga erisha olmaydi. Shuning uchun, qulf sotib olingandan so'ng, uni bir vaqtning o'zida qayta sotib olish mumkin emas (bu o'zaro istisno xususiyatini buzadi).
Biroq, biz bir vaqtning o'zida qulfni olishga urinayotgan bir nechta mijozlar bir vaqtning o'zida muvaffaqiyat qozona olmasligiga ishonch hosil qilishni xohlaymiz.

Agar mijoz maksimal blokirovka muddatiga teng yoki undan ko'p vaqt ichida ko'pchilik misollarni bloklagan bo'lsa, u qulfni yaroqsiz deb hisoblaydi va misollarni qulfdan chiqaradi. Shuning uchun, biz mijozning ko'p holatlarni qulflash muddatidan qisqaroq vaqt ichida qulflashga muvaffaq bo'lgan holatni ko'rib chiqishimiz kerak. Bunday holda, yuqoridagi dalilga kelsak, in MIN_VALIDITY Hech bir mijoz qulfni qayta sotib ololmasligi kerak. Shu sababli, bir nechta mijozlar N/2+1 nusxalarini bir xil vaqt ichida bloklashi mumkin bo'ladi (bu 2-bosqichning tugashi bilan tugaydi), agar ko'pchilik blokirovka vaqti TTLdan kattaroq bo'lsa, bu qulfni bekor qiladi.

Xavfsizlikning rasmiy isbotini taqdim eta olasizmi, mavjud shunga o'xshash algoritmlarni ko'rsata olasizmi yoki taqdim etilgan narsada xato topasizmi?

Foydalanish imkoniyatini hisobga olish

Tizimning mavjudligi uchta asosiy xususiyatga bog'liq:

  1. Avtomatik qulfdan chiqarish (kalitlarning amal qilish muddati tugashi bilan): kalitlar oxir-oqibat qulflar uchun foydalanish uchun yana mavjud bo'ladi.
  2. Istalgan qulf olinmagan yoki sotib olingan, ammo ish tugallangan bo'lsa, mijozlar odatda qulflarni olib tashlash orqali bir-birlariga yordam berishlari; shuning uchun biz qulfni qayta tiklash uchun kalitlarning amal qilish muddati tugashini kutishimiz shart emas.
  3. Mijoz qulfni sotib olishga qayta urinib ko'rishi kerak bo'lganda, u ko'pchilik qulflarni olish uchun zarur bo'lgan vaqtdan nisbatan uzoqroq vaqtni kutadi. Bu resurs nizosidan kelib chiqadigan bo'lingan miya vaziyati ehtimolini kamaytiradi.

Shu bilan birga, tarmoq segmentlarida TTL vaqtiga teng bo'lgan kamaytirilgan mavjudlik uchun jarima mavjud, shuning uchun agar qo'shni segmentlar mavjud bo'lsa, bu jazo cheksiz bo'lishi mumkin. Bu mijoz qulfni qo'lga kiritganida va uni bo'shatishdan oldin boshqa segmentga kesilganda sodir bo'ladi.

Asosan, cheksiz uzluksiz tarmoq segmentlarini hisobga olgan holda, tizim cheksiz vaqt davomida ishlamasligi mumkin.

Ishlash, uzilish va fsync

Ko'p odamlar Redis-dan foydalanadilar, chunki ular qulflarni olish va chiqarish uchun zarur bo'lgan kechikish, shuningdek, soniyada bajarilishi mumkin bo'lgan xaridlar/relizlar soni nuqtai nazaridan yuqori blokirovka serverining ishlashini talab qiladi. Ushbu talabni qondirish uchun N Redis serverlari uchun kechikishni kamaytirish uchun aloqa strategiyasi mavjud. Bu multiplekslash strategiyasi (yoki "kambag'allarning multiplekslashi", bunda rozetka bloklanmaydigan rejimga o'rnatiladi, barcha buyruqlarni yuboradi va mijoz va har bir misol o'rtasida o'xshash aylanish vaqtini hisobga olgan holda buyruqlarni keyinroq oladi).

Ammo, agar biz ishonchli nosozlikni tiklaydigan model yaratmoqchi bo'lsak, ma'lumotlarni uzoq muddatli saqlashni ham hisobga olishimiz kerak.

Muammoni aniqlashtirish uchun, Redis-ni hech qanday doimiy ma'lumotlarni saqlashsiz sozlaymiz. Mijoz beshta misoldan uchtasini blokirovka qilishga muvaffaq bo'ladi. Mijoz blokirovka qilishga muvaffaq bo'lgan holatlardan biri qayta ishga tushiriladi, bunda biz bloklashimiz mumkin bo'lgan bir xil resurs uchun yana uchta nusxa yaratiladi. Boshqa mijoz, o'z navbatida, qayta ishga tushirilgan namunani bloklashi mumkin, bu esa qulflash eksklyuzivligining xavfsizlik xususiyatini buzadi.

Vaqtdan oldin (AOF) funksiyasini yoqish vaziyatni biroz yaxshilaydi. Masalan, siz SHUTDOWN buyrug'ini yuborish va uni qayta ishga tushirish orqali serverni targ'ib qilishingiz mumkin. Redis muddati tugashi operatsiyalari semantik tarzda amalga oshirilganligi sababli, hatto server o'chirilgan bo'lsa ham, vaqt o'tishda davom etadi, bizning barcha talablarimiz bajariladi. Agar oqlangan o'chirish ta'minlansa, bu yaxshi. Ammo elektr uzilishlari haqida nima deyish mumkin? Agar Redis sukut bo'yicha sozlangan bo'lsa, fsync disk bilan har soniyada sinxronlashtirilsa, qayta ishga tushirilgandan so'ng biz kalitni yo'qotishimiz mumkin. Nazariy jihatdan, agar biz har qanday misolni qayta ishga tushirishda blokirovka xavfsizligini kafolatlamoqchi bo'lsak, uni yoqishimiz kerak fsync=always doimiy ma'lumotlar sozlamalarida. Bu taqsimlangan qulflarni xavfsiz amalga oshirish uchun an'anaviy ravishda ishlatiladigan CP tizimlari darajasiga qadar ishlashni butunlay o'ldiradi.

Ammo vaziyat birinchi qarashda ko'rinadiganidan yaxshiroq. Asosan, algoritmning xavfsizligi saqlanib qoladi, chunki nosozlikdan keyin namuna qayta ishga tushirilganda, u hozirda faol blokirovkalarda qatnashmaydi.

Buni kafolatlash uchun biz shunchaki nosozlikdan keyin misol biz foydalanayotgan maksimal TTLdan bir oz ko‘proq vaqt davomida ishlamay qolishiga ishonch hosil qilishimiz kerak. Bu ishlamay qolganda faol bo'lgan barcha kalitlarning amal qilish muddati tugashiga va avtomatik ravishda chiqarilishiga imkon beradi.

Kechiktirilgan qayta ishga tushirishdan foydalanib, Redis-da uzoq muddatli barqarorliksiz ham xavfsizlikka erishish mumkin. Ammo shuni ta'kidlash joizki, bu mavjudlik qoidalarini buzganlik uchun jarimaga olib kelishi mumkin. Misol uchun, agar aksariyat hollarda muvaffaqiyatsiz bo'lsa, tizim TTL uchun global miqyosda ishlamay qoladi (va bu vaqt davomida hech qanday resurs bloklanishi mumkin emas).

Algoritmning mavjudligini oshirish: blokirovka qilish muddatini uzaytirish

Agar mijozlar tomonidan bajariladigan ish kichik bosqichlardan iborat bo'lsa, standart qulfning ishlash muddatini qisqartirish va qulfni yangilash mexanizmini amalga oshirish mumkin. Printsipial jihatdan, agar mijoz hisob-kitoblarni bajarish bilan band bo'lsa va blokirovka muddati xavfli darajada past bo'lsa, kalit hali ham mavjud bo'lsa va uning qiymati qulfni sotib olishda olingan tasodifiy qiymat bo'lsa, TTL kalitini kengaytiradigan barcha holatlarga Lua skripti yuborilishi mumkin.

Mijoz, agar ular amal qilish muddati ichida ko'pchilik holatlarni muvaffaqiyatli bloklagan bo'lsa, qulfni qayta sotib olish mumkin deb hisoblashi kerak.

Biroq, texnik jihatdan algoritm o'zgarmaydi, shuning uchun qulflarni olish uchun takroriy urinishlarning maksimal soni cheklangan bo'lishi kerak, aks holda mavjudlik xususiyatlari buziladi.

Manba: www.habr.com