[インデックス 19200] ファイルの概要

このコミットは、Go言語のnetパッケージにおけるDNS SRVレコードの重み付けシャッフルロジックの確率計算のバグを修正し、その動作を検証するための新しいテストを追加しています。

具体的には、以下のファイルが変更されました。

src/pkg/net/dnsclient.go: DNS SRVレコードの重み付けシャッフルを行うshuffleByWeight関数内の確率計算ロジックが修正されました。
src/pkg/net/dnsclient_test.go: shuffleByWeight関数の重み付け分布が正しく機能していることを検証するための新しいテストファイルが追加されました。

コミット

commit c45392bae0332e1407c4468ee35a5176651b03fa
Author: Brad Fitzpatrick <bradfitz@golang.org>
Date:   Thu Apr 17 13:28:40 2014 -0700

    net: fix probabilities in DNS SRV shuffleByWeight
    
    Patch from msolo. Just moving it to a CL.
    The test fails before and passes with the fix.
    
    Fixes #7098
    
    LGTM=msolo, rsc
    R=rsc, iant, msolo
    CC=golang-codereviews
    https://golang.org/cl/88900044

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/c45392bae0332e1407c4468ee35a5176651b03fa

元コミット内容

net: fix probabilities in DNS SRV shuffleByWeight

Patch from msolo. Just moving it to a CL.
The test fails before and passes with the fix.

Fixes #7098

LGTM=msolo, rsc
R=rsc, iant, msolo
CC=golang-codereviews
https://golang.org/cl/88900044

変更の背景

このコミットは、Go言語のnetパッケージ内でDNS SRVレコードを処理する際に使用されるshuffleByWeight関数における、確率計算の不正確さを修正するために行われました。DNS SRVレコードは、サービスディスカバリやロードバランシングのシナリオで広く利用されますが、その際に各ターゲットの「重み」に基づいて接続先を適切に分散することが重要です。

元の実装では、shuffleByWeight関数が、指定された重みに従ってエントリをシャッフルする際に、期待される確率分布を正確に再現できていませんでした。これにより、特定のサービスエンドポイントが過剰に選択されたり、逆に選択されにくくなったりする可能性があり、結果としてロードバランシングの効率が低下したり、サービス可用性に影響を与えたりする可能性がありました。

コミットメッセージにあるFixes #7098は、この問題がGoのイシュートラッカーで報告されていたことを示しています。ただし、現在の公開されているGoイシュートラッカーでは、この特定のイシュー番号（#7098）に直接対応する公開された報告は見つかりませんでした。これは、イシューが内部的なものであったか、あるいはイシュートラッカーのシステム変更により参照が困難になっている可能性が考えられます。

この問題は、msolo氏によってパッチが提供され、それをBrad Fitzpatrick氏がGoの変更リスト（CL）として取り込んだものです。修正が正しく機能することを確認するため、修正前には失敗し、修正後には成功するテストが追加されました。

前提知識の解説

DNS SRVレコード

DNS SRV (Service Location) レコードは、特定のサービスを提供するホスト名とポート番号を定義するために使用されるDNSレコードの一種です。通常のA/AAAAレコードがホスト名とIPアドレスをマッピングするのに対し、SRVレコードはサービスの種類（例: _sip._tcp）、プロトコル（TCP/UDP）、ポート番号、ホスト名、そして優先度 (Priority) と 重み (Weight) を指定します。

優先度 (Priority): 複数のSRVレコードが存在する場合、最も低い優先度のレコードが最初に試行されます。同じ優先度のレコードが複数ある場合、それらのレコードは重みに基づいて選択されます。
重み (Weight): 同じ優先度を持つ複数のSRVレコードがある場合、重みは各ターゲットが選択される相対的な確率を示します。重みが大きいターゲットほど、より頻繁に選択されるべきです。これは、ロードバランシングのメカニズムとして機能します。

重み付けシャッフル (Weighted Shuffle)

重み付けシャッフルは、複数の要素の中から、それぞれの要素に割り当てられた「重み」に比例した確率で要素を選択するアルゴリズムです。例えば、重みが60、30、10の3つの要素がある場合、合計重みは100です。この場合、最初の要素は60%の確率で、2番目の要素は30%の確率で、3番目の要素は10%の確率で選択されるべきです。

このアルゴリズムは、サービスディスカバリにおいて、複数のバックエンドサーバーがある場合に、それぞれのサーバーの処理能力や負荷に応じてリクエストを分散させるために利用されます。

`rand.Intn(n)`

Go言語の標準ライブラリmath/randパッケージに含まれるIntn(n int)関数は、[0, n)の範囲の非負の擬似乱数を生成します。つまり、0からn-1までの整数が均等な確率で生成されます。この関数の引数nは、生成される乱数の上限（排他的）を指定します。

技術的詳細

このコミットで修正されたshuffleByWeight関数は、DNS SRVレコードのリストを、その重みに基づいてランダムに並べ替えることを目的としています。この関数は、リストから要素を一つずつ選択し、それをリストの先頭に移動させることでシャッフルを行います。

元の実装におけるバグは、乱数の生成範囲と、その乱数と累積重みを比較する条件にありました。

`shuffleByWeight`関数のアルゴリズム（修正前と修正後）

合計重みの計算: 現在処理対象となっているSRVレコードのリストの合計重みsumを計算します。
乱数の生成:
- 修正前: n := rand.Intn(sum + 1)
  - これは[0, sum]の範囲の乱数を生成します。つまり、sumという値も乱数として生成される可能性があります。
- 修正後: n := rand.Intn(sum)
  - これは[0, sum-1]の範囲の乱数を生成します。sumという値は乱数として生成されません。
要素の選択:
- リストの各SRVレコードを順番に見ていき、それぞれのレコードの重みを累積していき、sとします。
- 修正前: if s >= n
  - 累積重みsが生成された乱数n以上になった場合、そのSRVレコードを選択します。
- 修正後: if s > n
  - 累積重みsが生成された乱数nより大きくなった場合、そのSRVレコードを選択します。
リストの更新: 選択されたSRVレコードはリストの先頭に移動され、sumからそのレコードの重みが引かれます。このプロセスは、リストに1つ以上の要素が残っている限り繰り返されます。

バグの原因と修正の論理

1. `rand.Intn(sum + 1)` の問題

rand.Intn(n)は[0, n-1]の範囲の乱数を生成するため、rand.Intn(sum + 1)は[0, sum]の範囲の乱数を生成します。このとき、もし乱数nがsumとして生成された場合、累積重みsは最大でもsumにしかならないため、s >= nという条件はs >= sumとなります。この場合、最後の要素の重みが0でない限り、最後の要素が選択される確率が歪むか、あるいは全く選択されない可能性がありました。例えば、合計重みが100の場合、rand.Intn(101)は0から100までの乱数を生成します。もし乱数が100だった場合、累積重みsが100になるまで要素は選択されません。しかし、sが100になった時点で、その要素が選択されるべきですが、このロジックでは最後の要素が正しく選択されない可能性がありました。

修正: n := rand.Intn(sum) に変更することで、乱数の範囲が[0, sum-1]に限定されます。これにより、乱数nがsumになることはなくなり、累積重みsがsumに達する前に必ず要素が選択されるようになります。これは、重み付けされたランダム選択アルゴリズムの標準的な実装に合致します。

2. `if s >= n` の問題

この比較条件は、特に乱数nが0の場合に問題を引き起こしました。もしnが0として生成された場合、s >= 0という条件は、最初の要素の重みが0でない限り、常に最初の要素が選択されることを意味します。これは、重み付けされたランダム選択において、最初の要素が不当に高い確率で選択される原因となります。

修正: if s > n に変更することで、累積重みsが乱数nを「厳密に超えた」場合にのみ要素が選択されるようになります。これにより、n=0の場合でも、最初の要素の重みが0でない限り、s > 0という条件が満たされるまで、他の要素も考慮されるようになります。これは、各要素がその重みに比例した確率で選択されることを保証し、より均等な分布を実現します。

これらの2つの変更により、shuffleByWeight関数は、DNS SRVレコードの重みに基づいて、より正確で公平な確率分布でシャッフルを実行できるようになりました。

コアとなるコードの変更箇所

src/pkg/net/dnsclient.goにおける変更点:

--- a/src/pkg/net/dnsclient.go
+++ b/src/pkg/net/dnsclient.go
@@ -191,10 +191,10 @@ func (addrs byPriorityWeight) shuffleByWeight() {
 	}
 	for sum > 0 && len(addrs) > 1 {
 		s := 0
-		n := rand.Intn(sum + 1)
+		n := rand.Intn(sum)
 		for i := range addrs {
 			s += int(addrs[i].Weight)
-			if s >= n {
+			if s > n {
 				if i > 0 {
 					t := addrs[i]
 					copy(addrs[1:i+1], addrs[0:i])

また、このコミットでは、src/pkg/net/dnsclient_test.goという新しいテストファイルが追加されました。このテストファイルには、checkDistribution、testUniformity、testWeightingといった関数が含まれており、shuffleByWeight関数が重み付けされた分布を正しく生成しているかを検証します。これにより、将来的な回帰を防ぎ、関数の正確性を保証します。

コアとなるコードの解説

`n := rand.Intn(sum)`

この変更は、乱数nの生成範囲を[0, sum-1]に限定します。これにより、乱数nがsumという値を取る可能性がなくなります。これは、重み付けされたランダム選択アルゴリズムにおいて、累積重みsがsumに達する前に必ず要素が選択されることを保証するために不可欠です。もしsumが乱数として生成されると、最後の要素が選択される確率が不正確になるか、あるいは全く選択されないという問題が発生する可能性がありました。この修正により、各要素がその重みに厳密に比例した確率で選択されるようになります。

`if s > n`

この比較条件の変更は、累積重みsが乱数nを「厳密に超えた」場合にのみ要素を選択するようにします。特に重要なのは、乱数nが0として生成された場合の挙動です。元のs >= nという条件では、n=0の場合、最初の要素の重みが0でない限り、s >= 0が常に真となり、最初の要素が不当に高い確率で選択されてしまう問題がありました。 s > nに変更することで、n=0の場合でも、sが0より大きくなるまで（つまり、最初の要素の重みが加算されるまで）は条件が満たされません。これにより、各要素がその重みに比例した確率で選択されることが保証され、特定の要素が過剰に選択される不公平な状況が解消されます。

これらの変更は、一見すると小さな修正に見えますが、重み付けされたランダム選択の確率論的な正確性を確保するために極めて重要です。これにより、DNS SRVレコードに基づくサービスディスカバリやロードバランシングが、期待通りに機能するようになります。

参考にした情報源リンク

Go言語 math/rand パッケージのドキュメント: https://pkg.go.dev/math/rand
RFC 2782 - A DNS RR for specifying the location of services (SRV): https://datatracker.ietf.org/doc/html/rfc2782
Weighted Random Selection Algorithm (一般的なアルゴリズムの説明): 関連するプログラミングブログやコンピュータサイエンスの資料。

comemo