Недавно тут сидел на нескольких защитах дипломных работ на Факультете Компьютерных Наук ВШЭ. Это занятие жутко неблагодарное, очень устаёшь всех слушать 4 часа, а ещё недавно мой организм дал мне понять, что я всего лишь кожаный мешок, и оно совсем не помогло его восстановлению. Тем не менее, были хорошие работы, которые понравились мне, и студенты разрешили о них поделиться:

1. Ковальков Дмитрий. Текст работы недоступен, Дмитрий не захотел публиковать текст из-за причин оформления :)

Тема: Исследование существующих решений консенсуса на устойчивость к отказам в fsync

Это отличное исследование и эксперименты со статьей 2020 года "Can Applications Recover from fsync Failures?", которая смотрела на падения систем, если вдруг не смог сработать fsync, когда ядру говорят, что пора данные на диск сбрасывать, а тот не смог принять это. И если система неправильно обрабатывает такие падения, то возможны серьёзные последствия.

Последствия: ломается leader election в Zookeeper. Дмитрий провёл исследование c помощью CuttleFS, написал патч к Zookeeper и выложил скрипты на github. Учитывая, что даже Jepsen не смог найти такие падения, я думаю, что при желании Дмитрий может превратить своё исследование в полноценный фреймворк. При защите у меня было ощущение, что Дмитрий как будто сам не осознал, какой у этого потенциал, поэтому говорю — огромный :)

2-3. Хасанова Алия. Родионов Антон.

Темы: хоть были их две, то я опишу их суммарно Анализ использования полей протобуфа

Так как я был руководитель этих дипломов, то немного предыстории. У меня давно в голове крутилась идея, что fault tolerance можно использовать как способ агрессивных оптимизаций. А именно если есть какой-нибудь MapReduce, то jobs/workers должны быть устойчивы к падениям и это нормальный ход вещей. А что если мы попытаемся оптимизировать достаточно агрессивно и поймём походу если надо, что были слишком агрессивны и просто перезапустим в более безопасном режиме? Пользователь не заметит и если мы обеспечим хороший rate успеха, то и ресурсы сэкономим.

В Гугле и Яндексе протобуфы читаются везде и всегда в таких сервисах, и если читаются протобуфы, а используются один-два поля, то много информации просто уходит в никуда. Так как протобуфы статические, то есть два подхода: анализировать сам код или трекать динамически. Алия делала первое, а Антон второе.

В первом подходе мы помечали все getters протобуфа специальными метками и удаляли их с помощью garbage collector в линкере, а во втором писали плагин, чтобы собирать всю информацию по ходу исполнения. Получался профиль, а что делать с этим профилем — решать уже пользователям, кто захочет перекомпилировать без этих полей, а кто напишет свой парсер и будет парсить только часть. В MapReduce можно падать, если прочитали поле, которое не в профиле и обновлять профиль.

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

Я в итоге сделал свою версию и протолкнул до open source, но, думаю, ещё десять раз поменяем интерфейс https://github.com/protocolbuffers/protobuf/blob/master/src/google/protobuf/field_access_listener.h. Заработает ли идея с агрессивностью, не знаю, надеюсь, что да, но интуиция говорит, что это очень тяжело.



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

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

К сожалению, сейчас в С++ нет максимально быстрого способа поджойнить строки, чтобы не платить оверхеда. И по-моему сейчас нет ни в одном языке библиотечной поддержки так делать:

Одни скажут, что можно сделать reserve и сделать append, но тогда append будет каждый раз проверять на то, нужно ли расширять буффер, будет добавлять нулевой байтик в конец, потому что строки в С++ заканчиваются нулевым байтом и будут обновлять размер:

std::string GeneratePattern(const std::string& pattern, size_t count) {
   std::string ret;
   ret.reserve(pattern.size() * count);
   for (size_t i = 0; i < count; i++) {
     // SUB-OPTIMAL:
     // * Writes 'count' nulls
     // * Updates size and checks for potential resize 'count' times
     ret.append(pattern);
   }
   return ret;
}

Другие скажут, что можно сделать resize и потом memcpy, но, к сожалению, resize должен как-то проинициализировать память, поэтому будет лишний memset:

std::string GeneratePattern(const std::string& pattern, size_t count) {
   std::string ret;
   const auto step = pattern.size();
   // SUB-OPTIMAL: We memset step*count bytes
   // only to overwrite them.
   ret.resize(step * count);
   for (size_t i = 0; i < count; i++) {
     // GOOD: No bookkeeping
     memcpy(ret.data() + i * step, pattern.data(), step);
   }
   return ret;
}

В итоге стандартные библиотеки имеют незадокументированную функцию __resize_default_init, которая просто аллоцирует сырые неинициализированные байты, в которые можно копировать. Abseil это использует для Join строк, а вот в Яндексе делается reserve и добавляется appendом. Тут винить некого, так просто получилось, что интерфейс "выделить сырую память и проинициализировать тем, чем надо" сложно выражется через обычные примитивы строк.

В C++ на этой неделе, надеюсь, примут в C++23 resize_default_init, который исправляет эту проблему. Синтаксис получается функциональный немного, вызывается callback, который должен заполнять байты выделенной строки, чтобы ни в какой момент времени не оставлять строку неинициализированной, возвращаемое значение отвечает за столько байт, сколько останется в строке в итоге.

ret.resize_default_init(step * count, [&](char* buf, size_t n) {
     for (size_t i = 0; i < count; i++) {
       // GOOD: No bookkeeping
       memcpy(buf + i * step, pattern.data(), step);
     }
     return step * count; // must be <=n, in that case ==n.
 });

[1] P1072 пропозал для стандарта
[2] Abseil resize uninitialized
[3] Abseil join
[4] Yandex join
[5] __resize_default_init в LLVM