Ускорение роутера в Django в 51 раз

История началась с разбора использования ресурсов приложением, которое занимается проксированием. Обнаружили, что довольно много времени оно тратит на выбор маршрута (роута), и решили ускорить этот процесс. Описанная в статье оптимизация не требует каких-то особых вложений, усилий или условий, поэтому приведенный код можно забрать к себе и использовать без каких-либо чрезмерных вмешательств.

Роутер

Каждый раз, когда в приложение приходит очередной запрос, оно берёт в руки URL запроса (и иногда HTTP verb), роутер, в котором описаны правила (роуты), и пытается найти подходящий. Всего таких механизмов два:

1. массив роутов;

2. компактное префиксное дерево (radix tree/trie) путей, которое используется в fasthttp (просьба не путать с fastapi) и axum. Оно имеет некоторые ограничения, в частности, на использование регулярок и не имеет возможности явно указывать приоритеты (какой роут пытаться резолвить первым), поэтому не является drop-in replacement и в нашем случае не подходит.

В 99% web-фреймворков используется первый вид — простой массив, куда записываются роуты, и вы их прекрасно знаете:

urlpatterns = [
	...
    path("marketplaces/<int:company_id>/status", MarketplacesStatusView.as_view(), name="marketplaces_status"),
    path("marketplaces/<int:company_id>/reports", MarketplacesReportsView.as_view(), name="marketplaces_reports"),
    path("marketplaces/reports/<int:report_id>", MarketplacesReportView.as_view(), name="marketplaces_report"),
    ...

Роуты могут быть вложенными друг в друга (в django — include), но алгоритм работы у них всегда один и тот же:

1. идти по массиву сверху вниз;

2. сравнивать URL с роутом;

3. если нашли — отдавать (в случае вложенности — спускаться на уровень ниже).

В Django это работает максимально неоптимальным образом: на каждый роут создаётся регулярное выражение, и каждый запрос проходит в худшем случае (если ни один роут не подошёл) все регулярки, пытаясь смэтчиться с каждой. В большом проекте роутов могут быть сотни. И даже несмотря на то, что регулярки в Python написаны на С, они всё равно медленные.

В 2017 году в Django появился новый способ объявлять роуты — path (способ с регулярками переименовали из url в re_path). Однако под капотом Django всё равно компилирует path в регулярку, поэтому никакого ускорения это не даёт.

Что тут ускорять

Цифры до оптимизации таковы: на продовом поде резолвинг URL /api/v5/jsonrpc занимал 180 мкс (0,18 мс) при следующих вводных:

• Python 3.11

• Django 4.1

• 180 роутов в роутере суммарно (re_path и path)

Может показаться, что ускорять нечего, но если методом пристального взгляда посмотреть на все роуты, то их можно разделить на четыре категории:

1. re_path со сложными регулярками;

2. path("hello/world", ...), где путь является константой и не содержит ни одной переменной (<int:user_id>);

3. path("hello/world/<int:user_id>/", ...), где путь содержит как минимум одну переменную, но перед первой переменной есть константная строка;

4. path("<path:url>", ...), где путь содержит как минимум одну переменную и перед первой нет константной строки.

С первой и последней категориями едва ли можно что-то сделать, а остальные содержат очень важный константный префикс. В каждом случае мы можем его использовать:

• Если путь является константой полностью, то самым логичным будет сравнить пришедший URL с этой строкой простым равенством == (такая оптимизация есть в aiohttp);

• Если путь содержит переменную, то можно запомнить префикс до первой переменной и сравнивать на то, что URL.startswith(prefix).

При этом, если путь содержит переменные, то нам неизбежно придётся использовать регулярку, чтобы извлечь эти переменные из URL. И может сложиться впечатление, что один match регуляркой «дешевле», чем сравнение на startswith, а затем match регулярки. И это правда, но справедливо, только если мы рассматриваем один роут в отрыве от всех. Если же роутов несколько, то к URL подойдёт ровно один роут, на котором Django остановит поиск и вернёт его. Остальные роуты с большой вероятностью не подойдут по префиксу, а значит, проверки по регулярке не будет вообще. Эта оптимизация ускоряет отбраковку роутов в 3–6 раз:

In [8]: %timeit url == x 
30.5 ns ± 0.0404 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

In [12]: %timeit url.startswith(x) 
80.3 ns ± 0.0754 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

In [13]: %timeit p.match(url)  # p=re.compile("hello/world/(?P<company_id>d+)") 
196 ns ± 0.276 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

Код регистрации нового роута с учётом того, что роуты в Django могут быть вложенными, получился такой:

from collections.abc import Awaitable, Callable, Sequence
from typing import Any

from django.http import HttpResponseBase
from django.urls.conf import _path  # type: ignore[attr-defined]
from django.urls.resolvers import RoutePattern, URLPattern, URLResolver


class PrefixRoutePattern(RoutePattern):
    def __init__(self, route: str, name: str | None = None, is_endpoint: bool = False) -> None:
        # Ищем расстояние до первой переменной
        idx = route.find("<")

        # Если не нашли, то весь паттерн — константная строка и её можно
        # сравнивать с URL'ом на равенство целиком
        if idx == -1:
            self._prefix = route
            self._is_static = True
        # Если нашли, запоминаем префикс до первой переменной
        else:
            self._is_static = False
            self._prefix = route[:idx]
        # Роут может быть неоконечным, то есть, паттерн сам по себе является префиксом. Например, в случае
        # `path("users/", include(...))`
        self._is_endpoint = is_endpoint
        super().__init__(route, name, is_endpoint)

    def match(self, path: str) -> tuple[str, tuple[Any, ...], dict[str, Any]] | None:
        # Если паттерн — константная строка (в нём нет переменных), то:
        if self._is_static:
            # Если роут оконечный, то сравниваем на равенство строки
            if self._is_endpoint and path == self._prefix:
                # match отдаёт кортеж из трёх значений:
                # 1. Остаток URL'а
                # 2. Неименованные переменные
                # 3. Именованные переменные
                # Так как наш роут оконечный и не содержит переменных, то все значения пусты
                return "", (), {}
            # Если же роут содержит саброуты, то проверяется, что URL начинается с префикса
            elif not self._is_endpoint and path.startswith(self._prefix):
                return path[len(self._prefix) :], (), {}
        # Если в паттерне есть хоть одна переменная, то проверяется,
        # что URL начинается с префикса и если это так, матчинг передаётся дальше (в регулярку)
        else:
            if path.startswith(self._prefix):
                return super().match(path)
        return None


def make_pattern(route: str, name: str | None = None, is_endpoint: bool = False) -> PrefixRoutePattern | RoutePattern:
    # При регистрации роута проверяется, содержит ли паттерн переменные
    # и насколько первая переменная далеко от начала.
    # Если первая переменная очень близко к началу строки,
    # то префикс получится пустой или короткий, в котором не будет смысла,
    # поэтому используется стандартный RoutePattern
    idx = route.find("<")
    if idx == -1 or idx > 2:
        return PrefixRoutePattern(route, name, is_endpoint)
    else:
        return RoutePattern(route, name, is_endpoint)


def my_path(
    route: str,
    view: (
        Callable[..., HttpResponseBase | Awaitable[HttpResponseBase]]
        | tuple[Sequence[URLResolver | URLPattern], str | None, str | None]
    ),
    kwargs: dict[str, Any] | None = None,
    name: str | None = None,
) -> URLResolver | URLPattern:
    return _path(route=route, view=view, kwargs=kwargs, name=name, Pattern=make_pattern)

На этом этапе резолвинг начал занимать 100 мкс — в 1,7 раз меньше.

Следующей оптимизацией была тривиальная перестановка неперекрывающихся «горячих» роутов повыше. Для нас это оказались jsonrpc хэндлеры.

Например, такие роуты можно менять местами, т. к. их области допустимых значений не пересекаются:

urls = [
    my_path("v3/jsonrpc", private_json_rpc_api.jsonrpc),
    my_path("v5/jsonrpc", private_json_rpc_api_v5.jsonrpc),
]

Можно и такие (int принимает только числа):

urls = [
    my_path("users/<int:user_id>", user_handler),
    my_path("users/me", me_handler),
]

А вот такие менять уже нельзя:

urls = [
    my_path("users/me", me_handler),
    my_path("users/<str:user_id>", user_handler),
]

После поднятия «горячих» роутов, резолвинг начал происходить за 12,4 мкс. Это 0,0124 мс, что даёт ускорение в 14,5 раз.

Последней оптимизацией было прикручивание LRU-кэша, хранящего часто используемые данные, в URLResolver с помощью ужасного манки-патчинга:

from functools import lru_cache


def patch_resolver() -> None:
    from django.urls.resolvers import URLResolver

    orig_resolve = URLResolver.resolve
    # Кэш размером 16 позволяет кэшировать 16 самых часто используемых роутов и имеет смысл
    # только если часто используемые роуты не имеют динамических частей (<int:something> или регулярок)
    cached = lru_cache(maxsize=16)(orig_resolve)

    def dispatcher(self: URLResolver, path: str | Any) -> ResolverMatch:
        if isinstance(path, str):
            return cached(self, path)
        return orig_resolve(self, path)

    URLResolver.resolve = dispatcher

patch_resolver()

Этот кэш едва ли поможет роутам с переменными, зато отлично работает на константных роутах, например, хэндлерах jsonrpc.

После этого резолвинг /api/v5/jsonrpc начал происходить за 3,5 мкс, и мы получаем итоговое ускорение в 51 раз.

Итог

Хитрым и условно бесплатным методом мы ускорили флоу каждого запроса на 150+ мкс. Формально — это малозаметная цифра, однако она является чистейшей CPU-нагрузкой, и на каждые 10000 запросов экономит 1,5 секунды процессорного времени, что для компьютера является десятью вечностями. Мелочь, а приятно.

Немного советов, как это использовать

1. Скопировать код PrefixRoutePattern в любое место. И заменить все path на my_path. Они полностью совместимы и заменяемы.

2. Скопировать код патча роутера (patch_resolver) в settings/__init__.py и там же его вызвать.

3. Поднять более горячие роуты выше, не забывая про overlap patterns.

4. Заменить re_path на my_path, если это возможно, избавившись от регулярок.

5. Тривиальные группы захвата (переменные) в роутах заменить на обычный текст. Например, /api/v<int:version>/jsonrpc/ имеет смысл разложить на несколько отдельных роутов: /api/v1/jsonrpc/, /api/v2/jsonrpc/ и т. д.

6. Увидеть запрос в БД на 10 секунд и понять, что это всё было зря.

7. Плакать.