potential partition tree enhancements

[lyang24]

motivation: i was wondering can we derive perf gains from arena based skiplist that is frequently used in other databases (for an example crdb memtable uses https://github.com/andy-kimball/arenaskl)

• Arena based keys: is it worth to explore arena based allocation? Instead of storing keys as HashMap<Vec, PkId>, pack ALL keys into one continuous block of memory (an "arena").

  • Much less allocation, less memory fragment
  • Better CPU cache performance (all keys are together)

• Lock-Free Map: partitions: RwLock<BTreeMap<PartitionKey, PartitionRef>> is it worth to explore a lockfree ordered map impl? if order is not critical we dashmap seems very promising.

• if we dont think lock free map is worth it - can we take a snapshot of partitions and release the read lock quickly then iterate and prune on the snapshot without holding the read lock?

  greptimedb/src/mito2/src/memtable/partition_tree/tree.rs

  Line 424 in c0652f6

  let partitions = self.partitions.read().unwrap();

• (nit) is it worth to maintain a hashmap of shard_id to shards? this can help with looks ups like

  greptimedb/src/mito2/src/memtable/partition_tree/partition.rs

  Line 564 in c0652f6

  let shard = self

  i think it would benefit only if there are lots of shards

[evenyag]

I'm going to replace the partition tree memtable with the new bulk memtable. My final goal is to keep one memtable.

• https://github.com/GreptimeTeam/greptimedb/blob/main/src/mito2/src/memtable/bulk.rs
• Bulk Memtable with full primary key support #6505

[lyang24]

great i just got started reading bulk memtable code :)