И почему самым неожиданным bottleneck оказался не поиск, не индексы и даже не база данных, а JSON
Есть проекты, которые начинаются с требования бизнеса. А есть проекты, которые начинаются с совершенно другого вопроса:
А насколько далеко можно зайти, если убрать из системы всё лишнее?
У меня получился второй вариант.
Есть интернет-магазин примерно с четырьмя миллионами товаров и сотнями тысяч посадочных страниц. На сайте есть фильтры, сортировки, пагинация и довольно большой набор URL, которые постоянно нужно обслуживать. Основная нагрузка при этом — чтение. Сам характер запросов достаточно предсказуем. Нужно получить страницу магазина или категории, открыть посадочную страницу, применить несколько фильтров, пересечь условия, ограничить диапазон цены, отсортировать результаты и вернуть первые 20–60 товаров. В какой-то момент я решил не пытаться оптимизировать традиционную архитектуру по отдельности, а посмотреть, сколько вообще можно из неё убрать.
Так появились Makodb — mmap-based KV DB с индексами — и затем SilentJSON, специализированный JSON serializer/parser, построенный вокруг той же идеи: если структура данных и модель доступа известны заранее, не нужно каждый раз платить за универсальность. Это не попытка сделать новую PostgreSQL. Наоборот. Это очень специализированное хранилище под очень конкретный класс нагрузки.
Всё началось с довольно простой идеи
Если у меня есть четыре миллиона товаров, мне не обязательно каждый раз прогонять запрос через всю привычную цепочку:
HTTP -> application -> ORM -> SQL -> query planner -> index -> rows -> objects -> interfaces -> JSON -> HTTP
Можно попробовать сделать путь значительно короче:
HTTP -> индексы -> docID -> mmap -> готовые данные -> JSON -> HTTP
Вторая схема выглядит даже скучно.
И именно поэтому она мне понравилась.
Почему не SQL
Сразу оговорюсь: я не считаю SQL плохим решением. Если приложению нужны транзакции, сложные JOIN, произвольные запросы, аналитика, конкурентные записи и богатая семантика данных, я бы не стал писать такую систему самостоятельно. Но мой workload совсем другой. Я почти всегда заранее знаю, что именно нужно найти. Например, запрос вида:
category = 123 AND brand = 42 AND price >= 500 AND price <= 5000 ORDER BY price LIMIT 60
не обязательно превращать в универсальный SQL-запрос. Если структура запросов известна, часть работы можно сделать заранее. У меня есть отдельные индексы категории, бренда, цены и сортировки. Категория может быть представлена как массив docID, бренд — ещё одним массивом, а цена — отсортированным числовым индексом. Дальше задача сводится к пересечениям этих структур. То есть вместо того, чтобы каждый раз заставлять универсальный движок разбираться, что именно я хочу получить, я заранее подготовил данные под наиболее частые способы доступа.
В центре всего находится docID
Makodb практически ничего не знает о самих документах. У каждого документа есть uint64 — docID.
Например:
1 2 3 ... 4000000
Что именно означает 123456, решает приложение. Для базы это просто идентификатор документа. Это довольно важное архитектурное решение. База не пытается понимать, что такое Product, Category, Brand, Price или Name. Она знает, что существует ключ и соответствующие ему данные. Смысл идентификатора появляется уже на уровне индексов:
этот
docIDсоответствует этому условию.
Получается очень простая модель: данные отдельно, а способы быстро найти нужные данные — в индексах.
mmap вместо обычного хранения
Основные данные хранятся в mmap. Условно структура выглядит так:
+----------------------------+ | header | +----------------------------+ | hash buckets | +----------------------------+ | data | | | | key + value | | key + value | | key + value | | ... | +----------------------------+
При чтении не требуется каждый раз собирать объект из базы. Можно получить прямое представление данных в памяти. В частности, у Makodb есть GetZeroAlloc, который возвращает view непосредственно в mmap. Для этой архитектуры это принципиально важно:
если копия не нужна, её не должно быть.
Но mmap сам по себе, конечно, не является магической кнопкой «сделать быстро». У mmap есть собственные компромиссы: page faults, TLB, взаимодействие с файловой системой и ОС, особенности работы с dirty pages и многое другое. В литературе по СУБД mmap неоднократно рассматривается именно как отдельный класс компромиссов, а не как универсальная замена другим механизмам хранения.
Поэтому я использую mmap не потому, что считаю его лучшим способом хранения вообще. Он просто хорошо подходит под мой конкретный workload: преимущественно чтение, предсказуемый доступ, заранее подготовленные индексы и отсутствие необходимости в полноценной транзакционной модели SQL-СУБД.
Шардирование без отдельного оркестратора
Следующая часть архитектуры выглядит немного необычно. Makodb шардирован. Например:
db, err := makodb.OpenSharded( "/path/to/db", 16, 6710886400, 1000, )
В результате получается 16 шардов. Но внутри базы нет отдельного менеджера, который постоянно решает, какой шард сейчас свободен, куда отправить запрос и как потом собрать всё обратно. Есть ключ. Из него вычисляется hash, а из hash определяется соответствующий шард. Условно:
request | hash(key) | +------------+------------+ | | | shard 0 shard 1 ... shard 15
Каждый шард практически представляет собой самостоятельную базу. Поэтому вместо одной глобальной точки синхронизации:
GLOBAL LOCK | +---------+---------+ | | | shard0 shard1 shard2
получается набор независимых блокировок:
shard0 → own lock shard1 → own lock shard2 → own lock ...
Чтение при этом выполняется без lock. Запись блокирует только конкретный шард. И это сделано не ради красивой архитектурной диаграммы. Мне просто не нужен глобальный уровень координации. Если hash уже определяет место хранения ключа, дополнительный менеджер маршрутизации становится ещё одним слоем, который нужно синхронизировать и обслуживать. В данном случае шардирование нужно не только для распределения данных. Оно позволяет естественно распараллеливать работу между независимыми участками хранилища.
Turbo indexes
Самая интересная часть Makodb — turbo indexes. По сути это отсортированные массивы uint64:
[10, 18, 27, 31, 42, 51, 73, ...]
Например, индекс категории может содержать все docID, относящиеся к этой категории. На первый взгляд кажется, что здесь слишком мало структуры. На самом деле именно это и является преимуществом. Два отсортированных массива можно пересечь обычным merge algorithm:
A = [1, 4, 8, 10, 20] B = [2, 4, 8, 15, 20] A ∩ B = [4, 8, 20]
Сложность — O(n + m).
При этом для операции не нужно создавать map[uint64]struct{}, не нужно строить временные объекты и не нужно превращать каждый идентификатор в какую-то более сложную структуру. По сути мы просто двигаем два указателя по двум массивам. Из этого же механизма получаются AND, OR и AND NOT.
Например:
category:phones AND brand:samsung AND sale:true
можно последовательно пересечь три отсортированных массива и получить небольшой список кандидатов. И чем больше исходный dataset, тем важнее становится то, что мы работаем не со всеми четырьмя миллионами товаров, а только с релевантными индексами.
Даже промежуточные массивы не всегда нужны
Здесь возникла ещё одна оптимизация. Мне не хотелось постоянно превращать результаты операций над индексами в обычные []uint64, а потом снова конвертировать их в другой формат. Поэтому в Makodb появились raw turbo operations. Вместо:
mmap []uint64 -> intersection -> []uint64 -> sort -> ...
можно оставаться ближе к исходному бинарному представлению:
mmap -> raw -> intersection -> raw
На одном запросе разница может выглядеть незначительной. Но если операция выполняется миллионы раз, стоимость промежуточных представлений начинает становиться вполне реальным фактором.
Сортировка тоже превращается в индекс
Допустим, пользователь выбирает:
цена ↑
Вместо того чтобы каждый раз выполнять сортировку найденных товаров, у меня заранее существует sort index:
sort:price:asc [docID1, docID2, docID3, ...]
Документы уже находятся в нужном порядке. Если фильтров нет, пагинация становится практически операцией над позицией:
page = 500000 limit = 60
не означает, что нужно пройти первые 500 тысяч страниц. Если индекс уже отсортирован, можно сразу обратиться к нужной позиции. Это одна из причин, почему глубина пагинации сама по себе в таком подходе не обязана становиться дорогой. С фильтрами немного интереснее. Предположим:
category = phones AND brand = samsung ORDER BY price LIMIT 60
Сначала получаем множество кандидатов:
category ∩ brand
Затем используем сортировочный индекс. Для этого существует position index, который позволяет сопоставить docID с его позицией в отсортированном массиве. Получается возможность пройти по уже отсортированному представлению и выбрать только документы, удовлетворяющие условиям.
Для диапазонов используются numeric indexes
С ценой возникает другая задача. Если запрос выглядит так:
5000 <= price <= 10000
нет смысла просматривать все товары. Для этого используется числовой индекс, отсортированный по значению. Сначала бинарным поиском находится начало диапазона:
O(log N)
а затем обрабатывается непосредственно нужная часть:
O(K)
где K — количество элементов в диапазоне. В результате поиск по четырём миллионам товаров не превращается в последовательный проход по четырём миллионам записей.
Я думал, что следующим bottleneck будет база
Чтобы проверить архитектуру, я начал гонять не микробенчмарки отдельных функций, а реальный HTTP workload. Сайт содержит сотни тысяч посадочных страниц и около четырёх миллионов товаров. Нагрузочные сценарии включают разные URL, категории, slug, фильтры, сортировки и пагинацию. На одном из этапов при concurrency 5800 получилось около 2,1 миллиона запросов за 60 секунд при нулевом количестве ошибок и примерно 35 тысяч запросов в секунду. В десятиминутном прогоне было около 19,6 миллиона запросов, также без ошибок, при среднем throughput порядка 32,7 тысячи RPS. При этом CPU был фактически загружен. Но система не разваливалась. Именно тогда я начал искать, что же на самом деле съедает оставшийся CPU. Я ожидал увидеть поиск, индексы, mmap или какую-нибудь неожиданную проблему в базе. Но bottleneck оказался значительно дальше.
Им оказался JSON.
Самая неожиданная часть — JSON
Когда поиск уже выполняется достаточно быстро, остаётся последний этап:
data -> JSON -> HTTP
И оказывается, что преобразование данных в JSON может стоить дороже, чем поиск самих данных. Это особенно неприятно для такой архитектуры, потому что база к этому моменту уже фактически закончила работу. Она нашла нужные docID, получила данные из mmap, выполнила фильтрацию и сортировку. А CPU всё ещё занят. Нужно превратить результат в JSON. Именно поэтому следующим проектом стал SilentJSON.
SilentJSON
Идея SilentJSON довольно близка к общей философии Makodb. Стандартный JSON должен быть универсальным. Он должен работать с огромным количеством типов, структур и способов использования. SilentJSON рассчитан на другой сценарий. Если структура данных известна заранее, зачем каждый раз заново выяснять её устройство? Если тип известен, зачем относиться к нему как к неизвестному интерфейсу? Если данные уже находятся в памяти в подходящем виде, зачем создавать несколько промежуточных представлений? Поэтому SilentJSON старается работать непосредственно с layout структур и минимизировать количество промежуточных объектов. Особенно заметная разница проявилась на parsing/unmarshal. В соответствующих тестах SilentJSON может показывать ускорение вплоть до трёх порядков относительно encoding/json.
Но здесь есть важная оговорка.
Быстрее обработать JSON — не значит автоматически быстрее отдать HTTP-ответ.
Именно это я обнаружил следующим.
Я ускорил JSON — и bottleneck переместился в w.Write
После оптимизации JSON стало особенно интересно посмотреть на полный pipeline. Получилась примерно такая картина:
получение данных -> очень быстро SilentJSON -> очень быстро w.Write(...) -> ???
И выяснилось, что после ускорения сериализации сам w.Write становится заметным ограничителем. Это абсолютно логично, если посмотреть на систему целиком. SilentJSON может существенно сократить стоимость подготовки JSON: меньше промежуточных объектов, меньше копирований, меньше универсальной логики и меньше работы GC. Но после того, как данные уже готовы, они всё равно должны пройти через HTTP stack и попасть к клиенту. Ускорение сериализатора не отменяет стоимость передачи данных. Получается принципиально разный pipeline.
В условно традиционном варианте:
структура -> универсальная обработка -> JSON buffer -> HTTP
В моём варианте:
структура / raw data -> прямая сериализация -> минимум промежуточных данных -> HTTP
Второй путь существенно дешевле именно на этапе обработки данных. Но как только этот этап перестаёт быть доминирующим, начинает проявляться следующий.
Оптимизация не убрала bottleneck. Она его передвинула.
И это, пожалуй, самый интересный результат всего эксперимента. До перехода на SilentJSON pipeline выглядел примерно так:
mmap -> поиск -> JSON -> GC -> Write ↑ bottleneck
После:
mmap -> поиск -> SilentJSON -> Write ↑ bottleneck
На моём workload переход на SilentJSON дал примерно 1,8× прироста общей производительности HTTP-сервиса. Но при этом w.Write никуда не исчез. Наоборот — после того как JSON перестал быть главным ограничителем, следующий этап стал заметнее. И это очень важное различие. Я не просто «ускорил JSON». Я переместил bottleneck дальше по pipeline.
Почему здесь важен GC
Поначалу может показаться, что смысл SilentJSON заключается исключительно в скорости Marshal. На практике это не совсем так. Самый важный выигрыш оказался связан с уменьшением количества промежуточных объектов и аллокаций. Это особенно хорошо сочетается с mmap-архитектурой. Если данные уже существуют в памяти, то цепочка:
mmap -> копия -> object -> interface -> JSON buffer
выглядит довольно странно. Каждый дополнительный объект означает не только время на его создание. Он также увеличивает давление на allocator и GC. Поэтому переход к:
mmap -> raw data -> SilentJSON -> HTTP
даёт эффект не только внутри самого сериализатора. Он меняет общую картину использования CPU. Именно поэтому локальный benchmark одной функции может выглядеть не так впечатляюще, как изменение полного HTTP workload.
Но прямой доступ к памяти не бесплатен
Есть и обратная сторона. Такая оптимизация требует гораздо больше контроля со стороны приложения. Нужно понимать layout данных, offsets, lifetime представлений, работу с буферами и то, где именно возникают копии. То есть я фактически меняю один тип сложности на другой:
меньше аллокаций меньше копирования меньше GC
в обмен на:
больше контроля над памятью больше ответственности за layout больше специализированного кода
Это не магия и не бесплатное ускорение. Просто для конкретного workload такой обмен оказался выгодным.
Что в итоге получилось
Если собрать систему целиком, она выглядит примерно так:
HTTP │ ▼ request parameters │ ▼ ┌─────────────────┐ │ Turbo Index │ └────────┬────────┘ │ candidate docID │ ┌────────────┴────────────┐ │ │ ▼ ▼ Numeric indexes Sort indexes │ │ └────────────┬────────────┘ │ ▼ docID │ ▼ mmap │ ▼ SilentJSON │ ▼ HTTP
А ниже находится шардирование:
key │ hash │ ┌───────────┴───────────┐ ▼ ▼ shard 0 shard N │ │ mmap mmap │ │ index index
Нет глобального shard coordinator. Нет глобального lock на чтение. Нет необходимости собирать всю базу в одну структуру. Нет необходимости каждый запрос превращать в универсальный SQL. И нет необходимости создавать объектную модель товара только для того, чтобы через несколько микросекунд превратить её обратно в JSON.
Что мне дал такой подход
Самое интересное — даже не максимальный RPS. И не отдельные benchmark-цифры. Для меня важнее предсказуемость стоимости операций. Я примерно понимаю, из чего складывается запрос:
Get → O(1) intersection → O(n + m) union → O(n + m) sort pagination без фильтра → O(1) numeric range → O(log N + K)
А затем могу посмотреть на настоящий workload и определить, где проходит реальный предел. Именно это в итоге и оказалось самым полезным. Я долго оптимизировал базу, индексы и доступ к данным, а затем обнаружил, что база уже достаточно быстрая. Следующий предел находился вообще в другом месте. В формировании ответа. А когда оптимизировал формирование ответа, bottleneck снова переместился. Уже в HTTP output.
Поэтому я больше не смотрю на такие системы как на набор функций
Можно сделать поиск невероятно быстрым и всё равно получить медленный HTTP-сервис. Можно сделать JSON-сериализацию невероятно быстрой и всё равно упереться в Write. Можно убрать аллокации и обнаружить, что теперь CPU тратится на совершенно другой участок pipeline. Поэтому сейчас я стараюсь смотреть не на:
«насколько быстро работает эта функция?» а на: «сколько времени занимает путь данных от request до network?» В этом есть довольно простой принцип:
request -> parse -> search -> filter -> sort -> load -> serialize -> write -> network
Если один этап ускорить в десять раз, следующий автоматически становится более заметным. Именно поэтому оптимизация — это не поиск одной «медленной функции». Это последовательное перемещение границы, в которую упирается система.
Makodb не пытается заменить PostgreSQL
Это, пожалуй, стоит подчеркнуть отдельно. Makodb не является попыткой построить универсальную базу данных. Она не предназначена для произвольных JOIN, сложных транзакций, аналитики, большого количества конкурентных записей или универсального query language. Она предназначена для гораздо более узкой задачи:
read-heavy workload с заранее известной моделью доступа и заранее известными индексами.
И именно это позволяет использовать решения, которые в универсальной СУБД выглядели бы довольно странно.
Почему база не знает, что такое Product? Потому что ей это не нужно. Почему индекс — это просто []uint64? Потому что для данной задачи этого достаточно. Почему нет глобального shard coordinator? Потому что hash ключа уже определяет shard. Почему serializer не любит interface{}? Потому что в hot path мне не нужен interface{}.
И, пожалуй, в этом заключается главный вывод
Я начинал с идеи сделать очень быстрое хранилище. Потом выяснилось, что быстрое хранилище — только половина задачи. Можно сделать поиск настолько дешёвым, что он перестанет быть проблемой. Можно сделать индексы настолько простыми, что пересечение миллионов документов превратится в обычный проход по двум массивам. Можно сделать чтение из mmap практически бесплатным с точки зрения аллокаций. А потом обнаружить:
получить данные → 1 ms подготовить ответ → несколько ms отдать ответ → ещё больше
И тогда становится очевидно, что оптимизировать отдельную функцию недостаточно. Нужно смотреть на весь путь данных. От request до network. И каждый раз задавать один и тот же вопрос:
А зачем мы вообще делаем эту операцию?
Если ответ звучит как:
«потому что так принято в универсальном решении»,
то, возможно, именно здесь находится следующий выигрыш.
Что дальше
Сейчас я не рассматриваю Makodb как законченную универсальную СУБД. Следующий серьёзный тест — production. И вот там benchmark уже перестанет быть главным аргументом. Появятся реальные пользователи, реальные распределения запросов, реальные пики нагрузки, реальные ошибки и реальные проблемы с памятью. И это будет намного интереснее любого синтетического теста. Потому что в конечном итоге самый полезный benchmark — не:
«сколько запросов выдержала программа за минуту?» а: «сколько реальной работы она может сделать, не превращая CPU и GC в отдельный вид деятельности?»
Тестовый стенд
Чтобы результаты было проще интерпретировать, вот конкретный стенд, на котором проводились испытания.
Использовалась одна машина с AMD Ryzen 9 7950X3D, 32 GB RAM и NVMe SSD на 4 TB. Makodb была запущена в конфигурации из 16 шардов с начальной ёмкостью mmap около 40 GB. Фактический объём данных составлял примерно 8,7 GB.
В dataset было около 738 тысяч посадочных страниц и порядка четырёх миллионов товаров. Помимо самих данных использовались индексы поиска, фильтрации, категорий и сортировки.
Четыре миллиона товаров, конечно, не означают, что каждый запрос формирует ответ из четырёх миллионов записей. Наоборот, смысл всей архитектуры как раз в том, чтобы через индексы быстро сократить множество кандидатов до небольшого количества docID.
При нагрузочных тестах генератор создавал более 260 GB HTTP-трафика в минуту. Это были не последовательные чтения нескольких гигабайт базы, а многократная обработка HTTP-запросов к одним и тем же данным с различными комбинациями посадочных страниц, категорий, slug, фильтров, сортировок и пагинации.
Поэтому приведённые цифры нельзя воспринимать как универсальный рейтинг Makodb относительно PostgreSQL, Redis или любой другой базы.
Это результаты конкретного workload на конкретной машине и конкретной архитектуры.
Но именно это мне в них и интересно.
Когда структура данных и модель запросов известны заранее, можно убрать огромное количество универсальной инфраструктуры — а затем наконец увидеть, где на самом деле заканчивается производительность системы.
Код
Это не исходный код Makodb, и внутри SilentJSON нет mmap. Но на нём хорошо видна общая идеология проекта: заранее известная структура данных, минимальное количество промежуточных представлений, работа с памятью напрямую и отказ от лишних аллокаций и преобразований.
Именно эта философия используется и внутри Makodb.
Сущности в базе хранятся в JSON-представлении. При этом JSON не используется как механизм поиска. Фильтрация, пересечения, диапазоны и сортировка выполняются отдельными индексами.
JSON нужен преимущественно на границе между хранилищем и приложением.
И, пожалуй, именно поэтому было особенно забавно обнаружить, что после того, как я сделал саму базу достаточно быстрой, JSON внезапно оказался одним из главных bottleneck’ов всей системы.
А после того как я ускорил JSON, bottleneck просто переехал дальше.
В w.Write.
Похоже, это и есть нормальное состояние любой системы, которую действительно начинаешь ускорять:
ты не уничтожаешь bottleneck. Ты заставляешь его каждый раз переезжать в новое место.
