Introduce mutex to ensure ordering consistency #218

mkgs · 2020-05-10T05:23:18Z

I'm opening this PR to spark a discussion on how to potentially fix the race condition and order corruption issues that can frequently occur when using this library at scale. This PR is definitely not production-ready in any capacity.

I propose an OrderedMutex model, where a db lock on a mutex instance is required before modifying any order. The key for a mutex instance is compiled from a hash of db_table and the order_with_respect_to fields.

class OrderedMutex(models.Model):
    """
    Mutex model that ensures ordering integrity
    """

    key = models.PositiveIntegerField(editable=False, primary_key=True)

class OrderedModelBase(models.Model):

    ....

    def _get_mutex(self):
        hashes = [hash(self._meta.db_table)]
        if self.order_with_respect_to:
            order_with_respect_to = [self.order_with_respect_to] if isinstance(self.order_with_respect_to, str) \
                else self.order_with_respect_to
            hashes.extend([hash(get_lookup_value(self, attr)) for attr in order_with_respect_to])
        return OrderedMutex.objects.select_for_update().get_or_create(key=reduce(xor, hashes) & 0xFFFFFFFF)[0]

What do y'all think of this approach?

imomaliev · 2020-05-20T05:40:52Z

I am not sure the mutex is a way to go in this case

imomaliev · 2020-05-20T05:42:09Z

Maybe something along those lines https://github.com/viewflow/django-fsm/blob/master/django_fsm/__init__.py#L422. I need to do some research on this

mkgs · 2020-10-15T01:59:57Z

Any other thoughts on this? Perhaps another backend (redis?) for the mutex?

We are moving to a fork of the library, as we continue to encounter order corruption problems. Whatever the implementation, the library should be responsible for order integrity imo.

shuckc · 2021-04-15T15:33:31Z

I doubt taking select ... for update row locks over a dedicated mutex table would be better than the approach in #190 which takes them in the OrderedModel table partition itself. Although of note you have covered more of the API calls - #190 fixes only to(), you covered save, delete, swap, to, above and below.

Using another storage system (like cache system) for the locks isn't great in a hosted environment where one store goes away for a bit and you don't want to cascade failures. Did you make any further findings as to what worked for you?

mkgs · 2021-04-15T21:35:49Z

#190 is a good improvement but I believe there still could be some strange behavior in instances where a new row has been added while a simultaneous ordering operation is occurring.

The dedicated mutex table feels hacky, and I proposed redis as an alternative since it is better suited to grabbing a temporary lock on an arbitrary key value. It also would remove the need for adding any database migrations to the package. However, I definitely hear you on the potential for introducing additional points of failure.

We'll keep using this fork as, however hacky it seems, it is definitely working. We may just change the key field on OrderedMutex to PositiveSmallIntegerField to reduce the key space size.

If I have some spare time I'll take a look at starting another fork that uses redis.

shuckc · 2021-04-16T07:51:07Z

Hi @mkgs as I mentioned on #190 I do think additions where the ordering is calculated on the client side are the weak point of the row locks. Since you are using this code I will aim for the changes in #190 to be applied in such a way that they can be subclassed/switched to an external synchroniser. Perhaps something like providing the synchroniser instance in the Model Meta data would be suitable, and we can ship a default taking row locks.

I'm not against having a cache-based synchroniser upstream, probably not default though.

mkgs added 5 commits October 14, 2020 21:40

add OrderedMutex model and use_order_mutex option

0aa049f

refresh order in delete() method

< 8000 /span>

d296a68

remove xxhash dependency

26ab29a

use get_lookup_value to follow relationships

05ac4b1

rm script/test

fe383a5

mkgs force-pushed the order_mutex branch from d22d0f2 to fe383a5 Compare October 15, 2020 01:43

mkgs added 2 commits October 14, 2020 22:28

fix out of range hash

9bb8503

explicitly order during operations in case model Meta is overridden

c8a6d5d

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Introduce mutex to ensure ordering consistency #218

Introduce mutex to ensure ordering consistency #218

Introduce mutex to ensure ordering consistency #218

Are you sure you want to change the base?

Introduce mutex to ensure ordering consistency #218

Conversation