или как уместить Вселенную в iPhone, не привлекая внимания санитаров

Разработчики — люди в целом неплохие, но с одной странностью: когда задача кажется им большой, они добавляют слой. Потом ещё слой. Потом, в три часа ночи, смотрят на то, что получилось, и долго молчат.

https://habr.com/ru/articles/1008806/

Автор проекта «ЭХО» взял и убрал всё лишнее. Без предупреждения, без RFC, без голосования в команде. Остался минимальный Linux, один бинарник на Go и файловая система — всё остальное полетело в мусор вместе с базами данных, фреймворками и «чёрными ящиками» с гарантией на три года. Получилась система на 250 миллионов анкет, которая работает на обычном пользовательском компьютере и не требует звонить в поддержку AWS в два часа ночи.

Но 250 миллионов — это как-то мелко, правда? Давайте замахнёмся на Вселенную. Ну или хотя бы на Млечный Путь для начала.

Вселенная у нас будет, прямо скажем, провинциальная: берём разрешение современного iPhone — 1170 × 2532, почти три миллиона точек, — и объявляем каждую точку галактикой. Заходим внутрь — и там снова такой же экран, только теперь это звёзды. Итого: три миллиона на три миллиона — девять триллионов звёзд. Тридцать шесть Млечных Путей, если считать в привычных единицах.

Тут возникает законный вопрос: а влезет ли вообще наш родной Млечный Путь в iPhone?

Считаем. Если хранить по 20 КБ на звезду — выходит два петабайта. Не влезет ни в iPhone, ни в пару шкафов, ни в большинство дата-центров средней полосы. Но если ограничиться текстом, 255 байт на запись — получается 25 ТБ. Несколько дисков. Небольшой сервер. Вещь, существующая в реальном мире. iPhone на 256 ГБ вмещает около миллиарда записей — примерно 1% Млечного Пути.

Один процент! Это уже звучит как инженерный результат, а не как авантюра.

А дальше начинается самое приятное — ровно то место, которое в романах Ильфа и Петрова называлось «Великий комбинатор задумался». Если нужны все сто процентов, математика даёт неожиданный ответ: сто человек по 256 ГБ. Никаких дата-центров, никаких облаков, никаких счетов. Просто сто человек с телефонами договорились — и поделили галактику. Кому-то достался рукав Ориона, кому-то — шумный центр, кому-то — тихая окраина, где никогда ничего не происходит и очень удобно думать о вечном.

Галактика — это не проблема инфраструктуры. Это вопрос хорошей компании.

Теперь о том, как это устроено внутри — и почему именно так, а не иначе.

В обычных системах сначала создают запись, потом придумывают ей идентификатор, потом строят индекс, чтобы её найти. Затем пишут документацию к индексу. Затем — документацию к документации. Здесь всё наоборот: адрес существует до записи — как почтовый адрес в городе, который ещё не построен, но улицы которого уже расчерчены. Координаты галактики и звезды сразу задают полный путь. Упаковываем их в 64 бита и выдаём пользователю строку вроде EHO-7K3F-91QM-2X — это одновременно ключ доступа, почтовый адрес и карта с крестиком. Никакого реестра реестров.

Каждая галактика — один бинарный файл. Внутри — записи по 256 байт, без заголовков, без метаданных, без поля «для будущей гибкости», которое потом никто не использует, но удалить боятся. Адресное пространство одной галактики: ~3 млн звёзд × 256 байт = 723 МБ. Звучит страшно, но файл разреженный (sparse file) — как и наша Вселенная, где большая часть это пустота, а всё интересное ютится в нескольких процентах пространства. Linux не пишет дыры на диск — только реальные данные. Физики до сих пор спорят, почему Вселенная устроена именно так. Мы не спорим — нам так удобнее. При 1% заполнении галактика занимает на диске ~7 МБ, а не 723.

Но три миллиона файлов в одном каталоге — это уже не Вселенная, это катастрофа. Файловая система начнёт задумываться над каждым запросом, потом задумываться дольше, потом просто задумается и останется так. Автор проекта «ЭХО» решил это изящно — не более 100 000 на уровень иерархии. Берём его идею и раскидываем галактики по «секторам Вселенной» — подкаталогам по первым символам ключа:

galaxies/
  AA/  ← сектор AA, тут спокойно
  AB/  ← сектор AB, тоже тихо
  ...

1296 секторов, в каждом около 2300 галактик. Все довольны, файловая система в том числе.

Внутри файла звёзды лежат не подряд, а по кривой Мортона — она перемешивает биты координат x и y так, что соседи по экрану оказываются соседями и на диске. Без этого диск скакал бы по секторам, как Паниковский через заборы — весело, но медленно. Мортон придумал это в 1966-м. Хорошие идеи не портятся.

Звезда записывается на своё место и именно туда же пишется при обновлении. Пустые звёзды — те, куда ещё никто не заглядывал, — просто дыры в файле, ядро их не трогает. Прочитали по смещению одни нули — здесь никого не было, безжизненное пространство, холодный вакуум. Идём дальше. Прочитали данные — проверяем CRC32. Не сошлось — сразу известно, без гаданий и суеверных постукиваний по корпусу сервера.

Файл галактики создаётся при первом обращении и живёт вечно. Блокировки не нужны: писать в звезду может только тот, у кого есть ключ. Ключ — это GUID, генерируется при создании звезды и выдаётся владельцу один раз. Пространство 2¹²² комбинаций — перебор невозможен даже теоретически, даже если очень хочется. Хранится в записи как Argon2(GUID + координата звезды) — Argon2 специально медленный, чтобы даже при утечке дампа восстановить GUID было нереально. Координата звезды — бесплатная соль, уникальная по определению. Структура записи:

[ 1 байт флаги | 32 байта Argon2 | 219 байт данные | 4 байта CRC32 ]

Флаговый байт решает последний вопрос: что если кто-то читает прямо в момент записи. Бит WRITING установлен пока идёт запись. Увидел его — либо подожди миллисекунду, либо получи сообщение: «вы застали рождение звезды из космического мусора». Вероятность поймать этот момент примерно как увидеть живого динозавра. Потерял GUID — потерял звезду. Никакого «восстановления пароля», никаких вопросов про имя первой кошки.

Когда галактик становится совсем много — префикс ключа определяет узел. Никаких распределённых транзакций, никаких выборов лидера, напоминающих съезд провинциальных чиновников, никаких протоколов консенсуса, от чтения документации к которым у разработчиков немеет левая рука. Файл либо на этом узле — либо на другом. Всё.

А теперь вопрос, который возникает сам собой: как показать всё это хозяйство визуально? Вселенная из девяти триллионов звёзд — штука плохо поддающаяся обозрению, но попробуем.

Карта Вселенной — это картинка 1170×2532, где каждый пиксель это галактика, а яркость пикселя — плотность её заполнения. Пустая галактика — чёрная, живая — светится. Генерируется просто: вместо чтения самих записей вызываем stat() на каждый файл галактики и смотрим сколько места он занимает на диске. Делим на 723 МБ — получаем плотность, красим пиксель. Три миллиона вызовов stat() на NVMe с горячим кэшем занимают 10–30 секунд. Много? Нет — потому что это фоновый процесс, запускается раз в час, пользователь получает готовый PNG. Никаких запросов в реальном времени.

Карта отдельной галактики — то же самое, только внутри: 1170×2532 пикселей, каждый — звезда. Наивный подход — делать seek к каждой записи и читать один байт — займёт почти минуту, это неприемлемо. Правильный подход — читать весь файл галактики последовательно и выбирать нужные байты на лету. 723 МБ на NVMe при скорости 3 ГБ/с — это 240 мс. А если галактика почти пустая, sparse-файл физически занимает ~7 МБ — и карта рисуется за 2–3 мс. Вселенная сама оптимизирует себя пропорционально населённости.

Под нагрузкой это решается тайловым рендерингом — делим карту на куски как в Google Maps, кэшируем каждый тайл отдельно и инвалидируем только тот сектор, в котором что-то изменилось. Большинство тайлов большую часть времени — просто чёрные прямоугольники. Их не надо перерисовывать вообще.

Автор проекта «ЭХО» замахнулся на 250 миллионов анкет. Мы — на девять триллионов звёзд, тридцать шесть Млечных Путей. Там JSON-индекс в памяти — у нас координата и есть адрес, никакого индекса вообще. Там структура папок выстрадана вручную — у нас кривая Мортона сама раскладывает всё по-соседски. Вместо PIN — GUID, который невозможно подобрать даже если очень скучно.

Взяли хорошую идею и довели до состояния, при котором она описывает не капсулу времени для потомков, а буквально всю Вселенную. Скромно, но со вкусом.

Вселенная — это не Big Data. Это просто очень аккуратный файл. Несколько таких файлов, разложенных по секторам, с кривой Мортона внутри и холодным вакуумом там, где ещё никто не побывал.

Рукав Ориона ждёт. Там пока никого нет — мы проверяли, одни нули.

Проект «безЭХО» — потому что автор этих строк чукча не программист, чукча системный аналитик. Кода нет, репозитория нет, pull request не принимаются. Зато архитектура расписана до последнего байта, все дыры в sparse-файле учтены, и тридцать шесть Млечных Путей терпеливо ждут своих звёзд. Если хочется написать реализацию — welcome, координаты известны.