《MMO 服务器开发》5.1 为什么游戏不只用 TCP

发送:   [p1] [p2] [p3] [p4] [p5]        p2 丢失
到达:   [p1] [--] [p3] [p4] [p5]
应用:   p1 交付；p3/p4/p5 全部阻塞在接收缓冲区
        ↓ 等 p2 重传（约一个 RTO）
应用:   p2 到达 → p2/p3/p4/p5 一次性交付
        此时 p3/p4/p5 的数据已经过期，但延迟已经发生了

// file: internal/kcp/hol.go
// tier: L1
// verify: go test ./internal/kcp/
package kcp

import (
	"math"
	"math/rand"
	"sort"
)

// SimConfig 描述一条虚拟信道。所有模拟都由固定种子驱动，因此同一份配置
// 在任何机器上都会跑出同一组数字。
type SimConfig struct {
	Seed       int64   // 固定随机种子
	LossRate   float64 // 丢包率，0~1
	RTTMs      float64 // 往返时延（毫秒）
	JitterMs   float64 // 单向抖动上限（毫秒）
	RTOFactor  float64 // 重传超时 = RTOFactor × RTT
	Count      int     // 消息条数
	IntervalMs float64 // 相邻消息的发送间隔（毫秒）
}

// oneWay 返回单向时延。RTT 是对称信道，所以一半一半。
func (c SimConfig) oneWay() float64 { return c.RTTMs / 2 }

// rto 返回重传超时。教学模型用 RTOFactor×RTT 近似 TCP 的 RTO，
// 不建模指数退避——这一节的目的是暴露队头阻塞，而不是复刻 TCP 的退让曲线。
func (c SimConfig) rto() float64 {
	f := c.RTOFactor
	if f <= 0 {
		f = 2
	}
	return f * c.RTTMs
}

// arrival 返回一条消息第一次成功抵达接收端的时刻：每次尝试按 LossRate
// 判定是否丢失，丢了就等一个 RTO 再试，直到某次成功。
func (c SimConfig) arrival(rng *rand.Rand, send float64) float64 {
	t := send
	for {
		if rng.Float64() >= c.LossRate {
			j := 0.0
			if c.JitterMs > 0 {
				j = rng.Float64() * c.JitterMs
			}
			return t + c.oneWay() + j
		}
		t += c.rto()
	}
}

// Simulate 用同一条消息流跑一次虚拟信道，返回每条消息的端到端延迟（毫秒）。
//
// streams == 1 时所有消息共享一条有序流，这正是 TCP 的语义：接收端必须按序
// 交付，前面一条丢了，后面已经到达的消息也只能压在缓冲区里等它重传，这就是
// 队头阻塞（head-of-line blocking）。
//
// streams 越大，消息越分散到互相独立的通道上；streams >= Count 时每条消息
// 各走各的，等价于一组互不阻塞的数据报。
func Simulate(cfg SimConfig, streams int) []float64 {
	if streams < 1 {
		streams = 1
	}
	rng := rand.New(rand.NewSource(cfg.Seed))
	delays := make([]float64, cfg.Count)
	last := make([]float64, streams)
	for i := range last {
		last[i] = math.Inf(-1)
	}
	for i := 0; i < cfg.Count; i++ {
		send := float64(i) * cfg.IntervalMs
		a := cfg.arrival(rng, send)
		s := i % streams
		// 关键的一行：交付时刻不能早于本通道上一条消息的交付时刻。
		d := math.Max(a, last[s])
		last[s] = d
		delays[i] = d - send
	}
	return delays
}

// LatencyStat 是一组延迟样本的常用分位。
type LatencyStat struct {
	P50  float64
	P99  float64
	Max  float64
	Mean float64
}

// Summarize 汇总一组延迟样本。
func Summarize(xs []float64) LatencyStat {
	return LatencyStat{
		P50:  Percentile(xs, 50),
		P99:  Percentile(xs, 99),
		Max:  Percentile(xs, 100),
		Mean: Mean(xs),
	}
}

// Percentile 用最近秩法求第 p 百分位（p 取 0~100），不修改入参。
func Percentile(xs []float64, p float64) float64 {
	if len(xs) == 0 {
		return 0
	}
	s := append([]float64(nil), xs...)
	sort.Float64s(s)
	rank := int(math.Ceil(p/100*float64(len(s)))) - 1
	if rank < 0 {
		rank = 0
	}
	if rank >= len(s) {
		rank = len(s) - 1
	}
	return s[rank]
}

// Mean 返回样本均值。
func Mean(xs []float64) float64 {
	if len(xs) == 0 {
		return 0
	}
	var sum float64
	for _, v := range xs {
		sum += v
	}
	return sum / float64(len(xs))
}

// file: internal/kcp/hol_test.go
// tier: L1
// verify: go test ./internal/kcp/
package kcp

import "testing"

// TestHOLBlocking 用同一组信道参数对比「单条有序流」与「多条独立通道」的
// 延迟分布。单流的中位数与 P90 会被队头阻塞显著抬高。
func TestHOLBlocking(t *testing.T) {
	for _, loss := range []float64{0.05, 0.20} {
		cfg := SimConfig{
			Seed:       42,
			LossRate:   loss,
			RTTMs:      60,
			JitterMs:   10,
			RTOFactor:  2,
			Count:      600,
			IntervalMs: 33.3, // 约 30Hz
		}
		t.Logf("=== 丢包率 %.0f%%，RTT 60ms，30Hz ===", loss*100)
		for _, streams := range []int{1, 4, 16, 600} {
			d := Simulate(cfg, streams)
			st := Summarize(d)
			t.Logf("streams=%-4d P50=%6.1f P90=%6.1f P99=%7.1f max=%8.1f mean=%6.1f",
				streams, st.P50, Percentile(d, 90), st.P99, st.Max, st.Mean)
		}
	}

	cfg := SimConfig{Seed: 42, LossRate: 0.05, RTTMs: 60, JitterMs: 10, RTOFactor: 2, Count: 600, IntervalMs: 33.3}
	single, multi := Simulate(cfg, 1), Simulate(cfg, 16)
	if Mean(single) <= Mean(multi) {
		t.Fatalf("队头阻塞未体现：single mean=%.1f 应高于 multi mean=%.1f", Mean(single), Mean(multi))
	}
	if Percentile(single, 90) <= Percentile(multi, 90) {
		t.Fatalf("队头阻塞未体现：single P90=%.1f 应高于 multi P90=%.1f",
			Percentile(single, 90), Percentile(multi, 90))
	}
	// 零丢包时两种模型必须完全一致，证明差异确实来自丢包而非模型本身。
	clean := cfg
	clean.LossRate = 0
	if s0, s16 := Summarize(Simulate(clean, 1)), Summarize(Simulate(clean, 16)); s0.P99 != s16.P99 {
		t.Fatalf("零丢包下不该有差异：%+v vs %+v", s0, s16)
	}
}