Critical limitations of the Least Outstanding Request load balancing policy in service meshes for large-scale microservice applications

Service meshes are becoming pivotal software frameworks for managing communication among microservices in distributed applications. Each microservice in a service mesh is paired with an L7 sidecar proxy, which intercepts incoming and outgoing requests to provide enhanced observability, traffic management, and security. These sidecar proxies use application-level load balancing policies to route outgoing requests to available replicas of destination microservices. A widely adopted policy is the Least Outstanding Request (LOR), which directs requests to the replica with the fewest outstanding requests. While LOR effectively reduces latency in applications with a small number of replicas, our comprehensive investigation- combining analytical, simulation, and experimental methods- uncovers a novel and critical issue for large-scale microservice applications: the performance of LOR significantly degrades as the number of microservice replicas increases, eventually converging to the performance of a random load balancing policy. To recover LOR performance at scale, we propose an opensource solution named Proxy-Service, tailored for microservice applications where load balancing incurs significantly lower resource demands than microservice execution. The core idea is to consolidate load balancing decisions per microservice into one or a few reverse proxies, transparently injected into the application.