al8n / orderwal

A generic-purpose, ordered, zero-copy, Write-Ahead Log implementation for Rust.
Apache License 2.0
5 stars 0 forks source link

Use `skl::SkipMap` as the sidecar lookup map instead of `crossbeam_skiplist::SkipMap` and `std::collections::BTreeMap` #11

Open al8n opened 16 hours ago

al8n commented 16 hours ago

While crossbeam_skiplist::SkipMap and std::collections::BTreeMap are solid choices for a general-purpose ordered map, they may not be ideal for a database environment. This is primarily due to its reliance on dynamic memory allocations for each entry, leading to non-contiguous memory layouts. In a database scenario, where performance and efficient memory usage are critical, this can become a bottleneck.

The lack of contiguous memory means that pointer chasing occurs frequently during lookups, increasing cache misses and search times. This added overhead can significantly impact performance when performing large-scale or frequent queries.

In contrast, skl::SkipMap provides a more suitable approach for database environments because it stores entries in a continuous memory buffer, reducing the need for frequent allocations. This leads to better cache locality and faster search operations, making skl::SkipMap a more performant choice in cases where minimizing memory overhead and maximizing search efficiency are crucial, such as in database systems.

Hence, in 0.5, the sidecar of the write-ahead log will be changed to skl::SkipMap.

al8n commented 2 hours ago

The benchmark of skl shows that crossbeam_skiplist is faster than skl, need to figure out what happens in skl implementation

al8n commented 15 minutes ago

Find the problem, see https://github.com/al8n/skl/issues/41