Inverse the order of writes on create transition #350

arthurnn · 2019-06-12T20:20:44Z

Context

Dependabot is using statesman, and we are running the Dependabot service using MySQL at GitHub.
After some load testing the system, we found out some increasing number of deadlocks coming from states man. This fixed the problem for us.

This is a lock-free solution for #228. Probably also fixes #206

Short problem description

When we were trying to call ar_model.transition_to!, we would get a Deadlock error if the system was under pressure. (lots of concurrent transitions happening at the same time)

Detailed problem and root cause analysis

Some context

When doing a transition_to! statesman will do, mainly, two operations in the database, inside the same transaction:

Update the old transitions to mark them as non-most-recent
Insert the new transition with a most_recent set to TRUE.

Also, the transitions table usually have two unique indexes, (parent_id,sort_key) and (parent_id,most_recent), the second index is there to guarantee we only have one most_recent transition for the parent entry. Thus we need the update before the insert.

Problem

MySQL default transaction isolation level is REPEATABLE READ and that's what we use at Dependabot/GitHub. It states:

This is the default isolation level for InnoDB. Consistent reads within the same transaction read the snapshot established by the first read.

What means is if in a loop, we do the same SELECT within a db transaction, even if other clients have committed data between the runs, it will, ALWAYS, see the first results it saw the first time.
That is also respected when doing writes (Update/Delete). so UPDATE transitions SET most_recent=NULL where parent_id=1 AND most_recent=true; will put an exclusive lock on the row for that unique index, as it cannot allow other transactions to change the data. However, if there is no row to update, MySQL will have to create a next-key lock, to also prevent others from changing this data, as the transaction's view of the snapshot didn't include any rows, as the UPDATE returned 0 rows changed.
The issue is, two independent transactions can put the next-key lock on the table (even if they reference different columns values on the index), and when it tries to do the next operation, the insert, it will lock, waiting for the next-key lock to be released. Therefore, if two updates happen first, and two inserts after, they will deadlock. (for better understanding see Simulation 1)
However, if the Update would have changed at least one row, there would be no locking, as for REPEATABLE READ that would be our current snapshot of the data. Thus no need for a gap locking.
See

If id is not indexed or has a nonunique index, the statement does lock the preceding gap.

This is also explained on this 2003 issue, by the people that wrote InnoDB, and on a few articles: 1 2

Solution

There are a few different ways to fix this. The easiest is just to (1)retry on deadlock, another one,(2) would be to change the transaction isolation level for that transaction to READ COMMITTED, which means SELECTS within the transaction are not consistent, and will always return committed data, thus, MySQL will not create the gap lock, as it is safe to update without the lock.
The problem of 1 is that we would still need to limit the number of retries, and eventually can still have the deadlocks, and number 2 would require us to always use ROW based replication as statement base replication wants REPEATABLE READ. [Also, not advised to change the transaction isolation level inside a library]
Instead, we can tackle the root problem: First, I thought in doing a select, and if transition data had to be updated do the update. However, that is race prone.
The actual fix is, re-order the operations, and always do the insert before, so we know the next Update will at least touch one row, and make our latest transition most_recent after. Thus, no next-key lock will happen and less contention will be created.

To simulate this:

Simulation 1 (SQL)

A and B are different MySQL clients:

CREATE TABLE `transitions` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `to_state` varchar(40) NOT NULL,
  `sort_key` int(11) NOT NULL,
  `parent_id` bigint(20) NOT NULL,
  `most_recent` tinyint(1) DEFAULT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `index_parent_sort` (`parent_id`,`sort_key`),
  UNIQUE KEY `index_parent_most_recent` (`parent_id`,`most_recent`)
) ENGINE=InnoDB AUTO_INCREMENT=4 DEFAULT CHARSET=utf8mb4

A: START TRANSACTION;
B: START TRANSACTION;
A: UPDATE transitions SET most_recent=NULL where parent_id=1 AND most_recent=true;
B: UPDATE transitions SET most_recent=NULL where parent_id=42 AND most_recent=true;
A: INSERT INTO transitions(to_state, sort_key, parent_id, most_recent) values ('pending', 10, 1, TRUE);
B: INSERT INTO transitions(to_state, sort_key, parent_id, most_recent) values ('pending', 10, 42, TRUE);

cc @greysteil @hmarr

StatesMan will update the old transitions to `most_recent: nil` and then insert the new transition as `most_recent: true`. However that can cause deadlocks on MySQL when running concurrent state transitions. On the update, MySQL will hold a gap lock to the unique indexes there are, so other transactions cannot insert. After two updates on the most_recent and two inserts, the second insert will fail with a deadlock. For more explanation see the PR description that includes this commit.

greysteil · 2019-06-12T22:31:06Z

@lawrencejones / @Sinjo - thought you might be interested in this one.

lawrencejones · 2019-06-13T05:00:21Z

It's great what you find when you start running this stuff on different db engines! I hadn't considered MySQL and it's default of repeatable reads with this type of operation but it makes sense it won't be healthy for throughput.

I think this probably makes sense but it does add a query to the transition operation which will have a measurable impact on people relying on low latency transitions. I'll put some time aside today to consider the full scope of that impact and give this a proper review.

danwakefield · 2019-06-13T08:09:32Z

sqlite, postgres and mysql all support upsert, at least in recent versions. Could we check for this and use it to update both of the columns simultaneously? We'd keep the current proposal as a fallback to maintain compatibility.

…

On Thu, 13 Jun 2019, 06:00 Lawrence Jones, ***@***.***> wrote: It's great what you find when you start running this stuff on different db engines! I hadn't considered MySQL and it's default of repeatable reads with this type of operation but it makes sense it won't be healthy for throughput. I think this probably makes sense but it does add a query to the transition operation which will have a measurable impact on people relying on low latency transitions. I'll put some time aside today to consider the full scope of that impact and give this a proper review. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#350?email_source=notifications&email_token=AAFC7WXBUYGMUQTTIPXSST3P2HH6NA5CNFSM4HXRCJY2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODXSQP4Y#issuecomment-501549043>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAFC7WQEVRJJUK7KXNQAG6DP2HH6NANCNFSM4HXRCJYQ> .

lawrencejones · 2019-06-13T08:19:25Z

Using upsert is going to be really difficult through the AR layer- I think you'd need to insert the new transition, catch the conflict and write a fallback that both updates the conflicting transition and retries your initial insert. You'd also catch genuine race conflicts that should throw exceptions too, the sort you'd normally want to recover from with retry_conflicts.

Doing a general tidy-up of the statesman now to get a local development environment going, then I'm going to breakdown what SQL is actually being run here to be clear on how the behaviour will change. Will drop an update here when I've got something!

@arthurnn

gocardless#350 @arthurnn opened gocardless#350 to reduce the impact of Statesman taking gap locks when using MySQL. The crux of the issue is that MySQL's implementation of REPEATABLE READ can take wide locks when an update touches no rows, which happens frequently on the first transition of Statesman. By first creating the new transition, we can avoid issuing an update that will take the large gap lock. This order of queries meant we added an additional query to the transition step which could impact people who rely on low-latency Statesman transitions. This commit is another take on the same approach that collapses two queries into one, by taking the update of the old and new transition's most_recent column and updating them together. It's slightly janky but if robust, would be a good alternative to avoid additional latency.

lawrencejones · 2019-06-13T11:32:28Z

Hey @arthurnn, I had a think about this and have put together arthurnn#1 that I'd love your feedback on. It's in the same spirit as your PR but removes the additional query which could be nice for those who care.

The description should explain everything but let me know if I can be clearer somewhere.

arthurnn · 2019-06-13T14:45:56Z

@lawrencejones Pretty cool what you did on arthurnn#1, I like the approach of reusing the UPDATE to change the most_recent. Indeed is more complex. I don't mind the complexity though, however, not sure what the maintainers of the gem will think.
To be completely honest, I don't see the extra query(UPDATE) as a problem. It is equivalent to your UPDATE with the OR, the only thing, it adds an extra network call, and an exclusive lock for a bit longer.
Anyways, I am happy with either solution.

I am glad to merge your PR into my branch, so it will update this PR. just let me know.

@danwakefield I thought about using an upsert, but we still need to update the old transitions to change the most_recent, thus I could not find a working solution using it.

danwakefield · 2019-06-13T15:03:03Z

So because of next_sort_key, @last_transition contains its namesake until the new transition overwrites it after the save. This would give you access to both ids allowing you force an insert conflict.

But the UPDATE proposed by @lawrencejones makes sense and I think we are happy to add the complexity in order to support MySQL fully while being as performant as possible.

lawrencejones · 2019-06-13T15:11:27Z

the only thing, it adds an extra network call, and an exclusive lock for a bit longer

I suspect @greysteil has already mentioned this, but we use statesman at GoCardless for a load of our application code. In several places we transactionally transition many models and while the database queries are super-fast, the latency to the database dominates the query runtime. Consequently we'd much prefer to avoid adding extra hops if possible!

I am glad to merge your PR into my branch, so it will update this PR. just let me know.

Let's do it!

Once we have that PR merged, we're happy to try this out in our staging environment to double check everything is sound. If things look good we'll

Lock-lesser transitions without additional queries

arthurnn · 2019-06-13T16:39:08Z

Interesting note on the db latency. 👍

merged.

arthurnn · 2019-06-13T16:39:28Z

will fix rubocop. one min

arthurnn · 2019-06-13T18:36:34Z

or wont work on rails <5 =/
Also, Statesman::Adapters::ActiveRecord with a namespaced model behaves like an adapter #create the new transition with a previous transition sort_key now fails, as the UPDATE won't raise an error now, because it is an update_all

lawrencejones · 2019-06-14T14:46:30Z

A note to say I'm not ignoring this, just busy today. Will get to fixing this next week.

lawrencejones · 2019-06-21T15:36:42Z

A note to say I didn't get the time to look at things this week but intend to next. Hope it's not impacting anyone!

greysteil · 2019-07-02T16:56:10Z

@lawrencejones gentle reminder on this one. @arthurnn is now on paternity leave so won't be responsive anymore 😢

lawrencejones · 2019-07-03T07:14:15Z

Ahh that's really annoying, I missed getting to this before going on holiday last week.

My general plan was to identify an alternative to using Arel OR, or maybe just waiting for Rails 6 to be released at which point we can deprecate support for older versions that don't support that functionality.

I think the approach here (as in, the mechanics of how the SQL now work) is the correct one, just need to find a way to make tests pass. I'm going to be pressed for time this week (it's roadmap week internally) so would welcome any adjustments you'd want to make @greysteil?

greysteil · 2019-07-03T09:26:44Z

lib/statesman/adapters/active_record.rb

+      # previous transitions.
+      def update_most_recents(most_recent_id)
+        transitions = transitions_for_parent
+        last_or_current = transitions.where(id: most_recent_id).or(


Equivalent SQL should be:

transitions.where("#{transition_class.table_name}.id = #{most_recent_id} OR #{transition_class.table_name}.most_recent = #{::ActiveRecord::Base.connection.quote(true)}")

The interpolation should be safe, too, since everything's from statesman internals.

We use a similar approach in Statesman::Adapters::ActiveRecordQueries.

Can PR it if you're 👍 on the approach.

Absolutely- please do just add it to this PR!

Slightly concerned about table_name (if the table name is hyphenated, then I think this will break depending on what database you use?) but if we use it elsewhere then it's unlikely to be something people rely on.

Think we use it elsewhere, but no reason not to quote the shit out of it 🤷‍♂

Better to use AREL in this case, to be more safe and database agnostic.

@arthurnn

#350 @arthurnn opened #350 to reduce the impact of Statesman taking gap locks when using MySQL. The crux of the issue is that MySQL's implementation of REPEATABLE READ can take wide locks when an update touches no rows, which happens frequently on the first transition of Statesman. By first creating the new transition, we can avoid issuing an update that will take the large gap lock. This order of queries meant we added an additional query to the transition step which could impact people who rely on low-latency Statesman transitions. This commit is another take on the same approach that collapses two queries into one, by taking the update of the old and new transition's most_recent column and updating them together. It's slightly janky but if robust, would be a good alternative to avoid additional latency.

gabrielbaldao · 2019-12-16T18:22:16Z

lib/statesman/adapters/active_record.rb

+      # indexes. By doing the conditioning on the column, rather than Rails' opinion of
+      # whether the database supports partial indexes, we're robust to DBs later adding
+      # support for partial indexes.
+      def not_most_recent_value


What do you think about change this method to

def not_most_recent_value false if transition_class.columns_hash["most_recent"].null == false end

jurre · 2020-04-22T09:00:09Z

Hey hey, we're still running into this issue, @arthurnn has switched teams but I'm happy to help wherever I can to get this over the line.

@arthurnn

#350 @arthurnn opened #350 to reduce the impact of Statesman taking gap locks when using MySQL. The crux of the issue is that MySQL's implementation of REPEATABLE READ can take wide locks when an update touches no rows, which happens frequently on the first transition of Statesman. By first creating the new transition, we can avoid issuing an update that will take the large gap lock. This order of queries meant we added an additional query to the transition step which could impact people who rely on low-latency Statesman transitions. This commit is another take on the same approach that collapses two queries into one, by taking the update of the old and new transition's most_recent column and updating them together. It's slightly janky but if robust, would be a good alternative to avoid additional latency.

@arthurnn

#350 @arthurnn opened #350 to reduce the impact of Statesman taking gap locks when using MySQL. The crux of the issue is that MySQL's implementation of REPEATABLE READ can take wide locks when an update touches no rows, which happens frequently on the first transition of Statesman. By first creating the new transition, we can avoid issuing an update that will take the large gap lock. This order of queries meant we added an additional query to the transition step which could impact people who rely on low-latency Statesman transitions. This commit is another take on the same approach that collapses two queries into one, by taking the update of the old and new transition's most_recent column and updating them together. It's slightly janky but if robust, would be a good alternative to avoid additional latency.

@arthurnn

* Inverse the order of writes on statesman transitions StatesMan will update the old transitions to `most_recent: nil` and then insert the new transition as `most_recent: true`. However that can cause deadlocks on MySQL when running concurrent state transitions. On the update, MySQL will hold a gap lock to the unique indexes there are, so other transactions cannot insert. After two updates on the most_recent and two inserts, the second insert will fail with a deadlock. For more explanation see the PR description that includes this commit. * Make sure the initial most_recent state is false/nil * Lock-lesser transitions without additional queries #350 @arthurnn opened #350 to reduce the impact of Statesman taking gap locks when using MySQL. The crux of the issue is that MySQL's implementation of REPEATABLE READ can take wide locks when an update touches no rows, which happens frequently on the first transition of Statesman. By first creating the new transition, we can avoid issuing an update that will take the large gap lock. This order of queries meant we added an additional query to the transition step which could impact people who rely on low-latency Statesman transitions. This commit is another take on the same approach that collapses two queries into one, by taking the update of the old and new transition's most_recent column and updating them together. It's slightly janky but if robust, would be a good alternative to avoid additional latency. * fmt * Replace Arel#or with raw SQL * Attempt to fix typecasting * Fix MySQL issue with ordered updates This commit first refactors the construction of transition SQL statements to use Arel. This is safer and hopefully more readable than constructing large SQL statements using strings. It also fixes a bug with transition updates where MySQL would throw index violations. This was caused by MySQL validating index constraints across a partially applied update, where Statesman would set the latest transition's most_recent = 't' before unsetting the previous. * Smooth-over breaking API change in Arel rails/rails@7508284 When merged with Rails core, Arel removed an initialisation parameter that was unused in all but a few of the Arel features. For now, provide a helper local to the ActiveRecord adapter that can construct Manager classes independent of the API change. * Handle transitions differently for MySQL To avoid a gap lock with MySQL, first insert the new transition with most_recent=false and then flip the values for the latest two transitions in order. * MySQL specific gaplock protection is configurable Instead of depending on the name of the ActiveRecord adapter to identify if the database is MySQL, gaplock protection is configurable, as suggested by @jurre on #399 * Loosen dependency on pg gem This reflects a recent change in Rails (rails/rails@592358e) Co-authored-by: Arthur Neves <[email protected]> Co-authored-by: Lawrence Jones <[email protected]> Co-authored-by: Grey Baker <[email protected]>

arthurnn · 2020-05-20T17:35:47Z

I think this has being merged in master already right?

thom-oman · 2020-05-20T17:37:15Z

@arthurnn yes, and we released it yesterday. this should've been closed, will close now.

@arthurnn

* Inverse the order of writes on statesman transitions StatesMan will update the old transitions to `most_recent: nil` and then insert the new transition as `most_recent: true`. However that can cause deadlocks on MySQL when running concurrent state transitions. On the update, MySQL will hold a gap lock to the unique indexes there are, so other transactions cannot insert. After two updates on the most_recent and two inserts, the second insert will fail with a deadlock. For more explanation see the PR description that includes this commit. * Make sure the initial most_recent state is false/nil * Lock-lesser transitions without additional queries gocardless#350 @arthurnn opened gocardless#350 to reduce the impact of Statesman taking gap locks when using MySQL. The crux of the issue is that MySQL's implementation of REPEATABLE READ can take wide locks when an update touches no rows, which happens frequently on the first transition of Statesman. By first creating the new transition, we can avoid issuing an update that will take the large gap lock. This order of queries meant we added an additional query to the transition step which could impact people who rely on low-latency Statesman transitions. This commit is another take on the same approach that collapses two queries into one, by taking the update of the old and new transition's most_recent column and updating them together. It's slightly janky but if robust, would be a good alternative to avoid additional latency. * fmt * Replace Arel#or with raw SQL * Attempt to fix typecasting * Fix MySQL issue with ordered updates This commit first refactors the construction of transition SQL statements to use Arel. This is safer and hopefully more readable than constructing large SQL statements using strings. It also fixes a bug with transition updates where MySQL would throw index violations. This was caused by MySQL validating index constraints across a partially applied update, where Statesman would set the latest transition's most_recent = 't' before unsetting the previous. * Smooth-over breaking API change in Arel rails/rails@7508284 When merged with Rails core, Arel removed an initialisation parameter that was unused in all but a few of the Arel features. For now, provide a helper local to the ActiveRecord adapter that can construct Manager classes independent of the API change. * Handle transitions differently for MySQL To avoid a gap lock with MySQL, first insert the new transition with most_recent=false and then flip the values for the latest two transitions in order. * MySQL specific gaplock protection is configurable Instead of depending on the name of the ActiveRecord adapter to identify if the database is MySQL, gaplock protection is configurable, as suggested by @jurre on gocardless#399 * Loosen dependency on pg gem This reflects a recent change in Rails (rails/rails@592358e) Co-authored-by: Arthur Neves <[email protected]> Co-authored-by: Lawrence Jones <[email protected]> Co-authored-by: Grey Baker <[email protected]>

arthurnn added 2 commits June 12, 2019 16:03

Make sure the initial most_recent state is false/nil

753649d

arthurnn force-pushed the arthurnn/deadlocks branch from b181139 to 753649d Compare June 12, 2019 20:59

lawrencejones self-requested a review June 13, 2019 07:35

lawrencejones mentioned this pull request Jun 13, 2019

Lock-lesser transitions without additional queries arthurnn/statesman#1

Merged

Merge pull request #1 from gocardless/lawrence-deadlocks

b7cc669

Lock-lesser transitions without additional queries

fmt

353f1b1

greysteil reviewed Jul 3, 2019

View reviewed changes

greysteil mentioned this pull request Jul 3, 2019

Arthurnn/deadlocks #353

Closed

gabrielbaldao reviewed Dec 16, 2019

View reviewed changes

thom-oman mentioned this pull request Apr 29, 2020

Handle transitions differently for MySQL #399

Merged

thom-oman closed this May 20, 2020

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Inverse the order of writes on create transition #350

Inverse the order of writes on create transition #350

arthurnn commented Jun 12, 2019

greysteil commented Jun 12, 2019

lawrencejones commented Jun 13, 2019

danwakefield commented Jun 13, 2019 via email

lawrencejones commented Jun 13, 2019

lawrencejones commented Jun 13, 2019

arthurnn commented Jun 13, 2019

danwakefield commented Jun 13, 2019 •

edited

Loading

lawrencejones commented Jun 13, 2019

arthurnn commented Jun 13, 2019

arthurnn commented Jun 13, 2019

arthurnn commented Jun 13, 2019 •

edited

Loading

lawrencejones commented Jun 14, 2019 •

edited

Loading

lawrencejones commented Jun 21, 2019

greysteil commented Jul 2, 2019

lawrencejones commented Jul 3, 2019

greysteil Jul 3, 2019

lawrencejones Jul 3, 2019

greysteil Jul 3, 2019

dmitry Jul 4, 2019

gabrielbaldao Dec 16, 2019 •

edited

Loading

jurre commented Apr 22, 2020

arthurnn commented May 20, 2020

thom-oman commented May 20, 2020

Inverse the order of writes on create transition #350

Inverse the order of writes on create transition #350

Conversation

arthurnn commented Jun 12, 2019

Context

Short problem description

Detailed problem and root cause analysis

Some context

Problem

Solution

Simulation 1 (SQL)

greysteil commented Jun 12, 2019

lawrencejones commented Jun 13, 2019

danwakefield commented Jun 13, 2019 via email

lawrencejones commented Jun 13, 2019

lawrencejones commented Jun 13, 2019

arthurnn commented Jun 13, 2019

danwakefield commented Jun 13, 2019 • edited Loading

lawrencejones commented Jun 13, 2019

arthurnn commented Jun 13, 2019

arthurnn commented Jun 13, 2019

arthurnn commented Jun 13, 2019 • edited Loading

lawrencejones commented Jun 14, 2019 • edited Loading

lawrencejones commented Jun 21, 2019

greysteil commented Jul 2, 2019

lawrencejones commented Jul 3, 2019

greysteil Jul 3, 2019

Choose a reason for hiding this comment

lawrencejones Jul 3, 2019

Choose a reason for hiding this comment

greysteil Jul 3, 2019

Choose a reason for hiding this comment

dmitry Jul 4, 2019

Choose a reason for hiding this comment

gabrielbaldao Dec 16, 2019 • edited Loading

Choose a reason for hiding this comment

jurre commented Apr 22, 2020

arthurnn commented May 20, 2020

thom-oman commented May 20, 2020

danwakefield commented Jun 13, 2019 •

edited

Loading

arthurnn commented Jun 13, 2019 •

edited

Loading

lawrencejones commented Jun 14, 2019 •

edited

Loading

gabrielbaldao Dec 16, 2019 •

edited

Loading