18 января 2023 г.

Еще один сценарий для waiting time paradox

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

Сейчас по работе пишу небольшую странично-организованную структуру данных. Записи в ней случайного размера – т.е. не выровнены по границам страниц. Если очередная запись не влезает место, оставшееся на текущей странице, то надо либо разделить ее на две страницы, либо полностью перенести на новую страницу, а на старой оставлять padding-record.

Вариант "переносить полностью" – проще, но часть места непроизводительно теряется. Мне захотелось оценить: насколько большая эта потерянная часть? Если средний размер записи X, то сколько, в среднем, на страницу будет теряться на padding-record?

Интуитивно кажется, что в среднем будет теряться половина средней записи, X/2. Но первая же симуляция показала, что больше X/2.

И тут я вспомнил, где такое видел – это же waiting time paradox. Чтобы увидеть аналогию, пришлось немного переформулировать задачу: пусть случайные размеры записей отложены подряд на прямой. Мы тыкаем в случайную точку на этой прямой ("конец страницы"), и спрашиваем: какое, в среднем, расстояние до предыдущей границы записи?

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

(Еще в той задаче нас интересовало время до следующего автобуса, а здесь время от границы предыдущей записи – но это практически ничего не меняет в вычислениях)

Ответ получается тот же: в среднем теряется $$\frac{E[X]}{2}(1+\frac{D[X]}{E[X]^2})$$ – то есть всегда больше половины среднего размера записи. Если распределение размера записи Пуассоновское, то, в среднем, будет теряться ровно средний размер записи на страницу. Для распределений с бОльшей вариацией – и того больше.

11 мая 2022 г.

Mystery of link imbalance #2: как можно починить MRU-пул

Я не удержался, и еще поэкспериментировал с симуляцией link imbalance из предыдущего поста. Там есть вопрос: как эту проблему исправить? Как сделать так, чтобы трафик не собирался на один-единственный канал?

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

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

Однако кажется, что можно сохранить преимущества MRU, но предотвратить link imbalance.

8 мая 2022 г.

Mystery of link imbalance (metastable failure)

Я люблю системы, где из простых элементов возникает какое-то нетривиальное поведение. Последний месяц я игрался с симуляцией одной такой системы из статьи "Metastable Failures in Distributed Systems"1

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

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

30 января 2022 г.

Are You Sure You Want to Use MMAP in Your Database Management System?

Кажется, что отображение файлов в память (mmap) удобно использовать для реализации баз данных, потому что можно не реализовывать пул страниц, а бесплатно использовать всю машинерию виртуальной памяти, уже существующую в ОС – работать с данными как будто они лежат в памяти, и ОС позаботится почти обо всех деталях.

В статье Are You Sure You Want to Use MMAP in Your Database Management System?1 авторы аргументируют, что это удобство – иллюзия. Memory mapped files только выглядят удобно, у них есть неочевидные на первый взгляд недостатки, аккуратный обход которых потребует усилий, сравнимых с самостоятельной реализацией пула страниц.

Самая интересная и неожиданная для меня часть: одним из крупных преимуществ mmap часто называют производительность – отображение файлов в память позволяет уменьшить количество syscalls, и избежать копирования kernel -> user space, и потому должно быть быстрее обычных методов IO.

Авторы показывают, что и это тоже иллюзия: на скоростях современных SSD/NVM и при современных объемах данных пропускная способность чтения данных с диска через отображаемые в память файлы в 2-20 раз уступает пропускной способности прямого чтения в обход файлового кэша. Происходит это потому, что на больших скоростях и больших объемах ОС приходится очень часто загружать и выгружать страницы, и узким местом становится сама машинерия виртуальной памяти – обновление таблицы страниц (page table) и выгрузка страниц на диск (page eviction).

2 ноября 2021 г.

SiliFuzz: Fuzzing CPUs by proxy

Недавно писал про статью инженеров гугла об аппаратных дефектах микропроцессоров (Cores that don't count) Там констатировалось, что такие дефекты есть, и их не так уж мало – но что с этим делать обсуждалось только гипотетически.

SiliFuzz: Fuzzing CPUs by proxy1 – продолжение этой темы. Авторы задались целью создать механизм непрерывного тестирования парка серверов на аппаратные ошибки. Поскольку заранее неизвестно, какие именно аппаратные ошибки искать, то авторы решили положиться на фаззинг.

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

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

10 октября 2021 г.

Тестирование конфигурации: aftermath через 5 лет

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

Я давно уже не касался этой темы, потому что для меня в ней ничего принципиально нового не происходило: написанные тесты продолжали работать, новых тестов мы писали не так уж много, новых проектов, где конфигурацию было бы важно тестировать – не подворачивалось. Но перед уходом в творческий отпуск я почищал хвосты – и рефлексировал над тем, что мы получили в нашем проекте от внедрения тестов конфигурации, через 3-5 лет после их внедрения.

31 августа 2021 г.

Ironies of automation

В 1983 году когнитивный психолог Лизанна Бэйнбридж опубликовала статью "Ironies of automation"1, о человеческом факторе в автоматизации. Статья – одна из наиболее цитируемых в области human-machine systems, о ней даже есть отдельная страница на википедии 2.

Основная идея статьи: автоматизация какой-либо системы – перевод ее с ручного управления на автопилот – часто не улучшает, а ухудшает надежность системы. Это происходит потому, что автопилот не заменяет человека полностью – нестандартные и аварийные ситуации все равно требуют вмешательства живого оператора. Но в штатном режиме автопилот отбирает у людей-операторов возможность набрать опыт управления системой. В нештатной ситуации автопилот передает ответственность человеку, а человек не готов управлять системой в нештатной ситуации, потому что не наработал "чуйку", опыт управления системой в более штатном режиме. В результате – инцидент, авария, катастрофа.

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

15 августа 2021 г.

Примеры зачастую полезнее объяснений

Я тут осознал, что сильно недооценивал роль примеров (examples) для технической документации. Документация очень сильно выигрывает от хороших примеров. Продуманные примеры могут быстро сориентировать читателя – ввести в курс дела, и облегчить понимание более детального описания. Более того, хорошо подобранные примеры способны сходу предоставить читателю (= пользователю) решение конкретной проблемы, без необходимости вообще вникать в детали. Вообще, кажется, есть много сценариев, где наиболее практичная документация == правильно подобранный набор примеров с краткой аннотацией.

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

4 августа 2021 г.

Никто не читает документацию

В комментариях к передыдущему посту я спорил с этим утверждением, но потом порефлексировал над своим собственным опытом, и передумал: нет, и правда, почти никто.

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

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

28 июля 2021 г.

Умение понятно писать – один из самых недооцененных инженерных навыков

Мне кажется, что умение понятно писать – ясно излагать мысли, создавать понятные описания и ясные инструкции, формулировать четкие вопросы и давать полезные ответы – один из самых недоразвитых сейчас навыков среди инженеров. Недоразвитых, и недооцененных.

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

Конечно, есть миллион других навыков, которые не помешали бы инженеру, но я выделяю этот, потому что это low hanging fruit: большинство инженеров уже умеют думать, и уже хорошо разбираются в предмете. Не хватает, по-моему, малого – немного научиться думать о читателе.

20 июля 2021 г.

What makes a rule complex (for brain): mechanical sympathy applied to humans

Интересная статья 2020 года: "What makes a rule complex?". Что делает правило (алгоритм) сложным для выполнения человеческим мозгом?1

Мы часто оцениваем стоимость выполнения алгоритма: на какой-то абстрактной машине, или на реальном железе (конечном автомате, машине Тьюринга, Intel Core i7…). А что насчет человеческого мозга? Если смотреть на мозг как вычислительную машину, и скармливать ему разные "программы" – описания алгоритмов на человеческом языке – то насколько "дорого" для мозга будет выполнить действия соответственно описанию? Как цена выполнения алгоритма мозгом будет зависеть от устройства алгоритма?

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

14 июня 2021 г.

Cores that don't count: "тихие" производственные дефекты процессоров

TL;DR: Инженеры гугла утверждают, что примерно 0.1% современных процессоров содержат дефекты, ускользнувшие от техконтроля производителя, из-за чего некоторые инструкции на таких процессорах втихую дают неправильный результат. Вероятно, доля таких производственных дефектов будет расти. Вероятно, пора отвыкать думать о процессоре как об идеальном вычислителе, и искать способы создавать такие программные системы, которые обнаруживают и компенсируют ошибки CPU.

В твиттере проскочил очень интересный доклад Питера Хошчилда (Peter H. Hochschild) из гугл на конференции HotOS 20211

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

24 мая 2021 г.

Когда имеет смысл передавать IO в отдельный поток?

Допустим, у нас есть простая система, которая принимает запросы из сети, как-то их обрабатывает ("бизнес-логика"), и отправляет результат назад, в сеть. Мы заинтересованы в быстром отклике (=latency), а отправка – это IO, так что возникает идея ее снести в отдельный поток.

Но тогда придется передавать данные из основного потока в поток отправки – а межпоточная коммуникация это какие-то накладные расходы (копирование, инструкции синхронизации, т.п.)

Стоит ли вообще игра свеч, и если стоит – то когда?

27 марта 2021 г.

Рабочие заметки в помощь мозгу

Давно уже хотел написать об этом, но только сейчас дошли руки:

Комрады! Пишите рабочие заметки – о чем вы думаете, над чем работаете – особенно если думаете о чем-то достаточно сложном. Это очень, очень, очень помогает думать! (И не только думать)

Вот уже несколько лет я практически все рабочие и личные задачи обсуждаю с большим файлом notes.txt (notes.org). Этот файл решает сразу несколько задач:

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

9 августа 2020 г.

Queueing theory for fun and practice #3: системы с потерями

Начальник отдела челобитных Апполинарий Матвеевич любит порядок, поэтому просители могут ожидать его внимания только смиренно сидя в приемной, а не толкаясь возле дверей присутственного места – оттуда их гоняет казак Семен.

Какова должна быть посадочная вместимость приемной, чтобы не более 1 просителя в день ушло не солоно хлебавши, если пропускная способность Апполинария Матвеевича не более дюжины челобитных в день, а входящий поток около 10 челобитных в день?

TL;DR: реальные системы обрабатывают не все задачи – часть задач теряется или отбрасывается за счет ограниченности буферов и/или таймаутов. Потери делают систему устойчивой к перегрузке, и улучшают качество обслуживания тех задач, что дожидаются обработки – теряются более вероятно именно те задачи, которым пришлось бы ждать дольше всех. Системы с потерями – добро, делайте его больше.

(часть 3, предыдущая часть: нагрузка и время отклика)

Я уже упоминал, что система с бесконечной очередью, загруженная на 100%, будет давать неограниченное время ожидания. Однако на практике этого не происходит: есть немало систем, пропускная способность которых планировалась по максимуму, без запаса емкости – и которые, при этом, вполне приемлемо работают.

Почему? Конечно, может быть в оценку трафика затесалась ошибка, и система на самом деле имеет запас емкости. Другое возможное объяснение: в системе есть потери – она обрабатывает не всех клиентов. Часть клиентов не добирается до кассира, часть задач не добирается до сервера.

Два самых очевидных механизма потерь: либо очередь ограничена, и задачи теряются, когда она переполнена, либо задачи сами имеют какой-то внутренний TTL, и "уходят" из очереди, когда он превышен.

27 июля 2020 г.

Queueing theory for fun and practice #2: нагрузка и время отклика

Во храме Божьей Матери Поклонской батюшка Иннокентий принимает исповедь у раба божьего обыкновенно минут за 10, а утешения жаждут около 5-и рабов божьих в час. Много ли стульев надобно поставить во храме, дабы исповеди ожидающие не толпились в праздности пред святым алтарем?

"Массовое окормление паствы: пособие для начинающих" (редакция 3-я, неизданная)

(Часть 2, начало: ТМО, square root staffing, Little)

Как зависит время отклика от нагрузки на систему (утилизации)? Для многих систем измерения дадут что-то вроде такой картинки:

Такую кривую зависимости среднего времени отклика от нагрузки за характерную форму часто называют J-curve. Конечно, не обязательно кривая в конкретной системе будет выглядеть точно так – например, могут присутствовать ступеньки, соответствующие разным механизмам, которые ответственны за время отклика – но в среднем такая кривая свойственна многим системам, и приводит к ней как раз наличие внутренних очередей/буферов.