Insert-during-iterate deadlock

[marvin-j97]

Discussed in #73

^{Originally posted by dbbnrl August 3, 2024}
In my application I sometimes generate DB entries from existing entries. The pattern is that I iterate over a range of existing keys, occasionally creating new entries (outside the iterator range) as I go.

It looks like Fjall is deadlocking in this scenario after some number of insertions. I thought perhaps using the snapshot feature would help, but it makes no difference.

Glancing at the code, I can see that create_iter takes a bunch of Read locks which it holds until the iterator is dropped. Presumably the insert code is attempting to grab a Write lock at some point (memtable flush?) so this isn't a surprising outcome...

I thought about reporting this as an issue but if this kind of usage is an explicit non-goal of Fjall I didn't want to do that.

Is this supported? Supportable?

[marvin-j97]

Code should never ever deadlock, so if try_lock fails for the journal rotation and the memtable size is much larger than the configured limit, return an Error::WhatIsGoingOn (not literally), maybe

[marvin-j97]

1. Add try_rotate_active_memtable to lsm-tree

2. On lock error, check memtable size

3. If memtable size > 110% * max_memtable_size, we probably have an insert-while-iterate scenario, so return Error::Overpressure [1]

4. add a unit test with a function that loops forever, inserting stuff while having an iterator open... that function should return Error::Overpressure and not panic or deadlock (as it would now)

[1] Because try_lock may be prevented by open reads, we may need a fair RwLock, so the writers don't starve...