Atomic ets

classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

Atomic ets

Joe Armstrong (AL/EAB)

   Agggggggggggggggggggggggggghhhhhhhhhhhhhhhhhh

   Verily verily verify I say untoo ye

   Even thou thy hath vouchsafed a lock - and even though thy
thath promest to delivery it back - there will come a day
when the Great one will return and the lock will be raised
and there will be much gnashing of teeth and wailing and
the bones of the long dead will rise and dance on the graves
of the unfrocked bishops.

   /Joe

 

 

> -----Original Message-----
> From: owner-erlang-questions
> [mailto:owner-erlang-questions]On Behalf Of Mats Cronqvist
> Sent: den 13 december 2005 17:35
> To: erlang-questions
> Subject: Re: Atomic ets
>
>
>    years ago, i suggested to OTP that adding atomic
> expressions (similar to
> block expressions) to Erlang would allow one to solve this
> kind of problems. like;
>
> atomic
>    case ets:lookup(a,b) of
>      [] -> ets:insert(a,c);
>      _ -> ok
>    end
> end
>
>    inside the atomic block you'd be guaranteed not to be
> scheduled out.
>    i don't remember if they laughed hysterically or just
> waited for me to go
> away, but nothing came of it. quite possibly there were good
> reasons for that.
>
>    mats
>
> p.s. of course it'd be really easy to crush the emulator with
> this feature. i
> don't think that's a good reason for nixing it though.
>
>
> Ulf Wiger (AL/EAB) wrote:
> >  
> > Thomas Lindgren wrote:
> >
> >>1. Am I being dense in writing my ets code? Are there simple,
> >>useful ways to write ets code that avoids the problem of
> >>getting preempted between, say, a lookup and an insert?
> >
> >
> > Well, yes (on the second question). You can make sure that
> > all updates to a table are serialized using e.g. a gen_server.
> >
> > You can then pass the server an update fun if you want.
> >
> > /Uffe
>


Reply | Threaded
Open this post in threaded view
|

Atomic ets

Hal Snyder-2
"Joe Armstrong (AL/EAB)" <joe.armstrong> writes:

>    Agggggggggggggggggggggggggghhhhhhhhhhhhhhhhhh
>
>    Verily verily verify I say untoo ye
>
>    Even thou thy hath vouchsafed a lock - and even though thy
> thath promest to delivery it back - there will come a day
> when the Great one will return and the lock will be raised
> and there will be much gnashing of teeth and wailing and
> the bones of the long dead will rise and dance on the graves
> of the unfrocked bishops.

One great appeal of Erlang has been its avoidance of the Slough of
(P)Threads and Mutexes into which my colleagues, many of whom are also
deeply into OOP, have disappeared for months at a time. I shudder
whenever purveyors of mutexes and other such evils make a run at the
unspoiled atoll that is OTP.

Once someone snidely asked "With all this concurrency, what are
Erlang's synchronization primitives", only to be crushed by the
simplicity of the response: "send and receive".


Reply | Threaded
Open this post in threaded view
|

Atomic ets

Thomas Lindgren-5


--- Hal Snyder <hal> wrote:

> "Joe Armstrong (AL/EAB)"
> <joe.armstrong> writes:
>
> >    Agggggggggggggggggggggggggghhhhhhhhhhhhhhhhhh
> >
> >    Verily verily verify I say untoo ye
> >
> >    Even thou thy hath vouchsafed a lock - and even
> though thy
> > thath promest to delivery it back - there will
> come a day
> > when the Great one will return and the lock will
> be raised
> > and there will be much gnashing of teeth and
> wailing and
> > the bones of the long dead will rise and dance on
> the graves
> > of the unfrocked bishops.
>
> One great appeal of Erlang has been its avoidance of
> the Slough of
> (P)Threads and Mutexes into which my colleagues,
> many of whom are also
> deeply into OOP, have disappeared for months at a
> time. I shudder
> whenever purveyors of mutexes and other such evils
> make a run at the
> unspoiled atoll that is OTP.
>
> Once someone snidely asked "With all this
> concurrency, what are
> Erlang's synchronization primitives", only to be
> crushed by the
> simplicity of the response: "send and receive".

Note that transactions provide another conceptually
simple approach. My prediction is that fine-grain,
hardware-assisted transactions will largely replace
locking in conventional systems. But not for a while;
the comp.arch. researchers have just gotten their
teeth into it.

So far the alternatives for "atomic ets" seem to be:

1. Serialize all non-atomic ets requests through a
gen_server. Drawback: needs extra trip to server.
(There is another design drawback: it can be a very
pessimistic "locking" regime for the data, leading to
excessive waiting.)

2. Use mnesia, abandon ets. Drawback: transactions are
more expensive.

3. Introduce critical sections, e.g., run a fun() to
completion. Drawback: it's a temptation to the
foolish. This approach seems attractive to me -- for
example: no need for explicit locking -- but the more
one wants to avoid mischief, the more it starts
looking like mnesia:transaction.

4. Use locks. Drawback: well-known to be difficult to
do right.

5. Introduce a magical new API more suited for
concurrent/atomic ets. Drawback: it doesn't exist yet
:-)

Out of these alternatives, as a rule of thumb, using
mnesia after all seems the solution with least scope
for trouble in an SMP system. Or, when suitable, use a
carefully-designed gen_server.

Best,
Thomas


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around
http://mail.yahoo.com 


Reply | Threaded
Open this post in threaded view
|

Atomic ets

Ulf Wiger-5
Den 2005-12-14 20:29:03 skrev Thomas Lindgren <thomasl_erlang>:

> 5. Introduce a magical new API more suited for
> concurrent/atomic ets. Drawback: it doesn't exist yet
> :-)

You'd think that with a functional language, there
should be a way to write code that is verifiably
'shallow' (no loops, no side effects - or, in this
case, only allowed side effects). This is essentially,
what we want for the match specifications (replacing
the ms_transform module), for mnesia transactions
(where the manual kindly asks us to write pure code)
and perhaps for atomic ets. If a function could be
tagged as (conditionally) safe, one could offer an
'atomic' construct and have it execute only such
code.

/Uffe (who volunteers _not_ to be the one implementing it.)


Reply | Threaded
Open this post in threaded view
|

Atomic ets

Mats Cronqvist (ÄL2/EAB)


Ulf Wiger wrote:

> Den 2005-12-14 20:29:03 skrev Thomas Lindgren <thomasl_erlang>:
>
>> 5. Introduce a magical new API more suited for
>> concurrent/atomic ets. Drawback: it doesn't exist yet
>> :-)
>
>
> You'd think that with a functional language, there
> should be a way to write code that is verifiably
> 'shallow' (no loops, no side effects - or, in this
> case, only allowed side effects). This is essentially,
> what we want for the match specifications (replacing
> the ms_transform module), for mnesia transactions
> (where the manual kindly asks us to write pure code)
> and perhaps for atomic ets. If a function could be
> tagged as (conditionally) safe, one could offer an
> 'atomic' construct and have it execute only such
> code.
>
> /Uffe (who volunteers _not_ to be the one implementing it.)


   perhaps a few times a year i'm faced with problems where serializing, locking
or (especially) mnesia are noticably slowing the code down. for those
situations, i would be happy for the possibility to run any code in the "magical
new API", even though it is potentially risky.
   of course, it'd be better if the compiler would enforce that i could only
call bif's in the critical section (that would make is pretty safe i guess).

   mats



Reply | Threaded
Open this post in threaded view
|

Atomic ets

Dave Smith-2
In reply to this post by Thomas Lindgren-5
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


On Dec 14, 2005, at 12:29 PM, Thomas Lindgren wrote:

> Note that transactions provide another conceptually
> simple approach. My prediction is that fine-grain,
> hardware-assisted transactions will largely replace
> locking in conventional systems. But not for a while;
> the comp.arch. researchers have just gotten their
> teeth into it.

If you will humor a Erlang newbie, what exactly is the difference  
between a "transaction" and a mutex/critical section? And, if the  
difference is negligible, wouldn't introducing a transaction  
construct or the other "atomic" ideas mentioned furthered down the  
thread, just (re-)introduce the complexity of all the locking madness  
Erlang currently shields us from?

The complaints about having to serialize to a gen_server seem odd to  
me (again, a newbie :)). Mutexes introduce a similar sort of  
serialization (i.e. you have to design carefully for speed/
contention), yet have much more difficult semantics.

Just my $0.02...

D.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (Darwin)

iD8DBQFDoXq3s6zMNAt8YgcRAhWyAJ4j41r40XghRrazs3xA9rkB12+eHQCfcv6F
05StLget1N0oDIfy9dtBoyk=
=qGX9
-----END PGP SIGNATURE-----


Reply | Threaded
Open this post in threaded view
|

Atomic ets

Mats Cronqvist (ÄL2/EAB)
In reply to this post by Mats Cronqvist (ÄL2/EAB)


Robert Virding wrote:

>
> I think you will find when you get down to it that a magical new API
> probably won't be much more efficient as it basically still has to do
> the same work. Even if you don't SEE it.
>
> One of the original tenants of Erlang was that distribution could be
> transparent when desired, message passing and error handling were
> designed to be transparently distributable. I can think of better things
> to do than to add a general distributed transaction system to Erlang.
> And to add one to the basic language that only worked localy would be a
> Bad Thing and would probably mean that the poor users will not only
> shoot themselves in the foot but also chop off the whole leg. At the
> very best.

   i've been mulling over the above for a while now, and i don't get it.

the original question in the thread was this:
 > Are there simple,
 > useful ways to write ets code that avoids the problem of
 > getting preempted between, say, a lookup and an insert?

   more generally, what do you do if you you need to make sure your erlang
process is not scheduled out between two BIF calls. i think the answer is;
"write a new BIF"(*). see e.g erlang:spawn_link/3;

    spawn_link(Module, Function, ArgumentList)

    This BIF is identical to the following code being evaluated in an atomic
    operation:

    > Pid = spawn(Module, Function, ArgumentList),
      link(Pid),
      Pid.

    This BIF is necessary since the process created might run immediately and
    fail before link/1 is called.

or ets:insert_new/2, which is basically an atomic version of;

case ets:loopkup(Tab,Key) of
   [] -> ets:insert(Tab,{Key,Val});
   _ -> false
end

   in an atomic block spawn_link could be implemented like this;
atomic
   link(Pid = spawn(Module, Function, ArgumentList))
end

   i'm not sure what "general distributed transaction system" has to do with any
of this.

   mats

(*) in some cases, such as in the original question, you can serialize through a
server (which will slow you down some).
   sometimes i've resorted to this nasty hack;

erlang:yield(),
foo(),
bla().

   which'll (probably) make foo and bla atomic (at least as long as the vm uses
reduction counting)


Reply | Threaded
Open this post in threaded view
|

Atomic ets

Björn Gustavsson-3
Mats Cronqvist <mats.cronqvist> writes:

> (*) in some cases, such as in the original question, you can serialize
> through a server (which will slow you down some).
>    sometimes i've resorted to this nasty hack;
>
> erlang:yield(),
> foo(),
> bla().
>
>    which'll (probably) make foo and bla atomic (at least as long as
> the vm uses reduction counting)

And as long the Erlang emulator can not run more than one Erlang process,
which is no longer true in the SMP-enabled emulator in R11B.

/Bjorn
--
Bj?rn Gustavsson, Erlang/OTP, Ericsson AB


Reply | Threaded
Open this post in threaded view
|

Atomic ets

Mats Cronqvist (ÄL2/EAB)
   yes, and that would go for the "atomic block" idea too i guess.

   mats

Bjorn Gustavsson wrote:

> Mats Cronqvist <mats.cronqvist> writes:
>
>
>>(*) in some cases, such as in the original question, you can serialize
>>through a server (which will slow you down some).
>>   sometimes i've resorted to this nasty hack;
>>
>>erlang:yield(),
>>foo(),
>>bla().
>>
>>   which'll (probably) make foo and bla atomic (at least as long as
>>the vm uses reduction counting)
>
>
> And as long the Erlang emulator can not run more than one Erlang process,
> which is no longer true in the SMP-enabled emulator in R11B.
>
> /Bjorn


Reply | Threaded
Open this post in threaded view
|

Atomic ets

Thomas Lindgren-5
In reply to this post by Dave Smith-2


--- Dave Smith <dizzyd> wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
>
> On Dec 14, 2005, at 12:29 PM, Thomas Lindgren wrote:
>
> > Note that transactions provide another
> conceptually
> > simple approach. My prediction is that fine-grain,
> > hardware-assisted transactions will largely
> replace
> > locking in conventional systems. But not for a
> while;
> > the comp.arch. researchers have just gotten their
> > teeth into it.
>
> If you will humor a Erlang newbie, what exactly is
> the difference  
> between a "transaction" and a mutex/critical
> section?

OK, first, the comment above referred to mainstream
hardware research, not Erlang. I think stock hardware
will have support for "basic transactions" in a few
years (where you run a delimited segment of code and
either "commit" all memory operations or "abort" and
discard them). Compared to explicit locking, writing
correct code is just so much simpler in this model.

Anyway, compared to critical sections, full
transactions are also consistent, isolated and
durable. A transaction supports (more or less)
transparent fine-grain locking of multiple database
entries over multiple tables, ensures that the effects
are undone if the transaction aborts, etc etc.

> And, if the  
> difference is negligible, wouldn't introducing a
> transaction  
> construct or the other "atomic" ideas mentioned
> furthered down the  
> thread, just (re-)introduce the complexity of all
> the locking madness  
> Erlang currently shields us from?

Basically, transactions provide a safe wrapper for the
locking and associated operations on a shared memory
(or database). Your sanity won't be destroyed by
directly gazing at the locking code being executed
behind the scenes (cf. Gray, Reuter, TRANSACTION
PROCESSING :-).

Erlang has less need (or perhaps no need, some may
claim) for a shared memory/database, but in practice
it seems to creep back in for some purposes. Most of
the practical systems I have seen do use mnesia, for
example.

> The complaints about having to serialize to a
> gen_server seem odd to  
> me (again, a newbie :)). Mutexes introduce a similar
> sort of  
> serialization (i.e. you have to design carefully for
> speed/
> contention), yet have much more difficult semantics.

Yes, but if you funnel all writes to a table through a
server, you "lock the whole table" to, say, update a
single entry. I would prefer a more concurrent
solution when table operations are common.

Best,
Thomas


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around
http://mail.yahoo.com 


Reply | Threaded
Open this post in threaded view
|

Atomic ets

Thomas Lindgren-5
In reply to this post by Ulf Wiger-5


--- Ulf Wiger <ulf> wrote:

> Den 2005-12-14 20:29:03 skrev Thomas Lindgren
> <thomasl_erlang>:
>
> > 5. Introduce a magical new API more suited for
> > concurrent/atomic ets. Drawback: it doesn't exist
> yet
> > :-)
>
> You'd think that with a functional language, there
> should be a way to write code that is verifiably
> 'shallow' (no loops, no side effects - or, in this
> case, only allowed side effects). This is
> essentially,
> what we want for the match specifications (replacing
> the ms_transform module), for mnesia transactions
> (where the manual kindly asks us to write pure code)
> and perhaps for atomic ets. If a function could be
> tagged as (conditionally) safe, one could offer an
> 'atomic' construct and have it execute only such
> code.

This might be a viable approach; how about permitting
pattern matching, guards, and bodies where the only
function calls are to BIFs? Receive might be excluded,
but case/if should be okay since no loops. Atomicity
will have to support abort/undo as well.

Nice support for match specifications and associated
"codelets" would be great too.

Best,
Thomas


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around
http://mail.yahoo.com 


Reply | Threaded
Open this post in threaded view
|

Atomic ets

Robert Raschke-6
Hi,

warning, cynicism ahead.

Whenever a new email on this thread pops up in my inbox, I check the
date.  Every single time I think it might be April, 1.

If your application uses ets as a communication mechanism between
processes, that is surely quite a sore design mistake.

Where does this desire for programming with locks come from?  Erlang
has a much simpler way of dealing with parallelism.  But you do have
to think about it, it's no use to take a book on PThreads and try to
translate the algorithms directly.

Programming with locks or atomic regions always makes me think of the
chaos that would ensue if there were only one library in the world
with exactly one copy of every book and nobody is allowed their own.
To read anything you have to go to the library and check out the book
you want.  Oh, and you're only allowed to write any book by going to
the library, checking out an existing book or getting a blank one (if
it's a new book).

Hang on, we can optimise this.  How about you can check out individual
chapters, or pages, or lines, or letters ...

It would sure save a lot of space ...

Robby



Reply | Threaded
Open this post in threaded view
|

Atomic ets

Matthias Lang-2
Robert Raschke writes:

 > If your application uses ets as a communication mechanism between
 > processes, that is surely quite a sore design mistake.

Looking at a freshly started erlang node, I can see a number of ETS
tables:

   1> ets:all().              
   [ac_tab,
    inet_db,
    inet_hosts,
    file_io_servers,
    inet_cache,
    global_names_ext,
    global_locks,
    global_names,
    10,
    9]

In some (many? most?) cases, ETS seems to have been used for no
particularly good reason at all. For example: inet_db is a gen_server
which uses an ets table (inet_db) to store its 20
configuration/environment parameters.

The only explanation I can think of is "it must be historical
junk". Or am I missing something?

Matthias