Described are aspects of a sharded monitoring system that collects metrics data from a plurality of targets within a monitored system. The monitoring system includes multiple monitoring-server instances each collecting metrics data from a respective subset of the targets, as well as a federation server that collects aggregated metrics data from the other monitoring-server instances. Mappings between monitoring targets and monitoring-server instances collecting their metrics data may be stored in a temporal routing map, e.g., on the federation server, which may build the map based on time-series routing metrics received from the other monitoring-server instances. The routing map may be used to direct queries for metrics data from a client to the appropriate monitoring-server instance.