Haskell: TVar: предотвращение голодания

Я рассматриваю возможность использования TVar для хранения некоторого состояния в веб-приложении (которое можно воссоздать при перезапуске). Однако меня беспокоят спорные аспекты TVar. Кажется, что частая короткая транзакция может привести к истощению более длинных транзакций, постоянно прерывая их. Кроме того, поскольку более длительные транзакции продолжают перезапускаться, это увеличивает нагрузку на ЦП, что приводит к дальнейшему увеличению продолжительности этих транзакций. В конце концов я чувствую, что это может привести к тому, что сервер полностью перестанет отвечать на запросы.

В связи с этим у меня такие вопросы:

(1) Может ли TVar (или другой тип данных) использовать блокировки, а не одновременные попытки/повторные попытки.

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


concurrency haskell ghc stm tvar
person Clinton    schedule 11.04.2012    source источник
comment
Примечание retry не перезапускает транзакцию немедленно; транзакции повторяются только тогда, когда используемые ими TVar изменены.   -  person ehird    schedule 11.04.2012
comment
@ehird: Разве транзакции не повторяют автоматически немедленно, если другая транзакция записывает в TVar, который они ранее читали (даже без вызова retry)?   -  person Clinton    schedule 11.04.2012
comment
@Clinton: Да, они повторяют попытку, но только после того, как система выполнения обнаружит возможность другого результата транзакции. т.е. он ждет, пока один из TVars не прочитает, прежде чем повторная попытка изменится. Что превращает занятое ожидание в схему push-уведомлений.   -  person jmg    schedule 11.04.2012
comment
@jmg: Если другая транзакция записывает в прочитанный TVar, не повторяется ли она немедленно (поскольку TVar изменился)?   -  person Clinton    schedule 11.04.2012
comment
@Clinton: Но только если другая транзакция записала в такой TVar. В противном случае он ждет, пока это не произойдет. И я думаю, что транзакция перезапускается после завершения другой. Иначе сразу возник бы конфликт.   -  person jmg    schedule 11.04.2012
comment
@jmg: Но только если другая транзакция записывалась в такой TVar. Это моя точка зрения. Это было бы тривиально, если бы были только транзакции чтения и транзакции записи без конкуренции. Плохое поведение возникает, когда к одному TVar применяется много транзакций. По мере увеличения конкуренции увеличивается нагрузка на ЦП, что еще больше увеличивает конкуренцию. Кроме того, переменная должна использоваться только в 1% случаев, чтобы возникла эта проблема, если доступ к переменной осуществляется в течение 0,0001 секунды каждые 0,01 секунды, транзакция длиной 0,1 секунды (которая должна читать, выполнять некоторую обработку и запись) никогда не завершится.   -  person Clinton    schedule 11.04.2012
comment
@Clinton: Livelock всегда вызывает беспокойство (но редко является реальной проблемой), но стратегии предотвращения очень конкретны. Вам нужно будет указать, какие транзакции вы собираетесь выполнять с какими ограничениями, прежде чем можно будет дать эффективный ответ.   -  person sclv    schedule 20.05.2012

Ответы (3)


arrow_upward
3
arrow_downward

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

Если вас это действительно беспокоит, рассмотрите возможность использования флага TVar. Установите его в false и проверяйте, что это false в начале каждой дешевой транзакции, вызывая retry в противном случае. Затем просто установите для него значение true перед входом в длительную транзакцию и установите значение false при выходе. В качестве альтернативы вы можете просто защитить свое состояние за TMVar. Ваше длительное вычисление берет tmvar атомарно, делает то, что кажется, а затем возвращает его. Остальные транзакции происходят полностью в рамках одной фактической транзакции STM.

Помните также, что длительная транзакция STM — это своего рода хитрый зверь. Из-за лени можно дешево вложить дорогое значение в var. Вы также можете очень быстро прочитать «моментальный снимок» данных из целой группы переменных. Чтобы иметь действительно длительную транзакцию, вам нужно прочитать целую кучу переменных, а затем на основе того, что вы прочитали, вычислить, в какие переменные вы собираетесь записывать новые значения (или читать значения from), и само вычисление должно быть дорогим. Так что, скорее всего, вы даже не в этом сценарии с самого начала!

person sclv    schedule 19.05.2012

arrow_upward
5
arrow_downward

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

Конечно, голодание может привести к значительному снижению производительности, но только при условии, что такие большие транзакции действительно необходимы. Один принцип проектирования, который я стараюсь учитывать, заключается в использовании TVars на низком уровне детализации. Например, вместо помещения всего Data.Map в TVar, что может вызвать разногласия при каждом обновлении записи, вы можете использовать более удобную для STM структуру данных, такую ​​как списки пропуска [1].

[1] http://hackage.haskell.org/package/tskiplist

person Peter    schedule 11.04.2012
comment
Я действительно не понимаю, как STM менее подвержен ошибкам. Разве частые короткие транзакции не устанавливают блокировку, которая никогда не снимается для более длительных транзакций? Разве это не более подвержено ошибкам, чем в системе на основе блокировки, по крайней мере, в какой-то момент более длительная транзакция захватит блокировку и завершится? STM, по-видимому, заставляет программиста следить за тем, чтобы их самая продолжительная транзакция занимала меньше времени, чем самый длинный промежуток между транзакциями. Хотя, возможно, я что-то здесь упускаю. - person Clinton; 11.04.2012
comment
Если я правильно понимаю, в системе блокировки, если транзакция в данный момент выполняется, другая транзакция должна ждать. В STM, если транзакция в настоящее время выполняется, вместо того, чтобы начать выполнять работу, она в любом случае будет отменена. В обоих случаях не выполняется никакой полезной работы, поэтому я не вижу, почему STM блокирует меньше, чем обычные блокировки. Но опять же, возможно, я что-то упускаю. - person Clinton; 11.04.2012
comment
@Clinton: Основная проблема с блокировками не в голодании, а в небольшом количестве блокировок или взаимоблокировок. Таким образом, проблемы с блокировками обычно связаны с корректностью, а не с производительностью. В то время как проблемы с STM могут быть проблемами с производительностью. Вы также должны учитывать возможности лени. Ленивость позволяет записать результат длительных чистых вычислений в короткой транзакции в TVar. - person jmg; 11.04.2012
comment
@Clinton: Concurrency не зависит от того, сколько блокировок происходит. С ручными блокировками вы можете иметь нужное количество блокировок, но все же столкнуться с взаимоблокировками при объединении модулей или библиотек. В то время как STM является компонуемым. Вам следует взглянуть на это: research.microsoft .com/en-us/um/people/simonpj/papers/stm/ - person jmg; 11.04.2012
comment
@jmg: я читал эту статью раньше и не совсем уверен в логике. Если у меня есть функция f с транзакцией, которая выполняется в течение 0,01 секунды в течение 0,00001 секунды, и другая функция g, в которой есть транзакция, использующая ту же транзакцию TVar, которая выполняется каждые 10 секунд в течение 0,1 секунды, я не могу их составить, f заблокирует g. Однако я мог бы скомпоновать два, используя блокировки (хотя f временами немного задерживался). Кажется, что замки более компонуемы, чем STM. - person Clinton; 11.04.2012
comment
@Clinton: я опубликовал свой ответ как отдельный ответ. - person jmg; 11.04.2012
comment
@Clinton: строго говоря, это не композиция, а просто выполнение двух транзакций в одной программе. Да, описанная вами ситуация могла привести к голоданию, но на практике это случается редко. Хорошей практикой является сделать все ваши транзакции короткими. Если у вас высокая конкуренция за конкретную часть общего состояния, вам может быть лучше с чем-то другим, кроме STM. (также активная область исследований - планирование стратегий, позволяющих избежать голодания) - person Simon Marlow; 19.05.2012

arrow_upward
0
arrow_downward

Это было написано как комментарий к одному из комментариев Клинтона к ответу Питера. Но стало слишком долго.

Предположим, у вас есть два банковских счета: А и Б. Каждый защищен своим замком. Теперь у вас есть две транзакции: первая переводит деньги из A в B, а вторая — из B в A. Каждая из них сначала блокирует исходную учетную запись, а затем — целевую, переводит деньги и снимает блокировки. Если вам не повезет, две транзакции будут заблокированы, и с этими двумя учетными записями ничего не будет сделано. Если вы сделаете это в STM, они будут работать друг за другом. Если у вас есть бесконечное множество транзакций первого типа, они могут заморозить вторую транзакцию. Но ты все равно много успеваешь. В то время как с блокировкой ничего никогда не происходит.

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

person jmg    schedule 11.04.2012