OSDI前沿技术调研
PB21030838 罗浩铭
MLsys方向
Achieving μs-scale Preemption for Concurrent GPU-accelerated DNN Inferences
提要
论文关注GPU处理不同时延要求的并发DNN任务时的调度问题，即在满足强实时性任务（Real-Time task）的低时延需求的同时，提高非实时任务（Best-effort task）的吞吐量。
成果与创新点
idea非常简单，不知道为什么之前没有人做。 文章成果思路如下：记强实时性任务（Real-Time task）为RT，非实时任务（Best-effort task）为BE。当RT到来，直接kill掉所有的BE，全力执行RT，在此基础上算力还有余则塞给BE。无RT时，直接并发地执行BE。
- 基于GPU Kernel的幂等性，提出了reset-based preemption技术，通过直接kill正在执行的非实时任务，实现微秒级的任务抢占
- 同时，本工作还基于对DNN推理任务时延可预测性的观察，提出了Dynamic Kernel Padding技术，通过动态地将不同任务的GPU Kernel合并到一起，允许非实时任务利用实时任务的剩余资源与其并行执行，在保证实时任务时延不受干扰的情况下，避免非实时任务饥饿，同时也提高了吞吐量。
结果
测试表明，相比只执行实时任务，REEF可以保证对实时任务的时延干扰小于2%的前提下，提高1.1 ~ 4.3倍吞吐。
详细笔记
原来的GPU任务调度方式：
1. 序列执行。将接到的任务仅仅作为一个队列处理，这样既有低时效的问题，又有低吞吐量的问题（见PPT图示）
2. Block-level Preemption。无并发，接到低时延任务就开始执行它直到把它执行完
3. Multi-Streams。用并发的方式，轮流执行多路任务。高吞吐量，但时延高
附：概念解释
- 幂等性：用户对于同一操作发起的一次请求或者多次请求的结果是一致的，不会因为多次点击而产生了副作用(a+a+a+.....=a)
大作业可行性分析
- 需要GPU
Ekko: A Large-Scale Deep Learning Recommender System with Low-Latency Model Update
提要
论文关注低延迟的模型更新。
成果与创新点
- Ekko允许模型更新直接从训练集群中发送给全球推理集群中的模型副本，从而避免了高延迟的模型验证和广播过程。为了实现这个想法，Ekko实现了一个高效的点对点模型更新分发协议。这个协议利用了模型更新的稀疏性（即一个大型模型短时间内的更新往往会集中在热点参数），从而使得海量在线模型同步得以实现高吞吐和低延迟。
- 另外，Ekko进一步提供了SLO保护机制：一个优先级模型更新调度器和一个模型状态管理器。这个调度器确保了Ekko在繁忙网络上可以优先发送对于SLO具有重大影响的模型更新。同时，模型状态管理器可以保证有害的模型更新（造成精度下降）可以被快速探测，并且将受影响的模型状态做到实时恢复。
结果
在大型集群测试中，我们发现Ekko比最先进的深度学习推荐系统降低了几个量级的模型更新延迟。
详细笔记
现有的深度学习推荐系统无法满足低延迟的模型更新这种需求。它们往往以离线的方式训练和验证模型，之后将模型从单个训练集群中广播给部署在全球推理集群中的模型副本。这种做法会产生分钟甚至小时级别的模型更新延迟，从而对推荐服务的质量（Service-Level Objectives, SLOs）产生负面影响。
（Ekko 源自腾讯微信内部 WePS 项目，已落地微信生产环境两年，将推荐模型更新延迟从数分钟降到2秒，包括视频号、看一看和订阅号等场景，每天服务超过10亿用户。）
附：概念解释
大作业可行性分析
分布式系统
一致性算法
...
数据密集型应用系统设计读书笔记
要搞清楚要解决的问题是什么，具体的技术手段可以是怎样的 以下的调研将分主题展开，各主题有宏观有微观。
总览
当今许多新型应用都属于数据密集型，而不是计算密集型，对于这些类型的应用，CPU的处理能力不是瓶颈，关键在于数据量、数据复杂度及数据的快速多变性。
场景
可靠性
- 系统局部失效时，保障数据正确性与完整性
- 系统降级
可扩展
- 系统增加
可维护
- 友好的API
总体结构
它通常包含以下部分：数据库、高速缓存、索引、流式处理、批处理，
分布式数据系统综述
场景
总的场景
- 负载过大，需要分散到各个机器上
- 需要多台机器提供冗余
- 在全球范围内部署服务，以方便用户从最近的数据中心获取服务（可忽略）
总体结构
无共享结构为主流，我们将主要使用无共享结构，即各主机之间只通过传统网络连接，相对于共享硬件的有共享结构。
复制
场景
这里的场景主要指复制技术具体遇到的问题
- 数据处于不断变化之中，常规复制会导致不同节点之上呈现不同时间点的数据
- 异步复制，原主节点的所有数据未分发完时掉线，此时新主节点并未受到所有的写请求；若它再上线，可能让新的主节点收到冲突的写请求
- 如果在数据库之外有其他系统依赖于数据库的内容并在一起协同使用，丢弃数据的方案就特別危险。例如，在GitHub的一个事故中, 某个数据并非完全同步的MySQL从节点被提升为主副本，数据库使用了自增计数器将主键分配给新创建的行，但是因为新的主节点计数器落后于原主节点（即二者并非完全同步） ，它重新使用了已被原主节点分配出去的某些主键，而恰好这些主键已被外部Redis所引用，结果出现MySQL和Redis之间的不一致，最后导致了某些私有数据被错误地泄露给了其他用户。
- 两个节点都自认为是主节点
- 如何设置合适的超时时间来检测主节点失效？太长则恢复时间久，太短则容易将正常情况误判为掉线
最严苛的有： - 由于软件BUG造成的无提示数据损坏
具体技术
处理节点失效
从节点失效：追赶式恢复，从节点可以得知故障前处理的最后一笔事务，然后连接到主节点，并请求那次事务之后的所有数据变更，将其应用到本地以追赶主节点
主节点失效：节点切换，确认主节点失效，选举新的主节点，重新配置系统令新主节点生效
复制日志的实现
基于语句的复制
复制每个操作语句。 问题是： - 任何调用非确定性函数，如NOW()获取当前时间，或者RAND()获取随机数的操作，可能产生不同结果（可将其替换为执行后结果再分发，但存在太多边界条件需要考虑） - 副本必须完全按照顺序执行，这对并发执行限制很大 - 有副作用的语句可能在每个副本上产生副作用
基于预写日志(WAL)
对数据库写入的字节序列都被加进日志，其粒度足以让从节点与主节点完全同步 其缺点是： - 日志描述的数据结果非常底层，比如哪些磁盘块的哪些字节发生改变，甚至主从节点使用不同版本的存储程序都不行（这使得不能热更新应用，必须停机）
基于行的逻辑日志复制
复制日志与存储引擎采用不同格式，这时复制日志称为逻辑日志。它与存储底层逻辑剥离，可支持不同版本甚至不同应用间的复制，信息以行作为单位（MYSQL的binlog基于该方式）
基于触发器的复制
数据变更将触发一段指定代码的执行，灵活度很高，不过复制开销更大
多主节点的复制
多个主节点，每个主节点仍然可以带从节点，好处是性能更好、可容忍主节点失效
处理写冲突
多主节点复制最大问题即可能发生写冲突，两个写请求可以使得两个主节点数据发生不同的变更。这可以通过避免冲突（令特定请求总由一个特定节点处理）、merge冲突内容、LWW（最后写入者获胜）来解决。
无主节点复制
没有主节点，允许任何副本直接接受用户写请求。
读写quorum
每次写请求都会附一个版本号。 设副本节点数为n，读、写都并发地向各节点发送请求，需要保证读成功数达到r与写成功数达到w且w+r>n，则可以保证必定读到一个最新版本的值。 - 读修复：读到新值与旧值时根据新值更新所有旧值 - 反熵过程：有一个后台进程不断寻找数据库旧值并更新 - 宽松的quoru，允许借助n个副本外的节点暂存数据，一旦副本节点恢复则开始回传
复制滞后问题
要保证的一致性
写后读一致性：保证用户总能看到自己提交的新数据
单调读：用户在某个时间点读到数据之后，不能再读到比该时间点更早的数据
前缀一致读：保证数据的因果关系，如总是先读取问题再读取回答
解决方案
前一个的解决办法有：可能产生此问题的数据在主节点读取，或者比较节点最新更新时间戳与提交的新数据的时间戳作对比（这办法不很可靠，时钟是不可靠的，不同请求到达延迟也不同） 后两个的解决办法通常都是：保证相关的数据总是在同一个节点读
（后面可线性化问题那里会有更深入讨论）
分区
将大的数据集分块存储。
事务
事务即将应用的多个读写请求捆绑在一起称为一个逻辑操作单元的机制。一个事务的执行要么成功（提交），要么失败（中止，并回滚或重试）
ACID
- 原子性：事务中操作不可分，一个事务的执行要么成功（提交），要么失败（中止，并回滚或重试）。
- 一致性：所有数据更改必须满足合法性（其实与事务无关，主要由应用层负责）
- 隔离性：其它线程无法看到其执行的中间结果，只能看到执行前或后的状态
- 持久性：一旦事务提交成功，其所写入的数据就保证不会丢失
脏读 客户端读到了其他客户端尚未提交的写入。读-提交以及更强的隔离级别可以防 止脏读。 脏写 客户端覆盖了另一个客户端尚未提交的写入。几乎所有的数据库实现都可以防止 脏写。 读倾斜 (不可重复读) 客户在不同的时间点看到了不同值。快照隔离是最用的防范手段，即事务总是 在某个时间点的一致性快照中读取数据。通常采用多版本并发控制（MVCC） 来 实现快照隔离。 更新丢失 两个客户端同时执行读-修改 - 写入操作序列，出现了其中一个覆盖了另一个的写 入，但又没有包含对方最新值的情况，最终导致了部分修改数据发生了丢失。快 照隔离的一些实现可以自动防止这种异常，而另一些则需要手动锁定査询结果 (SELECT FOR UPDATE) 。 写倾斜 事务首先査询数据，根据返回的结果而作出某些决定，然后修改数据库。当事务 提交时，支持决定的前提条件已不再成立。只有可串行化的隔离才能防止这种异 常。 幻读 事务读取了某些符合査询条件的对象，同时另一个客户端执行写人，改变了先前 的査询结果。快照隔离可以防止简单的幻读，但写倾斜情况则需要特殊处理，例 如采用区间范围锁。 弱隔离级别可以防止上面的某些异常，但还需要应用开发人员手动处理其他复杂情况 （例如，显式加锁）。只有可串行化的隔离可以防止所有这些问题。我们主要讨论了 实现可串行化隔离的三种不同方法： 严格串行执行事务 如果每个事务的执行速度非常快，且单个CPU核可以满足事务的吞吐量要求，严 格串行执行是一个非常简单有效的方案。 事务 I 251 两阶段加锁 几十年来，这一直是实现可串行化的标准方式，但还是有很多系统出于性能原因 而放弃使用它。 可串行化的快照隔离 (SSI ) —种最新的算法，可以避免前面方法的大部分缺点。它秉持乐观预期的原则，允 许多个事务并发执行而不互相阻塞，仅当事务尝试提交时，才检査可能的冲突， 如果发现违背了串行化，则某些事务会被中止。 本章中的示例都采用关系数据模型。但是，正如本章前面的 “多对象事务的需求” 所 描述的，无论对哪种数据模型，事务都是非常有用的数据库功能。 本章所介绍的算法、方案主要针对单节点。对于分布式数据库，还会面临更多、更复 杂的挑战，我们将在接下来的两章中继续展开讨论。