Use skiplist tailored for LSM-tree

[marvin-j97]

• No need for remove and get() methods, we only need range() and insert()

• Arena-based (store towers/nodes in arena)

• Should probably be a new repo - will definitely involve unsafe

• Needs to be concurrent, at least reads shouldn't get blocked by writes

[guycipher]

Why not a read-write lock skiplist? Why the granular concurrency? It will lead to complexity and unsafely no? From experience I can’t say you’ll get major performance boosts doing a granular approach. Also, why just range? What about iteration for cursing through?? Forwards and backwards the entire list. Range on a memtable?

[marvin-j97]

Why not a read-write lock skiplist? Why the granular concurrency? It will lead to complexity and unsafely no? From experience I can’t say you’ll get major performance boosts doing a granular approach.

Well the current skiplist already is concurrent.
Granular not being better is anecdotal, the point is to have a lock-free read path, and make reads not blocking writes too much.

Also, why just range? What about iteration for cursing through?? Forwards and backwards the entire list. Range on a memtable?

Range is an Iterator. More correctly a DoubleEndedIterator.

[guycipher]

Well the current skiplist already is concurrent.
Granular not being better is anecdotal, the point is to have a lock-free read path, and make reads not blocking writes too much.
I'm just providing some perspective. Yes that is nice but comes with complexity and dare I say it doesn't provide much of a boost as it does bugs and uncertainty; Since the skip list is already in memory it's rather performent no?

Range is an Iterator. More correctly a DoubleEndedIterator.
I thought this was more specific to databases. A range iterator is like hey give me 100-3000 and you can only iterate between those, that's what I understood by it. I mean this can be done in any way truly. Here's some more food for thought can iterating through the memtable and sstables from the memtable to the last sstable be accomplished?

[marvin-j97]

Yes that is nice but comes with complexity and dare I say it doesn't provide much of a boost as it does bugs and uncertainty; Since the skip list is already in memory it's rather performent no?

It's not about boosting performance, it's about keeping the current locking behaviour, but not depending on crossbeam's epoch system. For long reads, having a RwLock would block writes.

Here's some more food for thought can iterating through the memtable and sstables from the memtable to the last sstable be accomplished?

And yes, that's what an LSM-tree implicitly does.