ConETS table consistency while entries are deleted from 2 processes

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

ConETS table consistency while entries are deleted from 2 processes

Frank Muller
Hi all


Lets assume a public ETS table of type ‘ordered_set’.

Every minute, a process A is deleting expired entries from it (see below).

In the same time, another process B can delete any entry (ex. randomly) from this table.

I’ve implemented two strategies which can be used by process A:

_________________________________________
-spec purge1(pos_integer()) -> ok.
purge1(Now) ->
    Key = ets:first(?MODULE),
    purge1(Now, Key).

purge1(Now, Key) when Key =< Now ->
    true = ets:delete(?MODULE, Key), %% idempotent call
    purge1(Now);
purge1(_, _) -> %% '$end_of_table’ or Key > Now
    ok.

or:
_________________________________________
-spec purge2(pos_integer()) -> ok.
purge2(Now) ->
    Key = ets:first(?MODULE),
    purge2(Now, Key).

purge2(Now, Key) when Key =< Now ->
    Next = ets:next(?MODULE, Key),
    true = ets:delete(?MODULE, Key), %% idempotent call
    purge2(Now, Next);
purge2(_, _) -> %% '$end_of_table’ or Key > Now
    ok.
_________________________________________

Question: is it safe in general to have process B deleting entries while A is running?

Which strategy is more consistent: purge1/1 or purge2/1?

Best
/Frank
Reply | Threaded
Open this post in threaded view
|

Re: ConETS table consistency while entries are deleted from 2 processes

Jesper Louis Andersen-2
On Sun, Dec 8, 2019 at 9:29 AM Frank Muller <[hidden email]> wrote:
Hi all


Lets assume a public ETS table of type ‘ordered_set’.


The ETS documentation defines "safe traversal". Traversal of `ordered_set` tables are always safe. That is, they will do the "right thing" if updates are done while traversal happens.

For tables of the other types, you either do the whole traversal in one call, or you use the safe_fixtable/2 call to fix the table while traversal is happening.

The underlying reason is that the table has an order. This means we can always drill down into the table and find the place we "were" so to speak by utilizing this order. In the case of e.g., `set` tables, we don't a priori have an order, so we are encoding something like a hash bucket and the element we reached. But if that element is gone, we don't know where we were, and there is no other structural information to go by. The fixtable calls basically postpones changes to the table in a separate buffer until the traversal is done, then replays the buffer on the table. This ensures the core table is traversal-stable. Requests to the table first checks the buffer before checking the main core table[0]

[0] This model is essentially a 2 level log-structured-merge-tree (LSM tree) variant.

--
J.
Reply | Threaded
Open this post in threaded view
|

Re: ConETS table consistency while entries are deleted from 2 processes

Frank Muller
Crystal clear Jesper, thanks.

is purge1/1 valid/correct?

/Frank

On Sun, Dec 8, 2019 at 9:29 AM Frank Muller <[hidden email]> wrote:
Hi all


Lets assume a public ETS table of type ‘ordered_set’.


The ETS documentation defines "safe traversal". Traversal of `ordered_set` tables are always safe. That is, they will do the "right thing" if updates are done while traversal happens.

For tables of the other types, you either do the whole traversal in one call, or you use the safe_fixtable/2 call to fix the table while traversal is happening.

The underlying reason is that the table has an order. This means we can always drill down into the table and find the place we "were" so to speak by utilizing this order. In the case of e.g., `set` tables, we don't a priori have an order, so we are encoding something like a hash bucket and the element we reached. But if that element is gone, we don't know where we were, and there is no other structural information to go by. The fixtable calls basically postpones changes to the table in a separate buffer until the traversal is done, then replays the buffer on the table. This ensures the core table is traversal-stable. Requests to the table first checks the buffer before checking the main core table[0]

[0] This model is essentially a 2 level log-structured-merge-tree (LSM tree) variant.

--
J.
Reply | Threaded
Open this post in threaded view
|

Re: ConETS table consistency while entries are deleted from 2 processes

Jesper Louis Andersen-2
I think both would work.

There is also the possibility B sends a delete message to A which then deletes keys. This forces linearization in A.

How many concurrent deletes you have sort-of determines if this strategy is more viable, and also in which direction the system might go in the future. If you only have a handful deletes I would just factor it through a single process since a lot of things are easier that way, typically.

In any case, your Erlang/OTP version matter here. For 22.0 and onwards, you can set `{write_concurrency, true}` for ordered_set tables and expect an improvement as core count increases. Before, there is no effect and you are essentially grabbing a table lock for the whole table whenever you want to issue a write (i.e. delete). So before 22, concurrent deletes yields no performance improvement, which argues a messaging model might be simpler to reason about[0].

[0] Why? Because there is an invariant which is easy to maintain: if the process is purging, messages wait in the mailbox. So no other deletes can happen in between. If the process is deleting, it cannot be purging.



On Sun, Dec 8, 2019 at 3:07 PM Frank Muller <[hidden email]> wrote:
Crystal clear Jesper, thanks.

is purge1/1 valid/correct?

/Frank

On Sun, Dec 8, 2019 at 9:29 AM Frank Muller <[hidden email]> wrote:
Hi all


Lets assume a public ETS table of type ‘ordered_set’.


The ETS documentation defines "safe traversal". Traversal of `ordered_set` tables are always safe. That is, they will do the "right thing" if updates are done while traversal happens.

For tables of the other types, you either do the whole traversal in one call, or you use the safe_fixtable/2 call to fix the table while traversal is happening.

The underlying reason is that the table has an order. This means we can always drill down into the table and find the place we "were" so to speak by utilizing this order. In the case of e.g., `set` tables, we don't a priori have an order, so we are encoding something like a hash bucket and the element we reached. But if that element is gone, we don't know where we were, and there is no other structural information to go by. The fixtable calls basically postpones changes to the table in a separate buffer until the traversal is done, then replays the buffer on the table. This ensures the core table is traversal-stable. Requests to the table first checks the buffer before checking the main core table[0]

[0] This model is essentially a 2 level log-structured-merge-tree (LSM tree) variant.

--
J.


--
J.
Reply | Threaded
Open this post in threaded view
|

Re: ConETS table consistency while entries are deleted from 2 processes

Frank Muller
Got it. I’m on the latest 22.x and gonna go with purge1 then.

/Frank

I think both would work.

There is also the possibility B sends a delete message to A which then deletes keys. This forces linearization in A.

How many concurrent deletes you have sort-of determines if this strategy is more viable, and also in which direction the system might go in the future. If you only have a handful deletes I would just factor it through a single process since a lot of things are easier that way, typically.

In any case, your Erlang/OTP version matter here. For 22.0 and onwards, you can set `{write_concurrency, true}` for ordered_set tables and expect an improvement as core count increases. Before, there is no effect and you are essentially grabbing a table lock for the whole table whenever you want to issue a write (i.e. delete). So before 22, concurrent deletes yields no performance improvement, which argues a messaging model might be simpler to reason about[0].

[0] Why? Because there is an invariant which is easy to maintain: if the process is purging, messages wait in the mailbox. So no other deletes can happen in between. If the process is deleting, it cannot be purging.



On Sun, Dec 8, 2019 at 3:07 PM Frank Muller <[hidden email]> wrote:
Crystal clear Jesper, thanks.

is purge1/1 valid/correct?

/Frank

On Sun, Dec 8, 2019 at 9:29 AM Frank Muller <[hidden email]> wrote:
Hi all


Lets assume a public ETS table of type ‘ordered_set’.


The ETS documentation defines "safe traversal". Traversal of `ordered_set` tables are always safe. That is, they will do the "right thing" if updates are done while traversal happens.

For tables of the other types, you either do the whole traversal in one call, or you use the safe_fixtable/2 call to fix the table while traversal is happening.

The underlying reason is that the table has an order. This means we can always drill down into the table and find the place we "were" so to speak by utilizing this order. In the case of e.g., `set` tables, we don't a priori have an order, so we are encoding something like a hash bucket and the element we reached. But if that element is gone, we don't know where we were, and there is no other structural information to go by. The fixtable calls basically postpones changes to the table in a separate buffer until the traversal is done, then replays the buffer on the table. This ensures the core table is traversal-stable. Requests to the table first checks the buffer before checking the main core table[0]

[0] This model is essentially a 2 level log-structured-merge-tree (LSM tree) variant.

--
J.


--
J.