Читал всякие мануалы, пока готовился к паре про время и вот на что наткнулся --^

Немного приятно стало, что даже в манах написано, что MM/DD/YYYY - дурацкий формат

man 3 strptime
link

В этом году, волею судеб, я был научным руководителем двух студентов из ИТМО. Это было мегаинтересное приключение длиной почти в год, которое закончилось две недели назад - ребята получили два заслуженных отла и степень магистра!

Принёс небольшой отчёт о проделанной работе и каплю рефлексии

Что делали

Формальные названия научных работ запарные, но по сути задача была разработать прототип вычислительного узла join с учётом SOTA-решений и граблей, на которые мы в YDB успели понаступать.

Что сделали

Скрафили два алгоритма: HashJoin - побыстрее и GraceHashJoin - помедленнее, но зато с партиционированием и заделом на спиллинг. А также бонусом 3 (три!) хэштаблицы под разные сценарии использования и алгоритм, гибко адаптирующий джоин под входные данные.

Синтетические бенчи показали, что новый join работает в несколько раз быстрее, чем текущие реализации. См. BlockGraceJoin::* на графике.

Да, на реальных данных результаты могут отличаться - встроить код в пайплайн достаточно сложно, а без этого даже TPC-H/DS прогнать не получится, не говоря уже о настоящих запросах.

Но тем не менее! Офигенные результаты для прототипа. Испытываю какую-то невероятную гордость за ребят.

For nerds

Нанотехнологии имплементации
- поддержано блочное (Apache Arrow) представление данных
- фокус сделан на типовые аналитические джоины - в основном фильтрующие, с явным разделением на build/probe стороны
- разработано компактное внутреннее представление (сериализация) и конвертеры, использующие SIMD-инструкции
- гистограммы, которые по первым N мб данных оценивают кардинальность и выбирают стратегию хранения
- используются prefetch-инструкции (если честно, я всегда считал, что их придумали маркетологи, чтобы продавать книжки по проге, но тут разница видна - буду разбираться ещё)
- ну и блум-фильтры офк

Про защиту

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

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

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

Если бы ребята за такую огромную проделанную работу получили бы не отлы - это был бы мегапровал (в первую очередь меня как научника)

Про студентов вообще

Вообще, в этом году я как-то много работал со студентами: в вышке на АКОСе, был стажёр, и вот теперь - магистры.

Удивляюсь, какие студенты нынче жёсткие. Схватывают на лету, замотивированные, да еще и знают кучу всего. Как будто с детства под подушкой прячут TLPI (да я буду везде его упоминать). Пообщаешься немного и сразу хочется тоже что-то крутое замутить!

Что дальше

В планах на полгода у нас разработка полноценного нового production-ready джоина. Мне предстоит полноценно продумать его дизайн, защитить его на внутреннем design review и как-то запрограммировать.

Пока трудно сказать, будут ли использоваться какие-то наработки студентов - всё-таки это прототип, и в нём учитываются не все требования, которые у нас есть. Но если что-то понадобится, то буду пинать ребят, чтобы приносили PRы, и код не пропал.

Постараюсь освещать тут, как движется работа над джоином. Проект обещает много страданий, но и много всего интересного. Про свой прошлый проект - спиллинг в вычислительных узлах, я ничего не писал, хотя там тоже была куча интересных проблем. Надо хотя бы сейчас не продолбаться.
#join

Мэтт Годболт (автор Compiler Explorer) опубликовал интересную статью о том, как проект устроен внутри. Если вы когда-либо смотрели на ассемблерный вывод онлайн, то скорее всего это было именно на https://godbolt.org

Сама статья:
https://xania.org/202506/how-compiler-explorer-works
Гитхаб:
https://github.com/compiler-explorer/compiler-explorer

Compiler Explorer started as a shell script running watch "gcc -S example.cpp -O1 | c++filt | grep -v ..." in a screen session with a vim panel on one side and the script on the other. I was trying to show that C++11 range-based for loops generated identical code to their non-range-based equivalents.

Несколько фактов из поста, которые мне показались интересными:
1. Все компиляторы и библиотеки Compiler Explorer'а занимают 4 ТБ (жесть)
2. Самый популярный язык - C++, на втором месте C
3. В среднем нагрузка - 3 компиляции в секунду (не понимаю, много это или мало)
4. Для сборки под x86 используется около 10 хостов (я думал, что сильно больше)
5. Обслуживание проекта обходится в $3000/мес
6. Всё работает на AWS

Также Годболт пишет, что они используют автоскейлинг и количество хостов автоматически растет под нагрузкой:

We haven’t had a major outage from traffic spikes in years - the auto-scaling just quietly does its job.

А у меня что-то сжимается внутри, когда слышу auto-scaling или serverless…. https://serverlesshorrors.com/

Ну и публичный дашборд со всякими метриками (считаю, что каждый сайт должен такой выкладывать, интересно же!):

https://ce.grafana.net/public-dashboards/326d9aa2606b4efea25f4458a4c3f065?orgId=0&refresh=1m

(на нем, кстати, количество хостов прыгало от 8 до 20 за последние пару дней)

Подготовился к новому учебному году и купил синкпад!

Теперь акос буду вести не с виртуалок, а с честного локального линукса - технолоджияя

Удивительно, но убунта поставилась за 10 минут, причем 5 из них качалась.

Надо бы арч накатить, чтобы студенты сразу поняли, что я жестко крутой. Есть школьники в чате? Подскажите, я успею ко вторнику его поставить и привыкнуть? Или спалюсь, что не выучил все шорткаты i3? Что там вообще сейчас модно в десктопном линуксе?

Там неделю назад стартовал публичный курс от CMU и Энди Павло по разработке баз данных:
https://15445.courses.cs.cmu.edu/fall2025/schedule.html

Они выкладывают видосы, домашки и там даже есть публичный грейдер (но сдавать в него можно только после дедлайна у студентов).

Вообще CMU-шные видосы супертоповые, я их смотрю периодически, сам курс тоже должен быть крутым.
Тем более, если сделать все Project домашки, то в итоге получится самодельная база!

Ну не кайф ли?
Чел сделал "Doom" поверх cedarDB.

https://cedardb.com/blog/doomql/

Хоть мне и кажется не очень честным писать "shooter in pure SQL", когда gameloop написан на баше, а чтение входов на питоне, но тем не менее испытываю сильнейшую радость от прочитанного.

Код вот:
https://github.com/cedardb/DOOMQL/tree/main

P.S. надо бы на ydb что-то такое тоже замутить, а то чем мы хуже

Мучило меня это весь день. В итоге смастерил PoC анимации на кликхаусе.

0 строк питона, 0 строк баша. Только 1 sql запрос и все.

(конечно, это не чистый sql, а с надстройками кх, но для меня это выглядит уже более честным).

В чем catch:

1. Волшебный loop в кх, который возвращает промежуточные результаты:
https://clickhouse.com/docs/sql-reference/table-functions/loop

2. Но! Луп выводит все сгенерированные строки подряд (что ломает анимацию). Однако, если добавить в начало кадра символ очистки экрана и переноса курсора '\x1b[2J', '\x1b[H', то предыдущая запись начинает удаляться и все воркает!

В общем, минус выходные, дум жди

Ааааааааа
Чел запустил веб сервер на дуделке!

https://bogdanthegeek.github.io/blog/projects/vapeserver/

Код:
https://github.com/BogdanTheGeek/semihost-ip

Спасибо @yellalena за ссылку

Смотрел тут свежее выступление Годболта. Он рассказывает про всякие фичи Compiler Explorer - много всего интересного, но удивил меня следующий прикол.

Если написать алгоритм подсчета единичных битов в числе, то компилятор догадается переписать весь этот код просто в одну инструкцию popcnt.

НО!

Загадка:

Если дополнительно указать компилятору, что код нужно собирать именно под skylake, то неожиданно, помимо popcnt dst, src, там появляется еще и xor dst, dst, который выглядит лишним, ведь popcnt не использует dst в вычислениях, а просто кладет туда результат. Зачем же он тогда нужен?

https://godbolt.org/z/hYG7zEs4Y

Разгадка:

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

И в данном семействе процессоров была особенность (баг), которая добавляла лишнюю зависимость к инструкции popcnt.

popcnt dst, src зависела не только от src, но также и от dst. Из-за чего инструкция могла выполняться заметно дольше, потому что ждала фантомную зависимость от dst.

Чтобы эту зависимость уничтожить, уже компилятор вынужден на своей стороне дополнительно что-то предпринимать. По-видимому, самое простое и дешевое - вставить зануление регистра через xor dst, dst, который гарантированно изменит его значение и сломает цепочку зависимостей.

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

P.S.
Меня еще удивило, что на вопрос со сцены "а почему там появился лишний xor", в зале нашелся человек, который корректно на это ответил. Видимо, это какая-то популярная тема и только я как всегда был не в курсе.

Всякие ссылки по теме:

- фикс в clang: https://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160215/332717.html
- фикс в gcc: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62011
- исходный вопрос на stackoverflow: https://stackoverflow.com/questions/25078285/replacing-a-32-bit-loop-counter-with-64-bit-introduces-crazy-performance-deviati
- и еще ответ со списком похожих проблем:
https://stackoverflow.com/a/70649222

Провел пару про кэши во вторник!

https://youtu.be/Qff61KxVCk8

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

Но несмотря на все это пара получилась интересной: с наглядными примерами и я даже не так жестко тупил (только воду пролил)! Да и студенты вопросы задавали и подсказывали)

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

Как это работает:
Возьмем массив чаров размером 256x4096 и будем считать, что в массиве 256 элементов, разделенных дырками по 4096 байт.

Перед чтением удаляем массив из кэша (`_mm_clflush`) и дальше читаем какой-то элемент из 256.

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

Большие дырки в 4096 байт нужны для того, чтобы при чтении одного элемента не загрузились кэшлинии, содержащие другие элементы

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

Поиграть с этим можно вот тут:
https://godbolt.org/z/nYdzYz65P

Данный side channel - часть уязвимости spectre. Исходное описание и код можно прочитать вот тут:

https://spectreattack.com/spectre.pdf

Также другие материалы по теме:
https://www.youtube.com/watch?v=_f7O3IfIR2k
https://www.youtube.com/watch?v=ehNkhmEg0bw
https://habr.com/ru/companies/skbkontur/articles/740564/
https://www.youtube.com/watch?v=bNAPVxvJPds

Каждый год на паре про бинарные уязвимости я позорюсь в одном и том же месте!

Есть вот такой код:

char input[9];
char password[9] = "password";

scanf("%s", input);

if (strcmp(input, password) == 0) {
    printf("Access granted\n");
} else {
    printf("Access denied\n");
}

И из-за особенностей работы scanf в input можно ввести больше символов, чем ожидается, переполнить буффер и перезаписать password так, чтобы проверка ниже проходила.
Например, можно подать 'aaaaaaaa\0aaaaaaaa\0' через echo -e и программа выведет "Access granted".

Так вот, каждый год я в этом месте говорю про стек, переполнение и дальше спрашиваю: "Какой надо подать ввод, чтобы проверка прошла?"

И по какой-то причине студенты всегда говорят '11111111\011111111\0', я без задней мысли это ввожу и программа выдает "Access denied", опровергая все, что я только что рассказывал.

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

А дело в том, что echo -e поддерживает escape-последовательности вида \0NNN, где N - цифра от 0 до 7. Такая последовательность интерпретируется как байт с соответствующим кодом. И поэтому на самом деле вместо 4х байт я ввожу всего 1.

А самое обидное, что \0111 соответствует символу I, и поэтому даже если напечатать эту строку, то получится 11111111I11111! И в панике эту единицу-импостера еще попробуй разгляди!

Сама пара:
https://youtu.be/hHiVtDtJagM

Через buffer overflow обошли пароль, затем через замену return address смогли вызвать произвольную функцию в чужом коде. Ну а потом загрузили на стек произвольный бинарь и заставили его выполняться.

Хотел еще сказать, как этого добиться с выключенным execstack, но не успели (

Всякие интересные ссылки с пары и по теме:
1. Почти тьюринг полный printf: https://www.ioccc.org/2020/carlini/index.html
2. ROP compiler: https://github.com/pakt/ropc
3. Smashing The Stack For Fun And Profit - https://inst.eecs.berkeley.edu/~cs161/fa08/papers/stack_smashing.pdf