Experimental chill

Недавно мы потратили несколько дней, чтобы найти memory corruption в C++ коде. Оказалось это была плохая сортировка. В общем, пропозал, который все точно ждали. Давайте проверять в сортировке strict weak ordering на первых X элементов. Про квадратичный алгоритм проверки я уже писал, надо дотащить до конца и для всех. Квадратичный алгоритм находит больше багов, кубический алгоритм даже на 100 элементах будет достаточно дорого обходиться, а вот квадратичный самое то. Сортировки >100 элементов в реальной жизни достаточно редки, чтобы в них поставить баг и не заметить. В общем, можете почитать RFC в LLVM: https://discourse.llvm.org/t/rfc-strict-weak-ordering-checks-in-the-debug-libc/70217

Сегодня прочитал статью по поводу того, что в clang санитайзеры применяются уже после некоторых оптимизаций, которые могут пользоваться неопределенным поведением, то есть вы написали плохой код, потом оптимизатор воспользовался этим, а санитайзер не поймал. Статья направлена на то, чтобы найти эти оптимизации. Результаты получились хорошими, нашли ещё несколько багов, в том числе в OSS-Fuzz. В целом если возможно, запускайте Msan, Asan с -O0 оптимизациями (особенно Msan). Если не получается, может быть хватит у кого-то сил дотащить эту статью до LLVM. Статья милая, читается легко. Назвали такой процесс тоже смешно, Don't LookUB. А вот репозиторий ещё не открыли https://github.com/vusec/LookUB. Наука про санитайзеры все ещё развивается в вероятностные схемы. https://goto.ucsd.edu/~gleissen/papers/dontlookub.pdf Ещё интересная идея пришла в голову, что при всяких хеш таблицах с реальными данными порой не стоит считать хэш функции от всего объекта, для строк может хватить первого/последнего+размер и перехешировать, если видно, что хеш таблица сильно забита. Порисерчу, что вообще есть по этому поводу, иногда прям есть бинари, где хеши проблемные.

libuv наконец-то замержил io_uring, не прошло и нескольких лет https://github.com/libuv/libuv/pull/3952 Вообще я фанат libuv, мне легче в нем пишется код. В Boost.Asio сложнее, скажем, примитивы синхронизации не такие явные, и поэтому часто возникает интеграция непонятных велосипедов. Наверное, из минусов, что libuv задумывался как чистый event loop, а boost.asio как networking asynchronous protocol, поэтому в первом вы увидите всякую работу с диском, а во втором прицепы из SSL, что может быть иногда удобнее. Не то, чтобы я эксперт и сварщик asynchronous protocols, но на субъективное ощущение libuv кажется легче для восприятия. В общем, прогресс едет, вещи становятся получше, рад за libuv и поздравляю их с поддержкой io_uring

Я приехал с очень мне нужного отпуска. Мы начинаем 1 неделю постов каждый день. То, что будет в голове, о том и буду писать. 1. ZSTD 1.5.5 выложили с фиксом нашего corruption и упомянули меня. Мораль на самом деле здесь интересная, потому что мы фаззили в OSS-Fuzz этот код два года и не нашли этот баг. Почему? Потому что все таки фаззинг не магия, я начал писать огромный пост про то, почему фаззинг не работает в таких случаях и скорее всего нашел бы этот баг только за 150-1000 лет. Обновитесь, баг вряд ли задел хоть единого пользователя на миллион, но экзабайты данных тестируют на прочность все. 2. Сортировку в LLVM откатили в 16.0.1, но оставили в Head. С моралью, что пользователи стали репортить проблемы с неправильными компараторами. Поставили немного чеков на это и к LLVM 17 сортировку должны все таки устаканить. Мораль, что такой проект уже занимает два года. Я бы сказал, что это адски медленно, но вот это состояние, когда надо что-то менять на миллиарды пользователей. 3. Я читал тут статью про систему мониторинга Monarch (готовился для моего менти). И это чуть ли не единственная статья, где говорится про скейл Гугла. 144к инстансов, на каждом скорее всего минимум по 4 CPU, можете посчитать, сколько занимает просто мониторинг на 2020 год. А потом сравнить с топ компьютерами мира. Просто забавный факт, не более. Должно получится около 1000 петафлопс. Цифры не воспринимайте серьезно, это просто прикидка и реальность скорее всего более сложная.

Надо отдохнуть Я не поспеваю за тем, что происходит сейчас в мире. LLM что-то меняют, а я как-то не успеваю с ними подружиться, а ощущение, что сейчас ими занимаются чуть ли не все. Что-то интересное вырисовывается, по крайней мере много кто пользуется этой технологией. Я не особый фанат ML, попытка обесценить интеллект происходит, и много интересных вопросов возникает от "Да это всё фигня" до "Кажется все в будущем будут только операторами GPT". Принимать одну точку зрения не хочется и в чате я тоже против heated дискуссий. Возможно просто продолжать свои интересы и встроить это в свои тулзы будет хорошо. Я сейчас уеду в отпуск на 2 недели, без связи, подумать и к чему-то прийти. Пока какой-то дамп, что интересного я надумал (not related to LLMs): 1. То, что я целый год не постил ничего на danlark.org, как-то заставляет меня грустить. За последний год я и правда стал писать с меньшим огнём. Но и если честно, постил я туда порой через кранчи и бессонные ночи. В этом году хотелось спать больше :) 2. По поводу перфа в последнее время хочется больше смотреть в сторону Last Level Cache Misses, так как я уже много писал, что скорость памяти не растёт, значит любые циклы, которые мы простаиваем в памяти, будут только хуже сказываться на всём остальном. Оптимизируя как мы ходим по памяти, ускорим все остальные процессы. Особенно в Cloud environment, когда LLC Miss это отобранная работа у соседа. Сложность с этим -- померить "до" и "после", бенчмарки обычно хорошо прогружены. Такая же история происходит и с branch misses: но тут хотя бы есть интересные решения как cmov инструкции и их семейство. С памятью тяжелее, пробросить новые регистры через SRAM в архитектуру непосильно, надо сидеть и думать как реинжинирить решения. Ещё интересная идея для баз данных: возьмите любой запрос и посмотрите, а сколько write инструкций в память вы делаете? Оказалось, что какой-нибудь ClickHouse проводит 25% из всех циклов работы с памятью в запись при запросе, well, чтения из базы? Что? :) 3. Хочу втаскивать простой ML в оптимизацию конфигов и параметров. Статьи по этому существуют: Machine Learning Framework to Improve Storage System Performance (acm). Самые простые вещи, которые хочется конфигурировать -- размеры кешей, уровни компрессии данных и тд. Руками замучаешься каждый раз это делать. 4. Больше визуализации данных. Осознавая, что человеческий visual cortex очень силён, хочется больше глядеть и понимать код исходя из реальности. Скажем, в flame graphs я бы с радостью смотрел, является ли frame в for цикле, так можно находить всякие квадратичные-кубические алгоритмы. Пока как-то это сложно делать. 5. Как ни странно, в Arm мы всё ещё продолжаем вкладываться, но мой интерес упал, потому что происходит какая-то неинтересная работа -- починено с сотню багов и перф, ну, просто норм. Дальше надо строить процессоры, и это очень сложный процесс по соединению software и hardware. Я отошёл слегка от дел, но планирую чуть побольше там сидеть. Все эти вещи заставляют задуматься над чуть более верхнеуровневым концептом -- какие-то интересные истории вроде делаются, а вроде за последний год слегка меньше огня, больше работы делается "через силу". И даже усталости нет, просто меньше прёт. Попробую подумать в отпуске, что же это такое.

CMake Fuzztest is official Я уломал, и мы будем поддерживать CMake в Google FuzzTest. https://github.com/google/fuzztest/pull/177 Вообще, конечно, про CMake можно много чего говорить, но больше хочется рассказать про то, что в C++ проектах в Google поддерживается только Bazel, потому что он везде и на него не надо тратить силы. А на CMake нужно очень много сил. Я пришёл и сам сделал нам CMakeLists, потому что мне случайные люди стали писать из-за форка, который я сделал и о котором писал в блоге. Теперь можете просто добавить зависимость и писать что-то в духе add_executable(first_fuzz_test first_fuzz_test.cc) # Optional user provided target_link_libraries. link_fuzztest(first_fuzz_test) И всё. Сложнее конфигурации будут в случаях, когда вы сами используйте absl и re2, но тут уже сами разберётесь. Мини дока здесь. Мнеэто понадобилось, потому что я очень сильно хотел в свои sparse_ngrams добавить FUZZ_TEST. Убил полвыходного и добавил CMake в FUZZ_TEST, заодно бонус в гугле отхвачу. sparse_ngrams не сильно продвинулись из-за этого..

Не смогу пройти мимо релиза бывших коллег из яндекса -- YTsaurus https://github.com/YTsaurus/YTsaurus https://medium.com/yandex/ytsaurus-exabyte-scale-storage-and-processing-system-is-now-open-source-42e7f5fa5fc6 Наверное, самое удивительное в этом проекте это то, каких людей он привлёк по ходу своей разработки. Команда YT в Яндексе всегда считалась абсолютно звёздной, много карьерных решений я принимал в своей жизни смотря на них. Там и лекторы, у которых я учился теории, и инженеры, смотря на которых писал код. Я всегда себя считал просто никем и дурачком, когда смотрел, что они делают. Поздравляю, это крутой релиз.

Sparse Ngrams Devlog. Part 1 Следующие несколько постов, дней, недель я буду много постить о сайд проекте, а именно о GitHub Indexing Codesearch, а именно Sparse Ngrams solutions. Мне надоели Russ Cox trigram индекс и Zoekt. Посмотрим куда приведёт: https://github.com/danlark1/sparse_ngrams Основную идею я уже писал в блоге выше, а именно мы должны взять все ngrams, хеши биграм которых на концах больше, чем в середине. Так как хеши не зависят от input, то подстроки будут иметь подмножество такого разбиения. А всего таких ngram не более 2n. Понятно, что при запросе не надо разбивать таким алгоритмом и в статье GitHub сказано, что At query time, we use the exact same algorithm, but keep only the covering ngrams, as the others are redundant. Covering ngrams -- такой же алгоритм, только надо удостовериться, нет никакой подстроки другой в множестве. У меня в тесте для for(int i=42 как раз получается интересная история: всяких ngram много: "for", "or(", "for(", "r(i", "for(i", "(in", "int", "(int", "nt ", "t i", " i=", "t i=", "i=4", "t i=4", "nt i=4", "(int i=4", "=42" А covering ngrams меньше, они более репрезентативны и должны быстрее отвечать на запрос из-за ngram =42 и (int i=4. "for(i", "(int i=4", "=42" Как строятся такие ngrams и coverage? Сначала добавляем все триграмы как мельчайшие единицы. Потом алгоритм в точности является sliding min/max window (LeetCode полезно решать вообще). Когда мы добавляем следующий хеш в стек, надо выкинуть все элементы, которые меньше по хешу из конца. В итоге в первом случае мы когда убираем из стека, мы добавляем этот range ngrams, а во втором случае добавляем все убывающие последовательности. На картинке в статье, к сожалению, ошибка (пропущена "ste"). Covering ngrams в строке "chester " (с пробелом) в этом случае будут "chester ". Потому что пока все значение после девятки меньше девяти, то мы будем добавлять в стек (один раз уберем из стека по ходу, но эту ngram не добавим пока не дойдём до конца), а когда наткнёмся на 7, надо будет всё убрать до начала и в итоге мы найдём очень большую ngram. А для подстроки "chester" (без пробела) covering ngrams будут "che", "hes", "este", "ter". Потому что когда мы дойдём до нулевого хеша, у нас sliding window закончится, и надо обработать хвост. Единственная возрастающая последовательность это "1 2", поэтому добавляем "este", остальное -- обычные триграмы как мельчайшие единицы. Асимптотика -- линейная, потому что добавляем и убираем из стека каждый элемент суммарно не более двух раз. Алгоритм весь получился на 70 строк кода. Понятное дело дальше будет интересно, потому что надо будет доводить до инженерного решения. А там шардирование, большие ngram не нужны, фаззинг, тестирование и тд. 70 строк ещё можно математически доказать, дальше не очень. Мораль: за 70 строк кода написали ядро, нашли ошибку в статье github (не все подстроки имеют разбиение, что все ngrams содержатся в надстроках -- забыли рассказать о деталях), и алгоритмы тоже пригождаются.

Paxos, Raft и тд Моё отношение к консенсусным протоколам менялось. В универе я их понял на уровне, что консенсусы возможны, потом на практике я видел как баги в Paxos/Raft есть и будут всегда, но последние 1-2 года багов стало как-то сильно меньше, и привыкнув к алгоритмам, потихоньку приходит осознание в их детальных различиях, в том числе полученные горьким опытом. Мне захотелось ещё раз прочитать разницу между Paxos и Raft и как они живут вместе с FLP теоремой. Последняя гласит, что детерминированный консенсус невозможен в полностью асинхронной сети, когда сообщения могут не доставляться или доставляться с задержкой. Выбор лидера в Raft может никогда не завершиться, на практике борются с этим с помощью случайных таймаутов. У Paxos два proposer могут никогда не договориться о решении, что тоже на практике лечат случайными таймаутами. Это отличный вопрос на собеседовании, чтобы отсечь тех, кто видит в Raft ответы на все вопросы, о негативных результатах надо тоже знать. По моему мнению на практике самая большая разница в том, что при потере лидера Paxos может медленнее восстанавливаться: 1. Paxos выбирает лидера исходя из id узла, и если он отстает на немного от закоммиченных значений, то ему надо их применить, поэтому если сервер с большим id выигрывает, бывают проблемы и спайки в ожидании запросов. Случайный id не всегда хорошо коррелирует с живностью. На практике в больших системах много работы надо доделать, например, всякие обновления метаданных, и это начинает быть заметно. 2. В Raft узлы с бОльшим количеством закоммиченных чаще выигрывают, но зато у Raft больше шансов получить ситуацию, когда много проголосовали за 2 кандидата и надо переизбрать ещё раз. Вторая ситуация происходит реже, поэтому Raft более практичен. Другое отличие, что так как алгоритмы достаточно сложные для программиста и хотелось бы едва понять любую из статей, происходит следующее 1. Raft и Paxos имплементируются по статьям. 2. В Raft есть проблемы с network partitioning, если узлы видят разные подмножества, может быть бабах (Cloudflare). Подробный разбор и как сконфигурировать etcd и всё сломать можно прочитать в статье. Дальше происходит, что написание нового кода приводит к багам, которые чинятся годами. Тем не менее, ситуация намного улучшилась, в etcd 3.4 добавили Raft Prevotes, чтобы избежать проблем с сетью. Но потом чинить баги всё равно пришлось. Вещи становятся лучше со временем в таких примитивах, это не может не радовать. Самое удивительное в этой индустрии, насколько она наполнена людьми, которые, мол, думают, что поняли консенсус. Из-за того, что консенсусы нетривиальны, редки, я вижу много от людей в виде: "выучи TLA+", "напиши автоматическое доказательство", "а ты слышал про EPaxos, он лучше, чем Paxos". Ребят, мне бы понять первую статью. И не врать себе, что задача просто сложная. Я очевидно во всем не разобрался, но спустя годы оно стало лучше. Поэтому если вам кажется, что вы не можете это понять, дайте себе время. За несколько месяцев и лет, из-за важности свойств, сложность осядет, и вы поймете, что к чему. Читайте потихоньку, пытайтесь понять примитивы, читайте имплементации (хороших много на github), не бойтесь спрашивать. [1] Различия Paxos и Raft [2] Вообще читайте всё, что написано от Heidi Howard, она топ эксперт в мире по консенсусным протоколам [3] etcd network partitioning failure, инцидент от Cloudflare [4] Имплементации Raft [5] Ещё более простое объяснение Raft с иммутабельными цепочками. Чем больше иммутабельности, тем легче нам понимаются перезаписи и тд

Google Performance Tips of the Week Мои коллеги выложили https://abseil.io/fast/. Я очень надеюсь там публиковаться, думаю, один эпизод в следующие месяцы будет под моим авторством. Это похожий на сборник C++ Tips of the Week https://abseil.io/tips/ от Google. Хоть каждую неделю мы не выкладываем эпизоды, но сохранилась традиция часто писать про одну идею, чтобы рассказать что-то интересное и полезное, особенно тем, кто задается вопросом, а можно ли что-то улучшить в их приложениях. Это хорошие, понятные, промодерированные, проверенные временем эпизоды с 6-7 ревью от топ экспертов в Google. Такие моменты мне лично сложно не ценить, почти ни в какой другой компании так открыто говорить о том, что мы увидели на масштабе флота датацентров нельзя.