Systems and methods provide for scaling service discovery in a micro-service environment. A controller can inject a service discovery agent onto a host. At least one of the controller or the agent can identify a first set of micro-service containers that are dependencies of the first micro-service container and a second set of micro-service containers that are dependencies of the second micro-service container. At least one of the controller or the agent can update routing data for the first set of micro-service containers and the second set of micro-service containers. At least one of the controller or the agent can determine the second micro-service container has terminated on the host computing device. At least one of the controller or the agent can update the agent to remove the routing data for the second set of micro-service containers.