Proposal: a better structure for LevelHandler

[Little-Wallace]

Problem

LevelHandler will re-sort the whole sst file in one level. But if there are 100K files in one level, once sort operation may cost 20~100ms (I bench it in my macbook 2020). And if there are many compaction jobs running together, they may block the read thread too long.

Solution

I propose a two-level b+ tree for LevelHandler and it will split the sst into much page. Every time it changed it only copy the origin page and update one row of it, and then replace it in a short time with holding mutex. I think two-level is enough because sort one thousand string can be finished in 1ms.

[coocood]

If we use multiple instances, the largest level only contains tens of files.

[skyzh]

If we use multiple instances, the largest level only contains tens of files.

Using multiple instances of LSM store on a single disk seems not efficient. We have as many WAL files as instance number, which would lead to inefficient fsync and fragmentation in SSD internally.

[BusyJay]

Multiple instance can share WAL. For example, using raft engine to store WAL. But I do think we need to consider the number of SSTs as a generic engine.

[Little-Wallace]

Do we need to consider how to split a manifest version of sst into multiple?

[Connor1996]

Do we need to consider how to split a manifest version of sst into multiple?

What's it used for?

[Little-Wallace]

Do we need to consider how to split a manifest version of sst into multiple?

What's it used for?

To split one engine into two engine. Because @coocood commented that we may use multiple db instances.