создание снимка сложной изменяемой структуры в параллельной среде

Question

Дано: сложная структура различных вложенных коллекций с разбросанными по разным уровням ссылками.

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

Таким образом, один поток «считыватель» должен прочитать все сложное состояние в одной длинной транзакции.Поток "писатель" тем временем вносит изменения в несколько коротких транзакций.Насколько я понимаю, в таком случае движок STM использует историю ссылок.

Здесь мы имеем некоторые интересные результаты.Например, считыватель достигает некоторого реф через 10 секунд после начала транзакции.Writer изменяет эту ссылку каждые 1 сек.В результате получается 10 значений истории ссылок.Если он превышает предел :max-history для ссылки, транзакция считывателя будет выполняться навсегда .Если оно превышает :min-history, транзакция может быть перезапущена несколько раз.

Но на самом деле читателю нужно только одно значение ref (1-е), а автору - только последнее.Все промежуточные значения в списке истории бесполезны.Есть ли способ избежать такого злоупотребления историей?

Спасибо.

Answer 1

Для меня это немного "дизайнерский запах" - иметь большую структуру с множеством вложенных ссылок.Вы эффективно эмулируете изменяемый граф объектов, , что является плохой идеей, если вы считаете, что Рич Хики принимает параллелизм .

Несколько различных идей, которые стоит попробовать:

• Идиоматическим способом решения этой проблемы в Clojure было бы поместить состояние в единую ссылку верхнего уровня, в которой все внутри него было бы неизменным.Затем читатель может бесплатно сделать снимок всего одновременного состояния (даже без необходимости транзакции).Возможно, будет трудно изменить рефакторинг на то, где вы находитесь в данный момент, но я бы сказал, что это лучшая практика.
• Если вы хотите, чтобы читатель только получил снимок ссылки верхнего уровня, вы можете просто разыменовать егонепосредственно за пределами транзакции.Просто имейте в виду, что ссылки внутри могут продолжать мутировать, поэтому, будет ли это полезно или нет, зависит от требований согласованности, которые вы предъявляете для читателя.
• Вы можете делать все в пределах транзакции (dosync ...)как обычно для читателей и писателей.Вы можете получить конфликты и повторные попытки транзакции, но это может не быть проблемой.
• Вы можете создать функцию «снимка», которая быстро пересекает график и разыменовывает все ссылки внутри транзакции, возвращая результат с ссылками.раздетый (или замененный новыми клонированными ссылками).Считыватель вызывает снимок один раз, а затем продолжает выполнять остальную часть своей работы после того, как снимок завершен.
• Вы можете сделать снимок сразу каждый раз после завершения записи и сохранить его отдельно в атоме.Читатели могут использовать это напрямую (т. Е. Только поток записи напрямую обращается к графу данных в реальном времени)

Answer 2

Что вам нужно, так это современный высокопроизводительный параллелизм. Вы должны посмотреть на работу Натана Бронсона и сотрудничество его лаборатории с Александаром Прокопеком, Филом Багвеллом и командой Scala.

Двоичное дерево: http://ppl.stanford.edu/papers/ppopp207-bronson.pdf https://github.com/nbronson/snaptree/

Хэш-карта на основе массивов http://lampwww.epfl.ch/~prokopec/ctries-snapshot.pdf

Тем не менее, быстрый взгляд на приведенные выше реализации должен убедить вас, что это не территория, на которую вы сами катитесь. Я постараюсь адаптировать готовую параллельную структуру данных к вашим потребностям, если это возможно. Все, с чем я связан, свободно доступно на JVM, но не является родным Clojure как таковым.

Answer 3

Общий ответ на ваш вопрос заключается в том, что вам нужно две вещи:

1. Флаг, указывающий, что система находится в режиме «записи моментального снимка»
2. Очередь для хранения всехтранзакции, которые происходят, когда система находится в режиме моментального снимка

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

Но вы на правильном пути.Если вы в основном переводите систему в «режим записи моментальных снимков», то ваши методы чтения / записи должны автоматически менять место чтения / записи, чтобы поток, который вносит изменения, получал все «текущие значения», а поток, читающийСнимок состояния читает все «значения снимка».Вы можете разделить их на отдельные методы - программа чтения снимков будет использовать методы «значение снимка», а все остальные потоки будут читать методы «текущее значение».

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

Если поток пытается прочитать «значения моментального снимка», когда в данный момент не установлено «состояние моментального снимка», он должен просто ответить «текущими значениями».Не важно.

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

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