Speed up your router in Django by 51 times
The story began with an analysis of resource usage by an application that performs proxying. We discovered that it spends quite a lot of time choosing a route (route), and decided to speed up this process. The optimization described in the article does not require any special investments, efforts or conditions, so the given code can be taken home and used without any excessive intervention.
Router
Every time another request comes to the application, it picks up the request URL (and sometimes the HTTP verb), the router, which describes the rules (routes), and tries to find a suitable one. There are two such mechanisms:
array of routes;
compact prefix tree (radix tree/trie) of paths, which is used in fasthttp (please do not confuse with fastapi) and axum. It has some restrictions, in particular on the use of regular expressions and does not have the ability to explicitly indicate priorities (which route to try to resolve first), therefore it is not drop-in replacement and is not suitable in our case.
99% of web frameworks use the first type – a simple array where routes are written, and you know them very well:
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), но алгоритм работы у них всегда один и тот же:
идти по массиву сверху вниз;
сравнивать URL с роутом;
если нашли — отдавать (в случае вложенности — спускаться на уровень ниже).
В Django это работает максимально неоптимальным образом: на каждый роут создаётся регулярное выражение, и каждый запрос проходит в худшем случае (если ни один роут не подошёл) все регулярки, пытаясь смэтчиться с каждой. В большом проекте роутов могут быть сотни. И даже несмотря на то, что регулярки в Python написаны на С, они всё равно медленные.
В 2017 году в Django появился новый способ объявлять роуты — path (способ с регулярками переименовали из url в re_path). Однако под капотом Django всё равно компилирует path в регулярку, поэтому никакого ускорения это не даёт.
Что тут ускорять
Цифры до оптимизации таковы: на продовом поде резолвинг URL /api/v5/jsonrpc занимал 180 мкс (0,18 мс) при следующих вводных:
Может показаться, что ускорять нечего, но если методом пристального взгляда посмотреть на все роуты, то их можно разделить на четыре категории:
re_pathсо сложными регулярками;path("hello/world", ...), где путь является константой и не содержит ни одной переменной (<int:user_id>);path("hello/world/<int:user_id>/", ...), где путь содержит как минимум одну переменную, но перед первой переменной есть константная строка;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\d+)") 196 ns ± 0.276 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each) The code for registering a new route, taking into account the fact that routes in Django can be nested, turned out like this:
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)
At this stage, resolution began to take 100 µs – 1.7 times less.
The next optimization was the trivial rearrangement of non-overlapping hot routes higher. For us, these turned out to be jsonrpc handlers.
For example, such routes can be swapped, since their ranges of acceptable values do not intersect:
urls = [
my_path("v3/jsonrpc", private_json_rpc_api.jsonrpc),
my_path("v5/jsonrpc", private_json_rpc_api_v5.jsonrpc),
]You can also have these (int accepts only numbers):
urls = [
my_path("users/<int:user_id>", user_handler),
my_path("users/me", me_handler),
]But these can no longer be changed:
urls = [
my_path("users/me", me_handler),
my_path("users/<str:user_id>", user_handler),
]After raising “hot” routes, resolution began to occur in 12.4 µs. This is 0.0124 ms, which gives a speedup of 14.5 times.
The last optimization was to attach an LRU cache that stores frequently used data to the URLResolver using a terrible manky patch:
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()This cache is unlikely to help routes with variables, but it works great on constant routes, for example, jsonrpc handlers.
After this resolution /api/v5/jsonrpc started happening in 3.5 µs, and we get a final speedup of 51 times.
Bottom line
Using a cunning and shareware method, we accelerated the flow of each request by 150+ microseconds. Formally, this is an insignificant figure, but it is a pure CPU load, and for every 10,000 requests it saves 1.5 seconds of processor time, which is ten eternities for a computer. It's a small thing, but nice.
Some tips on how to use it
Copy code
PrefixRoutePatternto any place. And replace everythingpathonmy_path. They are fully compatible and replaceable.Copy the router patch code (
patch_resolver) Vsettings/__init__.pyand call him there.Raise hotter routes higher, not forgetting about overlap patterns.
Replace
re_pathonmy_pathif possible, getting rid of regular characters.Replace trivial capture groups (variables) in routes with plain text. For example,
/api/v<int:version>/jsonrpc/It makes sense to split it into several separate routes:/api/v1/jsonrpc/,/api/v2/jsonrpc/etc.See a query in the database for 10 seconds and realize that it was all in vain.
Cry.
