/* There is an application with a microservice architecture. A microservice can be abstracted using the Backend interface. To access a single instance of a microservice, you can use the BackendImpl type, which is already implemented. For each microservice, there are several dozen running instances, each accessible via its own address addr. However, individual instances of the microservice are unreliable: they can crash, be unavailable, or overloaded. Therefore, you need to implement the Balancer type, which also implements the Backend interface and performs client-side load balancing among the microservice instances, choosing the **least loaded** instance each time. */ type Request interface{} type Response interface{} type Backend interface { Invoke(ctx context.Context, req Request) (Response, error) } var _ Backend = &BackendImpl{} // addr contains the ip:port of a specific instance func NewBackend(addr string) *BackendImpl type Balancer struct { //TODO } var _ Backend = &Balancer{} // addrs contain the addresses of all balancable instances func NewBalancer(addrs []string) *Balancer { //TODO }

To implement a client-side load balancer that selects the least loaded Backend instance, you can do the following:

1. In the Balancer structure, store a slice of BackendImpl and counters for the current load (e.g., number of active requests) for each instance.
2. When calling Invoke, select the Backend with the minimum load.
3. Before calling Invoke, increment the load counter; after completion, decrement it.

Example implementation in Go:

import (
    "context"
    "sync"
)

type Balancer struct {
    backends []*BackendImpl
    mu       sync.Mutex
    loads    []int // number of active requests for each backend
}

func NewBalancer(addrs []string) *Balancer {
    b := &Balancer{
        backends: make([]*BackendImpl, len(addrs)),
        loads:    make([]int, len(addrs)),
    }
    for i, addr := range addrs {
        b.backends[i] = NewBackend(addr)
    }
    return b
}

func (b *Balancer) Invoke(ctx context.Context, req Request) (Response, error) {
    b.mu.Lock()
    // Find index with minimum load
    minIdx := 0
    minLoad := b.loads[0]
    for i, load := range b.loads {
        if load < minLoad {
            minLoad = load
            minIdx = i
        }
    }
    b.loads[minIdx]++
    b.mu.Unlock()

    // Call backend
    resp, err := b.backends[minIdx].Invoke(ctx, req)

    b.mu.Lock()
    b.loads[minIdx]--
    b.mu.Unlock()

    return resp, err
}

This approach ensures the selection of the least loaded instance at the moment of invocation, considering the current active load. For more precise accounting, atomic operations or more complex load metrics can be used.