hungtruongOwolf/deterministic-feed-recovery

# 确定性数据流恢复 **DFR** — 一个故意制造故障的市场数据流，以及将其重新组装的 C++20 客户端。 一个带种子的故障注入器和用于交易所市场数据流的恢复库。每次运行都是其种子的确定性函数，因此一个故障就是一个其他人可以输入并亲自验证的数字。 [](https://github.com/hungtruongOwolf/deterministic-feed-recovery/actions/workflows/ci.yml) [](LICENSE)   **[观看运行过程 →](https://hungtruongowolf.github.io/deterministic-feed-recovery/)** ## 状态 所有九个 namespace 均已实现并完成测试。 | | 内容 | 状态 | |---|---|---| | `dfr::core` | `result`、错误、视图、注入的时钟 | 完成 | | `dfr::wire` | MoldUDP64, IEX-TP, SoupBinTCP 3.00, OUCH 4.2, DEEP 1.0, Glimpse | 完成 | | `dfr::capture` | 读取 pcap，针对真实的 IEX HIST 文件进行回放 | 完成 | | `dfr::chaos` | 带种子的、感知协议的故障注入 | 完成 | | `dfr::recovery` | 仲裁、间隙追踪、重传、快照恢复、一个基于轮询的客户端 | 完成 | | `dfr::venue` | 市场数据发布者、重传与快照设施、基于 SoupBinTCP 会话的 OUCH 订单录入 | 完成 | | `dfr::trace` | 将运行过程记录为 JSONL，以及读取它的查看器 | 完成 | | `dfr::concurrent` | 位于单一线程边界处的无锁 SPSC 环，已完成基准测试 | 完成 | | `dfr::wire::deep` | IEX DEEP 1.0 消息解码，每个偏移量均已针对真实抓包验证 | 完成 | | `dfr::book` | 一个聚合订单簿，以及运行在它之上的 oracle | 完成 | | `dfr::wire::glimpse` | 作为字节的快照协议，通过 SoupBinTCP 提供 | 完成 | **720 个测试在五种配置下通过** —— 断言设置为 paranoid、fast 和 off，以及 AddressSanitizer + UndefinedBehaviorSanitizer + ThreadSanitizer —— 全部开启将警告视为错误，在本地 Apple Clang 和 CI 中的 Linux Clang 上运行。在合成流和真实抓包数据之上均实现了端到端的 oracle。 ## 需要消息层的这个不变量 在这些消息具有实际意义之前，这个项目能证明的最有力的一点仅仅是关于*簿记*的：每个序列号都精确到达一次。这是必要的，但并不是交易系统需要听到的。它需要的是关于内容的陈述，现在它已被断言： 现在它已显示在提交的 trace 中，而不仅仅是在测试中。Act I 保留了这两条线路，而 Act II 丢失了一条，两者的最终结果都是**相同的订单簿** —— 买价 20.8700，卖价 20.9500，成交 6,831 股。Act III 永久丢失了数据，最终结果不同：231 股。查看器在运行过程旁边绘制了盘口数据，并且 `npm run check` 对已提交的数据断言了这种相等性和差异性。 这是一个更为严格的不变量。如果恢复机制以错误的顺序传递了正确的消息、两次应用了修复，或者丢弃了大小为零的删除操作，它都会失败 —— 这些都是序列号计数无法察觉的。 编写它的过程发现了一些问题，而且不是在库中发现的。第一个版本按照客户端*传递*它们的顺序应用消息，结果订单簿不匹配：相同的 600 条消息，相同的更新次数，不同的订单簿。恢复机制是对的。**当一个缺口处于打开状态时，客户端会故意继续传递后续的消息** —— 因为在遇到缺口时停滞会将一次丢包转变为一次停机 —— 因此修复会在较高序列号之后到达。聚合订单簿是“后写覆盖”（last-write-wins）的，因此第二应用较旧的更新会永久地在那个价格上留下错误的数量。 因此，填补缺口的数据流的正确消费者必须按照**序列顺序而非到达顺序**进行应用。客户端通过为其移交的所有内容编号使这成为可能，但却没有任何提示警告你。`book_oracle_test.cpp` 保留了一个测试，展示了天真版本如何产生错误的订单簿，因为一个没人演示的危险就是每个人都会重新发现的危险。 ### DEEP 字段偏移量的来源 并非规范 —— 它的在线 URL 提供的是一个存根，就像 IEX-TP 的一样。在编写任何代码之前，真实的 IEX HIST 抓包（2017-08-26，20,145 个数据包，48,635 条消息）已经按类型和长度进行了制表，这提供了十一种消息类型及其观察到的确切大小作为既定事实。然后从语义上确认了这些布局： - 每个时间戳都解码为抓包当天的日期，即 2017-08-26； - 这些代码是真实的股票代码 —— WWE, IEXT, VIAV； - 在同一时刻对同一代码在 **$20.8900** 有一个买方价格层级，在 **$20.9000** 有一个卖方价格层级：一个有效的一美分价差，错误的 price offset 不可能偶然产生这种结果； - 一份成交报告（Trade Report）价格为 $20.9000 —— 即卖价 —— 数量为 100 股。 抓包中的所有 48,635 条消息全部解码成功，**未知类型为零，长度不匹配为零**。 ## 代价 | | | |---|---| | 端到端接收单个数据包 | **~41 ns**，单核约 24 M 数据包/秒 | | 将消息批量移交给另一个核心 | **~13 ns**，约 76 M 消息/秒 | | 启动后的内存分配 | **0**，通过替换全局 `operator new` 统计 | | paranoid 断言，最紧凑的操作 | 3× | | paranoid 断言，现实中的热点路径 | **低于噪声基准** | 最后一行是有用的那一行：**到处都是边界检查的构建版本是可以交付的。** 它们在 header decode（几乎全是检查操作）上消耗了 3 倍的代价，而在主导数据摄取的路径上没有任何可测量的开销。 未测量，在此处也无法测量：tick-to-trade、NIC-to-NIC、任何网络延迟 —— 笔记本电脑或云虚拟机上没有 NIC 时间戳，也没有 PMU 计数器。请参阅 [docs/BENCHMARKS.md](docs/BENCHMARKS.md) 了解在此过程中发现的三个测量错误，并参阅 [docs/CONCURRENCY.md](docs/CONCURRENCY.md) 了解**ThreadSanitizer 如何通过了一个故意损坏的 ring** 的实验，以及在 arm64 上的属性测试如何在 12 次测试中 12 次捕获该错误的。 故意不构建的：撮合引擎。撮合是其他 1,071 个 C++ 仓库已经在实现的部分；开源世界所缺少的是围绕它的协议行为，因此执行由调用者驱动，而宿主的工作是保持记账准确并发出正确的消息。有关此论点，请参阅 `include/dfr/venue/order_entry.hpp`。 ## 试用 ``` cmake -S . -B build/dev && cmake --build build/dev -j8 # 一个 order-entry session，wire 的两个方向。 # 最后三行是关键：客户端自己计算了 sequence。 ./build/dev/tools/session # 全部 720 个测试，assertions 设为 paranoid。 ctest --test-dir build/dev # 一次运行记录为 JSONL。相同的 seed 产生 byte-identical 的输出；不同的 seed 则不会。 ./build/dev/tools/trace --seed 4711 --messages 300 --faults 6 --out /tmp/a.jsonl ./build/dev/tools/trace --seed 4711 --messages 300 --faults 6 --out /tmp/b.jsonl && diff /tmp/a.jsonl /tmp/b.jsonl # 针对真实的 capture，如果你有一个 IEX HIST pcap： ./build/dev/tools/inspect ./build/dev/tools/verify --seed 4711 --faults 40 ``` 或者[在浏览器中运行](https://hungtruongowolf.github.io/deterministic-feed-recovery/) —— 该页面将此库编译为 WebAssembly，因此你输入的种子会触发一次真实的运行。而不是记录的回放。 ``` # 浏览器 build，以及至关重要的检查：它是否产生与 terminal 相同的 bytes？ ./scripts/build-wasm.sh ./scripts/check-wasm.sh dev ``` 两款编译器，两个目标平台，同一个种子。六种运行形态 —— 一条线路、两条线路、glimpse 竞争、两个会话脚本 —— 逐字节进行比对。如果它们之间存在任何差异，说明库中的某些内容依赖于其平台，那么“确定性”就只是一个词语而不是一种属性，因此 CI 会在此情况下报错失败。 ## 预期目标 在 namespace `dfr` 下的三个组件，按以下顺序构建： 1. **`dfr::chaos`** —— 一个带种子、感知协议的故障注入器，用于 MoldUDP64 / IEX-TP 组播流。突发丢包、乱序、重复、A/B 线路分歧、序列重置、快照/增量竞争。这是 `(seed, packet_index)` 的确定性函数，因此任何故障都可以精确重放。 2. **`dfr::recovery`** —— 一个能够在上述所有情况下生存下来的客户端库：间隙检测、重传请求、基于快照的订单簿重建、A/B 仲裁、NAK 抑制。 3. **`dfr::venue`** —— 一个使用真实通信协议的模拟交易所，以便可以针对表现得像真实交易所而非存根的行为来测试 `dfr::recovery`。通过 IEX-TP 输出市场数据、可能拒绝请求的重传和快照机制，以及引入 OUCH 4.2 订单录入。 此处的“确定性”是对实现的约束，而不是对其质量的宣称：没有挂钟时间、没有未加种子的随机性、没有基于指针的排序，且为核心采用单线程，因此可以从一个种子加上构建指纹中重现失败的运行。 ## 为什么选择这个问题 在 2026-07-29 搜索了 GitHub： | 查询条件 | 仓库数 | |---|---| | `"order book" language:C++ created:>2026-01-01` | 1,071 | | ……其中，星标 ≥5 的 | 7 | | `"gap fill" multicast market data` | **0** | | `glimpse soupbintcp` | **0** | | `feed arbitration multicast market data` | 1 (0 stars) | 数据流*解码器*已经饱和。恢复路径 —— 即仅在出现问题时才运行的代码 —— 没有任何开源实现，并且也没有工具可以对其进行测试。 支持“这正是 bug 所在”的证据：Yuan 等人（OSDI'14）发现，92% 的灾难性系统故障来源于对软件中明确发出的错误的不当处理，且其中 58% 本可以通过对错误处理代码的简单测试来捕获。 ## 400 个种子扫描的实际结果 页面报告了两个属性，之所以报告它们，是因为它们是经过测量后保留下来的结果，而不是听起来不错的夸夸其谈。尝试了早期的两项声明，但都是错误的： | 声明 | 成立情况 | |---|---| | 没有任何内容被传递两次 | **400/400** | | 在最后一道防线响应太晚之前，没有任何内容丢失 | **400/400** | | 两条线路意味着需要往返传输的消息更少 | 399/400 | | 每个 act 都被迫比上一个更深入一层 | 经常失败 | 这两次失败才是有趣的部分。 **“每个 act 都更深入”** 在任何种子上都是错误的，只要第二个 act 的故障碰巧由第一个 act 也需要的重传来填补 —— 例如在种子为 7 且有六个故障的情况下，第二个 act 从未请求任何内容。 **“两条线路意味着更少的往返请求”** 以两种不同的方式失效。在种子 114 处，第二条线路填补了漏洞的*中间*，将一个 27 条消息的间隙拆分为 9 条和 15 条：*更多*的请求，*更少*的消息。而在种子 186 处，两条线路比一条线路需要回传更多的消息，因为注入器分别损坏了每条线路 —— 冗余并不是单线故障的严格子集，它是另一种不同的故障。 因此，运行摘要中在 `retransmit_requests` 旁边增加了 `retransmit_messages`，因为这两者回答的是不同的问题，并且页面将第三行陈述为一种趋势而不是一条定律。这种区分正是将“诚实账本”应用于我想做出的声明的全部意义所在。 ## 针对真实抓包数据的验证 IEX-TP 的字段偏移量是从一份其在线 URL 现在只提供“此文档已移动”存根的规范中转录的，因此它们只有单一数据源。它们已经通过 `tools/inspect` 对照真实的 IEX HIST 数据进行了检查： | 抓包文件 | 格式 | 帧数 | 消息数 | VLAN | 链断开 | |---|---|---|---|---|---| | `20170826` DEEP，整个文件 | classic pcap | 20,145 | 48,635 | 1013 | **0** | | `20191224` DEEP，gzip 的前 12 MB | pcapng | 348,103 | 380,611 | 无 | **0** | | `20170923` DEEP，整个文件 | pcapng | 27,827 | 60,647 | 无 | **0** | | `20180929` DEEP，整个文件 | pcapng | 23,258 | 59,239 | 无 | **0** | | `20190907` DE，整个文件 | pcapng | 21,047 | 60,043 | 无 | **0** | | `20241001` DEEP，整个文件 | classic pcap | 20,198 | 59,367 | 无 | **0** | 跨越 460,578 个真实数据包且零链断开，意味着 IEX-TP 的所有三个冗余链在每一个数据包上都成立：序列号链、流偏移链，以及块框架完全符合声明的有效负载长度。如果 Stream Offset 或 Payload Length 的偏移量有误，在处理第二个数据包时就会发生断链。 最后四行是重新验证，是在更改了 `chain_checker` 之后运行的 —— 因为一个“验证过一次”然后被编辑过的解码器，就是一个尚未被验证的解码器。 ``` $ curl -s 'https://iextrading.com/api/1.0/hist?date=20170826' | python3 -m json.tool $ curl -L -o deep.pcap.gz '' && gunzip deep.pcap $ inspect deep.pcap ``` ## 端到端 oracle `tools/verify` 将带种子的故障计划注入到真实抓包中，通过 `dfr::recovery` 运行受损的数据流，并利用未受损的原始数据作为重传服务器进行播放。它检查两个属性，如果其中任何一个失败，则非零退出： - **检测** —— 客户端报告缺失的消息正好是那些从未到达的消息，不多也不少； - **修复** —— 借助重传服务器，最终没有缺失任何内容，并且每条消息都只被精确传递了一次。 ``` $ verify deep_20170826.pcap --seed 4711 IEX-TP packets usable 20145 messages delivered 48635 retransmits served 11 reported missing 0 actually never arrived 0 delivered twice 0 detection exact yes every message once yes accounting balances yes fully repaired yes ``` 这两个属性在 **50 次运行**中均成立 —— 包含从 2017 年到 2024 年的五次抓包，涵盖两种容器格式，每次十个种子。消息计数与 `inspect` 对同一文件的独立计数相匹配，这是对该记账结果的第二重确认。 相同的 oracle 也在合成数据包（`tests/integration/recovery_oracle_test.cpp`）的 CI 中运行，在那里它运行速度快、自包含，并且会在破坏了某些功能的提交上失败。合成流携带了心跳包，因为没有心跳的流曾让一个真实的缺陷漏网：心跳在未推进仲裁器水位的情况下推进了追踪器的预期，而填补由此产生的漏洞的重传被计算了两次。只有真实数据的运行才发现它。 这次练习发现了三件事： - **VLAN 标签在整个语料库中并不一致。** 2017-08-26 文件带有 VLAN 1013；采样的其他每个文件都不带标签。只针对其中一种情况进行测试的读取器在遇到另一种情况时就会损坏，并将故障报告为“此文件不包含 IP 流量”。 - **没有需要寻找的格式切换开关。** 最初的猜测是日期边界，因为从 2017-07-03 开始的交易日是 pcapng，而 2017-08-26 的周六文件是 classic pcap。进一步采样彻底打破了这一理论：七年后的 `20241001` 也是 classic pcap，其 snaplen 为 262,144 而不是 65,535。格式仅仅是因文件而异，因此工具不能通过日期或时代来选择读取器 —— 它必须尝试一种并回退到另一种，这就是 `inspect` 所做的。 - **组播组、端口和会话 ID 也都各不相同**（2017 年是 233.215.21.4:10378，2024 年是 233.215.21.242:32001）。任何从某次抓包硬编码的内容，都是只能在一个文件上工作的解析器。 ## 记录的运行 `tools/trace` 记录了整个运行过程 —— 交易所发布、注入的故障、客户端的每一个决定 —— 每行一个 JSON 对象。一次 trace 是种子的确定性函数，因此它被提交在代码旁边而不是重新生成：`traces/` 目录保存了两个，将新的运行与它们进行 `diff` 就是一份人类可读的行为回归测试。 ``` $ trace --seed 4711 --messages 300 --out run.jsonl $ trace --glimpse --out glimpse.jsonl # loses the Glimpse race on purpose ``` 每个事件都带有*生成的*客户端状态和关键数据。这种冗余是故意的：查看器必须能够通过读取一行来绘制任意时刻，因为如果查看器从事件序列中重建状态，那它就会成为状态机的第二种实现 —— 当两者不一致时，图像将是错误的，且无迹可寻。 header 还带有一个生成的 `limits` 数组：即这次运行测量了哪些声明，以及哪些在可用硬件上无法测量。它位于数据中而不是散文中，因此它不会偏离运行实际执行的操作。 ## 查看器 `viewer/` 是一个静态页面，它读取 trace 并将其绘制出来：数据包轴上的时间擦洗器、贯穿整个运行过程的客户端状态条带、绘制在序列轴上的 Glimpse 竞争、冗余对的每条线路健康状况，以及诚实账本。 **在线查看：** ``` cd viewer && npm install && npm run dev ``` 它**不包含任何领域逻辑**。绘制的每个数字都是 trace 已经包含的字段；没有任何东西是重新计算出来的。如果查看器从事件序列中重建状态，那它将是用另一种语言实现的状态机，当两者不一致时，图像将是错误的，且无迹可寻 —— 这正是这个库存在是为了防止的失败，却在为显示它而构建的工具中重新引入了。 `scripts/regenerate-traces.sh` 刷新已提交的测试固件；随后的 `git diff traces/` 就是一份行为回归报告。 ## 测试数据 真实的通信格式抓包，免费且无需注册： - **IEX HIST** (`iextrading.com/api/1.0/hist`) —— 包含 802.1Q VLAN + IPv4 组播 + IEX-TP 的 pcap。主要语料库。 - **`Open-Markets-Initiative/omi-data-pcaps`** —— 正版的 NASDAQ MoldUDP64 组播 pcap。 - **B3 `MBO_EQT_Incremental_FeedA/FeedB`** —— 目前找到的唯一免费的 A/B 冗余抓包对。 请注意，NASDAQ 自己的免费样本 (`emi.nasdaq.com`) 是 BinaryFILE 格式：2 字节长度前缀加上原始 ITCH，整个传输层已被剥离。它们不包含 MoldUDP64 header、没有 session ID 也没有数据包序列号，因此如果不先合成传输层，就无法用它们来测试间隙处理 —— 到了那一步，测试的其实就是合成器了。 ## 既定限制 - 所有的开发和测量都在云虚拟机上进行。没有 PMU 计数器，没有 Intel PT，没有 NIC 硬件时间戳，也没有可靠的亚微秒级时钟。**这里的任何计时数字都是软件时间戳，应当以此方式来解读。** 这个项目关注的是正确性和确定性，而不是 tick-to-trade 延迟。 - AWS 在普通的 VPC 上不支持组播。本地测试使用的是 `veth` + network namespace + `tc netem`，因此对 IGMP snooping 和 querier 行为 —— 即导致数据流静默的常见运维原因 —— 进行的是推理分析，而不是重现。 ## 构建 ``` cmake --preset dev # paranoid assertions, no optimisation cmake --build --preset dev ctest --preset dev ``` 其他预设：`release`（优化版，断言仍保持在 fast 级别），`bench`（关闭断言，用于衡量断言的代价），`asan`，`tsan`。 **直到 `dev`、`release`、`bench`、`asan` 和 `tsan` 这五个预设全部通过，更改才算完成。** 这个矩阵不是摆设：此仓库中的两个缺陷在某一种配置下是不可见的，但在另一种配置下却是致命的 —— 一个是指向已销毁临时对象的悬空 `span`，而 `-O0` 还没有重用其栈空间；另一个是一个断言，测试某个被禁用的断言是否会评估其条件，而关闭断言的构建将此报告为未使用的声明。 **矩阵无法看到的东西：编译器。** 它改变优化、断言级别和 sanitizers，但全部都在一个工具链上。在它的第一次运行中，CI 发现了五个在 Linux Clang 下是错误、但在 Apple Clang 下却静默通过的调用点 —— 一个指定初始化程序（designated initialiser）跳过了某个字段，`-Wmissing-field-initializers` 由其中之一实现而另一个没有。这四个本地配置不可能捕获到它，而一个略去其无法看见之物的验证故事，正是本项目在其他地方所批评的那种过度声称。 `.github/workflows/ci.yml` 在 Linux Clang 下运行相同的五个预设，**并在 GCC 14 下运行整套测试套件**，对每个解码器进行模糊测试，检查 WebAssembly 构建是否与原生构建逐字节匹配，检查提交的 trace 是否仍然能逐字节重现，并构建查看器。目前仅限于 Clang，因为这台机器没有真正的 GCC —— Apple Clang 会响应 `g++` —— 而一个 GCC 任务将会是一个在提交前没有任何人验证过的配置。 ## 文档 - `RESEARCH-DOSSIER.md` —— 问题是是如何被选定的，以及排除了哪些内容。 - `BUILD-GUIDE.md` —— 数据源、协议规范、测试目标、确定性风险、学习路径。 - `LUAN-GIAI-TIENG-VIET.md` —— 相同的推理链的越南语版本。 - `docs/DESIGN.md` —— 机制选择，每一项都附有证明其有效的真实项目和文件，以及为什么现有的两个开源 MoldUDP64 库不能满足这些要求。 - `docs/STYLE.md` —— 关于注释、断言、文件大小、聚合默认值、README 和提交的内部规则，根据对 Linux、SQLite、TigerBeetle、simdjson、quill 等项目的注释和断言密度的测量进行了校准。 - `viewer/README.md` —— 查看器遵循的唯一规则，以及为什么它不包含领域逻辑。 - `traces/` —— 记录的运行过程，作为固件提交。随后运行 `scripts/regenerate-traces.sh`，然后 `git diff traces/` 就是一份行为回归报告。 ## 许可证 [MIT](LICENSE)。一个没有许可证文件的作品集仓库在法律上是*保留所有权利*的 —— 任何人都不得复制代码片段、引入其 header，或在商业环境中安全地从中学习，并且某些法务部门甚至完全不允许工程师打开它。这与它存在的初衷背道而驰，因此它采用了与其所学习的库相同的许可方式：rigtorp 的 SPSCQueue 和 max0x7ba 的 atomic_queue 都是 MIT 许可证。

标签：AI工具, Bash脚本, C++20, 容错与恢复, 故障注入, 网络协议解析, 行情数据, 订单簿, 金融科技