lundi 28 juin 2021

Is this request frequency limiter thread safe?

In order to prevent excessive server pressure, I implemented a request frequency limiter using a sliding window algorithm, which can determine whether the current request is allowed to pass according to the parameters. In order to achieve the thread safety of the algorithm, I used the atomic type to control the number of sliding steps of the window, and used unique_lock to achieve the correct sum of the total number of requests in the current window. But I'm not sure whether my implementation is thread-safe, and if it is safe, whether it will affect service performance. Is there a better way to achieve it?

class SlideWindowLimiter
{
public:
  bool TryAcquire();
  void SlideWindow(int64_t window_number);

private:
  int32_t limit_;   // maximum number of window requests
  int32_t split_num_;   // subwindow number
  int32_t window_size_; // the big window
  int32_t sub_window_size_;  // size of subwindow = window_size_ / split_number
  
  int16_t index_{0};  //the index of window vector
  std::mutex mtx_;
  std::vector<int32_t> sub_windows_;  // window vector 
  std::atomic<int64_t> start_time_{0};  //start time of limiter
}

bool SlideWindowLimiter::TryAcquire() {
   int64_t cur_time = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::system_clock::now().time_since_epoch()).count();
   auto time_stamp = start_time_.load();
   int64_t window_num = std::max(cur_time - window_size_ - start_time_, int64_t(0)) / sub_window_size_;
    
   std::unique_lock<std::mutex> guard(mtx_, std::defer_lock);
   if (window_num > 0  && start_time_.compare_exchange_strong(time_stamp, start_time_.load() + window_num*sub_window_size_)) {
     guard.lock();
     SlideWindow(window_num);
     guard.unlock();
   }
 
   monitor_->TotalRequestQps();
   {
     guard.lock();
     int32_t total_req = 0;
     std::cout<<" "<<std::endl;
     for(auto &p : sub_windows_) {
       std::cout<<p<<" "<<std::this_thread::get_id()<<std::endl;
       total_req += p;
     }
 
     if(total_req >= limit_) {
       monitor_->RejectedRequestQps();
       return false;
     } else {
       monitor_->PassedRequestQps();
       sub_windows_[index_] += 1;
       return true;
     }
     guard.unlock();
   }
 }

void SlideWindowLimiter::SlideWindow(int64_t window_num) {
   int64_t slide_num = std::min(window_num, int64_t(split_num_));  
   for(int i = 0; i < slide_num; i++){
     index_ += 1;
     index_ = index_ % split_num_;
     sub_windows_[index_] = 0;
   }
 }

Aucun commentaire:

Enregistrer un commentaire