Hints/thoughts on approaches to challenge 6 - how to implement g0 and make Maelstrom happy

Yesterday I was walking through the city with my friend Denis to the Georgian restaurant (pub) and we were discussing g0 while on the go. The discussion ended up thinking of how PostgreSQL actually handles this anomaly.

Shall you know that there is a Hermitage project by Martin Klepmann (GitHub - ept/hermitage: What are the differences between the transaction isolation levels in databases? This is a suite of test cases which differentiate isolation levels.) that actually demonstrates all of them for various databases. The one I was looking for was hermitage/postgres.md at master · ept/hermitage · GitHub. The question was about how PG handles cases when a conflicting transaction commits in the middle of a ww-conflict. So, it turns out PostgreSQL for g0

postpones the conflicting transaction like the following (at least at READ COMMITTED):

begin; set transaction isolation level read committed; -- T1
begin; set transaction isolation level read committed; -- T2

update test set value = 11 where id = 1; -- T1
update test set value = 12 where id = 1; -- T2, BLOCKS
update test set value = 21 where id = 2; -- T1
commit; -- T1. This unblocks T2

select * from test; -- T1. Shows 1 => 11, 2 => 21
update test set value = 22 where id = 2; -- T2
commit; -- T2

select * from test; -- either. Shows 1 => 12, 2 => 22

I am guilty of taking a different approach to the implementation of the detection and prevention of this anomaly. Basically what I did and what can also be done in an alternative way is:

  • we detect conflicts as we go on creating new tuples (basically on key writes) by checking through the present uncommitted tuples in the key
  • we abort only IF there is an impossible conflict - only when we have found actual Dirty Write, not when we are meeting the first ww-edge.
  • the magic is that to make the commit consistent we commit transaction writes in a single point in time either before or all after. anyway, there is some freedom how you can pick the commit time point but the idea is IF you are reading a snapshot that is formed at the moment of the tx start then you can basically commit writes in that exact point and have a somewhat serializable schedule. but we are not doing serializability here so whatever. just put your writes together on commit.

My approach is worse because it requires an effort to do consistent commits for transactions that had conflicting edges and were committed in the middle. Then we actually abort transactions that could avoid that. Another concern is that Maelstrom does not like Aborts.

But what it can do perfectly fine is to:

wait a little bit until your postponed transaction will be committed. This must be a perfect approach to that problem. Just mimic what normal databases do like a PG and you will be good.

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.