deduplicate

带有可选 LRU 缓存的异步去重器

如果你有一些“慢”、“昂贵”或“不可靠”的任务，你想要提供去重和可选的结果缓存，那么这个 crate 可能正是你所需要的。

Deduplicate 结构体通过在创建 Deduplicate 实例时提供的委托函数来控制对数据的并发访问。

use std::sync::Arc;
use std::time::Instant;

use deduplicate::Deduplicate;
use deduplicate::DeduplicateFuture;

use rand::Rng;

/// If our delegated getter panics, all our concurrent gets will
/// fail. Let's cause that to happen sometimes by panicking on even
/// numbers.
fn get(_key: usize) -> DeduplicateFuture<String> {
    let fut = async {
        let num = rand::thread_rng().gen_range(1000..2000);
        tokio::time::sleep(tokio::time::Duration::from_millis(num)).await;

        if num % 2 == 0 {
            panic!("BAD NUMBER");
        }
        Some("test".to_string())
    };
    Box::pin(fut)
}

/// Create our deduplicate and then loop around 5 times creating 100
/// jobs which all call our delegated get function.
/// We print out data about each iteration where we see how many
/// succeed, the range of times between each invocation, the set
/// of results and how long the iteration took.
/// The results of running this will vary depending on whether or not
/// our random number generator provides us with an even number.
/// As long as we get even numbers, all of our gets will fail and
/// the delegated get will continue to be invoked. As soon as we
/// get a delegated call that succeeds, all of our remaing loops
/// will succeed since they'll get the value from the cache.
#[tokio::main]
async fn main() {
    let deduplicate = Arc::new(Deduplicate::new(get));

    for _i in 0..5 {
        let mut hdls = vec![];
        let start = Instant::now();
        for _i in 0..100 {
            let my_deduplicate = deduplicate.clone();
            hdls.push(async move {
                let is_ok = my_deduplicate.get(5).await.is_ok();
                (Instant::now(), is_ok)
            });
        }
        let mut result: Vec<(Instant, bool)> =
            futures::future::join_all(hdls).await.into_iter().collect();
        result.sort();
        println!(
            "range: {:?}",
            result.last().unwrap().0 - result.first().unwrap().0
        );
        println!(
            "passed: {:?}",
            result
                .iter()
                .fold(0, |acc, x| if x.1 { acc + 1 } else { acc })
        );
        println!("result: {:?}", result);
        println!("elapsed: {:?}\n", Instant::now() - start);
    }
}

API 文档

安装

[dependencies]
deduplicate = "0.4"

致谢

这个 crate 建立在几个人的辛勤工作和灵感之上，其中一些人与我直接合作过，一些人则给了我间接的灵感。

• https://github.com/Geal
• https://github.com/cecton
• https://fasterthanli.me/articles/request-coalescing-in-async-rust
• 各种 apollographql 路由开发者

感谢您的反馈和宝贵建议。当然，所有的错误都是我的。

基准测试

请参阅下面的更新以获取更新后的比较

当我在这篇 Reddit 帖子 上宣布这个 crate 时，我收到的主要反馈是应该做一些重工作来检查移除用于控制对内部 WaitMap 访问的 Mutex。与其直接进行操作，我认为我应该与 moka 进行一些比较，看看当前性能如何。

我很喜欢 moka，它拥有大量的功能，并且在各种问题应用中都非常好。然而，对于我测试的具体场景，我发现即使有 Mutex，deduplicate 的性能也比 moka 更好。

我的基准测试针对一个非常具体的问题集，不能保证 deduplicate 总是比 moka 更快。所有测试都是在 AMD Ryzen 7 3700X 8 核上进行的，运行 ubuntu 20.04，使用 rustc 1.66.0。比较是在 deduplicate 0.3.2 和 moka 0.9.6 之间进行的。

基准测试是高度并发的，涉及在缓存未命中时对一个小型（约 10,000 个条目）的字符串数据集（从磁盘加载）进行 O(n) 搜索。deduplicate 只提供异步接口，所以比较是对 moka future::Cache 缓存的。

(我已经移除了旧数据的链接，因为它们不能代表当前的状态。请参见下面的更新以获取最新结果。我将在这里留下我的推测和想法，以便为更新提供一些背景。)

我对 moka 的结果感到非常惊讶。当我改变缓存大小时，性能似乎并没有提高。使用更多缓存后，deduplicate 得到了改善，直到它拥有一个大约是主数据集80%大小的缓存。这正是我预期的 moka 的表现，尽管这种意外行为的来源可能是 moka 在并发负载下执行的“批处理”。也有可能是我没有正确编写基准测试代码，但我已经尽力在两个crate之间保持一致性，所以请告诉我如果发现我可以纠正的错误。

当我有多余的时间时，我会考虑如何移除Mutex并保持性能。

更新（2023年11月2日）

moka 的主要作者在基准测试中提出了一个问题（感谢！）并解释了为什么 moka 的表现没有达到我的预期。

我已经合并了更新基准测试的PR，并生成了一套新的结果，其中显示 moka 的表现要好得多。

我使用相同的系统、更新的rust编译器（1.67.1）生成了更新的结果，并与 deduplicate（0.3.6）和 moka（0.10.0）进行了比较。

如果您想查看我生成的 criterion 报告，最清晰的比较是通过点击 get 链接，但您可以自由深入细节。

如果您想生成自己的基准测试比较，请下载repo并运行以下命令：

cargo bench --bench deduplicate -- --plotting-backend gnuplot --baseline 0.3.6

这假设您已经在本系统上安装了gnuplot。（apt install gnuplot）并且您已经安装了criterion 用于基准测试。

如果我从更新的报告中得出任何结论，我会说性能差异不大，但 moka 在缓存限制为总可能结果的小百分比时似乎表现更好，而随着缓存大小的增加，deduplicate 的性能更好。

现在查看Mutex可能值得... :)

许可证

Apache 2.0 许可。有关详细信息，请参阅LICENSE。