Disclosed are systems, methods, and computer-readable storage media for scaling service discovery in a micro-service environment. A controller can instantiate, on a host computing device, a first container instance providing a first micro-service of an application. The host computing device can include a service discovery agent. The controller can identify a set of micro-services that are dependencies of the first micro-service, and update the service discovery agent with routing data for container instances providing the set of micro-services that are dependencies of the first micro-service. The service discovery agent can use the routing data to route requests from the first container instance to container instances providing the set of micro-services that are dependencies of the first micro-service.