Paper Notes: [SOSP'01] SEDA: An Architecture for Well-Conditioned, Scalable Internet Services

The simplest and most direct approach is to start a thread to handle each incoming request. The benefit of doing this is that the programming model is extremely simple, and issues such as scheduling and isolation are handed over to the operating system to guarantee, which is also relatively reliable. The downside is that when the load is high, it introduces non-negligible overhead. Because physical resources are limited, although the operating system provides a layer of abstraction that makes it look as if we can obtain a very large amount of resources, this is all an illusion and will be fully exposed under high load. The time slice allocated to each thread is limited; a very large number of threads perform frequent context switches; caches keep thrashing; the overhead of thread scheduling increases as the problem scale grows; and lock resources are contended. All of these factors cause performance to drop sharply. Frequent thread creation and destruction also introduce considerable overhead. Judging from the charts provided by the authors, continuing to increase pressure after exceeding the system’s capacity causes system performance to decline. We expect to use some means of self-protection so that the system can remain near its peak performance.

A simple improvement is to use a thread pool. This at least solves the problem caused by having too many threads. The authors mention here that under high load, this approach introduces fairness problems.

Fairness is indeed a very important issue in multi-tenant systems, and it is also a problem that must be faced once a system reaches a certain scale. Let me be a little wordy here and elaborate briefly. Simply put, the resource utilization of a multi-tenant service is much higher than that of a single-tenant service. When there are enough tenants, and they are sufficiently diverse, while some users are busy, there are usually also some users who are idle. This brings an improvement in overall utilization. First, we need to ensure fairness, so that one person’s unexpected use of an unusually large amount of resources does not affect other users who are using the service normally. Otherwise, because of degraded user experience, users will refuse to use your service. Going further, perhaps we need to provide tiered service for users: high-priority users can preempt resources used by low-priority users, and of course the pricing may also be tiered.

The fairness problem mentioned by the authors occurs in the following scenario. When the load is extremely high, the speed at which we process requests cannot keep up with the speed at which requests are generated. A large number of requests accumulate in the task dispatch queue, or even in the network protocol stack. In this situation, the overall latency of a newly arriving request should be the queuing latency plus the latency of actually executing the processing. The queuing latency is uncontrollable, and because the overload problem cannot be properly scheduled, this violates fairness.

I partly agree with the authors' conclusion here. From a purely theoretical perspective, there is indeed no perfect solution to this problem. From a perspective that better matches practical situations, there are actually still some things we can do, and they can achieve good results in some cases. If we consider a DoS (Denial of Service) attack, then never mind your service; even the network equipment may be overwhelmed. In that case, we already have no way to handle it well at the software layer. The more common situation is that some users have abnormal request volumes that exceed their own quotas, but do not exceed the capacity of the whole service; or they do exceed the capacity of the whole service, but not by an especially outrageous amount, for example only by one or two times (depending on the complexity of your business logic). For the former, through quota management, when this request is scheduled for processing, we can reject it, thereby avoiding the burden of executing the business logic. In this way, we can improve our system’s capacity to some extent. If the load rises further, perhaps the speed at which we reject requests cannot keep up with the speed at which requests are generated. In that case, perhaps we can adopt some NIC queue-management strategies, such as Random Early Discard, to further improve our system’s capacity (but it is already lossy at that point).

The authors also give a fairly interesting example. For instance, when the system is idle, a few relatively large requests arrive and occupy all the threads in the thread pool (but there are no subsequent queued requests). Then a bunch of small requests suddenly arrive. Although we could handle them if we had just one more idle thread, now none of the active threads can get to this work in time, and the waiting queue is blown up. This may require more refined policy tuning on a case-by-case basis, such as classifying requests by size to avoid one type of request occupying all active threads.

This paper was written relatively early, and it mainly investigated topics related to HTTP servers, so I feel the model and data processing may indeed both be relatively simple. Therefore, a lot of the time, when people talk about the thread-pool model, it may really mean directly putting requests into the thread pool and running them, without considering more design aspects.

Judging from the authors' broad description, this feels like a traditional event model driven by epoll. Almost all blocking I/O is converted into events, which are then delivered to each submodule for further processing. Each submodule uses a state machine to manage its own state, so the request context is managed by the state machine instead of being placed directly on the thread context. This model is obviously much more complex than the multithreaded model.

This section introduces some improvements to event-driven concurrency. It only says a little about them in general, and I did not see anything particularly valuable, so I will skip it for now.

First, there is nothing wrong with the stage abstraction; it nicely isolates different modules. But not every stage needs to be bound to a thread pool. In some places, it may be more reasonable to combine stages and run them on a single thread pool (concurrency boundaries). Where a thread pool is not needed, an event queue is not needed either; direct method calls are more efficient. I do not think this needs much explanation. The main point is that most of the time the system runs under low load, and creating several thread pools and event queues for no reason is already pretty strange. Moreover, the stage abstraction itself is a logical abstraction, so it is also strange to insist on binding it to a thread pool.

Then it discusses some implementation details. At that time, Java did not yet have non-blocking I/O. In short, this aspect is not important, so I will not talk about it.

Writing it in Java was absolutely the right choice (routine teasing of C/C++)!

Consider load and resource bottlenecks during modeling. One reason is that you can intuitively see where the bottleneck is (you only need to see where the queue is long). Another reason is that your service cannot merely run normally under low load and then fall over as the load approaches its limit.

It also says that test suites are very important. Some test suites simply do not consider high-load situations at all. They also do not consider testing memory bottlenecks, I/O bottlenecks, socket pressure, and so on. In any case, this is basically a complaint about test design. Everyone should take it as a warning when doing performance testing, and should not blindly trust test data obtained in such specific scenarios; its reference value is relatively limited.