模糊Rocks概述

由RocksDB支持，使用任意距离函数和SymSpell算法加速的模糊键查找的持久数据存储。

相对于其他SymSpell实现，使用此crate的原因包括：

• 你有非标准键字符（例如，DNA片段等）
• 你想使用自定义距离函数
• 启动时间很重要（你无法在加载时重新计算键变体）
• 你有数百万个键，并且关心内存占用

注意 此README是crate文档的首页，但许多链接在上下文中查看时可能损坏。您可以通过此处访问最新版本的完整文档

记录与键

一个[表]包含记录，每个记录都有一个唯一的[记录ID]，每个记录都与一个或多个[键]相关联。键用于执行记录的模糊查找。一个[键]通常是[String]或 [&str]，但也可以是任何数量的KeyCharT集合，例如[Vec]、[Array]或[Slice]。

键在表中不必是唯一的，多个记录可能具有共同的键。如果查找键和其他标准与表中的多个记录匹配，则所有查找方法都可能返回多个记录。

使用示例

使用默认[表]配置和使用字符串作为键的简单用例。

use fuzzy_rocks::{*};

//Create and reset the FuzzyRocks Table
let mut table = Table::<DefaultTableConfig, true>::new("test.rocks", DefaultTableConfig()).unwrap();
table.reset().unwrap();

//Insert some records
let thu = table.insert("Thursday", &"Mokuyoubi".to_string()).unwrap();
let wed = table.insert("Wednesday", &"Suiyoubi".to_string()).unwrap();
let tue = table.insert("Tuesday", &"Kayoubi".to_string()).unwrap();
let mon = table.insert("Monday", &"Getsuyoubi".to_string()).unwrap();

//Use lookup_best, to get the closest fuzzy match
let result = table.lookup_best("Bonday")
    .unwrap().next().unwrap();
assert_eq!(result, mon);

//Use lookup_fuzzy, to get all matches and their distances
let results : Vec<(RecordID, u8)> = table
    .lookup_fuzzy("Tuesday", Some(2))
    .unwrap().collect();
assert_eq!(results.len(), 2);
assert!(results.contains(&(tue, 0))); //Tuesday -> Tuesday with 0 edits
assert!(results.contains(&(thu, 2))); //Thursday -> Tuesday with 2 edits

//Retrieve a key and the value from a record
assert_eq!(table.get_one_key(wed).unwrap(), "Wednesday");
assert_eq!(table.get_value(wed).unwrap(), "Suiyoubi");

另一个使用存储（简化）DNA序列的[表]的用例。对于生物分子的更全面表示，请参阅FASTA格式。

use fuzzy_rocks::{*};

//A simplified data type that might represent a Nucleobase.
// https://en.wikipedia.org/wiki/Nucleobase
#[derive(Copy, Clone, Eq, PartialEq, Hash, serde::Serialize, serde::Deserialize)]
enum Nucleobase {
    A, // adenine
    C, // cytosine
    G, // guanine
    T, // thymine
    U, // uracil
}

struct Config();
impl TableConfig for Config {
    type KeyCharT = Nucleobase;
    type DistanceT = u8;
    type ValueT = usize;
    type CoderT = DefaultCoder;
    const UTF8_KEYS : bool = false;
    const MAX_DELETES : usize = 2;
    const MEANINGFUL_KEY_LEN : usize = 24;
    const GROUP_VARIANT_OVERLAP_THRESHOLD : usize = 5;
    const DISTANCE_FUNCTION : DistanceFunction<Self::KeyCharT, Self::DistanceT> = Self::levenstein_distance;
}

//Create and reset the FuzzyRocks Table
let mut table = Table::<Config, false>::new("test_custom_config.rocks", Config()).unwrap();

其他使用示例可以在位于src/lib.rs文件底部的测试中找到。

表配置

一个 [TableConfig] 对象作为参数传递给 Table::new。TableConfig 指定了关于表格的多个属性，包括

• 数据类型，用于定义 [Table] 的某些方面的结构和表示
• 调整参数，以影响各种操作的性能
• 距离函数，用于计算度量空间中两个键之间的距离

[DefaultTableConfig] 是一个零大小的类型，实现了针对 UTF-8 键的默认 [TableConfig]。这对于许多情况来说已经足够。如果您需要自定义 TableConfig，可以在 [TableConfig] 的文档中找到有关类型参数和字段的更多详细信息。

Unicode 和 UTF-8 支持

根据您的需求，[Table] 可以配置为将键编码为 UTF-8 或不编码。这是通过 [TableConfig] 对象的 UTF8_KEYS 常量来配置的。

算法细节

SymSpell 的权威描述是 SymSpell 项目 的 ReadMe。

fuzzy_rocks 实现还有一些需要注意的额外细节

• fuzzy_rocks 不会找到没有至少一个共同字符的键，无论 MAX_DELETES 的值是多少。例如，键 me 不会通过查询字符串 hi 被找到，即使距离为 2（或任何其他值）。这个决定是因为短键的变体空间变得非常拥挤，空字符串变体的极端例子对短键的性能造成了严重破坏。

性能特征

这个 crate 设计用于大型数据库，其中启动时间和常驻内存占用是重要的考虑因素。这个 crate 已经被测试过，累计有 200,000 条记录，超过 1,000 万个键，以及约 1.4 亿个键变体。在这种情况下，模糊查找在 500us（微秒）到 1ms 之间，在我的笔记本电脑上运行——我认为这在绝对术语中非常昂贵，但对于许多用例来说是可以接受的。

性能也会根据键的分布和表格参数有很大的变化。与其他键不同的键将导致搜索速度更快，而共享许多共同变体的键将导致搜索速度较慢。

针对性能的调整

性能高度依赖于创建 [Table] 时使用的 [TableConfig] 的值，但必须匹配数据集中的键的特征。

简要来说，调整参数包括

MAX_DELETES：较小的 MAX_DELETES 值将表现出指数级的性能提升，但将能够找到更少的搜索结果。《tt class="txt-plain">MAX_DELETES 应该调整到尽可能小的值，但不能更小。

MEANINGFUL_KEY_LEN：更高的 MEANINGFUL_KEY_LEN 值会导致对距离函数的评估更少，但会导致变体数据库中的条目更多，从而降低数据库性能。

GROUP_VARIANT_OVERLAP_THRESHOLD 控制了当键与现有的 key_group 合并时，与创建新的 key_group 时的逻辑。

有关这些调整参数的更多详细信息，请参阅 [TableConfig] 的文档。

如果您的用例可以应对更高的启动延迟，并且您不介意将所有密钥和变体加载到内存中，那么使用基于Rust原生集合的解决方案，例如这个symspellcrate，在crates.io上，查询性能肯定会更好。

性能计数器

您可以使用[PerfCounterFields]来测量正在执行的内部操作的数量，并使用这些信息来调整[TableConfig]参数。

首先，您必须在Cargo.toml文件中启用perf_counters功能，条目类似于以下内容

[dependencies]
fuzzy_rocks = { version = "0.2.0", features = ["perf_counters"] }

然后，可以通过调用Table::reset_perf_counters来重置性能计数器，并通过调用Table::get_perf_counters来读取。

基准测试

Fuzzy_rocks包含一组（虽小但不断增长）的基准测试，使用criterion实现。可以通过以下方式调用

cargo bench -- --nocapture

数据库格式

根据使用的[Coder]，数据库内容使用BitCode、Bincode或MessagePack进行编码。目前数据库包含5个列族。

1. “rec_data”CF使用小端编码的[RecordID]作为其键，并存储一个varint编码的整数Vec，代表key_group索引，每个索引都可以与一个RecordID结合，以创建一个KeyGroupID。每个引用的key_group至少包含一个与记录相关的键。rec_dataCF是在构建与记录相关的密钥集时开始的地方。

2. “keys”CF使用小端编码的KeyGroupID作为其键，并存储一个varint编码的Vec的OwnedKeys（可视为字符串），每个表示key_group中的一个键。在当前实现中，给定的key_group仅存储单个记录的键，并且KeyGroupID将其关联的[RecordID]嵌入其低44位。这种方案未来可能会改变。

3. “variants”CF使用序列化的键变体作为其键，并存储一个fixint编码的Vec的KeyGroupID，代表每个包含可以减少到这种变体的键的key_group。在CF中，完整的键字符串本身被表示为变体。

4. “values”CF使用小端编码的[RecordID]作为其键，并存储与记录关联的ValueT。

5. “metadata”CF存储有关crate版本和TableConfig的信息，以便由不兼容版本创建的Table DB不会被打开和/或损坏。

未来工作

1. 对密钥度量空间中拥挤的社区的优化。当前设计优化了单个记录具有多个具有重叠变体的键的情况。在许多邻近的键属于同一记录的情况下，这是一个有效的设计，例如当多个拼写变体被提交到Table时。

   首先，这里有一些关于我们如何达到这个设计的背景信息。在v0.2.0版本中，添加了多键支持，因为许多用例涉及创建多个记录，这些记录在概念上是相同的，以便表示键的变体，例如同一事物的多种有效拼写。因为这些键通常彼此相似，并且在数据库中共享许多变体，所以添加了key_groups功能来通过减少每个变体条目中的键的数量来提高性能。理想情况下，给定的变体条目只包含对记录的一个引用，即使该记录有许多相似的键。

   不幸的是，这意味着所有记录的键都会一起加载，这导致了对每个记录的所有键进行不必要的距离函数调用。v0.2.0版本的解决方案是将记录的键分割成key_groups，这样相似的键就会在同一个key_group中，而其他键则不需要测试。这种解决方案对于具有许多聚集在一起的键的个别记录来说效果很好。

   然而，当来自不同记录的许多键聚集在一起时，仍然存在一个大的性能问题。为了解决这个问题，我认为需要不同的数据库布局，以下是我的思考：

   • 需要创建一个单独的CF来存储完整键，并且每个键条目将包含与该键关联的[RecordID]。有两种可能的实现方式：

     • 对于较长的键，一个更紧凑的实现是将"KeyID"用于引用每个键条目。然后条目将包含键本身，以及与键关联的[RecordID]，这些[RecordID]位于同一条目或另一个也按KeyID索引的CF中。在这个实现中，变体CF仍然用于查找KeyID，也许我们可以建立一个惯例，即变体将一个精确匹配的KeyID放在列表的开始处。

     • 需要较少查找间接引用的实现是使用确切的键本身（或者可能是有意义的键。（参见TableConfig::MEANINGFUL_KEY_LEN）作为CF的Rocks键。然后我们会将确切的键与"variants" CF分开，键本身不会被放入"variants" CF。每个变体条目将包含它作为变体的所有完整键。

     关于哪种实现更好，取决于平均键长度。64位KeyID相当于8字节的键，但平均键大约是16字节。另一方面，消除与第二次数据库查询相关的间接引用可能会使直接嵌入键更有利。

   • 上述更改解决了具有相同键的许多记录，但我们可能还想保留在变体条目中只使用一个KeyGroupID来实施许多相似键的优化，而不是为每个单独的键一个引用。特别是如果这些键经常一起获取。

     因此，我相信最佳前进的道路更像上面的第一个选项。所以我们会

     • 重新设计KeyGroupID，使其不再暗示其低44位中的[RecordID]，而是一个完全不同的数字，按需分配。

     • 重新设计key_group条目，使每个键与一个[RecordID]列表相关联。

     • 重新设计"rec_data" CF，使其存储记录的完整键列表，而不是键组索引列表（这些索引随后被转换成KeyGroupID）。

     我相信这种方法将提高存在许多属于不同记录的相似键时的查找性能。然而，我确实能识别出几个缺点：

     • 查找确切的函数不再有现有的快速路径，因为它必须无论如何获取键组条目，以便获取[RecordID]。这可以通过将精确匹配的键组移至变体的列表开头来部分缓解。此外，当前的快速路径有一个BUG！（见本列表中的第8项。）

     • 由于每个key关联的[RecordID]向量，key_group条目解析将变得更加昂贵。然而，由于需要加载的key_group条目更少，这可能会带来净收益——至少不会造成损失。

     • “rec_data”CF将随着每个key组索引（约1字节）被整个key（平均16字节）替换而膨胀。然而，rec_data仅用于账务操作，不会影响模糊查找速度。因此，主要影响将是数据库大小，我们预计这将增加5-10%。

2. 在key组内进行BK-Tree搜索。如果我们最终得到许多相邻的key，则在表中拥有二级搜索结构可能会有优势。实际上，我认为BL-Tree总是优于列表，所以真正的问题是这个性能提升是否值得工作量和技术复杂性。

   SymSpell针对稀疏key空间进行了非常优化的处理，但在密集key空间（许多key共享许多变体）中，SymSpell优化仍然需要使用距离函数测试数百个key。在这种情况下，BK-Tree可能会显著加快模糊查找速度。

3. 在查找过程中进行多线程。重新设计内部管道，以便可以并行检索和处理变体条目，从而并行评估key组和并行执行距离函数。

4. 研究添加一个“k-nn查找”方法，该方法将返回最多k个结果，按其与查找key的距离排序。或许除了或代替Table::lookup_best方法，因为这种方法本质上是对Table::lookup_best方法的泛化。

   这个想法有点问题，因为当存在等距离结果时，返回恰好k个结果的函数不能是确定性的。我们通常会发现在k跨越边界时，返回确定性的结果集的唯一方法就是返回多于k个结果。（或者少于k个，但这可能意味着没有结果的集合，这可能不是调用者想要的。）

5. 将TableConfig保存到数据库中，以便检测到配置发生变化时数据库无效的错误。还包括软件版本检查，并创建一个函数来表示哪些软件版本包含数据库格式兼容性中断。开放问题：我们应该存储距离函数的校验和吗？该函数可能被重新编译或内部更改，而不改变行为，但我们无法确定。

6. 一旦Rust中的"GenericAssociatedTypes"稳定，就立即删除KeyUnsafe特性。
   https://github.com/rust-lang/rust/issues/44265。一旦我能够实现具有非Key特性参数内部生命周期的关联类型，我就能返回具有相同基础类型但关联生命周期更短的对象，从而消除转换生命周期的需要。

7. 研究工具以检测当[Table]参数因数据集而调整不良时的情况，基于已知某些性能计数器的最优比率。或者构建工具以协助执行参数搜索优化过程，该过程可以自动遍历参数，为给定的数据集搜索最优的[TableConfig]。

8. 修复BUG！由我们未加载与精确变体关联的key_group的优化造成的Table::lookup_exact，因此我们可能返回键是查找键超集的记录。注意：这可能会在1中提出的更改的副作用中修复。

发布历史

0.4.0

• 添加了Bitcode编码器格式并将其设置为默认格式。
• 对打开具有不兼容格式的数据库进行安全检查

0.3.0

• 在数据库中抽象编码/解码格式
• 添加了MessagePack格式，尽管Bincode仍然是默认格式

0.2.2

• 修复了可能导致某些结果丢失的逻辑错误

0.2.0

• 支持多键。记录现在可以与多个键关联
• Lookup_best现在返回一个迭代器而不是任意选择的记录
• 支持由泛型KeyCharT类型组成的键，而不仅仅是ASCII或UTF-8
• 中心TableConfig特性和所有调整参数集中化
• 添加了使用Criterion的微基准测试
• 添加了perf_counters功能
• 在某些情况下，对查找进行了大量性能优化（10x-100x）
  • lookup_best在更昂贵的lookup_fuzzy之前先检查lookup_exact
  • key_groups将记录的相似键混合在一起
  • 对levenstein_distance函数进行微优化，以实现3倍速度提升
  • 将记录值存储在数据库中的键之外，因此不需要不必要地解析值

0.1.1

• 初始发布

致谢

• @Linus789发现了v.0.2.2中的逻辑错误并进行了修复

• @0x07C0在bitcode作者的@caibear的帮助下添加了bitcode支持，使某些查找操作的速度提高了2倍

杂项

注意：所包含的geonames_megacities.txt文件是geonames_test的占位符，旨在对该crate进行压力测试。简化的文件包含在内，以确保测试通过，并避免下载膨胀。geonames_megacities.txt的内容来源于geonames.org的数据，并按照Creative Commons Attribution 4.0 License授权