SEDA: An Architecture for Well-Conditioned, Scalable Internet Services
Abstract
? Staged Event-Driven Architecture（SEDA）是一种新的高并发Internet服务设计，旨在支持大量并发需求，并简化条件良好的服务的构造。在SEDA中，应用程序由显式队列连接的事件驱动阶段（event-driven stage）网络组成。
? SEDA利用一组动态资源控制器（dynamic resource controllers ），在负载波动较大的情况下，让各个stage内部保证稳定运行，防止在需求超过服务能力时过度使用资源。我们设计了几种用于自动调优和负载调节的控制机制：线程池大小调整、事件批处理和自适应减载。
1 Introduction
? 本文描述了一个基于SEDA的互联网服务平台的设计、架构和实现。该平台提供高效、可扩展的I/O接口以及多种资源控制机制，包括线程池大小和动态事件调度。
? SEDA的目标是：在负载发生巨大变化的情况下，能保持多数服务的健壮性，同时易于编程。
? 要提高服务的可伸缩性（scalability），复制（Replication）是一个传统的重头戏。对于一个服务实例来说，当负载成倍增长，那就必须对其重新配置，才能维持这个服务性能的稳定。但是，假如我们假设每个节点都会经历较大的负载峰值，由于峰值负载可能远远大于平均负载，因此复制不能处理最大的潜在需求。
? 传统操作系统为了提供最大的透明度，为每个进程提供一个虚拟机的抽象，该虚拟机具有自己的CPU、内存、磁盘和网络。这在某种程度上与互联网服务的需求不符，互联网服务需要大量的一致性和对资源使用的广泛控制。
? 因此尽管进程和线程是很好的**并发编程模型，但在高并发环境下，上下文切换和内存占用**会导致极大开销，从而限制并发性。对于对于特定服务来说，会有相应的方法保证它们的性能和健壮性，而SEDA的目标是实现一个通用的解决方案。
? SEDA结合了基于线程和基于事件的编程模型，以管理Internet服务的并发性、I/O、调度和资源管理需求。在SEDA中，应用程序被构造为a network of stages，每个阶段都有一个相关的传入事件队列。每个stage模块保证自身的健壮，当服务量可能超过自身处理能力的时候，可以通过设置阈值或事件过滤来单独调节加载。并且，应用程序可以根据事件队列的状态获取网络内部的状况，做出相应的调度和资源管理决策，例如重新排序、过滤或聚合请求。SEDA利用动态资源流量控制（dynamic resource throttling）控制应用程序组件的资源分配和调度，允许系统适应过载条件。
2 Background and Related Work
? SEDA两个重要的研究方向:使用基于线程的并发模型简化编程，使用基于事件的并发模型实现高并发。
? 本节通过概述导致SEDA设计的步骤中的关键贡献和问题来开发这种方法的沿袭。直观地说，如果一个服务表现得像一个简单的管道（pipeline），那么它就是well-conditioned，其中管道的深度是由通过网络的路径和服务本身的处理阶段决定的。
? 随着所提供的负载的增加，所交付的吞吐量会成比例地增加，直到管道满了，吞吐量达到饱和；附加负载不应降低吞吐量。类似地，服务显示的响应时间在轻负荷下大致恒定，因为它是由管道的深度决定的。当负载接近饱和时，排队延迟占主导地位。
? 在许多服务的典型闭环场景中，每个客户端在交付下一个请求之前等待响应，响应时间应该随着客户端数量的增加而线性增加。而对于传统的Web来说，当负载增加时，吞吐量降低，响应时间显著增加，造成服务崩溃。well-conditioned服务一定要能graceful degradation（高效处理崩溃）：当提供的负载超过容量时，服务仍旧能以线性响应时间代价维持高吞吐量，对所有clients的影响是相同的，或者至少基于一些特定服务的策略能够预测这个代价。
2.1 线程并发 Thread-based concurrency
? 下图简要描述了基于线程的并发：每个传入请求被分配给一个单独的线程，该线程处理请求并将结果返回给客户端。这里没有显示其他I/O操作，如磁盘访问，但是将合并到每个线程的请求处理中。
? 
服务器应用程序最常用的设计是thread-per-request model（线程请求一对一模型）。顾名思义，这个模型接受的每个请求都会用一个专门的线程去处理，同步操作保护共享资源。OS通过线程之间的透明切换（transparently switching）实现计算和I/O资源的复用（overlap）。
? 尽管这个模型实现起来很简单，但当并发数量很大时，与线程切换（即上下文切换）相关的开销可能导致严重的性能下降（比如缓存和TLB丢失、调度开销和锁争用）。因为无论对于线程还是进程，它们设计的初衷都是为了支持“多程序编程”。操作系统的做法都是为它们分配一套虚拟的硬件资源。这个做法确实很适用于它的初衷，对于应用程序来说，线程间的资源分配就是透明的了，就没必要在这方面投入过多精力。
? 然而当使用背景从“多程序编程”转换为“高并发”，这个方法会使应用程序很少有机会参与系统范围的资源管理决策，或者得到资源可用性的指示。所以它可能无法适应不断变化的条件。因为虚拟化从根本上隐藏了资源是有限和共享的这一事实。
? 因此，如果优化目标是安全高效的资源虚拟化而非高效管理（graceful management）和高并发性（high concurrency），那依旧是为多程序编程而设计的。
2.2 线程池 Bounded thread pools
? 为了避免线程的overuse，许多系统设计了一个粗糙的负载调节方法——固定大小的线程池：当服务器中的请求数量超过某个固定的阈值时，将不接收额外的连接。通过限制并发线程的数量，服务器可以避免吞吐量下降，而且总体性能比不受约束的thread-per-request model更健壮。
? 但是，当每个请求由单个线程处理时，很难找到内部性能瓶颈，所以很难执行调优和负载调节。考虑一个简单的线程Web服务器，其中有一些cheap请求（例如缓存的静态页面），也有一些expensive请求（例如，大页面不在缓存中）。在高并发场景里，这些expensive的请求可能是性能瓶颈的根源，因此需要减载。然而，服务器无法检查内部请求流以实现这样的策略，所以它只知道线程池已饱和，不知道瓶颈在哪，并且武断地拒绝处理一切请求。
? 并且，这种方法对客户端并不友好：当所有服务器都很忙或阻塞时，客户端请求在网络中排队等待服务，这可能会导致客户机饿死。
2.3 事件驱动并发 Event-driven concurrency
? 下图描述了采用事件驱动的服务器的事件流：主线程处理来自网络、磁盘和其他来源的传入事件，并使用这些事件来驱动许多有限状态机的执行。每个FSM代表整个系统的单个请求或执行流。该设计的复杂性的关键来源是事件调度程序，它必须能控制每个FSM。
? 基于thread的并发对可伸缩性限制太大，因此很多系统采用基于event的方法来管理并发。
? 在这种方法中，服务器由少量线程（通常每个CPU一个）组成，这些线程连续循环，处理队列中不同类型的事件。事件可能由操作系统或应用程序内部生成，通常包括network和disk I/O就绪和完成的通知（readiness and completion notifications），计时器（timers），或其它特定应用程序产生的事件。
? 事件驱动并发将每个task视为有限状态机（FSM）进行处理，其中FSM状态间的转换由event触发。可以看到，基于线程的并发依赖线程上下文（thread context），而事件驱动并发的服务器维护每个task各自的状态。
? 而其星形结构意味着，Scheduler监听所有事件，负载很重。
? 以Flash系统为例，服务器里设计了不同的组件，每个组件都会响应特定类型的event（如socket连接、filesystem access）而主服务器的进程负责连续地将事件分发相应组件。这些组件通过库调用（library calls）实现。当然，一些I/O操作（比如filesystem access）没有异步接口，那主服务器进程就会通过IPC将这些event分发给helper processes来处理这些事件。helper processes发出或阻塞I/O请求，并在完成后向主进程返回event。（不过FTP协议的filesystem access是通过单个进程实现的）
? 事件驱动系统对负载具有鲁棒性，负载过饱和时吞吐量几乎不会降低。随着任务数量的增加，服务器吞吐量会增加直到填满管道，瓶颈（比如CPU）饱和。如果管道中的任务数量进一步增加，多余的任务将被服务器的事件队列吸收。因此高负载下的吞吐量仍能在很大的范围内保持不变，而每个任务的延迟线性增加。
? 但这也说明该模型需要基于一个重要的假设：事件处理线程不阻塞，因此必须使用非阻塞I/O机制。由于interrupts、page faults和garbage collection的存在，无论使用哪一种I/O机制，哪怕是可伸缩的（scalable ）I/O原语，事件处理线程都可能阻塞。因此事件驱动设计的重点就是事件的调度和排序，即应用程序负责决定何时处理每个传入事件以及以何种顺序处理多个流的FSM。而设计的难点在于平衡公平性和低响应时间。
? 并且，基于事件的并发很难模块化：首先，事件调度算法的选择通常是针对特定应用而定制的，引入新功能可能需要重新设计算法；此外，模块化意味着每个模块的代码必须可信，否则就会产生阻塞或消耗大量资源，从而导致事件处理线程暂停。
2.4 结构化事件队列 Structured event queues
? 针对上述问题，已经提出了标准事件驱动设计的几个变体。这些设计的一个常见方面是使用一组事件队列来设计event-driven的应用程序，以提高代码模块性并简化应用程序设计。
3 SEDA The Staged Event-Driven Architecture
? SEDA是流水线化的事件驱动模型，能够异步执行服务。和直接用事件驱动模型相比，SEDA更加去中心化与模块化。下图描述了SEDA的架构，其特点主要有：
- 服务通过Queue分解成Stage: 每个Stage代表FSM的一个状态集合，Queue作为一个explict的控制边界，将Satges解耦；
- 使用Thread Pool驱动Stage的运行: 将事件处理同线程的创建和调度分离，Stage可以顺序或者并行执行，Stage可能在内部阻塞，给阻塞的stage分配较少的线程；
- 有助于服务的调试和性能分析：SEDA将应用程序代码分解为多个阶段和明确的事件传递机制，调试工具可以跟踪系统中的事件流，并将其描述为Stages间的交互，由于Stages通过事件分派协议而不是传统的API进行交互，因此直接在Stage间插入Proxy Stages就可以进行调试和性能评测。
3.1 优势 Goals
- 大规模并发：为了避免线程导致的性能下降，SEDA尽可能使用事件驱动。这也要求系统提供高效和可伸缩的I/O原语；
- 易于构建well-conditioned服务：为了降低构建Internet服务的复杂性，SEDA设计一套接口，屏蔽许多调度和资源管理的细节、支持模块化、并提供对调试和性能分析的支持；
- 支持introspection：应用程序应该能够分析request stream，以适应不断变化的负载条件。例如，系统应该能够对请求进行优先排序和过滤，在高负载下对一些不重要的请求服务降级；
- 自适应资源管理：系统应该动态调整其资源管理参数，而不是强制要求应用程序资源和客户端提供其需求和负载特征的参数。例如，分配给一个stage的线程数应该根据感知到的并发需求自动确定，而不是由程序员硬编码。
3.2 设计健壮的Stage模块 Stages as robust building blocks
Stage是SEDA的基本处理单元，其结构如下：
- 一个接受输入的Event Queue；
- 一个应用程序开发者编写的Event Handler，Handler本身可以创建新的event；
- 一个Controller用于对执行过程进行控制，实现自适应资源管理;
- 一个Thread Pool用于并发处理。
? 线程是SEDA中的基本并发机制，然而线程只存在于每个Stage内部。即SEDA宏观上基于事件，微观上基于线程。
? Stage Thread通过从Incoming Event Queue中提取一批事件，并调用应用程序提供的相应的事件处理程序去处理（event handler processes ）。
? Event Handler是每个Stage的核心逻辑部分，其输入是一个事件的batch。它处理每一批事件，并将它们发送到其它Stage的事件队列。事件处理程序不能直接控制队列操作或线程。Handler本身可以创建新的event。
? 通过将应用程序核心逻辑与线程管理和调度分离，Stage能够控制Event Handler程序的执行，以实现不同资源管理策略。如，传递给事件处理程序的事件的数量和顺序可以由运行时环境外部控制。但是，应用程序也可以通过过滤或重新排序传递给它的event batch来实现自己的调度策略。
? 此外，动态控制可以根据需要自动调整分配给每个阶段的线程数量。根据线程系统和调度程序的特性，此设计允许阶段按顺序或并行运行，或两者的组合。在本文中，我们假设SMP环境中支持操作系统的抢占式线程，尽管这种选择不是SEDA设计的基础。例如，可以设计一个线程系统，该系统了解应用程序的阶段结构并相应地调度线程。
3.3 应用程序在Stages间 Applications as a network of stages
? Stage间由事件队列连接，当前Stage的事件处理程序先通过系统提供的查找例程获取目标Stage传入事件队列的句柄，在通过句柄调用该队列上的排队操作，从而将事件发送给下一个Stage。然而，在Stage之间引入队列提供了隔离、模块化和独立的负载管理，但可能会增加延迟，因为事件队列是有限的，如果目标事件队列已经达到阈值，即发生Backpressure，排队操作可能会失败。
? 两种处理方法：阻塞、丢弃新事件。或执行自定义操作，如向用户发送错误、执行替代功能、提供降级服务等。
? 所谓Backpressure是一种这样的现象：在数据流从上游生产者向下游消费者传输的过程中，上游生产速度大于下游消费速度，导致下游的Buffer溢出。Buffer本身就是因为上游生产速度大于下游消费速度而出现的，但由于外部条件的限制，使它具有上限。Buffer达到上限的时候，就产生了Backpressure现象。
3.4 动态资源控制器 Dynamic resource controllers
? Controller观察Stage的运行时特征，并动态调整参数。控制器可以完全使用Stage的内部状态信息进行调控，也可以基于全局状态协同工作。并且，SEDA无需知道底层的操作系统具体使用的是哪一种资源管理算法（比如一些线程调度策略），而只是通过观察资源变化来调度。当然有些情况下应该去在一定程度上控制操作系统，毕竟操作系统提供的基本资源管理机制，可以受到应用程序级的控制，来满足Internet服务的需求。
? SEDA中存在多种资源控制器，这里提到两种：
? 线程池控制器通过调整Stage Thread的数量来控制Stage内部的合理并发。它通过定期对输入队列进行采样，并在队列长度超过某个阈值时添加一个线程，直至当前Stage的最大线程数。当线程在指定的时间段内处于空闲状态时，会将其从阶段中删除。这个线程池看起来是独立的，实现过程中可能是共享的。
? 批处理控制器通过调整Batching因子，即每次调用Event Handler所处理的事件数，以平衡低响应时间和高吞吐量。因为一次处理多个事件会增加吞吐量，然而较大的批处理因子也会增加响应时间，因此这个资源控制器尝试通过观察Stage的事件输出速率，来找到具有稳定吞吐量的最小Batching因子。先降低Batching因子直到吞吐量开始下降，若吞吐量小幅降低，则适当增大，若吞吐量骤降，则Batching因子直接设置为最大值。所以它运行的时候，吞吐量呈现出有规律的波动。
4 Asynchronous I/O Primitives
? 为了满足SEDA支持高并发的目标，需要高效、健壮的I/O接口。本节描述在SEDA中如何使用现有的OS原语实现这些接口。我们描述了一个异步套接字层，该层使用操作系统提供的非阻塞I/O；以及一个异步文件I/O层，该层使用操作系统提供的阻塞I/O和线程池来描述非阻塞行为。这两个层都是作为SEDA Stage实现的，应用程序可以使用这些Stage来提供快速异步I/O。
4.1 异步套接字层 Asynchronous socket I/O
? 异步套接字（asyncSocket）层为服务提供易于使用的非阻塞套接字接口。
? 应用程序创建asyncClientSocket和asyncServerSocket类对象，用于初始化传出套接字（Outgoing Socket）和传入套接字（Incoming Socket）的连接。
? asyncConnection实现与外部的接口。建立连接时，asyncConnection对象被push到用户提供的一个事件队列（通常是与请求阶段关联的队列）上，相当于插头连接了插板。传入Socket的数据包（Incoming packet）被放在用户的事件队列中，传出Socket的数据包（Outgoing packet）被放在一个由asyncConnection实现的队列上。并且，每个Outgoing packet还可以绑定一个专属的事件队列，这个Packet传输时（不是传输完成，因为操作出队的时候才调用相应的sysCall），Completion Event被放到该队列上。
? 在内部，asyncSocket层使用三个Stage实现，这些阶段被所有Socket共享：
- readStage读取网络中的packet并响应用户请求，在一个新的Socket上初始化一个packet reading；
- writeStage将packet写入网络并建立新的传出连接（Outgoing Connection）；
- listenStage接受新的TCP连接并响应用户请求，监听一个新的端口。
? asyncConnection、asyncClientSocket、asyncServerSocket上的每个操作都会转换为一个请求，并放置到相应阶段的请求队列中。每个Stage服务于两个独立的事件队列：来自用户的request queue和来自操作系统的I/O readiness/completion event queue。每个Stage中的线程交替服务于每个队列，使用简单的timeout机制在两个队列之间切换。I/O事件队列用一个库来实现，当操作出队的时候调用适当的System Call来检索I/O事件。为了提高套接字之间的公平性，每个Stage都会随机处理操作系统传递的I/O事件的顺序。否则操作系统通常以固定顺序返回套接字事件（例如，按文件描述符file descriptor的递增顺序）。
? readStage：当I/O readiness event表明某一个Socket里面有可用数据时，readStage执行Socket Read操作。它将最大16 KB读入预分配的缓冲区，并将得到的packet放到用户提供的事件队列中。在I/O错误的情况下(例如，因为对等端关闭了连接)，readStage关闭Socket并向用户发送通知，这个通知也是一个事件。
? 每次Socket Read需要alloc一个新的packet buffer，可能会导致大量 garbage collection的开销，不过用Java实现的话这个garbage collection并不会引起什么性能问题。
? readStage还提供了一个可选的速率控制器（Rate Controller），可以throttle从网络中读取数据包的速率。它通过计算incoming packet速率的平均值和在event-processing的循环中引入人工的delay控制速率。因为它是控制器，因此也是过载情况下进行减载。
? writeStage：接收来自用户的Packet Write请求，并将它们放入与特定的Socket所绑定的内部队列中。当操作系统指示套接字已准备好写入时，它就尝试在这个Socket的Outgoing队列上写入下一个packet。可以对Socket所绑定的队列设置阈值，避免“慢”套接字在服务器中消耗过多资源。
4.2 异步文件I/O层 Asynchronous file I/O
? 因为（本文使用的）底层操作系统不提供非阻塞文件I/O原语，所以只能使用阻塞I/O和Bounded线程池来实现这一层。
? 用户通过asyncFile对象执行文件I/O，该对象支持常见的read, write, seek, stat, close接口。这些操作中的每一个都变成请求，放在asyncFile Stage的事件队列上。和上面一样，每一个请求出队的时候，对文件执行相应的阻塞I/O操作。为了确保同一文件上的多个I/O请求被串行执行，一次只能有一个线程处理特定文件的事件。当一个I/O请求完成时，相应的Completion Event被放入用户的事件队列中。
? asyncFile Stage被线程池中的某个线程初始化，而SEDA的线程池控制器负责根据观察到的并发需求动态调整线程池的大小。