Routing Architecture and Client Side Boundary Caching

Efficient routing in range partitioned systems depends on a small, ordered boundary map that defines which partition owns each key range, combined with client side caching to minimize metadata lookup overhead. The boundary map is typically an ordered list of tuples in the form [start_key, end_key, owner_node, epoch], where epoch or version numbers detect staleness. Clients fetch this map on initialization and cache it locally, routing requests by binary search to find the partition responsible for a given key. On successful requests, the cache remains valid. On "moved" or "split" responses, the client refreshes the affected portion of the map (not the entire map) and retries the request to the new owner. This design keeps routing overhead low even with thousands of partitions dynamically splitting and moving. Hierarchical metadata architectures, pioneered by Google Bigtable, avoid single point bottlenecks for large scale deployments. Bigtable uses a three level hierarchy: a Chubby cell stores the location of the root tablet, the root tablet stores locations of metadata tablets, and metadata tablets store locations of user tablets. All levels are themselves range partitioned tablets, preventing any single metadata partition from becoming a hotspot. Clients traverse this hierarchy once to populate their cache, then route directly to user tablets. When boundaries change due to splits or moves, clients receive redirects with hints to the new owner and update their cache incrementally. This approach has scaled to petabyte tables with hundreds of thousands of tablets while keeping metadata lookup off the critical path for most requests. Versioning and consistency are critical for correctness during concurrent splits and moves. Each partition boundary includes an epoch number that increments on ownership changes. Servers reject requests with stale epochs and return the current epoch plus the new owner's address. Clients use short Time To Live (TTL) values (typically 30 to 300 seconds) on cached boundaries and implement exponential backoff on repeated redirects to avoid amplifying load during rebalancing storms. The routing layer must handle edge cases like keys landing exactly on split boundaries (convention is [start, end) semantics where start is inclusive and end is exclusive), concurrent splits of the same range (resolved via epoch comparison), and metadata inconsistencies during network partitions (fail safe toward refreshing from authoritative source).

Google Bigtable clients cache tablet locations fetched from the metadata hierarchy. A client routing a request performs binary search on its cached boundary map (typically a few kilobytes for thousands of tablets), routes directly to the tablet server, and only contacts the metadata service when receiving a "tablet moved" response. This design keeps 99+ percent of requests off the metadata path.

Apache HBase clients maintain a two level cache: region locations and metadata (META) region location. On first access to a table, the client fetches META region location from ZooKeeper, queries META for user region locations, caches the results, and routes directly to region servers. Cache entries have no TTL but are invalidated on NotServingRegionException, triggering incremental refresh.

MongoDB mongos routers cache chunk distribution metadata from config servers. When routing a query, mongos performs binary search on cached chunk ranges to determine target shards. If a chunk has moved (detected via stale routing errors), mongos refreshes that specific namespace's metadata and retries. Cache refresh happens asynchronously to avoid blocking queries.