ETS: update list value without race condition

[Frank Muller]

Hi guys

I’ve a little issue I’m unable to solve with the current ETS API.

My table is of type set. Keys are integers and values are list of names:
123 -> [ jane, john, bob ]
456 -> [ joe, alice ]



Process A with Key=123 wants to delete ‘Jane’ while process B with Key=123
wants to add ‘Adam’.

First, they both needs to read the value associated with Key=123, update
that list accordingly and set back the new value.

But this lead to race condition (ex. process B could put back ‘jane’ - last
write wins).

Could this problem be solved atomically without involving explicit locking
per Key?

Is there any other better way to represent this data set which will not
suffer from the race condition?

Thanks
/Frank

[Sverker Eriksson]

It seems ets:select_replace could be your solution.



The documentation contains this example usage to do a compare-and-swap for a single key:



[Old] = ets:lookup(T, Key),

New = update_object(Old),

Success = (1 =:= ets:select_replace(T, [{Old, [], [{const, New}]}])),



/Sverker



From: erlang-questions <erlang-questions-***@erlang.org> On Behalf Of Frank Muller
Sent: den 22 april 2021 13:32
To: Erlang-Questions Questions <erlang-***@erlang.org>
Subject: ETS: update list value without race condition



Hi guys



I’ve a little issue I’m unable to solve with the current ETS API.



My table is of type set. Keys are integers and values are list of names:

123 -> [ jane, john, bob ]

456 -> [ joe, alice ]






Process A with Key=123 wants to delete ‘Jane’ while process B with Key=123 wants to add ‘Adam’.



First, they both needs to read the value associated with Key=123, update that list accordingly and set back the new value.



But this lead to race condition (ex. process B could put back ‘jane’ - last write wins).



Could this problem be solved atomically without involving explicit locking per Key?



Is there any other better way to represent this data set which will not suffer from the race condition?



Thanks

/Frank

[Frank Muller]

Indeed it’s Sverker.

This CAS example you provided doesn’t involve any full table scan, right?

Post by Sverker Eriksson
It seems ets:select_replace could be your solution.
[Old] = ets:lookup(T, Key),
New = update_object(Old),
Success = (1 =:= ets:select_replace(T, [{Old, [], [{const, New}]}])),
/Sverker
Of *Frank Muller
*Sent:* den 22 april 2021 13:32
*Subject:* ETS: update list value without race condition
Hi guys
I’ve a little issue I’m unable to solve with the current ETS API.
123 -> [ jane, john, bob ]
456 -> [ joe, alice ]


Process A with Key=123 wants to delete ‘Jane’ while process B with Key=123
wants to add ‘Adam’.
First, they both needs to read the value associated with Key=123, update
that list accordingly and set back the new value.
But this lead to race condition (ex. process B could put back ‘jane’ -
last write wins).
Could this problem be solved atomically without involving explicit locking per Key?
Is there any other better way to represent this data set which will not
suffer from the race condition?
Thanks
/Frank

[Jesper Louis Andersen]

Another path is to figure out if the ETS type 'bag' is more suitable in
your situation.

On Thu, Apr 22, 2021 at 1:46 PM Sverker Eriksson <

Post by Sverker Eriksson
It seems ets:select_replace could be your solution.
[Old] = ets:lookup(T, Key),
New = update_object(Old),
Success = (1 =:= ets:select_replace(T, [{Old, [], [{const, New}]}])),
/Sverker
Of *Frank Muller
*Sent:* den 22 april 2021 13:32
*Subject:* ETS: update list value without race condition
Hi guys
I’ve a little issue I’m unable to solve with the current ETS API.
123 -> [ jane, john, bob ]
456 -> [ joe, alice ]


Process A with Key=123 wants to delete ‘Jane’ while process B with Key=123
wants to add ‘Adam’.
First, they both needs to read the value associated with Key=123, update
that list accordingly and set back the new value.
But this lead to race condition (ex. process B could put back ‘jane’ -
last write wins).
Could this problem be solved atomically without involving explicit locking per Key?
Is there any other better way to represent this data set which will not
suffer from the race condition?
Thanks
/Frank

[Frank Muller]

Can’t see how the bag type can help with concurrent update Jesper.

I still need a read, update followed by a write.
Am I wrong?

Post by Jesper Louis Andersen
Another path is to figure out if the ETS type 'bag' is more suitable in
your situation.
On Thu, Apr 22, 2021 at 1:46 PM Sverker Eriksson <

Post by Sverker Eriksson
It seems ets:select_replace could be your solution.
[Old] = ets:lookup(T, Key),
New = update_object(Old),
Success = (1 =:= ets:select_replace(T, [{Old, [], [{const, New}]}])),
/Sverker
Behalf Of *Frank Muller
*Sent:* den 22 april 2021 13:32
*Subject:* ETS: update list value without race condition
Hi guys
I’ve a little issue I’m unable to solve with the current ETS API.
123 -> [ jane, john, bob ]
456 -> [ joe, alice ]


Process A with Key=123 wants to delete ‘Jane’ while process B with
Key=123 wants to add ‘Adam’.
First, they both needs to read the value associated with Key=123, update
that list accordingly and set back the new value.
But this lead to race condition (ex. process B could put back ‘jane’ -
last write wins).
Could this problem be solved atomically without involving explicit locking per Key?
Is there any other better way to represent this data set which will not
suffer from the race condition?
Thanks
/Frank

--
J.

[Jesper Louis Andersen]

In a bag you can have multiple tuples with the same key. So you would store

{123, jane}
{123, john}
{123, bob}
{456, joe}
{456, alice}

When you match on e.g., 123, you get back all tuples matching this, so you
can still get the behavior you want and obtain [jane, john, bob]. However,
now, if one process wants to add {123, adam} and another process wants to
delete {123, jane}, it's possible because the rows are different, even if
they have the same key. As your problem is formulated, this works in your
situation. However, I think your problem might be a bit more involved than
this cooked example in reality, so it might not work.

If you have a low number of updates to the table, I usually just make it
protected and then factor all updates through an owning process. Once
there's a single writer things are usually simpler, but beware that you can
still have interleaved reads so one must think about atomicity in this case.

Post by Frank Muller
Can’t see how the bag type can help with concurrent update Jesper.
I still need a read, update followed by a write.
Am I wrong?

Post by Jesper Louis Andersen
Another path is to figure out if the ETS type 'bag' is more suitable in
your situation.
On Thu, Apr 22, 2021 at 1:46 PM Sverker Eriksson <

Post by Sverker Eriksson
It seems ets:select_replace could be your solution.
The documentation contains this example usage to do a compare-and-swap
[Old] = ets:lookup(T, Key),
New = update_object(Old),
Success = (1 =:= ets:select_replace(T, [{Old, [], [{const, New}]}])),
/Sverker
Behalf Of *Frank Muller
*Sent:* den 22 april 2021 13:32
*Subject:* ETS: update list value without race condition
Hi guys
I’ve a little issue I’m unable to solve with the current ETS API.
123 -> [ jane, john, bob ]
456 -> [ joe, alice ]


Process A with Key=123 wants to delete ‘Jane’ while process B with
Key=123 wants to add ‘Adam’.
First, they both needs to read the value associated with Key=123, update
that list accordingly and set back the new value.
But this lead to race condition (ex. process B could put back ‘jane’ -
last write wins).
Could this problem be solved atomically without involving explicit locking per Key?
Is there any other better way to represent this data set which will not
suffer from the race condition?
Thanks
/Frank

--
J.

[Frank Muller]

Sverker,

The doc states there is a full table scan :-(

Is it possible to specify the Key in the match spec to avoid the table scan?

ets:select_replace(T, [{Old, [], [{const, New}]}])),

Post by Sverker Eriksson
It seems ets:select_replace could be your solution.
[Old] = ets:lookup(T, Key),
New = update_object(Old),
Success = (1 =:= ets:select_replace(T, [{Old, [], [{const, New}]}])),
/Sverker
Of *Frank Muller
*Sent:* den 22 april 2021 13:32
*Subject:* ETS: update list value without race condition
Hi guys
I’ve a little issue I’m unable to solve with the current ETS API.
123 -> [ jane, john, bob ]
456 -> [ joe, alice ]


Process A with Key=123 wants to delete ‘Jane’ while process B with Key=123
wants to add ‘Adam’.
First, they both needs to read the value associated with Key=123, update
that list accordingly and set back the new value.
But this lead to race condition (ex. process B could put back ‘jane’ -
last write wins).
Could this problem be solved atomically without involving explicit locking per Key?
Is there any other better way to represent this data set which will not
suffer from the race condition?
Thanks
/Frank

[Frank Muller]

Old contains the key already.

Maybe in this case there no full table scan :-)
Sverker, could you please confirm?


Sverker,

Post by Frank Muller
The doc states there is a full table scan :-(
Is it possible to specify the Key in the match spec to avoid the table scan?
ets:select_replace(T, [{Old, [], [{const, New}]}])),

Post by Sverker Eriksson
It seems ets:select_replace could be your solution.
[Old] = ets:lookup(T, Key),
New = update_object(Old),
Success = (1 =:= ets:select_replace(T, [{Old, [], [{const, New}]}])),
/Sverker
Behalf Of *Frank Muller
*Sent:* den 22 april 2021 13:32
*Subject:* ETS: update list value without race condition
Hi guys
I’ve a little issue I’m unable to solve with the current ETS API.
123 -> [ jane, john, bob ]
456 -> [ joe, alice ]


Process A with Key=123 wants to delete ‘Jane’ while process B with
Key=123 wants to add ‘Adam’.
First, they both needs to read the value associated with Key=123, update
that list accordingly and set back the new value.
But this lead to race condition (ex. process B could put back ‘jane’ -
last write wins).
Could this problem be solved atomically without involving explicit locking per Key?
Is there any other better way to represent this data set which will not
suffer from the race condition?
Thanks
/Frank

[Sverker Eriksson]

Correct.

If the key is fully bound in the match spec no table traversal is needed.



/Sverker





From: Frank Muller <***@gmail.com>
Sent: den 22 april 2021 14:37
To: Sverker Eriksson <***@ericsson.com>
Cc: Erlang-Questions Questions <erlang-***@erlang.org>
Subject: Re: ETS: update list value without race condition



Old contains the key already.



Maybe in this case there no full table scan :-)

Sverker, could you please confirm?

[Frank Muller]

Great, thanks!

Post by Sverker Eriksson
Correct.
If the key is fully bound in the match spec no table traversal is needed.
/Sverker
*Sent:* den 22 april 2021 14:37
*Subject:* Re: ETS: update list value without race condition
Old contains the key already.
Maybe in this case there no full table scan :-)
Sverker, could you please confirm?

[Tristan Sloughter]

If you just want to add a single element you can use `select_replace` like in the example in the docs https://erlang.org/doc/man/ets.html#select_replace-2 since a matchspec can include a cons:

MS = ets:fun2ms(fun({K, L}) when is_list(L) -> {K, [marker | L]} end).

A bag might still be more appropriate, but if the goal is to just have a single call that handles this for you then `select_replace` can work. The third option would be a compare and swap with `select_replace`, which is the second example in the docs.

Post by Frank Muller
Hi guys
I’ve a little issue I’m unable to solve with the current ETS API.
123 -> [ jane, john, bob ]
456 -> [ joe, alice ]


Process A with Key=123 wants to delete ‘Jane’ while process B with Key=123 wants to add ‘Adam’.
First, they both needs to read the value associated with Key=123, update that list accordingly and set back the new value.
But this lead to race condition (ex. process B could put back ‘jane’ - last write wins).
Could this problem be solved atomically without involving explicit locking per Key?
Is there any other better way to represent this data set which will not suffer from the race condition?
Thanks
/Frank