ロードバランサーを作ってアルゴリズムを学ぼう -  ラウンドロビン

## 概要 

Go でアプリケーション ロードバランサーを作成しながらロードバランシングの基本的なアルゴリズムを学びます。

## 目的

- Layer7 ロードバランサー (LB) の作成を通して
  - ロードバランシングに使用されている基本的なアルゴリズムを学ぶ
  - スケーラブルな LB で使用されているアルゴリズム・技術を学ぶ
- (筆者が勉強中である) Go を使って慣れる。
    - 可能な限り 3rd party ライブラリを使用せずに！

※ 筆者は Go を勉強中です。業務で使用しているわけではないため、Go の流儀と異なる書き方などをしている箇所があるかもしれません。その場合アドバイスいただけると大変ありがたいです！
※ 本トピックに関しては長くなりそうなので、何本かに分けて投稿したいと思います。

## ステップ 1: シンプルな LB　（ラウンドロビン方式）
今回はシンプルなラウンドロビン方式でロードバランシングを行う Layer7 LB を作成します。
とその前に、確認しながら実装をすすめるためにもバックエンド (アップストリーム) サーバーを用意しておくと便利そうです。
ということで予め簡単なバックエンドサーバーを Docker イメージで用意しました ([link](https://hub.docker.com/r/hirotake1111/go-tiny-web))。これを docker-compose を使ってよしなに複製して実装をすすめます。
(link のイメージは現時点では M1 Mac のみで利用可能です。ご了承ください 😓)

### どのようにリバース プロキシするか

まず LB を作るにあたり、クライアントからのリクエストをどのようにバックエンドへリバース プロキシするか、という疑問が頭に浮かびます。
当初はHTTP ヘッダーとボディの中身をコピーしてバックエンドへリクエストする、とか考えていたのですが、実は Go の標準ライブラリの中に [httputil.NewSingleHostReverseProxy](https://pkg.go.dev/net/http/httputil#NewSingleHostReverseProxy) というものがあり、これを使用することで簡単にリバースプロキシが可能です。

```go
import "net_http_httputil"
// ...
rp := httputil.NewSingleHostReverseProxy(url)
http.HandleFunc("/", func(w http.ResponseWriter, r *http.Request) {
    rp.ServeHTTP(w, r)
})
```

標準ライブラリのみでも何でもできてしまうのが Go の強みですね！

### ラウンドロビン方式について

ロードバランシングにおいては、ラウンドロビンはリクエストを各バックエンドへ順番に振り分けを行うとてもシンプルな方式です。絵で書くとこんな感じです。

<img width="500" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2664705/c6915adf-7a2d-78b3-8506-f8f5bec419a2.png" >

### いざ実装

実際のコードは [こちら](https://github.com/hirotake111/TinyBandaid/tree/main/1_simple_round_robin) をご参照ください。

今回は以下のように `Backend` という struct の中に `ReverseProxy` というフィールドを定義しました。
(URL は後々必要になることがありそうなのでフィールドに含めています。)

```go:models.go
package models

// ...

type Backend struct {
	Url          *url.URL               // Backend's URL
	ReverseProxy *httputil.ReverseProxy // reverse proxy instance
}

// Returns a pointer to a new backend server
func NewBackend(serverUrl string) *Backend {
	url, err := url.Parse(serverUrl)
	if err != nil {
		panic(fmt.Sprintf("Cannot instantiate a server with URL %s", serverUrl))
	}
	return &Backend{Url: url, ReverseProxy: httputil.NewSingleHostReverseProxy(url)}
}
```

あとあと実装が大きくなりそうなので、別パッケージ上に `Pool` という struct を定義し、この中で `Backend` を管理する形にします。


```go:pool.go
package pool

// ...

type HttpHandler func(w http.ResponseWriter, r *http.Request)

type Pool struct {
	backends     []*models.Backend // array of backend
	currentIndex uint64            // current index of serving backend
}

// Returns a pointer to next available backend
func (p *Pool) nextBackend() *models.Backend {
    // Round Robin
	p.currentIndex = (p.currentIndex + 1) % uint64(len(p.backends))
	return p.backends[p.currentIndex]
}

// Returns a pointer for a new server pool
func New(serverUrls []string) *Pool {
	backends := make([]*models.Backend, len(serverUrls))
	for i, serverUrl := range serverUrls {
		backends[i] = models.NewBackend(serverUrl)
		log.Printf("server #%d: %s registered.\n", i, serverUrl)
	}
	return &Pool{
		backends:     backends,
		currentIndex: uint64(len(backends) - 1),
	}
}

// Returns an HTTP handler for load balancing
func (p *Pool) CreateHandler() HttpHandler {
	return func(w http.ResponseWriter, r *http.Request) {
		b := p.nextBackend()
		b.ReverseProxy.ServeHTTP(w, r)
	}
}
```

肝心のラウンドロビンは `nextBackend()` で実装しています。
(順番にバックエンドのインデックスを取得し、最後まで到達したら 0 に戻ります。)

```go
func (p *Pool) nextBackend() *models.Backend {
    // Round Robin
	p.currentIndex = (p.currentIndex + 1) % uint64(len(p.backends))
	return p.backends[p.currentIndex]
}
```

バックエンドサーバーのコンフィグは JSON 形式のコンフィグ ファイルを用意し、ロードする形にします。
(ファイル名は `config.json` の決め打ち)

```json:config.json
{
    "server_urls":["http://web1", "http://web2", "http://web3", "http://web4"]
}
```

```go:config.go
type Config struct {
	ServerUrls []string `json:"server_urls"`
}

func LoadConfigFile(fileName string) (*Config, error) {
	var config *Config
	data, err := os.Open(fileName)
	if err != nil {
		return config, err
	}
	defer data.Close()
	byteArray, err := io.ReadAll(data)
	if err != nil {
		return config, err
	}
	json.Unmarshal(byteArray, &config)
	return config, nil
}
```

これらを `main()` 内でつなぎ合わせていきます。

```go:main.go
func main() {
	c, err := config.LoadConfigFile(CONFIG_FILE_NAME)
	if err != nil {
		panic(err)
	}

	p := pool.New(c.ServerUrls)
	mux := http.NewServeMux()
	mux.HandleFunc("/", p.CreateHandler())
	server := http.Server{Addr: ":3000", Handler: mux}

	fmt.Println("Load balancer is up and running - http://localhost:3000")
	if err := server.ListenAndServe(); err != nil {
		log.Fatal(err)
	}
}
```

### 動作確認

`docker-compose` で LB とバックエンドのコンテナを起動し、別ターミナルから `curl http://localhost:3000` を叩くと、期待通りの動作をしていることが確認できます。 

![スクリーンショット 2023-03-08 16.16.20.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2664705/97201c68-ce35-4454-d272-36c918f0b51e.png)

### 終わりに

お気づきの方もいるかもしれませんが、この実装では バックエンドの一部が停止状態などの応答しない状況では、そのバックエンドへロードバランシングした際にクライアントへ HTTP502 をレスポンスします。
このような状況では応答しないサーバーへのロードバランシングを行わないようにしたいので、次はバックエンドへのヘルスチェック機能を追加したいと思います。