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

Вообще это достаточно метафизическая фраза, которая сработала на меня. Не факт, что работает у других, и историй я слышал много.

Вещи, без которых я не могу жить в рабочем дне:

1. Понятное дело, Google
2. Поиск по коду. Пользуйтесь IDE, пользуйтесь cs.github.com, возможно пользуйтесь copilot. Когда у вас есть API, какая-то мелкая задача, все эти вещи дают быструю скорость просмотра, быстрое обучение мыслительному процессу как устроен тот или иной фреймворк. В один момент вы начинаете понимать от корки до корки как устроены библиотеки, языки, концепты. Примеры, понимание дизайна помогают привыкать. Чем быстрее ваши методы нахождения информации, тем быстрее вы выучите. В какой-то степени IDE даже хуже, потому что кодовая база проекта имеет малую видимость, а поиск по коду гитхаба имеет все репозитории мира.

Пример: я учу https://github.com/3b1b/manim для рисовалки анимаций для математики. Документация не оч, зато тысячи примеров https://github.com/3b1b/videos. Придумал себе задачу, пошел учить, за день учишь прилично, за месяц уже плаваешь в этом. За 3 находишь баги, репортишь, за год пишешь свое (шутка) :)

3. Люди, без них вообще не понимаю как. Мой САМЫЙ сильный рост был, когда я смотрел как мой босс пишет код, ищет информацию, пользуется своими тулзами, фактически скринкаст рабочего дня. Мыслительный процесс профессионала просто невероятно важен. Я всегда с джунами включаю свой экран и показываю как решать их проблемы систематично через тулзы. Постоянно смотрю на других и учусь у них.
4. Понимать тулзы. Я почти уверен, что очень много, кто не знает как работает git, shell, vim, системы сборки и тд. Это безумно глубокие темы, идти смотреть в код, попробовать все команды сильно позволяет расти с точки зрения осознания, а что вообще можно сделать за пару минут.
5. Читать статьи, следить за релизами. Кто-то сделал лучше? Почему вас это останавливает сделать? Принципы/философия/лицензии/бюрократия?

Тулзы, люди и т.д. как раз создают ощущение определенности, когда у вас задачи не получаются. Понятное дело можно ещё тут много говорить про математику, алгоритмы, теорию про P/NP для всяких отрицательных результатов, но такие вещи пригождаются меньше в software engineering.

Помните, что как индустрия Software Engineering существует лет 50 максимум. Мы едва начинаем понимать, что работает, а что нет. Все очень быстро меняется, понимать как решать неопределенность и постоянно учиться позволило мне достаточно быстро вырасти. Возможно это неплохая стратегия, возможно я ошибаюсь.

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

Вот такое мое мнение. Срач не разводите в комментах, пожалуйста. Такие посты всегда вызывают эмоции на такую большую аудиторию. Будьте любопытны (curious), а не осуждающими (judgemental).

Мы тут выложили Protobuf Table-Driven Parser.

Основная идея, что для каждого отдельного типа Protobuf мы генерировали огромный кусок кода, и он рос линейно/супер линейно с количеством полей в протобуфе.

Рост происходил из-за того, что компилятору мы давали код в духе


auto [tag, wire_format] = ReadTag(ptr);
if (tag == kMessageProtoTagNumber) {
ptr = ParseMessage(ptr);
}
if (tag == kIntProtoTagNumber) {
ptr = ParseVarInt32(ptr);
}

И так далее. В итоге был огромный кусок кода и компилятор уставал аллоцировать регистры, делать push, pop регистров при входе/выходе из вложенных функций, компиляция росла. Я писал об этом аж 1.5 года назад https://xn--r1a.website/experimentalchill/95 про аттрибут [[musttail]]. И теперь то самое начало давать свои плоды.

Так как формат фиксированный, мы можем просто брать функцию из значения тега и вызывать её, сохраняя все регистры и заставив компилятор не делать push/pop. 6 параметров регистров мы спрятали PROTOBUF_TC_PARAM_DECL.

#define PROTOBUF_TC_PARAM_DECL \
::proto2::MessageLite *msg, const char *ptr, \
::proto2::internal::ParseContext *ctx, \
::proto2::internal::TcFieldData data, \
const ::proto2::internal::TcParseTableBase *table, uint64_t hasbits

В итоге оно выглядит как

data.read_tag<type>();
data.read_data<type>();
ptr += size_read;
SetField(data.offset(), ptr);
has_bits |= 1 << data.index_idx();
ReadInstruction()
dispatch to next Instruction from table

Пример можно посмотреть здесь.

Плюсы, которые мы получили:

1. Мы сильно уменьшили размер генерируемого кода и время компиляции. Теперь нам нужна только таблица с инструкциями что делать для того или иного поля
2. У нас нет переполнения стека из-за отсутствия push/pop, теперь мы поддерживаем сообщения любой вложенности
3. По перфу нейтрально -- выиграли в push/pop, проиграли в статичности функций
4. Легче понимать профили бинарей, что они парсят на уровне сообщений
5. Только 1 имплементация парсинга на всех
6. Мы сможем менять формат протобуфов даже на ходу

Как мы сможем его менять? Скажем, при типе int32 мы пишем varint. Если число отрицательное, мы пишем 5 байт из-за того, что отрицательные числа наполнены единицами. А что если мы хотим написать его в типе sint32, чтобы писать меньше? В прошлые разы мы генерировали парсинг на основании типа и формата поля, то есть цикл парсинга мог воспринимать тип только строго.

Теперь мы можем писать int32, скажем, как

1. Если положительное, просто в varint
2. Если отрицательное, в отрицательном varint
3. Цикл парсинга всё поймёт, так как привязки к типу нет, и число в память напишется как напишется
4. Мы сэкономили байты и не проиграли в парсинге

Такие оптимизации можно делать даже на ходу -- алгоритм сериализации можно подменить так же.

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

Пройдёт 3-5 лет, и мы сможем так делать по дефолту (build horizon). Пока -- под опцией.

Что ж, подходит мой 14й день постов. Пропустил я два дня, и мне честно было просто тяжело публиковать каждый день. В итоге это вылилось в несколько осознаний:

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

Писать продолжу чуть чаще, чем в старом формате -- полтора-два раза в неделю с такими забегами раз в полгода.

Ну а вот вам интересный факт: если вы отключите L1/L2 префетчеры для кешей, то вероятно для своих серверных или жёстких по памяти процессов вы получите прирост производительности

https://www.reddit.com/r/pcmasterrace/comments/usoko0/disabling_hardware_prefetcher_l1_and_l2_led_to_a/

Почему? Потому что мы все больше упираемся в память, а префетчеры могут ошибаться и занимать вообще место для работы с памятью. Результаты будут скорее всего смешанными, то есть вероятно вы увидите прирост, но некоторые части кода сильно замедлятся. Особенно те, которые работают с большими кусками памяти.

В таких частях кода можно вставить software prefetching с помощью __builtin_prefetch. Скорее всего больше полезной работы будет выполнено, так как в среднем какие-то серверные процессы больше пытаются достать что-то из памяти, чем что-то посчитать. Память не растет по скорости, чем больше вы позволите ей делать то, что нужно, тем будет лучше.

Если вы работаете в HFT и у вас AMD машинки, я думаю, такую тему можно попробовать.

https://twitter.com/jorgbrown/status/1616711913106444289

Это один из моих коллег. Наверное, он лучше всех разбирается в микро и макро компиляторных оптимизациях в мире. Он мне рассказывал про m68k, как важно следить за компилятором и просто я читал много его тредов. В прошлом году он сэкономил несколько миллионов долларов Гуглу. После 18 лет работы его уволили. Вообще никто не понимает, почему.

Я пока остался, но для Европы процесс увольнений в Гугле затянется на несколько месяцев. Что будет, то будет. Но проживать такие события интересно

Донаты

Итак, этот момент настал. Я понял, что пара фондов читающих мой блог заработали несколько миллионов долларов за прошлый год.

В идеале я бы работал только на себя, может, это приблизит меня к этой цели. Без отдачи аудитории сложно вычитывать каждое слово, а с ростом аудитории растёт ответственность. Я верю, что это поможет мне увеличить качество блога в разы и реализовать амбициозные идеи.

Донаты:

https://www.patreon.com/danlark/ -- Patreon
https://boosty.to/danlark -- Patreon, но для русских читателей
https://www.paypal.com/donate/?hosted_button_id=UNZQYV2YP2RBE -- Paypal, если вы хотите остаться незаметным
ETH: 0xDD1b1927dF4533Dcc8975496670228fbC303F941 -- крипта для совсем незаметных

Маленькие суммы позволят получать доступ к постам на 1 день раньше (в итоге качество написанного текста будет расти). Большие донаты дадут возможность проводить регулярные 1:1 (менторство, обучение, консультации) со мной. Рекламы в канале пока ещё долго не будет.

Илья Токарь, мой сокомандник, засветился на Phoronix https://www.phoronix.com/news/LLVM-Google-Light-AVX-Option

Я писал про то, что поддерживать зоопарк железа достаточно трудно и из-за этого сложнее использовать новые инструкции процессоров. После 12 лет (AVX вышел в 2011) на таком разнообразии стало возможным делать шаги в сторону включения AVX по умолчанию, но есть несколько нюансов:

1. Герцовость процессора понижается, если использовать сложные инструкции из AVX/AVX2 на процессорах года до 2016. Для простоты можете считать, что если есть операция умножения или работа с float, то понизится, если нет, то нет
2. Стандартные инструкции вида загрузить/положить в память/сделать shuffle байт не понижают герцовость
3. В компиляторах есть флаги -mavx -mavx2 и так далее, которые не очень учитывают герцовость. В итоге, чтобы таких эффектов не было, можно было только разрешить работать с 16 байтными регистрами xmm семейства
В итоге Илья решил добавить так называемый LightAVX флаг, чтобы можно было использовать 32 байтные инструкции, которые не вредят окружению и не понижают герцовость. Доступно с LLVM 16.

Тем не менее хочу сказать, что просто включение AVX не даст много преимуществ, да, всякие копирования памяти может быть улучшатся, но самые большие ускорения вы скорее всего увидите из-за Bit Manipulation Instruction Set. Они умеют занулять младщий единичный бит, делать операции AND NOT (~x & y) и больше используются компиляторами. Сейчас включить BMI и не включить AVX невозможно, зато станет возможным включить LightAVX и BMI и насладиться большинством ускорений. Такое только подходит для пользователей, кто должен работать с большим разнообразием процессоров -- базы данных, большие cloud компании и тд. Если у вас есть контроль за железом, пользуйтесь всем, чем можно.

1. В ZSTD появился externalMatchfinder, вы теперь можете писать свои алгоритмы компрессии. Для чего?

Очень много запросов от индустрии по ускорению ZSTD, поэтому разные компании хотят построить hardware акселераторы для компрессии. Инженеры из Meta задизайнили решение. На выход вы даёте множество ZSTD_Sequence -- тройки из (litLength, matchLength, offset) -- сколько скопировать "просто так", потом сколько скопировать от уже раскодированного и откуда взять оффсет раскодированного. Далее ZSTD сам уже применит Huffman, FSE.

Полезно, в PR в репозитории не мало упоминаний людей из Intel, что-то явно хотят сделать.

2. Я недавно перечитывал статью про Borg -- система оркестрации в Google и обратил внимание на интересную деталь. Если коротко, когда приходит новое задание, Borg должен посчитать оценку, на какие машины лучше всего его положить. Я задался интересным вопросом, ведь машин сотни тысяч/миллионы, как они избавляются от квадратичного роста. Оказалось, решение достаточно интересное, надо просто смотреть в случайном порядке, и оно само сойдётся:

Relaxed randomization: It is wasteful to calculate feasibility and scores for all the machines in a large cell, so the scheduler examines machines in a random order until it has found “enough” feasible machines to score

Это интересное решение, которое позволяет всякому batch процессингу находить сломанные машины быстрее, не сошлись чексуммы, когда должны несколько раз? Машину на свалку. Из-за случайности больше и быстрее находим.

3. Мы тут недавно списывались с людьми, которые пишут в Rust хештаблицу с открытой адресацией похожую на abseil'овский flat_hash_map, зовут их hashbrown. Нашли интересный момент:

В Abseil мы вычисляем хеши H1, H2, первый хеш для того, чтобы понять куда в таблицу с открытой адресацией положить элемент (по модулю степени двойки), второй для того, чтобы положить в отдельный массив и фильтровать элементы до того, как мы будем их сравнивать. Первому мы даём 57 бит хеша, второму лишь 7, чтобы помещался в один байт и оставался битик, чтобы пометить удалённые или несуществующие элементы.

Интересный момент, а откуда эти 7 бит брать из вычисленного хеша в 64 бита? Мы решили брать нижние 7 бит, потому что хеши на верхних битах иногда ведут себя плохо, не хватает энтропии. В итоге чтобы поддержать таблицу из 2^N элементов, нам достаточно где-то N+7 бит энтропии. В итоге можно считать не 64 битные хеши, а лишь 48, так как хеш таблицы размера 2^40 огромные.

В Rust решили брать старшие 7 бит из 64. Это даёт свои плюсы. Нам в любом случае надо сделать сдвиг (в abseil на 7, в rust на 57). А вот в Abseil нам надо ещё сделать маску на нижние 7, когда как вычисление по модулю для нахождения позиции можно брать без какой либо операции в Rust. В итоге Rust использует на 1 инструкцию меньше, зато им стоит поддерживать, что старшие биты в хеше должны иметь достаточно энтропии.

Такие трейдоффы.

На этой неделе была тьма анонсов про поиски. Вышел новый Bing, в Google анонсировали Bard.

Они интересны и холиварны, поэтому о них я рассказывать не буду, потому что техническая часть там не в моей компетенции :)

А зато мне хочется сильно похвалить команду GitHub за то, что теперь cs.github.com индексирует 45 миллионов репозиториев с 115 млрд файлов.

У обратных индексов по всему, что связано с кодом история достаточно давняя и не сильно заисследованная: Russ Cox рассказывал про то, что обратная индексация по триграмам и токенизация запроса по им работает достаточно хорошо, но на масштабах GitHub они признались, что такой подход работает только до поры до времени. Почему? Потому что мы любим писать всякие циклы через последовательности for ( и поэтому они плохо фильтруют документ, если в запросе есть триграма for. В Google мы рассказывали, что долго использовали суффиксные структуры, но в итоге решили использовать решение о sparse n-grams, которое хорошо заработало, и в статье GitHub упоминается. Немного истории:

Если вы будете использовать 4, 5 граммы, то есть индексировать 4-5 подряд символов в document_id и позицию, то индекс сильно вырастет, поэтому это как-то непрактично, а 2-граммы не сильно хорошо фильтруют. Но хочется добавить и подстроки побольше, чтобы быстрее фильтровать. Чтобы запрос хорошо фильтровал, надо чтобы разбивка n-grams у подстроки запроса была подмножеством разбивки документа (то есть если есть подстрока s в запросе, то любая надстрока S в документе должна иметь n-grams от s), иначе будет некорректный поиск. В итоге придумали схему, которая в среднем увеличивает индекс в пару раз и добавляет приличное количество подстрок бОльшей длины:

На каждую биграму посчитать хэш, поставить на позиции значения хешей. Взять только те подстроки, в которых все значения хешей внутри строго меньше, чем на краях. Так как хеши не зависят от подстрок, свойство о разбивки подстрок выполняется. С другой стороны количество строк увеличится в среднем в константу раз, так как количество подстрок попавших в индекс при переходе с длины n на n+1 уменьшается в среднем в экспоненциальное количество раз. Если аккуратно выписать все выражения, количество строк в индексе будет примерно в 2 раза больше, а по размеру в большую, но удобную константу, когда индексация происходит построчная. Инженерно можно ещё запретить слишком большие n-grams, хорошо пожать с алгоритмом и положить на SSD. В итоге будет индекс GitHub, который хорошо расширяется. Интересные задачи у них скорее всего связаны с метаданными, метаданные на 115млрд растут всё таки линейно, но об этом они ничего не написали :(

В итоге если вы ищете какое-нибудь выражения с очень частой подстрокой типа for (int i = 42, то вы не будете искать пересечения триграм с for, которая находится в каждом файле, а будете искать в том числе какую-нибудь большую подстроку вида i = 42, что встречается реже. В итоге меньше проверок на вхождение, лучше фильтрация. А если вы ищете то, что находится в миллионах документов, скажем, вы просто ввели запрос for, то там не так важно что вернуть, непонятно что вы и хотите, если спрашиваете такое, и документов скорее всего будет много.

В добавочку:

Пригласили на LLVM Code Generation and Optimization Symposium, буду рассказывать с коллегами про то как мы меняли std::sort в LLVM и в Google. Спойлер: у истории есть продолжение, а именно хоть огня и не было, а вот ускорений в проде по сравнению с микробенчмарками мы не увидели

https://llvm.org/devmtg/2023-02-25/

Если мне, конечно, одобрят визу в Канаду к концу февраля :)

SIMDProto

Я убил приличное количество времени думая о проблемах с памятью в последнее время. Одна из них -- можно ли как-то быстрее парсить protobufs. Хочу здесь поделиться, с какими проблемами я столкнулся, и почему это сложнее, чем кажется.

Самая главная проблема, что практически невозможно парсить varints быстро. Попробую дать интуицию:

В JSON вы можете найти символы ", {, }, [, ], : достаточно быстро, они будут в какой-то степени разделителями, показывая где начало и где конец поля. После этого вам надо найти все позиции и на каждый найденный символ найти второй соответствующий, например, на открывающую скобку -- закрывающую. Это зависимость (цепочка) длины 1, остальные байты легко пропускаются, итерации по битам делать не надо.

У протобуфов числа устроены таким образом, что мы должны смотреть на старший бит байта, чтобы понять, какой следующий -- что это продолжение числа или начало нового поля? В итоге, чтобы понять разделители и их индексы, нужно решать достаточно длинные цепочки, и в итоге парсер прыгает как-то по одному-двум байтам. Если хочется выйти из лимита, как 1 cycle на байт для чисел, тегов и тд, нужно уметь обрабатывать varints пачками, притом пачками в том смысле, чтобы varint спокойно могли находиться между других полей, в том числе широкие вектора могут состоять из такого ужаса:

1. [строка][tag][varint][tag][size][строка]

2. [varint][tag][varint][tag][varint]

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

Тем не менее у нас есть кандидаты для парсинга varint с помощью SIMD.

Любые попытки написать даже простой код заканчиваются неудачно. В итоге сейчас SIMDJSON быстрее и популярнее протобуфов. Даже по скорости на 1 бит информации (JSON обычно весит больше, чем прото).

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

О таких вещах хочется писать почти сразу :)

https://github.com/facebook/zstd/pull/3517

Нашли ещё поцарапанные данные в ZSTD. Удивительный факт в том, что этому багу 2 года.

На этот раз никакое тестирование, фаззинг, который 2 года фаззил этот код, не помог. Нашли случайно, а баг ещё одна манифестация Silent Data Corruption. Из хорошего это замечательный кейс для фаззера, почему не нашел, что можно сделать, чтобы фаззинг такое находил хотя бы за недели.

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

Советую обновиться тем, кто использует. Проблемы были в ZSTD level 13-22. decompress(compress) (редко) возвращал другие данные.

C++17 -> C++20

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

От самых страшных до не самых страшных

1. Spaceship operator<=>

Единственная фича, которая уменьшила количество слов в стандарте и добавила головной боли компиляторным инженерам. Сломаться может интересно: если у типа есть implicit оператор вида


struct Int {
int i;
operator bool() const {
// Returns true if not 0, false if 0.
return i;
}
};

Тогда <=> оператор в первую очередь применит оператор меньше к кастуемому типу, в итоге

std::pair{Int{1}, Int{2}} < std::pair{Int{3}, Int{4}}

вернёт 1 в C++17, 0 в C++20.

Достаточно опасно, так как сильно меняет семантику. Как чинить? Писать explicit operator. Пример падения в проде.

2. operator== ambiguity


struct B {};
struct D : B {
bool operator==(const B& other);
};
D d;
bool eq = d == d; // работает в C++17, но не в C++20

На самом деле та же проблема. Бьярне и компания написали целую статью про это тут. Если коротко, то в C++20 написали правила, чтобы операторы == и != вели себя логичным образом, что !(a == b) это a != b. С другой стороны это создаёт проблему в духе


struct S {
friend bool f(S, const S&) { ... }
friend bool f(const S&, S) { ... }
};

bool b = f(S{}, S{});

И в итоге operator== и operator!= считаются одними и те же функциями. Это поломало много проектов, поэтому компиляторы быстро взяли фикс из C++23, и проблем больше нет https://godbolt.org/z/7e4E6qhbM.

3. Всякие проблемы с std::string_view против std::vector<std::string*like> и тд

Конструкция {"a", "b"} вызывает лёгкий ужас, так как в C++20 в string_view добавили конструктор от 2 итераторов и "a" и "b" являются const char* start и const char* end, что очень плохо заканчивается: вы читаете чёрт пойми какую память.

std::vector<std::string_view>{{"a", "b"}}

Теперь создаёт палёный string_view из локации, где "a" -- начало, потом где "b" -- конец, а в C++17 создавало 2 строки. Санитайзеры не ловят. https://gcc.godbolt.org/z/jboa5rbfa. Самое ядро заключается в том, что {"a", "b"} создают не initializer_list, а обычную string_view

Зато можно всякого интересного придумать.

Например, можно добавить в libc++ код в духе


template <int M, int N>
constexpr basic_string_view(char_type (&a)[M], char_type (&b)[N]) : basic_string_view() {
_LIBCPP_ASSERT(&a == &b);
}

И он будет падать в рантайме, в санитайзерах, орать warningами и быть ещё standard compliant. Выстрел в ногу, но всё таки элегантно чинится.

4. Всё остальное кажется достаточно минорным, атомики перестали быть trivially constructible, поэтому их в union не очень стоит класть, добавили слова concept, requires, добавились constexpr контейнеры, поэтому все шаблоны вектора должны быть полными типами. Стали делать std::move на начальное значение в std::accumulate, поэтому функция аккумулирования перестала принимать lvalue references. Aggregates теперь не компилируются, если есть конструкторы. Всё это чинится проходом по всему и достаточно прямолинейно.

Я думаю по сложности C++14 -> C++17 был проще, чем C++17 -> C++20, но тоже со своими интересными решениями, как noexcept как часть типа и тд. Всё равно суммарно набирается работы, хоть и не так много.

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

Google Performance Tips of the Week

Мои коллеги выложили https://abseil.io/fast/. Я очень надеюсь там публиковаться, думаю, один эпизод в следующие месяцы будет под моим авторством.

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

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

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 с иммутабельными цепочками. Чем больше иммутабельности, тем легче нам понимаются перезаписи и тд

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 содержатся в надстроках -- забыли рассказать о деталях), и алгоритмы тоже пригождаются.

Не смогу пройти мимо релиза бывших коллег из яндекса -- YTsaurus

https://github.com/YTsaurus/YTsaurus

https://medium.com/yandex/ytsaurus-exabyte-scale-storage-and-processing-system-is-now-open-source-42e7f5fa5fc6

Наверное, самое удивительное в этом проекте это то, каких людей он привлёк по ходу своей разработки. Команда YT в Яндексе всегда считалась абсолютно звёздной, много карьерных решений я принимал в своей жизни смотря на них. Там и лекторы, у которых я учился теории, и инженеры, смотря на которых писал код. Я всегда себя считал просто никем и дурачком, когда смотрел, что они делают.

Поздравляю, это крутой релиз.

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 не сильно продвинулись из-за этого..

Надо отдохнуть

Я не поспеваю за тем, что происходит сейчас в мире. 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. Я отошёл слегка от дел, но планирую чуть побольше там сидеть.

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

Я приехал с очень мне нужного отпуска. Мы начинаем 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 петафлопс. Цифры не воспринимайте серьезно, это просто прикидка и реальность скорее всего более сложная.