背景

1. 通信不可靠：丢包，超时，乱序，重复

2. 时钟不可靠：时钟漂移，拖尾，回退

3. 节点不可靠：阻塞，宕机，掉线，停顿

确定性测试 & 模拟

• 混沌测试：ChaosMesh

• 验证框架：Jepsen

• 修复后如何验证真的解决了？还是需要精确复现这个问题

• 更多时候还因为日志和信息不足无法定位，要给程序添加日志后等待再次复现

Jepsen 的出现成功击溃了几乎所有它测试的分布式系统，这表明我们在根本上以一种错误的方式构建分布式系统，这种方式无法避免 bug 的出现

1. 将代码写成能在模拟器上被确定性运行的形式 2. 写一个模拟器去模拟真实世界的行为

业界实现和落地

FoundationDB

ACTOR Future<float> asyncAdd(Futur<float> f, float offset) {
    float value = wait(f);
    return value + offset;
}

testTitle=SwizzledCycleTest
    testName=Cycle
    transactionsPerSecond=1000.0
    testDuration=30.0
    expectedRate=0.01

    testName=RandomClogging
    testDuration=30.0
    swizzle = 1

    testName=Attrition
    machinesToKill=10
    machinesToLeave=3
    reboot=true
    testDuration=30.0
    
    testName=ChangeConfig
    maxDelayBeforeChange=30.0
    coordinators=auto

Anyway, we did this for a while and found all of the bugs in the database. I know, I know, that’s an insane thing to say. It’s kind of true though. In the entire history of the company, I think we only ever had one or two bugs reported by a customer. Ever. Kyle Kingsbury aka “aphyr” didn’t even bother testing it with Jepsen, because he didn’t think he’d find anything.

RisingWave & MadSim

将这些状态的转移在时间轴上排列，状态转移之间的时间对状态机是没意义的，模拟器就可以通过离散事件模拟的方式在一个转移结束后直接跳到下一个转移的时间节点，实现时间加速

• runtime 初始化时，使用传入的 seed 构造随机数生成器，之后所有事件的模拟都能被这个 seed 确定

/// Create a new runtime instance with given seed and config.
pub fn with_seed_and_config(seed: u64, config: Config) -> Self {
    let rand = rand::GlobalRng::new_with_seed(seed);
    let sims = Arc::new(Mutex::new(HashMap::new()));
    let task = task::Executor::new(rand.clone(), sims.clone());
    let handle = Handle {
        rand: rand.clone(),
        time: task.time_handle().clone(),
        task: task.handle().clone(),
        sims,
        config,
        allow_system_thread: false,
    };
    let rt = Runtime { rand, task, handle };
    rt.add_simulator::<fs::FsSim>();
    rt.add_simulator::<net::NetSim>();
    rt
}

• 定时器，实质上是在时间堆中加入了一个带定时器回调的输入

pub(crate) fn add_timer_at(
    &self,
    deadline: Instant,
    callback: impl FnOnce() + Send + Sync + 'static,
) {
    let mut timer = self.timer.lock();
    timer.add(deadline - self.clock.base_instant(), |_| callback());
}

pub(crate) fn add_timer(&self, dur: Duration, callback: impl FnOnce() + Send + Sync + 'static) {
    self.add_timer_at(self.clock.now_instant() + dur, callback);
}

• 调度器：通过 event-loop 来进行调度，从就绪队列里随机取任务执行，这里的「随机」也是基于全局的随机数生成器，调度顺序都是被 seed 确定的。然后直接跳转到下一个事件的时间点

pub fn block_on<F: Future>(&self, future: F) -> F::Output {
    // ...
    
    loop {
        self.run_all_ready();
        if task.is_finished() {
            return task.now_or_never().unwrap();
        }
        let going = self.time.advance_to_next_event();
        
        // ...
    }
}

/// Drain all tasks from ready queue and run them.
fn run_all_ready(&self) {
    while let Ok(runnable) = self.queue.try_recv_random(&self.rand) {
        // ...
        
        // run the task
        let res = {
            let _guard = crate::context::enter_task(info.clone());
            std::panic::catch_unwind(move || work(runnable))
        };
        if let Err(e) = res {
            // ...
        }

        // advance time: 50-100ns
        let dur = Duration::from_nanos(self.rand.with(|rng| rng.gen_range(50..100)));
        self.time.handle().advance(dur);
    }
}

• 网络接口的语义比较复杂，这部分有不小工作量，最底下是维护链接的实现，这里存储了所有节点的信息，使用 channel 进行通信，并且可以根据配置的丢包率和延迟来注入故障。再往上提供 socket 语义的接口，感觉都是体力活

/// Opens a new connection to destination.
pub(crate) async fn connect1(
    self: &Arc<Self>,
    node: NodeId,
    port: u16,
    mut dst: SocketAddr,
    protocol: IpProtocol,
) -> io::Result<(PayloadSender, PayloadReceiver, SocketAddr)> {
    self.rand_delay().await?;
    if let Some(addr) = self
        .ipvs
        .get_server(ServiceAddr::from_addr_proto(dst, protocol))
    {
        dst = addr.parse().expect("invalid socket address");
    }
    let (ip, dst_node, socket, latency) = (self.network.lock().try_send(node, dst, protocol))
        .ok_or_else(|| {
        io::Error::new(io::ErrorKind::ConnectionRefused, "connection refused")
    })?;
    let src = (ip, port).into();
    let (tx1, rx1) = self.channel(node, dst, protocol);
    let (tx2, rx2) = self.channel(dst_node, src, protocol);
    trace!(?latency, "delay");
    // FIXME: delay
    // self.time.add_timer(latency, move || {
    socket.new_connection(src, dst, tx2, rx1);
    // });
    Ok((tx1, rx2, src))
}

/// Try sending a message to the destination.
///
/// If destination is not found or packet loss, returns `None`.
/// Otherwise returns the source IP, socket and latency.
pub fn try_send(
    &mut self,
    node: NodeId,
    dst: SocketAddr,
    protocol: IpProtocol,
) -> Option<(IpAddr, NodeId, Arc<dyn Socket>, Duration)> {
    let dst_node = self.resolve_dest_node(node, dst, protocol)?;
    let latency = self.test_link(node, dst_node)?;
    let sockets = &self.nodes.get(&dst_node)?.sockets;
    let ep = (sockets.get(&(dst, protocol)))
        .or_else(|| sockets.get(&((Ipv4Addr::UNSPECIFIED, dst.port()).into(), protocol)))?;
    let src_ip = if dst.ip().is_loopback() {
        IpAddr::V4(Ipv4Addr::LOCALHOST)
    } else {
        self.nodes.get(&node).expect("node not found").ip.unwrap()
    };
    Some((src_ip, dst_node, ep.clone(), latency))
}

/// Returns the latency of sending a packet. If packet loss, returns `None`.
fn test_link(&mut self, src: NodeId, dst: NodeId) -> Option<Duration> {
    if self.link_clogged(src, dst) || self.rand.gen_bool(self.config.packet_loss_rate) {
        None
    } else {
        self.stat.msg_count += 1;
        // TODO: special value for loopback
        Some(self.rand.gen_range(self.config.send_latency.clone()))
    }
}

1. 单元测试：单元测试关注面比较小，难以发现复杂的问题，所以不是确定性测试主要作用的目标，但确定性模拟器在这里还是起了不少作用，比如测试有关超时的逻辑能瞬间完成。另外单元测试也能反过来验证一些外部系统包装（如 etcd 模拟器）的实现正确与否

2. E2E 测试：E2E 测试中涵盖了系统的各个模块，更容易出现错误。RisingWave 架构复杂，涉及各种服务



通过 MadSim，可以将上述所有服务运行在模拟器的单线程环境中，使环境构建简单得多，并且基于模拟器时间加速的特性，一轮完整测试只用耗时两分钟，是原先的四分之一
并且能轻松地并行执行测试，如果发生了错误，使用同样的 seed 就可以轻易复现结果，包括修改代码添加日志，也不会影响可复现性

3. 异常测试：E2E 测试主要还是在测试正常情况下的行为，没法完全发挥 MadSim 的作用。在异常测试中，会刻意构造各种故障并验证系统是否仍然能保持正确。在这个过程中发现了很多 bug，得益于模拟器的可复现性，这些问题都能被很快定位和修复

4. 扩容测试：集群配置发生变化时，需要进行重平衡，这个过程也很容易发生错误，特别是叠加异常情况时



在正常测试中，受限于集群和数据规模的问题，测试覆盖面不足。但在模拟器中可以轻松构造较大规模和极端情况下的 case，帮助发现并修复了大量问题

Dropbox Trinity

TigerBeetle & VOPR

• https://docs.tigerbeetle.com/about/performance#single-core-by-design

pub fn main() !void {
    // ...

    while (tick < cli_args.ticks_max_convergence) : (tick += 1) {
        simulator.tick();
        tick_total += 1;
        if (simulator.pending() == null) {
            break;
        }
    }

    // ...
}

pub fn tick(simulator: *Simulator) void {
    simulator.cluster.context = simulator;

    simulator.cluster.tick();
    simulator.tick_requests();
    simulator.tick_crash();
}

while (true) {
    replica.tick();
    if (multiversion != null) multiversion.?.tick();
    try command.io.run_for_ns(constants.tick_ms * std.time.ns_per_ms);
}

• https://docs.tigerbeetle.com/about/internals/lsm

• A Programmer-Friendly I/O Abstraction Over io_uring and kqueue

• Tiger Style

FrostDB & Resonate

runtime: add GORANDSEED to seed go runtime's randomness · polarsignals/go@ea083ca

This helps with deterministic execution. This commit additionally enables randomized scheduling. The runtime needs to be run with GOOS=wasip1 GOARCH=wasm for deterministic executions given an initi...

https://github.com/polarsignals/go/commit/ea083ca4892a62eb229c1886517e1cdb575ee19a#diff-99a8f74dc3dbef74ab6a6792a8e36e17d2196486ef16e9b8199ce9a9e7512183R44-R52

• The One Where DST Finds a Real Bug | Resonate

import (
	"testing"
	"testing/synctest"
	"time"
)

func Test(t *testing.T) {
	synctest.Run(func() {
		before := time.Now()
		time.Sleep(time.Second)
		after := time.Now()
		if d := after.Sub(before); d != time.Second {
			t.Fatalf("took %v", d)
		}
	})
}

Antithesis

Antithesis is a continuous reliability platform that autonomously searches for problems in your software within a simulated environment. Every problem we find can be perfectly reproduced, allowing for efficient debugging of even the most complex problems.

• https://antithesis.com/blog/

• MongoDB 使用 Antithesis 测试存储引擎，核心服务器，同步和升降级功能。发现了一个严重的数据丢失问题：
• Accelerating developers at MongoDB
• Working with Antithesis at MongoDB

• Ethereum 在从 PoW（工作量证明）转向 PoS（权益证明）时使用 Antithesis 进行测试
• Testing the Ethereum merge

• WarpStream 端到端测试了整个 SaaS 系统，而不是局限在单个组件或进程
• Deterministic Simulation Testing for Our Entire SaaS

• CockroachDB 在 Antithesis 上重现并定位了之前被搁置数年的事务并行提交 bug
• Antithesis of a One-in-a-Million Bug: Taming Demonic Nondeterminism

• Hermit: Deterministic Linux for Controlled Testing and Software Bug-finding

总结

Ref

1. What's the big deal about Deterministic Simulation Testing?

2. sled simulation guide (jepsen-proof engineering)

3. Deterministic Simulation: A New Era of Distributed System Testing (Part 1 of 2)

4. Applying Deterministic Simulation: The RisingWave Story (Part 2 of 2)

5. 确定性模拟的背景、原理、框架及应用实例 - RisingWave中文开源社区

6. Testing sync at Dropbox

7. We Put a Distributed Database In the Browser – And Made a Game of It!

8. A Programmer-Friendly I/O Abstraction Over io_uring and kqueue

9. (Mostly) Deterministic Simulation Testing in Go

10. Deterministic Simulation Testing | Resonate

11. Is something bugging you? | Antithesis

12. So you think you want to write a deterministic hypervisor? | Antithesis

13. Your computer can test better than you (and that's a good thing) | Antithesis

14. Debugging in the Multiverse | Ahtithesis

15. Accelerating developers at MongoDB

16. Working with Antithesis at MongoDB

17. Deterministic Simulation Testing for Our Entire SaaS

18. Antithesis of a One-in-a-Million Bug: Taming Demonic Nondeterminism

19. Hermit: Deterministic Linux for Controlled Testing and Software Bug-finding