MEM-MEMTABLE-002: MemTable usa BTreeMap O(log n) em vez de skip list lock-free — concorrência limitada

[ElioNeto]

🟡 Médio | Performance | MemTable

Problema

O MemTable usa BTreeMap<Vec<u8>, LogRecord> protegido por Mutex. Inserções são O(log n), e o lock serializa todo acesso ao MemTable. Skip lists oferecem O(log n) médio similar, mas com concorrência lock-free e melhor localidade de cache.

Impacto

• Inserção no MemTable bloqueia todos os readers durante write
• Sem potencial para escritas lock-free concorrentes
• BTreeMap com Vec<u8> como chave faz alocações extras (comparação de fatia vs vetor)

Evidência

src/core/memtable.rs:3: use std::collections::BTreeMap
src/core/memtable.rs:6: data: BTreeMap<Vec<u8>, LogRecord>

Medição de performance

// Benchmark: inserir 1M registros no MemTable atual
// vs crossbeam-skiplist
// vs BTreeMap com &[u8] como chave

Correção recomendada

Opção A (recomendada): crossbeam-skiplist

# Cargo.toml
crossbeam-skiplist = "1"

use crossbeam_skiplist::SkipMap;

pub struct MemTable {
    data: SkipMap<Vec<u8>, LogRecord>,
}
// Insert: O(log n) lock-free
// Get: O(log n) lock-free
// Scan: iterador ordenado

Opção B: Manter BTreeMap mas com Arc<[u8]> como chave

// Reduz alocações comparando &[u8] em vez de Vec<u8>
pub struct MemTable {
    data: BTreeMap<Arc<[u8]>, LogRecord>,
}

Esforço: Alto (16h para crossbeam-skiplist, 4h para Arc<[u8]>)