衍射的博客

Trie 树，又叫前缀树，字典树， 是一种有序的树形数据结构，用于高效地存储和检索字符串数据集中的键。下图是维基百科上关于trie树的一个典型例子，我们可以很清晰地看到，这棵树存储了许多前缀相似的字符串，给定一个字符串，我们可以很容易知道这个字符串是否被存储，而不需要遍历比较。

这一数据结构有相当多的应用情景，例如：

• 自动补全：
  • 搜索提示：输入网址，跳出可能的选择
  • 输入提示：根据已经输入的字符预测可能的词组和句子
• 拼写检查：存储合法的单词列表，快速查找是否存在合法的单词
• 前缀匹配
• IP路由查找

题目

leetcode 208 实现Trie（前缀树）

请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

提示：

• 1 <= word.length, prefix.length <= 2000
• word 和 prefix 仅由小写英文字母组成
• insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次

分析

这道题有几个地方需要注意：

• insert时，需要标记单词是否截止，因为trie中的节点既有可能是前缀，也有可能是单词
• search与 startswith的区别在于， startswith只需要搜索下去，看看有没有对应的节点；而search还需要判断这个节点是否有截止信号

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

class Trie(object):

    def __init__(self):
        self.root = {}

    def insert(self, word):
        """
        :type word: str
        :rtype: None
        """
        cur_node = self.root
        for c in word:
            if c in cur_node.keys():
                cur_node = cur_node[c]
            else:
                cur_node[c]={}
                cur_node = cur_node[c]
                cur_node[0]=0 # 标记是否截止
        # 标记这个cur_node，标注上截止信号，代表这是一个词
        cur_node[0]=1

        

    def search(self, word):
        """
        :type word: str
        :rtype: bool
        """
        cur_node = self.root
        for c in word:
            if c in cur_node.keys():
                cur_node = cur_node[c]
            else:
                return False
        # 判断有没有截止信号
        if cur_node[0]==0:
            return False
        return True
        

    def startsWith(self, prefix):
        """
        :type prefix: str
        :rtype: bool
        """
        cur_node = self.root
        for c in prefix:
            if c in cur_node.keys():
                cur_node = cur_node[c]
            else:
                return False
        return True
    
trie = Trie()
trie.insert("app")
trie.insert("apple")
trie.insert("beer")
trie.insert("add")
trie.insert("jam")
trie.insert("rental")
trie.insert("rental")
print(trie.search("apps"))
print(trie.startsWith("app"))
print(trie.search("app"))

介绍

期望最大化算法（Expectation-Maximization algorithm, EM）是一种在统计学中估计概率模型参数的方法，特别适用于包含隐变量（latent variables）的概率模型。

如果一个概率模型只有观测变量，那么我们可以基于观测得到的数据，用最大似然估计求得概率模型的参数。但是如果概率模型还包含了无法观测的变量（隐变量），则无法用上述方法估计，所以需要考虑隐变量，引入新的方法对参数进行估计。

应用举例

假设我们有一组一维数据\(X=\{x_1, x_2,...,x_n\}\)，我们认为这些数据是由2个正态分布混合而成的。我们的目标是估计这2个正态分布的参数（均值和方差）以及它们各自的权重。参数如下：

• 第1个分布 \(N(\mu_1, \sigma_1)\)，其中\(\mu_1=5\), \(\sigma_1=9\)
• 第2个分布 \(N(\mu_2, \sigma_2)\)，其中\(\mu_2=15\), \(\sigma_2=0.5\)

两个分布的权重满足：\(\sum_{k=1}^2\pi_k=1\)

我们目前手中只有这一组一维观测数据\(X=\{x_1, x_2,...,x_n\}\)，已知观测数据由2个正态分布组成，目标是求出这2个正态分布的参数以及各自的权重。

注意，我们不能直接使用观测数据去拟合2个分布，因为观测数据的分布实际上是2个正态分布混合而成，其中包含了一个隐变量：

\[ z_i= \begin{cases} 0& x_i \in N(\mu_1, \sigma_1^2)\\ 1& x_i \in N(\mu_2, \sigma_2^2) \end{cases} \]

隐变量\(z_i\)表示数据点\(x_i\)由哪个分布生成。而隐变量\(z_i\)的值无法被观测，所以当我们用最大似然估计去做时，需要考虑所有可能的隐变量情况（不同取值的权重）：

\[ \begin{aligned} L(\theta)&=\prod_{i=1}^{n}f(x_i;\theta) \\ ln L(\theta) &= \sum_{i=1}^{n}ln f(x_i:\theta) \\ &= \sum_{i=1}^{n}ln \sum_{k=1}^{2} \pi_k f(x_i:\theta_k) \end{aligned} \] 但由于 \(\pi_k\)未知，所以难以进行最大似然估计。

EM算法步骤

我们首先用两个正态分布混合生成观测数据：

1
2
3
4

np.random.seed(8)
n_samples = ⅓
data = np.concatenate((np.random.normal(5, 3, n_samples),
                       np.random.normal(15, 0.5, n_samples)))

并随机给予两个分布初始参数以及权重，代码如下：

1
2
3
4
5
6

mu1, sigma1 = 10, 1
mu2, sigma2 = 20, 1
pi1, pi2 = 0.5, 0.5

tolerance = 1e-6
max_iterations = 1000

EM算法分为两个步骤： ### E步（期望步, Expectation step）： 我们需要计算每个数据点 \(x_i\) 属于不同分布的后验概率（本质上是隐变量z的条件期望值），此处可以使用贝叶斯公式计算得到：

\[ \begin{aligned} P(z_i=1|x_i, \theta)&=\frac{P(x_i|z_i=1)P(z_i=1)}{P(x_i)}=\frac{P(x_i|z_i=1)P(z_i=1)}{P(x_i|z_i=1)P(z_i=1)+P(x_i|z_i=2)P(z_i=2)}\\ &=\frac{\pi_1N(x_i|\mu_1, \sigma_1^2)}{\pi_1N(x_i|\mu_1, \sigma_1^2) + \pi_2N(x_i|\mu_2, \sigma_2^2)} \end{aligned} \]

同理可以求得\(P(z_i=2|x_i, \theta)\)。代码如下：

1
2
3
4
5
6
7
8
9
10
11

def normal_pdf(x, mu, sigma):
    # 计算x_i的概率密度
    return (1 / (np.sqrt(2 * np.pi) * sigma)) * np.exp(-0.5 * ((x - mu) / sigma) ** 2)

for iteration in range(max_iterations):
    # E步：计算后验概率
    likelihood1 = normal_pdf(data, mu1, sigma1)
    likelihood2 = normal_pdf(data, mu2, sigma2)
    total_likelihood = pi1 * likelihood1 + pi2 * likelihood2
    posterior1 = (pi1 * likelihood1) / total_likelihood
    posterior2 = (pi2 * likelihood2) / total_likelihood

M步（最大化步, Maximization step）：

在E步得到 \(x_i\) 属于不同分布的后验概率后，也是隐变量\(z_i\)的条件期望后，我们利用这个期望来更新参数估计值，以最大化观测数据的似然函数。

因为现在已经知道了关于隐变量z_i的条件期望，所以我们可以用最大似然估计去估计各分布的参数了：

\[ \mu_k=\mathop{\arg\max}\limits_{\mu_k}{\sum_{i=1}^{n}P(z_i=k|x_i, \theta)}lnf(x_i;\mu_k,\sigma_k^2) \]

\[ \sigma_k^2=\mathop{\arg\max}\limits_{\sigma_k^2}{\sum_{i=1}^{n}P(z_i=k|x_i, \theta)}lnf(x_i;\mu_k,\sigma_k^2) \]

对上述两式进行求解可得各部分更新公式如下（\(\pi_k\)更新同理）： \[ \mu_k = \frac{\sum_{i=1}^{n}P(z_i=k|x_i,\theta)x_i}{\sum_{i=1}^{n}P(z_i=k|x_i,\theta)} \]

\[ \sigma_k^2 = \frac{\sum_{i=1}^{n}P(z_i=k|x_i, \theta)(x_i-\mu_k)^2}{\sum_{i=1}^{n}P(z_i=k|x_i,\theta)} \]

\[ \pi_k=\frac{1}{n}\sum_{i=1}^{n}P(z_i=k|x_i,\theta) \]

代码如下：

1
2
3
4
5
6
7

# M步: 更新参数
pi1_new = np.mean(posterior1)
pi2_new = np.mean(posterior2)
mu1_new = np.sum(posterior1 * data) / np.sum(posterior1)
mu2_new = np.sum(posterior2 * data) / np.sum(posterior2)
sigma1_new = np.sqrt(np.sum(posterior1 * (data - mu1_new) ** 2) / np.sum(posterior1))
sigma2_new = np.sqrt(np.sum(posterior2 * (data - mu2_new) ** 2) / np.sum(posterior2))

完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

import numpy as np
import matplotlib.pyplot as plt

# 生成数据
np.random.seed(8)
n_samples = 100
data = np.concatenate((np.random.normal(5, 3, n_samples // 2),
                       np.random.normal(15, 0.5, n_samples // 2)))

# 初始化参数
mu1, sigma1 = 10, 1
mu2, sigma2 = 20, 1
pi1, pi2 = 0.5, 0.5
tolerance = 1e-6
max_iterations = 1000

def normal_pdf(x, mu, sigma):
    return (1 / (np.sqrt(2 * np.pi) * sigma)) * np.exp(-0.5 * ((x - mu) / sigma) ** 2)

for iteration in range(max_iterations):
    # E步: 计算后验概率
    likelihood1 = normal_pdf(data, mu1, sigma1)
    likelihood2 = normal_pdf(data, mu2, sigma2)
    total_likelihood = pi1 * likelihood1 + pi2 * likelihood2
    posterior1 = (pi1 * likelihood1) / total_likelihood
    posterior2 = (pi2 * likelihood2) / total_likelihood
    
    # M步: 更新参数
    pi1_new = np.mean(posterior1)
    pi2_new = np.mean(posterior2)
    mu1_new = np.sum(posterior1 * data) / np.sum(posterior1)
    mu2_new = np.sum(posterior2 * data) / np.sum(posterior2)
    sigma1_new = np.sqrt(np.sum(posterior1 * (data - mu1_new) ** 2) / np.sum(posterior1))
    sigma2_new = np.sqrt(np.sum(posterior2 * (data - mu2_new) ** 2) / np.sum(posterior2))

    # 检查是否收敛
    if (abs(mu1_new - mu1) < tolerance and
        abs(mu2_new - mu2) < tolerance and
        abs(sigma1_new - sigma1) < tolerance and
        abs(sigma2_new - sigma2) < tolerance):
        break

    # 更新参数
    mu1, mu2, sigma1, sigma2, pi1, pi2 = mu1_new, mu2_new, sigma1_new, sigma2_new, pi1_new, pi2_new

# 打印最终结果
print(f"迭代次数: {iteration}")
print(f"μ1: {mu1}, σ1: {sigma1}, π1: {pi1}")
print(f"μ2: {mu2}, σ2: {sigma2}, π2: {pi2}")

# 绘制结果
plt.hist(data, bins=30, density=True, alpha=0.6, color='g')
x = np.linspace(min(data), max(data), 100)
plt.plot(x, pi1 * normal_pdf(x, mu1, sigma1), 'r-', lw=2, label=f'N({mu1:.2f}, {sigma1:.2f})')
plt.plot(x, pi2 * normal_pdf(x, mu2, sigma2), 'b-', lw=2, label=f'N({mu2:.2f}, {sigma2:.2f})')
plt.legend()
plt.show()

最长公共子序列（LCS）是一个在一个序列集合中用来查找所有序列中最长子序列的问题。这与查找最长公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置。而最长公共子串（要求连续）和最长公共子序列是不同的。

比如：字符串 ABCBDAB 和 字符串 BDCAB 的LCS为 BCAB。

LCS在计算机领域有诸多应用，比如可以：

• 比较 DNA 序列或蛋白质序列。
• 比较不同版本的文件，找出更改的部分
• 文本（代码）相似性检
• ...

假设有两个版本的文件：

• 文件 V1: The quick brown fox jumps over the lazy dog.
• 文件 V2: A quick brown dog jumps over the lazy cat.

通过 LCS 算法，可以找到它们的最长公共子序列为 quick brown jumps over the lazy，剩余的部分为更改，这有助于生成补丁文件和合并冲突。

题目

leetcode 1143 是最长公共子序列的经典问题： > 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。 > >一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 > >- 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。 > > 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：

• 1 <= text1.length, text2.length <= 1000
• text1 和 text2 仅由小写英文字符组成。

分析

最长公共子序列（Longest Common Subsequence, LCS）问题非常适合使用动态规划来解决，原因在于它具备了动态规划的两个关键特性：最优子结构和重叠子问题。

1. 最优子结构：LCS问题的最优解可以由其子问题的最优解构建而来。具体来说：

   • 如果两个序列的最后一个字符相同，那么这个字符必定是LCS的一部分，接下来的问题就转化为了求这两个序列去掉最后一个字符之后的LCS。即 \(LCS(i, j) = LCS(i-1, j-1) + 1\)
   • 如果两个序列的最后一个字符不同，则LCS不会同时包含这两个字符，问题转化为求一个序列去掉最后一个字符之后与另一个序列的LCS。即 \(LCS(i, j) = max(LCS(i-1, j), LCS(i, j-1))\)

   这种性质允许我们将大问题分解为更小的子问题，通过解决这些子问题来构建原始问题的解。

2. 重叠子问题：在求解 LCS 的过程中，我们会反复遇到相同的子问题。例如，在计算两个序列 \(X\) 和 \(Y\) 的LCS时，可能会多次计算 \(X\) 的前 \(i\) 个字符和 \(Y\) 的前 \(j\) 个字符的LCS。由于这些子问题会被多次求解，我们可以将它们的结果存储起来，避免重复计算，这就是动态规划中所谓的“记忆化”。

求解

动态规划的求解步骤如下：

1. 定义状态

   • 在最长公共子序列（LCS）问题中，状态可以用一个二维数组 \(dp\) 表示，其中 \(dp[i][j]\) 表示序列 \(X\) 的前 \(i\) 个字符和序列 \(Y\) 的前 \(j\) 个字符的最长公共子序列的长度。

2. 状态转移方程

   • 在上节最优子结构的判断中，已经定义出了状态转移方程：

     • if \(X[i]==Y[j]\)， \(dp[i][j] = dp[i-1][j-1] + 1\)
     • if \(X[i]!=Y[j]\)， \(dp[i][j] = max(dp[i-1][j], dp[i][j-1])\)

python代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution(object):
    def longestCommonSubsequence(self, text1, text2):
        """
        :type text1: str
        :type text2: str
        :rtype: int
        """
        n, m = len(text1), len(text2)
        # 多声明一行一列，方便计算dp[1][1]
        dp = [[0 for j in range(m+1)] for i in range(n+1)]
        for i in range(1, n+1):
            for j in range(1, m+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[n][m]

最终的\(dp\)表为：

[0, 0, 0, 0]

[0, 1, 1, 1]

[0, 1, 1, 1]

[0, 1, 2, 2]

[0, 1, 2, 2]

[0, 1, 2, 3]

扩充

如果题目要求我们求出具体的最长公共子序列呢？我们可以根据\(dp\)表进行回溯，思路为

1. 从\(dp[n][m]\)开始向前回溯
2. 如果当前\(X[i]==Y[j]\)，那么说明此时\(X[i]\)（\(Y[j]\)）属于LCS的一部分，则加入LCS；同时\(X\)和\(Y\)都向前推进一位
3. 如果当前\(X[i]!=Y[j]\)，那么我们需要找出LCS是在\(X[i-1]\)和\(Y[j]\)中产生，还是在\(X[i]\)和\(Y[j-1]\)中产生，则只需要对比\(dp[i-1][j]\) 和 \(dp[i][j-1]\)

所以代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution(object):
    def longestCommonSubsequence(self, text1, text2):
        """
        :type text1: str
        :type text2: str
        :rtype: int
        """
        n, m = len(text1), len(text2)
        # 多声明一行一列，方便计算dp[1][1]
        dp = [[0 for j in range(m+1)] for i in range(n+1)]
        for i in range(1, n+1):
            for j in range(1, m+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        # 回溯
        i, j = n, m
        lcs = []
        while (i > 0 and j > 0):
            if text1[i-1]==text2[j-1]:
                lcs.append(text1[i-1])
                i-=1
                j-=1
            else:
                if dp[i-1][j] > dp[i][j-1]:
                    i-=1
                else:
                    j-=1
        lcs_str = ''.join(lcs)[::-1]

        return dp[n][m], lcs_str

solution = Solution()
lcs_len, lcs = solution.longestCommonSubsequence('abcde', 'ace')
print(lcs_len, lcs)

回溯路径为：

[0, 0, 0, 0]

[0, 1, 1, 1]

[0, 1, 1, 1]

[0, 1, 2, 2]

[0, 1, 2, 2]

[0, 1, 2, 3]

题目：TraStrainer: Adaptive Sampling for Distributed Traces with System Runtime State

来源：FSE 2024

作者：中山大学DDS实验室

摘要

微服务系统每天都会产生大量的trace数据，带来了极大的计算和存储成本。trace sampling 技术被用来缓解这种压力。trace sampling 分为两种：

• random sampling：又称 head sampling，即以固定概率决定每条trace是否采样
• biased sampling：又称 tail sampling，即根据trace的状态决定是否采样

很明显，random sampling 实现起来简单，但无法保证得到高质量的采样数据；biased sampling 能够根据用户偏好进行采样（比如高延时、异常状态码）。

先前的 biased sampling 工作大多基于密度（diversity），即偏好采样那些少见（edge-case）的traces，常见（common-case）的traces则少采样一些。然而，作者认为仅根据trace的状态进行采样是不充分的，应该再考虑当前系统运行状态（system runtime state），特别是系统处在故障状态时。（作者很有想法，在trace采样中玩了多模态，引入了metric，我觉得陈鹏飞老师实验室的工作还是很扎实且新颖的）

本文提出了TraStrainer，从以下角度进行在线采样： - 考虑密度：采用一种可解释的编码方式将trace转化为向量，方便后续密度采样 - 考虑系统状态：结合当前系统各种运行指标生成偏好向量，方便后续系统采样 - 密度采样+系统采样 \(\to\) 最终采样决策

动机

陈鹏飞老师实验室有大量关于微服务系统的故障诊断的工作，其中有许多是基于trace进行分析的，比如MicroRank，TraceRank和MicroSketch。

trace采样是这些工作的上游任务，先前与biased sampling相关的工作都是基于密度的，目标是采样edge-case traces，没有考虑过采样的traces对下游故障诊断工作的影响。作者从以下两点进行了分析：

1. 仅考虑edge-case traces是不够的。作者在此举例说明 common-case traces也有很大的用处:

   • common-case traces 可能与根因有关。比如线程池因为太多请求的到来而用尽，而这些与根因相关的请求的traces并不一定是异常的，也就被认定为common-case traces。而我们分析这些common-case traces，可以发现这个时刻有高峰流量（这个是我根据自己理解加的）。
   • common-case traces 有利于下游的分析任务。很多工作比如TraceRCA，T-Rank，都需要common-case traces来获得系统的正常模式，从而与故障时刻进行比对。

2. 结合 system runtime state 有利于判断有价值的trace。作者拿了华为的一个真实场景进行分析，如Fig. 3所示，[a,b]时间段 Node A 的 MySQL服务进行全表查询，导致 Node A 的CPU被打满，到达 Node A 的请求变得异常。SREs通常先检查系统状态，发现CPU升高，然后分析经过 Node A 的traces。然而，如果只根据密度进行trace采样，那么[a,b]的traces将被采集的很少，因为还没有发生异常。如果结合系统状态进行采样，那么[a,b]的traces将给予更高的采样权重（[a,b]存在CPU攀升）。

综上，作者认为应该在trace采样时不仅仅考虑traces之间的密度，也要引入对当前系统状态的考虑。

问题定义

给定一段时间收集的traces \(\mathcal{T}\)、对应的系统状态指标 \(\mathcal{M}\)、采样率 \(\beta\)，需要对\(\mathcal{T}\)中每个trace \(t\) 计算采样概率 \(\rho\)。整个过程定义为：

\[ S_p(\beta, \mathcal{T}, \mathcal{M}, t) \to \rho, \mathcal{T'} \]

其中，\(\mathcal{T'}\)是\(\mathcal{T}\)的采样子集。

TraStrainer 概要

TraStrainer的架构和其他在线采样器相似，包含以下模块：

• Runtime Data Preprocessing：

  • Trace Encoder：对trace进行结构和状态编码
  • System Bias Extractor：将当前系统状态指标进行编码

• Comprehensive Sampling：

  • System-Biased Sampler：优先采样与当前系统波动最相似的trace
  • Diversity-Biased Sampler：优先采样edge cases traces
  • Composite Sampler：结合上述两种采样器进行最终决策

Trace Encoder

如Fig.5所示，trace的编码包含结构编码和状态编码两部分：

状态编码：结合 Fig. 5 的例子进行说明，Fig. 5 的Trace Vector的上半部分展示了由指标（node，metric_name）构成的向量，比如指标\(m_1\)就是（\(C\), \(SQLConnectionTime\)）。一条trace由各种span构成，文章的span携带了一些tag（比如Node和annotation）。为了计算\(m_1\)的值\(f_{m_1}\)，作者将所有与\(m_1\)相关的span的duration结合起来，具体计算如下：

\[ f_{m_1}=(|S_a|+1)*\sum_{i=1}^{n}s_{m_1i}.duration \]

\(s_{m_1i}\)即与指标\(m_1\)相关的span，而\(|S_a|\)即相关span中异常span的个数（状态码为error，Fig.5中为1） > 注：最开始不太理解这种设计，后来发现是作者将指标与对应的trace的状态信息（延时+状态码）联系起来，相当于量化了指标对trace状态的影响，非常巧妙。

结构编码：这一块比较简单，即将trace看做一棵树，每层可能有多个span，这些spans由parentSpan、method以及params组成，每一层的spans都被编码为一个特征。这些特征共同组成一个vector。

System Bias Extractor

这一部分的本质是衡量当前系统哪个指标比较重要，这个重要程度由指标的异常程度决定。每个指标的异常程度组合成一个一维的preference vector数组，

作者认为基于统计模型的异常检测不准确，无法识别周期性；而基于LSTM和Transformer的深度学习模型在响应太慢，无法适应线上采样。所以最终采用DLinear algorithm¹，如Fig.6所示，这个算法通过指标的历史时序数据预测当前值\(v_k'\)，并通过以下公式计算指标异常程度： \[ \alpha=\frac{v_k'-v_k}{max(v_k', v_k)} \]

这个公式通过预测值与真实值的差距计算异常度。所有指标\(\mathcal{M}\)的异常度拼在一起就是preference vector \(\mathcal{P}\)。

System-Biased Sampler

System-Biased Sampler的核心是优先考虑与当前系统指标波动最相似的traces（与motivation中的故障诊断对上）。那么需要对新到来的trace进行注意力评估和采样概率计算。

本文定义了一个固定长度look-back window，由\(k\)条最近收集的历史traces组成：\([t_1,...,t_k]\)。System-Biased Sampler只需用到trace的状态编码部分，每条trace的状态向量由n个指标组成，表示为\(t_i=[f_{1i},...,f_{ni}]\)。对历史traces每一维指标计算均值\(\mu_i\)和标准差\(\sigma_i\)，则对新到来的trace \(t_{k+1}\) 的第\(i\)个指标注意力分数计算如下： \[ a_i = \frac{|f_{ik+1}-\mu_i|}{\sigma_i} \]

\(t_{k+1}\)的所有指标的注意力分数记为 \(\mathcal{A}=[a_1,...,a_n]\)，TraStrainer通过将注意力分数\(\mathcal{A}\)和preference vector \(\mathcal{P}\) 进行点积得到面向系统的采样概率\(p_s\)： \[ p_s(t_{k+1})= \frac{2}{1+e^{-2\mathcal{P·\mathcal{A}(t_{k+1})}}}-1 \]

以上操作是将点积\(P·\mathcal{A}(t_{k+1})\)通过tanh函数映射到[0,1]范围，点积越大，代表当前trace与当前系统状态越相似，面向系统的采样概率越大。

Diversity-Biased Sampler

Diversity-Biased Sampler的目标是考虑edge-case traces（即少见的traces），这篇文章与先前工作一样基于聚类来筛选edge-case traces。

论文将look-back window的历史traces进行聚类（基于trace的特征），并计算每个类的质量（traces数量），并把新trace \(t_{k+1}\) 归于最近的类 \(c_{k+1}'\)。\(c_{k+1}'\)的质量为\(ma_{k+1}'\)，计算 trace \(t_{k+1}\) 和 所属类\(c_{k+1}'\) 之间的Jaccard相似度\(si(t_{k+1})\)。

一般来说，所属类\(c_{k+1}'\)的质量和\(si(t_{k+1})\)越小，代表所属类越稀有、新trace越独特，应该给予更高的采样概率。所以面向密度的采样概率\(p_d(t_{k+1})\)计算如下： \[ p_d(t_{k+1})=\frac{\frac{1}{ma_{k+1}'*si(t_{k+1})}}{\sum_{i=1}^{k+1}\frac{1}{ma_{i}'*si(t_{i})}} \]

Composite Sampler

对于新到trace \(t\)，综合两个采样概率 \(p_s(t)\) 和 \(p_d(t)\) 后，考虑采样额度 \(\beta\)，基于动态投票机制（dynamic voting mechanism）最终决策。

首先统计过去look-back window里采样概率 \(\theta\)，如果： - \(\theta \geq \beta\)，必须两个采样决策都为True，才采样 - \(\theta \leq \beta\)，只需要有一个采样决策为True，即可采样

题目：Diagnosing Performance Issues for Large-Scale Microservice Systems with Heterogeneous Graph

来源：TSC 2024

作者：南开大学AIOps@NKU团队，清华大学Netman实验室

摘要

微服务系统的可用性对于业务运营和企业声誉至关重要。然而，微服务系统的动态性和复杂性给大规模微服务系统的性能问题诊断带来了重大挑战。文章分析了腾讯性能故障的真实案例后，发现故障传播的因果关系与服务之间的调用关系不一致，所以之前基于调用关系的根因定位方法准确率不高。文章提出适用于大规模微服务系统的性能问题诊断方法，MicroDig，步骤如下：

• 基于调用和微服务之间的因果关系构建异构传播图
• 采样面向异构的随机游走算法进行根因服务定位

MicroDig在腾讯、Train-Ticket、银行三个数据集上能实现至少85%的top-3 accuracy。

背景

随着微服务系统的快速演变和规模扩张，微服务自身固有的动态性和复杂性给系统的可靠性维护带来了挑战。当微服务系统发生性能异常时，需要及时定位到根因服务，并把问题工单发给对应微服务的团队。然而，由于微服务数量太过庞大（Alibaba有超过30000服务），并且服务之间交互复杂，性能异常在服务之间进行传播，导致大量服务同时异常，进而使得人工诊断变得耗时耗力。

有许多现有工作基于trace来进行根因分析。trace记录了每次请求的调用路径以及相关性能表现，然而，海量的traces会带来极大的存储开销（eBay每天产生150 billion的traces）。所以，越来越多的公司只保留两个服务之间的端到端聚合调用（end-to-end aggregated calls）。

有些工作已经使用了aggregated call（这里指的是Codewisdom团队的GMTA¹），采取模式匹配的方式进行根因定位，但需要非常充足的历史故障数据，这在现实场景中很难实现；也有一些工作基于因果图进行根因定位，他们的因果挖掘算法有极高的计算成本，并且准确率较低。

文章提出的MicroDig的核心思想是：调用关系不等于因果关系（在动机中有具体说明），于是在故障诊断前先构造因果图（节点是微服务和调用）。 【从相关工作的分析到方法的提出有点衔接生硬，可能是因为因果方面的分析放到了动机的原因】

动机

调用关系≠异常传播的因果关系

\(A \to B \to C\) 的异常次数急剧增加，如果仅仅根据调用关系去分析异常传播，那么根因是\(C\)，然而，操作员却没有在\(C\)中发现有意义的故障报告。因为 \(B\) 已经用尽了文件描述符，无法建立与 \(C\) 的新连接，所以\(B \to C\)有大量的异常出现。所以根因是\(B\)不是\(C\)，这与调用关系的回溯是违背的。文章提到腾讯有35%的性能问题不能仅仅依靠调用关系回溯解决。

所以异常的被调用服务不一定是根因，调用方和被调用方都有可能是根因

异构传播图

由3.1可知，仅仅从调用关系分析异常传播是不够的，所以本文提出了一种异构传播图（heterogeneous propagation graph）来描述故障传播的因果关系：

• 如上图所示，\(R(A,B)\) 代表\(A \to B\)的异常率（anomaly rate），\(R(A)\) 代表服务\(A\) 本身的异常率。注意，服务本身的异常率，如\(R(A)\)，在这个工作中是不可观测的；边的异常率，如\(R(A,B)\)，是可以被观测的。

• 因为3.1中展示了调用方和被调用方均可能贡献异常，所以每个服务都应该有一条指向调用边的因果线（比如\(R(A) \to R(A,B)\)）。

• 文章添加了一些假设：①服务之间是独立的，比如\(R(A)\)和\(R(B)\)是独立的【这个假设有点不太符合现实】，②没有交集的两条调用边是独立的，比如\(R(A,B)\)和\(R(C,D)\)

根据作者的设计，这里应该就能看到\(R(B,C)\)是受\(R(B)\)和\(R(C)\)影响的了，从某种意义上给3.1的问题提供了思路。

MicroDig 架构

可以看到MicroDig分为几个部分： 1. 性能监控 (Monitoring) 2. 相关调用的识别 (Association Call Identification) 3. 异构传播图的构建 (Heterogeneous Propagation Graph Construction) 4. 根因定位 (Root Cause Localization)

Association Call Identification

对于大规模微服务系统，如果直接构造调用图，那么图中会包含大量与故障不相关的调用边。所以需要对边进行筛选。

构造port-level 异常子图

文章首先构造 port-level 异常子图，port-level即接口级别，图中的节点都是接口， 具体步骤如下：

1. 构造 port-level 调用图（为什么选用port-level）
2. 在调用图上进行 宽度优先搜索，对于被遍历的边，采用3-sigma 异常检测 对边的异常率或者超时率进行检测，将异常边保留下来，就得到port-level异常子图

为什么先构造port-level异常子图，而不是直接构造service-level异常子图？因为一个service包含太多port，聚合后一些异常port的表现可能被其他正常port掩盖。

构造service-level 异常子图

聚合构造好的port-level异常子图，即把同一个服务的port节点合并为一个service节点，就得到了service-level异常子图。对于服务\(S\)和\(S'\)，定义\(F(p,p')\)和\(N(p,p')\)分别为其中port-level边\(p \to p'\)的异常调用数和总调用数，那么时间点\(t\)的\(S \to S'\)的异常率\(R_t(S, S')\)为：

\[ R_t(S, S')=\frac{\sum_{p\in S, p' \in S'}F_t(p,p')}{\sum_{p\in S, p' \in S'}N_t(p,p')} \]

整个过程如图(a) (b)所示 ：

构造 Heterogeneous Propagation Graph

3.1 中提到调用关系≠故障传播的因果关系，所以service-level异常子图也不能直接用于根因定位，需要进一步构建Heterogeneous Propagation Graph （HPG）：

原理很简单： 1. 设置service节点：把service-level异常子图的所有服务加入到 HPG 2. 设置call节点：对于每个服务\(S\)，将\(S\)的出边和入边作为节点加入HPG 3. call节点和service节点的关系：对于每个call节点（\(S \to S'\)），设置 \(S \to (S \to S')\)，\((S \to S') \to S'\) 4. call节点和call节点的关系：对于每个服务\(S\)，设置：出边 \(\to\) 入边

根因服务定位

异构传播图（HPG）有两种节点（service，call）和两种边（service \(\to\) call, call \(\to\) call）。本文采取针对异构图的随机游走算法来定位根因：

转移权重

随机游走的核心是定义不同边的游走权重：

1. 对于call \(\to\) call：比如\(C_{23} \to C_{12}\)，通过计算这两个调用的异常率数组之间的相关系数来决定游走权重。
2. 对于service \(\to\) call：比如\(S_1 \to C_{12}\)

   • 首先计算service的异常程度，定义\(\mathbb{S}_U\)和\(\mathbb{S}_D\)分别表示服务\(S\)的上游服务集合和下游服务集合，服务\(S\)的异常程度\(\alpha_S\)可以表示为： \[ \alpha_S = \frac{|\{S'|S'\in \mathbb{S}_U \cup \mathbb{S}_D, \theta(S')=1 \}|}{|\mathbb{S}_U \cup \mathbb{S}_D|} \] 当\(S'\)有任意一条port-level的边是异常时，\(\theta(S')=1\)。

   • 然后计算service \(\to\) call的权重。对于任意一个call节点\(C=S_{caller} \to S_{callee}\)，有两条service \(\to\) call类型的边：\(S_{caller} \to C\) 和 \(C \to S_{callee}\)。这两条边的权重分别为：\(\omega_{caller}\) 和 \(\omega_{callee}\)，分别计算如下： \[ \omega_{caller}=max(0, \Delta \eta)*[0.5+\beta sgn(\Delta \alpha)] \]

   \[ \omega_{callee}=max(0, \Delta \eta)*[0.5-\beta sgn(\Delta \alpha)] \] 其中，\(\Delta \alpha = \alpha(S_{caller})-\alpha(S_{callee})\)，\(\Delta \eta\)即当前服务的所有入边的权重-所有出边的权重。

异构随机游走

与Personal pageRank不同的是，作者没有用个性化向量来跳出陷阱，而是在图上加了以下几种边来防止掉入陷阱：

• backward edge：如果有节点只有一条有向边连接，那么则加一个与有向边方向相反的backward edge，权重是有向边的\(\rho\)倍。
• self-loop edge：给每个节点加上自环边

游走算法如下图所示，与普通的随机游走没有太大差别：

总结

• 创新点：这篇文章的创新点不是很突出，随机游走感觉已经玩烂了（如果随机游走上能再精进一下，可能会好一些）。。。但是异构图的构建还是让人耳目一新的
• 动机：动机比较简单，没有实证分析（对腾讯数据的实证分析应该加上的）。
• 代码复现：公布的代码里应该是没有完整数据的，其实除公司以外的测试数据集应该要公开的。

参考文献

题目：MicroHECL: High-Efficient Root Cause Localization in Large-Scale Microservice Systems

来源：ICSE 2021

作者：复旦大学CodeWisdom团队，阿里云

摘要

微服务系统的可用性问题直接影响了业务的运行，这些问题通常由各种各样的故障类型以及服务间故障的传播造成。如何设计精准且高效定位故障根因的方法成为了一个重大挑战。然而，现有基于服务调用图的方法在异常检测的准确率和图游走的效率上存在不足。本文提出了一种高效的根因定位方法MicroHECL，通过如下步骤定位故障根因：

• 动态构建一段时间窗口内的服务调用图
• 对不同异常类型进行个性化异常检测
• 对不同异常类型分析异常传播链路，通过剪枝提高效率

背景

工业微服务系统包含大量的微服务（e.g., alibaba有3000个微服务，300个子系统）。一个服务都可能运行在成百上千个容器中，并时常动态创建和销毁。服务之间也存在复杂的调用关系（同步、异步）。

微服务系统可用性问题可能由不同类型的异常引起，每种异常都由一组指标表示。异常可能源自服务并沿服务调用传播，最终导致可用性问题。文章具体关注三种故障类型（就是谷歌提到的几种黄金指标）：

• 性能异常（Performance Anomaly）
• 可靠性异常（Reliability Anomaly）
• 流量异常（Traffic Anomaly）

MicroHECL 概述

MicroHECL支持三种故障类型的检测和诊断：性能异常、可靠性异常和流量异常。最终输出候选的故障根因服务排名。

服务调用图构建

当MicroHECL检测到异常后（3-sigma），会启动根因分析流程，首先就是构建过去30min内的服务依赖图（service call graph）。图上的节点就是每一个微服务；图上的边代表服务之间的调用关系，比如\(S_i \to S_j\)代表微服务\(S_i\)调用了微服务\(S_j\)；节点上具有一些属性：响应时间（RT），错误数量（EC）以及每秒请求量（QPS）。

异常传播链分析

检测到异常的微服务并不一定是故障根因，但是故障根因一般在这个微服务的上游或者下游。异常传播链分析的目的是筛选初始异常服务中可能的异常传播链来识别一组候选根本原因服务。整个过程由以下几步组成：

• 分析入口服务（即最初汇报异常的微服务，后面会混用）
• 异常传播链扩展
• 根因排序

分析入口服务

性能异常和可靠性异常的传播方向很好理解，因为上游服务的响应时间和状态码受下游服务影响。流量异常的传播方向是从上游到下游，原因是【笔者自己的理解】上游服务发生了故障（比如网络拥塞），那么发送到下游的流量会大幅减少，所以下游服务会出现QPS急剧减少的异常。这个结论也可以在ImpactTracer¹中找到。

有了故障的传播方向，文章从入口服务开始，向邻居节点不断扩展分析。如图Fig. 2所示，整个过程描述如下： > 1. 将入口服务\(S_5\)纳入异常传播链 > 2. 异常检测。检测\(S_5\)的邻居节点\(S_4\)和\(S_7\)的异常类型 > 3. 确认\(S_4\)的异常类型为Traffic Anomaly，\(S_7\)的异常类型为Performance Anomaly > 4. 检测是否符合传播方向（\(S_4\)是否是\(S_5\)的上游，\(S_7\)是否是\(S_5\)的下游） > 5. 符合，将\(S_4\)和\(S_7\)添加到异常传播链 > 6. 从\(S_4\)和\(S_7\)出发，对邻居节点重复上述步骤

以上过程其实就是故障的溯源，图中的箭头可以看作故障的传播路径。过程中涉及的异常检测在3.3节会提到。

异常传播链扩展

过程与3.2.1中描述的扩展过程一致。对于每个检测到的上游/下游异常节点，将其添加到异常传播链中。当无法向链中添加更多节点时，异常传播链的扩展结束。比如Fig. 2对于\(S_4\)方向的传播分析，以\(S_1\)结束；对于\(S_7\)方向的传播分析，以\(S_9\)和\(S_{10}\)结束。

候选根因定位

本文选择异常传播链的末端服务作为候选根因，比如Fig. 2中的候选根因服务为\(S_1\)，\(S_9\)和\(S_{10}\)。那么如何排名呢？

• 选取入口服务过去60min的业务指标 \(X\)
• 选取候选根因服务过去60分钟的质量指标（RT, EC or QPS）\(Y\)
• 计算两者之间的皮尔逊相关系数：

\[ P(X, Y)=\frac{\sum_{i=1}^n{(X_i-\overline{X})(Y_i-\overline{Y})}}{\sqrt{\sum_{i=1}^n{(X_i-\overline{X})^2}\sum_{i=1}^n{(Y_i-\overline{Y})^2}}} \]

皮尔逊相关系数范围为[-1,1]，绝对值越接近1则表明相关性越大。所以，根因则根据皮尔逊相关系数的绝对值来排序。

服务异常检测

这篇文章的重点应该是放在了如何设计精准的异常检测上。不同于以往的方法只使用一种异常检测手段，本文对三种故障类型（Performance Anomaly，Reliability Anomaly，Traffic Anomaly）分别设计了异常检测方法。

这三种方法分别对应三种指标：响应时间（RT），错误数量（EC）以及每秒请求量（QPS），以下是阿里巴巴监控系统中获取的异常案例：

性能异常检测

在RT的异常检测中，需要考虑RT可能存在的周期性（如Fig. 3 (d)）所示，简单的使用3-sigma方法会将这种正常周期波动视为异常。所以不仅需要考虑当前期间的质量指标，还需要考虑前一天和前一周同一天的质量指标。

本文使用OC-SVM训练异常检测模型，OC-SVM是一种常用的无监督机器学习模型，常用于异常检测和分类。文章为RT构建了以下4种特征：

• 当前检测窗口中RT的值大于给定比较时间窗口内RT的最大值的数量。
• 当前检测窗口中RT的最大值与给定比较时间窗口内的RT最大值的差值。
• 当前检测时间窗口中超过给定比较时间窗口中RT滑动平均值最大值的数量。
• 当前检测窗口中RT的平均值与给定时间窗口内RT的滑动平均值的最大值的比值。

其中，当前检测窗口大小为10min，给定比较时间窗口有3种：①过去一小时、②前一天同一小时、③前一周同一天的同一小时。（如果数据保存没那么完善和严格的话，笔者认为定义一段正常时间为比较窗口应该也是可以接受的）。所以一共有3*4=12种特征。

对于模型训练和验证，文章拿10000样本作为训练集，600个正负比例1:1的样本作为测试集。

可靠性异常检测

这里提到EC大多时候都是0（Fig.2 (b,c)），偶尔会出现少许波动，但很快会恢复（比如断路器打开时EC升高，关闭后EC降低），也没有周期性，如果用性能异常的模型，则会出现大量误报（少许波动都会算进去）。

所以，文章采用随机森林（Random Forest，RF）来分类，文章为EC构建了以下5种特征：

• 计算最近一小时的EC和前一天同一时间段的EC的增量；使用3-Sigma规则识别当前检测窗口中可能存在的增量异常值；如果存在，则返回异常值的平均值作为特征值，否则返回0。
• 计算最近一小时内EC值和每一个值的前一分钟EC值的增量；使用3-Sigma规则识别当前检测窗口中可能存在的增量异常值；如果存在，则返回异常值的平均值作为特征值，否则返回0。
• 检测窗口内的平均RT是否大于设定的阈值（例如，在本文的线上系统中，阈值设置为50ms）
• 检测窗口内最大错误率（EC/sum(QPS)）。
• 检测窗口内RT和EC的皮尔逊相关系数

其中，当前检测窗口大小为10min，对于模型训练和验证，文章拿1000样本作为训练集（有标签，正负比1:3），400个正负比例5:3的样本作为测试集。

流量异常检测

QPS大多满足正态分布（Fig.2 (c,f)），所以直接采用3-sigma进行检测。 > 这里笔者有小小的疑问，QPS真的满足正态分布吗？在系统那边的文章，许多流量都是以泊松分布注入的

其中，当前检测窗口大小为10min，选择过去1h计算均值和标准差。3-sigma的均值和方差选择。为了进一步消除误报，还需要检测初始异常服务的QPS和业务指标（就是入口服务被异常检测的指标）的皮尔逊系数，如果大于0.9，则报告流量异常。

剪枝

为了提高MicroHECL的异常回溯效率，需要控制指数增长的异常传播链分支数量，因为不断地进行异常检测也是非常耗时的。

核心思想：异常传播链中的两个连续服务调用的相应质量指标应该具有相似变化趋势

例子：Fig. 2中的 \(S_1 \to S_4\) 和 \(S_4 \to S_5\) 都是Traffic Anomaly 的传播路径，如果\(S_1 \to S_4\) 的 QPS 和 \(S_4 \to S_5\) 的 QPS 没有相似的趋势（即皮尔逊相关系数<0.7），则需要剪掉\(S_1 \to S_4\)，那么\(S_4\)就取代\(S_1\)变成了候选根因。

这里的检测窗口选取的过去60min。剪枝操作执行在异常节点加入异常调用链之前。

总结

文章思路挺好的，有理有据，方法朴实有效。写作的顺序不是传统的总分形式，首先就把整体流程讲完了，然后拿出异常检测和剪枝单独讲，初看有点不适应。

参考文献

题目：Characterizing Microservice Dependency and Performance: Alibaba Trace Analysis

来源：SoCC 2021

作者：中国科学院深圳先进技术研究院, 阿里巴巴

摘要

现在有大量针对微服务架构的研究，比如资源管理、弹性伸缩以及故障诊断等。但是目前仍缺乏针对生产环境中微服务特性的实证研究。这篇文章对阿里巴巴公布的trace数据集¹进行了详细的实证分析，从以下角度揭示了生产环境下微服务系统的特点：

• 微服务调用图的特点，与传统作业DAG的不同
• 无状态微服务之间的依赖关系
• 微服务系统的运行时性能受哪些因素的影响

此外，现有的微服务benchmark也存在一些问题，如：

• 规模太小。经典的benchmark（如DeathStarBench²），只包含数个微服务（不超过40）。在这些小规模的微服务benchmark上得到的结论不一定能推广到生产环境中；
• 静态依赖。这些benchmark的依赖关系都是静态的，无法模拟生产环境中常见的动态性。

所以这篇文章还基于阿里巴巴的trace数据构建了一个仿真的数学模型，模拟大规模动态微服务系统。

背景

微服务架构

这里首先介绍了微服务架构的调用图，以及图中常见的组件：

这里引入了几个关键术语：

• Entering Microservice：入口微服务，即请求进入微服务系统的入口。通常是前端微服务。
• UM, DM：分别指代一条调用链路的上游微服务（upstream microservice）和下游微服务（downstream microservice）。

对于微服务种类，文章基于服务提供的功能将微服务划分为有状态微服务（stateful）和无状态微服务（stateless）。

• stateful微服务：通常存储有一些状态数据，常见的有数据库（database）和缓存（memCached），它们大多的接口大多分为两类：reading 和 writing。
• stateless微服务：不存储状态数据，所以可以轻松的伸缩，它们通常提供成百上千个不同接口，用于完成不同的业务功能。

对于微服务交互种类，文章基于交互协议划分了三种类别：

• IP：进程间通信（Inter Process communication），常发生在stateless微服务和stateful微服务之间。
• RPC：远程过程调用（Remote Procedure Call），一种双向通信，DM必须返回给UM结果。
• MQ：消息队列（Message Queue），一种单向通信，UM发送消息到第三方中间件（消息队列），消息队列储存这个消息，直到DM主动取出这个消息。

一般来说，RPC效率高，MQ更加灵活。

此外，还介绍了两个概念：调用深度（call depth）和响应延迟（RT）。

• call depth：调用深度指调用图中最长的路径长度，比如Figure 1中的调用图长度为5。
• RT：从UM发出请求到UM收到回复的时长。即使同一种接口的请求也会因为参数、状态的不同产生差距较大的延时。

Alibaba Trace

alibaba的trace与常见的trace数据模型不同³，因为它更像一种多模态监控数据，包含了节点信息、指标以及调用链等。具体信息如下：

1. 物理运行环境：阿里巴巴的集群采用K8s进行管理，整个集群运行在裸机云（bare-metal cloud）上，服务与作业通常混合部署在一起以提高资源利用率。Figure 2 (a) 介绍了云上两种常见的运行方式：

   1. Online Services：比如微服务，运行在容器中，直接由K8s管理，有持续向外界提供服务的能力。（stateful微服务一般部署在特定集群中，不参与混合部署）
   2. Offline Jobs：这些作业一般都需要执行特定的任务，需要K8s事先为它们分配资源，然后调度到特定的机器上执行。

2. 微服务系统指标：这个大概分为三个部分：硬件层（缓存命中率）、操作系统层（CPU利用率）、应用层（JVM垃圾回收），具体内容如Figure 2 （b）。

3. 微服务调用链：如Figure 2 (c)所示，大体上与OpenTracing的数据模型类似，但是摒弃了spanID和parentSpanId，只留下UM和DM的信息，并用rpcId来唯一标识一个trace内的不同调用，Communication Paradigm代表调用类型（又名rpctype，如rpc）。

   

4. 聚合调用：如Figure 2 (d)所示，本质上是对单个微服务的调用信息进行聚合和统计。

调用图的剖析

这一块内容很多，我只提炼出较为有意义的部分。这里的调用图（call graph）并不是指整个微服务依赖图，应该指的是单个trace的拓扑图。

微服务调用图特征

作者在这里总结了三个特征，对下游任务非常有启发：

1. 调用图的微服务数量呈现长尾分布

   

现有的benchmark太小了：10%的调用图的微服务数量>40，存在微服务数量>100的调用图。 大量的Memcacheds：大规模的调用图中有一半的微服务都是Memcacheds，可能是为了减少RT。

2. 调用图是一棵树，并且很多图是一条长链路

   

   

较短的深度：一半的调用图深度在2~4 （a） 树有点胖：，深度随着微服务数量增加没有明显变化 （b），说明调用图是宽且浅的？很多下游微服务只是简单的查询数据（stateful微服务一般是叶子节点） 较深的图一般都是长链路：深度增加，但是后面的的微服务数量大多为1个，说明这棵树的宽度基本集中在第2层，后面的都是一条长链路

有些下游任务（弹性伸缩）会对调用图进行编码，作者特别提到有些图有很长的深度，会让这些任务产生很大的模型以及过拟合。我觉得这没有直接关系，这些数量远远达不到图网络的极限。而且这个实验也可以反过来说，大部分图深度都是很短的。

3. 许多stateless微服务是热点

   

存在高入度微服务：有5%的stateless微服务入度>16，这些微服务在90%的调用图存在，处理了95%的请求。这些服务很大概率是瓶颈，可以用来指导弹性伸缩。

4. 微服务调用图大多是动态的

这个动态和其他文章提到的动态不一样，文中的动态性指的是请求同一个服务的接口，如果参数不一样，会产生不同的拓扑链路（Figure 6）；其他文章提到的是微服务系统始终在动态变化。

微服务调用关系特征

1. 不同层之间调用类型差别大

   

首先考虑微服务是否DM，大致分为以下几类：① black holes（没有DM），②relay（必须有DM），③normal（一定概率有DM）

IP(S2D)，IP(S2M)，IP(S2) 表示IP通信的双方分别为：stateless 微服务与database，stateless 微服务与Memcacheds，stateless微服务与stateless微服务

深度增加，black holes比例增加，relay比例减少，normal中对应部分也是如此。

深度增加，IP(S2M) 比例先增后减，IP(S2D)在升高，表明缓存命中率在下降，转而去查询数据库。MQ比例增加，说明业务链路较深时（业务复杂），倾向于使用MQ来减少RT

微服务之间的依赖

这一章节对如何设计和优化微服务架构有启发，不是我研究的范畴，暂时略过

并行依赖

并行依赖很少：数据集中大部分的微服务都很少被并行调用，这个并行给我的感觉就是异步调用

微服务的运行时性能

这个章节很重要，对资源管理有很大的指导作用。首先介绍一个定义：MCR代表微服务调用速率，我的理解是服务承受的负载

MCR对资源的影响

1. MCR与CPU利用率和Young GC强相关，但与Memory利用率相关性弱

与CPU利用率，Young GC强相关：Young GC指的是对JVM堆内存中的新生代区域进行垃圾回收⁴，Young GC频繁会造成性能下降或者应用stop，可能是因为内存泄漏等原因。 与内存，Old GC相关性弱：alibaba trace中容器的内存一般都很稳定，Old GC频率可能也是如此（老年代本身垃圾回收就不频繁），所以在实验中不是很明显（受限于数据集特征）。

2. 资源对响应时间的影响

   

图中的延时选的是P75延时 > 与CPU利用率强相关：随着CPU利用率升高，RT明显升高，但RT对内存反应不是很明显（可能是因为缺乏高内存数据） > 与容器的MCR不太相关：Alibaba trace中即使MCR很高了，CPU利用率可能还低于10%，所以RT变化不大，说明资源浪费很严重

随机图模型

这里简单讲一下，代码实现应该不难： 1. 准备一个存储stateless服务的队列\(Q\)，并放入Entering Microservice 2. 执行循环，直到\(Q\)为空 1. \(Q\)弹出一个服务作为UM 2. 如果UM的类型是Relay或者normal (Relay)，则根据数据集中DM服务类型的分布，生成对应类型的服务数量 3. 为生成的DMs中不同服务类型确定communication paradigm 4. 将生成的DMs中stateless的微服务放入\(Q\) 3. 图优化 1. 遍历生成的图的每一层 1. 随机选择两个父项，如果他们共享相同的标签，则合并他们的两个孩子。 2. 合并的节点将连接到两个父节点

暂时还没有看到随机模型被其他论文使用，可能是因为大家都可以自己搭建环境生产数据吧，也可能是因为alibaba trace够用了

参考文献