糖果店

一个基于Rust实现的快速（当然，迅猛如雷™️）、持久、内联键值存储，它依赖于一种新颖的分区算法。究竟有多快？超过9000！

该算法可以看作是对存储在文件中的哈希表的“零开销”扩展，因为它被设计成最小化IO操作。参见基准测试和如何解释结果*。

概述

作为一个哈希表，键被哈希，生成一个64位数字。最高16位选择分区，然后是16位选择分区中的行，剩下的32位作为不可见的签名。签名与所选行中的签名数组进行匹配（使用SIMD）。行还存储条目的文件偏移量，用于检索条目的键和值。

                 hash (64 bits)                                                        
      ┌───────────────────────────────────┐                                            
   ┌──┴───────┬───────────┬───────────────┴──┐                                         
   │  shard   │   row     │    signature     │                                         
   │ selector │ selector  │                  │                                         
   │   (16)   │   (16)    │      (32)        │                                         
   └──┬───────┴───┬───────┴───────────┬──────┘                                         
      │           │                   │                                                
      │           │                   │        shard file [m..n)                       
      │       ┌───┼───────────────────┼────────────────────────┐                       
      │       │   │                   │                        │ shard file [n..p)     
      │       │   │  ┌─rows─┐         │ Parallel lookup of sig ├────┐                  
m <= sel < n  │   │  │0     │         │     within the row     │    │ shard file [p..q)
      │       │   │  ├──────┤     ┌───┼───┬─────┐              │    ├────┐             
      │       │   │  │1     │     ▼   ▼   ▼     ▼              │    │    │             
      │       │   │  ├──────┤   ┌───┬───┬─────┬───┐            │    │    │             
      └─────► │   └─►│2     ├───┤ 0 │ 1 │     │511│            │    │    │             
              │      ├──────┤   ├───┼───┼─...─┼───┤            │    │    │             
              │      │3     │   │sig│sig│     │sig│            │    │    │             
              │      ├──────┤   │off│off│     │off│            │    │    │             
              │      │.     │   │len│len│     │len│            │    │    │             
              │      │.     │   └───┴─┬─┴─────┴───┘            │    │    │             
              │      │.     │         │                        │    │    │             
              │      ├──────┤         ├─► entry's file offset  │    │    │             
              │      │63    │         └─► entry's length       │    │    │             
              │      └──────┘                                  │    │    │             
              └────┬───────────────────────────────────────────┘    │    │             
                   │                                                │    │             
                   └────┬───────────────────────────────────────────┘    │             
                        │                                                │             
                        └────────────────────────────────────────────────┘             

每个分区映射到一个分区文件，一个分区文件可以覆盖广泛的连续分区。我们开始时用一个覆盖整个分区范围的单个分区文件[0-65536]。

当分区文件变得太大，或者其中的某一行满了，它就会进行分割。这个操作将所有条目分成上下两部分（大小大致相等）。例如，如果文件覆盖了分区[0-65536)，分割后我们有两个文件，一个覆盖[0-32768)，另一个覆盖[32768-65536)。这个流程根据需要重复进行，本质上构建了一个分区文件树。每个文件独立分割，工作量是恒定的（与LSM树不同）。

               [0-65536)
              /         \
             /           \
          [0-32768)    [32768-65536)
         /         \
        /           \
    [0-16384)     [16384-32768)  

分片文件的头部（行、签名和文件偏移量）存储在一个 mmap 中，而文件其余部分的数据则是通过 pread 和 pwrite 访问。文件只有在分裂或 压缩 发生时才会扩展，因此算法是 崩溃安全的，这意味着它总是会返回一些有效的键值对版本，尽管可能会丢失未刷新的数据。

库信任内核的页面缓存，并假设 mmap 和写入会不时地刷新到磁盘。这允许我们放弃日志或写入前日志（WAL）。

默认参数（由模拟选择）是具有 64 行的分片，每行有 512 个条目。这些参数发生冲突的可能性很小，并且它们允许分片达到约 90% 的利用率，同时需要相对较小的头部表（32K 条目，占用 384KB）。在有 90% 利用率的情况下，你应该期望每个分片可以存储 29.5K 个键。对于 64MB 的分片文件，这仅是 0.6% 的开销。

由于数据结构是哈希表而不是搜索树，因此插入、查找和删除都是 O(1) 操作。

该概念可以扩展到分布式数据库，通过添加一层主分片层来选择服务器，然后是上面描述的正常分片机制。

示例

use candystore::{Config, Result, CandyStore};

let db = CandyStore::open("/tmp/candy-dir", Config::default())?;

// simple API

db.insert("mykey", "myval")?;
assert_eq!(db.get("mykey")?, Some("myval".into()));

assert_eq!(db.get("yourkey")?, None);

assert_eq!(db.iter().count(), 1);

for res in db.iter() {
    let (k, v) = res?;
    assert_eq!(k, "mykey".into());
    assert_eq!(v, "myval".into());
}

assert_eq!(db.iter().count(), 0);

// lists API

db.set_in_list("mylist", "key1", "123")?;
db.set_in_list("mylist", "key2", "456")?;
assert_eq!(db.get_from_list("mylist", "key1")?, Some("123".into()));

assert_eq!(db.iter_list("mylist").count(), 2);

for res in db.iter_list("mylist") {
    let (k, v) = res?;
    println!("{k:?} => {v:?}");
}

设计目标

• 快速且高效，内存占用非常低（约 0.6% 的开销）
• 无重量级/无界合并
• 无写入前日志（WAL）或任何类型的日志记录
• 崩溃安全：可能会丢失最新操作，但永远不会处于不一致状态
• 分裂/压缩是按分片进行的，因此没有全局锁定
• 适用于读写密集型工作负载
• 设计为并发（多个线程同时获取/设置/删除键）
• 后端存储被视为 SSD，因此它未针对 HDD 进行优化

备注

• 文件格式尚不稳定
• 需要夜间（对于 simd_itertools），使用很少的 unsafe（由于 mmap 所需）

路线图

• 基于文件锁的分布式协议（旨在在共享网络文件夹上运行）
• 添加代数作为适配器，以便将旧代数压缩到指数级更大的时间跨度中。它是 TTL 的替代品，并摊销随着数据集的增长而移动条目的次数。
• 可能添加算术编码/霍夫曼编码作为键和值的便宜压缩

如何解释性能结果

虽然上面的数字令人难以置信，但很明显，任何基于文件的存储都将受限于文件系统的延迟和带宽。例如，你可以期望从 SSD（NVMe）中获得 20-100us 的读取延迟，因此这是读取文件中随机位置的下限。

上面测量的数字是 算法 的性能，而不是 存储：如果你可以节省 0.6% 的开销映射到内存中，则查找/插入/删除只需要一次磁盘 I/O。替换（更新）现有元素需要两次 I/O，因为它需要在写入新内容之前比较键。这些 I/O 可能来自内核的页面缓存，在这种情况下，它实际上是立即的，或者来自磁盘，在这种情况下，你可以期望它需要 1-2 次设备的往返时间。

向列表中插入/从列表中删除需要 2-3 次 I/O，因为这些操作需要更新列表的头或尾，以及链接/取消链接到其前一个元素。这些操作应该使用“足够大的页面缓存”来执行。更新/获取列表中现有元素的操作与上述相同，只需要一次 I/O。

如果您的内存不足以保留映射的查找表（即，它们被移至磁盘），则在从表中检索行时，您将增加一个单位的“IO延迟”。由于该行跨越2KB（且对齐到4KB），它应该与4K IOs很好地配合。