写在开始
在这里，对 J Wires 等人的论文《Characterizing StorageWorkloads with Counter Stacks》(2014年)[1]做个简要的笔记。不足之处还请在评论区指出。
目录
1 简述
2 问题
3 方法
3.1 理想计数器堆栈
3.2 实际计数器堆栈
3.3计数器堆栈API
4 实验结果
5 其他
5.1 创新点
5.2 优缺点
参考文献
1 简述
目前(2014年)大部分用于确定工作负载大小以及跟踪负载活动的方法是基于缺失率曲线(Miss Ratio Curves, MRCs)。但这些方法都存在一个很重要的问题，就是存在较大的内存开销，这就导致它们不适合存储工作负载。[1]基于概率计数器提出了一种新的数据结构——计数器堆栈，它能够产生近似的MRCs。通过工作负载跟踪生成计数器堆栈流，再从堆栈流中计算堆栈距离(重用距离)，最后生成MRCs。计数器堆栈能够生成比完整跟踪小许多数量级的工作负载表示，并且能够描述在任意窗口上实时估计任意工作负载组合的MRCs。使用计数器堆栈能够准确地描述以及存储工作负载。概率计数器、下采样以及剪枝能够确保在计算过程中使用较少的内存空间，确保用于存储工作负载的磁盘空间较少。堆栈距离的计算确保能够快速地生成MRCs。在计数器堆栈API中，能够通过计算查询以及时间切片来识别不稳定的工作负载，说明了在不同的时间间隔内考虑MRCs十分重要，特别是对于长时间的工作负载。计数器堆栈中的时移功能为研究工作负载的粗粒度调度提供了一个强大的工具。[1]展示了计数器堆栈的在线分析功能如何提供对实时工作负载的有价值的洞察。
2 问题
首先，现有的(2014年)基于MRCs确定工作负载大小的技术存在较大的内存开销，这使得这些技术不适合大规模的存储工作负载。
其次，到目前为止(2014年)，由于存储工作负载的大小很大，导致计算它们的工作集的成本很高。matson的原始堆栈算法需要O(NM)的时间复杂度和O(M)的空间复杂度来跟踪N个请求和M个惟一元素。使用堆栈平衡树保持距离方法来进行优化，时间复杂度降低到O (NlogM)。
最后，存储工作负载持续时间的延长导致了在推理该工作集时的细微差别。CPU工作负载相对较短，在许多情况下，只要考虑它们在小时间间隔内的工作集(例如调度周期)就足够了。另一方面，存储工作负载可能跨越几周或几个月，并且随着时间的推移可能发生显著变化。这种规模的MRCs可能比较棘手：如果它们包含的历史记录太少，就可能无法捕获重要的重复模式，但是如果它们包含的历史记录太多，就可能严重歪曲最近的行为。存储工作负载位于文件系统缓存之后，因此通常比CPU工作负载显示更长的重用距离，这进一步加剧了这种现象。因此，存储工作负载中的缓存丢失对命中率的影响可能比CPU缓存丢失更明显，因为后续的重新访问很可能被文件系统缓存吸收，而不是在存储层造成命中。这意味着MRC分析需要在不同的时间间隔内执行，才能在存储领域有效。工作负载过去一小时的MRC可能与过去一天的MRC有显著差异；这两个数据点都是有用的，但都不能单独提供完整的情况。
J Wires基于对以上三个问题的考虑，提出了计数器堆栈结构。
3 方法
3.1 理想计数器堆栈
计数器堆栈是在处理跟踪时更新的内存中的数据结构。它捕获地址空间中访问序列的位置属性。对于存储系统来说，访问通常是对物理磁盘、逻辑卷或单个文件的读或写请求。计数器堆栈的目的是以一种高效计算和存储的形式表示请求流，并保留足够的信息来描述工作负载。
计数器堆栈维护一个计数器列表，这些计数器在处理跟踪时定期实例化。每个计数器记录自该计数器创建以来观察到的唯一微量元素的数量，这将捕获跟踪对应部分上的工作集的大小。
在每个时间步骤中，计数器堆栈可以报告一个值列表，其中给出在当前时间和之前所有时间点之间请求的不同块的数量。这种数据结构会随着时间的推移而发展，因此可以方便地将其历史显示为矩阵C，其中每一列记录计数器堆栈在某个时间点报告的值。该矩阵的第j列给出了第j步计数器堆栈报告的值，即，表示从那时到以前所有时间请求的不同块的数量。矩阵的第i行可以看作是由在第i步实例化的计数器生成的值序列。在每个时间步骤中，将计数器堆栈报告的值的当前列写入磁盘。这可以看作是检查点，或者增量更新矩阵的磁盘表示。这种磁盘上的表示称为计数器堆栈流。
给定请求的堆栈距离是自上次引用被请求元素以来观察到的不同元素的数量。因为计数器堆栈存储关于不同元素的信息，所以确定堆栈距离很简单。对于时间步骤j，找到被请求元素的上一个位置，假设是迹i，然后检查矩阵的条目，以确定在i和j之间请求的不同元素的数量，即为堆栈距离。
3.2 实际计数器堆栈
理想计数器堆栈流存储整个矩阵C，因此它需要跟踪长度为二次的空间。这实际上比存储原始跟踪更昂贵。在现实世界中，存储工作负载在短时间内可能不会有较明显的改动，因此原始矩阵C有很大的冗余。所以，在空间开销和准确度之间进行权衡。在实际计数器堆栈中，采用了概率计数器、下采样（降低时间分辨率）、剪枝来极大地减少计数器堆栈和流的空间。
3.2.1 概率计数器
内存计数器堆栈有一个挑战它必须能够在处理跟踪时更新这些计数，因此每个计数器必须保留它所看到的信息。如果让每个计数器显式地表示这个集合，就需要二次内存使用，所占的内存空间非常大。概率计数器占用的空间非常小，并且保证了准确性。实际计数器堆栈使用的是HyperLogLog计数器，一种概率计数器，用于统计某一字段的不同值得个数，即基数。它使用固定大小的字节计算任意大小的基数。
3.2.2 下采样
降低时间分辨率相当于只保留一个很小的C的子矩阵。该子矩阵提供了足够的数据，并且具有足够的准确性，可以用于应用程序。例如，在跟踪工作负载请求时，每第d个时间步骤启动一个新的计数器；这相当于只保留矩阵C的每d行的一行。接下来，只能在跟踪中的每第d个时间步骤更新计数器；这相当于只保留矩阵C的每d列的一列。这个过程称为下采样。下采样的效果如图1所示。图1(a)为原始矩阵C，图1(b)为下采样之后的矩阵。
原始矩阵C的相邻条目可以只有1不同，所以下采样矩阵中的相邻条目只有d可以不同。因此，在下采样矩阵中，缺失的任何条目都可以使用当前附近的条目来估计，误差最大为d。对于具有数十亿个不同元素的大规模工作负载，即使选择一个非常大的d值，对估计堆栈距离和MRCs的影响也可以忽略不计。
3.2.3 剪枝
当计数器之间的差异足够小时，较新的计数器提供的附加信息可以忽略不计。在这种情况下，可以删除较新的计数器，其值可以通过引用较老的计数器来近似估计。此过程称为剪枝。
论文[1]中使用的剪枝策略是只要较年轻的计数器的值至少是旧计数器值的倍，就删除它。该策略可确保当前时间步中，活动的计数器数量最多为
(M是整个跟踪中不同块的数量)。论文[1]中关于实现计数器方法的实验中，使用了参数
。剪枝的效果如图2所示。图2(a)为剪枝之前的矩阵，图2(b)为剪枝之后的矩阵。
3.3 计数器堆栈API
论文[1]构造一个实际的能够实施的系统。该系统是一个灵活的，内存有效的库，可用于处理跟踪，生成计数器堆栈流以及对这些流执行查询。使用该库的应用程序的工作流程如图3所示。使用CstackStreamWriter将请求或者跟踪转化为计数器堆栈流。通过周期性地输出矩阵的新列来产生输出的流。每列都以稀疏格式写入磁盘。计数器堆栈API支持切片、移位和连接操作。切片是指在特定时间间隔内只分析给定迹的子集。时移是指以恒定的时间间隔，连接迹线来改变时间特征。连接是指对于给定的两个或更多工作负载，将它们组合到单个工作负载中，观察将会导致的行为。计数器堆栈API提供了三种查询功能，即查询请求的数量、不同请求的数量以及MRCs曲线。
4 实验结果
在这里，从空间，时间开销以及准确性两方面给出论文中具有代表性的结果。
4.1 空间、时间开销
所提出的CS方法(低保真流和高保真流)与Mattson算法进行时间和空间开销比较。如图4所示。可以看出，使用CS方法，所用的内存不超过90MB，存储空间不超过11MB，而Masstion需要92GB的内存，2.9GB的存储空间。从吞吐量来看，CS方法更快。
4.2 准确性
所提出的CS方法(低保真流和高保真流)与Mattson算法进行比较，如图5所示。可以看出，高保真度的准确性相对于低保真度更高一点。而且，三条曲线几乎重合，仅仅在最初的时候有细微的差别。这表明CS方法具有足够的准确度。详细实验请参考论文[1]。
5 其他
5.1 创新点
论文[1]的创新点有：
1)提出了一种利用计数器堆栈估计失效率曲线的新技术，并对该技术的性能和精度进行了评估；
2)展示如何定期检查计数器堆栈并将其流到磁盘，以提供存储工作负载的高度压缩表示；
3)提供处理多个独立计数器堆栈的技术，以便估计新工作负载组合的MRCs。计数器堆栈API提供了切片、移位和连接功能，支持在任意窗口上实时计算任意工作负载组合的MRCs。这些功能扩展了MRC分析的功能，并提供了对实时工作负载的有价值的洞察。
5.2 优缺点
论文[1]所提出的方法优点有：
1)准确性，即使用计数器堆栈得到的MRCs足够准确。；
2)快速性。
论文[1]所提出的方法缺点有：
1) 存在误差
论文[1]中的实际计数器堆栈使用的是HyperLogLog计数器。HyperLogLog是一种概率计数器。它以两种方式引入错误：计数估计和寄存器同时更新。HyperLogLog计数器报告不同元素的计数，该计数只能精确到乘法因子ε，该因子由一个精度参数决定。这种不确定性会产生与真实MRCs的偏差。寄存器同时更新引入了一种更微妙的错误形式。由于HLLs的设计，有时寄存器更新可能导致旧计数器的值增加比新的计数器多。这个现象会导致 ∆y 的负值更新，因为老的计数器比年轻的计数器变化更慢。
2) 不确定性
论文[1]中实际计算堆叠距离的方案仅计算近似值。这种堆栈距离的不确定性是由下采样，剪枝和使用概率计数器引起的。在计算请求块发生的时间时，并没有足够的信息来准确地确定堆栈距离。
参考文献
[1] Wires J , Ingram S , Drudi Z , et al. Characterizing Storage Workloads with Counter Stacks[C]// Usenix Conference on Operating Systems Design & Implementation. USENIX Association, 2014.
