编程语言研究书库
Go 系统编程实践

时间序列数据挖掘三件套(分类/聚类/离群),加上 Green Tea GC 与 Go 1.26 的并发可观测性

数据挖掘三件套 + Go 1.26 的并发可观测性

这一章前半问:「一堆时间序列,怎么自动分成类、聚成堆、揪出异类?」 三个任务共用同一套距离度量,差别只在距离的用法: 分类比「谁最像」(最近邻投票),聚类比「谁属于哪堆」(K-Means), 离群比「谁离谁都远」(k 近邻平均距离)。 后半章切回运行时:Go 1.26 换了新垃圾回收器(Green Tea), 还给了两个看 goroutine 的新仪器——状态指标和泄漏档案。 读完你会拿到「无监督时间序列分析」的完整工具箱, 以及「怎么证明并发程序没漏」的新答案。

1. 这一章在原书里的位置

原书第 13 章,直接建在第 12 章的 tslib 之上—— 「三个数据挖掘任务的区别,只是距离的使用方式不同」1。 章内的暗线也很清楚:数据挖掘是 CPU 密集负载, 所以 GC 的停顿和 goroutine 的泄漏不是抽象话题, 而是吞吐量的直接敌人——后半章的运行时新特性就是为此而来。

2. 顶层全景:三个任务,一条流水线

  载入 → (可选)摘要降长 → Z 归一化 → 六种距离 × 并行(信号量限流)
        │
        ├─ 分类: 每个文件留一当查询,六个度量各排名次
        │         名次加总(弹性度量 ×2)= 共识最近邻
        ├─ 聚类: K-Means(k 堆,最多 iter 轮,seed 可复现)
        └─ 离群: 分 = 到 k 近邻的平均距离;
                  各度量先转名次(量纲不可直接相加),再加权加总
  ─────────────────────────────────────────────
  支撑: Green Tea GC(停顿更短)· goroutine 状态指标 · 泄漏档案(谁生的)

图说:上半是「距离的使用法」三分支,下半是「跑得快还要看得见」的两个新仪器。

3. 分类:留一法 + 六度量名次投票

任务定义:给每条序列找数据集中「最正宗的同类」。 书上方案的四个决策,每个都值得带走2:

  1. 留一(Leave-One-Out):每次拿一条当未知查询, 在剩下的文件里找邻居——自配对永远排除,结果可交叉验证;
  2. Z 归一化先于一切距离:把每条序列拉到均值 0、方差 1—— 只比形状不比量纲(第 14 号 LCSS 因量纲翻车的教训在这里补上);
  3. 六种度量各投一票:不迷信单一度量(各有各的偏见), 每个度量给候选排名次 1..N;
  4. 名次加权加总,弹性度量双倍:
  共识分 = 1×(Euclid名次 + Manh名次 + Cheb名次)
         + 2×(DTW名次 + LCSS名次 + MPdist名次)

权重 2.0 是明说的立场:形状匹配(DTW/MPdist 的视角)比逐点对齐重要一倍3。 工程配套:候选两两比较开 goroutine,但信号量 chan struct{} 限到 runtime.NumCPU() ——否则几百个 MPdist 齐飞,内存先崩(第 3 号 worker pool 的判据在此兑现)4。

4. 聚类:K-Means 搬上时间轴

K-Means 在这里没有新数学:随机选 k 条当初始中心、 按最近距离分堆、重算堆中心、迭代到收敛或轮数上限。 书上的工程细节比算法本身更教学:-seed 参数保证可复现 (默认 0 = 用当前时间,实验重跑会飘;手工设种子才能写进论文)5。 还有一个前置校验很朴素:文件数 ≥ k,否则「把数据分成比数据还多的堆」 数学上就不成立5。聚类输出天然是离群分析的序曲—— 单元素堆(ts8 独自成堆)就是离群的形状6。

5. 离群:谁离谁都远

定义干净:离群分 = 一条序列到它的 k 个最近邻的平均距离—— 分越高,连最像它的几个都差得远,它就是异类7。 关键的工程决策是名次归一:原始距离的量纲天差地别 (Manhattan 可能是几千、MPdist 是小数),直接相加没有意义; 每个度量内部先把分排序换成名次(rank 1 = 最正常,rank N = 最离群), 再按同一套权重(弹性 ×2)加总——「多种数学定义相似度下都 consistently 离群」的文件才会冒头7。这和分类的聚合是同一招,复用得漂亮。

6. Green Tea:换一颗回收器(Go 1.26)

Green Tea 把标记(mark)阶段从「逐对象追指针」改成「按内存页(page)处理」: 不再一个对象一个对象扫,整页入队、页内每个对象只占 2 个位(seen + scanned), 按内存顺序连续处理一大段——cache 命中率高了、指针追得少了、 每次回收更便宜8。配合分代假说(老对象大多一直活着): 折磨测试里那条 500 万节点的常驻链表被提升为老年代, 小回收几乎不用再看它9。

书上的折磨测试(greenTea.go)是刻意为旧 GC 设计的刑房: 节点凑满一个 CPU 缓存行(64 字节填充)→ 缓存局部性最差; 链表而非切片 → 标记只能逐节点追指针。 500 万节点常驻 + churn 5000 万临时对象,逼 GC 每轮都重扫活集10:

  旧 GC(GOEXPERIMENT=nogreenteagc): 111 轮,停顿合计 3.663 ms
  新 GC(默认):                      114 轮,停顿合计 3.362 ms
  → 停顿降约 8%,总时长快约 5%

图说:新 GC 宁可多跑几轮(每轮更便宜),总账还是赢。 (注:nogreenteagc 开关是实验性的,书里注明预计 Go 1.27 会移除10。)

7. Go 1.26 的并发可观测性两件套

① goroutine 状态指标(runtime/metrics 新增,开四个采样点)11:

  /sched/goroutines/runnable:  就绪排队等 CPU
  /sched/goroutines/running:   正在执行
  /sched/goroutines/waiting:   主动挂起(等 I/O、定时器、channel)
  /sched/goroutines/syscall:   卡在系统调用

示例程序造了两个对照 goroutine(一个 Sleep → waiting,一个死循环 → running), 快照输出:runnable 1 / running 3 / waiting 4—— waiting 恒定是正常,无限增长就是泄漏的签名12。

② goroutine leak profile(实验性,GOEXPERIMENT=goroutineleakprofile): 老办法 dump 栈只能看到 goroutine 卡在哪;新档案记录的是它在哪一行被生出来—— 统计采样 go 语句、记下生成时刻父栈,还存活的被采样 goroutine 可按 pprof 端点取出13。 演示程序是一个经典的「孤儿 worker 泄漏」:每处理一张图开一条 worker, worker 必须往无缓冲 results channel 发结果;消费端遇到 corrupted.jpg 提前 return,不再收——剩下的 worker 全堵在发送上,永远等不到接收者14。 这类 bug 以前要对着一堆栈猜;现在档案直接指到「哪个循环、哪一行 spawn 了它们」。 (对照第 5 号:goroutine 泄漏在那时只有症状学,这里是病因学。)

8. 作者的判断与证据

判断性质依据
三任务共用距离层,只换用法架构主张(代码事实支持)三程序同 import tslib1
多度量名次聚合优于单度量集成学习的朴素版(robust 是目标)权重设计与「consistently outliers」表述37
弹性度量权重应更高作者的领域立场WeightElastic = 2.0 明写3
并行必须配信号量工程事实(资源保护)sem := make(chan struct{}, NumCPU)4
Green Tea 对 CPU 密集负载有益作者实测(单一场景)8% 停顿降低、5% 提速10
waiting 无限增长 = 泄漏签名作者的可观测性判据指标一节原话12

9. 边界与局限

  • Z 归一化是本章唯一教的预处理,但量纲之外还有趋势/季节性 (差分、去趋势)一概未提——真实时间序列功课的一半缺席。
  • 名次聚合丢失了距离的绝对信息:两个「rank 3」可能一个是差点第一、 一个是勉强第三;加权加总对此无感。
  • K-Means 对初始中心敏感只提了 seed 可复现,没讲 k-means++ 之类 更好的初始化——教学取舍,但要知其短。
  • Green Tea 的 8% 来自一个人造的最坏场景:普通负载的收益书里没数据; 「Go 1.27 移除开关」是书里写的预期,属时效性信息,引用时应核最新发布说明。
  • leak profile 是统计采样,短命 goroutine 可能被漏采;实验特性, 生产启用前要读官方文档确认稳定性。

10. 可带走的

  1. 三任务一条线:分类 = 最近邻投票(留一),聚类 = K-Means 分堆, 离群 = k 近邻平均距离。
  2. 先 Z 归一化再比距离——只比形状不比量纲。
  3. 多度量集成:量纲不可直接相加,名次可以;名次加总 + 明说的权重 = 「哪种度量更可信」写进代码。
  4. 并行比较用信号量限到 CPU 数;-seed 让实验可复现。
  5. Green Tea:按页标记 + 每对象 2 位 + 分代假说;「每轮更便宜、轮数可更多」 是总账思维的样板。
  6. goroutine 四态:runnable / running / waiting / syscall; waiting 无限增长是泄漏签名。
  7. leak profile 从「卡在哪」追到「谁生的」——孤儿 worker(发送无接收)是 最经典的那类泄漏,实验特性,值得跟到转正。

11. 原文地图

主题原书章原文位置
三任务共用距离层Classificationtext/127-fm-classification.txt:2(搜「depends on time series distances」)
留一法与 Z 归一化Classificationtext/127-fm-classification.txt:12(搜「Leave-One-Out」) · :17(搜「Z-normalizes」)
名次加权聚合Classificationtext/127-fm-classification.txt:54(搜「WeightLockStep」) · :20(搜「double weight」)
信号量并行Classificationtext/127-fm-classification.txt:159(搜「sem := make」)
K-Means 参数与 seedClusteringtext/128-fm-clustering.txt:33(搜「k := flag.Int」) · :47(搜「seed」)
单元素堆 → 离群Clusteringtext/129-fm-outlier-analysis.txt:2(搜「singleton cluster」)
离群分与名次归一Outlier analysistext/129-fm-outlier-analysis.txt:18(搜「average distance」) · :23(搜「converts these raw scores into ranks」)
Green Tea 机制Trying the Green Tea GCtext/130-fm-trying-the-green-tea-garbage-collector.txt:19(搜「page-centric」) · :22(搜「two bits per object」) · text/131-fm-new-in-go-1-26-goroutine-metrics.txt:4(搜「generational hypothesis」)
折磨测试数字Trying the Green Tea GCtext/130-fm-trying-the-green-tea-garbage-collector.txt:64(搜「111」) · :73(搜「114」) · text/131-fm-new-in-go-1-26-goroutine-metrics.txt:1(搜「8% reduction」)
四态指标Goroutine metricstext/131-fm-new-in-go-1-26-goroutine-metrics.txt:53(搜「/sched/goroutines/runnable」) · text/132-fm-new-in-go-1-26-goroutine-leak-profile.txt:6(搜「runnable:goroutines」)
waiting = 泄漏签名Goroutine metricstext/132-fm-new-in-go-1-26-goroutine-leak-profile.txt:21(搜「grows indefinitely」)
leak profile 诞生现场Goroutine leak profiletext/132-fm-new-in-go-1-26-goroutine-leak-profile.txt:29(搜「GOEXPERIMENT=goroutineleakprofile」) · :31(搜「creation site」)
孤儿 worker 泄漏Goroutine leak profiletext/132-fm-new-in-go-1-26-goroutine-leak-profile.txt:48(搜「orphan worker leak」) · :48(搜「blocks indefinitely」)

Footnotes

  1. 出处:「Classification」(text/127-fm-classification.txt:2,搜「depends on time series distances」)。「What differs among the three data mining tasks is the way a distance is used」。 ↩ ↩2

  2. 出处:「Classification」第 6–28 段(text/127-fm-classification.txt:12,搜「Leave-One-Out」;:17,搜「Z-normalizes」;:19,搜「six different distances」)。 ↩

  3. 出处:「Classification implementation」(text/127-fm-classification.txt:54,搜「WeightLockStep」;:55,搜「WeightElastic」;:82,搜「twice as important」)。 ↩ ↩2 ↩3

  4. 出处:「Classification implementation」(text/127-fm-classification.txt:159,搜「sem := make」)。「restricting the number of simultaneous calculations to match hardware capacity」。 ↩ ↩2

  5. 出处:「Clustering」(text/128-fm-clustering.txt:33,搜「k := flag.Int」;:43,搜「k must」;:46,搜「seed」)。可复现与文件数 ≥ k 的说明在同段。 ↩ ↩2

  6. 出处:「Outlier analysis」开头(text/129-fm-outlier-analysis.txt:2,搜「singleton cluster」;:3,搜「statistical outlier」)。 ↩

  7. 出处:「Outlier analysis」(text/129-fm-outlier-analysis.txt:18,搜「average distance」;:23,搜「converts these raw scores into ranks」;:26,搜「consistently outliers」)。 ↩ ↩2 ↩3

  8. 出处:「Trying the Green Tea garbage collector」第 15–25 段(text/130-fm-trying-the-green-tea-garbage-collector.txt:19,搜「page-centric」;:22,搜「two bits per object」;:23,搜「cache misses」)。 ↩

  9. 出处:「Trying the Green Tea garbage collector」(text/131-fm-new-in-go-1-26-goroutine-metrics.txt:4,搜「generational hypothesis」;:5,搜「promotes it to an old generation」)。 ↩

  10. 出处:「Trying the Green Tea garbage collector」(text/130-fm-trying-the-green-tea-garbage-collector.txt:32,搜「Torture Test」;:44,搜「5,000,000 nodes」;:58,搜「nogreenteagc」;:64,搜「111」;:73,搜「114」;:77,搜「measurable performance boost」;:52,搜「expected to be removed in Go 1.27」)。 ↩ ↩2 ↩3

  11. 出处:「New in Go 1.26: Goroutine metrics」(text/131-fm-new-in-go-1-26-goroutine-metrics.txt:53,搜「/sched/goroutines/runnable」;:59,搜「metrics.Read」)。 ↩

  12. 出处:「New in Go 1.26: Goroutine metrics」(text/132-fm-new-in-go-1-26-goroutine-leak-profile.txt:6,搜「runnable:goroutines」;:16,搜「grows indefinitely」)。 ↩ ↩2

  13. 出处:「New in Go 1.26: Goroutine leak profile」(text/132-fm-new-in-go-1-26-goroutine-leak-profile.txt:29,搜「GOEXPERIMENT=goroutineleakprofile」;:31,搜「creation site」;:34,搜「statistically samples go statements」)。 ↩

  14. 出处:「New in Go 1.26: Goroutine leak profile」(text/132-fm-new-in-go-1-26-goroutine-leak-profile.txt:48,搜「orphan worker leak」;:45,搜「corrupted.jpg」;:48,搜「blocks indefinitely」)。 ↩

时间序列距离:六种度量、三种摘要、一个可发布的 Go 包,以及 TigerBeetle 金融账本

Previous Page

二叉树、基数树,以及收官之作:带 WAL 的分布式文件索引服务

Next Page

On this page

数据挖掘三件套 + Go 1.26 的并发可观测性1. 这一章在原书里的位置2. 顶层全景:三个任务,一条流水线3. 分类:留一法 + 六度量名次投票4. 聚类:K-Means 搬上时间轴5. 离群:谁离谁都远6. Green Tea:换一颗回收器(Go 1.26)7. Go 1.26 的并发可观测性两件套8. 作者的判断与证据9. 边界与局限10. 可带走的11. 原文地图Footnotes