Optimizing API Rate Limiters: Reducing Latency from 200ms to 3ms with B-Tree Indexing

The Quest Begins (The “Why”)

A microservice rate-limiter utilizing a Postgres backend experienced severe latency spikes under a modest load of 500 RPS. The system suffered from sequential scans on a table containing millions of rows, driving CPU usage to 92%.

Why This Matters

In theory, simple counter logic for rate limiting is efficient, but technical reality reveals that without proper indexing, database lookups scale linearly O(n) rather than logarithmically O(log n). This failure scale transforms a lightweight check into a system bottleneck, where latency increases by two orders of magnitude as the dataset grows into the millions.

Key Insights

• Sequential scans on large tables cause massive CPU spikes; adding a B-tree index reduced DB CPU usage from 92% to 18% (Timevolt, 2026).
• B-tree indexes maintain sorted keys for efficient range queries and O(log n) updates, making them more versatile than hash indexes in Postgres.
• Postgres INET or CIDR column types are semantically correct for IP storage and provided an additional ~15% performance boost over TEXT.

Working Examples

SQL migration to add a B-tree index to the IP column.

CREATE INDEX idx_rate_limits_ip ON rate_limits(ip);

Go implementation of the rate limiter check using SELECT FOR UPDATE for race condition prevention.

func allow(ip string) (bool, error) {
	var count int
	err := db.QueryRow(
		`SELECT count FROM rate_limits WHERE ip = $1 FOR UPDATE`, ip).Scan(&count)
	if err != nil {
		return false, err
	}
	if count >= limit {
		return false, nil // 429
	}
	_, err = db.Exec(
		`UPDATE rate_limits SET count = count + 1 WHERE ip = $1`, ip)
	return err == nil, nil
}

Practical Applications

• • Use case: High-throughput API throttling using indexed lookups allows horizontal scaling of API nodes without database saturation.
• • Pitfall: Over-indexing every column (e.g., user_agent or path) increases write overhead and degrades INSERT/UPDATE latency.

References:

• https://dev.to/timevolt/indexing-the-force-awakens-in-my-rate-limiter-quest-1dc8