/**
* Rate Limiter Implementation using Queue-based DSA
* Prevents resource exhaustion and implements sliding window rate limiting
* Uses circular queue for efficient memory usage
*/
import { logger } from './logger.js';
export interface RateLimitConfig {
/** Maximum number of requests allowed in the time window */
maxRequests: number;
/** Time window in milliseconds */
windowMs: number;
/** Identifier for this limiter (e.g., 'azure-cli', 'database-queries') */
limiterId: string;
}
export interface RateLimitResult {
/** Whether the request is allowed */
allowed: boolean;
/** Current number of requests in window */
currentCount: number;
/** Maximum allowed requests */
limit: number;
/** Time until next request is allowed (if blocked) */
retryAfterMs?: number;
/** Remaining requests in current window */
remaining: number;
}
/**
* Queue node for tracking request timestamps
* DSA: Queue (FIFO - First In First Out)
*/
interface RequestTimestamp {
timestamp: number;
correlationId?: string;
}
/**
* Circular queue implementation for efficient memory usage
* DSA: Circular Queue with fixed capacity
* Time Complexity: O(1) for enqueue/dequeue
* Space Complexity: O(n) where n = maxRequests
*/
class CircularQueue<T> {
private items: (T | null)[];
private head: number = 0;
private tail: number = 0;
private count: number = 0;
private capacity: number;
constructor(capacity: number) {
this.capacity = capacity;
this.items = new Array(capacity).fill(null);
}
enqueue(item: T): boolean {
if (this.isFull()) {
return false;
}
this.items[this.tail] = item;
this.tail = (this.tail + 1) % this.capacity;
this.count++;
return true;
}
dequeue(): T | null {
if (this.isEmpty()) {
return null;
}
const item = this.items[this.head];
this.items[this.head] = null;
this.head = (this.head + 1) % this.capacity;
this.count--;
return item;
}
peek(): T | null {
if (this.isEmpty()) {
return null;
}
return this.items[this.head];
}
isEmpty(): boolean {
return this.count === 0;
}
isFull(): boolean {
return this.count === this.capacity;
}
size(): number {
return this.count;
}
toArray(): T[] {
const result: T[] = [];
let index = this.head;
for (let i = 0; i < this.count; i++) {
if (this.items[index] !== null) {
result.push(this.items[index]!);
}
index = (index + 1) % this.capacity;
}
return result;
}
clear(): void {
this.items.fill(null);
this.head = 0;
this.tail = 0;
this.count = 0;
}
}
/**
* Rate Limiter using Sliding Window Algorithm with Queue
* Implements token bucket-like behavior with precise tracking
*/
export class RateLimiter {
private config: RateLimitConfig;
// Queue to track request timestamps (DSA: Queue)
private requestQueue: CircularQueue<RequestTimestamp>;
// HashMap to track rate limits per user/client (DSA: HashMap)
private clientQueues: Map<string, CircularQueue<RequestTimestamp>>;
constructor(config: RateLimitConfig) {
this.config = config;
this.requestQueue = new CircularQueue<RequestTimestamp>(config.maxRequests * 2);
this.clientQueues = new Map();
logger.info('Rate limiter initialized', {
limiterId: config.limiterId,
maxRequests: config.maxRequests,
windowMs: config.windowMs
});
}
/**
* Checks if a request is allowed under rate limits
* Uses sliding window algorithm
* Time Complexity: O(n) where n = requests in window (bounded by maxRequests)
*/
checkLimit(clientId: string = 'global', correlationId?: string): RateLimitResult {
const now = Date.now();
const windowStart = now - this.config.windowMs;
// Get or create queue for this client
if (!this.clientQueues.has(clientId)) {
this.clientQueues.set(clientId, new CircularQueue<RequestTimestamp>(this.config.maxRequests * 2));
}
const queue = this.clientQueues.get(clientId)!;
// Remove expired requests from queue (sliding window cleanup)
this.cleanupExpiredRequests(queue, windowStart);
const currentCount = queue.size();
// Check if limit exceeded
if (currentCount >= this.config.maxRequests) {
const oldestRequest = queue.peek();
const retryAfterMs = oldestRequest
? Math.max(0, (oldestRequest.timestamp + this.config.windowMs) - now)
: this.config.windowMs;
logger.warn('Rate limit exceeded', {
limiterId: this.config.limiterId,
clientId,
correlationId,
currentCount,
limit: this.config.maxRequests,
retryAfterMs
});
return {
allowed: false,
currentCount,
limit: this.config.maxRequests,
retryAfterMs,
remaining: 0
};
}
// Add new request to queue
const request: RequestTimestamp = { timestamp: now, correlationId };
queue.enqueue(request);
const remaining = this.config.maxRequests - (currentCount + 1);
logger.debug('Rate limit check passed', {
limiterId: this.config.limiterId,
clientId,
correlationId,
currentCount: currentCount + 1,
remaining
});
return {
allowed: true,
currentCount: currentCount + 1,
limit: this.config.maxRequests,
remaining
};
}
/**
* Removes expired requests from queue using sliding window
* Time Complexity: O(k) where k = number of expired requests
*/
private cleanupExpiredRequests(queue: CircularQueue<RequestTimestamp>, windowStart: number): void {
let cleaned = 0;
while (!queue.isEmpty()) {
const oldest = queue.peek();
if (!oldest || oldest.timestamp >= windowStart) {
break; // No more expired requests
}
queue.dequeue();
cleaned++;
}
if (cleaned > 0) {
logger.debug('Cleaned expired requests', {
limiterId: this.config.limiterId,
cleaned
});
}
}
/**
* Async wait until request can be allowed
* Uses exponential backoff with jitter
*/
async waitForSlot(clientId: string = 'global', correlationId?: string): Promise<void> {
const maxRetries = 10;
let retries = 0;
while (retries < maxRetries) {
const result = this.checkLimit(clientId, correlationId);
if (result.allowed) {
return;
}
// Exponential backoff with jitter
const baseDelay = result.retryAfterMs || 1000;
const jitter = Math.random() * 500; // Random 0-500ms
const delay = Math.min(baseDelay + jitter, 30000); // Max 30s
logger.info('Rate limit hit, waiting', {
limiterId: this.config.limiterId,
clientId,
correlationId,
delayMs: Math.round(delay),
attempt: retries + 1
});
await this.sleep(delay);
retries++;
}
throw new Error(`Rate limit exceeded after ${maxRetries} retries for ${this.config.limiterId}`);
}
/**
* Gets current status for a client
*/
getStatus(clientId: string = 'global'): {
currentCount: number;
limit: number;
remaining: number;
windowMs: number;
} {
const queue = this.clientQueues.get(clientId);
if (!queue) {
return {
currentCount: 0,
limit: this.config.maxRequests,
remaining: this.config.maxRequests,
windowMs: this.config.windowMs
};
}
// Clean up expired requests first
const windowStart = Date.now() - this.config.windowMs;
this.cleanupExpiredRequests(queue, windowStart);
const currentCount = queue.size();
return {
currentCount,
limit: this.config.maxRequests,
remaining: Math.max(0, this.config.maxRequests - currentCount),
windowMs: this.config.windowMs
};
}
/**
* Resets rate limiter for a specific client
*/
reset(clientId?: string): void {
if (clientId) {
this.clientQueues.delete(clientId);
logger.info('Reset rate limiter for client', { limiterId: this.config.limiterId, clientId });
} else {
this.clientQueues.clear();
logger.info('Reset all rate limiters', { limiterId: this.config.limiterId });
}
}
/**
* Gets all active clients being tracked
*/
getActiveClients(): string[] {
return Array.from(this.clientQueues.keys());
}
private sleep(ms: number): Promise<void> {
return new Promise(resolve => setTimeout(resolve, ms));
}
}
/**
* Rate limiter registry using HashMap pattern
* Allows multiple rate limiters for different resources
*/
export class RateLimiterRegistry {
private limiters: Map<string, RateLimiter> = new Map();
/**
* Creates or gets a rate limiter
*/
getLimiter(config: RateLimitConfig): RateLimiter {
const existing = this.limiters.get(config.limiterId);
if (existing) {
return existing;
}
const limiter = new RateLimiter(config);
this.limiters.set(config.limiterId, limiter);
return limiter;
}
/**
* Checks if a limiter exists
*/
has(limiterId: string): boolean {
return this.limiters.has(limiterId);
}
/**
* Removes a limiter
*/
remove(limiterId: string): boolean {
return this.limiters.delete(limiterId);
}
/**
* Gets all registered limiters
*/
getAllLimiters(): Map<string, RateLimiter> {
return new Map(this.limiters);
}
/**
* Resets all limiters
*/
resetAll(): void {
this.limiters.forEach(limiter => limiter.reset());
logger.info('Reset all rate limiters in registry');
}
}
/**
* Pre-configured rate limiters for common Azure operations
*/
export const createAzureRateLimiters = (): RateLimiterRegistry => {
const registry = new RateLimiterRegistry();
// Azure CLI commands: 60 per minute
registry.getLimiter({
limiterId: 'azure-cli',
maxRequests: 60,
windowMs: 60000
});
// Database queries: 100 per minute
registry.getLimiter({
limiterId: 'database-queries',
maxRequests: 100,
windowMs: 60000
});
// Destructive operations: 10 per minute
registry.getLimiter({
limiterId: 'destructive-ops',
maxRequests: 10,
windowMs: 60000
});
// API calls: 1000 per hour
registry.getLimiter({
limiterId: 'api-calls',
maxRequests: 1000,
windowMs: 3600000
});
return registry;
};
// Global registry instance
export const globalRateLimiters = createAzureRateLimiters();
