0%

0. 前言

VMware公司在2010年发表了一篇有关虚拟机容错的论文:《The Design of a Practical System for Fault-Tolerant Virtual Machines》。同时,它也是MIT6.824 LEC4的Preparation Read。本文将结合课程简单介绍论文内容。

1. 主/备份

实现服务器容错的一种通用方法是主/备份(primary/backup) 方法,当主服务器失效,备份服务器可以接管主服务器的工作。

为了保持主备状态同步,有2种方法:

  • **状态传递(State transfer)**。将主服务器上的所有状态(包括CPU、内存等等)都发送给备份服务器。这种方法能保证主备状态一致,但每次需同步大量数据,会占用大量宽带。

  • **复制状态机(Replicated state machine)**。主备服务器一开始处于相同状态,对于每一条发送给主服务器的输入请求(比如将一个数加1),主服务器会发送给备份服务器,它们以相同顺序执行输入请求,从而保持同步。这种方法同步的信息较少,效率更高。但是,对于一些不确定请求,比如获取当前时间、获取随机数、多核计算,主备服务器执行结果可能并不相同,还需要额外的操作来保持同步。

VMwareFT论文种使用了复制状态机来实现容错。

2. 基本设计

1

主备虚拟机运行在不同的机器上,它们共享一个磁盘(Shared Disk),主VM接收到的输入都通过日志通道(Logging channel)发送给备份VM。主备VM都执行相同操作,但只有主VM的输出才返回给客户端。

系统通过相关服务器之间的心跳和日志通道上的流量监控,来检测主备VM是否失效。

确定性重放

对于不确定事件或操作,比如中断、获取时间等,可能会导致主备VM状态不一致。

VMware确定性重放(deterministic replay)机制,能够捕获所有输入和所有可能不确定输入,并记录到日志文件,通过读取日志,备份VM可以准确地重放执行。

对于不确定输入,必须记录足够的信息来保证重放。当然论文中并未介绍是哪些信息,一种可能的方式是直接记录执行结果,备份VM只需复制结果即可,而不需要再次执行。而对于多核计算,暂时没有有效机制来保证执行结果一致,因此论文中的虚拟机VM都规定是单核的

(注:这一节为什么讲了跟没讲一样)

FT 协议

考虑一种情况:VM上有一个数A值为10,客户端请求将A+=1并返回结果,主VM接收请求后执行+1并返回11,但它正要将该请求告诉给备份VM时宕机了。备份VM接替了主VM,但由于备份VM并未收到请求,A的值依旧是10。此时,客户端再请求将A+=1并返回,它再次得到11,显然这是不正确的。

为了防止这种情况的发生,论文设计了一条输出规则:对于需要输出的请求,主VM会等备份VM确认收到请求后(备份VM会返回ACK),再将输出返回。同时,主VM只是延迟输出,并不会阻塞后面的任务(异步)。

1

但是,规则并不能保证结果只输出一次。比如:当主VM收到备份VM的ACK后,正要返回输出,但突然宕机了。备份VM接替之后,并不知道主VM是否已经返回输出,所以它会将最后一次输出再返回一次(其实之前的输出备份VM都不知道是否返回吧?)。当重复输出并无大碍,比如:对磁盘同一个位置重复写,一个数据包发两次(TCP能够检测重复的数据包)。

检测和故障响应

主VM和备VM之间会通过UDP心跳监控日志通道流量来检测对方服务是否正常,若停止的时间超过阈值,就说明出现故障。

不过这种检测方法并不能避免脑裂问题(split-brain) 。当备份VM长时间没有收到主VM的心跳和日志消息,可能是主VM宕机,也可能是网络问题。如果是因为暂时的网络问题,此时备份VM若顶替主VM,那网络上将出现2个主VM。

为了解决这个问题,VMware在共享磁盘上设置了test-and-set的原子操作 ,类似于一个锁,只能被一个VM获取,而只有拿到这个锁才能对共享磁盘进行操作。

3. FT实际应用

创建备份VM

VMware使用VMware vSphere现有的VMotion功能:将一个运行中的VM克隆到新机器上,而VM只需暂停不到1秒的时间。

同时,VMware vSphere实现了一个集群服务,它会根据主VM的备份请求选择合适的机器,然后通过VMotion进行克隆,这过程只需几分钟。

(细节啥也没说)

管理日志通道

为了管理监控日志通道,管理程序为日志通道维持了一个日志缓冲区,主VM向缓冲区写,备份VM从缓冲区读。

当缓冲区被填满(主VM写太快,备份VM读太慢)时,主VM将会停止执行,等待缓冲区有空闲。显然,这会影响客户端体验。为此,当缓冲区日志太多时,管理程序会降低主VM的执行速度(比如分配更少的CPU资源),等待备份VM消化缓存,更上日志进度。

当然,这种主VM减速很罕见。

4. 个人总结

不同于数据库备份,虚拟机这种整个操作系统的备份确实困难且复杂。因为它存在许多不确定操作,比如中断、多核并行等,复现难度大。

个人认为, 对于操作繁多且复杂的场景,应该避免做操作的同步,而应该做数据状态的同步 。比如,客户端请求对A进行+1操作,那么不应该让备份机器同步执行这个+1操作,而应该将A进行+1的结果同步给备份机器。当然,这其实就是在状态转移和复制状态机两种方式间做抉择。

这篇论文虽然并不详细,也没有带来多大的影响,但也有值得借鉴的点:

  1. 主VM需要确定备份VM获取到请求后,再返回给客户端。不过要是备份VM执行失败了怎么办?

  2. 通过外部权威来解决脑裂问题。感觉不如超半数投票?

0. 前言

2000年前后,随着互联网的飞速发展,单机的存储和计算能力早已达到瓶颈,急需通过增加机器数量来提高整体性能。但是,1+1并不大于2,机器数量的增加带来了许多新的问题:网络延迟、机器宕机、数据不一致等等。正是为了解决这些问题,Google在2003-2006年间先后发表了3篇论文《GFS》、《MapReduce》、《Bigtable》,分别解决了大规模数据的存储(非结构化)、计算、索引(结构化数据/数据库),这三篇也被称为Google三驾马车,鉴定了分布式大数据时代的基础。后来的开源项目Hadoop中,HDFS参考了《GFS》,MapReduce参考了《MapReduce》,HBase参考了《Bigtable》。

GFS首先被提出,它在大规模分散的机器上,实现了类似Linux文件系统的分布式存储系统。单台机器读写数据的性能有限,对于数亿GB的海量,肯定不能存放在单台机器上,而应将数据分割存储到多台机器上。同时,还需考虑机器宕机、磁盘损坏的问题,对同一份数据应做多个备份。如此又会出现许多新问题:如何在多台机器中找到用户想要的数据?如何保证系统在部分机器失效的情况下仍能正常运行?如何保证多个备份数据的一致?如何保证较高的读写性能?这些问题都将GFS中得到解决。

阅读全文 »

0. 前言

如果说比特币是区块链1.0,那以太坊就是区块链2.0。比特币的出现,让大规模、去中心化的电子货币交易成为可能。而以太坊的出现,让任何人都能构建去中心化的合约与应用。根据白皮书的标题,我们也可以清晰地知道:比特币的核心是点对点电子货币,而以太坊的核心是智能合约与去中心化应用。

阅读全文 »

前言

当下,分布式是一大热门,常用场景比如分布式数据库等。在错综复杂的分布式网络环境中,不同节点间的数据(也被称为状态)很可能不一致,原因比如:传输时数据丢失、节点崩溃等等。分布式中所要解决的一大问题,就是节点间如何达成共识,也就是如何保证各节点数据的一致性。最容易想到的方法是,选择一个主节点,其它节点与主节点状态保持一致。但致命的问题在于,主节点崩溃了怎么办?如何选取新的主节点?如何保证新主节点的数据是正确的?这些都需要一个完整的算法机制。

Raft是当下最流行的崩溃容错共识(CFT)/分布式一致性算法之一,被广泛应用于分布式数据库中,比如k8s中的etcd。本文主要是对Raft论文中关键内容的摘取翻译,并附加自己的理解。

Raft论文:Ongaro D, Ousterhout J. In search of an understandable consensus algorithm[C]//2014 {USENIX} Annual Technical Conference ({USENIX}{ATC} 14). 2014: 305-319.

阅读全文 »

论文:Dean J, Ghemawat S. MapReduce: Simplified data processing on large clusters[J]. 2004.

前言

MIT6.824分布式课程第一课的课前阅读要求。

MapReduce是谷歌提出的面向大规模数据的分布式并行计算模式,给大数据并行计算带来了革命性影响,MapReduce也是著名的Hadoop中相当重要的一部分。

阅读全文 »

论文:夏清,窦文生,郭凯文,梁赓,左春,张凤军.区块链共识协议综述.软件学报,2021,32(2):277−299. http://www.jos.org.cn/1000-9825/6150.htm

前言

共识是指:群体中各个独立的参与者,就某件事情达成一致。比如:公司的董事会根据某个决策,进行讨论、投票、最终达成一致的过程,就是一种共识。根据是否存在恶意参与者 ,共识可分为崩溃容错(crash fault tolerant,简称CFT)拜占庭容错(Byzantine fault tolerant,简称BFT) 两大类。崩溃容错是指:在不存在恶意节点的情况下,即使某个节点崩溃,系统也能正常运行并达成共识,它常用于中心化的分布式数据库中。而拜占庭容错,名字来源于著名的拜占庭将军问题,指存在恶意者的情况下,整体还能否达成正确的共识,比如:将军们的军事议会中混进了叛徒,决策是否会被影响。

共识作为区块链的核心技术,一直是区块链的重中之重。毫不夸张地说,比特币成功的关键是它独到的共识机制。而正是比特币的共识机制,使得大规模、分布式、拜占庭容错共识成为了可能。因此,了解区块链相关共识协议是研究区块链不可或缺的一步(当然也为了完成读书报告任务)。

本文主要以解读《区块链共识协议综述》为主,大多内容提炼自原文。论文虽是中文,但愚以为质量可观,感兴趣可阅读原文。

阅读全文 »

1. 引言

自然语言是指人类日常使用的语言,比如:中文、英语、日语等。自然语言灵活多变,是人类社会的重要组成部分,但它却不能被计算机很好地理解。为了实现用自然语言在人与计算机之间进行沟通,自然语言处理诞生了。自然语言处理(Natural Language Processing, NLP)是一个融合了语言学、计算机科学、数学等学科的领域,它不仅研究语言学,更研究如何让计算机处理这些语言。它主要分为两大方向:自然语言理解(Natural language Understanding, NLU)和自然语言生成(Natural language Generation, NLG),前者是听读,后者是说写。

本文将从自然语言处理的历史与发展讲起,进而分析目前深度学习在自然语言处理领域的研究进展,最后讨论自然语言处理的未来发展方向。

阅读全文 »