1. 一个基于 ARENA 跳表的无锁线程安全的并发 SkipMap 实现，有助于开发 LSM-Tree 的 MVCC memtable。
2. 一个基于磁盘的无锁线程安全的并发内存映射 SkipMap。

安装

• 仅使用堆后端（支持 no_std）

  [dependencies]
  skl = "0.13"
  

• 启用内存映射后端

  [dependencies]
  skl = { version = "0.13", features = ["memmap"] }
  

功能

• MVCC 和 3D 访问：内置 MVCC（多版本并发控制）和键值版本访问支持。
• 无锁和并发安全：SkipMap 提供无锁操作，确保高效的并发访问，无需显式锁定机制。
• 适用于键值数据库开发者的扩展性：作为低级 crate 设计，SkipMap 为键值数据库开发者提供了一个灵活的基础。您可以使用这些结构轻松构建自己的 memtable 或写入前日志（WAL）。
• 内存效率：这些数据结构针对最小内存开销进行了优化。它们围绕引用操作，避免不必要的分配和深度复制，这对于高效的内存使用至关重要。
  • 段跟踪器：内置段回收支持，无锁的空闲列表有助于重用空闲段。
  • 前缀压缩
    • 相同的键只会存储一次。
    • 具有共同前缀的键将只存储一次（最长的一个必须首先插入）。
  • 丢弃跟踪器：内置丢弃跟踪器，它将跟踪丢弃的字节，以帮助最终用户决定何时压缩或重写。
• 高效迭代：通过 SkipMap 中的元素快速向前和向后迭代。此外，还支持有界迭代器，允许您有效地遍历指定范围的元素。
• 快照支持：创建 SkipMap 的快照，提供特定时间点的只读视图。快照提供数据的一致视图，使得事务语义等实现和需要数据一致性的其他用例成为可能。
• 内存管理选项
  • 堆分配：内存分配由 Rust 的分配器处理，确保所有数据都驻留在 RAM 中。
  • 内存映射（Mmap）: 数据可以被操作系统映射到磁盘文件，这使得它非常适合写前日志（WAL）和持久化存储。
  • 匿名内存映射（Mmap匿名）: 通过操作系统映射到匿名内存（虚拟内存），对于大型内存中的memtables非常理想，优化内存利用率。

示例

请参阅示例文件夹获取更多详细信息。

测试

• 测试:

  cargo test --all-features
  

• miri:

  cargo miri test --all-features
  

支持平台

血统

此代码受 Cockroachdb 的 pebble arenaskl 和 Dgraph 的 badger skl 代码的启发和修改。

https://github.com/cockroachdb/pebble/tree/master/internal/arenaskl

https://github.com/dgraph-io/badger/tree/master/skl

pebble 的 arenaskl 代码基于 Andy Kimball 的 arenaskl 代码。

https://github.com/andy-kimball/arenaskl

arenaskl 代码基于 Badger 中找到的跳表，Badger 是一个基于 Go 的键值存储。

https://github.com/dgraph-io/badger/tree/master/skl

Badger 中的跳表本身是基于为 Facebook 的 RocksDB 构建的 C++ 跳表。

https://github.com/facebook/rocksdb/tree/master/memtable

许可证

skl受 MIT 许可证和 Apache 许可证（版本 2.0）的条款约束。

请参阅LICENSE-APACHE，LICENSE-MIT获取详细信息。

版权（c）2022 Al Liu。