PDF从 EDVAC 到 WEBVACs
面向计算机科学家的云计算
Daniel C. Wang
到现在为止，每个人都听说过云计算，并意识到它正在改变传统企业 IT 和新兴初创公司为未来构建解决方案的方式。这种向云端发展的趋势仅仅是硬件和软件行业复杂经济学的一次转变，还是对计算方式的根本性不同思考？在行业工作过之后，我可以自信地说两者都是。
大多数关于云计算的文章都过于关注转变的经济方面，而忽略了思维方式的根本性变化。本文试图填补这一空白，并帮助更广泛的受众更好地理解与云计算相关的一些更基本的问题。这里写的大部分内容对于那些日复一日与这些系统打交道的人来说不应该令人震惊，但本文可能会鼓励即使是专业的从业人员也以更细致的方式看待他们日常遇到的问题。
以下是要涵盖的要点
• 云计算机由如此多的组件组成，以至于系统地处理这些组件的故障是思考在云计算机上运行或与之交互的软件时要考虑的一个基本因素。
• 用于处理瞬时故障的常见架构模式是将系统划分为纯计算层和维护关键系统状态的单独层。这提供了可靠性、可扩展性和简单性。
• 一个成熟的现有最佳实践是使系统公开幂等接口，以便可以使用简单的重试逻辑来掩盖大多数瞬时故障。
• 简单的分析技术可以对各种重试策略进行定量陈述，并在理想化的故障模型下比较它们如何影响可靠性、最坏情况延迟和平均情况延迟。
对于许多现在将小型应用程序托管在大型多租户云计算机上以从规模经济中获益的人来说，关于处理故障的第一点可能看起来很新颖。然而，这实际上是一个非常古老的问题，因此讨论应该从回顾电子计算机的早期开始，而不是谈论最新的趋势。
来自 EDVAC 和冯·诺伊曼的教训
1945 年，约翰·冯·诺伊曼描述了第一台全电子存储程序计算机的计算模型。这是他作为 ENIAC 发明者约翰·莫奇利和 J. 普雷斯珀·埃克特 的顾问的副产品。尽管冯·诺伊曼并非许多关键思想的原创者，但他的名字与这种设计方法联系在一起，冯·诺伊曼架构很快成为构建电子计算机的标准设计。最初的 EDVAC（电子离散变量自动计算机）草案报告3 包含了冯·诺伊曼的这些有趣的段落
1.4 关于设备所需自动功能的 1.2 节评论当然必须假设它运行无故障。然而，任何设备的故障始终具有有限的概率——对于复杂的设备和长序列的操作，可能无法使这种概率保持在可忽略的水平。任何错误都可能使设备的整个输出无效。对于此类故障的识别和纠正，通常需要智能的人工干预。
然而，在某种程度上甚至有可能避免这些现象。设备可能会自动识别最常见的故障，通过外部可见的标志指示它们的存在和位置，然后停止。在某些情况下，它甚至可能自动执行必要的纠正并继续（参见 {3.3}）。
...
3.3 在本次讨论中，还必须对 1.4 节的观点进行一些考虑，该观点关注故障的检测、定位，甚至在某些情况下进行纠正。也就是说，必须注意检查错误的功能。我们将无法充分公正地对待这个重要主题，但我们将尝试在认为必要时至少粗略地考虑它。2
1945 年冯·诺伊曼和 EDVAC 设计师关心的实际问题是真空管的可靠性和使用水银延迟线存储的主存储器。（现代硬盘驱动器也是一种令人惊叹的机电设备，最终开始被固态存储器所取代。）晶体管、集成电路和纠错码的发明使冯·诺伊曼的担忧在今天看来有些古怪。计算机系统中的单位位错误甚至多位位错误虽然仍然可能发生，但已经足够罕见，以至于这些问题被认为是不重要的。然而，随着云计算机的出现，系统组件可能发生的故障再也不能被忽视，云计算机用商品服务器填满了数英亩的空间。
墨菲定律战胜摩尔定律
云计算机由如此多的组件组成，每个组件都有有限的故障概率，以至于所有组件在任何时间点都无错误运行的概率接近于零。因此，故障和自动恢复不仅是硬件层的基本关注领域，也是软件组件的基本关注领域。简而言之，我们正处于墨菲定律战胜摩尔定律的时刻。假设所有组件都能使系统完美无缺地工作，这是一种不再可能的奢侈。幸运的是，用于处理位级损坏的技术可以调整和扩展到云计算机，因此可以检测到大多数位级错误，即使不能修复。然而，我们担心的是服务器或整组服务器的故障。我们也正处于某些故障发生率如此之高的地步，以至于冯·诺伊曼关于系统只需检测到错误并等待人工操作员干预的建议在经济上不再明智。
您可能会问，我们是否可以更加努力地构建更可靠的系统，但是当您的主电源的可靠性与您所在地区电线啮齿类动物的密度成反比，或者工人将未绝缘的扳手掉入配电柜的可能性成反比时，很难想象有一种经济有效且系统的方法来解决通常容纳多达 100,000 台服务器的数据中心的可靠性问题。
从 EDVAC 到 WEBVAC
数据中心中处理频繁服务器级故障的一种非常流行的方法是将系统分解为一个或多个服务器层，这些服务器层以尽力而为的方式处理请求，并将任何关键应用程序状态存储在专用存储层中。通常，每个层的前面都有一个请求负载均衡器，以便层中的各个服务器可以发生故障并自动重新路由请求。这种设计的关键方面是长期系统状态和计算之间的完全分离。这与 EDVAC 设计中处理器和内存之间的分离相同。由于缺乏更好的术语，让我们将这些系统称为 WEBVAC，即全球弹性大型自动化集群，如图 1 所示。
这些 WEBVAC 在概念上与今天在传统数据中心看到的 Web 服务器场没有区别。WEBVAC 使用经过验证的架构，该架构提供弹性、可扩展性和基于无状态 HTTP 请求的非常熟悉的编程模型。主要的创新是配置的程度和易用性，以及弹性和规模。EDVAC 与早期计算机（如 ENIAC）区分开来的一个重要特征是，EDVAC 执行的程序作为数据存储在其内存中，而 ENIAC 则通过物理重新布线来针对不同的问题进行编程。
与 EDVAC 一样，现代云计算机允许使用一些简单的工件自动配置完整的服务器场。这消除了对服务器进行繁琐且容易出错的手动配置的需要，而这在更传统的系统中经常完成。
构建满足计算层需求的可靠存储层是一项具有挑战性的任务。存储层中的请求需要使用复杂的分布式共识协议跨多个服务器进行复制。构建存储层的方法有很多种，它们的 API 和一致性模型也存在很大差异。（在有限的篇幅内很难公正地对待这个主题，因此请参阅本文末尾的建议阅读。）但最终，存储层只是一个可以从计算层调用的抽象。计算层可以依赖于存储层提供的保证，因此使用更简单的编程模型。
这种更简单的编程模型，其中系统的所有重要状态都存储在通用存储层中，也简化了灾难恢复场景，因为对存储层进行简单的备份和还原通常足以将整个系统恢复到工作状态。精心设计的系统会对存储层进行异步持续备份，备份到物理位置不同的副本中。此位置需要足够近，以便可以高效且经济高效地复制数据，但又足够远，以至于遇到相同“天灾”的概率很低。（将主数据中心和备份数据中心都放在同一地震断层附近是一个坏主意。）
由于备份是异步的，因此故障转移到副本可能会导致一些数据丢失。然而，数据丢失可以限制在可接受且明确定义的范围内，只有当“天灾”导致主系统完全损毁时才会发挥作用。仔细确定数据中心的物理位置是第一个需要以端到端方式处理故障的情况。这种对故障的相同端到端关注在运行在系统上并与之交互的软件的设计和实现中也很重要。
如何为 WEBVAC 设计接口
WEBVAC 最终提供 API，允许台式计算机、移动设备或其他 WEBVAC 提交请求并接收对这些请求的响应。在任何情况下，您最终都会得到两个代理，它们必须通过某个接口在不可靠的通道上进行通信。重用客户端-服务器系统或标准 RPC（远程过程调用）方法的传统设计并非最佳方法。Andrew Tanenbaum 和 Robbert van Renesse1 描述了在对并非为分布式场景设计的代码进行幼稚的重构时的一些常见陷阱，这些陷阱通常也适用于此处的 API。他们指出的一个特殊问题是 2AP（双军问题），即不可能设计一种完全可靠的方法，让两个代理在可能静默丢弃消息的不可靠通道上达成共识。
这是处理拜占庭故障的更一般问题的受限版本，其中故障不包括数据损坏。因此，如果通道本身不可靠，则根本无法构建一个可以 100% 可靠地处理任何请求的系统。然而，2AP 结果并不排除渐近接近 100% 可靠性的协议。一个简单的解决方案是不断传输请求直到某个有限的界限，直到收到某个确认。如果通道的错误率是固定的，并且故障是独立的，那么成功的可能性会随着传输次数呈指数增长。
在大型数据中心中，不仅服务器之间的通信不可靠，而且服务器本身也容易发生故障。如果计算层中的服务器发生故障，则可以快速将针对它的请求重新路由到等效的计算服务器。然而，重新路由请求的过程通常不是完全透明的，并且请求可能会在重新路由期间丢失，因为路由逻辑无法立即检测到服务器故障，或者因为服务器在发生故障时正在处理请求。这些丢失的请求对用户来说表现为瞬时故障。
因此，在云计算的上下文中，观察到的请求故障率实际上是通信通道的综合错误率和参与计算的服务器的故障率。与其推断几个组件的单独故障率，不如做出简化的假设，即两个不可靠的代理在不可靠的通道上通信的系统等同于两个理想化的可靠代理在不可靠的通道上通信的系统，后者的故障率适当增加以考虑原始不可靠代理中的任何一个的故障。以下部分中的扩展示例更详细地说明了这一点。
在不可靠的通道上枚举一组文件
以下是一个简单的 ANSI C 接口定义，可用于枚举一组文件名。该接口的公开没有仔细考虑故障，只是引入了一个新的状态代码Fault，这表明故障很可能是由不可靠的交付引起的。假设调用这些函数中的任何一个都会发送请求并同步等待响应。假设是如果超时后未收到对请求的响应，则返回Fault状态。
enum Result {
Ok, /* 无错误完成。 */
NoMore, /* 没有更多名称要枚举。*/
Fault /* 消息在传输中丢失或未知故障。 */
};
/* 将光标移动到文件列表中的第一个元素之前。 */
Result SetCursorToStart();
/* 获取光标指向的当前文件名。
* 如果光标已移过最后一个名称，则返回 NoMore。
*/
Result GetCurrentFileName(char fileName[MAXLENGTH]);
/* 将光标移动到下一个文件名。
* 如果没有，则返回 NoMore。
*/
Result MoveToNextFileName();
这是一个简单的客户端函数，它尝试枚举所有文件，但在首次Fault收到对上述任何原始函数的调用时立即返回
Result ListFilesStopAtAnyFault()
{
char fileName[MAXLENGTH];
Result res;
res = SetCursorToStart();
if (res != Ok) { return res; }
printf("Start\n");
for (;;)
{
res = MoveToNextFileName();
if (res == NoMore) { break; }
if (res != Ok) { return res; }
res = GetCurrentFileName(fileName);
printf("File: %s", fileName);
}
printf("End\n");
return Ok;
}
您想估计此函数将返回Ok的概率，假设调用前面提到的三个函数中的任何一个的成功率为 0.99999 (S)，也就是说，平均每百万次函数调用中，有一次返回Fault。首先，您需要计算枚举 N 个文件所需的请求数 (M)。代码检查显示 M 等于
1 + 2 * N + 1
可以简化为
2 * (N + 1).
由于该函数在任何故障时立即失败，因此无故障的概率只是发送的所有请求都成功的概率，即 S^M，假设故障是均匀分布的。为了进行此分析，让我们假设故障是独立的且均匀分布的。这种简化的假设允许在等效的理想故障模型下比较各种方法的权衡。然而，在实践中，故障的分布通常既不均匀也不完全独立。结果总结在图 2 中。
根据工作负载特性，第一次尝试列出文件的成功率可能是可以接受的。在本例中，0.99999 的成功率（五个 9 的成功率导致连续运行的系统每年停机时间少于 5.3 分钟）非常高，通常只有通过对昂贵的硬件基础设施进行大量投资才能实现。更现实的错误率将是 0.999（三个 9 的成功率导致连续运行的系统每年停机时间少于 8.8 小时），这在商品组件中更为常见。三个 9 的成功率生成图 3 中的图表和值表。
显然，对于枚举 10 个文件而言，3% 的故障率是不可用的系统。您可以通过简单地重试整个函数来提高成功概率，但这不仅效率低下，而且对于较大的 N，成功率非常低，以至于需要不合理的重试次数。如果函数ListFilesStopAtAnyFault成功枚举 N 个文件的概率为
LS(N) = S2*(N+1)
则失败的概率为
LF(N) = 1 - LS(N).
在最多 K 次重试后函数成功的概率与概率
1 - LF(N)K.
相同，这是所有调用都失败的概率的补集。对于此讨论，如果当 N 为 100 时，成功概率至少为 0.999，则您必须平均重试 5 次；当 N 为 1,000 时，要获得三个 9 的成功率，重试次数至少为 50 次；对于 N = 10,000，次数接近 30 亿次。更明智的方法是防止ListFilesStopAtAnyFault在任何单个故障时立即失败。
这可以通过创建简单的包装函数来实现，这些包装函数在原始原语之上添加一些基本的重试逻辑，从而产生一组新的更健壮的原语。
#define MAX_RETRIES 3
Result SetCursorToStartWithRetry()
{
Result res;
for (int i = 0; i < MAX_RETRIES; i++)
{
res = SetCursorToStart();
if (res != Fault) { return res; }
}
return Fault;
}
Result GetCurrentFileNameWithRetry(char fileName[MAXLENGTH])
{
Result res;
for (int i = 0; i < MAX_RETRIES; i++)
{
res = GetCurrentFileName(fileName);
if (res != Fault) { return res; }
}
return Fault;
}
Result MoveToNextFileNameWithRetry()
{
Result res;
for (int i = 0; i < MAX_RETRIES; i++)
{
res = MoveToNextFileName();
if (res != Fault) { return res; }
}
return Fault;
}
生产代码可能会包含指数退避，这会使用指数增长的时间延迟来延迟每次重试。这避免了当许多客户端同时尝试从到给定服务器的网络分区中恢复时所谓的“雷鸣般的兽群”问题。为简单起见，本次讨论将忽略它。假设底层原语的成功率为 0.999，执行三次简单的重试使这些原语中的每一个返回而没有故障的概率
1 - (1 - 0.999)3 .
或 0.999999999（九个 9）。您现在可以编写一个新例程，该例程使用这些更可靠的包装器
Result ListFilesWithRetry()
{
char fileName[MAXLENGTH];
Result res;
res = SetCursorToStartWithRetry();
if (res != Ok) { return res; }
printf("Start\n");
for (;;)
{
res = MoveToNextFileNameWithRetry();
if (res == NoMore) { break; }
if (res != Ok) { return res; }
res = GetCurrentFileNameWithRetry(fileName);
printf("File: %s", fileName);
}
printf("End\n");
return Ok;
}
现在您可以评估函数ListFilesWithRetry的可靠性，但不是相对于原始请求计算它，而是相对于每个请求包装器被调用的次数计算它
| 包装器成功率 (W) |
文件数 (N) |
调用的包装器 (C) |
成功概率 |
| 1 - (1 - 0.999)^3 |
N |
C = 2*(N + 1) |
W^C |
| 0.999999999 |
1 |
4 |
0.999999996 |
| 0.999999999 |
10 |
22 |
0.999999978 |
| 0.999999999 |
100 |
202 |
0.999999798 |
| 0.999999999 |
1,000 |
2,002 |
0.999997998 |
| 0.999999999 |
10,000 |
20,002 |
0.999979998 |
现在每个包装器都具有九个 9 的成功率，即使当 N = 10,000 时，此函数的总体成功率也超过 0.9999（四个 9 的成功率导致连续运行的系统每年停机时间少于 53 分钟）。仍然有非零的可能性此函数将返回Fault，因此这种方法尚未解决 2AP，但已大大提高了系统取得进展的可能性。当然，插入重试会增加出现错误时的总体延迟，并且在合理的延迟模型下，可以计算出假设特定请求故障率枚举 N 个文件的预期时间。稍后将讨论这些更改对延迟的影响。
精明的读者应该注意到上面代码中的一个致命缺陷。该函数将在存在请求故障的情况下继续枚举，但是天真地添加重试会导致在出现故障时跳过文件。具体来说，此包装函数可能会导致文件被跳过
Result MoveToNextFileNameWithRetry();
这里的根本问题是底层原始请求MoveToNextFileName不是幂等的——它的一次调用在观察上不等同于该函数的多次调用。由于 2AP，服务器和客户端无法就光标是否在故障时向前移动达成一致。解决此问题的唯一方法是使MoveToNextFileName幂等。
有很多技术可以做到这一点。一种方法是包含序列号以检测重试并让服务器跟踪这些数字。这些序列号现在成为重要状态，必须为系统中的每个客户端放置在存储层中，这可能会导致可扩展性问题。更具可扩展性的方法是使用不透明状态令牌，类似于 HTTP 中 cookie 的使用方式，将状态从服务器卸载到客户端。客户端可以维护所需的状态，而不是让服务器跟踪它。这留下了以下 API，其中仅包含幂等函数
typedef int tok_t;
/* 获取起始令牌，光标位于文件列表中的第一个元素之前。 */
Result GetStartToken(tok_t *init);
/*
* 获取光标相对于状态令牌指向的当前文件名。
* 如果光标已移过最后一个名称，则返回 NoMore。
*/
Result GetCurrentFileNameWithToken(tok_t curent, char fileName[MAXLENGTH]);
/* 移动给定令牌并返回下一个状态令牌，光标已前进。
* 如果没有，则返回 NoMore。
*/
Result MoveToNextFileNameWithToken(tok_t curent, tok_t *next);
在本例中，状态令牌只是一个整数，在实际系统中，它更可能是一个可变长度的字节数组，系统会验证该数组是否有效，以防止恶意客户端损害系统。
重试包装器也可以像早期一样为这些新原语定义
Result GetStartTokenWithRetry(tok_t *init)
{
...
}
Result GetCurrentFileNameWithTokenAndRetry(tok_t current, char fileName[MAXLENGTH])
{
...
}
Result MoveToNextFileNameWithTokenAndRetry(tok_t current, tok_t *next)
{
...
}
最后，让我们定义一个使用包装原语的函数，该函数基于幂等 API
Result ListFilesWithTokenAndRetry()
{
char fileName[MAXLENGTH];
Result res;
tok_t current;
res = GetStartTokenWithRetry(¤t);
if (res != Ok) { return res; }
printf("Start\n");
for (;;)
{
res = MoveToNextFileNameWithTokenAndRetry(current, ¤t);
if (res == NoMore) { break; }
if (res != Ok) { return res; }
res = GetCurrentFileNameWithTokenAndRetry(current, fileName);
printf("File: %s", fileName);
}
printf("End\n");
return Ok;
}
先前对略有缺陷的版本（缺少幂等原语）执行的分析仍然有效，但现在该函数可以正确且可靠地工作。当 N = 10,000 时，成功率为 0.999979998（四个 9）。
估计重试引起的额外延迟
由于检测发送者和接收者之间消息丢失的唯一实用方法是通过超时，因此务必记录一方应等待请求处理多长时间的时间限制。如果请求在超过该时间限制后被处理，则认为请求失败。服务通常为它们支持的每个 API 函数定义一个上限（例如，99.9% 的所有请求将在 1 秒内成功处理）。如果未指定上限时间限制，则有保证的 99.9% 成功率在某种程度上毫无意义；您可能必须无限期地等待任何单个请求才能成功完成。
确定系统的合理上限可能非常复杂。可以通过观察大量请求的延迟分布并选择最大值来观察估计它，或者通过简单地让服务器包含一个看门狗计时器，该计时器具有明确的上限，该上限会使任何超过阈值的请求失败。在任何一种情况下，都需要最坏情况的界限，以便服务的客户端可以适当地设置超时，但是这些最坏情况的界限通常是对实际平均情况性能的非常保守的估计。本文分析了文件列表函数的最坏情况和平均情况延迟。为了简化分析，让我们假设对服务器的每个原始请求的最坏情况成功延迟为 Rmax，平均时间为 Ravg。
给定这些值，让我们估计函数ListFilesWithRetry的最坏情况和平均情况时间。由于我们只对成功的调用感兴趣，因此幼稚的最坏情况延迟直接与包装器函数的调用次数及其最坏情况延迟 WRmax 相关。
最坏情况是如果所有重试函数都遇到两个恰好花费 Rmax 的故障，然后是一个花费 Rmax 的成功调用。等式为
WRmax = 3 * Rmax
因为 MAX_RETRIES 定义为 3。枚举 N 个文件的包装器调用次数为
2 * (N + 1)
因此，最坏情况延迟为
2 * (N + 1) * WRmax = 3 * Rmax
或
Lmax(N) = 6 * (N + 1) * Rmax
这种最坏情况估计非常悲观。还有一种替代方法可以给出更合理的上限。
平均情况分析稍微复杂一些，因为必须考虑所有可能的结果。作为一种简化的假设，所有失败的请求都需要 Rmax 才能完成。这是一个稍微保守的假设，但由于失败请求的延迟分布不是先验地正态分布的，因此这种保守性是有道理的。要计算 WRavg，您必须首先考虑所有可能结果的时间，并按其可能性（包括故障）进行加权
| 权重 |
时间 |
| 0.999 |
Ravg |
| 0.001 * 0.999 |
Rmax + Ravg |
| 0.001 * 0.001 * 0.999 |
Rmax + Rmax + Ravg |
| 0.001 * 0.001 * 0.001 |
Rmax + Rmax + Rmax |
由于我们只对成功感兴趣，因此最后一个结果被删除，并且权重由感兴趣的子总体 (0.999999999) 重新标准化
| 权重 |
时间 |
| 0.999 / 0.999999 |
Ravg |
| (0.001 * 0.999) / 0.999999999 |
Rmax + Ravg |
| (0.001 * 0.001 * 0.999) / 0.999999999 |
Rmax + Rmax + Ravg |
这使得 WRavg 等于
0.999999999
和
Lavg( N) = 2 * ( N + 1) * WRavg = 2 * ( N + 1) * ( Ravg + 0.001000998001001 * Rmax)这是当 Rmax = 1,000 毫秒且 Ravg = 10 毫秒时的值表，其中 WRavg 的值约为 11.000998 毫秒
| N |
Lmax(N) | Lavg(N) |
| 1 |
12 秒 |
44 毫秒 |
| 10 |
1.1 分钟 |
242 毫秒 |
| 100 |
10.1 分钟 |
2.22 秒 |
| 1,000 |
1.66 小时 |
22 秒 |
| 10,000 |
16.6 小时 |
3.7 分钟 |
请注意，最坏情况延迟是一个非常保守的估计，反映了极不可能发生的事件序列，即故障始终发生在最初的两个请求上，而第三次重试以最坏情况延迟成功。另一种上限基于平均情况分析，在该分析中，您只需假设 Ravg = Rmax 并计算 WRslow = 1001.000998001。这提供了更可能的事件分布，该分布模拟非常慢的请求而不是病态行为。让我们将此界限称为 Lslow(N) = 2 * (N + 1) * WRslow 。下表比较了 N 的不同值下的三个值
| N |
Lmax(N) | Lslow(N) | Lavg(N) |
| 1 |
12 秒 |
4 秒 |
44 毫秒 |
| 10 |
1.1 分钟 |
22 秒 |
242 毫秒 |
| 100 |
10.1 分钟 |
3.34 分钟 |
2.22 秒 |
| 1000 |
1.66 小时 |
33.4 分钟 |
22 秒 |
| 10000 |
16.6 小时 |
5.56 小时 |
3.7 分钟 |
提高延迟
一些读者可能会觉得最终的实现过于“冗长”，更有效的协议可以减少服务器往返次数。实际上，API 中的三个函数可以用一个函数替换
/* 众所周知的起始令牌。 */
tok_t StartToken = -1;
/* 给定令牌，返回下一个状态令牌，光标已前进
* 和当前文件名。
* 如果没有文件，则返回 NoMore。
*/
Result GetCurrentFileNameAndNextToken(
tok_t curent,
char fileName[MAXLENGTH],
tok_t *next);
此协议具有固定的全局已知起始令牌和一个函数，该函数在一个请求中返回当前文件名和下一个令牌。我们也可以为其定义一个简单的重试包装器
Result GetCurrentFileNameAndNextTokenWithRetry(
tok_t curent,
char fileName[MAXLENGTH],
tok_t *next)
{
...
}
最后，调整函数以使用新接口，我们可以分析可靠性
结果 ListFilesWithTokenAndRetryOpt()
{
char fileName[MAXLENGTH];
Result res;
tok_t current = StartToken;
printf("Start\n");
for (;;)
{
res = GetCurrentFileNameAndNextTokenWithRetry(current, fileName, ¤t);
if (res == NoMore) { break; }
if (res != Ok) { return res; }
printf("File: %s", fileName);
}
printf("End\n");
return Ok;
}
| 包装器成功率 (W) |
文件数 (N) |
调用的包装器 (C) |
成功概率 |
| 1 - (1 - 0.999)^3 |
N |
C = N + 1 |
W^C |
| 0.999999999 |
1 |
2 |
0.999999998 |
| 0.999999999 |
10 |
11 |
0.999999989 |
| 0.999999999 |
100 |
101 |
0.999999899 |
| 0.999999999 |
1,000 |
1,001 |
0.999998999 |
| 0.999999999 |
10,000 |
10,001 |
0.999989999 |
与之前的版本相比，成功率的提升几乎不明显，但可靠性并非此处唯一考虑因素。预期延迟应该有所改善，通过使用此修改后的方法重新进行延迟分析可以清楚地看到这一点
| N |
L'max(N) | L'slow(N) | L'avg(N) |
| 1 |
6 秒 |
2 秒 |
22 毫秒 |
| 10 |
33 秒 |
11 秒 |
121 毫秒 |
| 100 |
5.05 分钟 |
1.68 分钟 |
1.11 秒 |
| 1,000 |
50.5 分钟 |
16.7 分钟 |
11.0 秒 |
| 10,000 |
8.33 小时 |
2.78 小时 |
1.83 分钟 |
部分重试策略：它有帮助吗？
在查看了这些文件列表函数的最后两个版本的可靠性表格后，读者可能会注意到，即使当 N = 10,000 时，成功概率也远高于三个九，因此自然而然地会产生一个问题：我们是否重试得太多了？能否牺牲一些可靠性来换取更好的平均延迟？一个观察结果是，在最佳情况下，当没有重试时，N = 10,000 的时间为 1.67 分钟，这意味着当前三次重试的方法最多增加了 10% 的延迟。假设当 N <= 10,000 时，我们对超过 0.999 的成功率不感兴趣。反向推算，您可以计算出一个最小的重试策略，以便当 N = 10,000 时，您刚好高于三个九
W10001 > 0.999
求解 W
W > e(Ln(0.999) / 10001)
W 大约大于 0.999999899959976，这相当于七个九。请记住
W = 1 - (1 - 0.999)K
其中 K 是重试次数。求解 K，您会发现 K 需要大约为 2.4。部分重试值可能看起来很荒谬，但它很容易实现，方法是确定性地重试前两次，并基于公平的抛硬币非确定性地执行最后一次重试。
结果 GetCurrentFileNameAndNextTokenWithRetry(tok_t curent, char fileName[MAXLENGTH], tok_t *next)
{
Result res;
res = GetCurrentFileNameAndNextToken(curent, fileName, next);
if (res != Fault) { return res; }
res = GetCurrentFileNameAndNextToken(curent, fileName, next);
if (res != Fault) { return res; }
if (CoinFlip()) { return Fault; }
return GetCurrentFileNameAndNextToken(curent, fileName, next);
}
此函数提供 2.5 次预期重试，对于 N = 10,000，预期成功率为 0.9996。现在让我们基于此部分策略计算平均延迟。首先枚举结果和加权可能性
| 权重 |
时间 |
| 0.999 |
Ravg |
| 0.001 * 0.999 |
Rmax + Ravg |
| 0.001 * 0.001 * 0.5 * 0.999 |
Rmax + Rmax + Ravg |
| 0.001 * 0.001 * 0.5 * 0.001 |
Rmax + Rmax + Rmax |
| 0.001 * 0.001 * 0.5 |
Rmax + Rmax |
再次对权重进行归一化，以便仅考虑成功的情况
| 权重 |
时间 |
| 0.999/0.9999994995 |
Ravg |
| (0.001 * 0.999)/ 0.9999994995 |
Rmax + Ravg |
| (0.001 * 0.001 * 0.5 * 0.999)/ 0.9999994995 |
Rmax + Rmax + Ravg |
这意味着 WR'avg 等于
0.999999499
当 Ravg = 10 且 Rmax = 1000 时，WR'avg = 10.999999。当计算 N = 10,000 的预期时间时，预期的改进几乎不明显，这可能并不太令人惊讶，因为前两次重试失败的可能性已经非常低。然而，该示例使用了简单的线性重试策略，而在实践中，您更可能使用指数退避算法。读者可能希望使用更实际的指数退避重试策略重新进行此分析。本文中介绍的所有基本技术也可用于分析估计使用此类策略的平均和最坏情况延迟。
结论
本文并非对围绕云计算的诸多有趣问题进行详尽的调查。其目标是证明仍然有各种各样的深刻问题有待解决。一些开发电子计算机的先驱者会对我们现在口袋里携带的计算能力感到震惊。他们也会对他们最早的一些想法经受住了时间的考验而感到同样惊讶。从历史的角度来看，现代 WEBVAC 不应被视为人类 70 年进步的顶峰，而仅仅是我们无法想象的美好未来的开始。
致谢
特别感谢 Gang Tan 提供了早期反馈并鼓励我撰写本文，以及 Steve Zdancewic，他提供了早期审阅反馈。
参考文献
1. Tanenbaum, A. S., van Renesse, R. 1988. 远程过程调用范式的批判。载于 EUTECO（欧洲远程信息会议）会议录，参与者版：775-783。
2. von Neumann, J. 1945. EDVAC 报告初稿。技术报告。 https://web.archive.org/web/20130314123032/http://qss.stanford.edu/~godfrey/vonNeumann/vnedvac.pdf.
3. 维基百科。EDVAC 报告初稿； http://en.wikipedia.org/wiki/First_Draft_of_a_Report_on_the_EDVAC.
延伸阅读
Calder, B., Wang, J., Ogus, A., 等. 2011. Windows Azure Storage：具有强一致性的高可用性云存储服务。载于第 23 届 操作系统原理研讨会会议录：143-157。DOI=10.1145/2043556.2043571； http://doi.acm.org/10.1145/2043556.2043571
DeCandia, G., Hastorun, D., 等. 2007. Dynamo：Amazon 的高可用性键值存储。载于第 21 届 操作系统原理研讨会会议录：205-220。DOI=10.1145/1294261.1294281； http://doi.acm.org/10.1145/1294261.1294281。
Ghemawat, S., Gobioff, H., Leung, S.-T. 2003. Google 文件系统。载于第 19 届 操作系统原理研讨会会议录：29-43。DOI=10.1145/945445.945450； http://doi.acm.org/10.1145/945445.945450。
喜欢或讨厌？请告诉我们
Daniel C. Wang 拥有普林斯顿大学计算机科学博士学位，并在计算行业工作超过 15 年。他现在在 Azure Web Workload 团队工作。文章中的任何观点均为作者个人观点，不代表其雇主的观点。
©right; 2015 1542-7730/14/0300 $10.00
最初发表于 Queue 卷。13，第 4 期—
在 数字图书馆中评论本文
更多相关文章
Marc Brooker, Ankush Desai - AWS 的系统正确性实践
构建可靠且安全的软件需要一系列方法来推理系统正确性。除了行业标准的测试方法（例如单元测试和集成测试）之外，AWS 还采用了模型检查、模糊测试、基于属性的测试、故障注入测试、确定性模拟、基于事件的模拟以及执行跟踪的运行时验证。形式化方法一直是开发过程的重要组成部分 - 也许最重要的是，形式化规范作为测试预言机，为 AWS 的许多测试实践提供了正确的答案。正确性测试和形式化方法仍然是 AWS 的主要投资领域，并因在这些领域已经看到的出色回报而加速发展。
Achilles Benetopoulos - 数据中心计算机的中间表示
我们已经到了分布式计算无处不在的地步。内存中应用程序数据的大小正在超过单台机器的容量，因此需要将其分区到集群中；在线服务具有高可用性要求，只有通过将系统部署为多个冗余组件的集合才能满足这些要求；高持久性要求只能通过数据复制来满足，有时跨越广阔的地理距离。
David R. Morrison - 模拟：分布式系统中未充分利用的工具
模拟在人工智能系统的出现中可以发挥巨大的作用：我们需要一种高效、快速且经济高效的方法来训练人工智能代理在我们的基础设施中运行，而模拟绝对可以提供这种能力。
Matt Fata, Philippe-Joseph Arida, Patrick Hahn, Betsy Beyer - 从企业到云端：Google 的虚拟桌面
超过四分之一的 Google 员工使用内部数据中心托管的虚拟桌面。这种本地产品位于公司网络中，允许用户从世界任何地方远程开发代码、访问内部资源和使用 GUI 工具。在其最显著的特性中，虚拟桌面实例可以根据手头的任务调整大小，具有持久的用户存储，并且可以在公司数据中心之间移动以跟随出差的 Google 员工。直到最近，我们的虚拟桌面还是使用名为 Ganeti 的自研开源虚拟集群管理系统托管在 Google 公司网络上商用硬件上。今天，这项重要的且对 Google 至关重要的工作负载在 GCP（Google Compute Platform）上运行。
© 保留所有权利。