Goで「決定的なサブセット選択」を実装してみた。

SRE本によれば、Googleはデータセンター内のロードバランシングに「決定的なサブセット選択」アルゴリズムを採用しているとのこと。

疑似コードが載っていたので、これをGoで実装してみました。

package main

import (
	"fmt"
	"math/rand"
	"reflect"
)

type Backend struct {
	ID int
}

type Client struct {
	ID int
}

func Subset(backends []Backend, clientID int, subsetSize int) []Backend {
	subsetCount := len(backends) / subsetSize

	round := clientID / subsetCount
	rand.Seed(int64(round))
	shuffled := Shuffle(backends, round)

	subsetID := clientID % subsetCount
	start := subsetID * subsetSize

	return shuffled[start : start+subsetSize]
}

func Shuffle(backends []Backend, round int) []Backend {
	shuffled := make([]Backend, len(backends))
	copy(shuffled, backends)

	for i := 0; i < len(shuffled); i++ {
		j := rand.Intn(i + 1)
		shuffled[i], shuffled[j] = shuffled[j], shuffled[i]
	}

	return shuffled
}

func main() {
	backendSize := 300
	clientSize := 300
	subsetSize := 10

	backends := []Backend{}
	for i := 0; i < backendSize; i++ {
		backends = append(backends, Backend{ID: i})
	}

	clients := []Client{}
	for i := 0; i < clientSize; i++ {
		clients = append(clients, Client{ID: i})
	}

	selected := [][]Backend{}
	for _, c := range clients {
		s := Subset(backends, c.ID, subsetSize)
		selected = append(selected, s)
	}

	// display
	for i, b := range selected {
		fmt.Printf("ClientID:%d -> %v\n", i, b)
	}

	// check dup
	for i := 0; i < len(selected); i++ {
		for j := 0; j < len(selected); j++ {
			if i == j {
				continue
			}

			if reflect.DeepEqual(selected[i], selected[j]) {
				fmt.Println("error")
				fmt.Println(selected[i])
				fmt.Println(selected[j])
			}
		}
	}

	// count by backendID
	flat := []Backend{}
	for _, b := range selected {
		flat = append(flat, b...)
	}

	stats := make(map[int]int)
	for _, backend := range flat {
		stats[backend.ID] = stats[backend.ID] + 1
	}

	for i, count := range stats {
		if count == subsetSize {
			continue
		}
		fmt.Println(stats[i])
	}
}

300台のクライアントが、300個のバックエンドサーバから10個を選択する場合、このようになります

一見ランダムに選択されているように見えますが、各バックエンドは正確に10回のみ選択されていることがわかります。
ランダムにバックエンドサーバを選択するアルゴリズムでは、このように均一にならず偏りが生じます。

アルゴリズムの詳細はSRE本のChapter20を参照してください。

参考

1. Site Reliability Engineering Chapter20 Load Balancing in the Datacenter