为什么ePoll比Poll更具可扩展性？

Question

为什么ePoll比Poll更具可扩展性？

epoll

13

这是一个简短的问题，但对我来说很难理解。

为什么ePoll比Poll更具扩展性？

- Filipe Santos

2个回答

19

每次调用 poll 系统调用时，都需要将文件描述符列表复制到内核中。但是使用 epoll_ctl 仅需要一次，而使用 epoll_wait 则不需要每次都进行这个操作。

epoll_wait 对于需要监视的描述符数量是 O(1) 的¹，这意味着您无论是等待一个还是等待5000或50000个描述符，都不会影响其性能。而 poll 虽然比 select 更有效率，但每次仍需遍历整个列表（即对于描述符数量而言是 O(N)）。

最后，epoll 除了可以在“普通”模式下运行外，还可以在“边缘触发”模式下工作，这意味着内核不需要在向您发出就绪信号后跟踪您读取了多少数据。这种模式比较难理解，但是效率更高。

¹正如 David Schwartz 所指出的那样，epoll_wait 当然还涉及到事件发生的数量，因此对于事件数量而言是 O(N) 的。使用任何接口都难以避免。如果在正在监视的描述符上发生了 N 个事件，则应用程序需要收到 N 个通知，并且需要执行 N 个操作以响应正在发生的情况。
在边缘触发模式下，这基本上是稍微不同，但并不根本不同，而且您实际上只会收到 M 个事件，使 M <= N。在边缘触发模式下，当相同的事件（例如 POLLIN）发生多次时，您可能只会收到少数通知，甚至只有一个。但是，这并不会对大O标记产生太大影响。

然而，epoll_wait 不受监视描述符数量的影响。假设它以预期的“正常”方式使用（即监视多个描述符但只关心少量事件），这才是真正重要的事情，此时时间复杂度确实为O(1)。

比喻来说，您可以想象一个哈希表。哈希表在O(1) 时间内访问其内容，但有人可能会认为计算哈希值实际上是相对于键长度为O(N) 的。从技术上讲，这是绝对正确的，也可能存在这种问题的情况，然而，对于大多数人来说，这并不重要。

- Damon

1

谢谢您的回答。但是，如果使用epoll，我只需要复制一次文件描述符，那么我如何从用户空间更改文件描述符列表呢？ - Filipe Santos

2

你可以使用 epoll_ctl 向集合中添加、删除或更改描述符。这会根据你的请求更改内核结构（例如，将 eventpoll 结构添加到文件描述符的等待队列中）。当你调用 epoll_wait 时，它只是阻塞。当文件描述符上发生某些事件时，它会唤醒该描述符的等待队列（实际上比这更复杂，在 eventpoll 结构内部还有另一个队列，因此多个线程可以在同一个 fd 上阻塞，但基本上就是这样）。所以实际上它更像是“定向通知”而不是“搜索轮询”，这也是为什么它的时间复杂度是 O(1)。 - Damon

实际上，epoll_wait 的时间复杂度是 O(N)，而不是 O(1)。使用 epoll_wait 发现的套接字数量是 O(N)，与 poll 类似。每个发现的套接字必须被复制到应用程序的 epoll_event 结构中。如果你将轮询的套接字数量翻倍，那么期望具有活动的套接字数量也会增加一倍。 - David Schwartz

@DavidSchwartz：你在某种程度上是正确的，epoll_wait 在同一时间内是 O(N) 和 O(1)。但重要的是它对于它被设计用来处理的“正常”情况是 O(1) 的。假设你监视许多（几十个、几百个、几千个）描述符，但实际上只有很少的事件（通常少于5个）会同时发生。epoll 不能做到“魔法”，它在事件发生方面不是（也不能是）O(1) - 如果发生 N 个事件，则必须为 N 个事件做些什么。然而，如果 N ≈ 1，那就几乎和 O(1) 一样好了。更重要的是... - Damon

...这是关于描述符数量的O(1)。因为如果你有N ≈ 10000，那么O(1)或O(N)并不是同一件事情（非常明显）。在这里，它真的很重要。您的反对意见是正确的，因为如果一个人以与其预期用途相反的方式使用epoll接口，并期望发生“魔法”，那么他可能会感到失望。在这种情况下，普通的poll可能更容易且同样快速。我在这个冗长的答案中提到了这一点，其中包括epoll在内（大约在中间位置）。 - Damon

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Schwartz · Accepted Answer

虽然 Damon 的理由对于你从不阻塞套接字的情况是正确的，但在典型的实际程序中，原因完全不同。一个典型的程序看起来像这样：

1）完成我们现在能做的所有工作。

2）检查是否需要服务任何网络连接，如果没有要处理的内容就进行阻塞。

3）处理发现的任何网络连接。

4）返回步骤 1。

通常，因为您刚刚完成了所有可以完成的工作，所以当您回到步骤 2 时，您没有要执行的工作。因此，您将不得不等待一会儿。现在，想象一下有 800 个您感兴趣的套接字。内核必须将您放到这 800 个套接字的等待队列上。在这 800 个套接字中的某个套接字收到数据的瞬间，内核就必须将您从这 800 个等待队列中删除。将任务放在等待队列上需要创建一个“thunk”，将该任务链接到该等待队列上。没有好的优化措施，因为内核不知道您将等待哪些 800 个套接字。

使用 epoll，epoll 套接字本身具有等待队列，进程只被放置在该单个等待队列上。需要一个 thunk 来将这 800 个连接中的每一个连接链接到 epoll 等待队列上，但是该 thunk 是持久性的。您可以通过将套接字添加到 epoll 集合中来创建它，并且它会一直保留在那里，直到您将套接字从集合中删除。

当套接字上有活动时，内核会在检测到活动的任务中处理它。当您等待时，内核已经知道是否有检测到事件，内核只需要将您放到那个等待队列上。当您唤醒时，它只需将您从该队列中删除即可。

因此，使用 select 或 poll 的问题不在于拷贝，而在于内核必须在每个阻塞操作上操纵大量的等待队列。