Мы тут выложили апдейт по тому, что будет с С++ в Google. В общем, на Rust у нас уже можно писать, Carbon все ещё разрабатывается, а с C++ мы будем включать bounds checks во всех приложениях.

Спойлер: включили bound checks во всяких векторах и строчках, немного CPU скушало, но все в пределах нормы. Были страхи, что встретим запрос смерти, который положит весь прод, пока не встретили, но появилась и у вас возможность уложить весь прод :)

https://security.googleblog.com/2024/10/safer-with-google-advancing-memory.html

Fast Commits в fsync

Я с универских времен изучал fsync, но только на уровне, что этот вызов -- самая последняя инстанция перед тем, как сказать диску, что надо всё на него сбросить. К своему удивлению, спустя несколько лет, я наткнулся на работу коллеги про Fast Commits, которая пытается соптимизировать fsync в EXT4 в Linux уже несколько лет, и, кажется, у этого дела виднеется свет в конце тунеля. Также получили на USENIX ATC 2024 best paper award https://www.usenix.org/conference/atc24/presentation/shirwadkar

fsync в EXT4 работает через алгоритм JBD2 (Journaling Block Device v2), который хранит последние операции работы с диском и применяет их, гарантируя, что всё корректно применится даже в случае отказа машинки. Первый инсайт, который я узнал -- всё это дело происходит раз в 5 секунд и при каждом вызове fsync.

Второй инсайт, что JBD2 хранит минимум 3 блока по 4kb на каждую операцию: блок дескриптора (метаданные о других блоках в коммите), по крайней мере один измененный блок метаданных и блок маркера коммита, указывающий конец коммита. Метаданные о дополнительных блоках нужны в интересных случаях, когда, например, машинка умерла, при загрузке она начнёт восстаналивать данные и потом она во время этого умирает. Идемпотентность можно только гарантировать с помощью сравнения изменений, поэтому JBD2 имеет чуть бОльший оверхед, чем возможно представляют себе люди. Из-за маркера коммита получается, что JBD2 делает минимум 2 операции с диском, что тоже немного неожиданно.

Третий инсайт, что fsync будит свой поток и из-за этого происходит 2 переключения контекста, что тоже стало неожиданностью для меня.

Fast commits представляют возможность избежать минусов упомянутых выше. Например, для идемпотентных операций, которые легче проверяются, например, переименование файла или добавление блоков к файлу можно писать достаточно маленькие куски с метаданными в журнал. В итоге и поток переключать не надо, и одна операция с диском и идемпотентность сохраняется.

Как можно догадаться, даже такая простая идея заняла около 6 лет, чтобы протащить в ядро. Очень много уделялось времени обратной совместимости, а также что делать со сложными операциями, например, filesystem resize, которые обязаны уйти в старый JBD2 и как теперь работать с обоими журналами.

В целом на бенчмарках экономия в 100-200 микросекунд, что для частых fsync собирается в неплохую историю. Для HDD это не такие большие цифры, а вот с развитием SSD это уже значительно. Включить на linux это дело можно через tune2fs -O fast_commit.

Тут с сожалением сообщу, что мейнтейнер RE2, по совместительству мой друг, Paul Wankadia, неожиданно скончался. RE2 используется очень много где, в Google Sheets, антиспаме и где только.

https://github.com/google/re2/issues/502

Мы с ним достаточно поработали и даже успели оказаться в одной команде на два месяца.

Он присылал мне всякие статьи про компрессию и кэширование, а я ему скидывал ужасные баги продакшена, которые он обожал. Он даже сделал внутри Гугла чатик "Production Immaturity" и теперь этот чатик наполнен призрачной пустотой.

Он убедил Jeff Dean откатить его оптимизации и сам смог исправить loading page of Google на 25% в бородатом 2009.

Он взял RE1 от Russ Cox и Ken Thompson и смог 10+ лет поддерживать в новую версию. Мы 2 месяца с ним общались, каким должен быть RE3, но поняли, что пока будет сложно, но этот момент должен был настать ближе, чем нам казалось.

RIP, Legend

GitHub

Re: Junyer · Issue #502 · google/re2

The univsrse is broken and so many people are upset about Junyer passing away at such an early age - he would be mortified at how many people loved him and his work and him being a decent human. He...

Удивительно, не думал, что об этом писали, но мы аж 2 года назад выложили статью про так называемый Flash cache! https://www.usenix.org/conference/atc22/presentation/yang-tzu-wei

Проблема: HDD дешёвый и, в основном, данные лежат на нём, но вот читать часто горячие куски с HDD не хочется. По всему гуглу перед чтением из Colossus (successor to Google File System) стоит SSD cache. Кеш этот большой и автоматический, то есть ничего пользователям не надо делать.

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

Была выбрана LARC стратегия, потому что 60% всех чтений с диска -- одноразовые, а LARC вставлял элемент в кеш только если его читали во второй раз (то есть было два промаха сравнительно недавно). Прожило это дело лет 6, со временем стало недостаточно, потому что если вы прочитали 1000 файлов, а потом ещё раз 1000 файлов быстро, то окажется, что вы очень сильно и быстро нагрузили SSD. Эту проблему пытались полечить SSD Throttler, чтобы писать меньше в короткие промежутки, но такое решение не учитывало разнообразие того, как ведут себя разные клиенты. Кому-то реально надо прочитать два раза, но зато потом не будет никаких промахов. Ещё одна проблема, что LARC всё таки промахивается два раза перед тем, как не промахиваться и в итоге была эвристика, которая оценивала, хорош ли LARC и выключала себя, если промахиваться два раза всё таки было странным. Всё обростало эвристиками и сложностями, и надо было переделывать на что-то более автоматическое.

В итоге решение было многогранным: взять много стратегий по своей жёсткости и оценивать насколько они хорошо работают в режиме реального времени. Учитывать это для принятие решений.

Были выбраны такие стратегии:

NeverAdmit < AdmitOnSecondMiss < AdmitOnMiss < AdmitOnWrite.

То есть никогда не вставлять блоки, вставлять только если промазали 2 раза, вставлять, если промазали (но не совсем как LRU, а с TTL) и вставлять если записали или промазали.

Чтобы понять какие стратегии самые лучшие, решаются задачи о рюкзаке. С данным TTL, статистикой доступа от клиентов и разными стратегиями, стоимостью разных операций (прочитать с HDD и тд), определяется оптимальная стратегия. Раз в какое-то время снова решают такие задачи. Выбирают один TTL с лучшей стратегией.

В результатах получается суммарная стоимость меньше на 6%, более адаптивный подход к SSD кешу и счастливые пользователи.

Внутри этот кеш достаточно известен, потому что находится во всех дэшбордах.

Wikipedia

Adaptive replacement cache

cache management algorithm

1. Не так часто в основной курс алгоритмов и структур данных можно включить новый не очень сложный алгоритм. Его Кнут назвал CVM алгоритмом для подсчёта количества различных элементов в потоке элементов. Действительно очень простой алгоритм https://arxiv.org/pdf/2301.10191 . Кнут написал целую статью про него https://cs.stanford.edu/~knuth/papers/cvm-note.pdf . Удивительно как я всё реже занимающийся такими вещами даже смог осилить доказательство. К сожалению или к счастью он не лучше по оценкам, чем HyperLogLog, но зато не использует никакого хеширования. Из хорошего, я думаю единицы в мире умеют доказывать оценку HyperLogLog, а тут получается, что можно даже доказать что-то за лекцию.

2. Тут вышли очередные бенчмарки хештаблиц. Скажу, что как обычно побенчмаркали какие-то огромные таблицы, которые в реальной жизни не так часты. Может быть для баз данных бывает такое, но для обычной бизнес логики большинство хеш таблиц десятки, максимум сотни элементов. absl::flat_hash_* был задизайнен именно для небольшого количества элементов. Мы кстати тут недавно поддержали Small Object Optimization.

3. Наконец-то std::pair станет тривиально копируемой, если оба элемента тривиально копируемы (правда под флагом другого ABI в libcxx). Не думал, что этот день настанет. Как раз 4 года назад у меня был блог об этом.

4. Блогу практически 5 лет. Я рад, что легаси блога живёт и даже вот вчера он появился на hacker news снова.

Признаться, 5 лет назад совсем другие мысли в голове были. Тогда я был юным, смелым, писал через силу и хотел, чтобы меня заметили. Взросление даёт о себе знать, да и мотивации поменялись.

5 лет назад хотелось делать большие распределенные системы, сейчас хочется заниматься в основном перформансом и обучением людей, так как очень сильно заинтересовали темы как экономика компаний, capacity engineering. В целом оптимизации, идеи, инновации в перформансе сильно хорошо окупаются (особенно в эпоху бесконечных трат на AI). Распутывать клубки, например, откуда пришли те или иные траты интересно как никогда.

Как вы видите, я в блоге всё реже и реже пишу. В целом, честно сказать, у меня не хватает времени и сил писать в текущее время, я буду это делать в своём небыстром темпе и только когда будет о чём-то рассказать. Амбиций на этот блог у меня нет.

LLAMA
Когда вы занимаетесь перформансом, одно из полезных упражнений для проделывания в голове -- анализ скорости света. В простом варианте надо задать себе вопрос "А какой реально лимит сделать то, что делаем мы в библиотеке/программе?".

Очевидный ответ, понятное дело, ноль, лимита нет. Но если подумать, всегда есть некоторые ограничения. Приведём примеры:

Компрессия -- лимит: memcpy. Скопировать данные уж точно надо будет

Хеширование -- проход по массиву, уж точно надо будет все данные прогрузить и сделать хотя бы одну инструкцию с ними

Аллокатор -- хмм, уже не очень понятно

Анализы скорости света выходят всё чаще и чаще, например, теоретические лимиты в математике/алгоритмах и так далее. Они часто оказываются неприменимы, но они действительно могут помочь понять, куда смотреть, находить какие-то эвристики для того, чтобы приблизиться к этому лимиту.

Тут вышла статья с технологией LLAMA (нет, не моделькой от фейсбука и название поста специально привлекает ваше внимание, потому что хайповые вещи я обсуждаю очень редко). А именно Learned Lifetime-Aware Memory Allocator.

https://dl.acm.org/doi/pdf/10.1145/3654642#page=89

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

Статья рассказывает, что если брать полный стектрейс аллокации и запоминать сколько объект поживёт, то с помощью LLM можно предсказывать сколько объект будет жить, и получить намного лучшую упаковку на реальных программах. К сожалению, запуск даже простых LLM и стектрейсов занимает микросекунды, когда TCMalloc возвращает память почти всегда за наносекунды.

Почему стектрейсы?

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

Что делать с перфом?

Ничего, это будет медленнее, но авторы обмазались кешами и всяким таким, потеряв немного качества и переобучаясь, если качество со временем падает заметно.

Из интересного, да, перформанс аллокатора замедлился раза в 3-4, но перформанс всей программы замедлился всего на 12%. Если посчитать, сколько занимает аллокатор, то в целом получается, что решения аллокатора ускоряют всё остальное. Поэтому не надо бояться проводить немного больше в аллокаторе -- его решения влияют на последующие результаты.

Что в итоге?

В статье очень красивые графики, которые показывают как фрагментация уменьшилась, но выводов особо нет. Это достаточно красивый метод как предсказывать и показывать, а где, собственно, лимит и что любые движения в том, чтобы попытаться такой подход заиспользовать.

В целом авторам удалось заметить некоторые эвристики, которые пошли в прод. Без деталей, но если надо, я найду для следующих постов, там долгая история:

We applied insights from this work to Temeraire, in order to make better decisions about when to break up huge pages in this allocator, which led to an estimated 1% throughput improvement across Google’s fleet

В общем, в этом достаточно интересный урок -- не бойтесь делать анализы скоростей света, когда можно потратить больше времени, чтобы найти лучше конфигурацию. Такие эксперименты дают больше понимания, что в идеальной ситуации должно работать.