Нарушение аксиом при выполнении программы

Делаем новые ошибки

Я работаю инженером-программистом уже около 15 лет. За свою карьеру я многому научился и применил эти знания для проектирования и внедрения (а иногда и поэтапного отказа или оставления как есть) многих распределенных систем. По пути я совершил множество ошибок и продолжаю их совершать. Но поскольку моим главным приоритетом была надежность, я обратился к своему опыту и сообществу, чтобы найти способы минимизировать частоту ошибок. Мой девиз: мы обязательно должны попробовать совершить новые ошибки (менее очевидные, более изощренные). Совершить ошибку – это нормально – именно так мы учимся, повторять – это грустно и обескураживающе.

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

Со скромного начала

Когда мы учимся программировать и делаем первые пробные (или смелые) шаги, мы обычно начинаем с чего-то простого:

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

Мы приобретаем мышечную память, изучаем синтаксис языка и, самое главное, меняем образ мышления и рассуждений. Мы учимся читать код, делать предположения о том, как он исполняется. Мы почти никогда не начинаем с чтения языкового стандарта и внимательно просматриваем его раздел «Модель памяти» — потому что мы еще не готовы полностью оценить и использовать его. Мы практикуем метод проб и ошибок: в наших первых программах мы вносим логические и арифметические ошибки. Эти ошибки учат нас проверять наши предположения: верен ли этот инвариант цикла, можем ли мы таким образом сравнить индекс и длину элемента массива (где вы поместите это -1)? Но если мы не видим каких-то ошибок, то зачастую неявно мы усваиваем какие-то ошибки. инварианты система обеспечивает и обеспечивает нас.

А именно этот:

Строки кода всегда оцениваются в одном и том же порядке (сериализуются).

Этот постулат позволяет нам предположить, что следующие утверждения верны (мы не собираемся их доказывать):

• порядок оценки не меняется между выполнениями
• вызовы функций всегда возвращаются

Математические аксиомы позволяют выводить и строить более крупные структуры на прочной основе. В математике есть евклидова геометрия с постулатами 4+1. Последний говорит:

параллельные прямые остаются параллельными, они не пересекаются и не расходятся

На протяжении тысячелетий математики пытались доказать это и вывести из первых четырех. Оказывается, это невозможно. Мы можем заменить этот постулат о «параллельных линиях» альтернативами и получить различные виды геометрии (а именно, гиперболическую и эллиптическую), которые открывают новые перспективы и оказываются применимыми и полезными. В конце концов, поверхность нашей планеты не плоская, и нам приходится это учитывать, например, в программном обеспечении GPS и маршрутах самолетов.

Необходимость перемен

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

Я вижу два ответа. Во-первых, это производительность . Если мы сможем заставить нашу программу работать вдвое быстрее или аналогичным образом — потребовав половину аппаратного обеспечения — это инженерное достижение. Если, используя тот же объем вычислительных ресурсов, мы сможем переработать 2x (или 3, 4, 5, 10x) данных - это может открыть совершенно новые приложения той же программы. Он может работать на мобильном телефоне в вашем кармане, а не на сервере. Иногда мы можем добиться ускорения, применяя умные алгоритмы или переписывая программу на более производительный язык. Да, это наши первые возможности для изучения. Но у них есть предел. Архитектура почти всегда превосходит реализацию. Закон Мура в последнее время работает не очень хорошо, производительность отдельного процессора растёт медленно, производительность оперативной памяти (в основном по задержке) отстаёт. Поэтому, естественно, инженеры начали искать другие варианты.

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

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

Потоки исполнения

Давайте посмотрим на этот кусок псевдокода:

```

def fetch_coordinates(poi: str) -> Point:

…

def find_pois(center: Point, distance: int) -> List[str]:

…

def get_my_location() -> Point:

…
def fetch_coordinates(p) - Point:
…

def main():

me = get_my_location()

for point in find_pois(me, 500):
loc = fetch_coordinates(point)
sys.stdout.write(f“Name: {point} is at x={loc.x} y={loc.y}”)

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

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

Потоки бывают разных типов: поток POSIX, зеленый поток, сопрограмма, горутина. Детали сильно различаются, но все сводится к тому, что можно реализовать. Если несколько функций могут выполняться одновременно, для каждой необходим свой собственный блок планирования. То есть откуда берется многопоточность, вместо одного мы имеем несколько потоков выполнения. Некоторые среды (MPI) и языки могут создавать потоки неявно, но обычно нам приходится делать это явно, используя `pthread_create` в C, классы модулей `threading` в Python или простой оператор `go` в Go. С некоторыми предосторожностями мы можем заставить один и тот же код выполняться преимущественно параллельно:

 def fetch_coordinates(poi, results, idx) -> None: … results[idx] = poi def main(): me = get_my_location() points = find_pois(me, 500) results = [None] * len(points) # Reserve space for each result threads = [] for i, point in enumerate(find_pois(me, 500)): # i - index for result thr = threading.Thread(target=fetch_coordinates, args=(poi, results, i)) thr.start() threads.append(thr) for thr in threads: thr.wait() for point, result in zip(points, results): sys.stdout.write(f“Name: {poi} is at x={loc.x} y={loc.y}”)

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

Мы намеренно отказались от сериализованного и предсказуемого исполнения. Есть нет биекции между функцией + моментом времени и данными. В каждый момент времени всегда существует одно сопоставление между работающей функцией и ее данными:

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

• критические секции: мьютексы (и спин-блокировки)
• алгоритмы без блокировки (самая простая форма представлена во фрагменте выше)
• инструменты обнаружения расы
• и т. д.

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

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

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

Изобретение процесса

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

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

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

Это еще один режим исполнения, который мы обнаружили, отказавшись от инварианта общей судьбы , отменив совместное использование виртуальной памяти и сделав копию. Копии не бесплатны:

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

Вырваться на свободу

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

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

Назвать несколько:

• Обновления ОС: время от времени нам необходимо перезагружать наши машины

• Аппаратные сбои: они случаются чаще, чем хотелось бы

• Внешние сбои: перебои в подаче электроэнергии и сети — это вещь.

  
  

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

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

Вынос

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

Цель состоит в том, чтобы иметь возможность различать, где мы находимся в данный момент, какие инварианты содержат, и действовать (модифицировать/проектировать) соответствующим образом. Мы выделили основные рассуждения, преобразующие «неизвестные неизвестные» в «известные неизвестные». Не относитесь к этому легкомысленно, это значительный прогресс.