Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Feature: support concurrently insert batches into memtable #81

Open
1 of 2 tasks
Fullstop000 opened this issue Sep 10, 2020 · 9 comments
Open
1 of 2 tasks

Feature: support concurrently insert batches into memtable #81

Fullstop000 opened this issue Sep 10, 2020 · 9 comments
Labels
enhancement New feature or request

Comments

@Fullstop000
Copy link
Owner

Fullstop000 commented Sep 10, 2020

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:

@Fullstop000 Fullstop000 added the enhancement New feature or request label Sep 10, 2020
@Fullstop000
Copy link
Owner Author

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
Copy link
Collaborator

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
Copy link
Owner Author

@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
Copy link
Collaborator

jayzhan211 commented Sep 23, 2020

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
Copy link
Owner Author

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
Copy link
Collaborator

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

@Fullstop000
Copy link
Owner Author

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
Copy link
Owner Author

@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
Copy link
Collaborator

Can you help me? I am quite busy now QQ

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

2 participants