devconf 19′: virtio 硬件加速

前言

devconf 也是我比较关注的一个 summit,devconf 的内容当然比较偏实践,但有一些东西还是比较前沿的。

很多人会认为 virtio 是一套实现(virtio-net, virtio-blk 等等),但实际上 virtio 是一套标准(或者说抽象层),因为 virtio 通过半虚拟化的方式来加速虚拟化的性能,那么就需要 hypervisor 和 guest 的协作来达到目的,其中 hypervisor 端我们称为 backend driver,guest 端称为 frontend driver。

virtio 的具体介绍在 developer works 有一篇很好的文章,如果对 virtio 不了解的话可以参考这篇: https://www.ibm.com/developerworks/cn/linux/l-virtio/index.html,进一步的,还可以阅读 Rusty 写的原论文:https://www.ozlabs.org/~rusty/virtio-spec/virtio-paper.pdf

这里简单介绍一下 virtio 的基本架构,就是下面这张图:

image.png-54kB

可以看到 IO 的核心就是 virtqueue,virtqueue 定义了 add_bufget_bufkick 等几个关键 IO 接口。

virtio 刚提出时其实是很先进的,因为通过共享内存替代了完整的 trap/模拟过程,大大提升了性能,但是随着底层 IO 设备性能的越来越强,大家对 virtio 也逐渐提出了更高的要求,例如通过 vhost 来加速等等,但是即使像 vhost、vhost-user 这些技术也解决不了对 hypervisor 资源(特别是 CPU)的占用问题,因此需要更加适合高性能 IO 设备的技术了。

一种思路是设备透传,作者在这里简单讲了下设备透传的缺点:

image.png-117.3kB

主要是一来热迁移很难做,当然并不是说完全不能,今年的 KVM Forum 上就有 topic 讲 GPU 透传怎么做热迁移,Netdev 也有讲 SRIOV 网卡怎么做透传,但有几个问题:

  1. 热迁移实现和透传设备类型强相关,例如上面 GPU 的热迁移和 SRIOV 网卡的设计完全不同
  2. 需要很多的代码改动,不能复用现有的 virtio 设备热迁移框架
  3. 更加灵活可控

为此 oasis 现在发布了 virtio 1.1 spec,在 devconf 时还是 draft 阶段,现在已经正式发布了:https://docs.oasis-open.org/virtio/virtio/v1.1/csprd01/virtio-v1.1-csprd01.html。virtio 解决的核心问题就是性能,这个不仅包括软件实现的性能,也包括硬件实现的性能(和实现的难度)。

设计

Packed virtqueue

首先 virtio 1.1 最重要的改变之一就是 virtqueue 的改变,由 split virtqueue 转为 packed virtqueue。这里我要先讲一下 split virtqueue 是什么,以及遇到了什么问题再讲 packed virtqueue。

image.png-117.1kB

本节的图来自去年的 DPDK Summit,Jason Wang(Redhat)和 Tiwei Bie(Intel)在去年 DPDK Summit 对 Virtio 1.1 做了很好的介绍,推荐阅读,原 Slide 在:https://www.dpdk.org/wp-content/uploads/sites/35/2018/09/virtio-1.1_v4.pdf

Split virtqueue 顾名思义,queue 会有多个 ring,分别是 available ring、descriptor ring 和 used ring,每条记录都通过
next 指针来标识下一条记录,这样就会有下图所示的几个问题,而且对于硬件实现来说,这些跳转会带来开销比较高的 pci transaction,不利于性能提高。

image.png-182.8kB

下面的是 packed virtqueue,packed queue 把原本分散在三个 ring 的元数据组合在了一起,这样元数据读取的软件实现可以减少 cache miss,硬件实现可以只用一个 PCI transaction 解决。

image.png-141.7kB

其他

另外就是一些新的特性,这些特性需要在设备 negotiate 时决定是否开启,比如:

  1. in-order completion。以往 ring 的完成是可以乱序完成的,这样 driver 实现就需要做的更复杂,也不利于优化(比如不好做批量动作)
  2. 支持内存访问有限制的设备(比如设备的内存访问要经过 IOMMU)
  3. 支持开启关闭特定 ring buffer 的 notification,硬件实现可以减少 PCI transaction
  4. notification 增加更多的信息,这样硬件实现上可以并行做更多事情,而且减少了在 PCI bus 上来回获取信息需要的时间。

目前的状态

硬件实现是需要看供应商的,所以这里除了 paper work 之外我们还可以说下目前软件实现的状态。

Packed virtqueue

packed virtqueue spec 其实已经定下来了,也发布在了 1.1 spec 中,对应实现需要 front 和 backed 都改,所以当前状态如下:

image.png-58kB

dpdk 这边进展是比较快的,通过 dpdk 理应已经可以测试 packed queue 带来的效果。

vDPA

image.png-227kB

即使有了上述规范,实现一个硬件 backend 的 virtio 设备也是比较繁琐的,因此 Intel 提出了 vDPA 这个框架,可以理解为如果你真的打算用硬件来做 virtio backend,vDPA 帮你把通用的一些工作已经做好了,例如硬件设备抽象、IO 路径等等,Intel 目前给出了 vDPA 下两个驱动,一个是 IFCVF,用来支持 Intel FPGA 100G,不过这个 FPGA 开发板可是很贵,后来 Intel 又提供了 vDPA Sample,这样你可以从中学习 vDPA 的工作方式。

vhost-mdev

vDPA 其实挺好的,但 Intel 后来又提出了 vhost-mdev,上面 vDPA 的架构图你也能看到有个 vhost/mdev,这是为什么呢?在我看来主要是因为 vDPA 原本设计比较面向网络,我们要先看下 vDPA 的原本设计细节架构(摘自 kvm forum 2018):

image.png-422.7kB

可以看到 vDPA 做了数据面,但是控制的部分其实是 virtio-net(vhost-user)实现的,这样在刚开始做 vDPA 来说很方便,因为减少了很多工作,但如果面向别的类型设备准备实现 virtio 硬件加速,比如存储啊、一些辅助加速设备啊什么的就会发现 vDPA 帮我们减少了数据面的代码量,但控制面还是需要很多工作。就像 vDPA 在 DPDK 里做 vdpa driver 这样解决 vhost 到 vDPA 这个过程。

有没有什么通用 IO driver 呢,其实是有的,vfio。

所以我们可以在前端使用 vfio,在后端做一个 mdev 对接下面具体的 virtio 加速设备,厂商可以自定义 MMIO、PCI 空间等等这些控制面细节。

image.png-406.8kB

vhost-mdev 目前还处于比较早期的阶段。

Intel Cascade Glacier

我对 FPGA 很多内容也不了解,只知道这个是 Intel 去年正式发布的 FPGA 智能网卡,可以实现 virtio 加速,OVS 卸载,从 Intel 在去年 OVS Conf 的介绍看,Intel 为之提供了一套 SDK 和软件栈。

image.png-342.5kB

此外还支持 P4:

WX20190508-003724@2x.png-742kB

总结

  • 越来越多供应商开始对 virtio 硬件加速感兴趣
  • 目前已经有至少一个硬件 ready
  • 有通用的软件框架支持各种硬件
  • Virtio 1.1 为硬件实现做了很多优化和改进

Eurosys 19′ Notes:Ursa: Hybrid Block Storage for Cloud-Scale Virtual Disks

Ursa 是美团云 16 就发布过的面向 IaaS 云主机的块存储系统,目前 Ursa 主要有几篇公开文章讨论其架构:

最早:https://tech.meituan.com/2016/03/11/block-store.html 介绍了 motivation、和其他块存储的比较
17 年在知乎专栏发表了基于混合存储的效率优化,和这次 Eurosys 19′ 内容相关:https://zhuanlan.zhihu.com/p/27695512
17 年还有一篇 USENIX 17′ 的文章:https://tech.meituan.com/2017/05/19/speculative-partial-writes-erasure-coded-systems.html 介绍了对 EC 的优化

下面介绍这篇文章,原文地址:https://www.cs.jhu.edu/~huang/paper/ursa-eurosys19.pdf or https://dl.acm.org/citation.cfm?id=3303967

简介

通过追踪块存储的 IO pattern 可以发现其 IO 的 locality 很差,因此相对于使用 SSD 作为 cache layer,Ursa 选择了底层直接使用 SSD-HDD 混布方案,将主副本放在 SSD 上,备副本放在 HDD 上,通过 Journal 来弥补 SSD 和 HDD 之间的性能差距。实验显示之中模式在大部分情况下可以达到与全 SSD 相同的性能,与全 SSD 的 Ceph 和 Sheepdog 相比效果也很好,而且有更高的 CPU 效率。

最近几年有一些提升虚拟磁盘吞吐的研究,例如 NSDI 14′ 发表的 https://www.usenix.org/system/files/conference/nsdi14/nsdi14-paper-mickens-james.pdf ,但低成本的提高虚拟磁盘效率还是很难。通过生产环境的实验以及过去的研究(https://www.usenix.org/legacy/event/fast08/tech/full_papers/narayanan/narayanan.pdf )可以发现块存储 IO 有两个典型特征:

  1. 大部分情况都是小 IO 为主,偶尔有顺序大 IO
  2. 读和写的 locality 都很差

因为小 IO 为主,因此 SSD 在构建块存储上一定优于 HDD。但是 SSD 的价格和能耗使得全 SSD 成本太高。因此考虑到第二个特征——locality 弱,使用 SSD 作为 cache layer 效果也并不会好,根据之前的研究,考虑到高端 SSD 在延迟和 IOPS 上高 HDD 三个数量级,因此哪怕 1% 的 cache miss 也会导致平均 IO 性能降低到预期的 1/10。此外,SSD cache 对长尾延迟帮助很小,而这个是云供应商 SLA 的一个重点。最后,额外的 Cache 层还会造成块存储层的一致性问题,例如 Facebook 在 2010 年就发生过这样的悲剧。

根据上面的介绍,Ursa 使用了 SSD、HDD 混布方案,SSD 作为主副本,HDD 作为备副本,为了弥补之间的巨大性能差距,通过 journal 来将 HDD 上的随机写转化为顺序的日志追加写,再把日志异步 replay、merge 回磁盘。为了提高效率,偶尔的大的顺序写还是直接发到 HDD,跳过 Journal。这篇 Paper 将介绍几个方面:

  1. SSD-HDD 混布方案的设计,同时为了解决 Journal 和副本的结合带来的复杂性,设计了 efficient LSMT(log-structured merge-tree) 来达到快速的 invalidate 无效 journal 和在故障恢复时快速读取 journal;
  2. Ursa 中的多个级别的并行,包括磁盘并行 IO、磁盘间的条带化和网络 pipeline,通过这些方法来提高吞吐性能;
  3. Ursa 的满足强一致性(线性一致性)的复制协议,rich-featured client 和在线升级的高效机制。

实验显示 Ursa 在混布模式下提供了接近全 SSD 的性能,与全 SSD 模式的 Ceph 和 Sheepdog 相比还实现了更高的 CPU 效率。实际环境验证显示能在更少的 SSD 数量下提供全 SSD 部署的 AWS、腾讯云的块存储相媲美甚至更好的性能。

动机

首先我们研究了微软在之前文章发布的数据以及自己收集的数据,显示可以看到 70% 的 IO 大小都小于 8KB,几乎所有 IO 都不大于 64KB,这说明块存储中小 IO 是主要组成。

image.png-56.8kB

因为 HDD 在随机小 IO 上的低性能,高性能存储往往使用 HDD 来构建,传统的 SATA SSD 比 HDD 在 IOPS 和延迟上要好两个数量级,PCIe SSD 的话更好。而且 SSD 比 HDD 有更低的故障率和相似的寿命。

SSD 的主要缺点就是价格,特别是基于副本的存储。一种办法是使用 SSD、RAM 做 Cache,但是 Cache 效果并不好。

image.png-37.9kB

上图显示了在读方面很低的 cache 命中率,因为这里很多数据都是只读一次。再考虑到 SSD 和 HDD 随机 IO 巨大的性能区别,稍低一点 cache 命中率就会很大影响整体性能,而且这种不稳定的 cache 命中会影响云服务的 SLA。

因此这里介绍的 SSD-HDD 混合块存储直接将主副本保存在 SSD 上,然后再复制到 HDD 上,所有客户端读一般来源于 SSD,所以没有 cache miss 的问题,不过问题是如果每次写都要同步复制到 HDD 的话,HDD 的性能会直接拖累这种简单的 SSD-HDD 混布设计,这样就没有意义做混布了,所以这里通过 journal 来弥补之间的差距,在异步 replay。尽管长期看起来看平均写性能还是受限于 journal 在 HDD 上的 replay,但实践中客户端感受到的随机小 IO 要比 journal 的顺序写性能好。

设计

架构概览

image.png-81.4kB

  1. Chunk Server。每个 data chunk 有一个主副本和多个备副本保存在不同机器,每个机器插多个 SSD 和 HDD,既保存 primary 也保存 backup。
  2. Client。VMM 通过 client 使用 NBD 接触块存储。client 查询和管理元数据(例如云盘的创建、打开、删除)时与 master 交互。这种交互是 stateless 的。
  3. Master。Ursa 中有一个类似 GFS 中的 master 来简化管理操作。master 不参与正常的 IO 路径来避免成为瓶颈。master 提供 coordination,包括云盘创建、打开、删除,元数据查询,状态监控,故障恢复等等。

SSD-HDD 混合存储架构

对于一个读请求,primary server 直接读取来自 SSD 的数据,而写请求则先写到 SSD,然后复制到 backup(backup 会在写完 journal 返回),最后返回到客户端。

journal 既可以保存在 SSD 也可以保存在 HDD 上,Ursa 选在保存在 SSD 上因为有更好的并发 IO 性能,此外使用一个 in-memory index 来保存 chunk offset 到 journal offset 的对应。

长期来看,journal 这种方法也会受限于 HDD 的随机写性能,但是:

  1. 写操作里有很大比例是在 overwrite,而 overwrite 到 journal 可以合并
  2. 通过 journal 重放时做合并和调度可以减少 HDD 磁头移动

Journal 都保存在 backup 本地,因为本地 journal replay 要比跨机器的 replay 简单很多。根据实践经验,Ursa 使用 SSD 1/10 的容量存放 journal。

按需 journal 扩展

当一个 SSD 耗尽 journal 的空间后,Ursa 可以动态扩展 journal 到另一个负载最低的 SSD(其 journal 空间没有用完)。如果所有 SSD 的 journal 空间都用完了,那就使用 HDD 的空间存放 journal。理论上讲 HDD journal 可以按需任意大,但是和日志文件系统不同(例如 https://www.researchgate.net/publication/221235948_DualFS_A_new_journaling_file_system_without_meta-data_duplication),journal replay 是必须的,不仅是空间效率的问题,还有快速恢复的原因。

HDD journal 设计与 SSD 几乎一样,除了 HDD journal replay 只会发生在 HDD 空闲时。在 Ursa 线上部署的两年时间里,HDD journal 从来没有用到过。这是因为条带将数据分布到很多机器上上,这样很难出现某一台机器集中产生大量写入。而且如果一个客户端产生大量的 IO 会先被 master 限速而不是把 SSD journal 耗尽。

Journal bypassing

大于 64KB 的 IO 会跳过 journal 直接写入 HDD。

Client direct replication

为了降低极小 IO 的延迟,考虑到很小的 IO 只占用极小带宽,小于 8KB 的 IO 会在 client 直接发到 primary 和 backup,不通过 primary 来复制。这个是这样算出来——每个机器两个万兆网口,希望最多只用一半的带宽,然后提供给客户端最高 40K 的 IOPS,考虑到三副本,那就是 20Gb/2/40K/3 ~= 10.4KB,所以设置为 8KB。

Journal index

因为上面介绍的 bypass,数据复制和恢复的复杂度会上升。为此 Ursa 设计了 per-chunk in-memory index 结构,map 了每个 chunk ofsset 对应 journal offset,这样可以快速 invalidate journal 和快速恢复。

journal index 一般通过 LSMT 设计,然后原本的 LSMT 无法满足 Ursa 在 invalidate 和 recovery 时的要求:

  1. LSMT 的 index 的 key space 是连续整数
  2. LSMT 的 index 查询和更新对 journal 读写有着严重影响,所以会直接决定 Ursa 的 IO 性能

因此 Ursa 对 LSMT 做了一下优化,显著提高了 range query 和 range insertion 的性能。

Composite keys

如果 key 对应的 journal offset 是连续的,那就合并为一个 composite key {offset, length}。composite key 之间定义了 LESS 关系:x LESS y iff x's offset+length <= y's offset,这样 composite key 形成了一个有序关系。

Index operations

因为上面定义的有序关系,因此快速的查询和更新就可以很快。

image.png-32.5kB

Index storage

KV({offset, length} -> j_offset)保存为一个 8 字节的结构体。Ursa 在 KV 中保存的是一个两级结构,第一级是红黑树,高插入效率,低存储效率,第二级是有序数组,插入效率低但存储效率和查询效率高。

当新增一个 KV 的时候,Ursa 首先快速插入到红黑树,然后由后台的低优先级工作线程异步合并到数组。因此数组中保存的 KV 可能是过期的(红黑树中的数据还没有同步到数组),所以查询查询时会先查询红黑树,然后在对 missed range 去数组查询。这样一级红黑树实际上是二级数组的一层小容量 cache。对于数组,8GB 的内存可以保存十亿条记录,相当于在 16TB journal 上全部以 16KB 的 IO 写入所需要的记录数量(16TB/16KB)。

多个层面的并行

磁盘层面

为了充分利用 SSD 的并行 IO 能力,每个 SSD 会运行多个 chunk server 进程,每个进程使用一个 libaio 线程。进程内 Ursa 会把 libaio 事件转换为协程,通过一个同步调用接口来隐藏 libaio,相反的,HDD 上只运行一个单线程进程,不使用 libaio。

跨磁盘层面

跨磁盘层面有三种并行机制,包括:

  1. 条带化
  2. 乱序执行
  3. 乱序完成

首先,Ursa 将一个虚拟机磁盘分割成多个固定大小的 chunk,然后两个或多个 chunk 组成 strip group,这样大的读写可以并行在多个 chunk 上。service manager 来保证数据 placement policy,即一个 strip group 的所有 chunk 不在同一磁盘或物理机上。

其次只要 IO 落在在不同的 chunk 上,Ursa 就允许它们乱序执行。

最后 Ursa 支持乱序返回。比如对某个 chunk IO 请求顺序是先有请求 r1,然后是请求 r2,那么返回时可以相反。

网络层面

网络拥塞和操作系统调度可能造成端到端的延迟。Ursa 的做法是使用对每个链接使用 pipeline 来处理 IO 请求,这样网络延迟对总体的 IOPS 和吞吐的影响就小很多。不过这样显然会有对上层的崩溃一致性的问题(因为完成顺序和发起顺序不一致),这个应当由上层来保证,例如 Linux Ext4、XFS 都有 journal 机制,OptFS 有 osync 和 dsync 来保证最终一致和持久化时保持一致(MatheMatrix:我觉得可以参考 OSDI 14′ 的这篇文章 https://www.usenix.org/system/files/conference/osdi14/osdi14-paper-pillai.pdf,以及我们实际遇到过的,一些文件系统并不一定达到了完整的崩溃一致性)。

一致性

概览

Ursa 通过 chunk server 间的 totally ordering write 来提供对每个 chunk 的线性一致性。简单来说,Ursa 的复制协议和 Paxos、Raft 这样的 RSM(Replicated State Machine)是同源的。每个 chunk 有版本号,chunk server 和 master 共同维护持久化的视图号(view number),view number 会在故障恢复后分配新 chunk server 时更新。

当客户端打开虚拟磁盘时,客户端会从 master 获得每个 chunk 的视图号和位置,然后向所有 replica 查询它上面的视图号。一旦视图号得到确认,client 会选择一个 replica 作为主副本(一般是 SSD 的那个),然后对主副本做读写请求,如下图。

image.png-82.5kB

如果 client 检测到某个 replica 失效,就会汇报到 master 重新分配一个 replica,更新 chunk 的位置,增长视图号。

尽管 Ursa 的复制协议 follow 了经典的设计原则,但是还是有两方面明显不同。其一是 Ursa 保证任意时刻只有一个 client 可以 access 虚拟磁盘(MatheMatrix:如果客户需要共享云盘?后面有解答);其二是混合错误模型来区别对待副本和网络失效。

Single client

Ursa 通过租约和锁协议来保证任何时候最多只有一个虚拟机可以某一个云盘读写数据。这样大大简化了强一致性设计。Client 会周期性 renew 租约,一般是 10s。如果有多个 VM 挂载同一个云盘,会在任意一个物理机上使用一个虚拟机通过类似 OCFS2 的集群文件系统协调 IO 请求,对所有挂载的 VM 提供服务。

混合错误模型

不同 GFS 这种同步复制系统(f+1 份拷贝,允许 f 个失效)或其他的异步复制系统(2f +1 份拷贝,允许 f 个失效),Ursa 将副本和网络的失效区分对待,类似 VFT、XFT 这样。Ursa 中 client 会尝试写到所有副本,但会有一个超时时间,如果发生了超时,只要主副本成功即可 commit(上图的第六步)。同时 client 会通知 master 来修复问题,例如分配一个新的 replica 来替换。

与同步复制系统相比,这样可以在一些 replica 失效时始终保持系统可用,和异步复制系统相比持久性更好,具体来说,Ursa 可以在下面的情况保持持久性:

  1. 2f+1 中不多于 f 个副本失效
  2. (失效副本数)+(链接故障数)< 总副本数

(MatheMatrix: 这里我一开始没看懂,后来咨询了本文主要作者之一李慧霸博士,这里的核心含义是 Ursa 会先尝试同步复制,但超时则降级到异步复制,从而实现用户视角的服务可用性)

Ursa 复制协议

一般情况

初始化

当打开虚拟磁盘时,客户端将从 master 获得所有 chunk 的位置和视图号,然后一步查询每个 chunk 的所有 replica 的版本号和视图号。如果一个 chunk 的所有 replica 都有与 master 保存的一致的 view number,那么就可以从中任意选一个作为 primary(优先选择 SSD 上那个);否则,客户端会先向 cluster director 通知修复一致性,然后再重试。因为前面介绍的 single client 设计,client 其实是可以在任意时间更换 primary 的选择。

读和写

一旦视图号和 primary 得到确认,client 就可以向 primary 发送读写请求了。其中读请求优先由 primary 处理,写请求则会带着 client 的 view number 和 version number。还是上面的图,当收到写请求时,primary 会先检查本地的 view number、version number 是否和这个写请求一致,如果一直就在本地写,同时复制到 backup,增长 version number,最后回复给 client。backup 上的操作也是类似的。

然而,如果 client 的 view number 和请求的不一致,那么 primary 会拒绝并回复给客户端。client 需要从 master 获得现在 view number,如果 client 的 view number 大于 primary 上的,那么 primary 将尝试通过增量修复来更新自己的状态,增量修复就是从其他副本同步修改过的数据。如果 client 的 版本号等于 primary 的版本号减 1,那么 primary 本地不会做这个写请求(因为 primary 实际已经执行过这个请求),但是会转发到其他 backup。考虑到 single client 的前提,client 的版本和 primary 的差不会大于 1.

前面介绍的混合错误模型一方面提升了系统的可用性,但也增加了数据持久性的难度。具体来说:

  • 正常情况下,所有 replica 写入成功即 commit
  • 如果 primary 无法从所有 replica 获得成功写入的消息,那么会等待一定时间看能否获得半数成功(这样加上 primary 就是多数成功)
  • 与此同时,client 会通知 master 去修复不一致问题,或者可能最终就是分配一个新的 replica 替代失效的 replica
更换主副本

如果 client 读写发到了一个 fail 的 primary,那么 client 应该会自主更换 primary 到一个有最新数据的 backup 上,这样来实现高可用。考虑到使用了 SSD journal,即使此时是在 HDD backup 上,写入性能也不会太受影响,不过读取性能此时还是会受影响的。此时 cluster director 会同步在 SSD 上再创建一个新 replica,最终 client 会将 primary 重新移回到 SSD 上。

增量修复

为了支持增量修复,每个 replica(包括 SSD 和 HDD)都在内存里保存了一个 journal lite,cache 最近的写请求的 position、offset 和 version number。当一个 primary 或者 backup 从临时故障恢复时(例如网络分区),相关的 replica 会发送他自身当前的 version number 到其他 replica,其他 replica 收到时:

  1. 根据请求的 version number 查询 journal lite,找到修改的数据
  2. 根绝 journal lite 里的信息构造修复消息
  3. 修复消息里加上新的 version number,回复给 replica

如果无法通过 journa lite 找到数据(比如因为垃圾回收),那么就会传送完整数据。

Client-directed replication

前面提过这个事情,就是小于等于 8KB 的 IO 会由 client 直接送到所有副本,而不是通过 primary,其 version number 的维护是类似的,这样可以显著降低小 IO 的延迟。

错误恢复(View Change)

当发生了不一致问题时,master 会向具有最高 version number 的 replica 发送请求来做增量修复。反之如果是 chunk 有问题,那么 master 最终会分配一个新的 replica 来替代问题的,view number 会更新为 i+1,client 会在下次读写时得知这次 view number 的变化。

更具体地说,master 会从多数 replica 中收集 version number,然后选择其中最大的 version number vm 作为最新 state,将数据分发到新分配的 replica,如果需要的话,同时对已存在的 replica 做增量修复。

最后,所有的 replica 将 view number 更新为 i+1,因为它们此时有相同的数据(以及相同的 version number vm)。如果 master 和一个 replica 同时故障了,那么先修复 master,然后修复 replica。

故障恢复的核心思想就是 master 从 quorum 中找到最高的 version number,这个和异步复制系统是一样的。这个方案的缺点就是如果多数 replica crash 则存在丢数据的可能。相反同步复制系统可以在哪怕只有一个幸存者时工作。

下面这里的讨论看起来是如何通过识别 majority 中的永久 crash replica 来达到即使只有一个幸存者 依然可以找回数据,目前 Ursa 的做法还比较依赖手工。

讨论

特性丰富的 Client

Ursa 将很多特性例如 tiny write replication、striping、snapshot、client-side caching 都放在了 client。这和与 Qemu 的紧密集成有关。

Client 被设计为装饰器模型的 pluggable modules,所有 module 实现了公共的 read()/write() 接口,client 可以在线无感升级。

在线升级

Client

当 client 和 VMM(qemu)断开连接时,VMM 不会自动重连,所以想在不影响 Guest 的前提下升级还是比较难的。一种思路是把代码尽可能放到 shared library,这样升级就是 dynamic reloading,就很简单,但是也有很多限制,比如现有很多静态库不适合,接口不好升级等等。因此 Ursa 升级粒度是 process 而不是 library。Ursa 将 client 分为两个 process——core 和 shell。当升级时:

  1. core 停止从 VMM 接受新 IO,将 pending IO 完成
  2. 将状态保存到一个临时文件
  3. 退出并返回一个特殊返回码

shell 进程接收到 exit code 启动一个新的 core,从临时文件读取状态并恢复。

(MatheMatrxi:大体就是一个通过外包壳来分离核心代码的思路,升级期间 IO 应该都 pending 了)

Master

Master 升级是比较简单的,因为不涉及 IO 路径,只要关掉旧的立刻启动新的即可。升级期间磁盘创建和空间分配都会失败,不过客户端会自动重试。

Chunk Server

这个就比较难了,特别是在 chunk server 升级中发生 failure 时会对 failure handle 产生 confuse。所以 Ursa 设计了一个优雅热升级的策略:

  1. 发送一个特别信号到 chunk server;
  2. 关闭服务端口,停止接收 IO;
  3. 等待 in-flight io 结束;
  4. 等待新的 chunk server 启动;
  5. 检查新 chunk server 正常工作。

如果热升级成功了,旧的 chunk server 关闭所有连接( MatheMatrix:比如管理端口的连接)退出,客户端自动重连到新的 chunk server。反之如果失败了,旧的 chunk server 会杀死新的 chunk server,重新打开服务端口继续提供服务。

逐个升级

一个 Ursa 集群有众多服务进程做成,升级时每次升级一个进程,检查状态再升级下一个。所以升级集群可能会持续好几天时间。所有组件保持向后兼容性,到目前 Ursa 在一个部署超过两年的集群里对 replication protocol 升级过四次版本,每次升级都会增加新的操作并保证之前的操作不会发生变化来达到向后兼容。

发挥磁盘并行性

根据经验,Ursa 对 SATA SSD 和 PCIe SSD 会跑两个和四个进程,HDD 上跑单线程单进程,这个线程同时处理 journal replay、small write 和 replication( large write)。评估显示单线程进程只用电梯算法就可以跑满 HDD,多进程、多线程这些都会扰乱电梯算法,降低性能。

硬件可靠性

根据统计(下面的表格),HDD 贡献了 70% 的错误,比 SSD 高一个数量及。而 SSD 的 wear leveling(损耗平均)保护了 SSD 不会被频繁的 journal 写影响寿命。

image.png-20.3kB

不过虽然 SSD 平均故障率比 HDD 低,但是有一个潜在风险就是 SSD 可能因为固件 bug 造成同一批、同一个供应商的 SSD 批量出现问题。(MatheMatrix:然后举了腾讯云去年的例子 /捂脸)

为了解决这个影响,需要增加购买 SSD 的多样性,而且把 primary chunk 和 backup chunk 的 journal 存放在不同批次、供应商的 SSD 上。和全 SSD 存储不同的是 Ursa 可以通过 HDD 避免因为 SSD 固件 bug 造成的批量 SSD 下线造成数据丢失。

局限

  1. primary replica 故障恢复时客户就需要忍受 HDD 的性能影响,这要求我们尽可能缩短降级时间;
  2. 因为每个机器能提供的 SSD journal 大小有限制,SSD journal 无法持续性提供长时间很高的随机写(这个在美团云服务中比较少见),这个通过 HDD journal 和限速来 work around;
  3. SSD 的实效恢复要比全 SSD 更 urgent(MatheMatrix:和 1 好像一样)
  4. 对 SSD 的大小要求比 SSD cache 大很多

评估

这里做了一些测试,我直接展示数据吧,比较了 Ursa(SSD 和 SSD-HDD 混布)、Ceph 和 Sheepdog:

image.png-86.5kB

QD(queue depth)最大为 16 因为 qemu NBD driver 只能提供到 16。Sheepdog 和 Ceph 都是部署在全 SSD 环境的。(c) 这里表现比较差主要是因为 1MB 的 BS 大于 64KB 的 journal pass 阈值,所以 backup 都直接写入 HDD 跳过 journal 了。

image.png-84.2kB

image.png-84kB

图 10 主要是因为 Ursa 很依赖 journal 的 range query 的性能,因此和 PebblesDB 做了一个比较。

image.png-156.9kB

图 14 这里的选取了三种有代表性的 trace 数据 prxy_0proj_0mds_1 分别代表不同的 IO pattern。

相关工作

这里举了一些块存储、EC、混合存储、文件系统、对象存储和一致性的文章

总结

未来计划 RDMA/DPDK/SPDK 来达到超低延迟;提高顺序写的 IOPS。

Ursa 的一部分组件是开源在 http://nicexlab.com/ursa/ 的,包括:

  • st-pio 前面说的 libaio 的包装
  • st-redis hiredis 的包装
  • logging lib 支持东岱更新配置的轻量级 logging library
  • crc32 高性能的 crc32 library
  • testing script

后面是致谢和线性一致性的正面,包括 normal case 和故障恢复。

使用 Clion 查看 DRBD(Kernel Module)代码

因为内核里有很多编译参数,所以需要配置下。

可以参考 http://ybin.cc/tools/clion-for-linux-driver-developer/

我的最终配置是:

...
include_directories(../kernel-3.10.0-327.36.1.el7/linux-3.10.0-327.36.1.el7/include)
include_directories(../kernel-3.10.0-327.36.1.el7/linux-3.10.0-327.36.1.el7/include/linux)
include_directories(../kernel-3.10.0-327.36.1.el7/linux-3.10.0-327.36.1.el7/mm)
include_directories(../kernel-3.10.0-327.36.1.el7/linux-3.10.0-327.36.1.el7/arch/x86/include)
include_directories(../kernel-3.10.0-327.36.1.el7/linux-3.10.0-327.36.1.el7/include/uapi)
include_directories(../kernel-3.10.0-327.36.1.el7/linux-3.10.0-327.36.1.el7/arch/x86/include/uapi)
include_directories(.)
include_directories(drbd)
include_directories(drbd/compat)
include_directories(drbd/linux)

add_definitions(-imacros ../kernel-3.10.0-327.36.1.el7/linux-3.10.0-327.36.1.el7/include/linux/kconfig.h)
add_definitions(-D__KERNEL__)
add_definitions(-DKBUILD_MODNAME)
add_definitions(-DCONFIG_BLOCK)
add_definitions(-DCONFIG_HZ)
add_definitions(-DMODULE)
add_definitions(-std=gnu89)
...

NSDI 2019 Notes

前言

NSDI 2019 里有两篇容器网络相关的话题,这篇还是比较有意思的,the morning paper 也谈到了这篇文章:https://blog.acolyer.org/2019/03/22/slim-os-kernel-support-for-a-low-overhead-container-overlay-network/。原版的视频、Slides、文章在 NSDI 官网都可以看:https://www.usenix.org/conference/nsdi19/presentation/zhuo。同时作者在 Github 上开源了实现:https://github.com/danyangz/Slim

大致思路是容器里的应用的流量送到另一个容器里的应用需要经过四次协议栈。

除了底层物理机的协议栈之外,主要是有一层 network namespace:

因此主要思路就是绕过这一层 stack,其效果还是不错的:

  • memcached 吞吐提高 71%,延迟降低 42%,CPU 占用减少 56%
  • Nginx CPU 占用减少 22-24%
  • PostgreSQL CPU 占用介绍 22%
  • Kafka CPU 占用减少 10%

介绍

容器网络往往使用 overlay 网络,但是 overlay 网络会带来显著地性能影响。测试显示 overlay 网络和 host 网络相比的吞吐会下降 23~48%,每个报文的延迟会增长 34~85%,CPU 占用会提高 93%,现有的加速技术往往是针对虚拟化的,对容器支持不够。

这里的核心问题就是一个包要在一个物理机上穿越两次协议栈,来回就是四次。这种设计显示受虚拟化的影响,因为虚拟机是有自己的协议栈的,宿主机不知道任何 Guest 的协议栈知识,但是容器不然,宿主机知道每个网络连接的完整信息。

因此作者设计了一种容器网络,核心思想就是让一个物理机上报文只经过一次协议栈。

这个设计有几个挑战:

  1. 网络虚拟化不能要求应用作出修改
  2. 需要支持与现在的网络相同的网络策略(network policy)
  3. 支持现在的容器网络相同的安全模型

Slim 的优点在上一节描述过了,缺点也有几个:

  1. 增加了连接建立的复杂性,因此连接建立慢了 106%;
  2. 不支持容器热迁移;
  3. network policy 由 packet-based 转为了 connection-based;
  4. 只支持 TCP 这种状态协议

背景

容器网络一般有几种通信模型:

  • bridge mode
  • host mode
  • macvlan mode
  • overlay mode

image.png-25.1kB

其中:

  • bridge mode 只用于同 host 通信;
  • host mode 性能好,但是管理和部署非常复杂,实际上像 Kubernetes 都不支持这种模型;
  • macvlan mode 类似于硬件机制(例如 SR-IOV),macvlan 让容器 IP 可以在 host 网络路由,但增加了数据中心网络路由的复杂性,因此大部分 cloud provider 已经 block 了 macvlan mode;
  • 所以最终最流行的方案还是 overlay,这个类似于虚拟机,目前有很多这样的实现,例如 Weave、Flannel、Docker Overlay 等。

overlay 网络的核心之一是 vswitch,提供了:

  • network bridging,允许同 host 通信
  • network tunneling,跨物理网络通信

vswitch 一般用 ovs,使用 vxlan 作为 tunneling protocol。

然后就是各种 network policy(例如 access control、rate limit、 QoS 等),具体实现往往通过 iptables、ovs 等。

这种 overlay 网络的问题很明显,就是基于 packet,因此在 network namespace 要经过打包、封包,在 host 上协议栈要再来一次包识别、封包,到了对端则要再解包、识别,再解包再识别,因此 overhead 就很重了。

下面的表格展示了实测中 overlay 带来的性能成本:

WX20190423-125222.png-69.5kB

下图展示了通过 Weave 实测的 CPU 占用成本:

WX20190423-125411.png-52.6kB

可以看到 CPU 主要陈本在 soft irq 上。

当然现在有一些技术来解决这个问题,例如 packet steering,创建多个 queue,对应每个 CPU 核心,用 hash 来 map 报文和 queue,这样跨核心的成本可以下降很多,下面的表格展示了使用 packet steering 带来吞吐和延迟提升:

image.png-60.5kB

packet steering 提升了 91% 的 TCP 吞吐,但并不能缓解延迟,而且 CPU 占用也有影响。

整体来说,这种容器网络,特别是 overlay 这种我们可以统称为 packet-based virtualization,可以用下图概括:

image.png-112.3kB

设计

Slim 通过减少报文进协议栈的次数来优化,其思路可以简称为 connection-based virtualization:

image.png-95.2kB

设计时有几个设计目标:

  1. 方便部署,支持未修改的应用;
  2. flexible,支持各种 network policy;
  3. 安全,容器不能去获得物理网络的信息们不能直接在 host network 上创建连接,或者提高 traffic priority

image.png-37.4kB

上图是 Slim 的整体设计,有三个主要组件:

  1. 用户态有一层叫做 SlimSocket,与应用相连接;
  2. 用户态的 SlimRouter,跑在 namespace 里;
  3. 一个小的可选的内核模块 SlimKernModule,可以实现一些高级功能,例如动态更改 access control rules、安全配置等

这里面 SlimSocket 暴露了 POSIX socket 接口,来 intercept 应用的 socket 相关 sys call。当 SlimSocket 探测到应用尝试建立连接,就发送请求到 SlimRouter,SlimRouter 负责创建连接,再以文件描述符(fd)返回给应用,下面应用就是用这个 fd 来 send/receive 报文。因为 SlimSocket 是 POSIX 接口,Slim 会将 SlimSocket 动态链接到应用,所以应用不需要改动。

下面是解决控制策略、安全策略,如果再回到 packet based 方法的话就太低效了,因此这里的方法是在创建 connection 之前通过 SlimRouter 检查。如果是连接建立起来之后规则改变了,那么 SlimRouter 会扫描所有现有连接然后 remove 不能满足规则的 fd。

这种将 host 的 fd 直接返回给容器内的进程显然会引起很多安全方面的 concern,为此 slim 提供了一个安全模式,当开启安全模式时,SlimKernModule 会限制返回给 container 的 fd 的能力,SlimKernModule 有三个功能:

  1. track fd 在 container 中 propagate;
  2. 根据 SlimRouter 请求 revoke fd;
  3. 禁止这个 fd 的不安全的 sys call(getpeername、connect、setsocket),SlimSocket 会对非恶意的应用的模拟这些 sys call。

下图是 blocking io 为例演示连接建立的整个过程:

image.png-88kB

这部分在 slide 中很好的演示,上图也很清晰,我就不详细介绍了。

现在很多应用都是使用异步 API 了(select、epoll),而不是上面演示的同步 API,以 epoll 为例,epoll_create 会创建一个 meta fd,meta fd 实际表示了一个 fd set,应用使用 epoll_wait 来等待 fd set 的任一事件。在连接建立时,我们需要修改 epoll fd set 中的 fd。SlimSocket 会通过 epoll_ctl track epoll fd 和 epoll fd set 的对应。比如 epoll fd set 中的 fd acceptconnect 时,SlimSocket 会将原 fd 从 set 中移除,并增加 host namespace 的 fd 到 set。

这个方案有一个限制是对现有的 IT 工具不友好(host 上使用的 IT 工具),如果你想用 iptables 什么的搞一些之前的一些 packet-based 的策略的话,就不能用 Slim。

实现

大致上在上一节都提到过了,SlimSocket、SlimRouter、SlimKernModule 分别用了 1184 行 C、1196 行 C++ 和 1438 行 C,SlimSocket 使用 LD_PRELOAD 来动态链接到应用,SlimSocket 和 SlimRouter 之间用 Domain Socket 通信。非安全模式时,SlimRouter 用 sendmsg 直接传递 fd 到 SlimSocket,安全模式则经过 SlimKernModule 通过 fd duplication method。

SlimRouter 通过 JSON 文件获得 access control 的内容,提供一个 CLI 来 reload JSON。rate limit 和 QoS 通过 tc 实现。

SlimRouter 和 SlimKernModule 之间通过 procfs 中的 dummy file 通信。

SlimKernModule 需要替换 sys call table 中的函数指针,用 hash table 保存 taged fd 和 unsafe 的 sys call 列表( MatheMatrix:tagged fd 原文说类似于 OSDI 10′ https://www.usenix.org/legacy/event/osdi10/tech/full_papers/Enck.pdf,是 SlimKernModule 实现里很重要的内容,但我没有具体看)

评估

直接看图了,测试环境是 40G 网络,使用 iperf3、NPtcp、mpstat 这些开源软件评估。RFS 为 weave 打开 rfs 的性能。

image.png-144.5kB

下图展示了 network policy 的效果。

image.png-166kB

此外还有一些使用应用的测试结果,有 Memcache、Nginx、PostgreSQL、Kafka

image.png-155.3kB

image.png-279.2kB

image.png-200.5kB

image.png-212.4kB

此外作者还测试了容器迁移,Slim 会轻微的影响迁移性能。

image.png-156.7kB

讨论

  • 连接建立时间。Slim 会比较明显的延长连接建立时间,优化思路吗,就是尽量少关 SlimSocket,都需要一些方法;
  • 容器热迁移。前面虽然测了容器迁移,但其实不是热迁移,Docker 现在有实验项目 criu,但还比较弱,Slim 从设计上将,增加了容器热迁移的难度;
  • UDP。UDP 本质上可以支持,但问题是做网络策略就比较难了,另外就是 UDP 在数据中心的典型使用场景是减少连接建立时间,而 Slim 正好相反;
  • Packet-based 网络策略。这个实在不好做,真的需要的话只能用 overlay 网络;
  • LD_PRELOAD。这个其实对应用有要求,因为一些 system 可能假设了一些应用(例如 Go 编写的一些)是静态链接的;
  • Error code。一些情况下,error code 与 overlay 网络的结果不同,不过这个是可以解决的;
  • SmartNic。SmartNic 对容器网络可能帮助并不大,比如 Catapult 可能需要 Linux 的改变,SR-IOV 有 macvlan 一样的问题,FlexNIC 可能还行,但还是实验阶段。

TLA+ 笔记

很久以前学过一些 Prolog,当时主要是为了学习人工智能和数理逻辑。TLA+ 与之有一点点像,Prolog 可以用来处理各种规划问题、一阶逻辑推理,TLA+ 可以用来设计各种分布式、异步系统,搭配 TLC(model checker) 来做验证——他们的设计目标都不是解决通用的编程问题,而是通过数理逻辑解决一些特定领域问题。

TLA+ Tools 包含很多工具,可以在这里下载,大部分人都是使用这个 Tools:
http://lamport.azurewebsites.net/tla/standalone-tools.html?back-link=tools.html

在里面的链接指向的 github 地址里,有 Windows、Linux、Mac 的二进制版本,良心。

在看 TLA+ Community Meeting 2018 的时候还看到了一个形式验证语言(其实是 Python 的扩展)DistAlgo,整体思路和 Demo 看起来特别棒,就是目前各种材料和介绍还是相对少,所以我没有继续研究下去,有兴趣和时间的话,看看 DistAlgo 也挺好。

下面是笔记。


介绍

分布式系统的正确性特别难验证,所以做出了 TLA+,因为 2015 年 AWS 在 CACM 发了一篇 How Amazon Web Services Uses Formal Methods 引起了很多人注意,年底 TLA+ 作者之一的 Langworthy 和 Lamport 找微软高层推动 TLA+ 在微软落地,一定程度上得益于 AWS 的文章和 Lamport 2015 年拿到图灵奖带来的影响力,Satya 发邮件说 Go go go。

2016 年开始微软在内部办了一共三天的 TLA+ School,教学了很多微软工程师 TLA+,一共运行了三次,到第四次时,Lamport 终于受不了重复给别人讲 TLA+ 基础,于是做了教学视频,没错就是很火的这个视频:http://lamport.azurewebsites.net/video/videos.html

image.png-63.4kB

所以从 2018 年开始,School 变成了 Workshop,目的从基础教育提升到了继续教育,特别是生产实践带来的反馈。

现在 TLA+ 在微软内部应用在 Service Fabric(类似 kubernetes)、Azure Batch、Azure Storeage、Azure Networking、Azure IoT、Cosmos DB。

(本节主要来自 http://tla2018.loria.fr/contrib/langworthy-slides.pdfhttps://www.youtube.com/watch?v=ifFfxRCX_jw

Learn TLA+ 笔记

主要是阅读 Learn TLA+ 的笔记,这个写了很多基础的练习和介绍,先是 PlusCal 的内容,在 TLA+ Tools 上用 ⌘+T 即可翻译成 TLA+,不过 PlusCal 并不能完全等价 TLA+。

Introduction & PlusCal

基本使用流程很简单,先在 modules 里建 module,写 PlusCal,转成 TLA+,再在 models 建 model,写条件,运行检查即可。

PlusCal 的基本语法:

---- MODULE module_name ----
\* TLA+ code

(* --algorithm algorithm_name
begin
\* PlusCal code
end algorithm; *)
====

每个文件里只能有一个 PlusCal 算法。

举个例子:

---- MODULE transfer ----
EXTENDS Naturals, TLC

(* --algorithm transfer
variables alice_account = 10, bob_account = 10, money = 5;

begin
A: alice_account := alice_account - money;
B: bob_account := bob_account + money;

end algorithm *)
====

里边 variable 即变量,声明变量使用 =,算法实现中使用 :=,A、B 是标签,定义了算法步骤,一个标签里的内容被视作一个事务。{a..b} 表示整数 a 到 b 的整数集合,\in 即集合论里的 in。

基本的运算符:

image.png-24.7kB

可以通过 process 来设计一个多线程程序,比如这样:

---- MODULE Transfer ----
EXTENDS Naturals, TLC

(* --algorithm transfer
variables alice_account = 10, bob_account = 10,
          account_total = alice_account + bob_account;

process Transfer \in 1..2
  variable money \in 1..20;
begin
Transfer:
  if alice_account >= money then
    A: alice_account := alice_account - money;
       bob_account := bob_account + money;
end if;
C: assert alice_account >= 0;
end process

end algorithm *)

MoneyNotNegative == money >= 0
MoneyInvariant == alice_account + bob_account = account_total

====

其中通过类似 MoneyNotNegativeMoneyInvariant 这样的语句来帮助添加一个全局的一致性检查 ,invariant 可以在 TLC 里指定,来检查全局的一致性:

image.png-169.8kB

上面的代码在并发时显然是有问题,所以 TLC 可以检查出来它:

image.png-615.8kB

展开 Error Trace 可以看到状态转移记录:

image.png-205kB

可以看到并发执行时,money 同时有两个值,由于转账时没有对账户加全局锁,所以账户总大于零这个断言被 break 了。

这里都是 P-Syntax,PlusCal 还有 C-Syntax 的格式,具体参考 https://lamport.azurewebsites.net/tla/p-manual.pdfhttps://lamport.azurewebsites.net/tla/c-manual.pdf

PlusCal 中是有 print 的,比如下面这个例子:

EXTENDS TLC

(* --algorithm hello_world
variable s \in {"Hello", "World!"};
begin
  A:
    print s;
end algorithm; *)

这里的 User Output 打出了内容:

image.png-419.6kB

PlusCal 的 if、while、goto 都和一般语言很像,就不赘述了。

Model Overview 里的 “no behavior spec” 一般很少用,运行后在 result 页可以使用 “evaluate constant expression”,然后可以写点东西来验证 TLA+ 是如何运行的。

最后是引入 divergent behavior,让系统在一个步骤里可以做不同的事情,对于单进程 PlusCal,可以通过 witheither 来引入。

either 简单地说就是没有条件的 if,可以让 TLC 知道这里有两种路径,都可以执行以下:

variables x = 3, i = 2;
begin
while i > 0 do
  either 
    x := x + 2;
  or 
    x := x * 2;
  end either;
  i := i - 1;
end while

结果是这样的:

image.png-15.2kB

另一种是 With:

with a \in {1, 2, 3} do
  x := x + a
end with;

结果是这样:

image.png-18.9kB

The design of a practical system for fault-tolerant virtual machines

这篇文章是 MIT 6.824 课程安排的一篇阅读材料。

我 Fork 了别人整理的 MIT 6.824 的课程材料,关于这篇文章的内容可以在这里找到:https://github.com/MatheMatrix/MIT-6.824-Distributed-Systems/tree/master/Lectures/LEC04

下面是笔记。


摘要

VMware 在 2010 年发布了这篇文章,主要描述它们在 vShpere 4.0 上实现的虚拟机高可用方案,这是一个商用的、企业级的方案,虚拟机性能下降在 10% 以内,虚拟机同步需要 20M 左右带宽。文章提到让这样一个系统支撑企业应用除了复制虚拟机的指令外,还有很多其他问题。

介绍

实现高可用的基本思路是主备,主备最简单的想法就是复制主的所有状态,包括 CPU、内存、IO。但是这个方案无疑需要非常大的带宽。
另一种方法是复制状态机思路,简单的说,这个思路就是把虚拟机当作一个确定状态机,两边先保持一个一致的初始状态,然后保证它们能够一样的顺序接收一样的指令。因为总有一些操作造成的结果不是确定性的,因此还需要额外的工作来保持同步(主要是内存)。

这个思路在物理机上无疑很难实现,但是在虚拟机上就好做很多,因为虚拟机就是一个定义的很完善的状态机,其所有操作、设备都是虚拟化的。但是相比物理机,虚拟机自己也有一些非确定性操作,例如读取时间和发送中断,这就是为什么我们刚才说需要额外操作来保持同步。

VMware vSphere FT 基于确定性重放(deterministic replay),但是增加了必要的额外协议和功能来保证系统功能完整。到写这篇文章时,FT 生产版本还只能支持单 CPU 虚拟机,因为对多 CPU 来说,几乎每次读写共享内存都是非确定性操作,由此带来巨大的性能损失。

这个系统的设计目标只处理 fail-stop 错误,也就是系统一旦出错则立即 stop,而且正确的服务器立刻知道它 stop 了。(分布式系统中的各种错误可以参考:http://alvaro-videla.com/2013/12/failure-modes-in-distributed-systems.html, fail-stop 几乎是最简单的错误类型)

FT 设计

首先我们将备份虚拟机运行在一个和主虚拟机不同的物理机上,备份虚拟机与主虚拟机保持同步和一致但有一个很小的时间差,这时我们称这两个虚拟机处于 virtual lockstep。
两个虚拟机的虚拟磁盘位于共享存储上(例如 FC 或 iSCSI,后面会讨论非共享存储的场景),只有主虚拟机会在网络上对外通告,所以所有网络输入只会进入主 VM,其他输入例如键盘和鼠标也是一样只到主虚拟机。

所有主虚拟机收到的输入,会通过网络(logging channel)来发到备份虚拟机。VMware 通过特定协议做收到确认,来保证主虚拟机失效时不会有数据丢失。

为了检测主虚拟机或备份虚拟机失效,VMware 会在两个服务器上跑心跳,同事监控 logging channel 的流量。

确定性重放(Deterministic Replay)的实现

虚拟机有大量的输入,包括:

  • 收到网络报文
  • 磁盘读
  • 键盘鼠标输入

还有大量非确定性事件(比如虚拟中断)和非确定性操作(比如读取 CPU 时钟计数器)都会影响虚拟机状态。

难点有三处:

  • 正确捕捉所有的输入和不确定性
  • 正确的在备份虚拟机上应用这些输入和不确定性
  • 确保不太多影响性能

此外,x86 处理器有很多复杂操作会造成未定义的、造成不确定性的副作用。

VMware 确定性重放(deterministic replay)(2007 年的这篇文章更详细的做了介绍:http://www-mount.ece.umn.edu/~jjyi/MoBS/2007/program/01C-Xu.pdf)解决了上述的前两个问题。

确定性重放可以记录虚拟机的所有输入和所有可能的非确定性,并以流的方式记录到一个日志文件里。通过读取这个文件,就可以对虚拟机操作进行重放,同时这个文件还记录了足够的信息来还原非确定操作造成的状态改变和输出。例如定时器、IO 完成中断这些非确定性事件会记录发生在具体哪个指令之后来保证重放时可以让事件发生在相同的位置。

FT 协议

上面说到确定性重发是记录日志的,但很好理解在 FT 实现里,我们不可能这么做,取而代之的是通过 logging channel 来把这些 log entry 发送到备份虚拟机。
备份虚拟机要实时的重放,这里最重要的要求是:

Output Requirement:如果备份虚拟机取代了主虚拟机,那么备份虚拟机要按照之前主虚拟机的输出保持完全一致的继续输出到外界

这里很重要的一点是备份虚拟机需要保持一致的对外输出,而不是一致的运行——一致的运行是不可能的,因为当主节点宕机时,肯定会有一些不确定性事件(比如中断)造成备份虚拟机与主虚拟机运行的不一致,而这些不确定性可能还没来得及同步,所以怎么保证主虚拟机宕机时,备份虚拟机总能够接得住主虚拟机的输出,让外界以为没有发生中断/切换呢?

比较简单的思路就是延迟对外输出(例如网络报文),就像这样:

在主虚拟机对外输出前,必须先要把所有的日志发送到备份虚拟机,备份虚拟机确定可以重放出主虚拟机输出时的状态时,主虚拟机才可以对外输出。这样如果主虚拟机宕机,备份虚拟机可以正确达到对外的一致状态。反之,如果备份虚拟机没有收到足够的日志,那么备份虚拟机会分叉。

延迟输出并没有暂停虚拟机,只需要在发送输出前延迟即可,虚拟机可以继续运行,这里和之前的容错系统是不同的(https://courses.mpi-sws.org/ds-ws18/papers/bressoud-hypervisor.pdf, http://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/papers/ftjvm.pdf

除非主虚拟机输出时引入两阶段提交,否则无法保证 fail-over 时无法保证输出只发生了一次,不过比较幸好的网络或磁盘 IO 上这个不是大问题。

宕机检测与主备切换

当备份虚拟机宕机时,主虚拟机必须立刻退出记录模式,不发送日志(不然会停止输出);主虚拟机宕机时,备份虚拟机则要立刻恢复正常模式,消费完 logging channel 的所有日志然后开始进行执行。此外 VMware FT 还会自动广播 MAC 等来帮助外界知道虚拟机的位置,还需要做一些磁盘 IO(后面描述,主要是磁盘并行和 DMA 的问题)

VMware FT 使用 UDP 来做心跳检测,并且不断监控 logging channel 的流量情况、备份虚拟机的 ack 情况——因为定时器中断的缘故,操作系统应该是总会有日志的。

不过这些检测手段都解决不了脑裂问题,因此 VMware 要求虚拟机一定运行在共享存储上,通过 test-and-set 来防止脑裂。

具体实现

上面只是大概设计,真正将系统可用、鲁棒、自动化还需要很多细节性的工作。

启动和重启备份虚拟机

这里讲 VMware 如何启动一个初始状态一致的虚拟机,对于 VMware 来说可以利用之前的 VMotion。

另一个问题是如何选择物理机来启动备份虚拟机。

管理 Logging Channel

如上图,两边各有一个 log buffer,当备份虚拟机 log buffer 为空时,需要暂停备份虚拟机,反之主虚拟机 log buffer 满时需要暂停主虚拟机。
因此,要非常小心的设计来规避主虚拟机 log buffer 满的情况。为此 VMware 设计了一个机制——当备份虚拟机执行跟不上主虚拟机的速度时,会降低主虚拟机的 CPU 性能,当能跟上时,再慢慢提高主虚拟机的性能,有点像滑动窗口一样。

FT 虚拟机上的控制操作

在 FT 虚拟机上的控制操作也需要考虑,例如所有的资源管理变化(比如调整虚拟机 CPU)都需要同步操作两个虚拟机,因此在 logging channel 里需要加特殊的一些控制 entry。
简单地说,除了虚拟机的 VMotion 之外,所以操作都需要同步。

不过这不意味着 VMotion 不需要修改:

  1. VMotion 时也要注意不能迁移到同一物理机;
  2. VMotion 时,备份虚拟机到主虚拟机会有中断重连发生,需要专门处理,特别是迁移备份虚拟机,因为需要主虚拟机控制对外住 IO。

磁盘 IO 实现上的问题

IO 在实现上有不少问题:

  1. 磁盘操作可能是异步、同步的,这样不同的 IO 可能请求了磁盘的同一位置,造成不确定性;
  2. 因为磁盘操作可能是通过内存 DMA 的,因此内存的相同位置的读写也会带来 IO 的不确定性;
  3. 主虚拟机 IO 发出但未完成时宕机,备份虚拟机升级为主虚拟机后无法知道 IO 究竟是否成功。

解决方案是:

  1. 检测竞争 IO,强行按照主虚拟机的情况顺序化
  2. 对目标磁盘 IO 相关内存做检测和页保护,页保护可以让虚拟机在访问还没完成的 IO 的内存 trap,然后 IO 完成后再恢复虚拟机。但是修改 MMU 的页保护时个非常昂贵的操作,因此 VMware 引入了 bounce buffer。bounce buffer 是一快和大小和所需要磁盘操作的内存大小相同的临时缓存,可以 buffer 住相同位置的 IO 操作。A disk read operation is modified to read the specified data to the bounce buffer, and the data is copied to guest memory only as the IO completion is delivered. Similarly, for a disk write operation, the data to be sent is first copied to the bounce buffer, and the disk write is modified to write data from the bounce buffer;
  3. 返回 IO 失败可能导致 Guest OS 无法正确处理,所以只好在备份虚拟机升级为主虚拟机的过程中重发 IO。

网络 IO 实现上的问题

为了优化性能,网络很多代码都是异步的,这在 FT 中会带来不确定性,所以很多优化诸如异步更新 Ring Buffer、异步收取 transmit queues 这些要禁用掉。
但直接禁用掉性能又肯定不行,为此需要优化中断机制,通过减少中断。
还有之前我们说过主虚拟机 Output 前需要受到备份虚拟机的 Ack,这个也很损耗性能,解决方案是减少这个延时,其中核心解决方案是减少了备份虚拟机收到 log 到回复 ack 的延时。

设计上的一些其他思路

共享磁盘 vs 非共享磁盘

如果是非共享磁盘,那么备份虚拟机将写入到不同的虚拟磁盘里,类似下图这样:

这样 Output Rule 这个设计也需要改变。优点是避免了共享存储的成本、可用性问题,可以想象一下远距离 FT 之类的场景,但是缺点是两个虚拟磁盘必须在刚开始时完全一致(包括内容和行为),而且需要考虑不同步时如何 resync。另外就是脑裂的问题,需要考虑用第三方作为 tiebreaker。

在备份虚拟机上直接读取磁盘

在我们的默认设计里,无论共享磁盘/非共享磁盘,虚备份虚拟机都不会读取自己的虚拟磁盘,因为磁盘读被考虑为一个输入,所以通过 logging channel 来同步。
可以考虑让备份虚拟机执行磁盘读请求,这样就可以减少 logging chennel 的负载,但这样可能降低备份虚拟机的性能,而且要考虑主虚拟机读取成功、备份虚拟机读取失败的场景,最后这里还有主虚拟机、备份虚拟机潜在的竞争问题,总之问题不少。VMware 在测试性能时测试了这个方案,对真实应用来说,会有轻微的性能下降,但会有显著地 logging chennel 带宽的减少。

性能评估

在两个服务器上每个运行了 8核8GB 的内存的虚拟机,服务器用万兆网络直接连起来,不过实际用了远小于 1Gb 的带宽。存储是 EMC Clariion 4 Gb FC 存储。

基本评估

虚拟机空闲时,大概会用 0.5~1.5 Mb 带宽,当有大量网络 IO 时,logging channel 的带宽会显著增大:

网络性能

网络的挑战很大:

  1. 高速网络会带来海量中断
  2. 海量报文都通过 logging channel 同步
  3. 海量报文的 Output Rule 造成大量延迟

具体参考上面的图

相关工作

我这里就略去了,大家可以直接看原文,此外后面 QEMU 发展了 COLO,又诞生了很多文章,可以在网上搜到,还有 VMware 这里依赖了它之前的确定性重放和 VMotion 的技术,感兴趣的话也需要再去查阅文献。

总结

有几点:

  1. 因为 FT 所需要的带宽往往并不那么大,因此长距离 FT 也是可能的,可以通过压缩等方法进一步减少 logging chennel 的带宽,但可能增大 CPU 负载;
  2. 确定性重放的设计只能在单 CPU 虚拟机上保持高效,多处理器是另一个可能的探索方向
  3. 目前针对的 fail 场景是 fail-stop,另一个可能的探索方向就是扩展到部分硬件失效,比如网络失效或者供电冗余失效等等

使用 Linux Bridge 搭建 VXLAN Overlay 网络

前言

使用 Linux Bridge 搭建 VXLAN 网络不是件很难的事,但是目前确实有一些小坑,这里记录一下。

本文会介绍:

  • 如何使用 Linux Bridge 搭建一个 VXLAN Overlay 网络
  • 如何用 Namespace 模拟虚拟机验证通信
  • Linux VXLAN DOVE Extension 带来的新参数

本文不会介绍:

  • VXLAN 是什么
  • 现代 VXLAN 协议的发展与控制平面的演化

命令

没有多大难度,直接介绍使用的命令。

iptables -D INPUT -j REJECT --reject-with icmp-host-prohibited
# 在我的环境里总会有默认的两条 reject 规则,好烦,先干掉

ip link add vxlan21 type vxlan id 100 dev eth0
# 先添加 vxaln 接口,这个是比较简洁的版本(dev eth0 可以去掉),你可以依照喜好添加一些参数,比如:
# local 10.0.121.180,指定一个本地地址,linux 下的 VXLAN 接口可以不指定 IP 地址、网卡,也可以指定,看需要设置;
# group 239.1.1.1 使用组播模式,239.1.1.1 即为组播地址;
# dstport 4789 指定 vxlan 端口,如果不写的或者写 dspport 0 的话系统会自动使用 8472——根据 IANA 的[标准][1]现在应该使用 4789,包括 VMware NSX 6.2.3 开始也默认从 8472 该到了 4789;
# srcport 32768 61000 可以指定源端口的范围;
# 此外还有一些 DOVE Extension 带来的参数,放在后面介绍

ip link set vxlan21 up
# 将接口 UP,系统会起一个 UDP Socket 监听相应端口

brctl addbr lb-int
ip link set dev lb-int up
brctl addif vxlan21
brctl addif lb-int vxlan21
bridge fdb append to 00:00:00:00:00:00 dev vxlan21 dst 10.0.56.18
# 配置一个对端 VTEP

ip link add veth20 type veth peer name veth02
ip link set veth02 up
brctl addif lb-int veth02
ip netns add veth2
# 创建 namespace 和 veth 设备模拟虚拟机

ip link set dev veth20 netns veth2
ip netns exec veth2 ip a add dev veth20 192.168.0.12/24
ip netns exec veth1 ip link set veth20 up
ip netns exec veth2 ping 192.168.0.11
# 如果你在另一台 hypervisor(VTEP)做好了相应操作模拟了 192.168.0.11 地址,此时应该已经可以通讯了

DOVE Extension

DOVE 的全称是 Distributed Overlay Virtual Ethernet,是从 Linux 3.8 开始引入到内核,目的是方便为 Linux VXLAN 接入控制平面,提升效率。

引入 DOVE 后目前在创建 VXLAN 设备时可以添加下面几个参数:

  • l3miss,在 drivers.net.vxlan.vxlan_xmit 中,如果 VXLAN 设备开启了 Proxy,会尝试进行 ARP 压缩(drivers.net.vxlan.arp_reduce,尽量将 ARP 广播范围压缩到本地),如果此时查找不到这个 IP 对应的 ARP 记录的话,就会触发 l3miss,发送一条消息(netlink)到 userspace,这时 agent (userspace 程序,例如 docker overlay)可以直接添加一条 Neighbor 信息,以替代广播;
  • l2miss,VTEP 的 FDB 不存在目的 MAC 所对应的 VTEP IP 时,触发 l2miss,通过 netlink 发送一条消息到 userspace 替代复制到所有 VTEP;
  • proxy,在上面 l3miss 中说过了,用于做 ARP 本地压缩;
  • leraning,学习远端虚拟机的 MAC 地址,就是 VXLAN 的 flood and learn;
  • ageing,上面学习到本地 FDB 的虚拟机的 MAC 的超时时间;
  • maxaddress,FDB 表的最大条目数;
  • rsc,也就是 L3 switching,直接 switch 到目的地址,不需要经过路由(作者本人没有测试过,如果你做了测试欢迎交流)。

当然了,我说的都是错的,我建议你还是直接看代码。

如果觉得看 vxlan.c 比较困难的话,可以看 DOVE 的 Patch:http://lists.openwall.net/netdev/2012/11/15/96。

Reference

  1. Rami Cohen, et al: Distributed Overlay Virtual Ethernet (DOVE) integration with Openstack,
    IP/IEEE International Symposium on Integrated Network Management (IM 2013), 29-
    -May-2013, pp 1088-1089

  2. Etsuji Nakai: How VXLAN works on Linux, https://www.slideshare.net/enakai/how-vxlan-works-on-linux

  3. Joe Julian: How to configure linux vxlans with multiple unicast endpoints, https://joejulian.name/blog/how-to-configure-linux-vxlansith-multiple-unicast-endpoints/

  4. Thomas Richter: Software Defined Networking using VXLAN, LinuxCon Edinburgh 21-Oct-2013

  5. 刘世民: Neutron 理解(14):Neutron ML2 + Linux bridge + VxLAN 组网, http://www.cnblogs.com/sammyliu/p/4985907.html

写给 OpenStacker 的 ZStack 指南(一)

前言

相比 OpenStack 而言,ZStack 全异步、追求高稳定性和安全的代码是相对难读的,所以本文希望能通过一些简单的例子和与 OpenStack 的一些对比,将 ZStack 的特点、代码的原理尽量描述出来,降低 ZStack 的入门门槛。欢迎更多 OpenStacker 参与 ZStack 或从 ZStack 的代码中汲取经验。

从执行一个 API 说起

对一个业内人士,观察在页面上一个指令如何逐步被执行,无疑是最直观深入的了解方式。

第一步 前端

打开 Mevoco/ZStack 的界面,可以发现基本设计思路与其他 IaaS 或 OpenStack 是基本类似的,然而打开开发者面板就会发现大有不同。

OpenStack 的面板一般通过 HTTP 到 Web 后端,可能是一个像 Horizon 的中间件,也可能是直接把请求发到后面的具体服务的 API 服务,例如 nova-api 或 neutron-server。当然中间可能还会有负载均衡器或高可用之类的设施。

image_1b6dgt82i1rl0md5j8t8va1v4m9.png-305.3kB

图1 在OpenStack的Horizon面板上创建虚拟机出发的Post请求

而在 ZStack 的面板中开发者面板是很干净的,打开之后无论什么操作是不会触发 HTTP 请求的,数据和请求都在 WebSocket 传递,比如我们在面板上创建一个虚拟机,可以看到通过 WebSocket 发送一个 frame,一个 org.zstack.header.vm.APICreateVmInstanceMsg 的消息,后面跟着的是创建的参数。

image_1b6dhje891gd7rj61e551r9hv3vt.png-209.3kB
图2 ZStack面板上创建虚拟机发出的WebSocket帧

Continue reading

为什么在 VyOS(Vyatta)中 commit 会很慢

最近就这个问题调查了蛮久,其实原因比较显然,在看到 strace 的结果就已经明白了大半,但是本着求(xia)知(zhe)探(teng)索的想法,仔细验证了代码逻辑和时间(新技能 get!给 C++、Perl 混合代码调试性能),攒出了这篇文章。

ZStack 是一个开源的 IaaS 软件,架构和性能都很优秀,可以在 103 秒内并发创建 1000 台虚拟机,可惜这个数据是在扁平网络下测试得到的,一旦用上云路由网络,单个虚拟机的启动时间会延长到七秒左右。

我们现看下看下实际的占用时间,我在 vyatta 的代码里添加了日志(Repo 是 https://github.com/vyos/vyatta-cfg )综合 zstack、zstack-vyos、vyos 的日志可以看到大概是这样的(注意 zstack 的日志时间精度只提供到秒,没有毫秒):

2017-02-13 13:22:08 start executing flow[NetworkServiceManagerImpl.java:apply-network-service-DHCP]

2017-02-13 13:22:08 DEBUG [RECV] /setsnat
2017-02-13 13:22:09 DEBUG [HTTP POST][ASYNC REPLY TO /setsnat]

2017-02-13 13:22:09 DEBUG [RECV] /adddhcp

# 以下为 vyos 日志
2017-02-13 13:22:09:458 Entered cli_bin::doCommit
2017-02-13 13:22:10:216 Entered commit::doCommit
2017-02-13 13:22:10:901 notify other users in config mode
2017-02-13 13:22:12:260 cs.commitConfig complete
2017-02-13 13:22:12:557 Exit commit::doCommit
2017-02-13 13:22:12:557 Normal exit cli_bin::doCommit
# 退出 vyos 日志

2017-02-13 13:22:12 DEBUG [HTTP POST][ASYNC REPLY TO /adddhcp]

2017-02-13 13:22:12 DEBUG [RESPONSE] to /setdns
2017-02-13 13:22:12 DEBUG [HTTP POST][ASYNC REPLY TO /setdns]

2017-02-13 13:22:12 DEBUG [SimpleFlowChain] (zs-thread-81) [FlowChain: apply-network-service-to-vm-13d1359b8bd34a05a91f61dedb112e96] successfully executed flow[NetworkServiceManagerImpl.java:apply-network-service-DHCP]

可以把时间与调用关系结合起来做成一张图:

VyOS_Commit
Continue reading