چالش های پیاده سازی ratelimiter برای یک CDN - قسمت ۱

struct Rule {
    time_duration: Duration,
    rate: usize,
}

/// State[int(now / time_duration)] -> counted requests
type State = HashMap<u128, usize>;

fn is_rate_limited(
    origin: SystemTime,
    current_time: SystemTime,
    rule: &Rule,
    state: &mut State,
) -> bool {
    let current_time_ms = current_time.duration_since(origin).unwrap().as_millis();
    let time_duration_ms = rule.time_duration.as_millis();
    let state_idx = current_time_ms / time_duration_ms;

    let t_state = state.entry(state_idx).or_insert(0);

    *t_state += 1;

    *t_state > rule.rate
}

struct Rule {
    time_duration: Duration,
    rate: u32,
}

type Request = (RequestResumer, Waiter);
type Bucket = mpsc::Sender<RequestResumer>;

async fn is_rate_limited(req: Request, bucket_tx: Bucket) -> bool {
    let (req, waiter) = req;
    match bucket_tx.try_send(req) {
        Ok(_) => {
            waiter.wait_in_queue().await;
            false
        }
        // queue is full
        Err(_) => true,
    }
}

async fn leak(rule: Rule, mut bucket_rx: mpsc::Receiver<RequestResumer>) {
    loop {
        if let Some(resumer) = bucket_rx.try_recv().ok() {
            resumer.send(()).unwrap();
        }
        sleep(rule.time_duration / rule.rate).await;
    }
}

struct Rule {
    time_duration: Duration,
    rate: usize,
}

type Log = Vec<u128>;

fn is_rate_limited(current_time: SystemTime, rule: &Rule, log: &mut Log) -> bool {
    let current_timestamp = current_time.duration_since(UNIX_EPOCH).unwrap().as_millis();
    let time_duration_ms = rule.time_duration.as_millis();
    // cleanup
    let mut logs_to_pop = 0;
    for timestamp in log.iter() {
        if *timestamp < current_timestamp - time_duration_ms {
            logs_to_pop += 1;
        }
    }
    log.drain(0..logs_to_pop);
    if log.len() >= rule.rate {
        true
    } else {
        // append
        log.push(current_timestamp);
        false
    }
}

rate = last_rate * weight + current_rate
rate = 5 * 0.8 + 0 = 4

struct Rule {
    time_duration: Duration,
    rate: usize,
}

struct State {
    /// last time we counted a request
    pub last_count_time: Instant,
    /// last block request count
    pub last_window_count: usize,
    /// current window request count
    pub current_window_count: usize,
}

fn is_rate_limited(origin: Instant, current_time: Instant, rule: &Rule, state: &mut State) -> bool {
    let duration_since_last_req = current_time.duration_since(state.last_count_time);
    if duration_since_last_req >= rule.time_duration * 2 {
        state.last_window_count = 0;
        state.current_window_count = 0;
    } else if duration_since_last_req > rule.time_duration {
        state.last_window_count = state.current_window_count;
        state.current_window_count = 0;
    }
    let t_ms = rule.time_duration.as_millis();
    let current_window_start = {
        let normal = current_time.duration_since(origin).as_millis() / t_ms;
        origin + Duration::from_millis((normal * t_ms) as _)
    };
    let w = {
        let d = current_time - current_window_start;
        let dp = if d > rule.time_duration {
            Duration::ZERO
        } else {
            rule.time_duration - d
        };
        (dp.as_millis() as f64) / t_ms as f64
    };

    let count = ((w * state.last_window_count as f64) as usize) + state.current_window_count;
    if count >= rule.rate {
        return true;
    }
    state.last_count_time = current_time;
    state.current_window_count += 1;
    false
}