Alex Baran ([info]aleksijb) wrote,
@ 2007-02-12 18:44:00
Previous Entry  Add to memories!  Share this!  Next Entry

Размышления Peter Van Roy, автора книги CTM, о том что большинство хороших идей в программировании пришлось на 60-е 70-е годы. То что было позже в основном касалось интеграции идей. Peter спрашивает какие революционные новые идеи появились после 1980?

(20 comments) - (Post a new comment)


[info]aleksijb
2007-02-12 04:58 pm UTC (link)
Упс, тред здесь

(Reply to this)


[info]voidbent
2007-02-15 08:17 pm UTC (link)
lock-free и wait-free алгоритмы и структуры данных например :)

(Reply to this) (Thread)

[info]aleksijb
2007-02-15 10:32 pm UTC (link)
Объектная база GemStone является lock-free, wait-free (судя из определений lack-free, wait-free данных в википедии). Если сесия меняет объект, то создается новая версия объекта. При комите происходит проверка write-write либо read-write конфликтов между сесиями. Первые упоминания о GemStone, которые мне удалось найти 86-87 год. Возможно теория была проработана раньше.

(Reply to this) (Parent)(Thread)

[info]voidbent
2007-02-16 08:46 am UTC (link)
Увы ничего не могу сказать про GemStone. Хотя и очень глубоко сомневаюсь что она wait-free. Если я ничего путаю то сама идея появилась в начале 90-х, а серьзёно к ней относиться начали только после того как в 2004 году на Programming Language Design and Implementation conference некто Michael Maged представил !первый в мире! lock-free алгоритм выделения памяти (база данных это будет чуть по серьёзнее чем выделение памяти). Об этом пишет А.Александреску вот сдесь - http://www.ddj.com/dept/cpp/184401865. В 86 году просто физически небыло возможности сделать lock-free а тем-более wait-free базу данных потому что тогда для этого у процессоров небыло нужных инструкций (для lock-free нужна как минимум CAS).

(Reply to this) (Parent)

[info]voidbent
2007-02-16 08:49 am UTC (link)
> Если сесия меняет объект, то создается новая версия объекта.
> При комите происходит проверка write-write либо read-write
> конфликтов между сесиями.
И при этом не используются мутексы и коднишин вариейблы?

(Reply to this) (Parent)(Thread)

[info]aleksijb
2007-02-16 10:42 am UTC (link)
При стандартной схеме работы не используются.

В GemStone все есть объект. Поэтому любое изменение - можно расматривать как изменение поля объекта (у колекций поля вместо названий содержат номера).
Когда происходит изменение поля объекта, создается копия и изменения вносятся в копию(поэтому нет необходимости делать lock). Все измененные транзакцией объекты(фактически копии) хранятся в write-set транзакции. Транзакция видит репозиторий таким каким он был в момент начала транзакции + с учетом своих изменений. Остальные видят последнее закомиченое состояние.
При комите выполняется проверка по каждому элементу write-set. Если оригинал элемента изменен другой транзакцией, то write-write конфликт. В случае конфликта происходит откат транзакции к текущему положению закомиченого репозитория.

Чем не lock-free?

P.S. Но там есть и локи, если например с точки зрения пользователя схема конфликт-откат является недопустимой.

(Reply to this) (Parent)(Thread)

[info]voidbent
2007-02-16 11:00 am UTC (link)
"При стандартной схеме работы не используются."
Почему вы так думаете?

"При комите выполняется проверка по каждому элементу write-set." - Вот тут собственно и возникает вопрос. Для такой проверки используется блокировка репозитория или нет. Если да (что скорее всего и происходит) - то GemStone - это не лок фри. Если нет, то как именно они обеспечивают безопасность нескольких одновременных комитов?

Грубо говоря как именно обеспечивается безопасность такой проверки, при помощи lock или при помощи lock-free алгоритмов?

(Reply to this) (Parent)(Thread)

[info]aleksijb
2007-02-16 01:15 pm UTC (link)
"При стандартной схеме работы не используются."
Почему вы так думаете?

По докам и форуму сложилось такое мнение, возможно ошибочное. ИМХО не стоило бы такой огород городить если бы на пользовательском уровне всеравно локами пользовались.
Да и к тому же народ делает схемы наката в случае конфликт-откат.

(Reply to this) (Parent)(Thread)

[info]voidbent
2007-02-16 01:20 pm UTC (link)
Ещё как стоило. Одно дело неконтролируемое Lock-based API а другое дело конролируемая Lock-based реализация.

lock-free это слишком сложно и дорого и в вашем примере пользы от lock-free будет ноль.

(Reply to this) (Parent)

[info]voidbent
2007-02-16 01:24 pm UTC (link)
Т.е. вы сделали вывод что база имеет lock-free реализацию только на основании того что в её API нету явных локов? В API у SQL-я тоже нету никаких локов, тем не мение внутри реализации они есть.

(Reply to this) (Parent)(Thread)

[info]aleksijb
2007-02-16 01:59 pm UTC (link)
Не получится ли так что реализация lock-free рано или поздно(возможно в железе) приведет к необходимости локов?

(Reply to this) (Parent)

[info]aleksijb
2007-02-16 02:03 pm UTC (link)
На сколько я помню SQL, там есть локи на таблицы, также вроде была такая конструкция select ... for update, которая позволяла лочить подмножество записей таблицы.

(Reply to this) (Parent)(Thread)

[info]voidbent
2007-02-16 02:22 pm UTC (link)
Ну возможно. Я тут ничего не могу сказать.

(Reply to this) (Parent)

[info]voidbent
2007-02-16 11:07 am UTC (link)
Кстати а вы точно уверенны что в GemStone вообще возможна ситуация нескольких одновременных комитов из разных потоков? Может там всё разрешается message passing-ом например и коммитит всегда 1 поток, или ещё как нибудь.

(Reply to this) (Parent)

[info]voidbent
2007-02-16 11:09 am UTC (link)
> P.S. Но там есть и локи, если например с точки
> зрения пользователя схема конфликт-откат является недопустимой.

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

(Reply to this) (Parent)(Thread)

[info]aleksijb
2007-02-16 01:06 pm UTC (link)
То как лочится репозиторий внутри, в доках не нашел. Потому ниже догадки.

Есть в базе такое понятие как CommitRecord. В этот record транзакция может записывать изменения. Насколько я понимаю иногда изменения пишутся непосредственно в репозиторий иногда в CommitRecord. В CommitRecord можно например писать если репозиторий залочен другой сесией. При снятии лока с репозитория можно внести в репозиторий самый старый CommitRecord. Считается ли это lock-free не знаю. Можно выстраивать CommitRecord-ы по времени. Текущим состоянием объекта будет то что находится в самом свежем record-е, либо в репозитории, если в рекордах такой объект отсутствует.
Для того чтобы транзакция видела репозиторий на момент своего начала делаем бранч от текущего рекорда. При комите смотрим все рекорды выше того от которого сделали бранч на предмет write-write конфликтов. Если комит успешный ложим рекорд на верх, так как он самый свежий.

(Reply to this) (Parent)(Thread)

[info]voidbent
2007-02-16 01:11 pm UTC (link)
> Считается ли это lock-free не знаю.

Всё зависит от того как оно внутри устроенно. Описание мне ни о чём не говорит. Если оно устроенно через мутексы внутри то нет. Если через CAS - то да. Скорее всего что мутексы внутри используются потому что lock-free это черезчур дорогое удовольствие.

(Reply to this) (Parent)

[info]voidbent
2007-02-16 01:18 pm UTC (link)
Для всех этих действий нужна синхронизация. Мы не можем всё это осуществить за просто так не синхронизируясь. Коммит по любому нужно синхронизировать. Вопрос в том какой тип синхронизации используется ВНУТРИ этого всего что вы описали. Я даю 99.99999% что внутри lock&wait based синхронизация - семафоры, мутексы, кондишины, месидж пассинг и т.д. И 0.00001% что внутри всего этого добра lock free синхронизация - CAS и ей подобные механизмы.

(Reply to this) (Parent)

[info]singalen
2007-09-04 09:53 am UTC (link)
lock-free выглядит примерно так: http://www.ibm.com/developerworks/java/library/j-jtp11234/
- это алгоритмы на атомарных операциях compareAndSet, compareAndSwap. Оные операции в новых процессорах атомарны на уровне железа, то есть не требуют блокировок на низком уровне.
На старых процессорах, соответственно, требуют.

(Reply to this) (Parent)(Thread)

[info]aleksijb
2007-09-04 01:03 pm UTC (link)
Спасибо, почитаю в четверг-пятницу, когда вернусь от заказчика

(Reply to this) (Parent)

(20 comments) - (Post a new comment)

Create an Account
Forgot your login or password?
Log in with OpenID
English • Español • Deutsch • Русский…