Кодеры за работой. Размышления о ремесле программиста - Сейбел Питер

Вот один из них — в системах с блокировкой этого нет. Я определяю высокоуровневые инварианты: у меня несколько банковских счетов, общая сумма денег на них равна N. Деньги перемещаются со счета на счет. Вот мой инвариант. Любая транзакция предполагает этот инвариант в начале и восстанавливает его в конце. Как вы определяете, что она это делает? Мы смотрим на любую транзакцию вида «Возьмите три из этого места и переместите их вон в то». Инвариант сохранен. Каково мое умозаключение в данном случае? Чисто последовательное. Определив высокоуровневые инварианты, я могу делать последовательные умозаключения о каждой транзакции отдельно.

Сейбел: Поскольку транзакции изолированы друг от друга.

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

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

Пейтон-Джонс: Ну, транзакционную память можно реализовать несколькими способами, и оптимистический параллелизм — лишь один из них. Можно устраивать блокировку по мере продвижения — это уже больше похоже на пессимистический параллелизм.

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

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

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

Последовательная реализация очереди с двухсторонним доступом — это задача, которую проходят в объеме курса бакалавра. Для параллельной реализации с блокировкой по каждому узлу — это тема для научной статьи. Это слишком нелегко, прямо до абсурда. А для транзакционной памяти такую проблему решает студент. Вы просто «заворачиваете» операции «вставить» и «стереть» в одну атомарную операцию — и дело сделано. По-моему, это занятно. Тут есть количественная разница. Сегодня те, кто реализует транзакционную память, должны убедиться, что несколько изменений вносятся в память как единая атомарная операция. Это не так просто — у вас есть только атомарная инструкция «сравнение с обменом». Надо быть внимательным.

Есть проблемы и с зависанием; здесь надо кое-что придумать на уровне логики приложения, чтобы избежать этого. Но потом, реализуя специфичное для приложения решение, вы снова используете транзакционную память. Для такого вида программ это, безусловно, шаг вперед.

Хочу сказать еще кое о чем — мы опять возвращаемся к функциональному программированию. Транзакционная память, конечно, не имеет к нему прямого отношения. Она касается изменения разделяемого состояния — не самой функциональной вещи.

Дело в том, что когда-то я пошел на лекцию Тима Харриса о транзакционной памяти в Java. До этого о транзакционной памяти я вообще не слышал. Тим описывал «атомарные транзакции» и, в общем, больше ничего такого.

Я сказал: «Здорово, но тогда придется протоколировать все побочные эффекты в памяти, все инструкции по загрузке и хранению. А сколько их в Java!» Но в Haskell, благодаря монадам, их почти нет. Загрузка и сохранение в Haskell выражены явно, и программисты считают их важными операциями.

И я подумал, что надо ввести в Haskell все эти атомарные операции, — будет классно. Потом, после лекции, я стал объяснять Тиму, как это можно сделать. Вскоре, поскольку у нас была чистая, элегантная инфраструктура, мы придумали retry и orElse. Механизм retry позволяет осуществлять блокировку внутри транзакции, а orElse — выбор внутри транзакции. Тиму и его коллегам при разработке транзакционной памяти такое не пришло в голову, поскольку они имели дело с довольно сложной средой.

И потому они мало задумывались о блокировке — или предполагали, что блокировка будет атомарной операцией вида «запускать эту транзакцию только при наличии такого-то предиката». Но это очень некомпозиционно. Предположим, вы хотите переложить деньги с одного счета на другой: каковы условия проведения транзакции? Ответ: если на первом счете достаточно денег, а на другом достаточно места, — то есть имеются ограничения на обеих сторонах. Довольно сложное условие. Если задействован и третий счет, все еще сложнее. Все очень некомпозиционно — надо вытаскивать наружу все предусловия методов.

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

Сейбел: То есть эта концепция на самом деле не завязана на Haskell, вы просто смогли ее придумать?

Пейтон-Джонс: Правильно. При той изначальной простоте легче было оценить хорошую идею. Нас все больше раздражало, что нельзя устроить блокировку, не теряя абстракции. Так и получились retry и orElse. Видимо, функциональное программирование лучше всего подходит для этого: изучить какого-нибудь неведомого монстра и затем выпускать в обычный мир. Транзакционная память — прекрасный пример; там было взаимодействие в обоих направлениях. Цикл теперь замкнулся, и, по-моему, это чудесно.

Сейбел: Какие книги по программированию вы бы взяли с собой на необитаемый остров?

Пейтон-Джонс: Обязательно «Programming Pearls» Джона Бентли. По поводу жемчужин: в чудной книге «Beautiful Code»[59] есть глава Брайана Хэйеса «Создание программ для „Книги"». Думаю, под книгой Брайан понимает вечно прекрасную программу. Даны три точки, надо найти, с какой стороны линии между двумя точками окажется третья. Есть решения, которые работают неважно, а потом находится идеальное простое решение.

Еще, конечно же, «The Art of Computer Programming»[60] Дона Кнута. Это не та книга, чтобы читать ее от и до, но одно время я активно ею пользовался. «Purely Functional Data Structures» (Чисто функциональные структуры данных) Криса Окасаки — просто фантастика: нечто вроде курса Артура Нормана, из которого сделана целая книга. Про то, как делать очереди, поисковые таблицы и кучи без всяких побочных эффектов и с хорошими ограничениями алгоритмической сложности. Великолепная книга, читать каждому. К тому же невелика по объему и доступно написана. «Structure and Interpretation of Computer Programs»[61] Абельсона и Сассмана — мне очень понравилось. «Compiling with Continuations» (Компиляция на продолжениях) Эндрю Аппеля — о том, как компилировать функциональную программу, используя стиль передачи продолжений. Тоже превосходная вещь.

Есть одна важная для меня книга, которую я читал мало, — «A Discipline of Programming» Дейкстры. Дейкстра заботится о красоте программ. Его программы полностью императивны, но обладают «свойством Хо-ара»: вместо того чтобы не иметь очевидных ошибок, они совершенно очевидно не имеют ошибок. Он очень хорошо и изящно рассуждает об этом. Я впервые понял, как это — рассуждать о программах, когда тебе невозможно возразить. Наконец, на меня сильно повлияла книга Пера Бринча Хансена о написании параллельных операционных систем. Я постоянно перечитываю ее.