2024年1月

一：背景

1. 讲故事

前些天有位朋友在微信上找到我，说他们的客户端程序卡死了，让我帮忙看下是什么原因导致的？dump也拿到了手，既然有了dump就开始正式分析吧。

二：WinDbg 分析

1. 什么导致的卡死

客户端的程序卡死比较好找原因，入手点就是主线程，看下它此时正在做什么，可以用
k
命令。


0:000> k
 # ChildEBP RetAddr      
00 003cdf7c 74c115ce     ntdll!NtWaitForSingleObject+0x15
01 003cdf7c 756e1194     KERNELBASE!WaitForSingleObjectEx+0x98
02 003cdf94 6f573bea     kernel32!WaitForSingleObjectExImplementation+0x75
03 003cdfc4 6f573c31     clr!CLREventWaitHelper2+0x33
04 003ce014 6f573bb6     clr!CLREventWaitHelper+0x2a
05 003ce04c 6f57c8be     clr!CLREventBase::WaitEx+0x152
06 003ce060 6f5764a9     clr!WKS::GCHeap::WaitUntilGCComplete+0x34
07 003ce0b0 6f583cf4     clr!Thread::RareDisablePreemptiveGC+0x231
08 003ce134 6a87a767     clr!JIT_RareDisableHelper+0x24
09 003ce16c 6a87472b     System_Drawing_ni+0x4a767
0a 003ce17c 0846b372     System_Drawing_ni!System.Drawing.Graphics.Clear+0x1b
...

从卦中信息看，代码正在托管层做Graphics，突然程序触发了GC，因为STW的原因，clr需要使用SuspendRuntime把主线程导入到
WaitUntilGCComplete
进行等待，有了这些信息之后，接下来就是寻找为什么会触发GC。

2. 为什么会触发 GC

要找到GC触发原因，首先要找哪一个线程触发了GC，这个可以用
!t
看下托管线程列表中的 GC 字样，输出如下：


0:000> !t
ThreadCount:      48
UnstartedThread:  0
BackgroundThread: 35
PendingThread:    0
DeadThread:       0
Hosted Runtime:   no
                                                                         Lock  
       ID OSID ThreadOBJ    State GC Mode     GC Alloc Context  Domain   Count Apt Exception
  48   42  ee8 0ee39f60   1029220 Cooperative 00000000:00000000 0076c700 3     MTA (GC) (Threadpool Worker) 
  ...

0:048> k 10
 # ChildEBP RetAddr      
00 4775c9e8 6f57d24e     clr!WKS::gc_heap::mark_object_simple1+0x8a
01 4775ca14 6f57bf72     clr!WKS::gc_heap::mark_object_simple+0x22b
02 4775ca34 6f5774b2     clr!WKS::GCHeap::Promote+0xaa
03 4775ca4c 6f57809c     clr!GcEnumObject+0x37
04 4775cdbc 6f5777cb     clr!EECodeManager::EnumGcRefs+0x854
05 4775ce10 6f5723b9     clr!GcStackCrawlCallBack+0x167
06 4775d0dc 6f5724bf     clr!Thread::StackWalkFramesEx+0x92
07 4775d410 6f57743b     clr!Thread::StackWalkFrames+0x9d
08 4775d448 6f57ba0e     clr!GCToEEInterface::GcScanRoots+0x108
09 4775d4a8 6f5792db     clr!WKS::gc_heap::mark_phase+0x18a
0a 4775d4d0 6f57966f     clr!WKS::gc_heap::gc1+0xda
0b 4775d508 6f57978c     clr!WKS::gc_heap::garbage_collect+0x447
0c 4775d530 6f70b767     clr!WKS::GCHeap::GarbageCollectGeneration+0x1f6
0d 4775d590 6f70b7a3     clr!WKS::gc_heap::trigger_ephemeral_gc+0x1e
0e 4775d590 6f575f6f     clr!WKS::gc_heap::allocate_small+0x270
0f 4775d5bc 6f575fca     clr!WKS::gc_heap::try_allocate_more_space+0x17c
...

从卦中可以看到当前 48 号线程触发了GC，并且是处于三阶段中的标记阶段，接下来需要观察下到底触发的是哪一代GC，可以用
dt
观察下 setting 全局变量即可。


0:048> x clr!*settings*
...
6fbd4bd8          clr!WKS::gc_heap::settings = <no type information>
6fbd7538          clr!SVR::gc_heap::settings = <no type information>
...

0:048> dp clr!WKS::gc_heap::settings
6fbd4bd8  00002ce4 00000002 00000001 00000001
6fbd4be8  00000000 00000000 00000000 00000000
6fbd4bf8  00000001 00000000 00000000 00000000
6fbd4c08  00000000 00000000 00000005 00000001
6fbd4c18  00000000 00000000 00000000 00000001
...

从卦中的
+0x4
偏移可以看到当前触发的是 FullGC，从
+0x38
可以看到GC的触发原因是
reason_oos_soh = 5
，有经验的朋友看到这里应该就知道是什么原因了。

3. 为什么会触发FullGC

相信大家都知道FullGC 有一个 STW 的概念，既然有STW自然就会让程序卡死，回过头来说一下经验在哪里，对，就是这个指针的长度，很显然这个程序是 32bit 的，所以很大概率程序是 32bit 部署，会受到 2G 虚拟地址的限制，因为可用内存不足导致高频的触发 FullGC，可以用
!address -summary
去验证一下。


0:048> !address -summary

--- Usage Summary ---------------- RgnCount ----------- Total Size -------- %ofBusy %ofTotal
<unknown>                               955          6029f000 (   1.503 GB)  81.21%   75.13%
Image                                  1251          10105000 ( 257.020 MB)  13.57%   12.55%
Free                                    326           995d000 ( 153.363 MB)            7.49%
Stack                                   165           34c0000 (  52.750 MB)   2.78%    2.58%
Heap                                    137           2db0000 (  45.688 MB)   2.41%    2.23%
Other                                    12             47000 ( 284.000 kB)   0.01%    0.01%
TEB                                      55             37000 ( 220.000 kB)   0.01%    0.01%
PEB                                       1              1000 (   4.000 kB)   0.00%    0.00%
...
--- State Summary ---------------- RgnCount ----------- Total Size -------- %ofBusy %ofTotal
MEM_COMMIT                             2152          66fc7000 (   1.609 GB)  86.97%   80.46%
MEM_RESERVE                             424           f6cc000 ( 246.797 MB)  13.03%   12.05%
MEM_FREE                                326           995d000 ( 153.363 MB)            7.49%
...

从卦中可以看到，当前程序吃了1.6G的虚拟地址，占全量的 80% ，这样情况按理说程序会抛
OutOfMemoryException
异常，在
!t
中也得到了验证。


0:048> !t
ThreadCount:      48
UnstartedThread:  0
BackgroundThread: 35
PendingThread:    0
DeadThread:       0
Hosted Runtime:   no
                                                                         Lock  
       ID OSID ThreadOBJ    State GC Mode     GC Alloc Context  Domain   Count Apt Exception
...
  33   39 10c8 0ee3dec0   1029220 Preemptive  00000000:00000000 0076c700 0     MTA (Threadpool Worker) System.OutOfMemoryException 32614444 (nested exceptions)
  ...
  46   44  89c 0ee3c458   1029220 Preemptive  00000000:00000000 0076c700 1     MTA (Threadpool Worker) System.OutOfMemoryException 32605d34 (nested exceptions)
  ...

接下来的问题是谁吃掉了 1.6G 的内存，总有地方会吃，可以使用
!eeheap -gc
观察下托管堆。


0:048> !eeheap -gc
Number of GC Heaps: 1
generation 0 starts at 0x32632d50
generation 1 starts at 0x3262534c
generation 2 starts at 0x03291000
ephemeral segment allocation context: (0x3265ffb0, 0x3265ffbc)
 segment     begin  allocated      size
03290000  03291000  0428fee4  0xffeee4(16772836)
06c60000  06c61000  07c5ffc4  0xffefc4(16773060)
...
7d210000  7d211000  7e20ffac  0xffefac(16773036)
31660000  31661000  3265ffb0  0xffefb0(16773040)
Large object heap starts at 0x04291000
 segment     begin  allocated      size
04290000  04291000  0450fa78  0x27ea78(2615928)
53390000  53391000  54391020  0x1000020(16777248)
Total Size:              Size: 0x4622fd30 (1176698160) bytes.
------------------------------
GC Heap Size:    Size: 0x4622fd30 (1176698160) bytes.

从卦中看应该就是托管堆吃掉了，接下来就是看下托管堆中哪一类对象最多，最终找到了一个大集合，命令输出如下：


0:048> !gcroot 4c0507c0
Thread 89c:
    471bd450 07f76405 IBatisNet.DataMapper.MappedStatements.MappedStatement.RunQueryForList[[System.__Canon, mscorlib]](IBatisNet.DataMapper.Scope.RequestScope, IBatisNet.DataMapper.ISqlMapSession, System.Object, System.Collections.Generic.IList`1<System.__Canon>, IBatisNet.DataMapper.RowDelegate`1<System.__Canon>)
        ebp+90: 471be6c4
            ->  32c2ea50 System.Collections.Generic.List`1[[xxx.Model]]
            ->  53391010 xxxRMT[]
            ->  4c0507c0 xxxMT

0:048> !do 32c2ea50
Name:        System.Collections.Generic.List`1[[xxx, xxx]]
MethodTable: 095f1b58
EEClass:     6e246b4c
Size:        24(0x18) bytes
File:        C:\Windows\Microsoft.Net\assembly\GAC_32\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
      MT    Field   Offset                 Type VT     Attr    Value Name
6e67ca34  4001886        4     System.__Canon[]  0 instance 53391010 _items
6e66f2d8  4001887        c         System.Int32  1 instance  3011824 _size
6e66f2d8  4001888       10         System.Int32  1 instance  3011824 _version
6e66d824  4001889        8        System.Object  0 instance 00000000 _syncRoot
6e67ca34  400188a        4     System.__Canon[]  0   static  <no information>

从卦中看当前的List有
length=3011824
，并且还被
89c
线程持有，最终通过代码找到了是某种查询下导致的大SQL引发。

三：总结

这次程序卡死还是挺有意思的，表象是主线程被GC卡住，实则是大SQL导致虚拟地址不足，分享出来让大家少踩坑吧！

图片名称

指数加权平均的偏差修正

\({{v}_{t}}=\beta {{v}_{t-1}}+(1-\beta ){{\theta }_{t}}\)

在上一个博客中，这个（红色）曲线对应
\(\beta\)
的值为0.9，这个（绿色）曲线对应的
\(\beta\)
=0.98，如果执行写在这里的公式，在
\(\beta\)
等于0.98的时候，得到的并不是绿色曲线，而是紫色曲线，可以注意到紫色曲线的起点较低，来看看怎么处理。

计算移动平均数的时候，初始化
\(v_{0} = 0\)
，
\(v_{1} = 0.98v_{0} +0.02\theta_{1}\)
，但是
\(v_{0} =0\)
，所以这部分没有了（
\(0.98v_{0}\)
），所以
\(v_{1} =0.02\theta_{1}\)
，所以如果一天温度是40华氏度，那么
\(v_{1} = 0.02\theta_{1} =0.02 \times 40 = 8\)
，因此得到的值会小很多，所以第一天温度的估测不准。

\(v_{2} = 0.98v_{1} + 0.02\theta_{2}\)
，如果代入
\(v_{1}\)
，然后相乘，所以
\(v_{2}= 0.98 \times 0.02\theta_{1} + 0.02\theta_{2} = 0.0196\theta_{1} +0.02\theta_{2}\)
，假设
\(\theta_{1}\)
和
\(\theta_{2}\)
都是正数，计算后
\(v_{2}\)
要远小于
\(\theta_{1}\)
和
\(\theta_{2}\)
，所以
\(v_{2}\)
不能很好估测出这一年前两天的温度。

有个办法可以修改这一估测，让估测变得更好，更准确，特别是在估测初期，也就是不用
\(v_{t}\)
，而是用
\(\frac{v_{t}}{1- \beta^{t}}\)
，t就是现在的天数。举个具体例子，当
\(t=2\)
时，
\(1 - \beta^{t} = 1 - {0.98}^{2} = 0.0396\)
，因此对第二天温度的估测变成了
\(\frac{v_{2}}{0.0396} =\frac{0.0196\theta_{1} + 0.02\theta_{2}}{0.0396}\)
，也就是
\(\theta_{1}\)
和
\(\theta_{2}\)
的加权平均数，并去除了偏差。会发现随着
\(t\)
增加，
\(\beta^{t}\)
接近于0，所以当
\(t\)
很大的时候，偏差修正几乎没有作用，因此当
\(t\)
较大的时候，紫线基本和绿线重合了。不过在开始学习阶段，才开始预测热身练习，偏差修正可以帮助更好预测温度，偏差修正可以帮助使结果从紫线变成绿线。

在机器学习中，在计算指数加权平均数的大部分时候，大家不在乎执行偏差修正，因为大部分人宁愿熬过初始时期，拿到具有偏差的估测，然后继续计算下去。如果关心初始时期的偏差，在刚开始计算指数加权移动平均数的时候，偏差修正能帮助在早期获取更好的估测。

层次聚类
算法是机器学习中常用的一种无监督学习算法，它用于将数据分为多个类别或层次。
该方法在计算机科学、生物学、社会学等多个领域都有广泛应用。

层次聚类
算法的历史可以追溯到上世纪60年代，当时它主要被用于社会科学中。
随着计算机技术的发展，这种方法在90年代得到了更为广泛的应用。

1. 算法概述

层次聚类
的基本原理是创建一个层次的聚类，通过不断地合并或分裂已存在的聚类来实现。
它分为两种策略：

  1. 凝聚策略
    ：初始时将每个点视为一个簇，然后逐渐合并相近的簇
  2. 分裂策略
    ：开始时将所有点视为一个簇，然后逐渐分裂

在
scikit-learn
中，
层次聚类
的策略有
4种
：

  1. ward
    ：默认策略，也就是最小方差法。它倾向于合并那些使得合并后的簇内部方差最小的两个簇
  2. complete
    ：计算两个簇之间的距离时，考虑两个簇中距离最远的两个样本之间的距离
  3. average
    ：计算两个簇之间的距离时，考虑两个簇中所有样本之间距离的平均值
  4. single
    ：计算两个簇之间的距离时，考虑两个簇中距离最近的两个样本之间的距离

2. 创建样本数据

下面创建月牙形状数据来看看层次聚类的各个策略之间的比较。

from sklearn.datasets import make_moons
import matplotlib.pyplot as plt

ax = plt.subplot()

X, y = make_moons(noise=0.05, n_samples=1000)
ax.scatter(X[:, 0], X[:, 1], marker="o", c=y, s=25, cmap=plt.cm.prism)

plt.show()

image.png
关于各种样本数据的生成，可以参考：
TODO

3. 模型训练

用四种不同的策略来训练上面月牙形状的样本数据。

from sklearn.cluster import AgglomerativeClustering

# 定义
regs = [
    AgglomerativeClustering(linkage="ward"),
    AgglomerativeClustering(linkage="complete"),
    AgglomerativeClustering(linkage="single"),
    AgglomerativeClustering(linkage="average"),
]

# 训练模型
for reg in regs:
    reg.fit(X, y)

fig, axes = plt.subplots(nrows=2, ncols=2)
fig.set_size_inches((10, 8))

# 绘制聚类之后的结果
axes[0][0].scatter(
    X[:, 0], X[:, 1], marker="o", c=regs[0].labels_, s=25, cmap=plt.cm.prism
)
axes[0][0].set_title("ward 策略")

axes[0][1].scatter(
    X[:, 0], X[:, 1], marker="o", c=regs[1].labels_, s=25, cmap=plt.cm.prism
)
axes[0][1].set_title("complete 策略")

axes[1][0].scatter(
    X[:, 0], X[:, 1], marker="o", c=regs[2].labels_, s=25, cmap=plt.cm.prism
)
axes[1][0].set_title("single 策略")

axes[1][1].scatter(
    X[:, 0], X[:, 1], marker="o", c=regs[3].labels_, s=25, cmap=plt.cm.prism
)
axes[1][1].set_title("average 策略")

plt.show()

image.png

从结果可以看出，
single策略
效果最好，它聚类的结果与原始数据的分类情况最为接近。
不过，这并不能说明
single策略
由于其它策略，只能说明
single策略
最适合上面的样本数据。

4. 总结

层次聚类
在许多场景中都得到了应用，例如图像分割、文档聚类、生物信息学中的基因聚类等。
它特别适合那些需要多层次结构的应用。

层次聚类
的最大
优势
在于它提供了一种层次结构的聚类，这对于许多应用来说是
非常自然
的，它能够展示数据在不同粒度下的聚类结果。

但它也存在一些
缺点
。
首先，它的计算
复杂度
相对较高，特别是当数据量很大时；
其次，一旦做出合并或分裂的决策，就不能撤销，这可能导致
错误的累积
。
此外，确定
何时停止
合并或分裂也是一个挑战。

众所周知，python性能比较差，尤其在计算密集型的任务当中，所以机器学习领域的算法开发，大多是将python做胶水来用，他们会在项目中写大量的C/C++代码然后编译为so动态文件供python加载使用。那么时至今日，对于不想学习c/c++的朋友们，rust可以是一个不错的替代品，它有着现代化语言的设计和并肩c/c++语言的运行效率。

本文简单介绍使用rust为python计算性质的代码做一个优化，使用
pyo3
库为python写一个扩展供其调用，咱们下面开始，来看看具体的过程和效率的提升。（PS：本文只是抛砖引玉，初级教程）

我的台式机环境:

设备名称	DESKTOP
处理器	12th Gen Intel(R) Core(TM) i7-12700   2.10 GHz
机带 RAM	32.0 GB (31.8 GB 可用)
系统类型	64 位操作系统, 基于 x64 的处理器

1. python代码

首先给出python代码，这是一个求积分的公式：

import time

def integrate_f(a, b, N):
    s = 0
    dx = (b - a) / N
    for i in range(N):
        s += 2.71828182846 ** (-((a + i * dx) ** 2))
    return s * dx


s = time.time()
print(integrate_f(1.0, 100.0, 200000000))
print("Elapsed: {} s".format(time.time() - s))

执行这段代码花费了:
Elapsed: 32.59504199028015 s

2. rust

use std::time::Instant;

fn main() {
    let now = Instant::now();
    let result = integrate_f(1.0, 100.0, 200000000);
    println!("{}", result);

    println!("Elapsed: {:.2} s", now.elapsed().as_secs_f32())
}

fn integrate_f(a: f64, b: f64, n: i32) -> f64 {
    let mut s: f64 = 0.0;
    let dx: f64 = (b - a) / (n as f64);

    for i in 0..n {
        let mut _tmp: f64 = (a + i as f64 * dx).powf(2.0);
        s += (2.71828182846_f64).powf(-_tmp);
    }

    return s * dx;
}

执行这段代码花费了:
Elapsed: 10.80 s

3. 通过pyo3写扩展

首先创建一个项目，并安装
maturin
库:

# (replace demo with the desired package name)
$ mkdir demo
$ cd demo
$ pip install maturin

然后初始化一个pyo3项目:

$ maturin init

✔

所谓高并发系统，是指能同时处理大量并发请求，并及时响应，从而保证系统的高性能和高可用

那么我们在设计一个高并发系统时，应该考虑哪些方面呢？

1. 搭建集群

如果你只部署一个应用，只部署一台服务器，那抗住的流量请求是非常有限的。并且，单体的应用，有单点的风险，如果它挂了，那服务就不可用了

因此，设计一个高并发系统，我们可以采用分布式部署的方式，部署多台服务器，使用负载均衡的方式把流量分流开，让每个服务器都承担一部分的并发和流量，从而提升整体系统的并发能力

2. 微服务拆分

所谓的微服务拆分，其实就是把一个单体的应用，按功能单一性，拆分为多个服务模块。比如一个电商系统，拆分为用户系统、订单系统、商品系统等等。

因此，微服务拆分同样可以分摊请求流量，提高并发能力。如果配合分布式部署，为每个微服务搭建集群，性能将进一步提升

3. 分库分表

在高并发的场景下，大量请求访问数据库，如果表存储的数据量太大，会影响 MySQL 性能，此时可以考虑分库分表

不管是分库还是分表，都有两种切分方式：水平切分和垂直切分

  • 分表
    • 垂直分表：表中的字段较多，将字段拆分到多个表
    • 水平分表：表中的数据较多，将数据拆分到多个表
  • 分库
    • 垂直分库：数据库表太多，按照业务逻辑进行切分，比如用户相关表放在一个数据库，订单相关表放在另一个数据库
    • 水平分库：指将单张表的数据切分到多个数据库，每个数据库都具有相应的表，只是表的数据不同

4. 主从分离

单机 MySQL 支撑的请求访问是有限的，如果遇到双十一这种情况查询请求量会非常大。这时可以做主从分离，实时性要求不高的读请求都去读从库，写请求或者实时性要求高的请求才走主库，提高了系统的吞吐

5. 使用缓存

使用缓存可以提升接口的性能，在高并发场景下支持更多的用户同时访问。常用的缓存包括：Redis 缓存，内存缓存，浏览器缓存等等

6. CDN

CDN 就是内容分发网络，它表示将静态资源分发到位于多个地理位置机房的服务器，可以做到数据就近访问，加速了静态资源如图片、视频等的访问速度，让系统更好处理正常别的动态请求

7. 异步处理

在类似双十一的活动可能会遇到流量暴涨，系统处理不过来，造成请求阻塞，系统崩溃。这时可以引用消息队列，将请求写入消息队列，系统再以合适的速率从消息队列获取请求处理，避免造成阻塞，提高系统性能

8. 熔断降级

当前互联网系统一般都是分布式部署的，如果出现某个基础服务不可用，最终将导致整个系统不可用。比如分布式调用链路 A -> B -> C，如果 C 出现问题，将导致 B 也会延迟，从而 A 也会延迟。A 会不断失败重新请求，消耗占用系统资源，最终会造成其他的请求同样不可用，导致系统崩溃。熔断机制可以防止应用不断尝试可能超时或失败的服务，保证自身快速响应，提高系统吞吐量

降级机制是指在流量过大，系统资源有限的情况下，为了保证关键服务正常运行，降低部分非关键服务的优先级或质量的一种策略。比如电商网站，流量大的时候就把评论功能停掉，把资源让出来给关键服务

9. 限流

大流量过来时，如果系统资源有限，实在没办法处理全部处理，可以采用限流机制，控制接口发送或接收请求的速率，当超过阈值时，限制新的请求对系统的访问，从而保证系统的稳定性

  1. 1
  2. ...
  3. 68
  4. 69
  5. 70
  6. 71
  7. 72
  8. 73
  9. 74
  10. ...
  11. 125