Server to Process Fair Number of Functions

Solution: Priority Queues with Fair Scheduling

class FairRequestServer {
    constructor() {
        this.highPriorityQueue = [];
        this.mediumPriorityQueue = [];
        this.lowPriorityQueue = [];

        this.workers = [];
        this.numWorkers = 4;
        this.running = false;

        // Weighted round-robin ratios
        this.weights = { high: 6, medium: 3, low: 1 };
    }

    async start() {
        this.running = true;

        // Start worker threads
        for (let i = 0; i < this.numWorkers; i++) {
            this.workers.push(this.worker(i));
        }

        await Promise.all(this.workers);
    }

    stop() {
        this.running = false;
    }

    async addRequest(request, priority = 'medium') {
        const queues = {
            high: this.highPriorityQueue,
            medium: this.mediumPriorityQueue,
            low: this.lowPriorityQueue
        };

        const queue = queues[priority];
        if (!queue) throw new Error(`Invalid priority: ${priority}`);

        // Check if queue is too long (back pressure)
        if (queue.length > 10000) {
            throw new Error('Server overloaded - request rejected');
        }

        queue.push(request);
    }

    async worker(id) {
        console.log(`Worker ${id} started`);
        let cycle = 0;

        while (this.running) {
            const request = this.getNextRequest(cycle);

            if (request) {
                try {
                    await this.processRequest(request);
                } catch (error) {
                    console.error(`Worker ${id} error:`, error);
                }
            } else {
                // No requests, sleep briefly
                await this.sleep(10);
            }

            cycle++;
        }

        console.log(`Worker ${id} stopped`);
    }

    getNextRequest(cycle) {
        // Weighted round-robin based on cycle number
        const totalWeight = this.weights.high +
                           this.weights.medium +
                           this.weights.low;

        const position = cycle % totalWeight;

        if (position < this.weights.high) {
            // Try high priority
            if (this.highPriorityQueue.length > 0) {
                return this.highPriorityQueue.shift();
            }
        } else if (position < this.weights.high + this.weights.medium) {
            // Try medium priority
            if (this.mediumPriorityQueue.length > 0) {
                return this.mediumPriorityQueue.shift();
            }
        } else {
            // Try low priority
            if (this.lowPriorityQueue.length > 0) {
                return this.lowPriorityQueue.shift();
            }
        }

        // Fallback: try any queue
        return this.highPriorityQueue.shift() ||
               this.mediumPriorityQueue.shift() ||
               this.lowPriorityQueue.shift();
    }

    async processRequest(request) {
        // Simulate processing
        const startTime = Date.now();
        await this.sleep(request.duration || 10);
        const duration = Date.now() - startTime;

        console.log(`Processed request: ${request.id} ` +
                   `(priority: ${request.priority}, ` +
                   `duration: ${duration}ms)`);
    }

    sleep(ms) {
        return new Promise(resolve => setTimeout(resolve, ms));
    }

    getStats() {
        return {
            high: this.highPriorityQueue.length,
            medium: this.mediumPriorityQueue.length,
            low: this.lowPriorityQueue.length,
            total: this.highPriorityQueue.length +
                  this.mediumPriorityQueue.length +
                  this.lowPriorityQueue.length
        };
    }
}

// Test
async function test() {
    const server = new FairRequestServer();
    server.start();

    // Add mixed priority requests
    for (let i = 0; i < 30; i++) {
        const priority = ['high', 'medium', 'low'][i % 3];
        await server.addRequest({
            id: i,
            priority: priority,
            duration: Math.random() * 50
        }, priority);
    }

    // Let it process
    await server.sleep(2000);

    console.log("Queue stats:", server.getStats());
    server.stop();
}

test();

With Rate Limiting

class RateLimitedServer extends FairRequestServer {
    constructor() {
        super();
        this.requestCounts = new Map();  // userId -> count
        this.resetInterval = 1000;  // Reset every second

        setInterval(() => this.resetCounts(), this.resetInterval);
    }

    async addRequest(request, priority = 'medium') {
        const userId = request.userId || 'anonymous';
        const limit = request.limit || 100;  // 100 requests per second

        const count = this.requestCounts.get(userId) || 0;

        if (count >= limit) {
            throw new Error(`Rate limit exceeded for user ${userId}`);
        }

        this.requestCounts.set(userId, count + 1);
        await super.addRequest(request, priority);
    }

    resetCounts() {
        this.requestCounts.clear();
    }
}

With Autoscaling

class AutoScalingServer extends FairRequestServer {
    constructor() {
        super();
        this.minWorkers = 2;
        this.maxWorkers = 16;
        this.scaleThreshold = 100;  // Queue size to trigger scaling

        setInterval(() => this.checkScale(), 5000);
    }

    checkScale() {
        const stats = this.getStats();
        const currentWorkers = this.numWorkers;

        if (stats.total > this.scaleThreshold &&
            currentWorkers < this.maxWorkers) {
            // Scale up
            this.scaleUp();
        } else if (stats.total < this.scaleThreshold / 4 &&
                   currentWorkers > this.minWorkers) {
            // Scale down
            this.scaleDown();
        }
    }

    scaleUp() {
        if (this.numWorkers >= this.maxWorkers) return;

        console.log(`Scaling up: ${this.numWorkers} -> ${this.numWorkers + 1}`);
        this.numWorkers++;
        this.workers.push(this.worker(this.numWorkers - 1));
    }

    scaleDown() {
        if (this.numWorkers <= this.minWorkers) return;

        console.log(`Scaling down: ${this.numWorkers} -> ${this.numWorkers - 1}`);
        this.numWorkers--;
        // Note: actual worker shutdown would be more complex
    }
}

Design Tradeoffs

Real-World Considerations

Monitoring:

• Queue lengths
• Processing latencies (p50, p99)
• Error rates
• Worker utilization

Circuit breakers: Fail fast when system overloaded

Timeouts: Don't let requests hang forever

Retries: With exponential backoff for transient failures

Idempotency: Safe to retry requests

Follow-Up Questions

Q: How to handle different request types (CPU vs I/O)?
A: Separate worker pools optimized for each

Q: What about distributed systems?
A: Use message queue (Kafka, RabbitMQ), load balancer

Q: How to guarantee ordering?
A: Partition by key, single worker per partition

Related Problems

• Implement a rate limiter - Fair resource allocation
• Write a program for producer-consumer problem - Scheduling problems
• Storing 1 million phone numbers - System design