Design Logger Rate Limiter

Overview

Design Logger Rate Limiter is a problem where you need to determine if a log message should be printed based on whether the same message was printed within a certain time window. A queue is perfect for this because it maintains timestamps of recent log messages and automatically removes timestamps outside the window.

This problem demonstrates:

• Rate limiting - Limit message frequency
• Time-window tracking - Track messages within time window
• Message deduplication - Prevent duplicate messages
• Efficient lookups - Quickly check if message was recently logged

Key characteristics:

• Message-based - Track messages, not just timestamps
• Time window - Same message can be logged after time window
• Queue-based - Queue maintains recent message timestamps
• O(1) check - Efficient check if message should be printed
• Automatic cleanup - Remove old timestamps automatically

How Logger Rate Limiter Works

Logger rate limiter uses a map and queue:

1. Track messages - Map message to queue of timestamps
2. Check rate limit - Check if message was logged within window
3. Record message - If allowed, add timestamp to queue
4. Cleanup - Remove timestamps outside window
5. Return result - Return whether message should be printed

The queue maintains recent timestamps for each message.

Basic Logger Rate Limiter Implementation

Simple logger rate limiter:

class Logger {
  private messageTimestamps: Map<string, number[]> = new Map();
  private windowSize: number;
  
  constructor(windowSize: number = 10) { // Default 10 seconds
    this.windowSize = windowSize;
  }
  
  shouldPrintMessage(timestamp: number, message: string): boolean {
    // Get timestamps for this message
    if (!this.messageTimestamps.has(message)) {
      this.messageTimestamps.set(message, []);
    }
    
    const timestamps = this.messageTimestamps.get(message)!;
    
    // Remove old timestamps outside window
    while (timestamps.length > 0 && timestamp - timestamps[0] >= this.windowSize) {
      timestamps.shift();
    }
    
    // Check if message was logged recently
    if (timestamps.length > 0) {
      return false; // Message logged recently, don't print
    }
    
    // Add new timestamp
    timestamps.push(timestamp);
    return true; // Can print
  }
}

Time: O(n) cleanup worst case, O(1) amortized, Space: O(m × n) where m is unique messages

Key insight: Track timestamps per message.

Pattern 1: LeetCode - Logger Rate Limiter

LeetCode problem implementation:

class Logger {
  private messageTimestamps: Map<string, number> = new Map();
  
  shouldPrintMessage(timestamp: number, message: string): boolean {
    const lastTimestamp = this.messageTimestamps.get(message);
    
    // If message not seen or last seen more than 10 seconds ago
    if (lastTimestamp === undefined || timestamp - lastTimestamp >= 10) {
      this.messageTimestamps.set(message, timestamp);
      return true;
    }
    
    return false;
  }
}

Time: O(1), Space: O(m) where m is unique messages

Key insight: Only need last timestamp per message, not queue.

Pattern 2: Logger with Queue per Message

Using queue for each message (if multiple occurrences matter):

class LoggerWithQueue {
  private messageQueues: Map<string, number[]> = new Map();
  private windowSize: number;
  
  constructor(windowSize: number = 10) {
    this.windowSize = windowSize;
  }
  
  shouldPrintMessage(timestamp: number, message: string): boolean {
    if (!this.messageQueues.has(message)) {
      this.messageQueues.set(message, []);
    }
    
    const queue = this.messageQueues.get(message)!;
    
    // Remove old timestamps
    while (queue.length > 0 && timestamp - queue[0] >= this.windowSize) {
      queue.shift();
    }
    
    // Check if message was logged recently
    if (queue.length > 0) {
      return false;
    }
    
    // Add timestamp
    queue.push(timestamp);
    return true;
  }
  
  // Get count of times message was logged in window
  getMessageCount(message: string, timestamp: number): number {
    const queue = this.messageQueues.get(message);
    if (!queue) return 0;
    
    // Remove old timestamps
    while (queue.length > 0 && timestamp - queue[0] >= this.windowSize) {
      queue.shift();
    }
    
    return queue.length;
  }
}

Time: O(n) cleanup, O(1) amortized, Space: O(m × n)

Key insight: Queue allows tracking multiple occurrences.

Pattern 3: Logger with Maximum Count

Logger that allows N messages per window:

class LoggerWithMaxCount {
  private messageQueues: Map<string, number[]> = new Map();
  private windowSize: number;
  private maxCount: number;
  
  constructor(windowSize: number = 10, maxCount: number = 1) {
    this.windowSize = windowSize;
    this.maxCount = maxCount;
  }
  
  shouldPrintMessage(timestamp: number, message: string): boolean {
    if (!this.messageQueues.has(message)) {
      this.messageQueues.set(message, []);
    }
    
    const queue = this.messageQueues.get(message)!;
    
    // Remove old timestamps
    while (queue.length > 0 && timestamp - queue[0] >= this.windowSize) {
      queue.shift();
    }
    
    // Check if exceeded max count
    if (queue.length >= this.maxCount) {
      return false;
    }
    
    // Add timestamp
    queue.push(timestamp);
    return true;
  }
}

Time: O(n) cleanup, O(1) amortized, Space: O(m × n)

Key insight: Allow multiple messages up to max count.

Pattern 4: Logger with Different Rates per Message Type

Logger with different rate limits for different message types:

class LoggerWithMessageTypes {
  private messageQueues: Map<string, number[]> = new Map();
  private rateLimits: Map<string, { window: number, maxCount: number }> = new Map();
  
  constructor() {
    // Set default rate limits
    this.rateLimits.set('error', { window: 60, maxCount: 10 });
    this.rateLimits.set('warning', { window: 30, maxCount: 5 });
    this.rateLimits.set('info', { window: 10, maxCount: 1 });
  }
  
  shouldPrintMessage(timestamp: number, message: string, messageType: string = 'info'): boolean {
    const key = `${messageType}:${message}`;
    const limit = this.rateLimits.get(messageType) || { window: 10, maxCount: 1 };
    
    if (!this.messageQueues.has(key)) {
      this.messageQueues.set(key, []);
    }
    
    const queue = this.messageQueues.get(key)!;
    
    // Remove old timestamps
    while (queue.length > 0 && timestamp - queue[0] >= limit.window) {
      queue.shift();
    }
    
    // Check rate limit
    if (queue.length >= limit.maxCount) {
      return false;
    }
    
    // Add timestamp
    queue.push(timestamp);
    return true;
  }
}

Time: O(n) cleanup, Space: O(m × n)

Key insight: Different rate limits for different message types.

Pattern 5: Logger with Sliding Window

Logger that tracks sliding window of messages:

class SlidingWindowLogger {
  private messageWindows: Map<string, number[]> = new Map();
  private windowSize: number;
  
  constructor(windowSize: number = 10) {
    this.windowSize = windowSize;
  }
  
  shouldPrintMessage(timestamp: number, message: string): boolean {
    if (!this.messageWindows.has(message)) {
      this.messageWindows.set(message, []);
    }
    
    const window = this.messageWindows.get(message)!;
    
    // Remove timestamps outside window
    while (window.length > 0 && timestamp - window[0] >= this.windowSize) {
      window.shift();
    }
    
    // Check if any message in window
    if (window.length > 0) {
      return false;
    }
    
    // Add to window
    window.push(timestamp);
    return true;
  }
  
  // Get all messages in current window
  getMessagesInWindow(message: string, timestamp: number): number[] {
    const window = this.messageWindows.get(message);
    if (!window) return [];
    
    // Remove old timestamps
    while (window.length > 0 && timestamp - window[0] >= this.windowSize) {
      window.shift();
    }
    
    return [...window];
  }
}

Time: O(n) cleanup, Space: O(m × n)

Key insight: Maintain sliding window per message.

Pattern 6: Logger with Bucket-Based Approach

Using buckets for better performance:

class BucketBasedLogger {
  private messageBuckets: Map<string, Map<number, number>> = new Map();
  private windowSize: number;
  
  constructor(windowSize: number = 10) {
    this.windowSize = windowSize;
  }
  
  shouldPrintMessage(timestamp: number, message: string): boolean {
    const bucket = Math.floor(timestamp / this.windowSize);
    
    if (!this.messageBuckets.has(message)) {
      this.messageBuckets.set(message, new Map());
    }
    
    const buckets = this.messageBuckets.get(message)!;
    
    // Remove old buckets
    const currentBucket = Math.floor(timestamp / this.windowSize);
    for (const [b] of buckets) {
      if (currentBucket - b >= 1) {
        buckets.delete(b);
      }
    }
    
    // Check if message in current bucket
    if (buckets.has(bucket)) {
      return false;
    }
    
    // Add to bucket
    buckets.set(bucket, timestamp);
    return true;
  }
}

Time: O(1) amortized, Space: O(m)

Key optimization: Bucket messages by time window.

Pattern 7: Distributed Logger Rate Limiter

Logger for distributed systems:

class DistributedLogger {
  private loggers: Map<string, Logger> = new Map();
  private windowSize: number;
  
  constructor(windowSize: number = 10) {
    this.windowSize = windowSize;
  }
  
  shouldPrintMessage(serverId: string, timestamp: number, message: string): boolean {
    if (!this.loggers.has(serverId)) {
      this.loggers.set(serverId, new Logger(this.windowSize));
    }
    
    const logger = this.loggers.get(serverId)!;
    return logger.shouldPrintMessage(timestamp, message);
  }
  
  // Check across all servers
  shouldPrintMessageGlobal(timestamp: number, message: string): boolean {
    for (const logger of this.loggers.values()) {
      if (!logger.shouldPrintMessage(timestamp, message)) {
        return false;
      }
    }
    return true;
  }
}

Time: O(servers), Space: O(servers × m)

Use case: Rate limit across multiple servers.

When to Use Queue for Logger Rate Limiter

Use queue for logger rate limiter when you see:

• "Rate limiter" - Limit message/request frequency
• "Logger" - Prevent duplicate log messages
• "Time window" - Same message within time window
• "Message throttling" - Throttle message frequency
• "Duplicate prevention" - Prevent duplicate messages
• "Sliding window" - Track messages in sliding window
• "Message deduplication" - Deduplicate messages

Key distinction:

• Queue - Track multiple timestamps per message
• Single timestamp - Only need last timestamp (simpler)
• Bucket-based - More efficient for high volume

Logger Rate Limiter Patterns

| Pattern | Description | Use Case |

|---------|-------------|----------|

| Simple | One timestamp per message | Basic rate limiting |

| Queue-based | Queue of timestamps per message | Track multiple occurrences |

| Max count | Allow N messages per window | Flexible rate limiting |

| Message types | Different rates per type | Different log levels |

| Bucket-based | Bucket messages by time | High performance |

| Distributed | Across multiple servers | Distributed systems |

Remember:

• Queue for tracking multiple timestamps
• Map for tracking per message
• Cleanup old timestamps automatically

Template (Basic Logger Rate Limiter)

class LoggerTemplate {
  private messageTimestamps: Map<string, number> = new Map();
  private windowSize: number;
  
  constructor(windowSize: number = 10) {
    this.windowSize = windowSize;
  }
  
  shouldPrintMessage(timestamp: number, message: string): boolean {
    const lastTimestamp = this.messageTimestamps.get(message);
    
    if (lastTimestamp === undefined || timestamp - lastTimestamp >= this.windowSize) {
      this.messageTimestamps.set(message, timestamp);
      return true;
    }
    
    return false;
  }
}

Template (Queue-Based Logger)

class LoggerQueueTemplate {
  private messageQueues: Map<string, number[]> = new Map();
  private windowSize: number;
  
  constructor(windowSize: number = 10) {
    this.windowSize = windowSize;
  }
  
  shouldPrintMessage(timestamp: number, message: string): boolean {
    if (!this.messageQueues.has(message)) {
      this.messageQueues.set(message, []);
    }
    
    const queue = this.messageQueues.get(message)!;
    
    // Remove old timestamps
    while (queue.length > 0 && timestamp - queue[0] >= this.windowSize) {
      queue.shift();
    }
    
    // Check if message logged recently
    if (queue.length > 0) {
      return false;
    }
    
    // Add timestamp
    queue.push(timestamp);
    return true;
  }
}

Time and Space Complexity

Simple Implementation (Single Timestamp)

• shouldPrintMessage: O(1)
• Space: O(m) where m is unique messages

Queue-Based Implementation

• shouldPrintMessage: O(n) cleanup worst case, O(1) amortized
• Space: O(m × n) where m is messages, n is timestamps per message

Bucket-Based Implementation

• shouldPrintMessage: O(1) amortized
• Space: O(m)

Note: Simple implementation is most efficient if only need last timestamp.

Practice Tips

1. Choose right structure - Single timestamp vs queue vs buckets
2. Cleanup old data - Remove timestamps outside window
3. Handle edge cases - Empty map, out-of-order timestamps
4. Optimize lookups - Use map for O(1) message lookup
5. Consider memory - Queue uses more memory than single timestamp
6. Message types - Support different rate limits per type
7. Distributed - Consider distributed systems requirements

Common Mistakes

1. Not cleaning up - Forgetting to remove old timestamps
2. Using queue unnecessarily - Using queue when single timestamp suffices
3. Wrong window calculation - Off-by-one errors in window size
4. Memory leaks - Not cleaning up old message entries
5. Race conditions - Not handling concurrent access
6. Out-of-order timestamps - Not handling decreasing timestamps
7. Precision issues - Timestamp precision problems

Real-World Applications

Logger rate limiter is used extensively in:

• Logging Systems - Prevent log spam, duplicate messages
• API Rate Limiting - Limit API request frequency
• Error Reporting - Prevent error message spam
• Monitoring Systems - Throttle alert messages
• Debugging - Control debug message frequency
• Analytics - Track event frequency
• Security - Rate limit security events
• Notification Systems - Prevent notification spam

Related Concepts

• Queue - Data structure for timestamp tracking
• Rate Limiting - General rate limiting concepts
• Hit Counter - Similar time-window tracking
• Sliding Window - General sliding window pattern
• Map - For message-to-timestamps mapping

Summary

Design Logger Rate Limiter demonstrates:

• Rate limiting - Limit message frequency
• Time-window tracking - Track messages within window
• Message deduplication - Prevent duplicate messages
• Efficient lookups - O(1) message lookup with map
• Automatic cleanup - Remove old timestamps

Key takeaways:

• Use map to track timestamps per message
• Single timestamp sufficient for basic rate limiting
• Queue needed if tracking multiple occurrences
• Cleanup old timestamps automatically
• Essential for logging systems and rate limiting

Mastering logger rate limiter design will help you solve rate limiting problems, prevent log spam, and design efficient logging systems in coding interviews.