It's not very fair, because threads that try to lock this key after we have removed the lock from the CHM have an advantage compared to threads that have been waiting for a while on our lock and now have to acquire the lock, unlock, and try again to lock on a new key.

Well the locks already aren't fair right? Also aren't the only cases of scenario 2 key removal and rollback of a put? So we would be talking insert/remove competition on the same key.


The key lock's lifecycle is not tied to the entry's lifecycle, instead it lives just for the duration of a transaction. As soon as the tx is committed/rolled back, the lock is removed, and any tx that was waiting on the lock will have to create its own lock.

Ah ok so it is a very big problem then. I agree then you need reference counting. You want that lock to stay around for as long as you have contention.