ACM

ACM通信

首页 / 杂志存档 / 2015年8月(第58卷第8期) / 从EDVAC到webvac /全文

实践

从EDVAC到webvac

作者:丹尼尔·c·王
ACM通信，2015年8月，第58卷第8期，44-51页
10.1145 / 2714079
评论

认为: 打印手机应用程序 ACM数字图书馆全文(PDF) 数码版分享: 通过电子邮件发送在reddit分享在StumbleUpon分享在黑客新闻上分享在推特上分享在Facebook上分享

到目前为止，每个人都听说过云计算，并意识到它正在改变传统企业it和新兴初创公司构建未来解决方案的方式。这种向云计算的趋势仅仅是硬件和软件行业复杂经济状况的转变，还是对计算的一种根本不同的思考方式?在这个行业工作过的我可以很自信地说，两者都有。

大多数关于云计算的文章过多地关注这种转变的经济方面，而忽略了思维的根本变化。本文试图填补这一空白，帮助更广泛的读者更好地理解与云计算相关的一些更基本的问题。这里所写的大部分内容对于那些每天使用这些系统的人来说不应该是惊天动地的，但是这篇文章可能会鼓励专家从业者以一种更微妙的方式来看待他们的日常问题。

以下是要涵盖的要点:

云计算机由如此多的组件组成，当考虑在云计算机上运行或与云计算机交互的软件时，系统地处理这些组件的故障是一个必须考虑的因素。
用于处理瞬态故障的常见架构模式是将系统划分为纯计算层和维护关键系统状态的独立层。这提供了可靠性、可伸缩性和简单性。
一个完善的现有最佳实践是让系统公开幂等接口，这样就可以使用简单的重试逻辑来掩盖大多数瞬时故障。
简单的分析技术可以对各种重试策略进行定量陈述，并比较它们如何在理想的故障模型下影响可靠性、最坏情况延迟和平均情况延迟。

对于那些为了从规模经济中获益而在大型多租户云计算机上托管小型应用程序的人来说，处理失败的第一点可能看起来很新鲜。然而，这实际上是一个非常古老的问题，所以讨论不应该从谈论最新的趋势开始，而应该回到电子计算机的早期。

回到顶部

EDVAC和冯·诺伊曼的教训

1945年，约翰·冯·诺伊曼描述了第一台全电子存储程序计算机的计算模型。这是他作为ENIAC发明家约翰·毛利和J.普莱斯珀·埃克特顾问的副作用。虽然他不是许多关键思想的鼻祖，但他的名字与设计方法联系在一起，冯·诺伊曼架构很快就成为了制造电子计算机的标准设计。EDVAC(电子离散变量自动计算机)初稿报告⁶包含了冯·诺伊曼的这些有趣的段落:

1.4当然，1.2中关于设备期望的自动功能的说明，必须假设它的功能没有故障。然而，任何设备发生故障的概率总是有限的，而且对于一个复杂的设备和长序列的操作来说，可能不可能保持这种可能性可以忽略不计。任何错误都可能损坏设备的全部输出。为了识别和纠正这种故障，智能的人工干预通常是必要的。

然而，在某种程度上甚至可以避免这些现象。设备可以自动识别最常见的故障，通过外部可见的标志指出故障的存在和位置，然后停止。在某些情况下，它甚至可能自动执行必要的修正并继续执行……

3．3在讨论过程中，1.4中关于故障的检测、定位和在一定条件下甚至纠正的观点也必须得到一些考虑。也就是说，必须注意检查错误的设施。我们将无法完全公正地对待这一重要问题，但每当这一问题显得必要时，我们将设法至少粗略地考虑一下。⁵

1945年，冯·诺伊曼和EDVAC的设计者们关心的实际问题是真空管和用水银延迟线储存的主存储器的可靠性。(现代硬盘也是一种神奇的机电设备，它终于开始被固态存储器所取代。)晶体管、集成电路和纠错码的发明使冯·诺伊曼的担忧在今天看来显得有些古怪。在计算机系统中，单位错误甚至多位错误虽然仍然可能发生，但已经非常罕见，因此这些问题被认为是不必要的。然而，随着云计算的出现，考虑系统组件故障的能力不能再被忽视，云计算用商用服务器填满了大量的空间。

回到顶部

墨菲定律战胜摩尔定律

云计算机由如此多的组件组成，每个组件都有有限的故障概率，以至于所有组件在任何时间点运行无误的概率接近于零。因此，故障和自动恢复不仅是硬件层需要关注的重要领域，而且也是软件组件需要关注的重要领域。简而言之，我们正处在墨菲定律战胜摩尔定律的时刻。假设一个系统的所有组件都能完美地工作是一种奢望，这种奢望已经不可能了。幸运的是，处理位级损坏的技术可以调整并扩展到云计算机，因此大多数位级错误即使不能修复，也可以被检测到。然而，我们担心的故障类型是服务器或整个服务器组的故障。我们也处在这样一个时刻:某些故障的发生率如此之高，以至于冯•诺伊曼的建议——系统简单地检测错误，然后等待人工操作人员进行干预——在经济上不再合理。

你可能会问，我们是否可以更努力地建立更可靠的系统，但当你的主电源的可靠性与你所在地区吃电线的松鼠的密度成反比，或与一个工人将一个未绝缘的扳手掉到配电柜的概率成反比时，很难想象有什么成本效益和系统的方法来解决数据中心的可靠性，这些数据中心通常拥有多达10万台服务器。

回到顶部

从EDVAC到WEBVAC

处理数据中心中频繁的服务器级故障的一种非常流行的方法是将系统分解为一个或多个服务器层，这些服务器层尽可能地处理请求，并将任何关键的应用程序状态存储在专门的存储层中。通常，在每个层前面都有一个请求负载平衡器，以便该层中的各个服务器可能出现故障，并自动重新路由请求。这种设计的关键是将长期系统状态和计算完全分离。这与EDVAC设计中存在于处理器和内存之间的分离是相同的。由于没有更好的术语，我们称这些系统为WEBVACs，即全球弹性大自动化集群。

这些webvac与今天在传统数据中心中看到的Web服务器群在概念上没有什么不同。WEBVACs使用一种经过验证的体系结构，它提供了弹性、可伸缩性和基于无状态HTTP请求的非常熟悉的编程模型。主要的创新是可配置的程度和易用性，以及弹性和规模。EDVAC区别于早期计算机(如ENIAC)的一个重要特征是，EDVAC执行的程序作为数据存储在内存中，而ENIAC是通过针对不同问题重新布线来编程的。图1显示了webvac和EDVAC在概念上的相似性。

与EDVAC一样，现代云计算机允许通过一些简单的构件自动配置一个完整的服务器群。这消除了在传统系统中经常进行的繁琐且容易出错的服务器手动配置的需要。

构建满足计算层需求的可靠存储层是一项具有挑战性的任务。存储层中的请求需要使用复杂的分布式共识协议在多个服务器之间复制。构建存储层的方法有很多种，它们的api和一致性模型也有很大的多样性。(在这里有限的篇幅内，很难对这个主题进行公正的阐述，所以请参阅本文末尾的额外阅读建议。)然而，最终，存储层只是一个可以从计算层调用的抽象。计算层可以依赖于存储层提供的保证，因此使用更简单的编程模型。

在这种更简单的编程模型中，系统的所有重要状态都存储在通用存储层中，这也简化了灾难恢复场景，因为存储层的简单备份和恢复通常足以将整个系统恢复到工作状态。设计良好的系统具有存储层到物理上不同位置的副本的异步连续备份。这个位置需要足够近，以便数据能够被有效地、成本效益地复制，但又要足够远，以便它遇到相同“天灾”的概率很低。(把主数据中心和备份数据中心都放在同一个地震断层线附近是一个坏主意。)

由于备份是异步的，因此故障转移到副本可能会导致一些数据丢失。但是，只有当天灾可能导致主系统完全破坏时，数据丢失才会被限制在可接受的和定义良好的限度内。仔细确定数据中心的物理位置是需要以端到端方式处理故障的第一种情况。同样的端到端对故障的关注在软件的设计和实现中也很重要，软件运行在系统上并与系统交互。

回到顶部

如何为WEBVACs设计接口

WEBVACs最终提供api，允许桌面计算机、移动设备或其他WEBVACs提交请求并接收对这些请求的响应。在任何情况下，您最终会得到两个代理，它们必须通过一个不可靠的通道上的某个接口相互通信。重用来自客户机-服务器系统或标准RPC(远程过程调用)方法的传统设计并不是最好的方法。安德鲁·塔内鲍姆和罗伯特·范·里斯⁴描述在对不是为分布式场景设计的代码进行naïve重构时的一些常见缺陷，这些缺陷通常也适用于这里的api。他们提出的一个特殊问题是2AP(两军问题)，这表明不可能设计一个完全可靠的方法，让两个代理在一个可能默默丢弃消息的不可靠通道上达成共识。

这是处理拜占庭式故障的更普遍问题的受限版本，在拜占庭式故障中，故障不包括数据损坏。因此，如果通道本身不可靠，就没有办法构建一个能够100%可靠地处理任何请求的系统。然而，2AP的结果并没有排除渐近接近100%可靠性的协议。一个简单的解决方案是不断地向某个有限的边界发送请求，直到接收到某个确认。如果信道的错误率是固定的，并且失败是独立的，那么成功的可能性就会随着传输的数量呈指数增长。

在大型数据中心中，不仅服务器之间的通信不可靠，而且服务器本身也容易发生故障。如果计算层中的服务器失败，那么针对它的请求可以快速地重路由到等效的计算服务器。重路由请求的过程通常不是完全透明的，并且在重路由过程中请求会丢失，因为路由逻辑不能立即检测到服务器故障，或者服务器正在处理请求时失败。这些丢失的请求在用户看来是瞬时故障。

因此，在云计算的上下文中，观察到的请求失败率实际上是通信通道的错误率和参与计算的服务器的错误率的组合。不需要对几个组件的个别故障率进行推理，可以做一个简化的假设，即由两个不可靠代理组成的系统通过一个不可靠通道进行通信，等价于通过一个不可靠通道进行通信的两个理想化的可靠代理，其故障率适当增加，以解释任何一个原始不可靠代理的故障。下面的扩展示例将对此进行更详细的说明。

通过不可靠通道枚举一组文件。图2显示了ANSI C中的一个简单接口定义，可用于枚举一组文件名。除了引入新的状态代码之外，该接口没有仔细考虑故障的错，这表示可能是由不可靠的传送引起的故障。假设调用这些函数中的任何一个发送请求并同步等待响应。假设是的错如果在某个固定超时后没有收到对请求的响应，则返回状态。

图3演示了一个简单的客户端函数，该函数试图枚举所有文件，但对第一个文件立即返回的错中的原语函数的任何调用都可以接收图2．

你要估计这个函数返回的概率好吧假设调用前面提到的三个函数中的任何一个都有0.99999 (S)的成功率，也就是说平均每100万个函数调用中有一个返回的错．首先，您需要计算枚举需要多少请求(M)N文件。检查代码可以发现M等于

哪一个可以简化成

由于函数在出现任何错误时立即失败，所以没有错误的概率就是所有发送的请求都成功的概率，即S^米假设故障均匀分布。为了进行分析，让我们假设失败是独立的和均匀分布的。这个简化的假设允许在等价的理想失效模型下比较各种方法的权衡。然而，在实践中，故障的分布通常既不是统一的，也不是完全独立的。研究结果总结在图4．

根据工作负载的特点，首次尝试列出文件的这种成功率可能是可以接受的。在本例中，0.99999的成功率(对于持续运行的系统，5 - 9的成功率导致每年停机时间不到5.3分钟)非常高，通常只能通过对昂贵的硬件基础设施进行大量投资才能实现。更现实的错误率应该是0.999(3 - 9的成功率导致持续运行的系统每年的停机时间少于8.8小时)，这在商用组件中更常见。中3 - 9的成功率产生了图表和数值表图5．

显然，列举10个文件的3%失败率不是一个可用的系统。您可以通过简单地重新尝试整个函数来提高成功的概率，但这不仅效率低，而且对于大型函数来说也是如此N在美国，成功率很低，需要不合理的重试次数。如果函数的概率ListFilesStopAtAnyFault列举N文件成功

那么失败的概率是

概率是，最多，K重试函数成功的概率是相同的

这是所有调用失败的概率的补数。对于这个讨论，如果成功的概率至少是0.999，当N是100，你必须重试，平均5次;当N是1000，重复次数至少是50才能得到3 - 9的成功率;为N= 1万，这个数字接近30亿。更聪明的方法是保持ListFilesStopAtAnyFault避免在任何单一的错误上立即失败。

这可以通过创建简单的包装器函数来实现，该函数在原始原语上添加一些基本的重试逻辑，从而产生一组新的更健壮的原语，如图6．

生产代码可能包含一个指数后退，以指数增长的时间延迟延迟每次重试。当许多客户端同时试图从一个网络分区恢复到一个给定的服务器时，这避免了所谓的“雷击群集”问题。为了简单起见，本文将忽略它。假设底层原语的成功率为0.999，执行三次简单的重试，则每个原语返回的概率为无错误

或者0.999999999(9个9)。图7演示如何编写使用这些更可靠的包装器的新例程。

现在你可以评估函数的可靠性了ListFilesWithRetry，但不是根据基本请求计算，而是根据调用每个请求包装器的次数计算(参见表1）.

既然每个包装器都有9比9的成功率，那么这个函数的总体成功率，即使N= 10,000，大于0.9999(对于持续运行的系统，4 - 9的成功率导致每年停机时间少于53分钟)。这个函数仍然有非零的返回机会的错因此，这并没有解决2AP问题，但显著增加了系统取得进展的可能性。当然，当出现错误时，插入重试会增加整体延迟，并且在合理的延迟模型下，增加枚举的预期时间N可以计算假设特定请求失败率的文件。这些更改的延迟影响将在后面讨论。

机敏的读者应该注意到代码中的一个致命缺陷。在出现请求失败的情况下，函数将继续枚举，但是重试的naïve添加将导致在出现失败时跳过文件。具体来说，这个包装器函数可能会导致文件被跳过:

这里的基本问题是底层的原语请求MoveToNextFileName它的一次调用在观察上并不等同于该函数的多次调用。由于2AP的存在，在出现故障时，无论光标是否向前移动，都无法让服务器或客户端同意。解决这个问题的唯一办法是MoveToNextFileName幂等。

有多种技术可以做到这一点。一种方法是包含序列号来检测重试，并让服务器跟踪这些编号。这些序列号现在成为必须放在系统中每个客户机的存储层中的重要状态，这可能会导致可伸缩性问题。一种更可伸缩的方法是使用不透明的状态令牌，类似于在HTTP中使用cookie的方式，将状态从服务器卸载到客户机。客户机可以维护所需的状态，而不是让服务器跟踪。中显示的API图8，它只包含幂等函数。

在本例中，状态令牌在现实系统中只是一个整数;它更有可能是一个可变长度的字节数组，系统验证它是有效的，以便恶意客户端不能伤害系统。

重试包装GetStartTokenWithRetry, GetStartTokenWithRetry,MoveToNextFileNameWithTokenAndRetry也可以定义为更早。

我们可以调整函数来使用幂等API上的包装原语(参见图9）.

先前在缺少幂等原语的有一些bug的版本上执行的分析仍然有效，但是现在函数可以正确可靠地工作。当N= 10000，则成功率为0.999979998(4个9)。

回到顶部

分析和改进延迟

由于检测发送方和接收方之间消息丢失的唯一实用方法是通过超时，因此记录任何一方应该等待请求被处理的时间限制非常重要。如果在超过时间限制后处理请求，则认为请求失败。服务通常为它们支持的每个API函数定义一个上限(例如，99.9%的所有请求将在一秒钟内成功处理)。如果不指定时间上限，保证99.9%的成功率就有点没有意义了;您可能需要等待无限长的时间才能成功完成任何单个请求。

确定一个系统的合理上限可能是相当复杂的。通过观察大量请求样本的延迟分布并选择最大值，或者通过简单地让服务器包含一个具有明确上限的看门狗定时器，该定时器会使任何超过阈值的请求失败，从而对延迟进行估计。在这两种情况下，都需要最坏情况边界，以便服务的客户端可以适当地设置超时，但这些最坏情况边界通常是对实际平均情况性能的非常保守的估计。本文的扩展版本发表于ACM队列分析文件列表函数的最坏情况、平均情况和慢情况延迟。

让我们假设对服务器的每个原语请求的最坏情况下成功延迟为R_马克斯的平均时间R_avg，通过这些参数，我们可以分析地估计重试策略如何影响延迟。最坏情况是建立在病态最坏情况的基础上，在这种情况下失败和重试的次数最多。这种分析过于悲观，我们可以使用我们的平均案例分析来得出一个慢案例估计，其中重试的分布与我们的平均案例分析相同，但我们假设每个请求都尽可能慢。

一些读者可能会觉得这个最终实现太“啰嗦”了，一个更有效的协议可以减少服务器往返。实际上，API中的三个函数可以被一个函数替换(参见图10）.

该协议有一个固定的全局已知的开始令牌和一个函数，该函数在一个请求中返回当前文件名和下一个令牌。延迟应该会有预期的改善，这可以通过对中描述的修改后的协议执行延迟分析看到表2．

延迟分析的详细信息见全文，并使用概率论的基本技术分析确定列出文件的函数调用者的合理超时值。

回到顶部

结论

本文远远没有详尽地介绍围绕云计算的许多有趣问题。这样做的目的是要证明仍有许多深层次的问题有待解决。一些开发电子计算机的先驱者会被我们现在口袋里的计算能力惊呆。他们同样会惊讶于他们的一些最早的想法居然经受住了时间的考验。从历史的角度来看，现代WEBVAC不应该被视为70年人类进步的顶点，而只是一个我们无法想象的充满希望的未来的开始。

回到顶部