• Julien Muchembled's avatar
    storage: in deadlock avoidance, fix performance issue that could freeze the cluster · 1280f73e
    Julien Muchembled authored
    In the worst case, with many clients trying to lock the same oids,
    the cluster could enter in an infinite cascade of deadlocks.
    
    Here is an overview with 3 storage nodes and 3 transactions:
    
     S1     S2     S3     order of locking tids          # abbreviations:
     l1     l1     l2     123                            #  l: lock
     q23    q23    d1q3   231                            #  d: deadlock triggered
     r1:l3  r1:l2  (r1)   # for S3, we still have l2     #  q: queued
     d2q1   q13    q13    312                            #  r: rebase
    
    Above, we show what happens when a random transaction gets a lock just after
    that another is rebased. Here, the result is that the last 2 lines are a
    permutation of the first 2, and this can repeat indefinitely with bad luck.
    
    This commit reduces the probability of deadlock by processing delayed
    stores/checks in the order of their locking tid. In the above example,
    S1 would give the lock to 2 when 1 is rebased, and 2 would vote successfully.
    1280f73e
transactions.py 24 KB