实践研究

2017年3月29日
第15卷，第1期

实践研究：分布式系统的追踪与调试；示例编程

计算机科学最佳研究的专家策划指南

本期“实践研究”涵盖了分布式系统和编程方法论中两个令人兴奋的主题。首先，Peter Alvaro 将带领我们游览最新的技术，用于调试世界上一些最大和最复杂的系统：现代分布式系统和服务导向架构。Peter 调查的技术可以揭示分布式调用图的混乱中的秩序。其次，Sumit Gulwani 阐述了如何在不显式编写程序的情况下进行编程，而是从示例中合成程序！Sumit 介绍的技术允许系统从说明性示例中“学习”程序表示，从而允许非程序员用户创建越来越重要的功能，例如电子表格宏。这两个选择都非常符合 RfP 的可访问、实用研究的目标；事实上，两位贡献者都已成功地将他们在各自领域的研究成果转化为生产，分别在 Netflix 和作为 Microsoft Excel 的一部分。读者也可能会发现用例！

与往常一样，我们在本专栏中的目标是让我们的读者在一个周末下午的阅读时间内成为计算机科学研究最新主题的专家。为了促进这一过程，我们提供了对数字图书馆的开放访问权限，以便您可以充分欣赏这些研究成果的相关引文。请尽情享受！—Peter Bailis

好的，但为什么？分布式系统的追踪与调试

作者：Peter Alvaro

大规模分布式系统的调试可能是一场噩梦。不太可能发生的事件（例如，服务器崩溃或进程响应请求的时间过长）在许多互联网企业运营的大规模环境中很常见。最先进的监控系统可以帮助衡量这些异常的频率，但对于识别其根本原因却无能为力。普遍存在的日志记录可能会记录适当粒度的感兴趣事件，但跨大量机器的日志关联事件非常困难。

分布式追踪系统克服了许多这些限制，使得更容易推导出跨分布式计算中许多节点的端到端交互的高级解释。但没有免费的午餐。广义而言，大规模追踪系统给采用者带来了检测负担（调整现有代码以添加检测点或传播元数据，或两者兼有的工作量）和开销负担（追踪捕获和传播的运行时成本）。此处选择的论文集展示了减轻这些负担的一些策略，以及高级解释的一些创造性应用。

使用上下文传播进行追踪

Sigelman, B. H., Barroso, L. S., Burrows, M., Stephenson, P., Plakal, M., Beaver, D., Jaspan, S., Shanbhag, C. 2010. Dapper，大规模分布式系统追踪基础设施； http://research.google.com/pubs/pub36356.html

Dapper 代表了基于上下文追踪的“早期”工业工作。它通过依赖 Google 相对同构的基础设施来最大限度地减少检测负担，其中所有代码都依赖于通用的 RPC（远程过程调用）库、线程库等。它通过仅选择少量入口请求并在请求旁边传播追踪元数据来最大限度地减少开销负担，以确保如果对请求进行采样，则对其响应做出贡献的所有交互也被采样。

Dapper 的数据模型（嵌套 span 树，捕获参与 调用图 的服务之间的因果和时间关系）和基本架构已成为行业中追踪收集的事实标准。Zipkin（在 Twitter 创建）是 Dapper 的第一个开源“克隆”；Zipkin 及其衍生产品（包括最近宣布的 Amazon Web Services X-Ray）如今已得到广泛使用。

Mace, J., Roelke, R., Fonseca, R. 2015. Pivot Tracing：分布式系统的动态因果监控。第 25 届操作系统原理研讨会论文集：378-393。 http://cs.brown.edu/~rfonseca/pubs/mace15pivot.pdf

Dapper 绝不是第一个提倡内联上下文传播的系统设计。这个想法至少可以追溯到 Xtrace，它是由 UC Berkeley 的 Rodrigo Fonseca 开创的。Fonseca（现在在布朗大学）仍然在该领域做着令人印象深刻的工作。Pivot Tracing 提出了数据库对低开销动态追踪的看法，将事件建模为元组，识别代表数据源的代码位置，并将动态检测转变为查询计划和优化问题。Pivot Tracing 重用了 Dapper/Xtrace 风格的上下文传播，以允许根据因果关系有效地关联事件。查询流！

追踪推断

Chow, M., Meisner, D., Flinn, J., Peek, D., Wenisch, T. F. 2014. 神秘机器：大规模互联网服务的端到端性能分析。第 11 届 Usenix 操作系统设计与实现会议论文集：217-231。 https://www.usenix.org/system/files/conference/osdi14/osdi14-paper-chow.pdf

那些无法（或只是不想）克服追踪的检测和开销负担的企业怎么办？他们可以从非结构化系统日志中事后重建因果关系吗？神秘机器描述了一个系统，该系统首先自由地制定关于分布式系统中事件如何相关的假设（例如，一个是另一个的原因吗？它们是互斥的吗？它们是否参与管道计算？），然后挖掘日志以寻找与现有假设相矛盾的证据（例如，其中事件 A 和 B 并发的日志立即反驳了 A 和 B 互斥的假设）。随着时间的推移，假设集会收敛到系统交互模型中，该模型可用于回答许多相同的问题。

新领域

Alvaro, P., Andrus, K., Sanden, C., Rosenthal, C., Basiri, A., Hochstein, L. 2016. 自动化互联网规模的故障测试研究。第七届云计算研讨会论文集：17-28。 https://people.ucsc.edu/~palvaro/socc16.pdf

刚刚描述的系统的存在理由 是理解用户感知的端到端延迟的原因。有了大规模分布式系统产生其结果的详细“解释”，我们可以做更多的事情。我在 UC Santa Cruz 的研究小组一直在探索使用“良好”或预期系统结果的解释来驱动故障注入基础设施，以便找出表面上具有容错能力的代码中的错误。基本思想是，如果我们能够解释分布式系统在无故障情况下的运行方式，以及它如何提供冗余来克服故障，我们就能更好地理解它的弱点。

这种称为 LDFI（谱系驱动的故障注入）的方法最初依赖于理想化的、细粒度的数据来源来解释分布式执行（请参阅我们之前的论文“谱系驱动的故障注入”，作者：Peter Alvaro、Joshua Rosen 和 Joseph M. Hellerstein，在 SIGMOD 2015 上发表）。这篇较新的论文描述了如何将 LDFI 方法调整为“嵌入” Netflix 的微服务架构，并从 Zipkin 风格的调用图追踪构建丰富的系统冗余模型。

结论

尽管分布式系统在学术界是一个成熟的研究领域，并且在工业界无处不在，但分布式系统的调试艺术仍处于起步阶段。很明显，传统的调试器以及随之而来的用于推导计算解释的传统最佳实践必须被取代，但现在说哪种方法将占据主导地位还为时过早。工业界在设计方面，尤其是在大规模追踪系统的普及方面处于领先地位，这是为了响应实际需求：了解在线服务的用户感知延迟的原因。随着这些系统成为通用基础设施，我们将发现这种用例只是冰山一角。询问和回答关于分布式执行的丰富“为什么”问题的能力将继续产生新的研究，从而提高大规模系统的一致性、可预测性和容错能力。

示例编程

作者：Sumit Gulwani

PBE（示例编程）是从底层程序空间合成或搜索满足给定输入-输出示例集的程序的任务。

PBE 的一个关键挑战是开发一种高效的搜索算法，该算法可以发现与示例一致的程序。已经开发了各种搜索技术，包括演绎方法、约束（SAT/SMT）求解器的使用、枚举搜索的智能启发式方法和随机搜索。PBE 的另一个关键挑战是处理意图规范中的歧义，因为有许多程序满足给定的示例，但不满足用户的意图。排序技术用于从与示例一致的程序集中预测预期程序。交互技术在细化循环中使用，以收敛到预期程序。

PBE 有多种应用。它允许最终用户（其中 99% 是非程序员）从示例中创建用于自动化重复性任务的小脚本。它促进了软件开发活动，包括程序重构、超级优化和测试驱动开发。以下最近发表的工作样本探讨了来自不同领域的应用，同时采用了不同类型的搜索和消除歧义算法。

使用反向传播的数据操作

Gulwani, S. 2011. 使用输入-输出示例自动化电子表格中的字符串处理。第 38 届 SIGPLAN-SIGACT 编程语言原理研讨会论文集：317-330。 https://www.microsoft.com/en-us/research/publication/automating-string-processing-spreadsheets-using-input-output-examples/

第一篇论文描述了一种用于自动化字符串转换的技术，例如将“FirstName LastName”转换为“LastName, FirstName”。该技术作为 Microsoft Excel 中的 Flash Fill 功能发布 (https://youtu.be/w-k9WjRJvIY)。该论文激发了对富有表现力的 DSL（领域特定语言）的设计，该 DSL 也受到足够的限制以允许高效搜索。灵感来自研究电子表格帮助论坛，最终用户在论坛中寻求字符串转换的帮助，同时使用示例描述他们的意图。该论文描述了一种领域特定的搜索算法，该算法实现了实时效率，打破了以前社区将搜索问题简化为查询现成的通用约束求解器的传统。后者虽然允许更快的原型设计，但缺乏自定义解决方案的有效性。

该论文还首次对处理歧义进行了处理，而不是需要更多的示例，从而提高了可用性和信任度。搜索算法返回大量（简洁表示的）满足示例的程序集，并且使用优先选择具有少量常量的较小程序的排序函数来猜测预期程序。

Flash Fill 的成功激发了学术界和工业界对为其他领域开发 PBE 技术的热情，包括数字/日期转换、从日志文件/网页/JSON 文档中提取表格数据以及重新格式化表格。由于数据科学家将 80% 的时间用于转换和清理数据以准备进行分析，因此 PBE 将通过实现更轻松、更快的数据操作来彻底改变这一领域。

Polozov, O., Gulwani, S. 2015. FlashMeta：归纳程序合成框架。2015 年 SIGPLAN 面向对象编程、系统、语言和应用程序国际会议论文集：107-126。 https://www.microsoft.com/en-us/research/publication/flashmeta-framework-inductive-program-synthesis/

开发和维护工业级 PBE 技术是一项智力和工程挑战，需要一到两个人年。第二篇论文观察到，许多 PBE 算法都是通用元算法和底层 DSL 中运算符逻辑属性的自然结果。元算法基于示例约束在底层 DSL 上的反向传播，将程序表达式的搜索问题简化为程序子表达式的更简单问题。元算法可以一劳永逸地实现。运算符属性与其逆语义相关，并且可以在多个 DSL 中重用。

这允许构建合成器生成器，该生成器接受 DSL 和 DSL 中运算符的语义属性，并生成领域特定的合成器。借助这样的生成器，PBE 技术变得模块化和可维护，从而促进了它们在工业产品中的集成。该框架已用于开发许多 PBE 工具，这些工具已部署在多个工业产品中，包括 Microsoft Operations Management Suite、PowerShell 3.0 和 Cortana 数字助理。

使用直接操作的绘图

Hempel, B., Chugh, R. 2016. 通过直接操作的半自动化 SVG 编程。第 29 届用户界面软件和技术研讨会论文集：379-390。 https://arxiv.org/abs/1608.02829

PBE 可以将直接 GUI（图形用户界面）操作（基于鼠标和菜单）和对数字工件（如电子表格、图像和动画）的编程操作的互补优势结合在一起。虽然直接操作可以轻松操作具体对象，但编程操作可以实现更大的自由度和可重用性（但需要技巧）。本文通过提出一种优雅的组合方法（称为直接操作编程）来弥合这一差距，该方法支持使用基于 GUI 的示例对象操作来创建和修改程序，用于 SVG（可缩放矢量图形）领域。

用户绘制形状，关联其属性，并使用 GUI 对其进行分组和编辑，并且绘图与底层程序保持同步。各种基于 GUI 的操作转化为示例绘图的约束。约束求解器用于生成对底层程序的候选修改，以便生成的程序执行生成满足这些约束的绘图。智能启发式方法用于从众多解决方案中选择预期的修改。熟练的用户可以在任何步骤编辑生成的程序，以改进自动生成的修改或实现一些新功能。

使用枚举搜索的超级优化

Phothilimthana, P. M., Thakur, A., Bodík, R., Dhurjati, D. 2016. 扩大超级优化规模。第 21 届编程语言和操作系统架构支持国际会议论文集：297-310。 https://people.eecs.berkeley.edu/~mangpo/www/papers/lens-asplos16.pdf

PBE 可用于解决从任意规范中进行程序合成的通用问题，前提是给定一个预言机，它可以生成合成工件与预期行为不匹配的反例。本文使用这种归约（也称为 CEGIS（反例引导的归纳合成））来推进超级优化领域的最新技术，超级优化是为给定代码片段找到最佳指令序列的问题。

本文的核心是一种新颖的基于枚举搜索的 PBE 算法，该算法按大小递增的顺序考虑底层状态空间中的程序。该算法利用一种优雅的记忆化策略，其中它计算满足给定示例集合的有界大小的程序集，并在下一次迭代中使用更多示例增量地细化该集合。程序使用它们在示例状态下的行为简洁地表示。该算法还利用了基于双向搜索的强大的中间相遇剪枝技术，其中候选程序从输入状态向前枚举，以及从输出状态向后枚举。

该论文进一步研究了不同搜索技术的优势和劣势，包括枚举搜索、随机搜索和基于求解器的搜索，并表明结合这些技术的协同搜索是最好的。

未来

PBE 可以被视为一种机器学习形式，其中问题是从非常少的示例中学习并在丰富的程序函数空间中学习。虽然过去 PBE 的发展利用了逻辑方法，但深度学习的最新进展能否推动前沿发展？另一个值得关注的令人兴奋的方向是基于自然语言的编程接口的开发。将基于示例和基于自然语言的意图规范相结合的多模式编程环境将开启大众编程的新时代。

致谢

感谢 Ravi Chugh、Phitchaya Mangpo Phothilimthana 和 Alex Polozov 为本文提供了有益的反馈。

Peter Bailis 是斯坦福大学计算机科学助理教授。他在未来数据系统组 (futuredata.stanford.edu/) 的研究重点是下一代数据密集型系统的设计和实现。他于 2015 年获得加州大学伯克利分校博士学位，并于 2011 年获得哈佛大学 A.B. 学位，均在计算机科学专业。

Peter Alvaro 是加州大学圣克鲁兹分校计算机科学助理教授，他在那里领导 Disorderly Labs 研究小组 (disorderlylabs.github.io)。他的研究重点是使用以数据为中心的语言和分析技术来构建和推理分布式系统，以便使它们可扩展、可预测且能够抵抗大规模分布固有的故障和不确定性。Alvaro 在加州大学伯克利分校获得博士学位，师从 Joseph M. Hellerstein。

Sumit Gulwani 领导微软的一个研究和工程团队，该团队开发用于数据整理的程序合成技术，并将其整合到实际产品中。他的示例编程工作促成了 Microsoft Excel 中 Flash Fill 功能的诞生，该功能被数亿人使用。Gulwani 共同撰写了约 50 项专利申请，在顶级会议/期刊上发表了 110 篇论文，涵盖多个计算机科学领域，并在各种论坛上发表了 30 次主题演讲/邀请演讲。由于他对最终用户编程和智能辅导系统的开创性贡献，他于 2014 年被授予 SIGPLAN Robin Milner 青年研究员奖。他从加州大学伯克利分校获得博士学位，并被授予 SIGPLAN 杰出博士论文奖。他于 2000 年获得印度理工学院坎普尔分校的学士学位，并被授予总统金牌。

最初发表于 Queue vol. 15, no. 1—
在数字图书馆中评论本文

更多相关文章

Charisma Chan, Beth Cooper - Debugging Incidents in Google’s Distributed Systems
本文介绍了 2019 年在 Google 工程师如何调试生产问题方面进行的研究成果，包括工程师在不同组合中使用以有效调试的工具类型、高级策略和低级任务。它考察了用于捕获数据的研究方法，总结了生产调查的常见工程历程，并分享了专家如何调试复杂分布式系统的示例。最后，本文将这项研究的 Google 特性扩展到提供一些您可以在组织中应用的实用策略。

Devon H. O'Dell - The Debugging Mindset
软件开发人员花费 35-50% 的时间来验证和调试软件。调试、测试和验证的成本估计占软件开发项目总预算的 50-75%，每年超过 1000 亿美元。虽然工具、语言和环境减少了花费在单个调试任务上的时间，但它们并没有显着减少花费在调试上的总时间，也没有减少调试的成本。因此，过度关注开发过程中消除错误是适得其反的；程序员应该将调试视为解决问题的练习。

Peter Phillips - Enhanced Debugging with Traces
创建用于运行旧程序的模拟器是一项艰巨的任务。您需要彻底了解目标硬件以及模拟器要执行的原始程序的正确功能。除了功能正确之外，模拟器还必须达到以原始实时速度运行程序的性能目标。实现这些目标不可避免地需要大量的调试。错误通常是模拟器本身中的细微错误，但也可能是对目标硬件的误解或原始程序中的实际已知错误。（原始程序的二进制数据也可能已变得略有损坏或不是预期的版本。）

Queue Readers - Another Day, Another Bug
作为本期关于程序员工具的一部分，我们在 Queue 决定就调试主题进行一项非正式的 Web 投票。我们请您告诉我们您使用的工具以及您如何使用它们。我们还收集了关于那些难以追踪的错误的故事，这些错误有时会让我们想到从事其他职业。