MySQL: "Deadlock found..." when creating a list item at position

[nmoadev]

Hello,

I've come across an issue where concurrent requests to create items in a list at a specific position leads to sporadic, but reproducible errors from MySQL like the following:

Mysql2::Error: Deadlock found when trying to get lock; try restarting transaction: INSERT INTO `todo_items` (`description`, `position`, `todo_list_id`) VALUES ('Thread5_Item0', 1, 1)

Reproduction Code

I can reproduce this issue with code like the following.

todo_list = TodoList.create(name: "The List")

threads = Array.new(THREAD_COUNT) do |i|
  Thread.new do
    LOOP_COUNT.times do |j|
      # Eventually, this line will raise ActiveRecord::Deadlocked
      item = TodoItem.create(description: "Thread#{i}_Item#{j}", todo_list: todo_list, position: 1)
    end
  end
end

threads.each {|t| t.join }

For a complete, runnable example, see this Gist: https://gist.github.com/nmoadev/0a078741e944ac5e5eec7fa80e6848f9

Gem Versions

ruby '2.5.3'
gem 'mysql2', '~> 0.5.2'
gem 'activerecord', '~> 5.2.2'
gem 'acts_as_list', '~> 0.9.3'

MySQL Version is 5.7.25

I think it may be possible to avoid the deadlock with more pessimistic locking, and would be willing to investigate a fix.

I think this issue is related to #235.

[brendon]

Hi @nmoadev, yes please, we'd love you to look into this further :) I think it's got something to do with table scans locking rows on the table, and perhaps sometimes we're scanning the table in reverse order leading to deadlocks?

[nmoadev]

Hi @brendon,

I read through the "Contributing to acts_as_list" notes at the end of the README and wanted to check:

Does this project have a Contributor License Agreement or something similar?

[brendon]

Hi @nmoadev, not that I'm aware of, but I'm not really savvy on such things. @swanandp might be able to shed more light. Why do you ask? :)

[nmoadev]

Thanks for getting back to me. I'm looking into this issue as part of a work project, so I need to know the licensing arrangements for any contributions I would make.

[brendon]

Sounds good. What would be an idea license for you?

[nmoadev]

Other projects that I'm aware of use CLAs like ones prepared by this tool (http://contributoragreements.org/ca-cla-chooser/) or something like the Microsoft CLA (https://cla.opensource.microsoft.com/SharePoint/sp-dev-gdpr-activity-hub).

Of course as the project maintainers, it's for you to decide what's the appropriate thing to do for this project. I found the FAQ at http://contributoragreements.org/faq.html pretty helpful to understand the what and why of CLAs.

[brendon]

Looks like it requires an infrastructure to accept signings etc... sounds a bit too overkill for a little project like this. Will this be a show-stopper for you if we don't do it?

[nmoadev]

Nope, the lack of CLA is not a problem. :)

I actually think that the "solution" to this issue won't be a code change to the gem. The techniques that one can use to mitigate the frequency of deadlocks are very context-dependent; what works well in one app may not be appropriate for another. I'll share a write up of what I've found soon. Maybe it will be a useful bit of documentation for the gem.

[brendon]

Thanks @nmoadev :D I'm glad RE the CLA :D

RE the deadlocking, I think that's what we've come to realise over the years. It would be great if we could black-box the updating so it didn't cause issues elsewhere with deadlocks but I guess by their very nature it's difficult because we don't control the other code that deadlocks with us. The advisory lock concept seemed to be the best way forward, but it sounds like we need to refactor things in this gem to reduce the callbacks to 1. See: #325

[nmoadev]

@brendon Yep, I agree with that conclusion. I went down a similar train of thought as #325 but didn't want to embark on such a large endeavor.

I wrote up the following set of suggestions / examples for someone using the gem. Could these part of the documentation for the gem? I thought it might save someone else some pain if they face the same issue:

1) Use the Most Concise API

One easy way to reduce deadlocks is to use the most concise gem API available. The more concise API results in one transaction instead of two, and it issues fewer SQL statements. Issuing fewer statements tends to lead to faster transactions. Faster transactions are less likely to deadlock.

# Good
TodoItem.create(todo_list: todo_list, position: 1)

# Bad
item = TodoItem.create(todo_list: todo_list)
item.insert_at(1)

2) Rescue then Retry

Deadlocks are always a possibility when updating tables rows concurrently. The general advice from MySQL documentation is to catch these errors and simply retry the transaction; it will probably succeed on another attempt. (see How to Minimize and Handle Deadlocks) Retrying transactions sounds simple, but there are alot of details that need to be chosen on a case-by-case basis: How many retry attempts should be made? Should there be a wait time between attemps? What other statements were in the transaction that got rolled back?

This a simple example of rescuing from deadlock and retrying the operation:

• ActiveRecord::Deadlocked is avilable in Rails >= 5.1.0.
• If you have Rails < 5.1.0, you will need to rescue ActiveRecord::StatementInvalid and check #cause.

  attempts_left = 2
  while attempts_left > 0
    attempts_left -= 1
    begin
      TodoItem.transaction do
        TodoItem.create(todo_list: todo_list, position: 1)
      end
      attempts_left = 0
    rescue ActiveRecord::Deadlocked
      raise unless attempts_left > 0
    end
  end

You can also use the approach suggested in this StackOverflow post:
https://stackoverflow.com/questions/4027659/activerecord3-deadlock-retry

3) Lock Parent Record

In additon to reacting to deadlocks, it is possible to reduce their frequency with more pessimistic locking. This approach uses the parent record as a mutex for the entire list. This kind of locking is very effective at reducing the frequency of deadlocks while updating list items. However, there are some things to keep in mind:

• This locking pattern needs to be used around every call that modifies the list; even if it does not reorder list items.
• This locking pattern effectively serializes operations on the list. The throughput of operations on the list will decrease.
• Locking the parent record may lead to deadlock elsewhere if some other code also locks the parent table.

Example:

todo_list = TodoList.create(name: "The List")
todo_list.with_lock do
  item = TodoItem.create(description: "Buy Groceries", todo_list: todo_list, position: 1)
end

[brendon]

Thanks @nmoadev, that's some great advice :) I'm happy to add a section for that to the README with that if you want. Would you mind doing up a quick PR? Be sure to add a line to the changelog too :)

[nmoadev]

Yep I'll make up a PR!

[nmoadev]

Considering this closed with #344

[brendon]

Indeed :) Thanks @nmoadev :)