Katkat
Back

Scaling a Collision-Free Rover Fleet to a Million Robots

ShopifySoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSystem Design

Last updated

This question tests the ability to design a distributed system that manages real-time state consistency across a massive, sharded spatial grid while handling concurrency and robot movement.

Scenario

You are designing a centralized control system for a warehouse fleet of 1 million autonomous rovers operating on a 2D grid of size 100,000 x 100,000 units. Each rover occupies exactly one unit at any given time. The system must process movement requests (e.g., "Move North") while ensuring no two rovers ever occupy the same coordinate.

Requirements

  1. Functional:
    • Process movement requests while maintaining the "no-collision" invariant.
    • Handle high throughput: the fleet generates 100,000 move requests per second.
    • Support a global query for any rover's current coordinates.
  2. Non-Functional:
    • High availability: The system should not go down if one node fails.
    • Latency: Movement requests must be processed in under 50ms.

Task

Design the architecture for this system. Your response should include:

  • Data Partitioning: How do you divide the 100,000 x 100,000 grid across a cluster of nodes?
  • Concurrency Control: How do you handle cases where two rovers attempt to move into the same adjacent cell simultaneously?
  • Failure Handling: What happens if a node managing a specific grid segment crashes?
  • API Design: Define the primary interface for movement requests and state lookups.

Hints

Hint 1

Consider spatial partitioning using techniques like quadtrees or grid-based sharding to map coordinate ranges to specific physical servers.

Hint 2

Think about how to handle 'boundary' conditions where a rover moves from a cell managed by Node A into a cell managed by Node B.

Hint 3

Evaluate whether a distributed lock manager or a leader-based partition architecture is more suitable for maintaining the collision-free invariant.

Follow-up questions

  • How would you handle a 'hotspot' scenario where 10,000 robots all cluster into a small area of the warehouse?
  • If the network latency between grid shards increases, how does that impact the safety of your movement validation?
  • How would you implement a 'look-ahead' feature that allows rovers to reserve paths rather than single-step movements?