Rate limiting nima? Token bucket, sliding window algoritmlari
Assalamu Alaykum bugun biz System designdagi yana bir mavzu rate limitingnimaligi va u nimaga keraligi hamda qanaqa usullarda rate limiting qilish mumkinligini ko'rib chiqamiz.
Rate limiting nima ?
Tarmoq orqali bog'langan sistemalarda foydalanuvchi yoki servisdan kelayotgan traffikni boshqarish uchun rate limiterdan foydalaniladi. Rate limiter malum bir vaqt ichida foydalanuvchi tomonidan uzatilayotgan so'rovlarni chegaralaydi ya'ni limitdan oshsa o'tkazmaydi.
Rate limiter bizga qanday yordam beradi ?
Rate limiter so'rovlardan serverda load ko'payib ketmasligi va foydalanuvchilar o'rtasida servisdan bir xil darajada foydalanishga yordam beradi. Bundan tashqari DDOS hujumi orqali serverda resurs yetishmay qolishini oldini oladi . Har bir katta kompaniya APIlarida bu mavjud, masalan Twitterda foydalanuvchi 3 soatda 300ta tweet qila oladi.
Xarajatlarni kamaytirish, ba'zi so'rovlarni cheklash orqali yuqori darajadagi tasklarni qilish mumkin hamda bu third part servicelarni ishlatadigan kompaniyalar uchun ham juda qulay chunki ular har bir so'rovga pul to'lashadi.
Rate limiting algoritmlari
Rate limiting uchun bir necha algoritmlar mavjud va har birining o'zini ishlatish joyi bor , ular quyidagilar :
Token bucket
Leaking bucket
Fixed window counter
Sliding window log
Sliding window counter
Token bucket algoritmi
U quyidagicha ishlaydi , bucketda oldindan belgilangan miqdorda tokenlar mavjud bo'ladi . Tokenlar malum muddatda (bir xil intervalda) bucketga qo'shilib boradi agarda bucketdagi tokenlar soni chegaraga yetib kelsa qolgan tokenlar qo'shilmaydi.
Har bir so'rov bir tokendan foydalanadi , so'rov kelganda bucket token olish uchun tekshiriladi:
Agarda bucketda keraklicha token bo'lsa , bir tokenni olib so'rovni o'tkazib yuboramiz.
Agarda bucketda yetarli token bo'lmasa so'rov bekor qilinadi.
Token bucket algoritmi 2 ta parameter qabul qiladi:
— Bucket hajmi. Maksimal ruxsat berilgan tokenlar soni.
— To'ldirish miqdori. Interval bilan qo'shiladigan tokenlar soni .
Bizga qancha bucket kerak bo'ladi , bu biz qo'yadigan qoidaga bog'liq.
— Odatda har bir API uchun alohida bucket kerak bo'ladi. Masalan, bir foydalanuvchi soatiga 100 ta friend so'rovi jo'nata oladi va sekundiga 3 ta tweet qiladi oladi bunda biz har bir user uchun 2 tadan bucket kerak bo'ladi.
Yaxshi tarafi :
— Tushunishga va ishlatishga oson algoritm
— Memory efficient
— Trafik birdan ko'payishiga ma'lum muddat imkon beradi . Token bo'lsa so'rov o'tkaziladi.
Yomon tomoni holatga moslash qiyin bo'lishi mumkin.
Amazon va Stripe bu uslubdan foydalanadi .
Leaking bucket algoritmi
Leaking bucket algoritmi ham token bucket uslubiga o'xshaydi ammo bu bir xil belgilangan miqdorda so'rovlarni ishlaydi. Odatda First in First Out FIFO uslubida implimentatsiya qilinadi. U quyidagicha ishlaydi so'rov kelganda bucket to'lgan yoki to'lmaganligi tekshiriladi , to'lmagan bo'lsa so'rov queuega qo'shiladi , agarda to'lgan bo'lsa so'rov bekor qilinadi.
Leaking bucket algoritmi 2 ta parameter qabul qiladi:
— Bucket hajmi . Bu queueni hajmiga teng bo'ladi. Queue so'rovlarni keyin bir xil miqdorda process bo'lishi uchun ushlab turadi.
— Process qilish miqdori. Bu berilgan vaqt ichida nechta so'rov process qilishi .
Yaxshi tomoni:
— Memory efficient chunki queue hajmiga limit qo'yamiz
— So'rovlar bir xil miqdorda process qilinadi bu server load ko'paymaydi.
Yomon tomoni:
— Trafik birdan ko'payishdagi so'rovlar vaqtida process qilinmasa queueni to'ldirib qo'yishi mumkin, yaqinda uzatilgan so'rovlar bekor qilinadi.
— Parameterlarni to'g'ri tune qilish qiyin.
Shopify va boshqa ecommerce bu uslubdan foydalanishadi.
Fixed window counter algoritm
Bu uslub quyidagich ishlaydi, algoritm timelineni bir xil qismlarga bo'lib chiqadi va ularga counter begilab ketadi. Har bir request counterga 1 qo'shadi. Counter oldindan belgilangan limitga yetganda keyingi so'rovlar bekor qilinadi.
Yaxshi tomoni:
— Memory efficient
— Tushunishga oson
Bu algoritmdagi asosiy muammo traffik time window oxirida ko'tarilganda belgilangan limitdan oshiq miqdorda so'rovlar o'tib ketishi mumkin.
Sliding window log algoritm
Oldingi sulubda aytganimizdek window time oxirgi qismida ko'p so'rovlar kelsa o'tkazib yuborishi mumkin edi , sliding window xuddi shu muammoni hal qilishga yordam beradi.
Algoritmda har bir so'rovning kelgan vaqti ,odatda redisda saqlanadi , agarda yangi so'rov kelsa eski so'rovlar hisonga olinmayd , eski so'rovlar hozirgi time window boshlanish vaqtidan oldingi so'rovlar. Yangi so'rov vaqti loglarga qo'shiladi agarda log hajmi belgilangan limitdan kam bo'lsa so'rov o'tkazib yuboriladi aks holda bekor qilinadi.
Yaxshi tomoni:
— Bu algoritm juda aniq , istalgan vaqt qismida so'rovlar belgilangan limitdan oshmaydi.
Yomon tomoni:
— Algoritm juda ko'p xotira egallaydi , chunki so'rov bekor qilinsa ham logda uning vaqti qolib ketadi.
Sliding window counter algoritmi
Sliding window bu oldinggi 2 uslubni qo'shilgani , u quyidagicha ishlaydi hozirgi time windowdagi so'rovlar soni va oldingi window bilan kesishadigan qism so'rovlar soni foizi bilan hisoblanadi.
Masalan , rate limit bu 7 ta so'rov minutiga , oldingi minutda 5 ta hozirgi minutda 3 ta so'rov bor , umumiy so'rovlar quyidagicha hisoblanadi:
5 * 0.4 + 3 = 5 biz yana 2 ta so'rovga ruxsat bera olamiz.
Yaxshi tomoni :
— Memory efficient
— Trafik oshishiga biroz imkoni berishi mumkin oldingi windowdagi so'rovlar o'rtachasini olganligi tufayli.
Yomon tomoni :
Bu uslub yaxshi bo'lmasligi mumkin chunki aniq emas , chunki biz oldingi time windowda so'rovlar teng taqsimlangan deb hisobladik . Ammo bu muammo bo'lmasligi mumkin Cloudflare uchun bu 400 million so'rovda 0.003% gina amalga oshgan.
Rate limitda qochish yoki to'g'ri foydalanish uchun quyidagilarni qilish kerak:
— Client tomondagi cachedan foydalanish va tez-tez API callar qilishdan qochish
— Limitni tushnungan holda undan ortiq so'rovlar uzatmaslik
— Limitdan kelgan xatoliklarni ushlash va so'rovni qayta takrorlash.
Keyingi maqola rate limiting algoritmlarini implimentatsiya qilish va ishlatib ko'rish haqida bo'ladi.
Xulosa
Xulosa qilib aytganda rate limiting implimentatsiya qilayotganda dasturning kattaligi , va sizga keladigan so'rovlar uslubini bilishingiz kerak. Kerakli so'rovlarni bekor qilmaslik uchun.
Bunda tashqari har doim foydalanuvchilar bilan reate limit haqidagi ma'lumotlarni berish , va bu orqali ular o'zlariga mos qayta urinib ko'rishlari mumkin.