مدلهای همزمانی ناهمگام (Async I/O): کالبدشکافی epoll در لینوکس و معماری Event Loop

از مسئله C10K تا C10M: چرا مدل Thread-per-Connection فرو میریزد؟

در معماری سرورهای سنتی (مانند Apache یا سرورهای WSGI همگام در پایتون)، به ازای هر اتصال شبکه ورودی، یک ترد سیستمعامل (OS Thread) اختصاص داده میشود. زمانی که تعداد اتصالات همزمان از چند هزار به صدها هزار (C10M Problem) میرسد، سیستمعامل با سه دیواره سختافزاری برخورد میکند:

• انفجار مصرف رم برای پشته (Thread Stack Overhead): در لینوکس، هر ترد به طور پیشفرض حدود ۲ تا ۸ مگابایت فضای پشته مجازی رزرو میکند و حتی با بهینهترین تنظیمات، نگهداری ۱۰۰ هزار ترد گیگابایتها حافظه کرنل را میبلعد.
• هزینه سنگین Context Switch در سطح کرنل: هر بار که تردی منتظر دریافت بسته شبکه میماند (blocking recv)، زمانبند لینوکس باید تمام ثباتهای پردازنده را ذخیره کند، فضای آدرس مجازی را تغییر دهد و با باطل شدن کش TLB (Translation Lookaside Buffer) و کش L1/L2، هزاران سیکل پردازنده هدر میرود.
• پیچیدگی زمانبندی (Scheduler Contention): زمانبند CFS لینوکس زیر بار مدیریت دهها هزار ترد که مدام بین حالت TASK_INTERRUPTIBLE و TASK_RUNNING جابهجا میشوند، بخش عمده CPU را صرف خودِ عملیات زمانبندی (System Time) میکند.

تکامل I/O Multiplexing در لینوکس: چرا select و poll مقیاسپذیر نیستند؟

برای نظارت بر هزاران سوکت با یک ترد واحد، ابتدا فراخوانهای سیستمی select() و poll() معرفی شدند. اما هر دوی آنها دارای پیچیدگی زمانی $O(N)$ هستند:

• محدودیتهای `select`: از یک آرایه بیتی با سقف ثابت ۱۰۲۴ توصیفگر فایل (`FD_SETSIZE`) استفاده میکند. در هر بار فراخوانی، کل این آرایه باید از فضای کاربر (User Space) به فضای کرنل (Kernel Space) کپی شود و کرنل مجبور است تمام ۱۰۰۰ سوکت را یکییکی به صورت خطی پیمایش کند تا ببیند کدامیک داده جدید دارد!
• محدودیتهای `poll`: سقف ۱۰۲۴ را برداشت، اما همچنان در هر حلقه، آرایهای از ساختارهای pollfd را بین فضای کاربر و کرنل کپی کرده و با پیچیدگی $O(N)$ تمام سوکتها را اسکن میکند. اگر ۱۰۰,۰۰۰ سوکت باز داشته باشید و تنها ۱ سوکت پیام فرستاده باشد، کرنل ۹۹,۹۹۹ بار بررسی بیهوده انجام میدهد.

کالبدشکافی ساختار داده داخلی epoll در کرنل لینوکس: پیچیدگی $O(1)$

فراخوان epoll (معرفیشده در کرنل 2.5.44) با جدا کردن مرحله «ثبت سوکت» از مرحله «انتظار برای رویداد»، پیچیدگی را از کل سوکتهای باز ($O(N)$) به تعداد سوکتهای واقعاً فعال ($O(K)$) کاهش داد. هنگامی که دستور epoll_create1() را صدا میزنید، کرنل یک ساختار داده struct eventpoll ایجاد میکند که دارای دو بخش کلیدی است:

• ۱. درخت قرمز-سیاه (Red-Black Tree - `rbr`): هرگاه با دستور epoll_ctl(EPOLL_CTL_ADD) یک سوکت جدید ثبت میکنید، کرنل آن را با پیچیدگی $O(\log N)$ در یک درخت قرمز-سیاه داخل حافظه کرنل درج میکند. دیگر نیازی به کپی مداوم لیست سوکتها از فضای کاربر در هر حلقه نیست!
• ۲. لیست پیوندی دوطرفه آمادهها (Ready List - `rdllist`): کرنل یک تابع بازگشتی (ep_poll_callback) را به صف انتظار کارت شبکه برای آن سوکت متصل میکند. به محض رسیدن پکت شبکه و رخ دادن وقفه سختافزاری (NIC Interrupt)، کارت شبکه مستقیماً آن سوکت را به rdllist اضافه میکند. وقتی برنامه شما epoll_wait() را صدا میزند، کرنل بدون هیچ جستجویی، صرفاً عناصر موجود در rdllist را با پیچیدگی $O(1)$ به فضای کاربر تحویل میدهد!

تفاوت حیاتی Level-Triggered (LT) و Edge-Triggered (EPOLLET)

در حالت پیشفرض Level-Triggered (LT)، تا زمانی که حتی یک بایت خواندهنشده در بافر کرنل سوکت باقی مانده باشد، epoll_wait در هر چرخه آن سوکت را گزارش میدهد. اما در حالت فوقسریع Edge-Triggered (`EPOLLET`) که در موتورهای مدرنی مثل Nginx، uvloop و Tokio استفاده میشود، کرنل فقط یک بار در لحظه تغییر وضعیت (رسیدن داده جدید) به شما اطلاع میدهد. بنابراین در حالت Edge-Triggered، برنامه شما موظف است سوکت Non-Blocking را در یک حلقه while بخواند تا زمانی که کرنل خطای EAGAIN یا EWOULDBLOCK برگرداند.

پیادهسازی سرور Reactor سطح پایین با select.epoll و حالت Edge-Triggered در پایتون

کد زیر بدون استفاده از هیچ فریمورک آمادهای (حتی بدون asyncio)، مستقیماً با سیستمکال epoll کرنل لینوکس در حالت Edge-Triggered (`EPOLLET`) یک سرور غیرمسدودکننده (Non-Blocking Event Loop) میسازد که چرخه واقعی کارکرد داخلی uvloop و Tokio را نشان میدهد:

import errno
import select
import socket
from typing import Dict

class LinuxEpollEdgeTriggeredReactor:
    """
    Zero-dependency, single-threaded O(1) Event Loop built directly
    on Linux epoll in Edge-Triggered (EPOLLET) mode.
    """
    def __init__(self, host: str = '0.0.0.0', port: int = 8080):
        self.server_sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        self.server_sock.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
        self.server_sock.setblocking(False)
        self.server_sock.bind((host, port))
        self.server_sock.listen(4096)

        # Create kernel eventpoll instance (Red-Black Tree + rdllist)
        self.epoll = select.epoll()
        # Register master listening socket in Edge-Triggered mode
        self.epoll.register(self.server_sock.fileno(), select.EPOLLIN | select.EPOLLET)

        self.connections: Dict[int, socket.socket] = {}
        self.read_buffers: Dict[int, bytearray] = {}

    def _accept_all_pending(self) -> None:
        """In EPOLLET mode, we must accept in a loop until EAGAIN."""
        while True:
            try:
                client_sock, _ = self.server_sock.accept()
                client_sock.setblocking(False)
                fd = client_sock.fileno()
                self.connections[fd] = client_sock
                self.read_buffers[fd] = bytearray()
                self.epoll.register(fd, select.EPOLLIN | select.EPOLLET | select.EPOLLRDHUP)
            except OSError as exc:
                if exc.errno in (errno.EAGAIN, errno.EWOULDBLOCK):
                    break
                raise

    def _drain_socket(self, fd: int) -> None:
        """Drain kernel socket receive buffer completely until EAGAIN."""
        sock = self.connections[fd]
        while True:
            try:
                chunk = sock.recv(4096)
                if not chunk:
                    self._close_connection(fd)
                    return
                self.read_buffers[fd].extend(chunk)
            except OSError as exc:
                if exc.errno in (errno.EAGAIN, errno.EWOULDBLOCK):
                    break
                self._close_connection(fd)
                return

        if b'\r\n\r\n' in self.read_buffers[fd]:
            response = b'HTTP/1.1 200 OK\r\nContent-Length: 18\r\nConnection: keep-alive\r\n\r\nepoll ET reactor\r\n'
            sock.sendall(response)
            self.read_buffers[fd].clear()

    def _close_connection(self, fd: int) -> None:
        self.epoll.unregister(fd)
        sock = self.connections.pop(fd, None)
        self.read_buffers.pop(fd, None)
        if sock:
            sock.close()

    def run_event_loop(self) -> None:
        server_fd = self.server_sock.fileno()
        try:
            while True:
                # Blocks until kernel rdllist is non-empty; returns strictly active FDs in O(1)
                events = self.epoll.poll(timeout=1.0)
                for fd, event_mask in events:
                    if fd == server_fd:
                        self._accept_all_pending()
                    elif event_mask & (select.EPOLLHUP | select.EPOLLERR | select.EPOLLRDHUP):
                        self._close_connection(fd)
                    elif event_mask & select.EPOLLIN:
                        self._drain_socket(fd)
        finally:
            self.epoll.close()
            self.server_sock.close()