Feature: support concurrently insert batches into memtable

[Fullstop000]

In the origin version of leveldb, the write path is like below:

          write
  write     +         write
    +       |   write   +
    |       |     +     |
    |       |     |     |
    |       |     |     |
+---v-------v-----v-----v---+
|                           |
|        Mutex<queue>       |
|                           |
+-------------+-------------+
              |
              |
              |  group batch
              | <single thread>
              |
              v
     +--------+--------+
     |                 |
     |     Memtable    |
     |                 |
     +-----------------+

Writing batches concurrently will result in a single thread ingestion into memtable and then notify all the relate blocked write request threads.
Maybe we can support concurrently inserting batches into memtable , which should improve the write performance a lot.

This feature includes following tasks:

• Introduce an thread-safe concurrent skiplit (support inline skiplist #85)
• Make the current queue scale with inserting threads

[Fullstop000]

The current Skiplist approach doesn't support concurrent inserting. Maybe we should port InlineSkipList from rocksdb https://github.com/facebook/rocksdb/blob/master/memtable/inlineskiplist.h

[jayzhan211]

The current Skiplist approach doesn't support concurrent inserting. Maybe we should port InlineSkipList from rocksdb https://github.com/facebook/rocksdb/blob/master/memtable/inlineskiplist.h

I would like to try on this.

[Fullstop000]

@accelsao Also you may refer to https://github.com/dgraph-io/badger/blob/master/skl/skl.go, which looks like a more clean version of the rocksdb's

[jayzhan211]

badger arena is different from rocksbdb, do you know which one is better to write in rust?
badger save node offset instead of a pointer.

[Fullstop000]

badger arena is different from rocksbdb, do you know which one is better to write in rust?
badger save node offset instead of a pointer.

I think they serve the same purpose with a different approach. Using the current arena should be enough.

[jayzhan211]

How do you think about crossbeam/skiplist, is it a good way to achieve concurrent insert for memtable?

[Fullstop000]

How do you think about crossbeam/skiplist, is it a good way to achieve concurrent insert for memtable?

It may need some extra work to fit the Comparator

[Fullstop000]

@accelsao I've tested the offset-based Arena and it seems more suitable with your inline skiplist implementation.
Do you have time to bring it to your current PR? Maybe I can help :)

[jayzhan211]

Can you help me? I am quite busy now QQ