Копирование при записи (Copy-on-write), что это?

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

Традиционные структуры данных изменяемы. Давайте взглянем на простейшее двоичное дерево поиска. Например:

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

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

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

Если копировать всё дерево — это немного странно для вас, то это потому что это так и есть. Обычно два дерева считаются одинаковыми, если у них одна и та же структура. Следовательно, не важно где узлы дерева находятся в памяти. Вы знаете, во многих языках программирования даже нет способа различать две копии одинаковых данных. Помня об этом, мы можем делится кусками структуры, вместо того, чтобы действительно создавать полную копию:

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

В общем, если вы обновляете один узел, то, чтобы иметь изменённую копию дерева, требуется скопировать только часть дерева, начиная от корневого узла до изменяемого узла (копирование пути). И это то, как работает копирование при записи. Та-дам!

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

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

Заметьте, что я предпочитаю говорить копирование при записи (прим. пер: а я переводить, хе-хе), вместо чистые, функциональные (прим. пер: см. чистота функции). Термин функциональные — способ перегрузить и одновременно вызвать негативные эмоции в умах обычных программистов (прим. пер: имеется ввиду в умах не функциональных программистов), которых обычно не интересуют вещи, связанные с функциональным программированием.

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

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

Далее: Как это использовать? (ещё не переведено)