https://www.cnblogs.com/opennaive/p/3312731.html

Abstract

主要提出了三个经过去重后解决碎片化问题的restore手段：increasing cache size, container capping, using a forward assembly area。

capping是一种在去重阶段减少碎片化但会导致去重率降低的技术，这个在之前我已经看到了代码

实现；

【回想一下capping的实现，也确实。

每次dedup一次处理的segment大小为20MB，容器固定大小为4MB。

我们通过capping技巧降低碎片化程度。在capping的实现中，我们记录所有涉及到去重的容器中所需去重块数，<container_id, chunk_num>，并且当涉及容器过多时会舍弃那些chunk_num小的不进行去重。

因为，chunk_num小，说明容器中有效块少，读放大率大，碎片化程度大，所以与其引用这些有效率小的容器，不如牺牲一下去重率，再把这些重复块copy一次。】

forward assembly是一种在restore时进行cache和prefetch的技术，并且通过算法优化减少了cache所需的RAM。

【这个东西好像也是老朋友了，也即recipe+cachechunk restore的实现原理】

思考1

感觉之后有必要再回忆一下代码实现和论文里看到的专业名词的差异了。

首先，总结一下论文中的流程。需要备份的应用先将backup转化为数据流，通过网络传输到deduplication app上。后者经过分块、去重、写回这几个流程，外加gc和restore两个辅助流程，实现了备份管理组织。

其中落实到具体算法，分块流程采用content-based chunk，在具体实现中是通过各种hash算法计算出fingerprint，从而实现对各个chunk的区分；去重阶段是通过一个全局指纹表，来判断chunk的重复；写回阶段，是根据去重的结果，将需要写回的chunks以顺序形式分割为一个个容器（容器体现为一个个文件），写回磁盘。【这也体现出为什么说IO单位是一个container了，你读磁盘确实一次就是一次性读一个文件的啊（）】

再落实到具体的优化策略：

  1. data layout

    去重结束后，会针对去重过程中收集到的块信息对数据布局进行适当的调整。

    对于MFDedup策略，GC过程较为简单，可能最主要在restore的时候需要访问数据布局；

    对于Odess，在GC中会根据二叉树进行数据块的迁移，保证每个叶子结点包含的chunks都大概率连续存储在连续的容器中，在restore时根据recipe进行恢复，从而无需访问数据布局。

  2. capping【经典rewrite技术，通过降低去重率来提高恢复速度】

    去重时，会根据容器的重复率进行capping，具体体现为造一个<cid, chunk_num>的map，根据这个map来进行容器的筛选。当涉及容器过多时会舍弃那些chunk_num小的不进行去重，从而限制一个备份版本能够使用的旧容器的最大数量FLAGS_CappingThreshold（每20MB）和新容器最大数量（不超过5个，因为20MB/4MB）。

    image-20231025221335792

    这段论述很精彩。要限制chunk碎片化，就是要限制restore过程中读取的容器数量；要限制restore涉及容器数量，就是要限制一个备份版本所涉及的所有容器数量；而所有容器数量中，我们能限制的就是这b最多能引用多少个旧容器。感觉这个逻辑链很完美。

    不过，为什么不像gc那样通过计算每个容器的活chunk比例呢，就像gc那样？而且实现也无需太复杂，毕竟容器大小都是固定的，所以比例只需计算map->second*chunk_sz/c_sz这样粗略即可，然后从尾到头（降序）进行逐一判断该比率即可。

    这点值得思考下。

  3. forward assembly

    在writeback时，每个备份版本都有一个对应的文件（logicFile）记录其meta data，根据chunk的不同类型（dedup or unique）对其进行记录。然后之后在恢复过程中，遍历此logic file，就可以做到“预先得知需要取的容器”，【而且在具体实现中，是通过cid从小到大进行容器遍历的，因为cid连续表明文件创建连续表明磁盘连续】从而借助cache进行乱序恢复就行。

    Odess由于预先根据二叉树进行了组织，所以在恢复过程中recipe涉及到的容器数会更少，读放大会更小。

Design

这部分具体来说，就是详细介绍了capping和forward assembly area的运作方法。

  1. capping

    capping的实现写法很容易理解，没什么好说的，但重要的是其思想精髓。我们的目的是防止备份碎片化，从而影响restore速率，保证读放大小。那么，为了保证读放大小，我们自然而然想到应该尽可能减少涉及到的容器个数（想想读放大计算公式），这也就是capping的核心思想：限制容器数量。

    每个segment的新容器数量被限制在1~5范围内，旧容器数量由一个参数规定。

  2. foward assembly area

    经典的LRU cache每次读入一整个容器，对一整个容器进行lru；这玩意每次读一个容器，仅保留容器中需要的chunks，会把容器其他部分释放

    这个相比起来有些复杂，并且跟以前看到的好像也不大一样，它大概更像是一个restore技术。在整个pipeline中，我们记录下recipe表。然后在恢复过程中，我们申请一块foward assembly area，每次读取一段recipe，然后根据recipe读取容器，并将所需chunks写入这块area中，若area开头有一段continuous的chunks，则写入文件，移动指针。

    其中area以循环队列形式出现。这个也很容易理解，这个东西听起来就很循环。

    fixed和rolling的区别可能是这样的。假设cache固定为1，也即一次只读入一个容器。fixed每次读取固定数量的recipe，然后全恢复完了再写回，恢复该段期间不读recipe；rolling的话就是每次读入一个container，就把前面continuous的部分写回，然后写回多少chunk就再继续读多少recipe，从而实现滚动。

思考2

码的，遇到了一个很严重的没想过的问题。。。

在论文中，那个recipe恢复的原理是一次读取固定大小，然后针对固定大小的地方进行随机恢复。但是我目前的写法的话需要进行多次的fseek，我就很害怕会导致每次fseek跨越很大。

但是，在实际测试中，我发现针对于cid、offset升序的情况，似乎这样得到的offset序列也是稳定升序的：

image-20231027101550605

并且经计算，非升序的仅占7%，并且平均seek跨越为23459150.000000。可以看到，这个数字还是比较resonable的，那么这玩意是不是gc的功劳呢？

测试需要等得久一些，不妨就先只从理论上来分析为什么这个GC算法可以让cid相邻的容器在文件中的位置也是稳定升序的。

好像仔细一想也确实，因为你看，你一个个segment处理是顺序的，所以你一个个chunks加入到chunks_to_add也是顺序的，这样就保证了内部升序，那么容器间升序是怎么做到的？额我怎么知道。。。这个好像更像数据内部特征了，与gc无瓜。

image-20231027103752642

确实，换了个数据集马上就寄了哎。而且看数据感觉能看得出来这b在不同容器间确实是反复横跳的。所以fseek的问题确实存在。

不过，我仔细想了想，感觉使用fseek跟它那啥玩意似乎各有优劣。

fseek：

  1. 优点
    1. 代码简单
    2. 一个container只用io一次
  2. 缺点
    1. 会反复横跳文件多个位置，并且这个横跳开销较大，我看到甚至好几次都跨度甚至达到g水平，有个2g和1g之类的

那啥玩意：

  1. 优点
    1. 不会发生横跳情况
  2. 缺点
    1. 一个container需要io多次，但是container io的seek部分应该跨度较小

等看完论文问一下两位学长吧，就问我简单粗暴用的那个seek开销会不会太大了，说明下发现测试数据中有跨度2g版本。

其实感觉也没必要了，毕竟最后测出来速度就是seek那个最牛逼。这可能也说明最主要开销还是容器重复IO罢。

草，感觉这里在说XX（）因为我们自始至终恢复都是直接恢复进RAM或者SSD的hhhh所以seek自然不是问题了

evaluation

文章中的评估方法这部分介绍得很详细，很适合菜鸡如我感受一下它的这个流程。

dataset

  1. workgroup dataset：

    There are 154 fulls and 392 incrementals in this 3.8 TB collection, with the fulls ranging from 3 GB to 56 GB, with a mean size of 21 GB.

    模型是：每天一增量，每周一全量的备份日程。使用TTTD技术进行chunk处理。

  2. 2-year dataset

    HPstorage提供（工业界），synthetic data set合成数据集，高度碎片化。

    一开始是一个10GB的文件系统快照，每几天就会随机选择2%的文件，并且synthetically（综合地）改变每个文件中10%的内容，并且增加200MB新文件。

    During each simulated week, one full backup and four incremental backups, one for each other weekday, are taken via uncompressed tar for a total of 480 backups covering 96 simulated weeks (1.9 years).

    每周有1个全备份和4个增量备份，每天的备份都是以未压缩的tar形式存在，然后一共进行2 year，也即一共有480个backup、96个模拟周。

    依然使用TTTD技术进行chunk处理。

由于备份数量还是太多，所以在实际中应该是不可能保留所有这些备份的，而是会保留一定数量。所以，我们设置每个备份只被保留30天，也即在备份第n个backup时删除第n-30个backup。【当然，尝试了别的schedule发现了不会影响结果】

此处介绍常见的备份轮换（Backup rotation scheme）算法（from wiki）：

  1. Grandfather-Father-Son (GFS)

    这是一种经典的备份轮换方案，通常包括每日、每周和每月备份。每日备份称为“儿子”（Son），每周备份称为“父亲”（Father），每月备份称为“祖父”（Grandfather）。

    儿子备份按照FIFO系统进行3个月的轮换。父亲备份类似地按照每两年的周期进行轮换，而祖父备份则按照每年的周期进行轮换。

  2. Tower of Hanoi：多级备份。例如，第一级备份可能是每天一次，第二级是每周一次，第三级是每月一次，以此类推。

    感觉这个用了汉诺塔原理的备份轮换算法还挺有意思的，之后学习下汉诺塔是啥玩意，然后再来看看这个算法简介。

  3. Weekly Rotation：每周备份轮换，保留过去几周的备份。

  4. Daily Rotation：每日备份轮换，保留过去几天的备份。

baseline

LRU caching, no capping

这个部分大概就是针对no capping的普通LRU，对两个数据集，测了随着cache增大而变化的speed factor、读放大这俩指标。

image-20231027221346694

可以看到图标是备份版本，纵轴是speed factor，横轴是cache大小。

然后根据线性回归算法说明了下碎片化程度与备份层级增多为线性强正相关，因而这也就说明，增加一倍的备份就会使restore速度double。

然后再说明了一下这两个数据集碎片化变化趋势不同，是因为碎片化程度可以被看做多个影响因素一维向量叠加后的成果，而不是一个固定的标量。

image-20231028220214261

capping

通过数据表示了capping后放弃的去重比率和速度提升倍数的关系。缓存越大，提升越有限，所以需要放弃更大比例的去重才能获取同样的效果。

image-20231027223619971

也表明了与碎片化的关系：

image-20231027223837565

不过为啥2year还能超过100%的？

这个则是体现了，去重率越低（rewrite越多）恢复速度越快，并且缓存越大越快。并且要注意segment大小需要适中。

image-20231027224435204

那么，此处为什么改变segment的大小，会影响capping效果，就值得思考。

假设cache足够大。首先，segment的大小不会影响capping的比率。所以我们需要从容器分布的角度来理解。由于segment只能体现局部性质，那么当一个容器在当前segment分布稀疏（导致被capping，从而其引用数据块的references从此被改变到新容器），而在之后的其他segment又密集，就会导致我们不大精准地rewrite了那部分数据。而当segment越大，我们的视野就越大，判断也会越精准，从而再次减小读放大，从而提高性能。

至于为什么当cache为128MB时，segment越大反而会起反效果呢？作者解释说，这是因为，去重过程中以S为segment大小相当于restore过程中以S为forward assembly area大小，而area越大，就必须得要有一个更大更充分的cache。那么如果当S接近于或大于cache size，LRU换入换出就会频繁，也就没半毛钱好处了。

assembly

RAM used for LRU is simply the number of container slots in the cache times the container size (4 MB). For the forward assembly area methods, it is the size of the forward assembly area.

对于LRU来说，RAM大小指的是它的LRU列表元素个数*容器大小这个值；对于faa来说，RAM大小指的是forward assembly area的大小。

在odes中，chunkcache的大小为128*4MB=512MB，应该是用的整块整块读的LRU算法

image-20231027232135327

可以看到，在有限RAM的情况下，改进的restore算法相比于LRU有极大提升，且rolling猛于fixed。

capping & assembly

首先一开始大概说了下容器大小的影响，这个测试部分做得确实很完善：

image-20231028132153808

在存储领域中，backup ingestion是什么意思

在存储领域中，”backup ingestion” 指的是备份摄取或备份导入的过程。这一阶段涉及将备份数据从源存储系统传输或复制到备份系统中，以确保数据的安全存储和管理。这个过程可能包括数据传输、数据转换、压缩、加密等步骤，确保备份数据能够有效地存储和恢复。

意思是说deduplication是在这个过程进行的吗

是的，通常在备份摄取（backup ingestion）的过程中，会应用去重（deduplication）技术。去重的目标是识别和消除备份数据中的重复块，以节省存储空间并提高备份效率。在备份数据传输到备份系统之前或之后，去重过程可以帮助减少存储需求，降低备份存储的成本，并加速备份和恢复操作。

提到了个sparce indexing，感觉有必要先去看看mfdedup的indexing方法。

在看之前，可以先稍微回忆下你现在理解的indexing是什么。回忆一下去重过程，本质上就是对到来的数据流进行重复检测，不重复则写入新的container，重复则找到以前重复块的位置进行引用。其中这个“重复检测”我想就是indexing的工作。具体而言，它应该是一张表的形式，记录着每个chunk的fp及其所处的位置。那么，将它存储在哪，以及如何对它进行快速查找，这就是我们需要考虑的。

在Odess实现中，提供了两种存储这个indexing table的形式。一个是存储在内存，另一个是通过RocksDB存储在磁盘中。

对于sparce indexing，它大概思想就是每次只抽样查询部分的indexing table来判断去重。

sparce indexing：

一般来说，基于chunks的去重都要求使用full index，而这RAM一般承受不起，但是纯用disk io就太慢了。所以它采取了一招：

  1. 将input stream划分为多个segment，每个segment仅与它最接近的之前的某个segment进行去重，也即只需对那个被选中的抽样segment进行index构建。

  2. 为了找到最接近的segment，使用了sampling（抽样）和sparce indexing。

    1. samples： We choose a small portion of the chunks in the stream as samples; samples是一些chunks。

    2. sparce indexing：Our sparse index maps these samples to the existing segments in which they occur.也就是<fp, segment_id>

  3. 避免了full index，而只有sampled chunks的fp被保留在RAM中。

它所用的数据局部性：

If two pieces of backup streams share any chunks, they are likely to share many chunks. 如果两个segment共享了某个chunk，那么它们很有可能共享很多chunks。

也就是说，它是这样的流程：

  1. 以segment为单位读取input stream；
  2. 计算该segment的每个chunk的fp，然后对每个chunk查询sparce indexing table: <fp, segment_id>，记录所需读取的segment_id；
  3. 读取这些segment_id对应的segment的chunk indexing table（存储在disk中）；
  4. for every chunks： 重复，copy entry ；不重复，add to new container
  5. 最后再将该segment的信息写入磁盘，填写sparce indexing表。

而sparce indexing表最一开始，由对input segment进行chunks的随机抽样得出（或者逐渐构建起来，反正大概是这个意思）

可以看到，它将segment info保留在disk中，在RAM中只保留fp2seg_id的映射，每次只需简单从磁盘中读取几个segment info即可，利用数据局部性极大地降低了磁盘IO次数。

然后我猜测估计mfdedup的indexing就是只保留neighborhood的indexing，也是类似的意思。

这个sparce indexing的好处除了有节省RAM之外，还有一个减少碎片化（因为每次只从受限个数的segment中进行去重，resonable）

我们对其算法进行了一定修改：将sparce indexing从原来的<fp, seg_id>改为<fp, cid>，并且每次只取top T个包含sample chunks最多的容器，从而将对segment进行cap修改为对container进行cap。仔细想想，这样确实依然保证了原算法的核心思想，也属于是segment size = container size的特种了。

草，不过这个<fp, cid>不就是Odess中的recipe（或者说是全局指纹表）吗？乐。Odess也确实体现了这种capping+sparce indexing结合的方法【只不过进行简化了，每个chunk固定取其第一个container】，只能说不愧是落地实现，处处映射。

future works

我们目前这玩意还是有缺点，就是它只是针对局部的segment进行capping，可能就使优化效果不是那么绝对。所以我们提出了两个解决方法：

  1. adaptive capping

    令当前的capping level根据recent segment的container nums进行调整，也许可以理解为再给这个recent seg的<cid, nums>信息进行一个FIFO，从而将局部视角扩展到略微全局平均一点的视角。

    这个会在那些unevenly fragment的备份中起到更好的优化作用。【至于为什么，可以回忆下我之前说的那个在一些部分被稀疏引用、在一些部分被密集引用的那个例子。具体大概在evaluation-capping那个部分。】

  2. 只记录recent segment中是否被使用，而不记录具体使用情况（如次数）

    We hope this will give us the same performance as using a larger segment size without actually needing to increase our segment buffer space.

    这也是我之前提到的，当cache足够大，segment理论上是越大越好的，因为这样就会有全局视角。

related works

  1. CBR

    CBR和Capping的思想极为相似。

    CBR：当且仅当某个容器包含该段至少T个块时，才会dedup该容器在该段中的chunks。并且这个T是会adaptive的。

    听起来简直和capping一模一样，只不过确实如blog所说capping更注重限制容器个数，从而获取读性能；CBR更注重限制rewrite比率。而且由于T的adaptive，CBR很有可能unbound，也即万一T=1那么碎片化问题无法缓解。

总结

精炼一下看完这篇论文后我的收获。

  1. design

    首先是对论文提出算法的理解。

    论文提出的最有用的应该就是capping这个rewrite技术。它的核心思想是将input stream划分为定长segment（通常20MB），通过限制每个segment的容器数量（重复chunks所在容器数、新容器数（不超过5个）），对部分chunks进行deny dedup重写，从而减少restore过程的读放大。

  2. evaluation

    然后就是论文中写得很好的evaluation部分了。它主要从以下这几个方面进行了全方位的性能评估：baseline、only capping、only assembly、capping+assembly。

    1. 测试指标：containers read per MB restored（读放大）、speed factor（1/读放大）、cumulative deduplication factor（累积去重率）、relative loss of cumulative deduplication factor（放弃的去重比率）、缓存大小

    2. dataset：介绍了两个经典data set，很值得看看，体会下practical的备份场景是什么样的。

    3. baseline：由于我们之后的几个实验都需要测试缓存大小对restore相关指标的影响，所以在一开始首先测试基准情况下随缓存大小的指标变化。

      基准情况：no capping， no assembly； use LRU cache to restore

      指标：containers read per MB restored && speed factor 随备份版本号变化，with different cache size

    4. capping：

      指标：cumulative deduplication factor和speed factor的关系、relative去重率和relative速度的关系；with different cache size and segment size

      重点体现了capping在降低去重率和提升restore速率之间的平衡；以及测试了capping相关指标（segment size）对capping的影响。

    5. assembly：

      指标：与baseline进行speed factor的对比测试；with different cache size

    6. both

      没什么好说的，体现了下container size的影响。

总的来说，是一篇测试很完善、rewrite很经典的文章，让本垃圾入门者也能轻易get到的好文。