MLSYS论文阅读——Universal Checkpointing

发表于 2025-07-18

MLSYS论文阅读——Universal Checkpointing

https://arxiv.org/pdf/2406.18820 硬件限制迫使模型必须通过模型并行（将模型状态分片至多张卡）实现扩展，但现有checkpoint技术仍难以适应分布式训练的需求：将分布式模型状态合并为单checkpoint显著拖慢训练速度，在大模型的场景下显得更为严重；而现有的分布式checkpoint与训练时的模型并行策略及硬件配置强绑定，导致其无法在不同配置下恢复训练。因此论文提出了Universal Checkpointing技术。

Introduction

以Megatron-LM和DeepSpeed为代表的分布式训练框架已被广泛用于大规模深度学习模型训练。这些系统提供了易用接口，使得用户能够轻松利用多GPU的高级并行策略（如ZeRO数据并行、张量并行等）训练大语言模型，无需关注底层分布式训练的复杂系统调优技术。尽管现有框架支持多种并行策略以加速训练，如ZeRO-DP/TP/PP/SP等。但其checkpoint机制存在显著缺陷：训练初始分配的GPU资源不可变更；无法在不同并行策略或硬件配置下恢复训练。这种限制在一些关键场景中会导致效率低下，比如GPU硬件资源因为故障或者其他原因发生动态变化，又或者从checkpoint恢复训练时，需调整GPU预算，但现有框架不支持跨配置恢复，会导致运行时错误或状态不一致。本文提出通用checkpoint（Universal Checkpointing, UCP），其核心能力概括就是支持自由恢复训练，允许用户以与原始训练不同的并行策略和硬件配置（如GPU数量）恢复分布式训练。其挑战与设计目标主要有几点：定义通用checkpoint格式，支持灵活转换ZeRO数据并行、3D并行等高级策略；不增加分布式训练过程的开销；模型质量无损，恢复后的loss需与原始策略一致。 UCP已集成至开源库DeepSpeed，具备以下特性： * 灵活转换支持：覆盖ZeRO-DP、TP、PP、SP等并行策略； * 弹性资源管理：支持硬件资源动态扩缩容，适应训练与微调需求； * 语言集成接口：提供声明式编程接口，描述并行模式并转换分布式checkpoint为UCP格式； * 跨框架兼容性：支持从HuggingFace Transformers Accelerate、PyTorch Lightning等框架恢复checkpoint（以DeepSpeed为后端）。

checkpoint是深度学习训练的核心组件。训练任务需周期性地将GPU上的模型参数、优化器状态以及重要CPU状态（如当前迭代次数、seed）保存至持久化文件或对象存储中。当训练因硬件/软件故障（如CUDA或NCCL API的运行时异常）需从checkpoint恢复时，系统需重启所有工作进程，从存储中加载checkpoint以初始化GPU和CPU状态，随后加载下一批训练数据，并从checkpoint对应的迭代继续训练。在分布式训练中，checkpoint的保存与加载更为复杂： 1. 数据并行场景： * 权重和优化器状态在GPU间复制，通常仅由主节点（如rank 0）保存全量状态； * 恢复时需在所有节点加载checkpoint。

高级并行策略场景（如DeepSpeed ZeRO、3D并行）：

模型参数和优化器状态被分片至各GPU，每个节点仅保存局部状态，生成分布式checkpoint；
优势：减少GPU状态到主机内存的拷贝开销，提升存储效率；
局限：假设恢复时需要使用相同的并行策略，导致跨配置恢复困难。

总结现有分布式checkpoint技术的不足：一是策略支持有限：仅支持数据并行或仅用于评估的权重转换；二是框架兼容性差：主流框架（如DeepSpeed、HuggingFace、PyTorch Lightning）都不支持跨并行策略恢复（例如从4路TP+4路PP切换至8路ZeRO-DP）。

Universal Checkpointing Design and Implementation

UCP Format: One Size Fits All

Distributed checkpointing challenges

提供UCP的挑战之一在于选择一种数据格式表示，使其能够轻松转换为不同GPU配置下的并行技术。为理解这一挑战，我们假设创建checkpoint时使用的并行技术为源（Source），而从源checkpoint恢复训练时选择的并行技术为目标（Target）。当系统使用多GPU时，源通常以分布式checkpoint的形式保存，即每个GPU保存其拥有的模型状态分片。这种设计的合理性在于：将分布式模型状态合并为单一checkpoint会显著拖慢训练速度，且在极端规模下不切实际。加载分布式checkpoint时，每个GPU加载其对应的checkpoint分片。然而，由于此类分布式checkpoint与训练运行的并行技术和硬件配置紧密耦合，它们无法在不同配置下使用（例如，当GPU数量或并行技术改变时，加载checkpoint会因名称或形状不匹配导致运行时错误）。若要将checkpoint直接从源适配到新的目标，需实现转换逻辑。然而，若存在N种分布式训练技术，每种技术有其独特的checkpoint保存与加载逻辑，则需要实现总计N×(N−1)个转换器以支持任意源到目标的转换，实现成本巨大。

Atom Checkpoints

为解决上述问题，UCP将通用checkpoint设计为原子checkpoint的集合。原子checkpoint是一种细粒度的持久化文件，包含以下内容： 1. 每个模型参数的完整表示（例如language_model.embedding.word_embeddings.weight）； 2. 元数据：用于将参数分片映射到任意分布式训练配置的训练节点。

以使用Adam优化器的训练为例，每个参数的原子checkpoint包含三个独立文件（如PyTorch的.pt文件）： 1. fp32.pt：存储FP32权重值； 2. exp_avg.pt：存储Adam优化器的一阶动量（均值）； 3. exp_avg_sq.pt：存储Adam优化器的二阶动量（方差）。

原子checkpoint的三大优势： 1. 解耦依赖：

原子化的checkpoint表示消除了分布式checkpoint与特定并行技术及硬件配置的耦合性。因此，无需为每对源到目标单独实现转换器。相反，UCP可作为不同分布式训练技术间的通用交换格式（如下图所示），从而轻松转换为其他分布式训练策略。
通过保留每个模型参数的完整表示，UCP支持按参数粒度灵活拆分和映射模型状态（或分片状态）到不同GPU，显著减少加载大模型checkpoint所需的工作内存。

按需惰性转换：

UCP转换仅在检测到并行技术或硬件配置变化时触发（例如训练过程中动态调整资源）。
现有分布式checkpoint保存逻辑无需修改，且UCP不会对正常分布式训练流程引入额外开销。

高级训练技术的兼容性：

UCP的结构天然支持分布式训练中的高级技术（如混合精度训练）。实践中，研究者可能需要在FP16和BF16混合精度训练之间切换。通过保留FP32权重和优化器值，训练可以灵活选择以FP16或BF16精度恢复。

UCP Language:"In-the-Box" Transformation

尽管UCP为不同并行策略提供了统一接口，但将任意分布式checkpoint转换为UCP格式仍可能面临较高的工程实现成本。这是因为在分布式训练中，每个GPU会调用持久化方法（如PyTorch的torch.save()）将其拥有的模型状态保存为checkpoint文件，而不同并行技术生成的checkpoint内容存在显著差异。为解决这一问题，UCP引入了UCP语言——一种简洁但强大的规范语言，用于将各类分布式checkpoint转换为上一章所提到的通用格式。其实现方式如下：

声明式系统与预定义参数模式：覆盖广泛的模型状态并行策略；
通用转换操作符：简化分布式checkpoint到原子checkpoint的转换。

如上图所示，当需要新的目标（Target）并行技术或硬件配置变更时，UCP语言被触发。其工作流程分为两步： 1. 转换阶段：将分布式checkpoint转换为UCP格式； 2. 加载阶段：基于目标并行技术和新硬件配置加载UCP checkpoint。

参数模式	含义
unique_params	参数唯一关联于某一GPU等级（常见于ZeRO-1/2和流水线并行）
replicated_params	参数在多个GPU间复制
fragment_params	参数需沿特定维度分片（例如张量并行中的行向或列向分片）
params_to_average	参数在各GPU上独立更新（需恢复时进行平均）

上表展示了UCP的参数模式，并且UCP语言的参数模式具有高度可扩展性，可轻松支持新的分布式训练模式。例如，用户可添加名为params_to_average的模式，表示参数在各GPU独立更新。

一旦识别出参数的模式，UCP会提供一组转换操作，帮助分布式检查点到UCP格式的转换，包括： * Extract：从分布式检查点中提取参数状态，保存为独立文件； * Union：根据参数模式合并分片（例如沿维度拼接）； * StripPadding：去除合并后参数中的填充数据； * GenUcpMetadata：为目标策略生成分片元数据（如形状和位置信息）； * Load：按元数据将原子检查点加载至GPU。

下表详细解释了主要UCP操作。

操作名称	功能描述
Extract	对分布式检查点调用`Extract`，返回该检查点包含的参数状态列表，并将每个参数状态保存为独立文件。可在多个分布式检查点上并行调用。
Union	对参数状态列表调用`Union`，返回合并后的参数列表。根据参数模式，对每个参数执行模式特定的合并逻辑。支持参数级并行处理，并行度越高速度越快，但内存消耗越大。
StripPadding	对合并后的参数调用`StripPadding`，去除其中的填充数据。避免存储冗余填充状态，同时简化检查点加载逻辑。
GenUcpMetadata	基于新的目标策略，为每个原子检查点计算并生成分片元数据（如形状和位置信息），用于将参数映射到指定GPU节点。计算分片信息时会引入填充。
Load	根据目标策略的UCP分片元数据，将原子检查点加载到各GPU节点。利用DeepNVMe库实现接近NVMe存储设备峰值带宽的顺序读取。

这份伪代码则展示了UCP语言如何基于参数模式和操作实现不同参数模式的合并逻辑

Algorithm 1 Workflow of UCP Conversion
▷ Extract
    for checkpoint ckpt in checkpoint_list do in parallel
        for parameter p in ckpt do
            if PatternMatch(replicated_params, p) then
                continue
            else
                Save(p)
▷ Union
    for parameter p in parameter_list do in parallel
        {f p1, f p2, ..., f pn} ← all files name matches p
        Switch p
            case PatternMatch(replicated_params, p) then
                ucpp = f p1
            case PatternMatch (params_to_average, p) then
                ucpp = Sum(f p1, f p2, ..., f pn) / n
            case PatternMatch(fragment_params, p) then
                ucpp = Concat(f p1, f p2, ..., f pn)
            case PatternMatch(unique_params, p) then
                assert(n = 1)
                ucpp = f p1
        if hasPadding(p) then
            ucpp = StripPadding(ucpp)
        Save(ucpp)

ZeRO Stage 3

ZeRO-3对模型权重和优化器状态都进行了分片。在保存ZeRO-3 checkpoint时，每个DP rank会将其拥有的分片参数和优化器状态保存到检查点。 UCP应用于ZeRO-3的过程如下图所示。 1. 首先使用UCP语言识别 ZeRO-3 的参数模式：ZeRO-3分布式checkpoint中的参数包含参数和优化器状态片段 (fragment_params)。 2. 基于该模式，UCP对分片参数运行Extract和Union操作，以创建原子检查点，其中包含合并后的参数及其优化器状态。 3. UCP会移除为硬件对齐添加的填充，并将原子检查点保存到持久文件中。 4. 恢复ZeRO-3训练时，每个GPU都会通过GenUcpMetadata计算其新的分区元数据，然后按照层顺序依次加载参数片段和优化器状态，并添加硬件对齐填充以实现高性能。加载完成后，会将更新后的扁平化内存属性（如 fp32_partitioned_groups_flat）广播至其他必要属性（如混合精度训练的 fp16_partitioned_groups_flat）

3D parallelism

3D并行是一种常见的分布式训练策略，它通过流水线并行（PP）水平切片模型 + 张量切片并行（TP）垂直切片模型，在保存检查点时，每个GPU仅存储其拥有的模型状态切片。 UCP语言识别了3D并行的参数模式，然后执行以下的步骤： 1. 模式识别：
- TP 并行度 >1：参数可能为 replicated_params, fragment_params, params_to_average；
- PP 并行度 >1：参数为 replicated_params；
2. 转换操作：
- 执行 Extract + Union → 按模式合并参数，生成去填充的原子检查点；
- 比如：TP采用行列分片 → 合并时需沿特定维度拼接为完整张量；
3. 恢复训练：
- 生成原子检查点与GPU节点的新映射关系；
- 各节点按新映射策略从原子检查点加载数据。

需要注意的是，其中一些模式（例如 fragment_params）包含具有额外形状和分区维度信息的子模式，以处理更复杂的检查点，上图右侧展示了两个示例。 1. MoE 模型示例：
- FFN 层权重张量形状为 [n_experts × hidden_out, hidden_in]；
- TP 分片沿 hidden_out 维度 → 子模式识别为三维张量并指定分片维度；
2. GQA示例：
- QKV 矩阵尺寸不同但合并为单一张量 [q_size + k_size + v_size, hidden]；
- TP 分片沿第一维度（Q/K/V 尺寸不同）→ 子模式识别变长分片并自适应处理。

UCP具有很强的可扩展性，允许用户轻松定义新的子模式来整合参数。

Conclusion and Future Work

文章提出了通用checkpoint (UCP)，作为一种灵活高效的checkpoint机制，可用于从分布式checkpoint恢复训练，并支持不同的分布式训练技术和硬件配置。UCP提供了一种通用的数据表示，可以轻松映射不同的分布式训练策略，包括ZeRO风格的数据并行、3D并行和序列并行。同时，UCP提供了UCP语言，这是一种简单而强大的规范语言，用于将分布式checkpoint转换为UCP格式。目前已经在 DeepSpeed库中实现了UCP，并证明UCP能够转换和加载具有不同并行策略和硬件配置的分布式检查点，而不会影响模型收敛性。与现有的分布式检查点相比，UCP不会增加额外的检查点保存开销，并且转换和加载UCP的开销极小。UCP的未来工作可能包括为新兴的并行策略添加可扩展模式，并进一步提高UCP的转换和加载效率。

MIT18-06S 2.3笔记

发表于 2023-11-08

MIT18_06S 2.3

Projection matrices and least squares

Projections

上一节我们了解到了矩阵可以把一个向量b投影到C(A)中。如果b垂直于C(A)，那么b就在A的left nullspace即中，并且。如果b本身就在C(A)里，那么，。

通常情况下，一个向量既含有在C(A)中的分量p，也含有垂直于C(A)的分量e，投影后e消失，只剩下p。

将b投影到A的左零空间的投影矩阵就是I-P：

Least squares

这里还是以一个最小二乘法的问题为例，解决点(1,1), (2,2), (3,2)的最佳拟合问题。我们想要找到这样的一条直线来拟合这三个点，这个过程就是线性回归，对于没有outliers的场景下是非常有效的。

最佳意味着这些点到拟合直线上的距离之和最小，即最小化。如果这条线能经过这三个点，那么就有：

但因为方程组无解，必然不存在这样的直线使得。

最小二乘有两种理解方式：

试图空间中的e1、e2 和 e3，即从数据点到线的垂直距离。
将b投影在A的列空间，投影结果为p，以及在 $的投影$ 。

上一章已经利用公式求解得C=2/3, D=1/2。

当然也可以利用微积分的方法去求解：

分别对C和D求导并令求导函数等于0，即可得到答案。

The matrix

如果A的列都是独立的，那么是可逆的（最小二乘法要求其必须是可逆的）。为了证明这一点，我们假设，然后证明x = 0一定为真：

因为A的列都是独立的，因此只有x=0才有。

MIT18-06S 2.2笔记

发表于 2023-11-03

MIT18_06S 2.2

Projections onto subspaces

Projections

这一章主要讲述子空间的投影情况，以一个二维的图为例（这里不画图了）。如果我们有一个向量b和一个向量a（2x1的向量）。假设b在a上的投影为p，这个p就位于与一条经过b并且与向量a正交的位置上，如果我们将 p 视为 b 的近似值，则 e = b − p的长度就是该近似值的误差。

由于p位于通过a的直线上，因此有 p = xa，这里x是一个常数；并且由于a垂直于e，就有

这里x的等式中，分子和分母都是标量，并且不能简单消除。这时就可以得到向量p的表达式了

由此可见，p跟b有着相关的关系，b的变化会影响p，而a则不会影响p。

此时可以将p进一步改写，写成这样一个形式，其中大写就是一个投影矩阵。

这说明向量b的在a上的投影p是一个矩阵作用在b上得到的，这个矩阵就是投影矩阵，这里分子就是一个2x2的矩阵。并由此得出两个性质：

后者的的几何意义是，对一个向量投影两次和投影一次相同。

Why project?

向量投影的意义需要从方程Ax=b讲起，以Ax=b为例，这个方程并不是任何时候都有解，向量Ax总是在A的列空间中，而b则很可能不在该列空间中。因此可以将b投影到 A 的列空间中的向量p上并求解Ax= p。

Projection in higher dimensions

以为例，要怎么将向量b投影到平面上的p点呢？

假设向量 $、$ 是平面的基，那么该平面就是矩阵的列空间。

从高维空间来看，这里的a就是矩阵，而x则是向量，投影，我们需要找到。误差向量垂直于列空间的平面，因此也垂直于该平面的所有向量。

误差向量e就属于的零空间，因为e与A的列空间垂直。

通过矩阵等式可以进一步化简：

因为A不一定是方阵，因此不能进一步化简，但可以看到的是，多维空间的投影矩阵同样满足

Least Squares

最小二乘法就是投影矩阵的应用之一，假设存在数据(1,1),(2,2),(3.2)，我们需要找到拟合b = C+Dt，这就等价于：

显然并不存在于一条线可以同时连接三个点，因此等式不可解，等我们可以求。此时可以算得C=2/3, D=1/2。

MIT18-06S 2.1笔记

发表于 2023-10-31

MIT18_06S 2.1

Orthogonal vectors and subspaces

本章主要讲向量、基和子空间正交的相关内容，核心内容是矩阵的行空间与其零空间正交，其列空间与其左零空间正交。

Orthogonal vectors

正交是垂直的另一种说法，如果两个向量之间的角度为90度，则它们是正交的。如果两个向量正交，则它们形成直角三角形，其斜边是向量之和。因此可以使用毕达哥拉斯定理来证明，当x和y正交时，点积的结果恰好为零。（长度平方）另外，所有向量都与零向量正交。

Orthogonal subspaces

子空间S与子空间T正交的定义：S中的每个向量都与T中的每个向量正交。

Nullspace is perpendicular to row space

矩阵的行空间与零空间正交，因为Ax = 0就意味着x与A的每一行的点积为0，x与A的任意行组合的乘积也必须为0。

同理，列空间与A的左零空间正交，因为的行空间垂直于的零空间。

实际上，矩阵的行空间和零空间将一个矩阵分解为两个互相垂直的子空间。比如，其行空间是一维的，基为，零空间则是维度为2的，与向量正交的平面。

零空间不仅与行空间正交，而且它们的维度加起来就是整个空间的维度，因此另一个说法就是零空间和行空间是中的正交补集。零空间包含垂直于行空间的所有向量，反之亦然。

其他

因为测量误差的存在，一般是不可解的，因为m > n（方程个数大于未知数）。因此需要找到一个“最优解"，就是关键，因为。这里还有两个关键定理：

只有在A的列都是不相关时（），才是可逆的。

举个例子：

这个例子就是可逆的。

MIT18-06S-1-11笔记

发表于 2023-10-19

MIT18_06S 1.11

这一章主要讲述任意允许加法和标量乘法的向量组成的向量空间。

New vector spaces

3 by 3 matrices

首先来看3x3的矩阵M，从这种矩阵可以得到三种子空间，分别是对称矩阵S，上三角矩阵S以及这两种矩阵的交集——对角矩阵的空间。M的维度是9，因为必须要选择9个数字来表示矩阵的9个位置，这就非常类似，其中基的选择可以是其中一个位置是1，其他位置都是0的3x3矩阵，一共有9个。

S的维度是6，S的元素主要是需要决定对角线的三个位置和右上角的三个位置。至于基的选择也是6个矩阵：

U的维度也是6，原因和基的选择与S类似，并且着恰好是M的基的子集。

D是S跟U的交集，因为它们基的交集恰好是3个，因此其维度也是3。

然而S跟U的并集却不是一个子空间，我们必须要对此进行填充，得到我们所说的和S + U。这是 M 的子空间。事实上，S + U = M。

Rank 4 matrices

现在考虑5 × 17的矩阵空间M，即使包含零矩阵，但包含所有4阶矩阵的M子集也不是子空间，因为两个 4 阶矩阵的和可能不具有 4 阶。

对于，所有满足的向量是一个子空间，它包含零向量，并且在加法和标量乘法下是闭环的。它是矩阵的零空间。因为A的秩为1，所以该零空间的维数为n − r = 3。该子空间具有特殊解的基：

列空间A为R1，左零空间仅包含零向量，维度为零，其基是空集。 A的行空间的维度也为 1。

Rank one matrices

矩阵的秩是其列（或行）空间的维数。矩阵的秩是1，因此其每一列都是前一列的倍数。

每个1阶矩阵A都可以写成，其中 U 和 V 是列向量。我们将使用 1 阶矩阵作为更复杂矩阵的构建块。

其他

本章还介绍了一些微分方程或者图论看作向量空间去考虑的内容，这里就不细说了。

MIT18-06S-1-10笔记

发表于 2023-10-10

MIT18_06S 1.10

The four fundamental subspaces

本章主要介绍一个矩阵A相关的四大子空间：

Column space：所有列向量组成的空间；
Nullspace：所有Ax=0的解所组成的空间；
RowSpace：行向量所组成的空间，即A转置后的Column space；
Left nullspace：A转置后的Nullspace；

Basis and Dimension

Column space：r个pivot columns构成了C(A)的基，dim C(A) = r；
Nullspace：Ax = 0的解，free variables的个数就等于纬度，dim N(A) = n - r；
Row space：；
Row space：；

New vector space

所有3×3矩阵的集合形成一个向量空间，称之为 M。我们可以将矩阵相加并将它们乘以标量，就得到了一个零矩阵（加法恒等式）。如果我们忽略矩阵相互相乘时，它们的行为就像向量一样。M的子空间包括了：

上三角矩阵；
对称矩阵；
对角矩阵；（对角矩阵就是上面两种矩阵的交集）

MIT18-06S-1-9笔记

发表于 2023-08-11

MIT18_06S 1.9

Independence, basis, and dimension

这一章主要讲了一些概念。

Linear independence

假设A是一个m x n的矩阵（m < n，Ax = b有着比等式更多未知数）。如果A至少有一个free variable，那么就会存在非零解使得Ax=0。那么A的列就是dependent。

如果两个向量不在同一条直线上，则它们是dependent。如果三向量不在同一平面上，则它们也是dependent。将Ax视为A列向量的线性组合，如果A的nullspace仅仅包含零向量，那么A的列向量independent。

如果A的列是independent，则所有列都是pivot列，A的rank为n，没有自由变量。如果A的列是dependent，则rank(A) < n。

Spanning a space

向量v1,v2,..,vn span成一个空间的意思就是，这个空间由这几个向量的任意线性组合组成。例如A的列向量组成了A的列空间。

Basis and dimension

一个向量空间的基(basic)就是一组符合如下特性的向量序列：

v1, ..., vd相互不相关（independent）；
v1, ..., vd可以span一个向量空间；

举个例子，，它们的的列线性无关，因为，只有当时才能成立。

然而矩阵的列向量就不能算是一组基，因为它们不满足线性不相关。基不能满足线性无关，并且组成的矩阵也是可逆的。

Basis for a subspace

和可以组成的一个平面但不能组成的一个基，换言之，一个空间的基都有着相等数量的向量，这个数也等于空间的维度。

Bases of a column space and nullspace

假设存在矩阵。

根据定义，A的四个列向量span A的列空间，其中第三和第四个列向量依赖于第一和第二列向量，前两列是独立的。因此，前两个列向量是主元列，它们构成列空间C(A)的basic。该矩阵的秩为 2。事实上，对于任何矩阵A都存在：

1	rank(A) = number of pivot columns of A = dimension of C(A).

这里矩阵A的列向量不是独立的，因此N(A)不仅仅包含零向量，所以存在

1	dimension of N(A) = number of free variables = n − r,

MIT18_06S 1.8笔记

发表于 2023-07-09

MIT18_06S 1.8笔记

Solving Ax = b: row reduced form R

这一节主要是解的问题。

Solvability conditions on b

我们还是用这个矩阵作为例子： A的第三行是其第一行和第二行的总和，因此我们知道，如果，则b的第三个元素应该等于第一和第二个元素的总和。如果b不满足，则等式无解。如果A的行组合算出零行，则b的元素组合也必须等于零。

确定是否可解的一种方法是对增广矩阵使用消元法。如果A中的一行被完全消除，则b中相应的条目也应被完全消除。在我们的示例中，A的第3行被完全消除了。为了使得这个例子有解，我们可以假设。

通过前面的学习，我们知道当b在列空间C(A) 中时，Ax = b就是可解的。事实上，这两种求可解性是等价的。

Complete solution

为了找到的所有解，我们首先检查方程是否可解，然后找到特定的解。通过将特定解添加到零空间中的所有向量，我们就能得到方程的完整解。

A particular solution

找到方程的特定解的一种方法是将所有free variables设置为零，然后求解pivot variables。对于前面示例矩阵A，令x2 = x4 = 0 得到方程组：最终可以求得一个特解。

Combined with the nullspace

因此的通解就可以通过给出，其中是零空间的通用向量，证明也比较简单：且，所以。前面我们也可求得的通解是和的线性组合。因此的全解就是：

Rank

矩阵的秩就是矩阵pivots的个数，如果A是秩为 r 的 m × n 矩阵，那么一定存在 r ≤ m 且 r ≤ n。此时，有0个或者无限个解。

Full column rank

如果 r = n，那么从前面知道零空间的维度为n − r = 0并且仅包含零向量，不存在自由变量或特殊解。如果有解，则该解是唯一的。我们知道 r ≤ m，因此如果 r = n，则矩阵的列数小于或等于行数，此时RREF就是，有1个或者0个解。

Full row rank

如果 r=m，RREF就是，没有零行，有n-m个free variables，有无限个解。

Full row and column rank

如果 r = m = n，则 A 是可逆方阵，RREF是单位矩阵。零空间的维度为零，并且有唯一的解。

LSM-based Storage Techniques: A survey

发表于 2023-07-03

LSM-based Storage Techniques: A survey

Introduction

随着LSM在NoSQL的应用越来越广泛，关于LSM的研究也变得越来越多。本文是一篇综述，主要目的是提供一些关于LSM存储技术的最优选择和前沿研究，并详细地介绍了相关技术对LSM系统的提高和权衡。

LSM-tree Basics

这一章主要是回顾了LSM树的背景，并深入讨论了LSM的基本结构。

History of LSM-trees

存储引擎主要分为两类结构：一是原地更新，如B+树等；另一个就是LSM树。前者对读和空间利用更友好，但牺牲了写的性能，至于后者则是对写更友好，但牺牲了读。非原地更新的结构在70年代就提出了，那时的做法就是将所有的写顺序地写到log文件里，但这种append-only logs的结构其读性能太差了，而且需要设计一个良好的逻辑去回收数据，做数据重组织。到了90年代，当下流行的LSM基本结构才逐渐成型，引入了多层结构，写memtable，实现了tiering merge策略等。

Today's LSM-trees

Basic Structure

这一章主要介绍了基本的LSM结构，现在的LSM实现仍然是非原地更新的方式从而尽量减少随机IO，所有的写入都会append到memory component中。disk components则是进行定期的合并然后生成新的component，而不会去修改现有。

通常来说会使用跳表或者B树去组织memory component，而disk component则是由B树或者sstable组成，一个sstable包含了多个data blocks和一个index block。对于LSM的查询来说，点查会从最新的component找到最旧的component，找到即返回，至于范围查询则需要所有层次的component都遍历一遍，丢到优先队列去归并。

最后则是介绍了下图所示的merge策略，主要分为两种：第一种是Leveling merge，每层只有一个component，然后下一层是当前层的T倍大小；另一种则是Tiering merge，每层最多T个components。前者对于查询更友好，后者则有利于写入。

Some Well-Known Optimizations

目前大多数LSM-tree实现都使用了两种比较流行的优化方法：一是bloom filter，它可以以非常节省空间的方式来判断集合成员的存在与否，它通常构建在磁盘组件之上，放在内存中，以极大地提高点查性能。

另一种则是Partitioning，LSM树的磁盘通常会被划分为多个小分区，对应到LevelDB就是sstable。这种划分方法可以限制每个合并操作的处理时间以及创建新sstable所需的临时磁盘空间，另一方面也可以避免因为顺序更新或者热点更新带来的负载，前者几乎不需要合并，而后者则不需要合并那些不涉及的小分区。如下图所示，leveldb的L0多个分区一般是具备重叠键范围的，这是因为这些分区是由memtable直接flush的。

Concurrency Control and Recovery

接下来主要讨论当今 LSM-tree 实现所使用的并发控制和恢复技术。对于并发控制，LSM-tree需要处理并发读取和写入并处理并发刷新和合并操作，这里确保并发读写的正确性是数据库系统中访问方法的基本要求。根据事务隔离要求，现在的 LSM-tree实现要么使用锁方案，要么使用多版本方案。后者天然适用于LSM树，因为在合并期间可以自然地对key的过时版本进行垃圾收集。对于恢复，则是使用WAL的方法，即先写日志再写memtable。

LSM-tree Improvements

A Taxonomy of LSM-tree Improvements

尽管LSM tree在NoSQL领域很受欢迎，但基本的设计仍然存在各种缺点和不足。一是写放大，包括leveldb、RocksDB等采用了水平合并策略，仍然会产生相对较高的写入放大。二是合并操作会对系统产生负面影响，包括合并后的缓冲区cache miss和大规模合并期间可能产生的写入停顿。三是如何充分利用硬件，早期的LSM-tree是为硬盘设计的。四是如何调整和定制基本的LSM树实现，以更好地应对特殊的工作负载。五则是Auto-Tuning，由于LSM-trees具备非常多可以调整的参数，需要对应不同的场景以实现最佳选择。六是二级索引，基本的LSM-tree只提供了简单的kv接口，如何在写入性能开销很小的情况下有效地维护一组相关的二级索引是非常值得探讨的。

Reducing Write Amplification

本节主要讲述为减少LSM树写入放大的改进。

Tiering

优化写入放大的一种方法是tiering的应用，因为它的写入放大比leveling低得多。文中提到了四种基于tiering进行的结构：

WriteBuffer (WB) Tree，这是一种具有垂直分组的partitioned tiering设计的变体，依靠hash-partitioning实现工作负载均衡，使得每个SSTable group存储接近数量的数据。此外，它将SSTable组组织成B+树的结构，实现自平衡以最小化总层数。
light-weight compaction tree (LWC-tree) ，采用了类似的partitioned tiering设计和垂直分组，SSTables不再是严格固定大小的，而是基于下一级重叠组的键范围而不是基于它们的大小生成的。
PebblesDB也采用了类似的设计，主要区别在于它使用受调表的启发，利用Guards思想来确定SSTable组的key范围。 Guards是SSTable组的key范围，这是根据插入的key概率选择的，从而实现工作负载平衡。一旦选择了一个Guard，它就会在下一次合并期间延迟应用。 PebblesDB进一步执行SSTables的并行查找以提高范围查询性能。
dCompaction则是引入了虚拟SSTables和虚拟合并的概念，以降低合并频率。虚拟合并操作会生成一个虚拟 SSTable，它只指向输入SSTable，但并不执行实际合并。

这四种结构都具有类似的基于partitioned tiering和垂直分组的高级设计，本质上都是用查询换取更低的写放大，它们的主要区别在于如何应付SSTable组的工作负载平衡。

Merge Skipping

skip-tree提出了一种合并跳过的想法来提高写入性能，如果可以实现将item跳过一些级别去合并，那么总的写入成本就会降低。如下图所示，在级别L的合并期间，skip-tree直接将一些key推送到可变的Level L+K的缓冲区，以便可以跳过一些逐级合并的层级。同时，可变缓冲区中跳过的item将在后续合并期间与Level L+K的SSTable合并。为确保正确性，只有当该key未出现在任何中间层才可以，这通过检查中间层级的布隆过滤器来满足条件是否成立。

Exploiting Data Skew

TRIAD的做法是在memtable中将热键与冷键分开，以便只有冷键被刷新到磁盘，因此当热键更新时，可以直接丢弃旧版本，而无需将它们写入磁盘。这个设计减少了一些热key频繁更新的倾斜更新工作负载带来的写入放大。热key是定期复制到新的事务日志中，以便回收旧的事务日志。另外TRIAD还通过延迟level 0的合并来减少写入放大，直到level 0包含多个 SSTable。最后还提出了一种优化，可避免在刷新后创建新的磁盘组件，相反直接在事务日志本身构建索引结构以提高查找性能。

Summary

Tiering已被广泛用于提高LSM树的写入性能，但这会降低查询性能和空间利用率。现有的基于Tiering的改进主要在 SSTable的管理方式上有所不同，通过垂直分组或水平分组来满足写入需求，另外skip-tree和TRIAD也提出了几个新的想法来提高写入性能。虽然这些改进都声称极大地提高LSM-tree的写入性能，但往往没有考虑LSM-tree的可调能力，因为他们都是与默认配置的LevelDB 或 RocksDB比较评估的。

Optimizing Merge Operations

Improving Merge Performance

在merge性能提升方面很多研究都提出了相应的设计方法，VT-tree提出了一种stitching的操作来提高性能，其基本思想是，在合并多个SSTable时，如果输入的SSTable中某个页面的key范围不与其他SSTable中的任何页面的key范围重叠，则该页面可以简单地被生成的SSTable指向，而无需读取和复制一遍。缺点是可能导致页面碎片和无法生成布隆过滤器。

还有一种思路如下图所示就是利用流水线优化，以更好地利用CPU和I/O并行性来提高合并性能，完整的合并操作包括了合并操作包含多个阶段，读取阶段、合并排序阶段和写入阶段。通过将其组合成流水线执行可以进一步加速合并。

Reducing Buffer Cache Misses

这一章主要是讲了由于sstable合并导致旧sstable删除引起的cache miss优化，文中提到的一个做法是用缓存预热的方法，将来自对旧sstable的查询平滑地重定向到新sstable。还有一种做法是将level L的就sstable，附加到与level L+1关联的缓冲区中，而不是立即删除，这些旧sstable也会被查询搜索以减少缓冲区缓存未命中，并根据访问频率逐渐删除它们。

Summary

这一章主要提出了一些关于优化合并操作的实现，包括写入性能、buffer cache命中率和write stall等。

Auto-Tuning

本章主要介绍了一些关于自动调整LSM参数的技术研究。

Parameter Tuning

有一些研究提出了一个分析模型，通过统计key的分布来改进LSM操作的成本估计，关键目标是如果能在合并早期就发现某个key被删除或者被更新，它就可以避免前面的合并，减少写放大。

还有一些研究是关于如何调整memtable与bloom filter之间的内存分配情况，以便找到特定工作负载最佳LSM设计，这里的一个关键是尽可能将Bloom filter的bit分配给低级别的sst table，最小化所有Bloom filter的误报率，从而最大化吞吐。

Conclusion

这一篇论文主要是一个综述文章，把最近的关于改进LSM tree的研究工作分别简单地介绍了下，如果有必要的话，最好是详细阅读其中的论文。

MIT18_06S 1.7笔记

发表于 2023-06-28

MIT18_06S 1.7笔记

这一章主要讲的是如何计算矩阵的nullspace

Computing the nullspace

假设要计算，并且存在矩阵A为：要计算上面的等式，还是继续使用消元法（因为右边是0，这里就不需要使用augmented matrix了），消元法中对于行的操作不会改变x的解，即nullspace，只会改变column space。操作步骤如下：矩阵U就呈现echelon form，第三行全是0，这是因为第三行是前面两行的线性组合。矩阵A的秩（rank）就等于2，即主元数量。

Special solutions

得到U之后，就可以通过代入找到x的解了，这里第一和第三列包含了主元，我们将其定义为pivot columns，其他的就是free columns。我们令 $、$ ，那么就可以求得 $、$ 。因此其中一个解就是。如果改一下free变量，就可以得到另一个解。A的nullspace就是所有解的线性组合。n-r(rank)就是nullspace的维数。

Reduced row echelon form

继续使用消除法可以将U转换为简化reduced row echelon form (rref form)的矩阵R，其中主元都等于1，而主元上方和下方均为零。通过交换一些列，R可以用左上角的单位矩阵的重写，后面可能是右侧的一些空闲列。如果A的某些行是线性相关的，则矩阵R下方的行将用零填充(I就是rank x rank的矩阵)：那么nullspace ，，N的每一列都是一个Special solution。

MLSYS论文阅读——Universal Checkpointing

Introduction

Background and Related Work

Universal Checkpointing Design and Implementation

UCP Format: One Size Fits All

UCP Language:"In-the-Box" Transformation

ZeRO Stage 3

3D parallelism

Conclusion and Future Work

MIT18_06S 2.3

Projection matrices and least squares

Projections

Least squares

The matrix

MIT18_06S 2.2

Projections onto subspaces

Projections

Why project?

Projection in higher dimensions

Least Squares

MIT18_06S 2.1

Orthogonal vectors and subspaces

Orthogonal vectors

Orthogonal subspaces

Nullspace is perpendicular to row space

其他

MIT18_06S 1.11

New vector spaces

3 by 3 matrices

Rank 4 matrices

Rank one matrices

其他

MIT18_06S 1.10

The four fundamental subspaces

Basis and Dimension

New vector space

MIT18_06S 1.9

Independence, basis, and dimension

Linear independence

Spanning a space

Basis and dimension

Basis for a subspace

Bases of a column space and nullspace

MIT18_06S 1.8笔记

Solving Ax = b: row reduced form R

Solvability conditions on b

Complete solution

A particular solution

Combined with the nullspace

Rank

Full column rank

Full row rank

Full row and column rank

LSM-based Storage Techniques: A survey

Introduction

LSM-tree Basics

History of LSM-trees

Today's LSM-trees

Basic Structure

Some Well-Known Optimizations

Concurrency Control and Recovery

LSM-tree Improvements

A Taxonomy of LSM-tree Improvements

Reducing Write Amplification

Tiering

Merge Skipping

Exploiting Data Skew

Summary

Optimizing Merge Operations

Improving Merge Performance

Reducing Buffer Cache Misses

Summary

Auto-Tuning

Parameter Tuning

Conclusion

MIT18_06S 1.7笔记

Computing the nullspace

Special solutions

Reduced row echelon form