Clojure STM and deadlocks
Mark Volkmann
deadlocks? I'm just trying to understand the basics of what, if
anything, it does to avoid them.
--
R. Mark Volkmann
Object Computing, Inc.
Jeffrey Straszheim
Mark Volkmann
<straszhe...@gmail.com> wrote:
> The code isn't too hard to follow, 'cept the barging stuff gets a bit
> tricky. A nice 10,000 foot overview would be nice, however.
>
> On Tue, Mar 17, 2009 at 8:04 AM, Mark Volkmann <r.mark....@gmail.com>
> wrote:
>>
>> Is there a summary somewhere of the steps Clojure STM takes to avoid
>> deadlocks? I'm just trying to understand the basics of what, if
>> anything, it does to avoid them.
I just ran across this quote from Rich Hickey near the bottom of
http://mail.google.com/mail/?ui=2&zx=gb3mbfrah3gv&shva=1#inbox/12014881fc65b5c1
“Clojure's STM and agent mechanisms are deadlock-free. They are not
message-passing systems
with blocking selective receive. The STM uses
locks internally, but does lock-conflict detection and resolution
automatically.”
I take this to mean that it is not possible for STM transactions in
Clojure to deadlock. I'm still interested in learning the basics of
how it does lock-conflict detection and resolution. I haven't found a
description of it anywhere. I guess I'll have to read through the
code.
Rich Hickey
On Mar 17, 2:32 pm, Mark Volkmann <r.mark.volkm...@gmail.com> wrote:
> On Tue, Mar 17, 2009 at 8:08 AM, Jeffrey Straszheim
>
> > The code isn't too hard to follow, 'cept the barging stuff gets a bit
> > tricky. A nice 10,000 foot overview would be nice, however.
>
>
> >> Is there a summary somewhere of the steps Clojure STM takes to avoid
> >> deadlocks? I'm just trying to understand the basics of what, if
> >> anything, it does to avoid them.
>
> “Clojure's STM and agent mechanisms are deadlock-free. They are not
> message-passing systems with blocking selective receive. The STM uses
> locks internally, but does lock-conflict detection and resolution
> automatically.”
>
> I take this to mean that it is not possible for STM transactions in
> Clojure to deadlock. I'm still interested in learning the basics of
> how it does lock-conflict detection and resolution. I haven't found a
> description of it anywhere. I guess I'll have to read through the
> code.
>
that. Explaining precisely and accurately how an STM works is not
something for a few paragraphs of prose. It's only about 600 lines of
code.
I don't want to promise anything about how the implementation works,
since I'd like to be free to change it. If you want to understand how
it currently works, the code is there.
Rich
Mark Volkmann
You certainly don't owe anyone a written summary of how any parts of
Clojure work. However, surely you would agree that if such summaries
existed, it would be easier for people interested in Clojure to get a
general understanding much faster than reading the code. As an
example, when people want to know how threads and locks work in Java,
they don't usually look at the source code. There are plenty of
tutorials on the web and books that explain it.
In my case I'm having a semi-debate with someone about why coding for
concurrency is easier in Clojure than in Java. The person I'm
discussing this with thinks that Clojure is oversimplifying
concurrency issues. He feels it is necessary to have a detailed
understanding of an entire application in order to avoid deadlocks. I
was looking for something that might convince him that it isn't true
and that deadlocks cannot occur in Clojure. I don't think you can
expect someone like him that is barely interested in Clojure to look
through the source. On the other hand, if there was a page on the
Clojure website that explained at a high level how Clojure avoids
deadlocks, I think he would read that.
I do understand though how not documenting certain things leaves you
free to change the implementation later.
Rich Hickey
On Mar 17, 3:21 pm, Mark Volkmann <r.mark.volkm...@gmail.com> wrote:
http://en.wikipedia.org/wiki/Software_transactional_memory
to get a feel for what a description of an STM looks like. Clojure's
STM is not exactly like any of those, but you'll see none of those
descriptions are elevator pitches.
also:
http://en.wikipedia.org/wiki/Multiversion_concurrency_control
http://en.wikipedia.org/wiki/Snapshot_isolation
for some of the other issues.
The bottom line is that STM implementations are complex and won't have
simple descriptions.
If the person you are arguing with can't understand how concurrency
could be made automatic and deadlock free, have him imagine an STM
where each ref had a unique locking number and a revision, no locks
were taken until commit, and then the locks were taken in locking
number order, revisions compared to those used by the transaction,
abort if changed since used, else increment revisions and commit.
Deadlock-free and automatic. It ends up that no STM works exactly this
way, but it is an example of how the deadlock-free correctness benefit
could be delivered simply.
Rich
Mark Volkmann
Thanks Rich! I've actually finished reading the Wikipedia entry for
STM this morning and it helped me a lot. I haven't looked at the other
two yet though, so I'll do that.
> The bottom line is that STM implementations are complex and won't have
> simple descriptions.
>
> If the person you are arguing with can't understand how concurrency
> could be made automatic and deadlock free, have him imagine an STM
> where each ref had a unique locking number and a revision, no locks
> were taken until commit, and then the locks were taken in locking
> number order, revisions compared to those used by the transaction,
> abort if changed since used, else increment revisions and commit.
> Deadlock-free and automatic. It ends up that no STM works exactly this
> way, but it is an example of how the deadlock-free correctness benefit
> could be delivered simply.
Thanks! That helps.
Luc Prefontaine
in a specific application transaction when coding a database centric application ?!?!?!
Most of the time, you do not really care about these things. You stick to a few minimal rules
and that's it. These rules vary a bit depending on your database design and application
requirements. Your thinking is not focused on how it's done by Oracle but what will be the data state
after a transaction is completed.
When we use Oracle we take somethings for granted. Do we hit deadlocks every time we code a transaction ?
No... if it happens it's most probably the result of a bad transaction design or a lack of system resources or both.
It means you broke one of the rules, not that Oracle is bad.
STM removes from your shoulder some of the issues you face with a db centric transaction.
How it deals internally with these issues remains academic if it delivers what it said it would.
People should take these as granted like other stuff Oracle provides you when you're coding db centric transactions.
Instead of guessing why it's not possible, try it...
The perception problem here is that concurrent apps always had a special look and tools
because of the context they evolved from.
Someone came up with threads, mutexes, semaphores, ... that are very low level abstractions most of them
came from operating system implementations.
No one at the time came out with a higher level abstraction.
No one tried to look at this as in memory transactions in the 1980s.
No one came out with a language that made immutability the default behaviour for data.
Transactions were reserved to the database world. Transaction implied some heavy stuff done on slow devices.
So for a number of years now, coding a concurrent application HAD to be complicated otherwise it's not good.
That's what we end up with these days in people's mind. A bit like coding a transaction with flat files without
a journal and having to insure integrity.
Oracle explains some of the stuff they do internally but they certainly do not publish the engine code
or go down to fine grain level of details and as far as I know no one complained yet :))))
Rich is right in being shy to describe how his implementation works in detail. It may change over time
for a number of reasons.
When using the early db run times (Ingres) we were spending time finding out
how to best express a query because we knew that the query plan produced would be a better fit.
You could change the order of conditions in a where clause and get very different performance results.
Great until the next release of the engine came out. All your code assuming such rules had to be
rewritten...
Any attempt to custom fit an application design with a real or supposed internal behaviour of STM is bad...
Guessing performance levels from an internal behaviour could be as bad as in the relational database early age.
Luc
|
Luc Préfontaine Armageddon was yesterday, today we have a real problem... |
