论文重点
- 采用软件zswap的方式进行cold memory数据压缩
- google的业务有32%的memory数据是cold memory，其中20%的数据是可压缩的，压缩效率中位数为3倍，那么TCO有4.2%的收益
- 该压缩策略保证了SLA不受影响：通过cold memory和promotion rate的模型保证
- 压缩解压缩的开销不大，完全可以接受
- 使用ML进行autotuner
1 introduction
问题：
- 随着资源的scaling，一个资源瓶颈会影响整个scaling的TCO。
- DRAM成为scaling的瓶颈，memory的TCO减少逐渐放缓
- 随着大数据workload的普及，主流的in-memory computing的方式加速了DRAM的需求
方向：far memory（介于DRAM和DISK之间的存储）
far memroy需要解决的问题：
- 不影响应用的性能
- 应用数量多且种类多样，不能对每个应用单独优化（不现实），需要对业务透明且robust的机制，有效使用Far memory
- 动态的cold数据行为：业务的数据冷热是会变化的，比如不同该时间段
2 Background & motivation
2.1 Far memory
non-volatile memory
- 高延迟
- 低带宽
- 读写不一致（读比写快）
remote memory：使用远程未使用的memory，或建立cluster共享的memory pool，用时tens of us，依赖cluster size和网络速度
- remote memory的页面换出是会扩展failuer的，cluster更容易failure
- 由于安全性的严格要求，需要加解密
- WSC的应用对tail latency 敏感，而cluster之间的tail latency比machine内部更难保证
2.2 Far Memory in a real-world WSC: opportunities and challenges
总结：
Far memory方案有潜力，值得做，但是运用到生产环境需要：
- 准确控制cold memory减少对性能的影响
- 灵活处理不同机器，cluster和job之间的差异
从两方面衡量Far Memory的方案前景：
- cold memory：单位时间内不被访问的memory占比，占比越多，前景越大；120s时间内，占比32%，比较可观。
- promotion rate：cold memory部分数据被访问的频率，频率越多，前景越小；120s统计的cold memory，promotion rate=15%
- 从图1看出，cold memory越大 promotion rate越大，两者需要折中。
图2展示了不同的cluster的每个机器的cold memory占比的分布（T=120s)：
- cold memory比例跨度大，从1%~52%，如果按照20%的memory设置Far memory，有的机器可能不够用，有的机器有浪费。
- 同cluster内部或cluster之间都有差异
图3展示了job的memory分布：
- bottom 10%的job只贡献了9%的cold memory
- top 10%的job贡献了43%的cold memory
- 应用的cold memory差异较大，但对于每个job分别优化不太现实，这里提出一个挑战
3 software-defined Far Memory
软件定义的Far Memory是通过zswap实现的：
- linux kernel3.11+即可
- 通过zswap压缩cold page到memory，然后pack更多data到memory
- 该实现与Far memory在更高层面是一致的，都是降低了每次访问的成本。
3.1 software-defined Far Memory优势
- 可靠：没有remote memory的缺点；不用引入新的硬件，简化设计、实现、测试、部署和监控。
- time to deployment：方案用时短，成本低。
- 没有新的hardware的成本：鉴于cpu利用率变化大，利用机器本身闲置的cpu cycle
- 适用于动态应用行为：第二章说明 machine，cluster和job都要区别对待。‘
3.2 software-defined Far Memory挑战
- 保证性能SLO
- 使用较少的cpu cycles，最大化memory TCO的优化
- zswap的缺陷：只有memory 不足时才会触发，且触发后避免allocation
- zswap的性能开销无法限制
- burst的压缩开销影响tail latency
- 在memory不饱和的时候没有实现memory 节省
- 不是所有data都适合压缩：例如video没有textual数据适合压缩
4 Cold page识别机制
我们的目标与原本zswap的区别是：什么时候压缩页面？确定是cold page时候。
4.1 cold page的定义
最后一次访问页面的时间，即age：cold age threshold。
越小越好，但是越小越多的访问会是far memory 影响性能，重点在于满足SLO的基础上尽可能小的age。
4.2 performance SLO for far memory
直接关联应用性能和age是不可取的，因为应用性能的特征多样化，有的是latency敏感的（例如web前端），有的是带宽敏感的（例如machine learning）。
因此要找个低level的容易衡量各个业务的指标，并且和far memory的性能开销要相关。
Promotion rate：表示一定时间内，内存需要从far memory page加载到near memory的比例
Target promotion rate：上述promotion rate是各个应用绝对值有差异的，因此需要归一化，那么所有应用都可以公用一个逻辑。
SLO的目标： 保证 promotion rate < P% * 应用的working set size（和memory BW使用正相关）/ min
等价于： promotion rate < P% * 该应用最小的cold age threshold内所有访问的page数 （age=120s不应该固定？？？）
等价于：( far memory 访问的page/min) / (所有访问的页面 working set size /min) < P%
具体的P的决定取决于near memory和far memory的性能差异，差异越大，P越小。谷歌 P=0.2% /min (通过month-long的A/B test）
这个SLO目标会导致burst的解压缩，可以选择性的退出或者杀死或者reschedule低优job。谷歌的borg 18个月未有SLO的eviction。
4.3 控制 cold age threshold
建立promotion的分布图（直方图）：
- 每个job一个直方图
- 横坐标是不同的cold age threshold；纵坐标是按照该cold age threshold的promotion rate。
这样选择达标的promotion rate中并且cold age threshold最小的那个T；但这只基于过去的信息是无法处理未来的spike的，因次增加下面的机制：
- 过去一段时间（具体多少？==S？？）每分钟记录一个best cold age threshold，选择他们中的K分位值作为下一分钟的cold age threshold（SLO违约可能只有1-K%）
- 如果上一分钟的best cold age threshold 大于K分位，那么选择上一分钟的cold age threshold（越大，SLO违约可能越小）
- 因为算法基于历史信息，要解决冷启动问题，一开始job自动disable zswap一段时间（S秒）
4.4 计算cold memory size
构造cold memory直方图，用于归一化promotion rate和离线分析。
- 每个job一个直方图
- 横坐标是不同的cold age threshold；纵坐标是按照该cold page的数目
5 系统实现
系统包括online和offline两大部分，其中
online包括：
- kernel增加的kstaled和kreclaimd两个模块
- 每台机器上都有的node agent，用于收集cold memory的信息
offline包括
- 存储数据的database
- 基于ML的autoTuner
5.1 kernel
- 使用linux memory cgroup（memcg）隔离job
- kernel增加了两个守护进程：kstaled和kreclaimd
zswap
- zswap压缩数据，压缩后的数据用zsmalloc存储
- zsmalloc要每台机器有一个全局的，之前尝试过每个memcg一个，但是带来负收益
- 当压缩后的数据大于2990B时（73%页面大小），无收益：无收益就会标记incompressible，后续都会停止对该页面的压缩，直到kstaled检测到该页面被修改了
- 当job的memory不够了，zswap会关闭，而不是当做一个swap device：因为WSC对于应用是要求fault-tolerant的，不应该在浪费cpu的资源，而是failing-fast并restart到别的机器。就像be应用out of memory时被kill一样
- 机器out of memory会直接进行memory reclaim
- node agent会按照job的memcg的working set size维护一个软限，低于这个限制，不会有reclaim发生，reclaim意味着消耗cpu进行zswap，对于高优业务划不来
kstaled（这个机制被现在的idle page tracking替代）
- 实现：
- 每个周期遍历page table：查看access bit，如果set了，那么age清零；否则增加age
- 遍历完该page，将access bit清零，保证下次访问
- 数据结构
- 在page的数据结构中增加8bit来保存该page的age
- 周期是120s，8bit可以大概最少8.5hours的age
- 其他
- kstaled还要将age信息用来更新cold age histogram和promotion histogram；然后发送给node agent来决策cold page age threshold
- kstaled大概会消耗一个逻辑core的11%的资源，可接受
kreclaimd
- kreclaimd会将node agent的cold page age threshold和各个page的进行比较，将age大的page交给szwap进行压缩
- 如果压缩页面被访问了，kreclaimd也会在机器空闲的周期中将其解压缩
- 我们只会将LRU list的page映射到far memory，其他不会进行压缩；这样保证unevictable和locked memory不被压缩（疑问？？unevictable 的 page 不也在 LRU list 上吗）
5.2 node agent
- node agent就是borglet，它用4.3的算法为每个job维护一个cold page age threshold。
- node agent会在job开始的S秒后使能zswap，直到将cold page age threshold设置为K分位（因为设置需要先训练）
- node agent 会周期性的将job的cold memory 信息保存到external database
5.3 ML-based Autotuner
offline的模型主要输出K和S。
fast far memory model：
- 用mapReduce的pipeline实现
- 输入：每个job的working set size， promotion histogram，cold page histogram（聚合成5分钟）
- 输出：cold memory size和promotion rate的95分位值
- 配置：K分位和S秒
- 约束：98分位的promotion rate < 0.2% / min * working set size(min)
- 速度快：job并行且独立：整个WSC的一周数据，不到1hour处理完。
ML-based autotuning
- 上述model的配置空间太大，用GP缩小尝试的次数？？？
6 评估
6.1 cold memory coverage
cold memory越多，收益空间越大。
图5是随着 cold memory 覆盖率=cold memory/total memory随着时间的趋势：
- A和B是进行静态参数配置的zswap的实现；C和D是加上了autotuner的实现。
- B=15%，D=20%；autotuner效果显著
图6是不同cluster的cold memory覆盖率的表现：
- 不同cluster的cold memory覆盖率有差异，cluster的cold memory较稳定，约20%
- 同一个cluster内的不同机器的cold memory覆盖率有差异
- 要采用zswap这种灵活的软件方式
6.2 性能影响
性能的影响主要是promotion rate和压缩解压缩的cpu开销。
图7是每个job归一化后的promotion rate的CDF图：
- 98分位对应的promotion rate都低于0.2%
- 25分位到90分位只有很少的promotion rate的差距，这警告我们，只有SLO有很大余量的时候才能将参数配置的更aggressive
- 对比autotuner使用前后，还是有效果的，promotion rate中位数增加了。
图8是分别是压缩和解压缩的cpu消耗，可见非常低，开销可以忽略不计。
6.3 compression
图9展示了压缩比和解压缩带来的latency开销：
- 压缩比的中位数是3倍，也就是说可以节省67%的memory容量
- 解压缩的latency开销是6.4us，98分位是9.1us，和far memory技术相比也是很有竞争力的（SSD或remote memory一般要tens of us）
6.4 bigtable的实践
图10展示了big table的采用了zswap的对比：
- cold memory覆盖率在5%~15%波动
- ipc相对于未采用zswap的变化不大。
