Hexo

end-to-end point

Posted on Edited on In
Symbols count in article: 9.1k Reading time ≈ 8 mins.

系统设计中的端到端论据

J.H. Saltzer, D.P. Reed 和 D.D. Clark*
麻省理工学院计算机科学实验室

作者地址：J.H. Saltzer 和 D.D. Clark，麻省理工学院计算机科学实验室，马萨诸塞州剑桥市科技广场545号，邮编02139；D.P. Reed，Software Arts, Inc.，马萨诸塞州韦尔斯利市Mica Lane 27号，邮编02181。
本研究部分由美国国防部高级研究计划局（ARPA）资助，海军研究办公室（ONR）根据合同号 N00014-75-C-0661 监督。
1981年4月8-10日法国巴黎第二届分布式计算系统国际会议论文修订版，第509-512页。© 1981 电气和电子工程师协会（IEEE）版权所有。经许可转载。
发表于《ACM计算机系统汇刊》第2卷第4期，1984年11月，第277-288页。
转载于 Craig Partridge 编辑的《互联网创新》，Artech House, Norwood, MA, 1988, 第195-206页。ISBN 0-89006-337-0。另计划转载于 Amit Bhargava 编辑的《综合宽带网络》，Artech House, Boston, 1991。ISBN 0-89006-483-0。
Scribe/FinalWord 源文件：http://web.mit.edu/Saltzer/www/publications/

摘要

本文提出了一种设计原则，用于指导在分布式计算机系统的模块间分配功能。该原则称为“端到端论据”，它指出，在系统低层提供的功能，与其在低层提供的成本相比，可能是冗余的或价值甚微。文中讨论的例子包括位错误恢复、使用加密的安全性、重复消息抑制、系统崩溃恢复以及交付确认。支持这些功能的低层机制，仅能作为性能增强手段来证明其合理性。

引言

在功能之间选择适当的边界，或许是计算机系统设计者的主要活动。为这种功能放置选择提供指导的设计原则，是系统设计者最重要的工具之一。本文讨论了一类功能放置论据，它已被使用多年，但既未被明确认识，也未被广泛信服。然而，数据通信网络作为计算机系统组件的出现，通过使其适用的情况和原因更加明显，从而突出了这条功能放置的论据。本文明确阐述了这一论据，以便审视其本质并了解其真正的普适性。该论据诉诸于应用需求，并为在分层系统中将功能向上移动、靠近使用该功能的应用程序提供了理论依据。我们首先考虑该论据在通信网络中的版本。

在一个包含通信的系统中，人们通常在通信子系统周围划定一个模块边界，并在它与系统其余部分之间定义一个严格的接口。这样做时，明显存在一个功能列表，其中每个功能都可以通过多种方式中的任意一种来实现：由通信子系统实现、由其客户端实现、作为联合项目实现，或者可能冗余地实现，各自执行自己的版本。在推理这种选择时，应用的需求提供了一类论据的基础，其内容如下：

端到端论据核心观点：
所讨论的功能只有借助通信系统端点的应用程序的知识和帮助，才能完整且正确地实现。因此，将该功能作为通信系统本身的特性提供是不可能的。（有时，通信系统提供的不完整版本的功能可能作为性能增强手段是有用的。）

我们称这种反对低层功能实现的推理为“端到端论据”。以下各节将详细探讨端到端论据，首先通过一个使用该论据的典型案例研究——所讨论的功能是可靠数据传输——然后展示该论据可适用的功能范围。对于数据通信系统的情况，这个范围包括加密、重复消息检测、消息排序、保证消息交付、检测主机崩溃以及交付回执。在更广泛的背景下，该论据似乎也适用于计算机操作系统的许多其他功能，包括其文件系统。然而，如果我们首先考虑更具体的数据通信背景，审视这个更广泛的背景将更容易。

端到端看护

考虑“谨慎文件传输”的问题。一个文件由文件系统存储在计算机 A 的磁盘存储器中。计算机 A 通过数据通信网络与计算机 B 相连，计算机 B 也有文件系统和磁盘存储。目标是将文件从计算机 A 的存储移动到计算机 B 的存储而不受损坏，同时意识到沿途的各个点都可能发生故障。这种情况下的应用程序是文件传输程序，其一部分在主机 A 运行，一部分在主机 B 运行。为了讨论此事务中文件完整性可能面临的威胁，我们假设涉及以下具体步骤：

  1. 在主机 A，文件传输程序调用文件系统从磁盘读取文件（文件驻留在多个磁道上），文件系统以固定大小的块（选择为独立于磁盘格式）将文件传递给文件传输程序。
  2. 在主机 A，文件传输程序要求数据通信系统使用某种通信协议传输文件，该协议涉及将数据拆分成数据包。数据包大小通常不同于文件块大小和磁盘磁道大小。
  3. 数据通信网络将数据包从计算机 A 移动到计算机 B。
  4. 在主机 B，一个数据通信程序从数据通信协议中取出数据包，并将其包含的数据交给文件传输应用程序的第二部分，即在主机 B 内操作的部分。
  5. 在主机 B，文件传输程序要求文件系统将接收到的数据写入主机 B 的磁盘。

根据这个涉及步骤的模型，谨慎的设计者可能会关注到事务的以下一些威胁：

  1. 磁盘读取错误： 文件虽然最初正确地写入主机 A 的磁盘，但现在读取时可能包含不正确的数据（磁盘硬件故障）。
  2. 软件错误： 文件系统、文件传输程序或数据通信系统的软件可能在缓冲和复制文件数据时出错（A 或 B）。
  3. 硬件瞬态错误： 硬件处理器或其本地内存在进行缓冲和复制时可能发生瞬态错误（A 或 B）。
  4. 通信错误： 通信系统可能会丢弃或更改数据包中的位，或丢失数据包，或多次传递同一个数据包。
  5. 主机崩溃： 在执行了未知数量（也许是全部）的事务后，任一主机都可能在中途崩溃。

那么，一个谨慎的文件传输应用程序将如何应对这个威胁列表呢？

  • 方法一（强化中间步骤）： 通过使用副本、超时和重试、精心放置的用于错误检测的冗余、崩溃恢复等来强化沿途的每一步。目标是将每个单独威胁的发生概率降低到一个可接受的微小值。缺点： 应对威胁二（软件错误）需要编写绝对正确的程序，非常困难且非所有相关程序都由文件传输程序员控制。如果所有威胁概率都较低，强力对策（如三重复制）显得不经济。
  • 方法二（端到端检查和重试）： 每个文件存储一个具有足够冗余的校验和，将未检测到错误的机会降至可忽略水平。应用程序完成传输步骤后，主机 B 端的程序读取传输的文件，重新计算校验和，将其发送回主机 A 与原始校验和比较。只有一致才声明事务提交。失败则从头重试。优点： 如果故障罕见，通常一次成功；重试成本低；最终结果可靠。

关键分析： 假设通信系统内部提供了可靠数据传输保证（例如，通过数据包校验和、序号检查、内部重试）。这可以消除威胁四（通信错误），但谨慎的文件传输应用仍需应对其他威胁（1,2,3,5），因此它仍需基于文件的端到端校验和提供自己的重试。通信系统的额外努力仅减少了应用层重试的频率，对结果的必然性或正确性没有影响（因为无论通信层可靠性如何，端到端校验和与重试保证了最终正确性）。

结论（端到端论据）： 为了实现谨慎的文件传输，执行传输的应用程序必须提供文件传输特定的、端到端的可靠性保证（校验和 + 重试/提交计划）。让数据通信系统额外付出努力去追求异常高的可靠性，并不会减轻应用程序确保可靠性的负担。

一个过于真实的例子

一个麻省理工学院的案例：一个由网关连接多个局域网的网络系统在每跳（网关间）使用了数据包校验和。应用程序员因此假设网络提供可靠传输，忽略了数据在网关内存中存储时不受保护。一个网关在复制数据时出现瞬态错误（字节对互换，频率约百万分之一）。一段时间内，操作系统源文件反复通过此网关传输，部分文件被损坏。最终，所有者被迫进行最终的端到端错误检查：手动对照旧列表比对和修正。

性能方面

如果得出结论说低层在获得可靠性方面不应起任何作用，那就过于简单化了。考虑一个不可靠网络（例如，丢包率1%）。简单的端到端策略（传整个文件后校验）随着文件长度增加，性能急剧下降（所有包正确到达的概率指数下降，预期传输时间指数增长）。显然，在低层付出一些努力提高网络可靠性（如包级校验重传），可以显著改善应用性能。但关键思想是：低层无需提供“完美”可靠性。

  • 工程权衡： 在数据通信系统中投入多少可靠性措施的努力，是基于性能的权衡，而非正确性的要求。
  • 性能成本的两个方面：
    1. 通信系统不可靠： 导致应用层频繁重试（端到端校验失败），性能差。
    2. 通信系统加强内部可靠性： 措施本身有成本（冗余数据占用带宽，内部一致性检查引入延迟）。
  • 权衡原则： 无论通信系统多可靠，应用层的端到端检查必须存在。因此，没必要追求应用层以下点的可忽略错误率。一个“恰当”的权衡：设计通信系统提供低成本、低工程代价的可靠性，评估残余错误水平，确保其与应用层可接受的重试频率一致。
  • 性能增强放置的复杂性： 将功能放在低层以提升性能需谨慎。有时高层能实现相同或更好的增强。低层执行可能更高效（若对现有机制扰动小），但也可能成本更高：
    • 低层子系统被多个应用共享，不需要该功能的应用也需付费。
    • 低层可能缺乏高层信息，无法高效完成任务。
  • 示例（文件传输于不可靠网络）： 早期重试机制（如接收方定期校验已接收部分并反馈，发送方重传出错部分）可放在通信层或应用层。
    • 放应用层： 简化通信系统，但增加总体成本（每个应用需实现自己的增强）。
    • 放通信层： 可能更高效（网络内按跳重试，减少延迟），但强制不需要该增强的应用付费。
    • 端到端论据未指明放置位置： 需根据具体系统信息权衡。

端到端论据的其他例子

交付保证 (Delivery Guarantees)

  • 问题： 通信网络（如ARPANET）提供消息送达目标主机的确认（如RFNM）。
  • 端到端观点： 知道消息送达主机不重要。应用需要知道的是目标应用是否处理了该消息（交付后、处理前仍可能出错）。真正需要的确认是端到端的（由目标应用发起 - “我做了”或“我没做”）。
  • 替代策略的局限性： 让目标主机承诺交付即处理，可消除某些应用的端到端确认需求，但不适用所有情况（如需要多主机协调的两阶段提交协议，或需要处理应用失败/拒绝的情况）。

数据的安全传输 (Secure Transmission of Data)

  • 问题： 通信系统提供自动加密所有流量。
  • 端到端观点（三方面）：
    1. 通信系统加密需信任其安全管理密钥。
    2. 数据在目标节点内及分发到目标应用过程中是明文，易受攻击。
    3. 消息的真实性仍需由应用检查。
  • 结论： 满足应用安全需求（认证、密钥管理、端到端保密），不需要通信子系统自动加密所有流量。端到端加密是解决方案。
  • 补充： 网络级自动加密（使用简单密钥，频繁更换）可作为防止信息泄露的防火墙，但这与应用级认证和访问控制是不同的、互补的需求。

重复消息抑制 (Duplicate Message Suppression)

  • 问题： 网络可能因内部重试机制导致消息重复交付。网络可提供抑制重复功能。
  • 端到端观点： 即使网络抑制了内部重复，应用自身在其故障/重试过程中也可能产生应用级重复请求（对网络是不同消息，无法抑制）。应用必须有能力检测和抑制自己的重复。因此，这个机制可以放在应用层，网络层的重复抑制功能可以省略（应用层机制也能处理网络产生的重复）。该推理同样适用于消息丢失（应用需检测并重试）。

保证先进先出 (FIFO) 消息传递 (Guaranteeing FIFO Message Delivery)

  • 问题： 通信系统通常保证同一虚电路上消息的FIFO交付。
  • 端到端观点： 对于跨多个独立虚电路或涉及外部进程的分布式应用（如一个节点发起需在多个站点执行动作的请求），通信系统提供的FIFO保证不足以保证动作按正确顺序发生。必须在高于通信子系统的层级（应用层或中间件层）使用独立机制控制动作的排序。

事务管理 (Transaction Management) - SWALLOW 系统案例

  • 设计： SWALLOW 分布式数据存储系统应用端到端论据显著降低开销。
  • 省略网络层功能：
    • 重复抑制： 不提供。理由：a) 对象ID+版本信息足以检测重复写入；b) 重复读请求只产生重复响应，发起方可轻松丢弃。简化了底层通信协议。
    • 交付确认： 不提供。写操作需要的确认是“数据安全存储”，只能由SWALLOW高层提供。读操作的响应本身即是确认。减少了一半的消息量，降低主机和网络负载，提高性能。
  • 结论： 基于应用语义，省略低层通用功能是可行且高效的。

识别端点 (Identifying the Ends)

端到端论据的应用需要细致分析具体应用需求。

  • 示例1 - 实时语音通话：
    • 应用需求： 恒定速率数据流，低延迟至关重要。少量数据损坏或丢失可接受（语音冗余，高层纠错如“请再说一遍”）。
    • 端到端论据应用： 低层追求比特完美（如重传损坏包）引入的延迟破坏性大于数据损坏本身。低层应接受轻微损坏或使用插值/静音，避免重传。可靠性主要由高层（用户交互）处理。
  • 示例2 - 语音留言系统：
    • 应用需求： 数据存储供日后收听。延迟不重要，但记录准确性至关重要（收听时无法请求重发）。
    • 端到端论据应用： 低层引入延迟以追求可靠性的措施不再被反对。端到端论据主要应用于数据包排序和重复抑制（确保存储文件正确）。
  • 关键点： 端到端论据不是绝对规则，而是指导协议和应用设计的分析工具。必须谨慎识别特定应用的“端”在哪里以及其具体需求。

历史以及在其他系统领域的应用

  • 起源： 文中例子非首创，是多年积累。作者首次注意到可疑中间确认是MIT CTSS系统的“wait”消息[3]。加密相关的论据由Branstad(1973)[2]首次公开讨论。
  • 数据库与分布式系统： 两阶段提交协议(Gray[5], Lampson & Sturgis[10], Reed[13,14])是端到端协议的典范（不依赖底层通信的完美性）。
  • 应用系统错误控制：
    • 银行系统： 高层审计程序（策略和法律要求）会捕获高低层错误。消除协调错误的昂贵算法不如使错误罕见的低成本算法合适。
    • 航空订票： 代理会持续尝试直至确认或拒绝。低层保证未确认请求在崩溃后存活的恢复机制非必需。
    • 电话交换机： 导致单次呼叫丢失的故障不值得提供显式恢复（用户会重拨）[7]。
  • 网络协议争论（数据报 vs. 虚电路）： 本质是关于端到端论据的辩论。虚电路提供易用的可靠流；端到端论据主张其功能对某些应用不完整，从数据报开始自建更灵活。
  • 磁带存储系统（1950年代）： 反复尝试构建“可靠磁带子系统”失败（磁带机不稳定、操作员不可靠、系统崩溃）。最终标准做法是每个应用提供自己的应用相关检查和恢复策略，假设低层错误检测仅减少高层检查失败的频率（如Multics备份系统[17]在强大磁带格式上仍用记录标签和文件多副本）。
  • RISC架构： 类似论据。让客户端（编译器）用基本指令实现所需功能性能更好；设计师预判深奥功能需求易失准，客户端终将重实现。
  • 开放操作系统 (Lampson[9])： 反对将任何功能永久固化在低层；低层提供的功能应总是可被应用的特殊版本替换。理由：任何功能总有一些应用为正确满足自身需求必须自己实现。这催生了由可替换库例程构成整个OS的“开放”系统概念（近期在单应用计算机上才可行）。典型大型OS的大量固定管理程序功能可能是复用昂贵硬件经济压力的产物。近期系统“内核化”项目[16,12]旨在将功能移出低层，虽动机不同（正确性），但副作用是使OS对应用更灵活，契合端到端论据主旨。

结论

  • 端到端论据是选择通信子系统功能时的一种“奥卡姆剃刀”。通信子系统常在应用未知时被设计，易诱使设计师通过承担过多功能来“帮助”用户。了解端到端论据有助于减少此类诱惑。
  • 分层通信协议是趋势，但缺乏明确的分层标准。分层利于模块化。端到端论据可视为组织此类分层系统的理性原则集的一部分。希望本文讨论有助于为关于“恰当”分层的争论增添实质内容。

致谢

感谢David Cheriton, F.B. Schneider, Liba Svobodova等人对本文初稿的审阅和评论。该主题也在1980年12月加州Fallbrook举行的ACM分布式计算基础研讨会上进行了讨论。这些评论和讨论对澄清论据非常有帮助。

参考文献

  1. Bolt Beranek and Newman Inc. Specifications for the interconnection of a host and an IMP. Technical Report No. 1822, Cambridge, Mass., December, 1981.
  2. Branstad, D.K. Security aspects of computer networks. AIAA Paper No. 73-427, AIAA Computer Network Systems Conference, Huntsville, Alabama, April, 1973.
  3. Corbato, F.J., et al. The Compatible Time-Sharing System, A Programmer’s Guide. M.I.T. Press, Cambridge, Massachusetts, 1963, p.10.
  4. Diffie, W., and Hellman, M.E. New directions in cryptography. IEEE Trans. on Info. Theory, IT-22, 6, (November, 1976), pp.644-654.
  5. Gray, J.N. Notes on database operating systems. In Operating System: An Advanced Course. Volume 60 of Lecture Notes in Computer Science, Springer-Verlag, 1978, pp.393-481.
  6. Greenwald, M. Remote virtual disk protocol specifications. M.I.T. Laboratory for Computer Science Technical Memorandum, in preparation. Expected publication, 1984.
  7. Keister, W., Ketchledge, R.W., and Vaughan, H.E.: No. 1 ESS: System organization and objectives. Bell System Technical Journal 53, 5 (part 1), (September, 1964) p. 1841.
  8. Kent, S.T.: Encryption-based protection protocols for interactive user-computer communication.: S.M. thesis, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, May, 1976. Also available as M.I.T. Laboratory for Computer Science Technical Report, TR-162, May, 1976.
  9. Lampson, B.W., and Sproull, R.F. An open operating system for a single-user machine. Proc. Seventh Symposium on Operating Systems Principles, Operating Systems Review 13, Special issue (December, 1979), pp.98-105.
  10. Lampson, B., and Sturgis, H: Crash recovery in a distributed data storage system. Working paper, Xerox PARC, November, 1976 and April, 1979. Submitted to CACM.
  11. Needham, R.M., and Schroeder, M.D.: Using encryption for authentication in large networks of computers. CACM 21, 12, (December, 1978), pp.993-999.
  12. Popek, G.J., et al.: UCLA data secure unix. Proc. 1979 NCC, AFIPS Press, pp.355-364.
  13. Reed, D.P.: Implementing atomic actions on decentralized data. ACM Transactions on Computer Systems 1, 1 (February, 1983), pp.3-23.
  14. Reed, D.P.: Naming and synchronization in a decentralized computer system. Ph.D. thesis, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, September 1978. Also available as M.I.T. Laboratory for Computer Science Technical Report, TR-205, September, 1978.
  15. Reed, D.P., and Svobodova, L.: SWALLOW: A distributed data storage system for a local network. In West, A., and Janson, P., ed. Local Networks for Computer Communications, Proc. IFIP Working Group 6.4 International Workshop on Local Networks. North-Holland, Amsterdam, 1981, pp.355-373.
  16. Schroeder, M.D., Clark, D.D., and Saltzer, J.H.: The Multics kernel design project. Proc. Sixth Symposium on Operating Systems Principles, Operating Systems Review 11, 5 (November, 1977), pp.43-56.
  17. Stern, J.A.: Backup and recovery of on-line information in a computer utility. S.M. thesis, M.I.T. Department of Electrical Engineering and Computer Science, August 1973. Available as M.I.T. Project MAC Technical Report TR-116, January, 1974.
-------------本文结束 感谢阅读-------------