Software-defined far memory in warehouse-scale computers

论文重点

  • 采用软件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方案有潜力,值得做,但是运用到生产环境需要:
  1. 准确控制cold memory减少对性能的影响
  2. 灵活处理不同机器,cluster和job之间的差异
0
从两方面衡量Far Memory的方案前景:
  • cold memory:单位时间内不被访问的memory占比,占比越多,前景越大;120s时间内,占比32%,比较可观。
  • promotion rate:cold memory部分数据被访问的频率,频率越多,前景越小;120s统计的cold memory,promotion rate=15%
  • 从图1看出,cold memory越大 promotion rate越大,两者需要折中。
0
图2展示了不同的cluster的每个机器的cold memory占比的分布(T=120s):
  • cold memory比例跨度大,从1%~52%,如果按照20%的memory设置Far memory,有的机器可能不够用,有的机器有浪费。
  • 同cluster内部或cluster之间都有差异
0
图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 系统实现

0
系统包括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效果显著
0
图6是不同cluster的cold memory覆盖率的表现:
  • 不同cluster的cold memory覆盖率有差异,cluster的cold memory较稳定,约20%
  • 同一个cluster内的不同机器的cold memory覆盖率有差异
  • 要采用zswap这种灵活的软件方式