/ * There is an application with a microservices 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 a type Balancer, which also implements the Backend interface and performs client-side load balancing among the microservice instances, choosing the **least loaded** instance each time. */

To implement a Balancer type that implements the Backend interface and selects the least loaded microservice instance, you can use the following approach:

1. Store a list of BackendImpl with their addresses and current load.
2. On each call to the Backend method, select the instance with the minimum load.
3. Update the load information after each request (for example, increment the active request counter and decrement after completion).

Example in Go:

package main

import (
    "errors"
    "sync"
)

// Backend interface for microservices
type Backend interface {
    DoRequest() error
}

// BackendImpl - specific instance of a microservice
// In reality, this would implement communication at the address addr
// For example, we just simulate

type BackendImpl struct {
    addr string
}

func (b *BackendImpl) DoRequest() error {
    // Implementation of request to microservice
    return nil
}

// Balancer implements Backend and balances load

type Balancer struct {
    backends []*backendWithLoad
    mu       sync.Mutex
}

type backendWithLoad struct {
    backend Backend
    load    int // number of active requests
}

func NewBalancer(addrs []string) *Balancer {
    b := &Balancer{}
    for _, addr := range addrs {
        b.backends = append(b.backends, &backendWithLoad{
            backend: &BackendImpl{addr: addr},
            load:    0,
        })
    }
    return b
}

func (b *Balancer) DoRequest() error {
    b.mu.Lock()
    // Find backend with minimum load
    var selected *backendWithLoad
    minLoad := int(^uint(0) >> 1) // max int
    for _, be := range b.backends {
        if be.load < minLoad {
            minLoad = be.load
            selected = be
        }
    }
    if selected == nil {
        b.mu.Unlock()
        return errors.New("no backends available")
    }
    selected.load++
    b.mu.Unlock()

    // Perform request
    err := selected.backend.DoRequest()

    // After completion, decrease load
    b.mu.Lock()
    selected.load--
    b.mu.Unlock()

    return err
}

This approach allows the client to balance load among instances by choosing the least loaded at the moment of the request. For more accurate load accounting, you can use metrics from the services themselves or consider response time.