Sharding hard
For spatial location-based sharding (like Uber or DoorDash), why is a 'Geohash' preferred over sharding by simple Latitude and Longitude coordinate pairs?
- A It uses significantly fewer characters, reducing the storage overhead on the physical disk.
- B It 'linearizes' two-dimensional coordinates into a one-dimensional string where common prefixes indicate physical proximity. This allows standard B-Tree 'Range Scans' to find nearby drivers efficiently.
- C It is more mathematically accurate for areas near the Earth's poles where standard latitude calculations fail.
- D It provides built-in encryption that anonymizes the user's exact location to comply with privacy regulations.
Answer: B. It 'linearizes' two-dimensional coordinates into a one-dimensional string where common prefixes indicate physical proximity. This allows standard B-Tree 'Range Scans' to find nearby drivers efficiently.
Searching 'all points within 5 miles' is a complex geometric problem. A 'Geohash' converts a location into a string like `dp3b`. Crucially, points near `dp3b1` are almost always near `dp3b2`. For a database like Postgres, this is a miracle: finding all nearby drivers becomes a simple query for 'all strings starting with `dp3b`'. This allows us to use standard, high-speed 1D sorting indexes to solve a 2D spatial search problem, making it orders of magnitude faster than calculating Euclidean distances across millions of rows.
One system design question a day, with spaced repetition so the ones you miss come back.
Get the appRelated questions
- In an E-Commerce platform, why might you choose to shard the `Orders` table by `user_id` rather than the more obvious `order_id`?
- In the context of database scaling, what is the fundamental difference between 'Vertical Partitioning' and 'Horizontal Partitioning' (Sharding)?
- If Shard A fails in a large cluster, and its incoming traffic is automatically re-routed to Shard B, what is the risk of a 'Cascading Failure'?
- In a standard 'Modulo Sharding' setup (`key % N`), what is the primary consequence of adding a new server to the cluster (increasing N from 10 to 11)?
- From an engineering perspective, when should you choose 'Vertical Scaling' (a bigger server) over 'Horizontal Scaling' (Sharding)?
- Which sharding strategy is mathematically optimized for efficient 'Range Scans' (e.g., retrieving all records created between January and March)?