Cross-shard queries in HLD - Scalability & System Analysis

Scalability Analysis - Cross-shard queries

Growth Table: Cross-shard Queries Scaling

Users / Data Size	100 Users	10K Users	1M Users	100M Users
Number of shards	1-2 shards	10-20 shards	100-200 shards	1000+ shards
Cross-shard query frequency	Rare, simple queries	Occasional, moderate complexity	Frequent, complex queries	Very frequent, highly complex queries
Latency impact	Negligible	Noticeable delays	Significant latency increase	High latency, possible timeouts
Data consistency challenges	Minimal	Moderate	High	Very high, complex coordination
Network overhead	Low	Moderate	High	Very high
System complexity	Low	Moderate	High	Very high

First Bottleneck: Query Coordination and Latency

As the number of shards grows, the first bottleneck is the query coordinator that must gather and merge data from multiple shards. This causes increased latency and network overhead. The coordinator's CPU and memory can become overwhelmed handling many parallel cross-shard queries. Also, data consistency and transaction management across shards become challenging, slowing down responses.

Scaling Solutions for Cross-shard Queries

• Query Routing: Design queries to target as few shards as possible by improving shard keys and data locality.
• Denormalization & Aggregation: Pre-aggregate or duplicate data to reduce cross-shard joins.
• Asynchronous Processing: Use background jobs or eventual consistency to avoid blocking user queries.
• Distributed Query Engines: Use specialized systems that parallelize and optimize cross-shard queries efficiently.
• Caching: Cache frequent cross-shard query results to reduce load.
• Horizontal Scaling: Add more query coordinators and shard servers to distribute load.
• Sharding Strategy: Revisit shard keys to minimize cross-shard queries by grouping related data.

Back-of-Envelope Cost Analysis

Assuming 1M users with 100 shards:

• Average queries per second (QPS): 10,000
• Cross-shard queries: 20% -> 2,000 QPS involving multiple shards
• Each cross-shard query touches ~5 shards -> 10,000 shard queries/sec
• Network bandwidth: 10,000 shard queries x 10 KB data = ~100 MB/s
• Coordinator CPU: Must handle merging 2,000 complex queries/sec, needs multiple servers
• Storage: Each shard stores ~10,000 users' data, scaling storage horizontally

Interview Tip: Structuring Scalability Discussion

Start by explaining how sharding improves write/read scale but introduces cross-shard query challenges. Identify the coordinator as the bottleneck. Discuss trade-offs between latency, consistency, and complexity. Propose solutions like better shard keys, caching, and distributed query engines. Use numbers to justify your approach and show understanding of system limits.

Self-Check Question

Your database handles 1000 QPS. Traffic grows 10x with many cross-shard queries. What do you do first?

Answer: The first step is to reduce cross-shard query load by improving shard keys to localize queries or add caching to avoid repeated cross-shard fetches. Then, scale query coordinators horizontally to handle increased query merging load.

Key Result

Cross-shard queries become a bottleneck as shards increase, mainly due to query coordination overhead and latency. Solutions focus on minimizing cross-shard queries, caching, and horizontally scaling coordinators.