об одном баге, программистское

[avva]

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

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

Я поступил так. Во-первых, все же уменьшил размер исходных данных настолько, чтобы эффект все еще всегда происходил и было довольно много примеров его, но, с другой стороны, один запуск всего процесса начал занимать не X времени, а Y времени, где Y намного меньше X. Во-вторых, вставил код, которых в определенные моменты работы процесса берет релевантные внутренние структуры, сериализует их в массив байтов, вычисляет его хэш, и уже только одно это хэш-значение пишет в некие лог-файлы, которые я потом могу проанализировать (эти файлы тоже оказываются огромными, но уже не гигантскими). Это позволило мне сделать два запуска и после этого убедиться, что в такой-то момент работы в них все еще было идентично... здесь тоже... а вот тут уже расхождение; ага, что у нас происходит между "здесь" и "тут"?

После нескольких сеансов такого сужения определился в общих чертах источник бага, и после этого уже просто внимательное изучение чужого для меня кода помогло найти конкретную проблему. Которая заключалась, кстати, в следующем. Определенная структура данных при создании не обнуляла все свои многочисленные поля, кроме одного: поля-сторожа, гарантирующего разумность всех остальных полей, и по умолчанию равного false. Только когда все остальное заполняется разумными данными, а не мусором, в него ставят true. Теперь представьте себе сочетание двух багов: одного, который в определенных редких обстоятельствах не обрабатывал эту структуру вообще, хотя должен был; и другого, который при обращении к структуре на предмет вытащить из нее полезные данные не проверял значение поля-сторожа... вот тебе, бабушка, и недетерминизм.

Что мне не нравится во всем этом - это то, что такие занятия - нахождение сложных багов в слабознакомом мне коде - мне слишком нравится (ну, если код не безобразный, конечно). Я получаю наслаждение от самого процесса быстрого вникания в незнакомый мне код, перемалывания его концепций и допущений у себя в голове, методично-шерлокхолмсовского вычленения того места, где есть проблема, и отбрасывания тех мест, где нет, погони за багом прыжками по болотным кочкам, с отладчиком наперевес (не в этом случае, но вообще говоря). Это дуэль - даже не с самим багом, который в итоге всегда незначителен, а с хитро спрятавшей его суть окружающей реальностью, дуэль с целью заставить ее объяснить, в чем дело. Мне слишком нравится побеждать в этой дуэли - и этот факт мне не нравится; лучше бы я с большим рвением стремился писать нужное новое свое, чем методично анализировать уже существующее. Конечно, преувеличивать проблему тоже не надо - я очень люблю и свое писать, и пишу; да и баг, который я таким образом нашел, вполне мог бы иначе натворить много чего нехорошего. Это вопрос баланса; но существующий баланс меня не очень устраивает, и я намереваюсь его несколько сдвинуть.

Comments

[rasteehead.livejournal.com]

House M.D. не смотрели? :)

[avva.livejournal.com]

Не только смотрел, еще и люблю и как раз недавно 3-й сезон досмотрел, пару дней назад :)

[http://users.livejournal.com/_foreseer/]

А в style guide у вас не рекомендуют все поля инициализировать, получается?

[avva.livejournal.com]

У нас очень хороший style guide, который мне не хотелось бы обсуждать подробно, если Вы не против ;) Не стоит пытаться обобщать на основании одного случая, который я к тому же специально описал довольно туманно, и скрыл/исказил всякие идентифицирующие подробности.

[deadkittten.livejournal.com]

Я в таких случаях всё же предпочитаю гигантские логи, которые потом можно переработать awk-ом...

[avva.livejournal.com]

Понимаете, есть гигантские, а есть гигантские.

[taganay.livejournal.com]

С хешем идея очень понравилась, возьму на вооружение.

[scolar.livejournal.com]

Если бы не любовь именно к этому занятию, Вы были бы либо хорошим учёным, либо плохим программистом.

[saccovanzetti.livejournal.com]

вы забыли про хороших инженеров.

[http://users.livejournal.com/_glav_/]

>После нескольких сеансов такого сужения
Вы несколько раз применяли хэш-функцию к результатам работы хэш функции? экспоненциально уменьшая количество выводимых данных? или к нескольким разным участкам кода применяли её по одному разу за весь тест?

[avva.livejournal.com]

Я использовал наиболее простой и быстрый способ получить ответ на следующий вопрос: "вот место в коде, которое я хочу зафиксировать, и через которое проходят все исходные данные. Как мне получить инвариант всей важной внутренней информации, которой код оперирует на данный момент?"

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

[nine_k]

Про хэши ловко!

Что может быть лучше работы, которая в кайф? :)

[saccovanzetti.livejournal.com]

муки творчества, если получится что-нибудь путное.

[igorlord.livejournal.com]

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

Мне иногда приходилось искать таких жучков в параллельных системах. Там такая штука как "а теперь мы сделаем хэш на всех структурах в памяти" не только "технически сложный процесс" но и очень вероятно может "починить" программку (что обидно). :)

[salas.livejournal.com]

А если от промежуточной синхронизации оно "починится", то, может быть, можно так с этой синхронизацией и оставить? Понятно, что производительность теряется, но на практике часто ли настолько, чтоб баг не становился менее критичным?

P.S. Я параллельных систем не делал, кроме игрушечных, мне просто любопытно.

[sleeping-death.livejournal.com]

познавательно, спасибо :)

[dzz.livejournal.com]

Думаю, с балансом всё нормально, просто сыграл роль элемент новизны - своё, хоть и родное, но до некоторой степени - рутина, чужое - незнакомое и интригующее, особенно, при столь нетривиальном баге ;)

Если посадить тебя в качестве тестера-дебаггера, через пару месяцев отлова блох баланс опять "сместится".

[loislo.livejournal.com]

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

Тема с хешами классная. Но подходящих задач нет. :)

[alta-voce.livejournal.com]

У меня был вопрос, но ты уже ответил.

[nice-beaver.livejournal.com]

Я хотел оставить комментарий, но вы мениа опередили

[slobin.livejournal.com]

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

... То крылом волны касаясь (по техническим причинам) ...

[ivan-gandhi.livejournal.com]

protobuffers нуждаются в радикальном лечении. Это всё такие 90-е...

[azzo27.livejournal.com]

>Что мне не нравится во всем этом - это то, что такие занятия - нахождение сложных багов в слабознакомом мне коде - мне слишком нравится

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

[badenov.livejournal.com]

Что мне не нравится во всем этом - это то, что такие занятия - нахождение сложных багов в слабознакомом мне коде - мне слишком нравится

Элементарно, Ватсон! Рудиментарный охотничий инстинкт. Причем с тех времён когда крупной добычи не было и приходилось довольствоваться насекомыми.
Чего уж там, охота за багами это и есть самый большой фан.

[plakhov.livejournal.com]

Это очень типичная проблема для компьютерных игр, наверное самый страшный из распространенного класса багов - async'и.

Встречается в мультиплеерных играх, построенных по p2p модели, где отдельные инстансы игры пересылают друг другу только команды соответствующих игроков, а в остальном полагаются на детерминизм. Любое нарушение детерминированности (из-за разных политик округления float'ов, например) означает, что дальше они уже играть не смогут.

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

Я, правда, не видел ни одного человека, который мог бы сказать "находить async'и мне слишком нравится". =)

[master-nemo.livejournal.com]

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

[slapsh.livejournal.com]

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

Обычно говорят "недетерминированным" и "недетерминированность, нет?

[comrade-voland.livejournal.com]

Завидую Вам, и полностью подписываюсь под всем сказанным кроме всех ""не нравится"" из последнего абзаца...

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

[sova.livejournal.com]

существующий баланс меня не очень устраивает

А почему? Чем это плохо? Ответь, пожалуйста -- мне это очень интересно и даже несколько важно.

[reader59.livejournal.com]

Хе-хе... модификация классического метода отлова львов в Сахаре.
А в целом - охотничий инстинкт, да...

[e2pii1.livejournal.com]

До хэша я тоже сам догадался.

Интересный вопрос: можно ли было бы избежать этого бага за счёт улучшений в дисциплине программирования и/или более компактного и красивого дезайна ? Или вся сложность там была по делу и такие досадные проколы никак не предотвратить ?

[(Anonymous)]

Это хорощо, ещё что процесс должен был быть детерминистским. А вот, блин, если это моделирование методом Монте Карло, то там по определению данные должны быть немного разными всякий раз. Мне как-то пришлось багу в такой программе. Решение было похожим с той лишь разницей, что вместо посчёта хэшей один раз приходилось делать кучу запусков и смотреть на среднее и дисперсию. Причём отклонение накапливалось постепенно по мере движения от низкоуровневых показателей к более общим. Я уже с опаской поглядывал на конспекты лекций по проверке статистических гипотез 8-\, так как проверки на уровне "ну вроде в среднем одно и то же получается, вроде разница в пределах колебаний" уже было недостаточно. Одно хорошо в таких поисках - после них код понимаешь от и до. Иногда такое чувство что можешь выполнить его в мозгу быстрее чем откомпилировать и запустить.

[avva.livejournal.com]

Ух, круто.

[iliat.livejournal.com]

Круто !
Мы недавно один алгоритм анализа электроенцефаллограм переводили с С на С# с небольшими оптимизациями. Ну и в начале результаты были очень разными. Вставили дампы внутренних состояний во все ключевые точки и постепенно начали выходить на монжество мелких багов (я даже хотел длинный пост написать о проблемах перевода С->С#: разная семантика копирования, выделения памяти, массивов и т.д.). Но данных было не очень много - так что до хэшей не дошли.
Оффтоп: Получил предложение - очень хорошее. Спасибо огромное за помощь!

[shmudder.livejournal.com]

А, кстати, может все-таки напишете пост?

Было бы очень интересно почитать.