System Design: High-throughput Client-side Ranged-read File Cache

You are asked to design and specify a client-side cache that accelerates ranged reads against a remote storage service.

Context and Assumptions

• The remote service supports HTTP Range-like reads: fetch(filename, offset, length).
• There is also an API to download an entire file by filename and known size.
• Workloads consist of many concurrent ranged reads, often overlapping or adjacent.
• The cache persists on local disk across process restarts.

Requirements

1. Concurrency and coalescing
   • Efficiently handle concurrent requests for overlapping/adjacent ranges.
   • Deduplicate overlapping in-flight downloads so only one fetch per chunk occurs.
   • Provide thread-safe access and correctness under concurrency.
2. Chunking, request strategy, and prefetch
   • Choose chunk size and justify trade-offs.
   • Coalesce requests to reduce remote calls and over-fetch sensibly.
   • Implement prefetch/read-ahead strategies for sequential access.
3. Backpressure and rate limiting
   • Limit remote QPS/throughput and disk I/O concurrency.
   • Disable prefetch under load; bound queues.
4. Cache management
   • Cache indexing and lookup.
   • Eviction policy (e.g., LRU) with byte budget.
   • Persistence across restarts.
   • Validation and invalidation if the remote file changes.
5. Reliability
   • Handle partial failures, retries, and timeouts.
   • Resume or refetch partial chunks.
6. API semantics
   • Define read(filename, offset, length) (sync or async), and streaming semantics if applicable.
   • Define write policy (e.g., read-through only, or write-through with invalidation).
7. Deliverables
   • Describe key data structures and on-disk layout.
   • Provide pseudocode for coordinating fetch, cache lookup, coalescing, and concurrency control.
   • Analyze scalability, correctness under concurrency, and time/space complexity.