Fixed va sliding window rate limiting algoritmlari (Node.js)

Assalamu Alaykum bugun window(oraliq bilan)uslubida ishlaydigan Nodejs uchun rate limiter middleware yozib uni tekshirib ko'ramiz !!

Ushbu maqolani o'qishdan oldin bu maqolalarni o'qishni tavsiya beraman:

• Rate limiting nima ?

• Token bucket rate limiting algoritmini 0 dan yozamiz !!

• Leaky bucket rate limiting algoritmini yozamiz!

Fixed window counter

Endi birinchi bo'lib Fixed window counter algoritmini yozamiz :

Asosiy mantig'i bu berilgan intervalda so'rovlar soni limitdan oshmasligi

class FixedWindow {
  constructor(windowMs, capacity) {
    this.capacity = capacity
    this.requestCount = 0
    this.windowMs = windowMs
    this.windowResetAt = Date.now() + windowMs
  }
  tryConsume() {
    this.resetWindowIfExpired()
    if (this.requestCount >= this.capacity) {
      return false
    } else {
      this.requestCount++
      return true
    }
  }
  resetWindowIfExpired() {
    if (Date.now() > this.windowResetAt) {
      this.requestCount = 0
      this.windowResetAt = Date.now() + this.windowMs
    }
  }
  getState() {
    this.resetWindowIfExpired()
    return {
      requestCount: this.requestCount,
      capacity: this.capacity,
      windowResetAt: this.windowResetAt,
    }
  }
}
class FixedWindowRateLimiter {
  constructor(capacity, windowMs) {
    this.windows = new Map()
    this.capacity = capacity
    this.windowMs = windowMs
  }
  getWindow(key) {
    if (!this.windows.has(key)) {
      this.windows.set(key, new FixedWindow(this.windowMs, this.capacity))
    }
    return this.windows.get(key)
  }
  isAllowed(key) {
    const window = this.getWindow(key)
    return window.tryConsume()
  }
  getState(key) {
    const window = this.getWindow(key)
    return window.getState()
  }
}

FixedWindow classi bu rate limiting logikasi bo'ladi. Unda 4 ta o'zgaruvchisi 3 ta metod mavjud:

capacity — bu qancha limit qo'yilgani, requestCount esa hozirgi oraliqda nechta so'rov qabul qilingani, windowMs — bu oraliq vaqti(millisekundda) , windowResetAt — yangi oraliq boshlanish vaqti.

• resetWindowIfExpired — bu metod har bir so'rovda oraliq vaqt yakunlanganmi tekshiradi va agar yangilandan bo'lsa counterni nollashtiradi.

• tryConsume — bu so'rov qabul qilish mumkinmi yoqligini bilib beradigan metod u avval resetWindowIfExpired metodini ishlatadi va undan keyin countlarni solishtiradi.

• getState — bu rate limiterni hozirgi holatini olib beradi.

FixedWindowRateLimiter bu class rate limiter logikasini o'z ichiga olib uni har bir key(userID, Ip address) bilan ishlatishga yordam beradi.

Bular uchun testlar yozilgan va serverga ulangan kodlari repostory linki oxirida beriladi.

Endi keyingi algoritmga o'tamiz.

Sliding window log

Bu algoritm asosiy mantig'i esa istalgan chergaralangan intervalda so'rovlar soni limitdan oshmasligi kerak.

class SlidingWindowLog {
  constructor(windowMs, capacity) {
    this.windowMs = windowMs;
    this.capacity = capacity;
    this.log = [];
  }
  isAllowed() {
    const now = Date.now();
    while (this.log.length && this.log[0] <= now - this.windowMs) {
      this.log.shift();
    }
    if (this.log.length < this.capacity) {
      this.log.push(now);
      return true;
    }
    return false;
  }
  getCurrentState() {
    const now = Date.now();
    while (this.log.length && this.log[0] <= now - this.windowMs) {
      this.log.shift();
    }
    return {
      count: this.log.length,
      capacity: this.capacity,
      remaining: this.capacity - this.log.length,
      oldestTimestamp: this.log[0] ?? null,
    };
  }
}
class SlidingWindowLogRateLimiter {
  constructor(windowMs, capacity) {
    this.windows = new Map();
    this.windowMs = windowMs;
    this.capacity = capacity;
  }
  getWindow(key) {
    if (!this.windows.has(key)) {
      this.windows.set(key, new SlidingWindowLog(this.windowMs, this.capacity));
    }
    return this.windows.get(key);
  }
  isAllowed(key) {
    return this.getWindow(key).isAllowed();
  }
  getCurrentState(key) {
    return this.getWindow(key).getCurrentState();
  }
}

SlidingWindowLog classi bu rate limiting logikasi bo'ladi. Unda 3ta o'zgaruvchisi va 2ta metod mavjud:

capacity — bu qancha limit qo'yilgani, windowMs — bu oraliq vaqti(millisekundda) , log — massivi o'zida qabil qilingan so'rovlar vaqtini saqlab turadi (oraliqdan o'tib ketsa o'chirib yuboriladi)

• isAllowed— bu so'rov qabul qilish mumkinmi yoqligini bilib beradigan metod. U avval yangi kelgan so'rov va eng eski qabul qilingan so'rov vaqtini tekshiradi va u berilgan intervaldan katta bo'lsa ularni olib tashlaydi va agar qabul qilingan so'rovlar limitga yetmagan bo'lsa ular yangi so'rovlar qabul qilinadi.

• getCurrentState — bu rate limiterni hozirgi holatini olib beradi unda limit , qancha so'rov qabul qolgani va eng eski so'rov vaqti beriladi.

SlidingWindowLogRateLimiter bu class rate limiter logikasini o'z ichiga olib uni har bir key(userID, Ip address) bilan ishlatishga yordam beradi.

Sliding window counter

Bu algoritm mantig'i oldingi algoritmdagidek hamm vaqtlarni yozib ko'p xotira olaydi va u oldingi intervaldagi so'rovlar sonini hisobga olgan holda taxminiy count yaratadi bu kam xotira olgan holda ammo birdan ko'p trafik o'tkazib yubormaslikga yordam beradi . (Aniq intervalda limitdan sal ko'proq so'rov ketishi mumkin)

class SlidingWindowCounter {
  #capacity;
  #windowMs;
  #windowStart;
  #currentCount = 0;
  #previousCount = 0;
  constructor(windowMs, capacity) {
    this.#windowMs = windowMs;
    this.#capacity = capacity;
    this.#windowStart = Date.now();
  }
  tryConsume() {
    this.#roll();
    if (this.#estimate() >= this.#capacity) {
      return false;
    }
    this.#currentCount++;
    return true;
  }
  #estimate() {
    const elapsed = Date.now() - this.#windowStart;
    const prevWeight = 1 - elapsed / this.#windowMs;
    return this.#previousCount * prevWeight + this.#currentCount;
  }
  #roll() {
    const elapsedWindows = Math.floor(
      (Date.now() - this.#windowStart) / this.#windowMs,
    );
    if (elapsedWindows <= 0) return;
    this.#previousCount = elapsedWindows === 1 ? this.#currentCount : 0;
    this.#currentCount = 0;
    this.#windowStart += elapsedWindows * this.#windowMs;
  }
  getState() {
    this.#roll();
    return {
      previousCount: this.#previousCount,
      currentCount: this.#currentCount,
      estimated: this.#estimate(),
      capacity: this.#capacity,
      windowEndsAt: this.#windowStart + this.#windowMs,
    };
  }
}
class SlidingWindowCounterRateLimiter {
  constructor(windowMs, capacity) {
    this.windows = new Map();
    this.windowMs = windowMs;
    this.capacity = capacity;
  }
  getWindow(key) {
    if (!this.windows.has(key)) {
      this.windows.set(
        key,
        new SlidingWindowCounter(this.windowMs, this.capacity),
      );
    }
    return this.windows.get(key);
  }
  isAllowed(key) {
    return this.getWindow(key).tryConsume();
  }
  getCurrentState(key) {
    return this.getWindow(key).getState();
  }
}

SlidingWindowCounter classi bu rate limiting logikasi bo'ladi. Unda 5ta o'zgaruvchisi va 4 ta metod mavjud:

#capacity — bu qancha limit qo'yilgani, #windowMs — bu oraliq vaqti(millisekundda) , windowStart — oraliq boshlanish vaqti ,

currentCount — hozirgi intervaldagi qabul qilingan so'rovlar soni, previousCount — oldingi intervaldagi qabul qilingan so'rovlar soni .

• #estimate — bu oldingi interval count va hozirgi vaqt intervali kesishmalarini hisobga olgan holda qancha so'rov qabul qilinganini hisoblab beradi.

• #roll — bu metod har bir so'rovda oraliq vaqt yakunlanganmi tekshiradi va agar yangilandan bo'lsa counterni nollashtiradi va hozirgi counterni eski deb belgilaydi.

• tryConsume — bu so'rov qabul qilish mumkinmi yoqligini bilib beradigan metod u avval #roll va #estimatemetodini ishlatadi va undan keyin countlarni solishtiradi.

• getState — bu rate limiterni hozirgi holatini olib beradi unda limit , oldingi va hozirgi intervaldagi so'rovlar countini va interval vaqtini olib beradi.

SlidingWindowCounterRateLimiter bu class rate limiter logikasini o'z ichiga olib uni har bir key(userID, Ip address) bilan ishlatishga yordam beradi.

Hamma kodlarni ushbu repodan olishingiz mumkin. Repo

Xulosa

Xulosa qilib aytadigan bo'lsak fixed window algoritmi oson ammo burst trafikni o'tkazib yuboradi, sliding window log algoritmi esa juda aniq ishlaydi ammo xotirada ko'p joy oladi , sliding window counter bu tepadagi uslub qorishmasi bo'lib juda aniq hisoblamasada ko'p tarfikni ham birdaniga qo'yib yubormaydi. Algoritm tanlash esa siz qaysi holat uchun ishlatishingiz muhim.