Diviner:确定性测试的新尝试

Xuejie Xiao

Xuejie Xiao

Nervos Core Team

我一直以来对确定性执行的问题很感兴趣。我们在多线程模型上花了很大时间。我们大部分人都应该遇到过一些只在一定概率范围内发生的 bug。即使你已经准备好了一个修复程序,你也不能确定它是不是还会再次发生,你所能做的不过是测试,测试,再测试,并希望这样的问题不会再次出现。我们可以确定地进行调试并拍着胸脯说这是 100% 确定的,这是每一位工程师的梦想,而这个问题已经被解决了。

在过去的几个月里,我一直在学习 TLA+,我现在坚信 TLA+ 是构建复杂的、多线程的、高性能的、(也可能是分布式的)系统的宝贵工具。在为我所有的项目写下第一行代码之前,我的确更喜欢在 TLA+ 中先构建一个设计。但 TLA+ 只能帮助你思考你的设计,并修复其中的设计缺陷。我们还需要考虑到另一面:实际执行该系统。我们可以有一个已经经过 TLA+ 验证的设计,但如果你写的代码是比较容易受到某些并发性 bugs 的攻击的,而这些 bugs 又是有一定概率会发生的,那这时候该怎么办呢?

当然,也有一些在解决方案上的尝试,比如 rr。但在这个领域还有一个真正的精华,那就是 FoundationDB。如果你不是很了解 FoundationDB,特别是不清楚它们是如何进行测试的,我强烈推荐以下两个视频:

它们所做的,是在 C++ 之上构建一个 actor 模型,然后使用 actor 模型来编写完整的数据库逻辑。因此,它们可以将基于 actor 的代码完全注入到一个确定性的测试框架中,以测试各种并发性问题。老实说,我之前就看过这些视频,但那时候比较早,我对他们的解决方案印象并不是很深刻,原因在于:他们的模拟框架是在一个单线程中连续运行的,这与真正的设置相差甚远,在真正的设置中,你是有多个线程在共同运行的。因此你从模拟中得到的性能数据没什么意义。

幸运的是,我有一个兴趣爱好,就是成为电脑学的考古专家:我会时不时地把一些相对较老的视频翻出来,重新观看一遍,以获得新的理解。这是一个过去的经验,在这个行业有很多的发明,都只是新瓶装旧酒。当我最近翻出 FoundationDB 的视频并再次观看时,我发现我之前犯了一个非常非常严重的错误。这确实是一件大事。

测试与基准测试是不同的

这里的关键是,测试与基准测试是不同的。测试的目的绝不是获得实际的运行时间,而是探索程序可以采用的所有路径。就像 TLA+ 会探索你设计中所有的状态一样,如果一个模拟可以探索一段代码可以采用的所有的执行路径,那么就已经足够了。使用 actor 模型重新组织的代码,你的逻辑会被自然地分割成很多个小的原子块,只要你能够枚举出一个程序可以有效执行的所有不同的执行顺序,那么就算是用一个单线程的测试框架也可以探索出多线程解决方案中可能导致的所有路径!

实际上,在一个模拟环境中还有很多好处:当你的现目发布时,人们可能开始使用它这意味着他们会尝试在许多不同的机器上运行你的代码。然后,这些机器将会探索你的程序可能导致的不同的执行状态,在某种程度上,我们可以认为所有这些机器都在为你的程序进行测试,寻找 bugs。为了保证你项目的质量,在理想的情况下,你应该在所有这些不同的机器之前找到新的 bugs。现在,问题就变成了列举出所有可能的状态和寻找 bugs 方面的竞赛。对于一些流行的产品,用户运行的机器数量很容易超过项目维护者所拥有的机器数量。问题来了:如何才能在使用极少的机器的情况下,找到更多的 bugs?

这个问题的答案,类似于 FoundationDB 解决方案中的模拟设计:首先,我们在一个 actor 模型的框架下组织逻辑,因此我们可以使用一个单线程模拟测试执行器来运行测试;然后,我们模拟所有和环境相关的代码,如计时器、网络 IOs、文件 IOs 等等。通过这种方式,我们可以将我们项目的核心,也就是大多数 bug 发生的地方,提炼成一段单线程的,连续的代码,有以下好处:

  • 当一个测试在一个单线程的环境中运行时,一个典型的多核机器就可以用来同时运行多个测试;
  • 当所有的 IOs 都被模拟出来之后,我们可以在测试中运行更少的代码(比如,我们可以跳过整个 TCP/IP 栈),从而更快地进行测试;
  • 有了模拟的 IOs,我们可以更容易地模拟异常情况,比如网络堵塞;

所有这些好处都意味着模拟方案可以允许我们在更少的时间内对代码进行更多的测试,让我们有机会在寻找 bugs 的竞速游戏中取得胜利。在 FoundationDB 的示例中,他们估计在过去的几年时间里,通过这种设计,他们已经积累了相当于一万亿 CPU-hours 的模拟压力测试。直到今天为止,我还没有看到一个更高级的测试框架设计。

现在只有一个问题了:虽然这个解决方案很好,也被证明非常有效,但我们能在其他地方使用它吗?我们是否会受到 C++ actor 框架的限制?答案是,当然不会!

Rust:一个基于 Actor 模拟测试的最佳选择

如果我们仔细思考一下,做一个 FoundationDB 类型的确定性模拟测试所需要的只是一个基于 actor 的代码,然后我们就可以根据测试需求对它们进行重组。令人激动的事情在于,Rust,我们敬爱的用于构建高性能的分布式软件的解决方案,已经提供了一个异步/等待设计,这很像 actor 模型(好吧,我并不能算是一名计算机科学教授,我把这个问题留给那些更有资格去评判异步/等待是不是 actor 模型的人)。为了使其更加有趣,Rust 的可切换运行时间的设计使其成为这种确定性模拟测试思想下的最佳选择:我们所需要做的,就是在测试中使用不同的运行时间,问题就会得到解决。

接下来就让我们有请出本文的主角:diviner

Diviner

一旦有了这个想法,我觉得它真的太伟大了,不夸张的说,我花了我所有的夜晚和周末来实现这个想法,这才有了 diviner。它由两部组成:

  • 一个设计成单线程和具有确定性的运行时间,因此我们可以利用它来构建确定性模拟测试;
  • 在现有的 Rust 异步库上面实现的封装器。封装器在正常模式下(通过内联函数和 newtypes)将直接编译成现有的实现,但在启用了特殊的 simulation 功能后,它们将被编译成与上述运行时间集成好的模拟版本,以便进行确定性测试。现在我是从 async-std 开始,但在未来可能会添加更多的封装器。

两个部分结合在一起,diviner 为异步/等待的 Rust 代码提供了一个 FoundationDB 类型的确定性测试解决方案。这里提供几个示例,以展示操作时间的能力,这允许我们以更快的方式测试超时,以及测试并发的 bugs 的能力。使用确定性 seed,diviner 将确定性地运行,让你有机会可以无限次地调试你的代码。它的美妙之处在于,它只是一个异步/等待的 Rust 代码,我们没有往 diviner 中引入任何新东西。

我还有一个例子,我希望在未来的几天内可以将其实现:

use byteorder::{ByteOrder, LittleEndian};
use diviner::{
net::{TcpListener, TcpStream},
spawn, Environment,
};
use std::io;
async fn handle(stream: Tcpstream) {
let mut buf = vec![];
loop {
let mut t = vec![0; 1024];
let n = stream.read(&mut t).await.expect("read error!");
if n == 0 {
break;
}
buf.extend_from_slice(&t[..n]);
let l = LittleEndian::read_u32(&buf) as usize;
if buf.len() >= l + 4 {
let content = &buf[4..l + 4];
stream.write(content).await.expect("write error!");
buf = buf.drain(0..l + 4).collect();
}
}
}
async fn server(addr: String) -> Result<(), io::Error> {
let mut listener = TcpListener::bind(addr).await?;
while let Ok((stream, _)) = listener.accept().await {
spawn(handle(stream));
}
Ok(())
}
fn main() {
let e = Environment::new();
let result = e.block_on(async {
let addr = "127.0.0.1:18000";
spawn(async {
server(addr.to_string()).await.expect("server boot error!");
});
let data: Vec<u8> = vec![4, 0, 0, 0, 0x64, 0x61, 0x64, 0x61];
for i in 1..data.len() {
let mut client = TcpStream::connect(addr).await.expect("connect error!");
client
.write(&data[..i])
.await
.expect("client write 1 error!");
client
.write(&data[i..])
.await
.expect("client write 1 error!");
let mut output: Vec<u8> = vec![0; 4];
client.read(&mut output).await.expect("client read error!");
if &output[..] != &data[4..] {
panic!("Invalid response!");
}
}
});
match result {
Ok(val) => println!("The task completed with {:?}", val),
Err(err) => println!("The task has panicked: {:?}", err),
}
}

这个例子展示的是一个典型的新手错误:TCP/IP 协议是基于流的,而不是基于包的。虽然你可能可以提供一个 1 KB 的缓冲区,但是协议可以通过任意数量的字节反馈你,在极端情况下可能只有 1 byte 的数据。在真正的测试中,这是很难模拟的,因为你需要创建一个 TCP/IP 非常拥挤的环境,它只有一个非常小的非常拥挤的窗口。但是有了 diviner,在测试中调整它将会是非常简单的。你写的代码,只是使用了 TcpListener/TCPStream,就像是 async-std 中同名的结构一样。是的,你将不得不通过 diviner 来导入它们,但是通过内联函数和 newtype 模式,性能完全不会受到影响。一旦你愿意做出这样的牺牲,我相信你将会发现一个全新的世界。

这才是让我兴奋的地方。现在,diviner 还处于非常早期的阶段,我将在有空的时候继续在 diviner 中添加缺少的部分(比如 async-std 中所缺少的封装器)。如果你也有兴趣,欢迎来试试,让我知道你的感受。

原文链接