[LRUG] Scoping sequences to a parent

[Andrew Stewart]

Hello LRUG,

Many thanks to everyone who replied.  With your ideas I have found not one but two solutions.

Both solutions use the database.  Redis would work too but it's not in my stack quite yet and I prefer not to add an unnecessary dependency.

> I have a Rails app using MySQL.  In the app I have a parent model with children and I would like to number the children scoped to the parent – much as GitHub issues are numbered by repo.

I should have clarified that although users are allowed to delete children, I don't want to reuse child sequence numbers.  I.e. once a child sequence number has been allocated it cannot be reused for a different child even if the original has been deleted.

This rules out deriving child sequence numbers by counting the children or finding the children's maximum sequence number and adding 1.  Instead I need to maintain a high-water-mark sequence number separately from the children's numbers.

> For the past 8 years each parent model has held a counter.  In an after_create callback in the child model, it calls a method on the parent which increments the counter and returns it; the child updates itself to store that value.
> 
> This generally works but I've noticed I get the odd deadlock and uniqueness violation (there's a uniqueness constraint on the child for [parent_id, number]).  These errors crop up when people are importing large numbers of children into the parent's collection.

Here is the initial code:

    class Parent < ActiveRecord::Base
      has_many :children

      def next_child_number
        update_column :child_number, (child_number + 1)
        child_number
      end
    end

    class Child < ActiveRecord::Base
      belongs_to :parent

      after_create :set_number

      def set_number
        n = parent.next_child_number
        update_column :friendly_id, "#{other_stuff}-#{n}"
        update_column :number, n
      end
    end

Additionally the children table has a uniqueness constraint on [parent_id, friendly_id].

I was able to reproduce the deadlock by changing Parent#next_child_number as follows:

    def next_child_number
      n = child_number
      sleep 5
      update_column :child_number, (n + 1)
      child_number
    end

– and then opening two consoles, running the following command in the first and then, once it started sleeping, running it in the second:

    Parent.last.children.create

This deadlocks because when #next_child_number sleeps, the open transaction in console A has a read lock (a.k.a. shared lock) on the parent row; console B then acquires a read lock on the same parent row.  When A has finished sleeping, it cannot acquire a write lock (a.k.a. exclusive lock) because B has a lock.  And vice versa.  So, deadlock.

Separately, starting from the original code, I was able to reproduce the uniqueness violation by changing Child#set_number to:

    def set_number
      n = parent.next_child_number
      update_column :friendly_id, "#{other_stuff}-#{n}"
      sleep 5
      update_column :number, n
    end

– and then doing the two-console thing as above.

This produces a non-unique friendly_id because the second console's transaction gets the same value from Parent#next_child_number as the first console's transaction, because the first one hasn't committed when the second one reads the value.

So the deadlocks and the uniqueness violations are two aspects of the same problem.  It's a classic race condition.

The first solution I found was to lock the parent record by changing Child#set_number to this:

    def set_number
      parent.lock!

      n = parent.next_child_number
      update_column :friendly_id, "#{other_stuff}-#{n}"
      update_column :number, n
    end

This makes the deadlocks and the uniquess violations go away, at (presumably) the cost of some throughput.

I then found a helpful page in the manual entitled Locking Reads [1] which uses my exact situation as an example.  It turns out that in MySQL you can achieve an atomic increment-and-read using LAST_INSERT_ID(expression).  So I change Child#set_number to:

    def set_code
      connection.execute "UPDATE parents SET child_number = LAST_INSERT_ID(child_number + 1) WHERE id = #{parent.id}"
      n = connection.execute("SELECT LAST_INSERT_ID()").first.first

      update_column :friendly_id, "#{other_stuff}-#{n}"
      update_column :number, n
    end

– and I can remove Parent#next_child_number altogether.  It's not portable but it's lock-free so (presumably) has a higher throughput.

Thanks again to everyone who helped!

Yours,
Andy

[1] http://dev.mysql.com/doc/refman/5.7/en/innodb-locking-reads.html