                              Matt Welsh, David Culler, and Eric Brewer
                               Computer Science Division
      University of California, Berkeley {mdw,culler,brewer}@cs.berkeley.edu

概述

我们为高度并发的Internet服务提出了一种新设计，我们将其称为分阶段事件驱动架构（SEDA）。SEDA旨在支持大规模并发需求并简化良好服务的构建。在SEDA中，应用程序由通过显式队列连接的阶段事件驱动网络组成。这种架构使服务具有良好的负载，在需求超过服务容量时防止资源过度使用。尽管负载波动很大，但SEDA利用一组动态资源控制器将各阶段保持在其运行状态。我们描述了几种用于自动调整和负载调节的控制机制，包括线程池大小调整，事件批处理和自适应负载消减。我们介绍了SEDA设计以及基于该架构的互联网服务平台的实现。我们通过两个应用程序评估SEDA的使用：用于Gnutella（无结构的P2P网络代表软件）对等文件共享网络的高性能HTTP服务器和数据包路由器。这些结果表明，SEDA应用程序表现出比传统服务设计更高的性能，并且对于负载的巨大变化具有稳健性。

1引言

      互联网呈现出前所未有的计算机系统问题：要求支持数百万用户的访问，服务必须是相应的、稳健的、始终可用的。Internet站点每天的并发会话数和点击次数转化为更多的I/O和网络请求，对底层资源提出了巨大的要求。雅虎每天收到超过12亿的页面浏览量，AOL的网络缓存每天提供超过100亿次点击。此外，互联网服务在服务负载方面经历巨大变化，突发与服务具有最大价值的时间一致。详细记录的“Slashdot效应”表明，当网站变得流行时，需求增长超过100倍并不罕见。随着对互联网服务的需求的增长，必须使用新的系统设计技术来管理这种负载。
      这种系统挑战被三种趋势放大，这些趋势增加了服务的普遍性。首先，服务本身变得越来越复杂，静态内容被涉及大量计算和I/O的动态内容所取代。其次，服务逻辑趋于快速变化，这增加了工程和部署的复杂性。第三，服务越来越多地托管在通用设施上，而不是在为特定服务精心设计的平台上。随着这些趋势的继续，我们设想将创建一系列丰富的新颖服务并将其推入基础设施，在这些基础设施中，它们可能会成功扩展到数百万用户。一些研究正在解决服务的高级方面，包括命名，查找，组合和版本控制。我们将重点放在问题的性能方面：在负载变化很大的情况下，在广泛的服务上实现强大的性能，同时保持其易用性。复制是服务可伸缩性的关键方面。给定一个可以维持一定性能水平的服务实例，必须复制它以维持负载的多倍增加，可扩展的集群现在被广泛用于在服务站点内获得复制，并且广泛的复制越来越多地用于特定服务，例如内容分发网络。但是，因为峰值负载可能比平均值大几个数量级，所以它不实用。复制大多数服务以处理最大的潜在需求。因此，我们预计每个节点所承受的负载会出现大幅峰值。我们的目标是开发一个通用框架，用于创建高度并发且运行良好的服务实例，以便优雅地处理负载。
      遗憾的是，传统的操作系统设计和广泛推广的并发模型并不能提供这种优雅的负载管理。商品操作系统专注于通过为每个进程提供独有的CPU，内存，磁盘和网络的虚拟机的抽象来提供最大的透明度。这个目标与互联网服务的需求有些不一致，互联网服务需要大量的并发性和对资源使用的广泛控制。进程和线程是良好支持的并发编程模型，但在上下文切换时间和内存占用方面往往需要很高的开销，这限制了并发性。透明的资源虚拟化阻止了应用程序做出明智的决策，这对于管理过多的负载至关重要。大多说工作都侧重于特定服务的性能和稳健性。然而，随着服务变得越来越动态和灵活，这种工程负担变得过度。很少有工具可以帮助开发高度并发，运行良好的服务; 我们的目标是通过提供帮助软件开发人员获取这些属性的通用机制来降低这种复杂性。
      我们为高度并发的服务器应用程序提出了一个新的设计框架，我们将其称为分阶段事件驱动架构（SEDA）。SEDA结合了线程和基于事件的编程模型的各个方面来管理Internet服务的并发性，I/O，调度和资源管理需求。在SEDA中，应用程序被构建为阶段网络，每个阶段都具有关联的传入事件队列。每个阶段可以通过单独调节负载阈值或过滤其事件队列来构建一个健壮的模块。此外，使事件队列显式化允许应用程序进行合适的调度和资源管理决策，例如重新排序，过滤或聚合请求。SEDA利用动态资源限制来控制应用程序组件的资源分配和调度，使系统能够适应过载状态。
      本文描述了基于SEDA的Internet服务平台的设计，体系结构和实现。该平台提供高效，可扩展的I/O接口以及多种资源控制机制，包括线程池大小调整和动态事件调度。我们通过两个应用程序评估框架 – 一个高性能HTTP服务器和一个用于Gnutella对等文件共享网络的数据包路由器。我们为这些应用提供了性能和可扩展性结果，证明了SEDA在负载的巨大变化上实现了稳健性，并且优于其他服务设计。我们基于Java的SEDA HTTP服务器优于基于C实现的两个流行的Web服务器，如第5.1节所述。我们认为使用SEDA，高度并发的应用程序更容易构建，更高效，更强大的负载。通过正确的接口，应用程序设计人员可以专注于特定于应用程序的逻辑，而不是并发和资源管理的细节。

2背景和相关工作

      SEDA汇集了两个重要的研究领域：使用基于线程的并发模型来简化编程，使用基于事件的模型来实现大规模的并发。本节通过概述主导SEDA设计的步骤中的关键贡献和问题来阐明开发这种方法的谱系。
      直观地说，如果服务的行为类似于简单的管道，那么服务就是运行良好的，管道的深度由通过网络的路径和服务本身内的处理阶段决定。随着提供的负载增加，交付的吞吐量按比例增加，直到管道充满并且吞吐量饱和; 额外的负载不应该降低吞吐量。类似地，服务所呈现的响应时间在轻负载时大致恒定，因为它由管道的深度支配。当负载接近饱和时，排队延迟占主导地位。在许多服务典型的闭环场景中，每个客户端在提交下一个请求之前等待响应，响应时间应随客户端数量线性增加。
      良好的服务的关键属性是优雅降级：当提供的负载超过容量时，服务保持高吞吐量，线性响应时间损失同等地影响所有客户端，或者至少根据某些特定于服务的策略可预测影响。请注意，这不是典型的Web体验; 相反，随着负载的增加，吞吐量会降低，响应时间也会大幅增加，从而产生服务崩溃的印象。

2.1 基于线程的并发

      服务器应用程序最常用的设计是thread-per-request线程模型，如RPC包，Java远程方法调用和DCOM中所体现的。当前的语言和编程环境很好地支持这个模型。在此模型中，如图1所示，每个接受的请求都使用一个线程来处理它，同步操作受保护的共享资源。操作系统通过在线程之间透明切换来交叉计算和I/O.

图1：线程服务器设计：将每个传入请求分派到一个单独的线程，该线程处理请求并将结果返回给客户端。边表示分支之间的控制流。请注意，此处未显示其他I/O操作（如磁盘访问），但会将其合并到每个线程的请求处理中。
      尽管编程相对容易，但与线程相关的开销（包括缓存和TLB未命中，调度开销和锁争用）当线程数量变大时，会导致严重的性能下降。作为一个具体示例，图2显示了随着线程数量的增加，简单线程服务器的性能。尽管有效的线程限制对于通用分时来说会很大，但它不足以满足Internet服务的巨大并发要求。

图2：线程服务器吞吐量降低
纵坐标表示吞吐量（每秒任务数）横坐标表示线程数
红线代表吞吐量蓝线代表实际延迟走势紫线代表理想状态下线性延迟走势
此基准测试用于测量一个简单的线程服务器，该服务器为管道中的每个任务创建单个线收到任务后，每个线程从磁盘文件执行8 KB读取; 所有线程都从同一个文件读取，因此数据总是在缓冲区缓存中。线程在服务器中预先分配，以消除测量中的线程启动开销，并在内部生成任务以消除网络效应。该服务器采用C语言实现，运行在Linux 2.2.14下的4路500 MHz Pentium III和2 GB内存上。随着并发任务数量的增加，吞吐量会增加，直到线程数量增大，之后吞吐量会大幅下降。随着任务队列长度的增加，响应时间变得无限制; 为了比较，我们已经显示了理想的线性响应时间曲线（注意x轴上的对数刻度）。
      线程和进程主要用于支持多道程序设计，现有的OS力求以对应用程序透明的方式虚拟化硬件资源。应用程序很少有机会参与系统范围的资源管理决策，或者给出资源可用性的指示，以使其行为适应不断变化的条件。虚拟化从根本上隐藏了资源有限和共享的事实。
      许多系统试图通过向应用程序公开更多控制来解决这个问题。调度程序激活[5]，应用程序特定处理程序[59]和操作系统（如SPIN [11]，Exokernel [28]和Nemesis [34]）都试图通过为应用程序提供特化内核做出的决策的能力来增强有限的操作系统接口。然而，这些系统的设计仍然基于多道程序设计，因为重点仍然放在安全和有效的资源虚拟化上，而不是优雅的管理和高并发性。

2.2 有界线程池

      为了避免过度使用线程，许多系统采用粗略形式的负载调节，用于绑定与服务关联的线程池的大小。当服务器中的请求数超过某个固定限制时，不接受其他连接。 Web服务器（如Apache [6]，IIS [38]和Netscape Enterprise Server [42]）以及应用程序服务器（如BEA Weblogic [10]和IBM WebSphere [25]）使用此方法。通过限制并发线程的数量，服务器可以避免吞吐量降低，并且整体性能比无约束的每任务线程模型更强大。但是，这种方法会给客户端带来很多不公平：当所有服务器线程忙或被阻塞时，客户端请求在网络中排队等待服务。正如我们将在5.1节中所示，这可能导致客户端经历任意大的等待时间。
      当每个请求由单个线程处理时，很难识别内部性能瓶颈以执行调整和负载调节。考虑一个简单的线程Web服务器，其中一些请求处理起来成本低廉（例如，缓存的静态页面）而其他请求则很昂贵（例如，不在缓存中的大页面）。对于许多并发请求，昂贵的请求可能是性能瓶颈的来源，因此需要执行减载。但是，服务器无法检查内部请求流以实现此类策略; 它所知道的是线程池已经饱和，并且一定是在不知道瓶颈来源的情况下随意拒绝工作。
      资源容器[7]和来自Scout操作系统[41,49]的路径概念是两种可用于限制服务器中任务的资源使用的技术。这些机制将垂直资源管理应用于一组软件模块，允许整个数据流通过系统的资源作为一个单元进行管理。在上述瓶颈的情况下，限制给定请求的资源使用，将避免由于高速缓存未命中而导致的降级，但允许高速缓存命中继续进行。

2.3事件驱动的并发

      线程的可伸缩性限制导致许多开发人员几乎完全避开它们，并采用事件驱动的方法来管理并发。在这种方法中，如图3所示，服务器由少量线程（通常每个CPU一个）组成，它们不断循环，处理队列中不同类型的事件。事件可以由操作系统生成，也可以由应用程序在内部生成，通常对应于网络和磁盘I/O就绪和完成通知，定时器或其他特定于应用程序的事件。事件驱动方法将每个任务的处理实现为有限状态机，其中FSM（finite state machine）中的状态之间的转换由事件触发。通过这种方式，服务器为每个任务维护自己的连续状态，而不是依赖于线程上下文。

图3：事件驱动的服务器设计：此图显示了通过事件驱动的服务器的事件流。主线程处理来自网络，磁盘和其他来源的传入事件，并使用它们来驱动许多有限状态机的执行。每个FSM代表通过系统的单个请求或执行流程。此设计的复杂性的关键来源是事件调度程序，它必须控制每个FSM的执行。
      事件驱动设计被许多系统使用，包括Flash [44]，thttpd [4]，Zeus [63]和JAWS [24] Web服务器以及Harvest [12] Web缓存。在Flash中，服务器的每个组件都响应特定类型的事件，例如套接字连接或文件系统访问。主服务器进程负责不断地将事件分派给每个组件，这些组件实现为库调用。因为某些I/O操作（在这种情况下，文件系统访问）没有异步接口，所以主服务器进程通过IPC将它们分派给辅助进程来处理这些事件。帮助程序处理发出（阻塞）I/O请求并在完成时将事件返回到主进程。Harvest的结构非常相似：它是单线程和事件驱动的，但FTP协议除外，它由一个单独的进程实现。(Harvest:google搜索到是一款面向自由职业者和小型企业的时间跟踪和在线发票应用程序。)
      线程和事件驱动的并发模型之间的权衡已经在JAWS Web服务器中进行了广泛的研究[23,24]。JAWS(一个高性能的web服务器架构，jaws设计论文)为Web服务器构建提供了一个框架，允许自定义并发模型，协议处理代码，缓存文件系统和其他组件。与SEDA一样，JAWS强调服务设计中适应性的重要性，通过促进服务框架中的静态和动态适应性。据我们所知，JAWS仅在轻载（少于50个并发客户端）下进行了评估，并未解决在高负荷下使用适应性进行调节的问题。
      事件驱动系统往往对负载具有稳定性，随着提供的负载增加超出饱和度，吞吐量几乎没有降低。图4显示了使用图2中的服务的事件驱动版本实现的吞吐量。随着任务数量的增加，服务器吞吐量会增加，直到管道填满并且瓶颈（在这种情况下为CPU）变得饱和。如果管道中的任务数量进一步增加，则多余的任务将被吸收在服务器的事件队列中。吞吐量在很大的负载范围内保持不变，每个任务的延迟线性增加。

图4：事件驱动的服务器吞吐量：该基准测试用于测量图2中服务器的事件驱动版本。在这种情况下，服务器使用单个线程来处理任务，其中每个任务从单个磁盘文件读取8 KB。尽管此处使用的操作系统（Linux 2.2.14）提供的文件系统接口是阻塞的，但由于磁盘数据始终位于缓存中，因此此基准测试可估算非阻塞磁盘I/O层的最佳性能。如图所示，当负载增加到非常大量的任务时，吞吐量保持不变（注意图2中水平轴刻度的变化），响应时间是线性的（注意x轴上的对数刻度）。
      此模型的一个重要限制是它假定事件处理线程不会阻塞，因此必须使用非阻塞I/O机制。虽然许多先前的工作已经研究了可伸缩的I/O原语[8,9,33,46,48]，但由于中断，页面错误或垃圾收集，事件处理线程会造成阻塞而不管所使用的I/O机制如何。
      事件驱动的设计为应用程序开发人员带来了许多额外的挑战。事件的调度和排序可能是最重要的问题：应用程序负责决定何时处理每个传入事件以及处理多个流的FSM的顺序。为了平衡公平性和低响应时间，应用程序必须仔细地复用多个FSM的执行。事件调度算法的选择通常是针对特定应用而定制的，并且新功能的引入可能需要重新设计算法。此外，模块化很难实现，因为必须信任实现每个状态的代码，以阻止或消耗大量可能使事件处理线程停滞的资源。

2.4结构化事件队列

      已经提出了关于标准事件驱动设计的若干变体来解决上述问题。这些设计的一个共同方面是使用一组事件队列构建事件驱动的应用程序，以提高代码模块性并简化应用程序设计。
      Click模块化分组路由器(Click路由器论文)[40]就是这样一个例子。在Click中，数据包处理阶段由具有自己的私有状态的单独代码模块实现。Click经过优化，可通过路由器改善每个数据包的延迟，允许单个线程直接通过多个数据包处理阶段进行调用。此设计针对特定应用程序（路由），单个线程为所有事件队列提供服务。Click假设模块具有有限的处理时间，从而导致相对静态的资源管理策略。Qie(Qie路由器论文)等。[47]还描述了在基于软件的路由器中调度和负载调节的技术; 与SEDA一样，他们的设计利用控制器根据负载动态调整运行时参数。
      Gribble的分布式数据结构（DDS）[20]层也使用了结构化的事件处理框架。在DDS中，存储服务器通过使用固定大小的线程池来模拟异步网络和磁盘I/O接口，并且使用显式事件队列或隐式上行调用来组成软件组件。Work Crews [56]和TSS/360队列扫描程序[35]是利用结构化事件队列和有限数量的线程来管理并发性的系统的其他示例。在这些系统的每一个中，事件队列的使用解耦了两个组件的执行，这提高了模块性和稳定性。
      StagedServer [31]是另一个利用显式事件队列进行通信的系统。在这种情况下，目标是通过仔细调度每个模块中的线程和事件来最大化处理器缓存局部性。通过聚合队列中多个类似事件的执行，增强了局部性，从而提高了性能。（译者注：线程跳转越少，局部性就会更好）
      Lauer和Needham的经典论文[32]讨论了通过消息进行通信的过程的优点，并将这种方法与“procedures”的方法进行了对比，这与上述线程模型密切相关。 SEDA可以看作是那里讨论的面向消息的模型的一个实例。作者声称基于消息和基于过程的模型是彼此的双重性，并且在一个模型中实现的任何程序都可以在另一个模型中有效地实现。虽然我们同意这种基本情绪，但这一论点忽略了构建可扩展通用多线程的复杂性，以及在没有显示请求队列的情况下在基于线程的模型中调整负载的固有困难。

3分阶段事件驱动架构

在本节中，我们提出了一种新的软件架构，即分阶段事件驱动架构（SEDA），旨在实现Internet服务的高并发性，负载调节和易于设计。SEDA将应用程序分解为由事件队列分隔的阶段网络，并引入动态资源控制器的概念，以允许应用程序动态调整以适应不断变化的负载。SEDA服务设计方法概述如图5所示。

图5：分阶段事件驱动（SEDA）HTTP服务器：这是基于SEDA的Web服务器的结构表示，在5.1节中有详细描述。应用程序由一组由队列分隔的阶段组成。边缘代表阶段之间的事件流。每个阶段都可以独立管理，阶段可以按顺序或并行运行，也可以两者结合使用。事件队列的使用允许每个阶段单独地加载条件，例如，通过对其事件队列进行阈值处理。为简单起见，从该图中省略了一些事件路径和阶段。

3.1目标

SEDA的主要目标如下：
支持大规模并发：为避免因为线程导致性能下降，SEDA尽可能使用事件驱动的执行。这还要求系统提供高效且可扩展的I/O原语。
简化良好条件服务的构建：为了降低构建Internet服务的复杂性，SEDA保护应用程序开发者免受许多调度和资源管理的细节。该设计还支持这些应用程序的模块化构造，并为调试和性能分析提供支持。
启用自我检查：应用程序应该能够分析请求流，以使行为适应不断变化的负载条件。例如，系统应该能够确定优先级并过滤请求，以支持在高负载下降级服务。
支持自我调优资源管理：系统应该动态调整其资源管理参数以满足性能目标，而不是强制要求应用程序资源需求和客户端负载特性的先验知识。例如，分配给阶段的线程数可以根据感知的并发需求自动确定，而不是由程序员或管理员硬编码。

3.2作为健壮构建块的阶段

      SEDA内的基本处理单位是stage。stage是一个独立的应用程序组件，由事件处理程序，传入事件队列和线程池组成，如图6所示。每个阶段由影响调度和线程分配的控制器管理，如下所述。阶段线程通过从传入事件队列中拉出一批事件并调用应用程序提供的事件处理程序来进行操作。事件处理程序处理每批事件，并通过将它们排入其他阶段的事件队列来调度零个或多个事件。

图6：SEDA阶段：阶段由传入事件队列，线程池和应用程序提供的事件处理程序组成。阶段的操作由控制器管理，控制器动态调整资源分配和调度。
      线程是SEDA中的基本并发机制，但它们的使用仅限于每个阶段的少量线程，而不是系统中每个任务一个线程。此外，动态控制的使用（参见3.4节）可以根据需求自动调整分配给每个阶段的线程数。此设计允许阶段按顺序或并行运行，或两者的组合，取决于线程系统和调度程序的特性在本文中，我们假设在SMP环境中的操作系统支持抢占式线程，尽管这种选择不是SEDA设计的基础。例如，可以设计一个线程系统，它认识到应用程序的分阶段结构并相应地调度线程。我们在3.4节回到这个问题。
      每个阶段的核心逻辑由事件处理程序提供，其输入是一批多个事件。事件处理程序无法直接控制队列操作或线程。通过将核心应用程序逻辑与线程管理和调度分离，该阶段能够控制事件处理程序的执行以实现各种资源管理策略。例如，传递给事件处理程序的事件的数量和顺序可以由运行时环境在外部控制。但是，应用程序还可以通过过滤或重新排序传递给它的事件批来实现自己的调度策略。

3.3作为阶段网络的应用

      SEDA应用程序构建为阶段网络，由事件队列连接。事件处理程序可以通过首先获取该阶段的传入事件队列的句柄（通过系统提供的查找例程），然后在该队列上调用入队操作，将事件排入另一个阶段。
SEDA中事件队列的一个重要方面是它们可能是有限的：也就是说，如果队列希望拒绝新条目（例如，因为它已达到阈值），则入队操作可能会失败。当排队操作失败时，应用程序可以使用背压（通过阻塞整个队列）或减载（通过丢弃事件）。或者，应用程序可能希望采取某些特定于服务的操作，例如向用户发送错误，或执行替代功能，例如提供降级服务。
      图5说明了基于SEDA的应用程序的结构，在本例中是5.1节中描述的Haboob Web服务器。该应用程序包含许多特定于应用程序的阶段，用于处理HTTP请求，实现页面缓存等，以及运行时提供的几个通用阶段，以支持异步I/O. 这些接口在第4节中进一步描述。
      阶段之间引入队列通过采用显式控制边界来解耦其执行。此模型将线程的执行约束到给定阶段，因为线程可能只通过将事件排入队列来跨控制边界传递数据。一个基本问题是两个代码模块是应该通过队列进行通信，还是直接通过子程序调用进行通信。在两个模块之间引入队列可提供隔离，模块化和独立负载管理，但可能会增加延迟。例如，第三方代码模块可以在其自己的阶段中隔离，允许其他阶段通过其事件队列与之通信，而不是直接调用它。
      SEDA设计有助于服务的调试和性能分析，这对于复杂的多线程服务器来说一直是一个挑战。将应用程序代码分解为阶段和显式事件传递机制有助于检查; 例如，调试工具可以跟踪通过系统的事件流，并可视化阶段之间的交互。由于各阶段通过事件调度协议而不是传统API进行交互，因此可以直接在组件之间插入代理阶段以进行调试和性能分析。使用这种机制，我们的SEDA原型能够生成描绘应用程序阶段及其关系的图表。原型还可以生成事件队列长度，内存使用和其他系统属性的时间视图，这些属性对于理解性能很有价值。

3.4动态资源控制器

      实现易于服务工程的关键目标是保护程序员免受性能调优的复杂性。为了使每个阶段保持在其运行状态内，SEDA利用一组资源控制器，根据观察到的性能和需求自动调整阶段的资源使用。抽象地，控制器观察阶段的运行时特性并调整分配和调度参数以满足性能目标。控制器既可以完全掌握关于特定阶段的本地知识，也可以基于全局状态协同工作。
      我们在SEDA中实现了几个资源控制器，其中两个如图7所示。第一个是线程池控制器，它调整每个阶段内执行的线程数。目标是避免分配太多线程，但仍有足够的线程来满足阶段的并发需求。控制器定期对输入队列进行采样，并在队列长度超过某个阈值时添加一个线程，最多为每个阶段的最大线程数。当线程空闲一段指定的时间后，线程将从一个阶段中删除。图8显示了在5.1节中描述的Web服务器中运行的线程池控制器的影响; 控制器操作将在4.2节中详细讨论。

图7：SEDA资源控制器：每个阶段都有一个关联的控制器，可以调整其资源分配和行为，以使应用程序保持在其运行状态。线程池控制器调整在阶段内执行的线程数，批处理控制器调整事件处理程序的每次迭代处理的事件数。
      第二个是批处理控制器，它调整每个阶段内事件处理程序调用处理的事件数（批处理因子）。已经观察到[31]一次处理许多事件会增加吞吐量，因为可以执行缓存局部性和任务聚合。但是，较大的批处理因子也会增加响应时间。控制器试图通过搜索维持高吞吐量的最小批处理因子来权衡这些影响。它通过观察来自一个阶段的事件的输出速率（通过维持许多样本的移动平均值）来操作，并降低批处理因子直到吞吐量开始降低。如果吞吐量略有下降，则批处理因子会少量增加。控制器通过将批处理因子重置为其最大值来响应负载的突然下降。图9显示了工作中的批处理控制器。

图8：SEDA线程池控制器：此图显示了在运行Haboob Web服务器期间线程池控制器的操作，如第5.1节中所述。控制器根据相应事件队列的长度调整每个阶段的线程池的大小。在此运行中，队列长度每2秒采样一次，如果队列超过100个条目，则会将一个线程添加到池中（每个阶段的最大限制为20个线程）。当线程空闲超过5秒时，它们将从池中删除。异步文件阶段使用10个队列条目的控制器阈值来夸大控制器的行为。

图9：SEDA批处理控制器：该图显示了批处理控制器对简单基准测试的操作，该基准测试包括以振荡速率生成事件的单个阶段。这导致测量的输出速率变化，如图的顶部所示。当输出速率增加时，控制器会降低批处理因子。当输出速率降低时，控制器会增加批处理因子。在输出速率突然下降之后，批处理因子被重置为其最大值。
      这些机制代表了SEDA中动态控制的两个简单例子。可以将更复杂的控制器引入系统中; 例如，控制器可能会根据阶段优先级的全局概念调整线程池大小，或者将整个系统中的线程数保持在某个阈值以下。另一种选择是根据阶段的进展调整线程调度参数，如Steere等人提出的。[51]。 SEDA异步套接字库（将在下一节中介绍）包含一个可选控制器，用于限制从网络读取数据包的速率在5.1节中，我们描述了一个特定于应用程序的控制器，它可以自适应地减少负载以满足响应时间目标。SEDA的结构有助于检查和控制底层应用，并且该模型可以实现一系列控制策略。
      SEDA中动态控制的一个重要方面是它允许应用程序适应不断变化的条件，尽管底层操作系统使用了特定的算法。从某种意义上说，SEDA的控制器对操作系统的资源管理策略很天真。例如，SEDA批处理控制器不知道OS线程调度策略; 相反，它会影响基于应用程序性能的外部观察的线程调度。虽然在某些情况下可能需要对底层操作系统施加更多控制 – 例如，为特定阶段或线程提供服务质量保证 – 我们认为商用操作系统提供的基本资源管理机制，取决于应用级别控制，足以满足互联网服务的需求。

3.5 Sandstorm：SEDA原型

      我们已经实施了一个名为Sandstorm的基于SEDA的互联网服务平台。Sandstorm完全用Java实现，并使用一组native库来实现非阻塞套接字I/O（如第4节所述）。使用最新的Java实现，加上正确地使用Java的语言功能，我们发现使用Java的软件工程的稳定性优势远远超过了性能权衡。例如，我们依靠Java的自动内存管理来在系统内对“过期”事件进行垃圾收集; 这大大简化了代码，因为组件不负责跟踪事件的生命周期。Java和静态编译语言之间的性能差距也在缩小; 事实上，我们基于Java的SEDA Web服务器优于在C中实现的两个流行的Web服务器，如第5.1节所述。
      在Sandstorm中，每个应用程序模块都使用单个方法调用handleEvents()实现一个简单的事件处理程序接口，该方法处理从阶段的传入事件队列中提取的一批事件。应用程序不创建或管理线程; 这是运行时系统和相关控制器的责任。Sandstorm提供了一个线程管理器接口，可以对其进行定制以实现各种线程分配和调度策略; 此处描述的版本管理每个阶段的线程池，并依赖于底层操作系统进行调度。 Sandstorm提供用于命名，创建和销毁阶段，执行队列操作，控制队列阈值以及分析和调试的API。下一节中描述的套接字和文件I/O机制被提供为标准接口。
      Sandstorm运行时由19934行代码和7871非注释源语句（NCSS）组成。其中，3023 NCSS专用于核心运行时，2566专用于I/O设施。

4异步I/O原语

要满足SEDA支持高并发性的目标，需要高效，强大的I/O接口。本节描述如何使用SEDA概念使用现有OS原语实现这些接口。我们描述了一个异步网络套接字层，它利用操作系统提供的非阻塞I/O，以及使用阻塞OS调用和线程池来暴露非阻塞行为的异步文件I/O层。这两个层都实现为一组SEDA阶段，应用程序可以使用它们来提供快速的异步I/O.

4.1异步套接字I / O.

      Sandstorm异步套接字（asyncSocket）层为服务提供了易于使用的非阻塞套接字接口。应用程序创建类asyncClientSocket和asyncServerSocket的实例以启动传出和传入套接字连接。建立连接时，会将asyncConnection对象推送到用户提供的事件队列（通常是与请求阶段关联的队列）。传入的数据包被排入用户的事件队列，asyncConnection实现了一个可以放置传出数据包的队列接口。每个输出包还可以具有相关联的事件队列，当包被传输时，一个完成事件被推到这个队列上。错误和其他通知事件以类似的方式传递给用户。
      在内部，asyncSocket层使用三个阶段实现，这三个阶段在所有套接字之间共享，如图10所示.readStage读取网络数据包并响应用户请求以在新套接字上启动数据包读取。writeStage将数据包写入网络并建立新的传出连接。 listenStage接受新的TCP连接并响应用户监听新端口的请求。asyncConnection，asyncClientSocket或async-ServerSocket上的每个操作都将转换为请求并放置到相应阶段的请求队列中。

图10：基于SEDA的异步套接字层：Sandstorm套接字接口包括三个阶段：读取，写入和监听。读取阶段响应网络I/O就绪事件并从套接字读取数据，将新数据包推送到应用程序阶段。写入阶段接受传出数据包并调度它们以写入适当的套接字。它还建立新的传出套接字连接。listen阶段接受新的TCP连接并将连接事件推送到应用程序。
      每个asyncSocket阶段都为两个独立的事件队列提供服务：来自用户的请求队列，以及来自操作系统的I/O 就绪/完成事件队列。每个阶段中的线程交替地为每个队列服务，使用简单的超时机制在两者之间切换。I/O事件队列实现为库，该库导致出队操作调用适当的OS调用以检索I/O事件。我们当前的实现支持标准的UNIX poll（2）系统调用以及用于事件传递的/dev/poll [46]接口。 native库用于在Java [60]中提供非阻塞套接字调用。为了提高套接字的公平性，每个阶段随机化处理操作系统提供的I/O事件的顺序。这是必要的，因为OS通常以固定顺序（例如，按文件描述符的递增顺序）返回套接字事件。
      只要I/O就绪事件指示套接字具有可用数据，readStage就会通过执行套接字读取来进行操作。它最多将16 KB读入预先分配的缓冲区，并将生成的数据包排入用户提供的事件队列中。在I/O错误的情况下（例如，因为对等方已关闭连接），该阶段关闭套接字并将适当的通知事件推送给用户。每个套接字读取都需要分配新的数据包缓冲区;虽然这可能会导致大量的垃圾收集开销，但我们并未发现这是一个性能问题。请注意，由于此系统是用Java实现的，因此不需要显式释放过期的数据包。readStage还提供了一个可选的速率控制器，可以限制从网络读取数据包的速率;该控制器可用于在过载条件下执行减载。通过计算输入包速率的移动平均值并将人工延迟引入事件处理循环以实现特定速率目标来实现控制器。
      writeStage接收来自用户的数据包写入请求，并将它们排入与特定套接字关联的内部队列。当操作系统指示套接字已准备好写入时，它会尝试在该套接字的传出队列上写入下一个数据包。如第5.2节所述，可以对套接字队列进行阈值处理，以防止“慢”套接字在服务器中占用过多资源。
      为了评估asyncSocket的性能，我们实现了一个简单的服务器应用程序，它接受来自多个客户端的8KB突发数据包，每1000个突发数据包响应一个32字节的ACK。这种有点人为的应用程序旨在强调网络层，并随着客户端数量的增加来衡量其可扩展性。图11显示了服务器的总吞吐量，期间客户端数量从1增加到8192.服务器和客户端计算机都是使用运行Linux 2.2.14和IBM JDK 1.3的千兆以太网互连的4路500 MHz Pentium III系统。

图11：异步套接字层性能：此图显示了基于SEDA异步套接字层作为并发连接数量的函数的性能。每个客户端打开与服务器的连接并发出8KB突发数据包; 服务器对每个1000个数据包的突发，响应一个32字节的单独ACK。所有机器都通过交换式千兆以太网连接，并运行Linux 2.2.14。基于SEDA的服务器使用操作系统提供的非阻塞I/O原语。将性能与使用阻塞套接字和多个线程来模拟异步I/O的兼容性层进行比较。基于线程的层无法接受超过400个并发连接，因为所需的线程数将超过Linux中的每用户线程限制。
      套接字层的两种实现方式。基于SEDA的层使用OS提供的非阻塞I/O和/dev/poll事件传递机制[46]。将其与使用阻塞套接字的兼容性层和用于模拟异步I/O的线程池进行比较。该层为每个连接创建一个线程来处理套接字读取事件和一个固定大小的120个线程池来处理套接字写入。此兼容层最初是为了在Java下提供异步I / O而开发的，它不直接提供此功能。
      非阻塞实现明显优于线程版本，随着连接数量的增加，线程版本迅速降级。实际上，当接收超过400个连接时，线程实现会崩溃，因为所需的线程数超过了Linux中的每用户线程限制。非阻塞层的轻微吞吐量降低部分是由于Linux网络堆栈缺乏可扩展性。即使使用高度优化的/dev/poll机制[46]进行套接字I/O事件通知，随着套接字数量的增加，来自操作系统的轮询准备事件所涉及的开销也会显着增加[29]。

4.2异步文件I/O.

Sandstorm文件I/O（asyncFile）层展示与asyncSocket非常不同的设计点。由于底层操作系统不提供非阻塞文件I/O原语，因此我们不得不利用阻塞I/O和有界线程池来实现该层.3用户通过asyncFile对象执行文件I/O，该对象支持熟悉的接口读，写，寻找，统计和关闭。这些操作中的每一个都转换为asyncFile阶段的事件队列中的请求。asyncFile线程将每个请求出列并对文件执行相应的（阻塞）I/O操作。为确保对同一文件上的多个I/O请求进行串行执行，一次只有一个线程可以处理特定文件的事件。当I/O请求完成时，相应的完成事件将排入用户的事件队列。
asyncFile阶段在其线程池中使用单个线程进行初始化。 SEDA线程池控制器负责根据观察到的并发需求动态调整线程池的大小。图8显示了在运行第5.1节中描述的基于SEDA的Web服务器期间工作的线程池控制器。运行分为三个阶段，每个阶段对应越来越多的客户;请注意，客户端负载是非常突发的。随着文件访问的突发到来，控制器将线程添加到每个阶段的线程池，直到最多20个线程饱和。在这之间，不需要I / O，并且线程池缩小。虽然PageCache和CacheMiss阶段需要更多线程且客户端负载增加，但服务文件I / O所需的线程数实际上会减少。这是因为底层文件系统缓冲区缓存正在预热，并且能够更快地为磁盘请求提供服务。线程池控制器推断出需要更少的线程来管理磁盘并发，并避免创建不需要的线程。

5应用和评估

在本节中，我们将介绍两个应用程序的性能和负载调节评估：Haboob，一个高性能的HTTP服务器; 和Gnutella对等文件共享网络的数据包路由器。 Haboob代表客户端发出请求并等待响应的“闭环”服务器，而Gnutella数据包路由器是一个“开环”服务器的例子，其中服务器性能不会成为提供负载的限制因素。

5.1 Haboob：高性能HTTP服务器

Web服务器构成了可扩展的Internet服务的原型组件。许多先前的工作已经研究了构建高性能HTTP服务器的工程方面，但很少有关于负载调节，稳健性和易于构造的说法。研究HTTP服务器的一个好处是，存在各种行业标准的基准来衡量它们的性能。我们选择了SPECweb99基准套件[50]中的负载模型作为我们测量的基础，并进行了两项重要修改。首先，我们仅测量静态网页访问的性能（构成SPECweb99负载混合的70％）。其次，我们将网页文件集固定为3.31 GB的磁盘文件，对应于SPECweb99目标负载1000个连接。文件大小从102到921600字节，可以使用SPECweb99规定的基于Zipf的请求分发进行访问。更多细节可以在[50]中找到。

5.1.1 Haboob架构

      Haboob的整体结构如图5所示。服务器包含10个阶段，其中4个阶段专门用于异步套接字和磁盘I/O，如上一节所述。HttpParse阶段负责接受新的客户端连接和传入数据包的HTTP协议处理。 HttpRecv阶段接受HTTP连接并请求事件并将它们传递到PageCache阶段（如果它们代表磁盘文件）或直接生成响应（对于为收集服务器统计信息而生成的动态页面）。 PageCache实现了使用哈希表实现的内存中网页缓存。
      Haboob的整体结构如图5所示。服务器包含10个阶段，其中4个阶段专门用于异步套接字和磁盘I/O，如上一节所述。HttpParse阶段负责接受新的客户端连接和传入数据包的HTTP协议处理。HttpRecv阶段接受HTTP连接并请求事件并将它们传递到PageCache阶段（如果它们代表磁盘文件）或直接生成响应（对于为收集服务器统计信息而生成的动态页面）。PageCache实现了一个使用由URL索引的哈希表实现的内存网页缓存，其中每个条目包含一个由HTTP头和Web页面有效负载组成的响应数据包。CacheMiss阶段负责处理页面缓存未命中，使用异步文件I/O层从磁盘读取所请求页面的内容。最后，HttpSend向客户端发送响应并处理连接管理和统计信息收集的某些方面。另一个阶段（图中未显示）从HTML模板生成动态Web页面，嵌入的代码用Python脚本语言编写[36]。此功能提供了通用的服务器端脚本，类似于Java Server Pages [26]。
      页面缓存尝试将缓存大小保持在给定阈值以下（对于下面提供的测量，设置为204800 KB）。它积极地回收容量未命中的缓冲区，而不是允许旧的缓冲区被Java运行时垃圾收集; 我们发现这种方法可以产生明显的性能优势。缓存阶段使用特定于应用程序的事件调度来提高性能。特别是，它实现了最短连接优先（SCF）[15]调度，它重新排序请求流以在较长的缓存条目之前发送短缓存条目，并优先考虑缓存命中而不是未命中。由于SCF仅应用于批处理控制器提供的每组事件，因此跨请求的饥饿不是问题。
      将Haboob构建为一组阶段极大地提高了设计的模块性，因为每个阶段都体现了一个强大的，可重复使用的软件组件，可以单独调节负载。我们能够测试页面缓存的不同实现，而无需对其余代码进行任何修改; 运行时只是实例化一个不同的阶段来代替原始页面缓存。同样，另一位没有Haboob结构知识的开发人员能够花很少的工作将Haboob使用异步文件层替换为备用文件系统接口。不包括Sandstorm平台，Web服务器代码仅包含3283个非注释源语句，其中676个NCSS专用于HTTP协议处理库。

5.1.2基准配置

      为了进行比较，我们提供了来自流行的Apache [6] Web服务器（版本1.3.14，与Linux Red Hat 6.2系统一起提供）以及Rice大学的Flash [44] Web服务器的性能测量。Apache使用150个进程的固定大小的进程池; 每个进程一次管理一个连接，从磁盘读取文件数据并使用阻塞I/O操作以8 KB块的形式将其发送到客户端。Flash使用高效的事件驱动设计，单个进程处理大多数请求处理任务。一组帮助程序进程执行（阻止）磁盘I/O，路径名解析和其他操作。Flash静态页面缓存的最大大小设置为204800 KB，与Haboob中的大小相同。Apache和Flash都是用C实现的，而Haboob是用Java实现的。
      以下所有测量均在服务器上运行，该服务器运行在具有2 GB RAM和Linux 2.2.14的4路SMP 500 MHz Pentium III系统上。IBM JDK v1.3.0用作Java平台。32台具有类似配置的机器用于生成负载，每台客户机使用多个线程来模拟许多实际客户机。所有机器都通过交换式千兆以太网互连。虽然这种配置不能模拟广域网效果，但我们感兴趣的是服务器在高负载下的性能和稳定性。
      客户端负载生成器循环，不断请求网页（使用SPECweb99套件指定的分发），读取结果，并在请求下一页之前休眠20毫秒的固定时间。为了更密切地模拟广域中客户端的连接行为，每个客户端在5个HTTP请求之后关闭TCP连接，并在继续之前重新建立连接。该值是根据[39]的HTTP流量观察结果选择的。所有基准测试均使用热文件系统和网页缓存运行。请注意，3.31 GB的文件集大小远远大于物理内存，Haboob和Flash的静态页面缓存仅设置为200 MB; 因此，这些测量包括大量的磁盘I/O.

5.1.3性能分析

      图12显示了Haboob与Apache和Flash在聚合吞吐量和响应时间方面的性能。还显示了每个客户完成的请求数量的the Jain fairness index(公平指数)[27]。该指标定义为
【译】SEDA: An Architecture for Well-Conditioned, Scalable Internet Services-编程知识网
其中xi是每N个客户端的请求数。公平指数为1表示服务器对所有客户端同等公平; 较小的值表示较不公平。直观地，如果N个客户端中的k个接收到相等的服务份额，而其他N-k个客户端不接收服务,则Jain公平性指数等于k/N.(维基)
      如图12（a）所示，Haboob的吞吐量随着客户端数量的增加而趋于稳定，为1024个客户端维持超过200 Mbps。Flash和Apache也表现出稳定的吞吐量，尽管略低于Haboob。这个结果可能看起来令人惊讶，因为我们所期望的基于进程的Apache服务器的性能随着客户端数量的增加而降低。但是，回想一下Apache服务器在任何时间只接受不超过150个客户端的连接，因而基于进程的高并发量并不难维持。当数量客户超过这个数量，所有其他客户在被系统接受之前，必须等待越来越长的时间。Flash有类似的问题：它限制了同时连接的数量506，由于可以使用 select() 系统调用的文件描述符的数量限制。当服务器饱和时，客户端必须在建立连接之前等待很长一段时间。
      图12（b）显示了这种效果，它显示了具有1024个客户端的每个服务器响应时间的累积分布。这里，响应时间定义为服务器响应给定请求的总时间，包括建立TCP连接的时间（如果尚未建立）。尽管所有三台服务器的平均响应时间大致相同，但分布却非常不同。Apache和Flash显示出比Haboob更快的低响应时间分布，但是有很长的尾巴，有相当大比例的请求超过几十秒。请注意，图中对数刻度的使用不会强调尾部的长度。 Apache的最大响应时间超过93秒，Flash的响应时间超过37秒。响应时间的长尾是由建立新连接的TCP重传定时器的指数后退引起的，在Linux下，这个时间可以增长到120秒。
      使用Apache，如果客户端是“幸运的”，则可以快速接受其连接，并且所有请求都由单个服务器进程处理。此外，每个进程仅与149个其他进程竞争，这在大多数系统上都是可管理的流程。这解释了大量的低响应时间。但是，如果客户端“不幸运”，则必须等待服务器进程可用; TCP重新传输退避意味着此等待时间可能变得非常大。这种对客户的不平等待遇反映在Apache的公平度量值较低。
      使用Flash，所有客户端都可以非常快速地接受到系统中，并且在服务器内受到排队延迟的影响。Flash中的低响应时间主要归功于非常有效的实现。包括快速HTTP协议处理库; 我们在Haboob中进行了一些优化。但是，Flash一次只接受506个连接的事实意味着在高负载下TCP退避成为一个问题，导致响应时间分布的长尾。
      相比之下，Haboob在超载时对客户表现出极大的公平性。平均响应时间为547毫秒，最大值为3.8秒。这符合我们优雅降级的目标 – 当服务器过载时，不应该以任意等待时间不公平地惩罚等待请求。Haboob迅速接受新的客户端连接，并允许请求在应用程序中排队，在它们在阶段之间传递时，它们得到公平的服务。因此，服务可以看到负载，允许应用各种负载调节策略。例如，为了提供差异化服务，有必要有效地接受连接以进行检查。这里的权衡是在低平均响应时间与响应时间的低方差之间。在Haboob，我们选择了后者。

图12：Haboob Web服务器性能：该图显示了Haboob Web服务器与Apache和Flash相比的性能。（a）显示每个服务器使用3.31 GBytes的文件集的吞吐量，因为客户端数量从1增加到1024.还显示了每个服务器提供的Jain公平性指数。公平指数为1表示服务器对所有客户端同等公平; 较小的值表示较不公平。（b）显示1024个客户端的响应时间的累积分布函数。虽然Apache和Flash表现出高频率的低响应时间，但尾部很重，最大响应时间相当于几分钟。

5.1.4自适应减载

      在本节中，我们评估Haboob在过载下的行为，并演示使用特定于应用程序的控制器，该控制器试图通过减载将响应时间保持在给定阈值以下。在此基准测试中，每个客户端都会重复请求一个动态Web页面，该页面需要生成大量的I/O和计算。通过使每个服务器受到大量这些“瓶颈”请求，我们通常可以产生比服务静态网页时更大的负载。
      对于每个请求，服务器执行循环的多次迭代，该循环打开文件，从中读取数据，并生成数据的总和。在此处理之后，服务器向客户端返回8 KB响应。在Apache中，这是作为在Apache服务器进程的上下文中运行的Perl模块实现的。在Flash中，使用了提供的“快速CGI”接口，它创建了许多（持久的）服务器进程来处理动态请求。当发出CGI请求时，使用空闲服务器进程来处理请求，或者如果没有空闲服务器进程则创建新进程。在Haboob中，瓶颈被实现为一个单独的阶段，允许线程池控制器确定专用于阶段处理的线程数，并在阶段的传入事件队列中使用阈值来拒绝超额负载。由于这三种实现之间的差异，通过调整动态页面生成所执行的工作量，使服务器端每个请求延迟40毫秒。
      图13显示了具有1024个客户端的三台服务器的响应时间的累积分布。 Apache和Haboob每个都表现出很大的响应时间，但原因各不相同。 Apache的响应时间尾部是由TCP重新传输退避引起的，如上所述，并且只有150个并发进程，服务器内的排队延迟最小。在Haboob中，在任何给定时间内，最多1024个并发请求在服务器内排队，导致瓶颈处的大排队延迟。 Flash的明显低响应时间是由于其CGI处理代码中的错误导致它在无法派生（fork）新的CGI进程时过早地关闭连接。对于1024个客户端，系统中一次最多可以有1024个CGI进程;与其他Flash进程一起，这超出了Linux中的每用户进程限制。当fork失败时，Flash会立即关闭客户端连接，而不会向客户端返回任何响应（甚至是错误消息）。在此次运行中，超过74％的请求导致过早关闭连接。
      这种机制提出了一种有效的方法来限制服务器中请求的响应时间：即，当服务器检测到它过载时自适应地减少负载。为了证明这一想法，我们在瓶颈阶段构建了一个特定于应用程序的控制器，它可以观察通过该阶段的请求的平均响应时间。当响应时间超过5秒的阈值时，控制器会以指数方式降低阶段的队列阈值。当响应时间低于阈值时，控制器将队列阈值增加固定量。当HttpRecv阶段无法将新请求存入瓶颈阶段的事件队列时（因为已超过队列阈值），将向客户端返回错误消息。请注意，这只是减载政策的一个例子; 替代方案是将HTTP重定向发送到服务器场中的另一个节点，或者提供降级服务。
      图13显示了启用响应时间控制器的累积响应时间分布。在这种情况下，控制器有效地减少了通过服务器的请求的响应时间，90％的请求表现出低于11.8秒的响应时间，最大响应时间仅为22.1秒。在此次运行中，由于队列阈值处理，98％的请求被服务器拒绝。请注意，此控制器无法保证响应时间低于目标值，因为队列阈值较高时发生的突发可能会导致客户端响应时间出现峰值。

图13：响应时间控制器：此图显示了特定于应用程序的控制器的影响，该控制器释放负载以使响应时间保持在目标值以下。这里，1024个客户端重复请求动态Web页面，该Web页面需要生成I/O和计算。Apache和Haboob（with no control）处理所有这些请求，导致大的响应时间。由于CGI处理代码中的错误，Flash拒绝了大量请求; 客户端永远不会被告知服务器正忙。启用响应时间控制器后，当平均响应时间超过5秒的阈值时，Haboob会拒绝带有错误消息的请求。

5.2 Gnutella数据包路由器

我们选择实现Gnutella数据包路由器来演示SEDA在非传统互联网服务中的使用。Gnutella路由器代表了一种与HTTP服务器完全不同的服务方式：在对等文件共享网络中的参与者之间路由数据包。像Gnutella这样的服务的重要性日益增加，因为新的分布式应用程序的开发是为了利用广域内主机的良好连接性。对等模型已被多个分布式存储系统采用，如Freenet [14]，OceanStore [30]和Intermemory [13]。
Gnutella [19]允许用户搜索和下载来自其他Gnutella用户的文件。该协议完全去中心化的;运行Gnutella客户端的节点形成一个通过TCP/IP分层的adhoc多跳路由网络，节点通过将收到的消息转发给它们的相邻节点来进行通信。Gnutella节点倾向于同时连接到几个（通常是四个或更多）其他节点，并且网络上节点的初始发现是通过众所周知的主机完成的。Gnutella中有五种消息类型：ping用于发现网络上的其他节点; pong是对ping的回应; query用于搜索其他Gnutella主机服务的文件; queryhits是对查询的响应;和push用于允许客户端通过防火墙下载文件。数据包路由器负责向所有其他相邻接点广播接收到的ping和查询消息，并沿着相应的ping或查询消息的路径路由pong，queryhits和push消息。有关消息格式和路由协议的详细信息，请参见[19]。

5.2.1架构

除了异步套接字I/O层之外，基于SEDA的Gnutella数据包路由器使用3个阶段实现。该代码由1294个非注释源语句组成，其中880个NCSS专门用于Gnutella协议处理。GnutellaServer阶段接受TCP连接并处理数据包，将数据包事件传递到GnutellaRouter阶段，该阶段执行路由表的实际数据包路由和维护。 GnutellaCatcher是用于连接Gnutella网络的助手阶段，它通过联系周所周知的站点（well-known site）来接收要连接的主机列表。除了由其他广域客户端建立的任何连接之外，它还尝试保持至少4个同时连接到网络的连接。加入“实时”Gnutella网络和路由数据包使我们能够在真实环境中测试SEDA，以及测量通过路由器的流量。在一个37小时的运行期间，路由器处理了2480万个数据包（平均每秒179个数据包），并从网络上的其他主机接收了72,396个连接，在任何给定时间平均有12个同时连接。路由器每秒能够支持超过20,000个数据包。

5.2.2 防止慢套接字

我们原始的数据包路由器原型展示了一个有趣的内存泄漏：在通过网络正确路由数据包几个小时之后，服务器会在耗尽内存后崩溃。观察各个阶段队列长度使我们能够轻松地检测问题的根源：大量的传出数据包正在排队等待某些广域连接，导致队列长度（因此内存使用）变得无限制。我们测量了Gnutella消息的平均数据包大小约为32个字节;每秒仅115个数据包的数据包速率可以使28.8千比特的调制解调器链路饱和，这仍然是许多Gnutella软件用户常用的。在这种情况下，解决方案是对每个套接字的传出数据包队列施加一个阈值，并关闭超过其阈值的连接。此解决方案是可以接受的，因为Gnutella客户端会自动发现并连接到网络上的多个主机;跨网络节点的冗余意味着客户端不需要依赖于特定主机来保持连接到网络。

5.2.3负载调节行为

      为了评估SEDA资源控制器在负载调节中的使用，我们在Gnutella路由器中引入了一个故意的瓶颈，其中每个查询消息都会导致20 ms的服务延迟。这是通过让应用程序事件处理程序在收到查询数据包时休眠20毫秒来实现的。我们实现了一个负载生成客户端，它连接到服务器并根据与实际Gnutella流量相近的分布生成数据包流。在我们的Gnutella流量模型中，查询消息构成了生成数据包的15％。使用单个线程执行数据包路由，很明显，随着流入服务器的数据包数量的增加，此延迟将导致其他消息的大量积压。
      图14（a）显示了ping和查询数据包通过服务器的平均延迟，提供的负载从100到1000包/秒增加。客户端和服务器计算机使用与HTTP服务器基准测试中相同的配置。当提供的负载超过服务器的容量时，数据包延迟会急剧增加。在1000个数据包/秒的情况下，服务器崩溃（由于内存不足以缓冲传入的数据包），然后才能进行延迟测量。
      此时，可以采用若干负载调节策略。一个简单的策略是对每个阶段的传入事件队列进行阈值处理，并在超过阈值时丢弃数据包。或者，可以使用类似于随机早期检测（RED）拥塞避免方案[17]中使用的方法，其中基于输入队列的长度概率地丢弃数据包。虽然这些策略会导致许多数据包在过载期间被丢弃，但由于Gnutella网络流量的有损性质，这可能是一种可接受的解决方案。另一种策略是允许所有数据包进入系统，但让应用程序事件处理程序过滤掉查询数据包（这是过载的来源）。另一个策略是利用asyncSocket输入速率控制器将进入的数据包速率限制在系统中。
      另一种方法是利用SEDA的资源控制器自动克服瓶颈。在这种方法中，线程池控制器在检测到需要额外的并发时将线程添加到GnutellaRouter阶段; 这种机制类似于基于集群的TACC [18]系统中的动态工作者分配。图14（b）显示了启用SEDA线程池控制器的Gnutella路由器的平均延迟。如图14（c）所示，2个线程被添加到GnutellaRouter线程池中，允许服务器处理增加的数据包负载，尽管存在瓶颈。这个数字与从Little的结果中获得的理论值相匹配：如果我们将阶段建模为具有n个线程的排队系统，平均数据包到达率为λ，查询数据包频率为p，查询服务延迟为L秒，那么维持λ完成率所需的线程数是n =λpL=（1000）（0.15）（20 ms）= 3个线程。

图14：Gnutella数据包路由器延迟：这些图显示了随着传入包率的增加，ping和query包通过Gnutella包路由器的平均延迟时间。Query数据包（15％数据包混合）会导致服务器端延迟20 ms。（a）显示了单个线程处理数据包的延迟。请注意，随着提供的负载超过服务器容量，延迟会急剧增加;在1000个数据包/秒时，服务器在进行延迟测量之前内存不足。（b）显示启用线程池控制器的延迟。请注意，对于100和200数据包/秒，没有线程被添加到应用程序阶段，因为事件队列从未达到其阈值。这解释了与400和1000包/秒相比较高的数据包延迟，其中2个线程被添加到该阶段。（c）显示GnutellaRouter队列长度随时间的变化，负载为1000包/秒，线程池控制器处于活动状态。控制器在指示的两个点中的每个点处向阶段添加了一个线程。

6讨论和结论

      因特网服务引发了一系列新的系统设计要求，因为必须以强大，易于编程的方式提供大规模并发，以便优雅地处理负载的巨大变化。 SEDA是为该制度建立设计原则的一步。在本文中，我们介绍了SEDA设计和执行模型，介绍了由显式事件队列连接的阶段的概念。SEDA利用一组动态控制器来管理每个阶段的资源使用和调度; 我们已经描述了几个控制器，包括两个跨阶段的控制线程分配和一个阶段内部使用的批处理程度。我们还分析了两个高效的异步I/O组件，以及使用SEDA设计构建的两个应用程序，表明SEDA在负载下表现出良好的性能和稳健的行为。
      SEDA模型在互联网服务设计领域开辟了新的问题。显式事件队列和动态资源控制器的使用提高了专门针对服务进行调整的新颖调度和资源管理算法的可能性。作为未来的工作，我们计划实施一个广义的流量控制方案，用于各阶段之间的通信; 在此方案中，每个事件都需要一定数量的信用才能排入目标阶段的事件队列。通过为每个事件分配可变数量的信用，可以实现有趣的负载调节策略。
      我们认为，测量和控制是繁忙的互联网服务中资源管理和过载保护的关键。这与基于资源遏制的长期存在的方法形成对比，后者为系统中的每个任务（例如进程，线程或服务器请求）分配固定资源，并努力控制每个任务消耗的资源。尽管这些技术在互联网服务中提供差异化服务方面已经取得了一些成功[57]，但是遏制通常要求对每项任务进行先验的资源分配，从而限制了适用的负载调节策略的范围。相反，我们认为动态资源控制，加上面对过载的特定应用适应，是接近负载调节的正确方法。
      当控制被视为资源管理的基础时，会出现两个新的挑战。第一个是检测过载情况：许多变量会影响服务的交付性能，而确定服务实际上是过载的以及原因是一个有趣的问题。第二是确定适当的控制策略来抵抗过载。我们计划对当前实施中的资源控制器进行多项改进，以及针对备用指标进行优化的新控制器。例如，为了减少资源消耗，可能需要优先考虑释放资源而不是消耗资源的阶段。在SEDA下，控制系统的工作主体[43,45]可以用于服务资源管理，我们只是触及了这种技术潜力的表面。
      关于事件驱动的并发模型的一个共同关注点是易于编程。现代语言和编程工具支持线程应用程序的开发和调试，许多开发人员认为事件驱动编程本质上更加困难。事实上，大多数事件驱动的服务器应用程序通常非常复杂，并且在设计上有点特别，这使得这种观点持续存在。根据我们的经验，SEDA模型中的编程比多线程应用程序设计和传统的事件驱动模型更容易。当线程被隔离到单个阶段时，线程同步和竞争条件等问题更易于管理。阶段之间面向消息的通信建立了明确的排序;在传统的事件驱动设计中，通过系统跟踪事件流程要困难得多。我们认为SEDA是线程和事件驱动设计之间的理想中间点，对编程模型的进一步探索是未来工作的重要方向。
      虽然SEDA有助于在商品操作系统上构建条件良好的服务，但SEDA模型为操作系统设计提供了新的方向。我们设想一个直接支持SEDA执行模型的操作系统，并为应用程序提供对调度和资源使用的更大控制。这种方法类似于各种研究系统[5,11,28,34]中提供的方法，可以实现特定于应用程序的资源管理。更为根本的是，基于SEDA的操作系统无需设计为允许多个应用程序透明地共享资源。Internet服务是高度专业化的，并不是为了与其他应用程序共享机器而设计的：例如，Web服务器通常不希望与数据库引擎在同一台机器上运行（更不用说科学计算或文字处理器）。尽管操作系统可以实施保护（以防止一个阶段破坏内核状态或另一个阶段），但系统不需要以掩盖应用程序可用性的方式虚拟化资源。
致谢
该研究得到了国防高级研究计划局（DABT63-98-C-0038和N66001-99-2-8913），国家科学基金会（授权EIA-9802069），英特尔公司，北电网络和 Royal Philips Electronics。Matt Welsh得到了美国国家科学基金会研究生奖学金的支持。我们要感谢Steve Gribble，Joe Hellerstein和Marti Hearst对本文的宝贵意见。Eric Fraser，Matt Massie，Albert Goto和Philip Buonadonna为用于获得性能测量的Berkeley Mil-lennium集群提供了支持。Eric Wagner在Haboob Web服务器中提供了服务器端脚本功能。我们特别感谢我们的指导者Andrew Myers和匿名审稿人的有益评论。
References
[1] Akamai, Inc. http://www.akamai.com/.
[2] America Online Press Data Points. http://corp.aol.com/press/
press_datapoints.html.
[3] DigitalIsland,Inc.http://www.digitalisland.com/.
[4] Acme Labs. thttpd: Tiny/Turbo/Throttling HTTP Server. http://www. acme.com/software/thttpd/.
[5] T. Anderson, B. Bershad, E. Lazowska, and H. Levy. Scheduler activa- tions: Effective kernel support for the user-level management of paral- lelism. ACM Transactions on Computer Systems, 10(1):53–79, February 1992.
[6] Apache Software Foundation. The Apache web server. http://www. apache.org.
[7] G. Banga, P. Druschel, and J. Mogul. Resource containers: A new facility for resource management in server systems. In Proc. Third Symposium on Operating Systems Design and Implementation (OSDI ’99), February 1999.
[8] G.BangaandJ.C.Mogul.ScalablekernelperformanceforInternetservers under realistic loads. In Proc. 1998 Annual Usenix Technical Conference, New Orleans, LA, June 1998.
[9] G. Banga, J. C. Mogul, and P. Druschel. A scalable and explicit event delivery mechanism for UNIX. In Proc. USENIX 1999 Annual Technical Conference, Monterey, CA, June 1999.
[10] BEA Systems. BEA WebLogic. http://www.beasys.com/ products/weblogic/.
[11] B. Bershad, S. Savage, P. Pardyak, E. G. Sirer, D. Becker, M. Fiuczyn- ski, C. Chambers, and S. Eggers. Extensibility, safety and performance in the SPIN operating system. In Proc. 15th ACM Symposium on Operating System Principles (SOSP-15), 1995.
[12] A. Chankhunthod, P. B. Danzig, C. Neerdaels, M. F. Schwartz, and K. J. Worrell. A hierarchical Internet object cache. In Proc. 1996 Usenix Annual Technical Conference, pages 153–163, January 1996.
[13] Y. Chen, J. Edler, A. Goldberg, A. Gottlieb, S. Sobti, and P. Yianilos. A prototype implementation of archival Intermemory. In Proc. Fourth ACM Conference on Digital Libraries (DL ’99), Berkeley, CA, 1999.
[14] I. Clarke, O. Sandberg, B. Wiley, , and T. W. Hong. Freenet: A dis- tributed anonymous information storage and retrieval system in designing privacy enhancing technologies. In Proc. ICSI Workshop on Design Issues in Anonymity and Unobservability, Berkeley, CA, 2000.
[15] M. Crovella, R. Frangioso, and M. Harchol-Balter. Connection scheduling in Web servers. In Proc. 1999 USENIX Symposium on Internet Technolo- gies and Systems (USITS ’99), October 1999.
[16] M.L.Dertouzos.Thefutureofcomputing.ScientificAmerican,July1999.
[17] S. Floyd and V. Jacobson. Random early detection gateways for conges- tion avoidance. IEEE/ACM Transactions on Networking, 1(4):397–413, August 1993.
[18] A. Fox, S. D. Gribble, Y. Chawathe, E. A. Brewer, and P. Gauthier. Cluster- based scalable network services. In Proc. 16th ACM Symposium on Oper- ating Systems Principles, St.-Malo, France, October 1997.
[19] Gnutella.http://gnutella.wego.com.
[20] S. Gribble, E. Brewer, J. Hellerstein, and D. Culler. Scalable, distributed data structures for internet service construction. In Proc. Fourth Sympo- sium on Operating Systems Design and Implementation (OSDI 2000), Oc- tober 2000.
[21] S. Gribble, M. Welsh, R. von Behren, E. Brewer, D. Culler, N. Borisov, S. Czerwinski, R. Gummadi, J. Hill, A. Joseph, R. Katz, Z. Mao, S. Ross, and B. Zhao. The Ninja architecture for robust Internet-scale systems and services. Computer Networks, June 2000. Special Issue on Pervasive Com- puting.
[22] Hewlett-Packard Corporation. e-speak Open Services Platform. http: //www.e-speak.net/.
[23] J. Hu, S. Mungee, and D. Schmidt. Techniques for developing and mea- suring high-performance Web servers over ATM networks. In Proc. IN- FOCOM ’98, March/April 1998.
[24] J. C. Hu, I. Pyarali, and D. C. Schmidt. High performance Web servers on Windows NT: Design and performance. In Proc. USENIX Windows NT Workshop 1997, August 1997.
[25] IBM Corporation. IBM WebSphere Application Server. http:// www-4.ibm.com/software/webservers/.
[26] S. M. Inc. Java Server Pages API. http://java.sun.com/ products/jsp.
[27] R.Jain,D.Chiu,andW.Hawe.Aquantitativemeasureoffairnessanddis- crimination for resource allocation in shared computer systems. Technical Report TR-301, DEC Research, September 1984.
[28] M. F. Kaashoek, D. R. Engler, G. R. Ganger, H. M. Bricen ̃o, R. Hunt, D. Mazie`res, T. Pinckney, R. Grimm, J. Jannotti, and K. Mackenzie. Ap- plication performance and flexibility on Exokernel systems. In Proc. 16th ACM Symposium on Operating Systems Principles (SOSP ’97), October 1997.
[29] D. Kegel. The C10K problem. http://www.kegel.com/c10k. html.
[30] J. Kubiatowicz, D. Bindel, Y. Chen, S. Czerwinski, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, C. Wells, and B. Zhao. OceanStore: An architecture for global-scale persistent storage. In Proc. Ninth international Conference on Architectural Support for Pro- gramming Languages and Operating Systems (ASPLOS 2000), November 2000.
[31] J.LarusandM.Parkes.Usingcohortschedulingtoenhanceserverperfor- mance. Technical Report MSR-TR-2001-39, Microsoft Research, March 2001.
[32] H. Lauer and R. Needham. On the duality of operating system structures. In Proc. Second International Symposium on Operating Systems, IRIA, October 1978.
[33] J. Lemon. FreeBSD kernel event queue patch. http://www. flugsvamp.com/ ̃jlemon/fbsd/.
[34] I.Leslie,D.McAuley,R.Black,T.Roscoe,P.Barham,D.Evers,R.Fair- bairns, and E. Hyden. The design and implementation of an operating system to support distributed multimedia applications. IEEE Journal on Selected Areas in Communications, 14:1280–1297, September 1996.
[35] A. S. Lett and W. L. Konigsford. TSS/360: A time-shared operating sys- tem. In Proc. Fall Joint Computer Conference, Volume 33, Part 1, pages 15–28, 1968.
[36] M.Lutz.ProgrammingPython.O’ReillyandAssociates,March2001.
[37] Microsoft Corporation. DCOM Technical Overview. http: //msdn.microsoft.com/library/backgrnd/html/msdn_ dcomtec.htm.
[38] Microsoft Corporation. IIS 5.0 Overview. http://www. microsoft.com/windows2000/library/howitworks/ iis/iis5techove%rview.asp.
[39] J. C. Mogul. The case for persistent-connection HTTP. In Proc. ACM SIGCOMM’95, October 1995.
[40] R. Morris, E. Kohler, J. Jannotti, and M. F. Kaashoek. The Click modular router. In Proc. 17th ACM Symposium on Operating Systems Principles (SOSP ’99), pages 217–231, Kiawah Island, South Carolina, December 1999.
[41] D. Mosberger and L. Peterson. Making paths explicit in the Scout operat- ing system. In Proc. OSDI ’96, October 1996.
[42] Netscape Corporation. Netscape Enterprise Server. http://home. netscape.com/enterprise/v3.6/index.html.
[43] K.Ogata.ModernControlEngineering.PrenticeHall,1997.
[44] V. S. Pai, P. Druschel, and W. Zwaenepoel. Flash: An efficient and portable Web server. In Proc. 1999 Annual Usenix Technical Conference, June 1999.
[45] S.Parekh,N.Gandhi,J.L.Hellerstein,D.Tilbury,T.Jayram,andJ.Bigus. Using control theory to achieve service level objectives in performance management. In Proc. IFIP/IEEE International Symposium on Integrated Network Management, Seattle, WA, May 2001.
[46] N. Provos and C. Lever. Scalable network I/O in Linux. Technical Report CITI-TR-00-4, University of Michigan Center for Information Technology Integration, May 2000.
[47] X.Qie,A.Bavier,L.Peterson,andS.Karlin.Schedulingcomputationson a software-based router. In Proc. SIGMETRICS 2001, June 2001.
[48] M. Russinovich. Inside I/O completion ports. http://www. sysinternals.com/comport.htm.
[49] O. Spatscheck and L. Petersen. Defending against denial of service at- tacks in Scout. In Proc. 3rd Symposium on Operating Systems Design and Implementation, February 1999.
[50] Standard Performance Evaluation Corporation. The SPECweb99 bench- mark. http://www.spec.org/osg/web99/.
[51] D.C.Steere,A.Goel,J.Gruenberg,D.McNamee,C.Pu,andJ.Walpole. A feedback-driven proportion allocator for real-rate scheduling. In Proc. 3rd Usenix Symposium on Operating Systems Design and Implementation (OSDI’99), pages 145–158, 1999.
[52] Sun Microsystems. RPC: Remote Procedure Call Protocol Specification Version 2. Internet Network Working Group RFC1057, June 1988.
[53] Sun Microsystems Inc. Enterprise Java Beans Technology. http:// java.sun.com/products/ejb/.
[54] Sun Microsystems, Inc. Java Remote Method Invocation. http:// java.sun.com/products/jdk/rmi/.
[55] Sun Microsystems Inc. Jini Connection Technology. http://www. sun.com/jini/.
[56] M. Vandevoorde and E. Roberts. Work crews: An abstraction for control- ling parallelism. Technical Report Research Report 42, Digital Equipment Corporation Systems Research Center, February 1988.
[57] T. Voigt, R. Tewari, D. Freimuth, and A. Mehra. Kernel mechanisms for service differentiation in overloaded Web servers. In Proc. 2001 USENIX Annual Technical Conference, Boston, June 2001.
[58] L. A. Wald and S. Schwarz. The 1999 Southern California Seismic Net- work Bulletin. Seismological Research Letters, 71(4), July/August 2000.
[59] D. A. Wallach, D. R. Engler, and M. F. Kaashoek. ASHs: Application- specific handlers for high-performance messaging. In Proc. ACM SIG- COMM ’96 Conference: Applications, Technologies, Architectures, and Protocols for Computer Communication, pages 40–52, Stanford, Califor- nia, August 1996.
[60] M. Welsh. NBIO: Nonblocking I/O for Java. http://www.cs. berkeley.edu/ ̃mdw/proj/java-nbio.
[61] M. Welsh and D. Culler. Virtualization considered harmful: OS design directions for well-conditioned services. In Proc. 8th Workshop on Hot Topics in Operating Systems (HotOS VIII), Schloss Elmau, Germany, May 2001.
[62] Yahoo! Inc. Yahoo! reports Second Quarter 2001 financial results. http: //docs.yahoo.com/docs/pr/release794.html.
[63] Zeus Technology. Zeus Web Server. http://www.zeus.co.uk/ products/ws/.
原文：https://github.com/mdwelsh/mdwelsh.github.io/blob/master/papers/seda-sosp01.pdf