Kubernetes: TopologyAwareHints のソースコードリーディング

// AddHints adds or updates topology hints on EndpointSlices and returns updated
// lists of EndpointSlices to create and update.
func (t *TopologyCache) AddHints(si *SliceInfo) ([]*discovery.EndpointSlice, []*discovery.EndpointSlice) {
	// Ready なエンドポイントの合計を取得
	totalEndpoints := si.getTotalReadyEndpoints()
	// 各ゾーンへのエンドポイント割当数を取得
	allocations := t.getAllocations(totalEndpoints)

	// うまくエンドポイントを割り当てられない場合は終了
	if allocations == nil {
		klog.V(2).InfoS("Insufficient endpoints, removing hints from service", "serviceKey", si.ServiceKey)
		t.RemoveHints(si.ServiceKey, si.AddressType)
		return RemoveHintsFromSlices(si)
	}

	// 既存の EndpointSlice で変更のないものが現在ゾーン割当されているならそれをカウント
	allocatedHintsByZone := si.getAllocatedHintsByZone(allocations)

	// 新たに作成されたものと変更があるものを割り当て可能なエンドポイントに追加
	allocatableSlices := si.ToCreate
	for _, slice := range si.ToUpdate {
		allocatableSlices = append(allocatableSlices, slice)
	}

	// 下記のコメントのとおりで、まず全てのエンドポイントで同じゾーンのものを割り当てる
	// step 1: assign same-zone hints for all endpoints as a starting point.
	for _, slice := range allocatableSlices {
		for i, endpoint := range slice.Endpoints {
			if !endpointsliceutil.EndpointReady(endpoint) {
				endpoint.Hints = nil
				continue
			}
			if endpoint.Zone == nil || *endpoint.Zone == "" {
				klog.InfoS("Endpoint found without zone specified, removing hints from service", "serviceKey", si.ServiceKey)
				t.RemoveHints(si.ServiceKey, si.AddressType)
				return RemoveHintsFromSlices(si)
			}

			allocatedHintsByZone[*endpoint.Zone]++
			slice.Endpoints[i].Hints = &discovery.EndpointHints{ForZones: []discovery.ForZone{{Name: *endpoint.Zone}}}
		}
	}

	// 次に、どのゾーンでエンドポイントを提供、または必要なのかを特定する
	// step 2. Identify which zones need to donate slices and which need more.
	givingZones, receivingZones := getGivingAndReceivingZones(allocations, allocatedHintsByZone)

	// 上で得た情報を元にエンドポイントを再分配する
	// step 3. Redistribute endpoints based on data from step 2.
	redistributions := redistributeHints(allocatableSlices, givingZones, receivingZones)

	for zone, diff := range redistributions {
		allocatedHintsByZone[zone] += diff
	}

	t.SetHints(si.ServiceKey, si.AddressType, allocatedHintsByZone)
	return si.ToCreate, si.ToUpdate
}

// getGivingAndReceivingZones returns the number of endpoints each zone should
// give to other zones along with the number of endpoints each zone should
// receive from other zones. This is calculated with the provided allocations
// (desired state) and allocatedHintsByZone (current state).
func getGivingAndReceivingZones(allocations map[string]Allocation, allocatedHintsByZone map[string]int) (map[string]int, map[string]int) {
	// 1. Determine the precise number of additional endpoints each zone has
	//    (giving) or needs (receiving).
	givingZonesDesired := map[string]float64{}
	receivingZonesDesired := map[string]float64{}

    // 各ゾーン毎に望ましいエンドポイント数を超えて割り当てられている数と、下回っている数を算出
	for zone, allocation := range allocations {
		allocatedHints, _ := allocatedHintsByZone[zone]
		target := allocation.Desired
		if float64(allocatedHints) > target {
			givingZonesDesired[zone] = float64(allocatedHints) - target
		} else if float64(allocatedHints) < target {
			receivingZonesDesired[zone] = target - float64(allocatedHints)
		}
	}

	// 2. Convert the precise numbers needed into ints representing real
	//    endpoints given from one zone to another.
	givingZones := map[string]int{}
	receivingZones := map[string]int{}

	for {
		// 提供側でもっともエンドポイント数が多いゾーンを選択
		givingZone, numToGive := getMost(givingZonesDesired)
		// 受け取り側でもっともエンドポイントの数が足りないゾーンを選択
		receivingZone, numToReceive := getMost(receivingZonesDesired)

		// 下記のいずれかに一致する場合は終了
		// - 提供側またはが受け取り側が存在しない
		// - 提供側と受け取り側のどちらもが1より少ない数しか扱えない
		// - 提供側または受け取り側が 0.5 より少ない数しか扱えない
		// return early if any of the following are true:
		// - giving OR receiving zone are unspecified
		// - giving AND receiving zones have less than 1 endpoint left to give or receive
		// - giving OR receiving zones have less than 0.5 endpoints left to give or receive
		if givingZone == "" || receivingZone == "" || (numToGive < 1.0 && numToReceive < 1.0) || numToGive < 0.5 || numToReceive < 0.5 {
			break
		}

		givingZones[givingZone]++
		givingZonesDesired[givingZone]--
		receivingZones[receivingZone]++
		receivingZonesDesired[receivingZone]--
	}

	return givingZones, receivingZones
}

// redistributeHints redistributes hints based in the provided EndpointSlices.
// It allocates endpoints from the provided givingZones to the provided
// receivingZones. This returns a map that represents the changes in allocated
// endpoints by zone.
func redistributeHints(slices []*discovery.EndpointSlice, givingZones, receivingZones map[string]int) map[string]int {
	redistributions := map[string]int{}

	for _, slice := range slices {
		for i, endpoint := range slice.Endpoints {
			if !endpointsliceutil.EndpointReady(endpoint) {
				endpoint.Hints = nil
				continue
			}
			if len(givingZones) == 0 || len(receivingZones) == 0 {
				return redistributions
			}
			if endpoint.Zone == nil || *endpoint.Zone == "" {
				// This should always be caught earlier in AddHints()
				klog.Warningf("Endpoint found without zone specified")
				continue
			}

			// 提供側のヒントを削除して、足りないゾーンで上書きする処理を繰り返す
			// とくに順序はないので、ランダム
			givingZone := *endpoint.Zone
			numToGive, ok := givingZones[givingZone]
			if ok && numToGive > 0 {
				for receivingZone, numToReceive := range receivingZones {
					if numToReceive > 0 {
						slice.Endpoints[i].Hints = &discovery.EndpointHints{ForZones: []discovery.ForZone{{Name: receivingZone}}}
						if numToGive == 1 {
							delete(givingZones, givingZone)
						} else {
							givingZones[givingZone]--
						}
						if numToReceive == 1 {
							delete(receivingZones, receivingZone)
						} else {
							receivingZones[receivingZone]--
						}

						redistributions[receivingZone]++
						redistributions[givingZone]--

						break
					}
				}
			}
		}
	}
	return redistributions
}